/ Check-in [bcbc7152]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Import the experimental parse-tree explainer, with fixes, from the tree-explain branch. Disabled by default. Use SQLITE_ENABLE_TREE_EXPLAIN to turn it on.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: bcbc7152d49107afa926c8950360c61a6cf3d244
User & Date: drh 2011-12-10 15:55:01
Original Comment: Import the experimental parse-tree explainer, with fixes, from the tree-explain branch.
Context
2011-12-10
17:17
Allow UNION ALL compounds to be promoted up to replace a simple wrapper SELECT even if the compounds are joins. check-in: 3d4b4f4f user: drh tags: trunk
15:55
Import the experimental parse-tree explainer, with fixes, from the tree-explain branch. Disabled by default. Use SQLITE_ENABLE_TREE_EXPLAIN to turn it on. check-in: bcbc7152 user: drh tags: trunk
14:44
Merge the latest trunk changes into tree-explain branch. Closed-Leaf check-in: 1a360da0 user: drh tags: tree-explain
13:49
Always use _msize() to get memory allocation sizes on windows, without having to do anything special in the makefile. check-in: 256e27bd user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/expr.c.

  2944   2944       sqlite3VdbeAddOp2(v, OP_Copy, inReg, iMem);
  2945   2945       pExpr->iTable = iMem;
  2946   2946       pExpr->op2 = pExpr->op;
  2947   2947       pExpr->op = TK_REGISTER;
  2948   2948     }
  2949   2949     return inReg;
  2950   2950   }
         2951  +
         2952  +#if defined(SQLITE_ENABLE_TREE_EXPLAIN)
         2953  +/*
         2954  +** Generate a human-readable explanation of an expression tree.
         2955  +*/
         2956  +void sqlite3ExplainExpr(Vdbe *pOut, Expr *pExpr){
         2957  +  int op;                   /* The opcode being coded */
         2958  +  const char *zBinOp = 0;   /* Binary operator */
         2959  +  const char *zUniOp = 0;   /* Unary operator */
         2960  +  if( pExpr==0 ){
         2961  +    op = TK_NULL;
         2962  +  }else{
         2963  +    op = pExpr->op;
         2964  +  }
         2965  +  switch( op ){
         2966  +    case TK_AGG_COLUMN: {
         2967  +      sqlite3ExplainPrintf(pOut, "AGG{%d:%d}",
         2968  +            pExpr->iTable, pExpr->iColumn);
         2969  +      break;
         2970  +    }
         2971  +    case TK_COLUMN: {
         2972  +      if( pExpr->iTable<0 ){
         2973  +        /* This only happens when coding check constraints */
         2974  +        sqlite3ExplainPrintf(pOut, "COLUMN(%d)", pExpr->iColumn);
         2975  +      }else{
         2976  +        sqlite3ExplainPrintf(pOut, "{%d:%d}",
         2977  +                             pExpr->iTable, pExpr->iColumn);
         2978  +      }
         2979  +      break;
         2980  +    }
         2981  +    case TK_INTEGER: {
         2982  +      if( pExpr->flags & EP_IntValue ){
         2983  +        sqlite3ExplainPrintf(pOut, "%d", pExpr->u.iValue);
         2984  +      }else{
         2985  +        sqlite3ExplainPrintf(pOut, "%s", pExpr->u.zToken);
         2986  +      }
         2987  +      break;
         2988  +    }
         2989  +#ifndef SQLITE_OMIT_FLOATING_POINT
         2990  +    case TK_FLOAT: {
         2991  +      sqlite3ExplainPrintf(pOut,"%s", pExpr->u.zToken);
         2992  +      break;
         2993  +    }
         2994  +#endif
         2995  +    case TK_STRING: {
         2996  +      sqlite3ExplainPrintf(pOut,"%Q", pExpr->u.zToken);
         2997  +      break;
         2998  +    }
         2999  +    case TK_NULL: {
         3000  +      sqlite3ExplainPrintf(pOut,"NULL");
         3001  +      break;
         3002  +    }
         3003  +#ifndef SQLITE_OMIT_BLOB_LITERAL
         3004  +    case TK_BLOB: {
         3005  +      sqlite3ExplainPrintf(pOut,"%s", pExpr->u.zToken);
         3006  +      break;
         3007  +    }
         3008  +#endif
         3009  +    case TK_VARIABLE: {
         3010  +      sqlite3ExplainPrintf(pOut,"VARIABLE(%s,%d)",
         3011  +                           pExpr->u.zToken, pExpr->iColumn);
         3012  +      break;
         3013  +    }
         3014  +    case TK_REGISTER: {
         3015  +      sqlite3ExplainPrintf(pOut,"REGISTER(%d)", pExpr->iTable);
         3016  +      break;
         3017  +    }
         3018  +    case TK_AS: {
         3019  +      sqlite3ExplainExpr(pOut, pExpr->pLeft);
         3020  +      break;
         3021  +    }
         3022  +#ifndef SQLITE_OMIT_CAST
         3023  +    case TK_CAST: {
         3024  +      /* Expressions of the form:   CAST(pLeft AS token) */
         3025  +      const char *zAff = "unk";
         3026  +      switch( sqlite3AffinityType(pExpr->u.zToken) ){
         3027  +        case SQLITE_AFF_TEXT:    zAff = "TEXT";     break;
         3028  +        case SQLITE_AFF_NONE:    zAff = "NONE";     break;
         3029  +        case SQLITE_AFF_NUMERIC: zAff = "NUMERIC";  break;
         3030  +        case SQLITE_AFF_INTEGER: zAff = "INTEGER";  break;
         3031  +        case SQLITE_AFF_REAL:    zAff = "REAL";     break;
         3032  +      }
         3033  +      sqlite3ExplainPrintf(pOut, "CAST-%s(", zAff);
         3034  +      sqlite3ExplainExpr(pOut, pExpr->pLeft);
         3035  +      sqlite3ExplainPrintf(pOut, ")");
         3036  +      break;
         3037  +    }
         3038  +#endif /* SQLITE_OMIT_CAST */
         3039  +    case TK_LT:      zBinOp = "LT";     break;
         3040  +    case TK_LE:      zBinOp = "LE";     break;
         3041  +    case TK_GT:      zBinOp = "GT";     break;
         3042  +    case TK_GE:      zBinOp = "GE";     break;
         3043  +    case TK_NE:      zBinOp = "NE";     break;
         3044  +    case TK_EQ:      zBinOp = "EQ";     break;
         3045  +    case TK_IS:      zBinOp = "IS";     break;
         3046  +    case TK_ISNOT:   zBinOp = "ISNOT";  break;
         3047  +    case TK_AND:     zBinOp = "AND";    break;
         3048  +    case TK_OR:      zBinOp = "OR";     break;
         3049  +    case TK_PLUS:    zBinOp = "ADD";    break;
         3050  +    case TK_STAR:    zBinOp = "MUL";    break;
         3051  +    case TK_MINUS:   zBinOp = "SUB";    break;
         3052  +    case TK_REM:     zBinOp = "REM";    break;
         3053  +    case TK_BITAND:  zBinOp = "BITAND"; break;
         3054  +    case TK_BITOR:   zBinOp = "BITOR";  break;
         3055  +    case TK_SLASH:   zBinOp = "DIV";    break;
         3056  +    case TK_LSHIFT:  zBinOp = "LSHIFT"; break;
         3057  +    case TK_RSHIFT:  zBinOp = "RSHIFT"; break;
         3058  +    case TK_CONCAT:  zBinOp = "CONCAT"; break;
         3059  +
         3060  +    case TK_UMINUS:  zUniOp = "UMINUS"; break;
         3061  +    case TK_UPLUS:   zUniOp = "UPLUS";  break;
         3062  +    case TK_BITNOT:  zUniOp = "BITNOT"; break;
         3063  +    case TK_NOT:     zUniOp = "NOT";    break;
         3064  +    case TK_ISNULL:  zUniOp = "ISNULL"; break;
         3065  +    case TK_NOTNULL: zUniOp = "NOTNULL"; break;
         3066  +
         3067  +    case TK_AGG_FUNCTION:
         3068  +    case TK_CONST_FUNC:
         3069  +    case TK_FUNCTION: {
         3070  +      ExprList *pFarg;       /* List of function arguments */
         3071  +      if( ExprHasAnyProperty(pExpr, EP_TokenOnly) ){
         3072  +        pFarg = 0;
         3073  +      }else{
         3074  +        pFarg = pExpr->x.pList;
         3075  +      }
         3076  +      sqlite3ExplainPrintf(pOut, "%sFUNCTION:%s(",
         3077  +                           op==TK_AGG_FUNCTION ? "AGG_" : "",
         3078  +                           pExpr->u.zToken);
         3079  +      if( pFarg ){
         3080  +        sqlite3ExplainExprList(pOut, pFarg);
         3081  +      }
         3082  +      sqlite3ExplainPrintf(pOut, ")");
         3083  +      break;
         3084  +    }
         3085  +#ifndef SQLITE_OMIT_SUBQUERY
         3086  +    case TK_EXISTS: {
         3087  +      sqlite3ExplainPrintf(pOut, "EXISTS(");
         3088  +      sqlite3ExplainSelect(pOut, pExpr->x.pSelect);
         3089  +      sqlite3ExplainPrintf(pOut,")");
         3090  +      break;
         3091  +    }
         3092  +    case TK_SELECT: {
         3093  +      sqlite3ExplainPrintf(pOut, "(");
         3094  +      sqlite3ExplainSelect(pOut, pExpr->x.pSelect);
         3095  +      sqlite3ExplainPrintf(pOut, ")");
         3096  +      break;
         3097  +    }
         3098  +    case TK_IN: {
         3099  +      sqlite3ExplainPrintf(pOut, "IN(");
         3100  +      sqlite3ExplainExpr(pOut, pExpr->pLeft);
         3101  +      sqlite3ExplainPrintf(pOut, ",");
         3102  +      if( ExprHasProperty(pExpr, EP_xIsSelect) ){
         3103  +        sqlite3ExplainSelect(pOut, pExpr->x.pSelect);
         3104  +      }else{
         3105  +        sqlite3ExplainExprList(pOut, pExpr->x.pList);
         3106  +      }
         3107  +      sqlite3ExplainPrintf(pOut, ")");
         3108  +      break;
         3109  +    }
         3110  +#endif /* SQLITE_OMIT_SUBQUERY */
         3111  +
         3112  +    /*
         3113  +    **    x BETWEEN y AND z
         3114  +    **
         3115  +    ** This is equivalent to
         3116  +    **
         3117  +    **    x>=y AND x<=z
         3118  +    **
         3119  +    ** X is stored in pExpr->pLeft.
         3120  +    ** Y is stored in pExpr->pList->a[0].pExpr.
         3121  +    ** Z is stored in pExpr->pList->a[1].pExpr.
         3122  +    */
         3123  +    case TK_BETWEEN: {
         3124  +      Expr *pX = pExpr->pLeft;
         3125  +      Expr *pY = pExpr->x.pList->a[0].pExpr;
         3126  +      Expr *pZ = pExpr->x.pList->a[1].pExpr;
         3127  +      sqlite3ExplainPrintf(pOut, "BETWEEN(");
         3128  +      sqlite3ExplainExpr(pOut, pX);
         3129  +      sqlite3ExplainPrintf(pOut, ",");
         3130  +      sqlite3ExplainExpr(pOut, pY);
         3131  +      sqlite3ExplainPrintf(pOut, ",");
         3132  +      sqlite3ExplainExpr(pOut, pZ);
         3133  +      sqlite3ExplainPrintf(pOut, ")");
         3134  +      break;
         3135  +    }
         3136  +    case TK_TRIGGER: {
         3137  +      /* If the opcode is TK_TRIGGER, then the expression is a reference
         3138  +      ** to a column in the new.* or old.* pseudo-tables available to
         3139  +      ** trigger programs. In this case Expr.iTable is set to 1 for the
         3140  +      ** new.* pseudo-table, or 0 for the old.* pseudo-table. Expr.iColumn
         3141  +      ** is set to the column of the pseudo-table to read, or to -1 to
         3142  +      ** read the rowid field.
         3143  +      */
         3144  +      sqlite3ExplainPrintf(pOut, "%s(%d)", 
         3145  +          pExpr->iTable ? "NEW" : "OLD", pExpr->iColumn);
         3146  +      break;
         3147  +    }
         3148  +    case TK_CASE: {
         3149  +      sqlite3ExplainPrintf(pOut, "CASE(");
         3150  +      sqlite3ExplainExpr(pOut, pExpr->pLeft);
         3151  +      sqlite3ExplainPrintf(pOut, ",");
         3152  +      sqlite3ExplainExprList(pOut, pExpr->x.pList);
         3153  +      break;
         3154  +    }
         3155  +#ifndef SQLITE_OMIT_TRIGGER
         3156  +    case TK_RAISE: {
         3157  +      const char *zType = "unk";
         3158  +      switch( pExpr->affinity ){
         3159  +        case OE_Rollback:   zType = "rollback";  break;
         3160  +        case OE_Abort:      zType = "abort";     break;
         3161  +        case OE_Fail:       zType = "fail";      break;
         3162  +        case OE_Ignore:     zType = "ignore";    break;
         3163  +      }
         3164  +      sqlite3ExplainPrintf(pOut, "RAISE-%s(%s)", zType, pExpr->u.zToken);
         3165  +      break;
         3166  +    }
         3167  +#endif
         3168  +  }
         3169  +  if( zBinOp ){
         3170  +    sqlite3ExplainPrintf(pOut,"%s(", zBinOp);
         3171  +    sqlite3ExplainExpr(pOut, pExpr->pLeft);
         3172  +    sqlite3ExplainPrintf(pOut,",");
         3173  +    sqlite3ExplainExpr(pOut, pExpr->pRight);
         3174  +    sqlite3ExplainPrintf(pOut,")");
         3175  +  }else if( zUniOp ){
         3176  +    sqlite3ExplainPrintf(pOut,"%s(", zUniOp);
         3177  +    sqlite3ExplainExpr(pOut, pExpr->pLeft);
         3178  +    sqlite3ExplainPrintf(pOut,")");
         3179  +  }
         3180  +}
         3181  +#endif /* defined(SQLITE_ENABLE_TREE_EXPLAIN) */
         3182  +
         3183  +#if defined(SQLITE_ENABLE_TREE_EXPLAIN)
         3184  +/*
         3185  +** Generate a human-readable explanation of an expression list.
         3186  +*/
         3187  +void sqlite3ExplainExprList(Vdbe *pOut, ExprList *pList){
         3188  +  int i;
         3189  +  if( pList==0 || pList->nExpr==0 ){
         3190  +    sqlite3ExplainPrintf(pOut, "(empty-list)");
         3191  +    return;
         3192  +  }else if( pList->nExpr==1 ){
         3193  +    sqlite3ExplainExpr(pOut, pList->a[0].pExpr);
         3194  +  }else{
         3195  +    sqlite3ExplainPush(pOut);
         3196  +    for(i=0; i<pList->nExpr; i++){
         3197  +      sqlite3ExplainPrintf(pOut, "item[%d] = ", i);
         3198  +      sqlite3ExplainPush(pOut);
         3199  +      sqlite3ExplainExpr(pOut, pList->a[i].pExpr);
         3200  +      sqlite3ExplainPop(pOut);
         3201  +      if( i<pList->nExpr-1 ){
         3202  +        sqlite3ExplainNL(pOut);
         3203  +      }
         3204  +    }
         3205  +    sqlite3ExplainPop(pOut);
         3206  +  }
         3207  +}
         3208  +#endif /* SQLITE_DEBUG */
  2951   3209   
  2952   3210   /*
  2953   3211   ** Return TRUE if pExpr is an constant expression that is appropriate
  2954   3212   ** for factoring out of a loop.  Appropriate expressions are:
  2955   3213   **
  2956   3214   **    *  Any expression that evaluates to two or more opcodes.
  2957   3215   **

Changes to src/main.c.

  2931   2931       ** subsequent calls to localtime() and variants fail. If onoff is zero,
  2932   2932       ** undo this setting.
  2933   2933       */
  2934   2934       case SQLITE_TESTCTRL_LOCALTIME_FAULT: {
  2935   2935         sqlite3GlobalConfig.bLocaltimeFault = va_arg(ap, int);
  2936   2936         break;
  2937   2937       }
         2938  +
         2939  +#if defined(SQLITE_ENABLE_TREE_EXPLAIN)
         2940  +    /*   sqlite3_test_control(SQLITE_TESTCTRL_EXPLAIN_STMT,
         2941  +    **                        sqlite3_stmt*,const char**);
         2942  +    **
         2943  +    ** If compiled with SQLITE_ENABLE_TREE_EXPLAIN, each sqlite3_stmt holds
         2944  +    ** a string that describes the optimized parse tree.  This test-control
         2945  +    ** returns a pointer to that string.
         2946  +    */
         2947  +    case SQLITE_TESTCTRL_EXPLAIN_STMT: {
         2948  +      sqlite3_stmt *pStmt = va_arg(ap, sqlite3_stmt*);
         2949  +      const char **pzRet = va_arg(ap, const char**);
         2950  +      *pzRet = sqlite3VdbeExplanation((Vdbe*)pStmt);
         2951  +      break;
         2952  +    }
         2953  +#endif
  2938   2954   
  2939   2955     }
  2940   2956     va_end(ap);
  2941   2957   #endif /* SQLITE_OMIT_BUILTIN_TEST */
  2942   2958     return rc;
  2943   2959   }
  2944   2960   

Changes to src/parse.y.

   390    390   %endif  SQLITE_OMIT_VIEW
   391    391   
   392    392   //////////////////////// The SELECT statement /////////////////////////////////
   393    393   //
   394    394   cmd ::= select(X).  {
   395    395     SelectDest dest = {SRT_Output, 0, 0, 0, 0};
   396    396     sqlite3Select(pParse, X, &dest);
          397  +  sqlite3ExplainBegin(pParse->pVdbe);
          398  +  sqlite3ExplainSelect(pParse->pVdbe, X);
          399  +  sqlite3ExplainFinish(pParse->pVdbe);
   397    400     sqlite3SelectDelete(pParse->db, X);
   398    401   }
   399    402   
   400    403   %type select {Select*}
   401    404   %destructor select {sqlite3SelectDelete(pParse->db, $$);}
   402    405   %type oneselect {Select*}
   403    406   %destructor oneselect {sqlite3SelectDelete(pParse->db, $$);}

Changes to src/printf.c.

   132    132     return (char)digit;
   133    133   }
   134    134   #endif /* SQLITE_OMIT_FLOATING_POINT */
   135    135   
   136    136   /*
   137    137   ** Append N space characters to the given string buffer.
   138    138   */
   139         -static void appendSpace(StrAccum *pAccum, int N){
          139  +void sqlite3AppendSpace(StrAccum *pAccum, int N){
   140    140     static const char zSpaces[] = "                             ";
   141    141     while( N>=(int)sizeof(zSpaces)-1 ){
   142    142       sqlite3StrAccumAppend(pAccum, zSpaces, sizeof(zSpaces)-1);
   143    143       N -= sizeof(zSpaces)-1;
   144    144     }
   145    145     if( N>0 ){
   146    146       sqlite3StrAccumAppend(pAccum, zSpaces, N);
................................................................................
   660    660       ** "length" characters long.  The field width is "width".  Do
   661    661       ** the output.
   662    662       */
   663    663       if( !flag_leftjustify ){
   664    664         register int nspace;
   665    665         nspace = width-length;
   666    666         if( nspace>0 ){
   667         -        appendSpace(pAccum, nspace);
          667  +        sqlite3AppendSpace(pAccum, nspace);
   668    668         }
   669    669       }
   670    670       if( length>0 ){
   671    671         sqlite3StrAccumAppend(pAccum, bufpt, length);
   672    672       }
   673    673       if( flag_leftjustify ){
   674    674         register int nspace;
   675    675         nspace = width-length;
   676    676         if( nspace>0 ){
   677         -        appendSpace(pAccum, nspace);
          677  +        sqlite3AppendSpace(pAccum, nspace);
   678    678         }
   679    679       }
   680    680       sqlite3_free(zExtra);
   681    681     }/* End for loop over the format string */
   682    682   } /* End of function */
   683    683   
   684    684   /*

Changes to src/select.c.

  4490   4490     }
  4491   4491   
  4492   4492     sqlite3DbFree(db, sAggInfo.aCol);
  4493   4493     sqlite3DbFree(db, sAggInfo.aFunc);
  4494   4494     return rc;
  4495   4495   }
  4496   4496   
  4497         -#if defined(SQLITE_DEBUG)
         4497  +#if defined(SQLITE_ENABLE_TREE_EXPLAIN)
  4498   4498   /*
  4499         -*******************************************************************************
  4500         -** The following code is used for testing and debugging only.  The code
  4501         -** that follows does not appear in normal builds.
  4502         -**
  4503         -** These routines are used to print out the content of all or part of a 
  4504         -** parse structures such as Select or Expr.  Such printouts are useful
  4505         -** for helping to understand what is happening inside the code generator
  4506         -** during the execution of complex SELECT statements.
  4507         -**
  4508         -** These routine are not called anywhere from within the normal
  4509         -** code base.  Then are intended to be called from within the debugger
  4510         -** or from temporary "printf" statements inserted for debugging.
         4499  +** Generate a human-readable description of a the Select object.
  4511   4500   */
  4512         -void sqlite3PrintExpr(Expr *p){
  4513         -  if( !ExprHasProperty(p, EP_IntValue) && p->u.zToken ){
  4514         -    sqlite3DebugPrintf("(%s", p->u.zToken);
  4515         -  }else{
  4516         -    sqlite3DebugPrintf("(%d", p->op);
         4501  +static void explainOneSelect(Vdbe *pVdbe, Select *p){
         4502  +  sqlite3ExplainPrintf(pVdbe, "SELECT ");
         4503  +  if( p->selFlags & (SF_Distinct|SF_Aggregate) ){
         4504  +    if( p->selFlags & SF_Distinct ){
         4505  +      sqlite3ExplainPrintf(pVdbe, "DISTINCT ");
         4506  +    }
         4507  +    if( p->selFlags & SF_Aggregate ){
         4508  +      sqlite3ExplainPrintf(pVdbe, "agg_flag ");
         4509  +    }
         4510  +    sqlite3ExplainNL(pVdbe);
         4511  +    sqlite3ExplainPrintf(pVdbe, "   ");
  4517   4512     }
  4518         -  if( p->pLeft ){
  4519         -    sqlite3DebugPrintf(" ");
  4520         -    sqlite3PrintExpr(p->pLeft);
  4521         -  }
  4522         -  if( p->pRight ){
  4523         -    sqlite3DebugPrintf(" ");
  4524         -    sqlite3PrintExpr(p->pRight);
  4525         -  }
  4526         -  sqlite3DebugPrintf(")");
  4527         -}
  4528         -void sqlite3PrintExprList(ExprList *pList){
  4529         -  int i;
  4530         -  for(i=0; i<pList->nExpr; i++){
  4531         -    sqlite3PrintExpr(pList->a[i].pExpr);
  4532         -    if( i<pList->nExpr-1 ){
  4533         -      sqlite3DebugPrintf(", ");
  4534         -    }
  4535         -  }
  4536         -}
  4537         -void sqlite3PrintSelect(Select *p, int indent){
  4538         -  sqlite3DebugPrintf("%*sSELECT(%p) ", indent, "", p);
  4539         -  sqlite3PrintExprList(p->pEList);
  4540         -  sqlite3DebugPrintf("\n");
  4541         -  if( p->pSrc ){
  4542         -    char *zPrefix;
         4513  +  sqlite3ExplainExprList(pVdbe, p->pEList);
         4514  +  sqlite3ExplainNL(pVdbe);
         4515  +  if( p->pSrc && p->pSrc->nSrc ){
  4543   4516       int i;
  4544         -    zPrefix = "FROM";
         4517  +    sqlite3ExplainPrintf(pVdbe, "FROM ");
         4518  +    sqlite3ExplainPush(pVdbe);
  4545   4519       for(i=0; i<p->pSrc->nSrc; i++){
  4546   4520         struct SrcList_item *pItem = &p->pSrc->a[i];
  4547         -      sqlite3DebugPrintf("%*s ", indent+6, zPrefix);
  4548         -      zPrefix = "";
         4521  +      sqlite3ExplainPrintf(pVdbe, "{%d,*} = ", pItem->iCursor);
  4549   4522         if( pItem->pSelect ){
  4550         -        sqlite3DebugPrintf("(\n");
  4551         -        sqlite3PrintSelect(pItem->pSelect, indent+10);
  4552         -        sqlite3DebugPrintf("%*s)", indent+8, "");
         4523  +        sqlite3ExplainSelect(pVdbe, pItem->pSelect);
         4524  +        if( pItem->pTab ){
         4525  +          sqlite3ExplainPrintf(pVdbe, " (tabname=%s)", pItem->pTab->zName);
         4526  +        }
  4553   4527         }else if( pItem->zName ){
  4554         -        sqlite3DebugPrintf("%s", pItem->zName);
  4555         -      }
  4556         -      if( pItem->pTab ){
  4557         -        sqlite3DebugPrintf("(table: %s)", pItem->pTab->zName);
         4528  +        sqlite3ExplainPrintf(pVdbe, "%s", pItem->zName);
  4558   4529         }
  4559   4530         if( pItem->zAlias ){
  4560         -        sqlite3DebugPrintf(" AS %s", pItem->zAlias);
         4531  +        sqlite3ExplainPrintf(pVdbe, " (AS %s)", pItem->zAlias);
  4561   4532         }
  4562         -      if( i<p->pSrc->nSrc-1 ){
  4563         -        sqlite3DebugPrintf(",");
         4533  +      if( pItem->jointype & JT_LEFT ){
         4534  +        sqlite3ExplainPrintf(pVdbe, " LEFT-JOIN");
  4564   4535         }
  4565         -      sqlite3DebugPrintf("\n");
         4536  +      sqlite3ExplainNL(pVdbe);
  4566   4537       }
         4538  +    sqlite3ExplainPop(pVdbe);
  4567   4539     }
  4568   4540     if( p->pWhere ){
  4569         -    sqlite3DebugPrintf("%*s WHERE ", indent, "");
  4570         -    sqlite3PrintExpr(p->pWhere);
  4571         -    sqlite3DebugPrintf("\n");
         4541  +    sqlite3ExplainPrintf(pVdbe, "WHERE ");
         4542  +    sqlite3ExplainExpr(pVdbe, p->pWhere);
         4543  +    sqlite3ExplainNL(pVdbe);
  4572   4544     }
  4573   4545     if( p->pGroupBy ){
  4574         -    sqlite3DebugPrintf("%*s GROUP BY ", indent, "");
  4575         -    sqlite3PrintExprList(p->pGroupBy);
  4576         -    sqlite3DebugPrintf("\n");
         4546  +    sqlite3ExplainPrintf(pVdbe, "GROUPBY ");
         4547  +    sqlite3ExplainExprList(pVdbe, p->pGroupBy);
         4548  +    sqlite3ExplainNL(pVdbe);
  4577   4549     }
  4578   4550     if( p->pHaving ){
  4579         -    sqlite3DebugPrintf("%*s HAVING ", indent, "");
  4580         -    sqlite3PrintExpr(p->pHaving);
  4581         -    sqlite3DebugPrintf("\n");
         4551  +    sqlite3ExplainPrintf(pVdbe, "HAVING ");
         4552  +    sqlite3ExplainExpr(pVdbe, p->pHaving);
         4553  +    sqlite3ExplainNL(pVdbe);
  4582   4554     }
  4583   4555     if( p->pOrderBy ){
  4584         -    sqlite3DebugPrintf("%*s ORDER BY ", indent, "");
  4585         -    sqlite3PrintExprList(p->pOrderBy);
  4586         -    sqlite3DebugPrintf("\n");
         4556  +    sqlite3ExplainPrintf(pVdbe, "ORDERBY ");
         4557  +    sqlite3ExplainExprList(pVdbe, p->pOrderBy);
         4558  +    sqlite3ExplainNL(pVdbe);
         4559  +  }
         4560  +  if( p->pLimit ){
         4561  +    sqlite3ExplainPrintf(pVdbe, "LIMIT ");
         4562  +    sqlite3ExplainExpr(pVdbe, p->pLimit);
         4563  +    sqlite3ExplainNL(pVdbe);
         4564  +  }
         4565  +  if( p->pOffset ){
         4566  +    sqlite3ExplainPrintf(pVdbe, "OFFSET ");
         4567  +    sqlite3ExplainExpr(pVdbe, p->pOffset);
         4568  +    sqlite3ExplainNL(pVdbe);
         4569  +  }
         4570  +}
         4571  +void sqlite3ExplainSelect(Vdbe *pVdbe, Select *p){
         4572  +  if( p==0 ){
         4573  +    sqlite3ExplainPrintf(pVdbe, "(null-select)");
         4574  +    return;
         4575  +  }
         4576  +  while( p->pPrior ) p = p->pPrior;
         4577  +  sqlite3ExplainPush(pVdbe);
         4578  +  while( p ){
         4579  +    explainOneSelect(pVdbe, p);
         4580  +    p = p->pNext;
         4581  +    if( p==0 ) break;
         4582  +    sqlite3ExplainNL(pVdbe);
         4583  +    sqlite3ExplainPrintf(pVdbe, "%s\n", selectOpName(p->op));
  4587   4584     }
         4585  +  sqlite3ExplainPrintf(pVdbe, "END");
         4586  +  sqlite3ExplainPop(pVdbe);
  4588   4587   }
         4588  +
  4589   4589   /* End of the structure debug printing code
  4590   4590   *****************************************************************************/
  4591   4591   #endif /* defined(SQLITE_TEST) || defined(SQLITE_DEBUG) */

Changes to src/shell.c.

  1122   1122         }
  1123   1123   
  1124   1124         /* echo the sql statement if echo on */
  1125   1125         if( pArg && pArg->echoOn ){
  1126   1126           const char *zStmtSql = sqlite3_sql(pStmt);
  1127   1127           fprintf(pArg->out, "%s\n", zStmtSql ? zStmtSql : zSql);
  1128   1128         }
         1129  +
         1130  +      /* Output TESTCTRL_EXPLAIN text of requested */
         1131  +      if( pArg && pArg->mode==MODE_Explain ){
         1132  +        const char *zExplain = 0;
         1133  +        sqlite3_test_control(SQLITE_TESTCTRL_EXPLAIN_STMT, pStmt, &zExplain);
         1134  +        if( zExplain && zExplain[0] ){
         1135  +          fprintf(pArg->out, "%s", zExplain);
         1136  +        }
         1137  +      }
  1129   1138   
  1130   1139         /* perform the first step.  this will tell us if we
  1131   1140         ** have a result set or not and how wide it is.
  1132   1141         */
  1133   1142         rc = sqlite3_step(pStmt);
  1134   1143         /* if we have a result set... */
  1135   1144         if( SQLITE_ROW == rc ){

Changes to src/sqlite.h.in.

  5678   5678   #define SQLITE_TESTCTRL_ASSERT                  12
  5679   5679   #define SQLITE_TESTCTRL_ALWAYS                  13
  5680   5680   #define SQLITE_TESTCTRL_RESERVE                 14
  5681   5681   #define SQLITE_TESTCTRL_OPTIMIZATIONS           15
  5682   5682   #define SQLITE_TESTCTRL_ISKEYWORD               16
  5683   5683   #define SQLITE_TESTCTRL_SCRATCHMALLOC           17
  5684   5684   #define SQLITE_TESTCTRL_LOCALTIME_FAULT         18
  5685         -#define SQLITE_TESTCTRL_LAST                    18
         5685  +#define SQLITE_TESTCTRL_EXPLAIN_STMT            19
         5686  +#define SQLITE_TESTCTRL_LAST                    19
  5686   5687   
  5687   5688   /*
  5688   5689   ** CAPI3REF: SQLite Runtime Status
  5689   5690   **
  5690   5691   ** ^This interface is used to retrieve runtime status information
  5691   5692   ** about the performance of SQLite, and optionally to reset various
  5692   5693   ** highwater marks.  ^The first argument is an integer code for

Changes to src/sqliteInt.h.

  1703   1703   #define EP_VarSelect  0x0020  /* pSelect is correlated, not constant */
  1704   1704   #define EP_DblQuoted  0x0040  /* token.z was originally in "..." */
  1705   1705   #define EP_InfixFunc  0x0080  /* True for an infix function: LIKE, GLOB, etc */
  1706   1706   #define EP_ExpCollate 0x0100  /* Collating sequence specified explicitly */
  1707   1707   #define EP_FixedDest  0x0200  /* Result needed in a specific register */
  1708   1708   #define EP_IntValue   0x0400  /* Integer value contained in u.iValue */
  1709   1709   #define EP_xIsSelect  0x0800  /* x.pSelect is valid (otherwise x.pList is) */
  1710         -
  1711         -#define EP_Reduced    0x1000  /* Expr struct is EXPR_REDUCEDSIZE bytes only */
  1712         -#define EP_TokenOnly  0x2000  /* Expr struct is EXPR_TOKENONLYSIZE bytes only */
  1713         -#define EP_Static     0x4000  /* Held in memory not obtained from malloc() */
         1710  +#define EP_Hint       0x1000  /* Optimizer hint. Not required for correctness */
         1711  +#define EP_Reduced    0x2000  /* Expr struct is EXPR_REDUCEDSIZE bytes only */
         1712  +#define EP_TokenOnly  0x4000  /* Expr struct is EXPR_TOKENONLYSIZE bytes only */
         1713  +#define EP_Static     0x8000  /* Held in memory not obtained from malloc() */
  1714   1714   
  1715   1715   /*
  1716   1716   ** The following are the meanings of bits in the Expr.flags2 field.
  1717   1717   */
  1718   1718   #define EP2_MallocedToken  0x0001  /* Need to sqlite3DbFree() Expr.zToken */
  1719   1719   #define EP2_Irreducible    0x0002  /* Cannot EXPRDUP_REDUCE this Expr */
  1720   1720   
................................................................................
  2647   2647   char *sqlite3MAppendf(sqlite3*,char*,const char*,...);
  2648   2648   #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
  2649   2649     void sqlite3DebugPrintf(const char*, ...);
  2650   2650   #endif
  2651   2651   #if defined(SQLITE_TEST)
  2652   2652     void *sqlite3TestTextToPtr(const char*);
  2653   2653   #endif
         2654  +
         2655  +/* Output formatting for SQLITE_TESTCTRL_EXPLAIN */
         2656  +#if defined(SQLITE_ENABLE_TREE_EXPLAIN)
         2657  +  void sqlite3ExplainBegin(Vdbe*);
         2658  +  void sqlite3ExplainPrintf(Vdbe*, const char*, ...);
         2659  +  void sqlite3ExplainNL(Vdbe*);
         2660  +  void sqlite3ExplainPush(Vdbe*);
         2661  +  void sqlite3ExplainPop(Vdbe*);
         2662  +  void sqlite3ExplainFinish(Vdbe*);
         2663  +  void sqlite3ExplainSelect(Vdbe*, Select*);
         2664  +  void sqlite3ExplainExpr(Vdbe*, Expr*);
         2665  +  void sqlite3ExplainExprList(Vdbe*, ExprList*);
         2666  +  const char *sqlite3VdbeExplanation(Vdbe*);
         2667  +#else
         2668  +# define sqlite3ExplainBegin(X)
         2669  +# define sqlite3ExplainSelect(A,B)
         2670  +# define sqlite3ExplainExpr(A,B)
         2671  +# define sqlite3ExplainExprList(A,B)
         2672  +# define sqlite3ExplainFinish(X)
         2673  +# define sqlite3VdbeExplanation(X) 0
         2674  +#endif
         2675  +
         2676  +
  2654   2677   void sqlite3SetString(char **, sqlite3*, const char*, ...);
  2655   2678   void sqlite3ErrorMsg(Parse*, const char*, ...);
  2656   2679   int sqlite3Dequote(char*);
  2657   2680   int sqlite3KeywordCode(const unsigned char*, int);
  2658   2681   int sqlite3RunParser(Parse*, const char*, char **);
  2659   2682   void sqlite3FinishCoding(Parse*);
  2660   2683   int sqlite3GetTempReg(Parse*);
................................................................................
  3028   3051     FuncDestructor *pDestructor
  3029   3052   );
  3030   3053   int sqlite3ApiExit(sqlite3 *db, int);
  3031   3054   int sqlite3OpenTempDatabase(Parse *);
  3032   3055   
  3033   3056   void sqlite3StrAccumInit(StrAccum*, char*, int, int);
  3034   3057   void sqlite3StrAccumAppend(StrAccum*,const char*,int);
         3058  +void sqlite3AppendSpace(StrAccum*,int);
  3035   3059   char *sqlite3StrAccumFinish(StrAccum*);
  3036   3060   void sqlite3StrAccumReset(StrAccum*);
  3037   3061   void sqlite3SelectDestInit(SelectDest*,int,int);
  3038   3062   Expr *sqlite3CreateColumnExpr(sqlite3 *, SrcList *, int, int);
  3039   3063   
  3040   3064   void sqlite3BackupRestart(sqlite3_backup *);
  3041   3065   void sqlite3BackupUpdate(sqlite3_backup *, Pgno, const u8 *);

Changes to src/vdbeInt.h.

    29     29   ** Boolean values
    30     30   */
    31     31   typedef unsigned char Bool;
    32     32   
    33     33   /* Opaque type used by code in vdbesort.c */
    34     34   typedef struct VdbeSorter VdbeSorter;
    35     35   
           36  +/* Opaque type used by the explainer */
           37  +typedef struct Explain Explain;
           38  +
    36     39   /*
    37     40   ** A cursor is a pointer into a single BTree within a database file.
    38     41   ** The cursor can seek to a BTree entry with a particular key, or
    39     42   ** loop over all entries of the Btree.  You can also insert new BTree
    40     43   ** entries or retrieve the key or data from the entry that the cursor
    41     44   ** is currently pointing to.
    42     45   ** 
................................................................................
   253    256     VdbeFunc *pVdbeFunc;  /* Auxilary data, if created. */
   254    257     Mem s;                /* The return value is stored here */
   255    258     Mem *pMem;            /* Memory cell used to store aggregate context */
   256    259     int isError;          /* Error code returned by the function. */
   257    260     CollSeq *pColl;       /* Collating sequence */
   258    261   };
   259    262   
          263  +/*
          264  +** An Explain object accumulates indented output which is helpful
          265  +** in describing recursive data structures.
          266  +*/
          267  +struct Explain {
          268  +  Vdbe *pVdbe;       /* Attach the explanation to this Vdbe */
          269  +  StrAccum str;      /* The string being accumulated */
          270  +  int nIndent;       /* Number of elements in aIndent */
          271  +  u16 aIndent[100];  /* Levels of indentation */
          272  +  char zBase[100];   /* Initial space */
          273  +};
          274  +
   260    275   /*
   261    276   ** An instance of the virtual machine.  This structure contains the complete
   262    277   ** state of the virtual machine.
   263    278   **
   264    279   ** The "sqlite3_stmt" structure pointer that is returned by sqlite3_prepare()
   265    280   ** is really a pointer to an instance of this structure.
   266    281   **
................................................................................
   319    334     i64 nFkConstraint;      /* Number of imm. FK constraints this VM */
   320    335     i64 nStmtDefCons;       /* Number of def. constraints when stmt started */
   321    336     char *zSql;             /* Text of the SQL statement that generated this */
   322    337     void *pFree;            /* Free this when deleting the vdbe */
   323    338   #ifdef SQLITE_DEBUG
   324    339     FILE *trace;            /* Write an execution trace here, if not NULL */
   325    340   #endif
          341  +#ifdef SQLITE_ENABLE_TREE_EXPLAIN
          342  +  Explain *pExplain;      /* The explainer */
          343  +  char *zExplain;         /* Explanation of data structures */
          344  +#endif
   326    345     VdbeFrame *pFrame;      /* Parent frame */
   327    346     VdbeFrame *pDelFrame;   /* List of frame objects to free on VM reset */
   328    347     int nFrame;             /* Number of frames in pFrame list */
   329    348     u32 expmask;            /* Binding to these vars invalidates VM */
   330    349     SubProgram *pProgram;   /* Linked list of all sub-programs used by VM */
   331    350     int nOnceFlag;          /* Size of array aOnceFlag[] */
   332    351     u8 *aOnceFlag;          /* Flags for OP_Once */

Changes to src/vdbeaux.c.

  2470   2470     }
  2471   2471     for(i=p->nzVar-1; i>=0; i--) sqlite3DbFree(db, p->azVar[i]);
  2472   2472     vdbeFreeOpArray(db, p->aOp, p->nOp);
  2473   2473     sqlite3DbFree(db, p->aLabel);
  2474   2474     sqlite3DbFree(db, p->aColName);
  2475   2475     sqlite3DbFree(db, p->zSql);
  2476   2476     sqlite3DbFree(db, p->pFree);
         2477  +#if defined(SQLITE_ENABLE_TREE_EXPLAIN)
         2478  +  sqlite3DbFree(db, p->zExplain);
         2479  +  sqlite3DbFree(db, p->pExplain);
         2480  +#endif
  2477   2481     sqlite3DbFree(db, p);
  2478   2482   }
  2479   2483   
  2480   2484   /*
  2481   2485   ** Delete an entire VDBE.
  2482   2486   */
  2483   2487   void sqlite3VdbeDelete(Vdbe *p){

Changes to src/vdbetrace.c.

     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   **
    13     13   ** This file contains code used to insert the values of host parameters
    14     14   ** (aka "wildcards") into the SQL text output by sqlite3_trace().
           15  +**
           16  +** The Vdbe parse-tree explainer is also found here.
    15     17   */
    16     18   #include "sqliteInt.h"
    17     19   #include "vdbeInt.h"
    18     20   
    19     21   #ifndef SQLITE_OMIT_TRACE
    20     22   
    21     23   /*
................................................................................
   148    150         }
   149    151       }
   150    152     }
   151    153     return sqlite3StrAccumFinish(&out);
   152    154   }
   153    155   
   154    156   #endif /* #ifndef SQLITE_OMIT_TRACE */
          157  +
          158  +/*****************************************************************************
          159  +** The following code implements the data-structure explaining logic
          160  +** for the Vdbe.
          161  +*/
          162  +
          163  +#if defined(SQLITE_ENABLE_TREE_EXPLAIN)
          164  +
          165  +/*
          166  +** Allocate a new Explain object
          167  +*/
          168  +void sqlite3ExplainBegin(Vdbe *pVdbe){
          169  +  if( pVdbe ){
          170  +    sqlite3BeginBenignMalloc();
          171  +    Explain *p = sqlite3_malloc( sizeof(Explain) );
          172  +    if( p ){
          173  +      memset(p, 0, sizeof(*p));
          174  +      p->pVdbe = pVdbe;
          175  +      sqlite3_free(pVdbe->pExplain);
          176  +      pVdbe->pExplain = p;
          177  +      sqlite3StrAccumInit(&p->str, p->zBase, sizeof(p->zBase),
          178  +                          SQLITE_MAX_LENGTH);
          179  +      p->str.useMalloc = 2;
          180  +    }else{
          181  +      sqlite3EndBenignMalloc();
          182  +    }
          183  +  }
          184  +}
          185  +
          186  +/*
          187  +** Return true if the Explain ends with a new-line.
          188  +*/
          189  +static int endsWithNL(Explain *p){
          190  +  return p && p->str.zText && p->str.nChar
          191  +           && p->str.zText[p->str.nChar-1]=='\n';
          192  +}
          193  +    
          194  +/*
          195  +** Append text to the indentation
          196  +*/
          197  +void sqlite3ExplainPrintf(Vdbe *pVdbe, const char *zFormat, ...){
          198  +  Explain *p;
          199  +  if( pVdbe && (p = pVdbe->pExplain)!=0 ){
          200  +    va_list ap;
          201  +    if( p->nIndent && endsWithNL(p) ){
          202  +      int n = p->nIndent;
          203  +      if( n>ArraySize(p->aIndent) ) n = ArraySize(p->aIndent);
          204  +      sqlite3AppendSpace(&p->str, p->aIndent[n-1]);
          205  +    }   
          206  +    va_start(ap, zFormat);
          207  +    sqlite3VXPrintf(&p->str, 1, zFormat, ap);
          208  +    va_end(ap);
          209  +  }
          210  +}
          211  +
          212  +/*
          213  +** Append a '\n' if there is not already one.
          214  +*/
          215  +void sqlite3ExplainNL(Vdbe *pVdbe){
          216  +  Explain *p;
          217  +  if( pVdbe && (p = pVdbe->pExplain)!=0 && !endsWithNL(p) ){
          218  +    sqlite3StrAccumAppend(&p->str, "\n", 1);
          219  +  }
          220  +}
          221  +
          222  +/*
          223  +** Push a new indentation level.  Subsequent lines will be indented
          224  +** so that they begin at the current cursor position.
          225  +*/
          226  +void sqlite3ExplainPush(Vdbe *pVdbe){
          227  +  Explain *p;
          228  +  if( pVdbe && (p = pVdbe->pExplain)!=0 ){
          229  +    if( p->str.zText && p->nIndent<ArraySize(p->aIndent) ){
          230  +      const char *z = p->str.zText;
          231  +      int i = p->str.nChar-1;
          232  +      int x;
          233  +      while( i>=0 && z[i]!='\n' ){ i--; }
          234  +      x = (p->str.nChar - 1) - i;
          235  +      if( p->nIndent && x<p->aIndent[p->nIndent-1] ){
          236  +        x = p->aIndent[p->nIndent-1];
          237  +      }
          238  +      p->aIndent[p->nIndent] = x;
          239  +    }
          240  +    p->nIndent++;
          241  +  }
          242  +}
          243  +
          244  +/*
          245  +** Pop the indentation stack by one level.
          246  +*/
          247  +void sqlite3ExplainPop(Vdbe *p){
          248  +  if( p && p->pExplain ) p->pExplain->nIndent--;
          249  +}
          250  +
          251  +/*
          252  +** Free the indentation structure
          253  +*/
          254  +void sqlite3ExplainFinish(Vdbe *pVdbe){
          255  +  if( pVdbe && pVdbe->pExplain ){
          256  +    sqlite3_free(pVdbe->zExplain);
          257  +    sqlite3ExplainNL(pVdbe);
          258  +    pVdbe->zExplain = sqlite3StrAccumFinish(&pVdbe->pExplain->str);
          259  +    sqlite3_free(pVdbe->pExplain);
          260  +    pVdbe->pExplain = 0;
          261  +    sqlite3EndBenignMalloc();
          262  +  }
          263  +}
          264  +
          265  +/*
          266  +** Return the explanation of a virtual machine.
          267  +*/
          268  +const char *sqlite3VdbeExplanation(Vdbe *pVdbe){
          269  +  return (pVdbe && pVdbe->zExplain) ? pVdbe->zExplain : 0;
          270  +}
          271  +#endif /* defined(SQLITE_DEBUG) */