src/select.c

   1 /*
   2 ** 2001 September 15
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 *************************************************************************
  12 ** This file contains C code routines that are called by the parser
  13 ** to handle SELECT statements in SQLite.
  14 */
  15 #include "sqliteInt.h"
  16
  17 /*
  18 ** Trace output macros
  19 */
  20 #if SELECTTRACE_ENABLED
  21 /***/ int sqlite3SelectTrace = 0;
  22 # define SELECTTRACE(K,P,S,X)  \
  23   if(sqlite3SelectTrace&(K))   \
  24     sqlite3DebugPrintf("%s/%p: ",(S)->zSelName,(S)),\
  25     sqlite3DebugPrintf X
  26 #else
  27 # define SELECTTRACE(K,P,S,X)
  28 #endif
  29
  30
  31 /*
  32 ** An instance of the following object is used to record information about
  33 ** how to process the DISTINCT keyword, to simplify passing that information
  34 ** into the selectInnerLoop() routine.
  35 */
  36 typedef struct DistinctCtx DistinctCtx;
  37 struct DistinctCtx {
  38   u8 isTnct;      /* True if the DISTINCT keyword is present */
  39   u8 eTnctType;   /* One of the WHERE_DISTINCT_* operators */
  40   int tabTnct;    /* Ephemeral table used for DISTINCT processing */
  41   int addrTnct;   /* Address of OP_OpenEphemeral opcode for tabTnct */
  42 };
  43
  44 /*
  45 ** An instance of the following object is used to record information about
  46 ** the ORDER BY (or GROUP BY) clause of query is being coded.
  47 */
  48 typedef struct SortCtx SortCtx;
  49 struct SortCtx {
  50   ExprList *pOrderBy;   /* The ORDER BY (or GROUP BY clause) */
  51   int nOBSat;           /* Number of ORDER BY terms satisfied by indices */
  52   int iECursor;         /* Cursor number for the sorter */
  53   int regReturn;        /* Register holding block-output return address */
  54   int labelBkOut;       /* Start label for the block-output subroutine */
  55   int addrSortIndex;    /* Address of the OP_SorterOpen or OP_OpenEphemeral */
  56   int labelDone;        /* Jump here when done, ex: LIMIT reached */
  57   u8 sortFlags;         /* Zero or more SORTFLAG_* bits */
  58   u8 bOrderedInnerLoop; /* ORDER BY correctly sorts the inner loop */
  59 };
  60 #define SORTFLAG_UseSorter  0x01   /* Use SorterOpen instead of OpenEphemeral */
  61
  62 /*
  63 ** Delete all the content of a Select structure.  Deallocate the structure
  64 ** itself only if bFree is true.
  65 */
  66 static void clearSelect(sqlite3 *db, Select *p, int bFree){
  67   while( p ){
  68     Select *pPrior = p->pPrior;
  69     sqlite3ExprListDelete(db, p->pEList);
  70     sqlite3SrcListDelete(db, p->pSrc);
  71     sqlite3ExprDelete(db, p->pWhere);
  72     sqlite3ExprListDelete(db, p->pGroupBy);
  73     sqlite3ExprDelete(db, p->pHaving);
  74     sqlite3ExprListDelete(db, p->pOrderBy);
  75     sqlite3ExprDelete(db, p->pLimit);
  76     if( OK_IF_ALWAYS_TRUE(p->pWith) ) sqlite3WithDelete(db, p->pWith);
  77     if( bFree ) sqlite3DbFreeNN(db, p);
  78     p = pPrior;
  79     bFree = 1;
  80   }
  81 }
  82
  83 /*
  84 ** Initialize a SelectDest structure.
  85 */
  86 void sqlite3SelectDestInit(SelectDest *pDest, int eDest, int iParm){
  87   pDest->eDest = (u8)eDest;
  88   pDest->iSDParm = iParm;
  89   pDest->zAffSdst = 0;
  90   pDest->iSdst = 0;
  91   pDest->nSdst = 0;
  92 }
  93
  94
  95 /*
  96 ** Allocate a new Select structure and return a pointer to that
  97 ** structure.
  98 */
  99 Select *sqlite3SelectNew(
 100   Parse *pParse,        /* Parsing context */
 101   ExprList *pEList,     /* which columns to include in the result */
 102   SrcList *pSrc,        /* the FROM clause -- which tables to scan */
 103   Expr *pWhere,         /* the WHERE clause */
 104   ExprList *pGroupBy,   /* the GROUP BY clause */
 105   Expr *pHaving,        /* the HAVING clause */
 106   ExprList *pOrderBy,   /* the ORDER BY clause */
 107   u32 selFlags,         /* Flag parameters, such as SF_Distinct */
 108   Expr *pLimit          /* LIMIT value.  NULL means not used */
 109 ){
 110   Select *pNew;
 111   Select standin;
 112   pNew = sqlite3DbMallocRawNN(pParse->db, sizeof(*pNew) );
 113   if( pNew==0 ){
 114     assert( pParse->db->mallocFailed );
 115     pNew = &standin;
 116   }
 117   if( pEList==0 ){
 118     pEList = sqlite3ExprListAppend(pParse, 0,
 119                                    sqlite3Expr(pParse->db,TK_ASTERISK,0));
 120   }
 121   pNew->pEList = pEList;
 122   pNew->op = TK_SELECT;
 123   pNew->selFlags = selFlags;
 124   pNew->iLimit = 0;
 125   pNew->iOffset = 0;
 126 #if SELECTTRACE_ENABLED
 127   pNew->zSelName[0] = 0;
 128 #endif
 129   pNew->addrOpenEphm[0] = -1;
 130   pNew->addrOpenEphm[1] = -1;
 131   pNew->nSelectRow = 0;
 132   if( pSrc==0 ) pSrc = sqlite3DbMallocZero(pParse->db, sizeof(*pSrc));
 133   pNew->pSrc = pSrc;
 134   pNew->pWhere = pWhere;
 135   pNew->pGroupBy = pGroupBy;
 136   pNew->pHaving = pHaving;
 137   pNew->pOrderBy = pOrderBy;
 138   pNew->pPrior = 0;
 139   pNew->pNext = 0;
 140   pNew->pLimit = pLimit;
 141   pNew->pWith = 0;
 142   if( pParse->db->mallocFailed ) {
 143     clearSelect(pParse->db, pNew, pNew!=&standin);
 144     pNew = 0;
 145   }else{
 146     assert( pNew->pSrc!=0 || pParse->nErr>0 );
 147   }
 148   assert( pNew!=&standin );
 149   return pNew;
 150 }
 151
 152 #if SELECTTRACE_ENABLED
 153 /*
 154 ** Set the name of a Select object
 155 */
 156 void sqlite3SelectSetName(Select *p, const char *zName){
 157   if( p && zName ){
 158     sqlite3_snprintf(sizeof(p->zSelName), p->zSelName, "%s", zName);
 159   }
 160 }
 161 #endif
 162
 163
 164 /*
 165 ** Delete the given Select structure and all of its substructures.
 166 */
 167 void sqlite3SelectDelete(sqlite3 *db, Select *p){
 168   if( OK_IF_ALWAYS_TRUE(p) ) clearSelect(db, p, 1);
 169 }
 170
 171 /*
 172 ** Return a pointer to the right-most SELECT statement in a compound.
 173 */
 174 static Select *findRightmost(Select *p){
 175   while( p->pNext ) p = p->pNext;
 176   return p;
 177 }
 178
 179 /*
 180 ** Given 1 to 3 identifiers preceding the JOIN keyword, determine the
 181 ** type of join.  Return an integer constant that expresses that type
 182 ** in terms of the following bit values:
 183 **
 184 **     JT_INNER
 185 **     JT_CROSS
 186 **     JT_OUTER
 187 **     JT_NATURAL
 188 **     JT_LEFT
 189 **     JT_RIGHT
 190 **
 191 ** A full outer join is the combination of JT_LEFT and JT_RIGHT.
 192 **
 193 ** If an illegal or unsupported join type is seen, then still return
 194 ** a join type, but put an error in the pParse structure.
 195 */
 196 int sqlite3JoinType(Parse *pParse, Token *pA, Token *pB, Token *pC){
 197   int jointype = 0;
 198   Token *apAll[3];
 199   Token *p;
 200                              /*   0123456789 123456789 123456789 123 */
 201   static const char zKeyText[] = "naturaleftouterightfullinnercross";
 202   static const struct {
 203     u8 i;        /* Beginning of keyword text in zKeyText[] */
 204     u8 nChar;    /* Length of the keyword in characters */
 205     u8 code;     /* Join type mask */
 206   } aKeyword[] = {
 207     /* natural */ { 0,  7, JT_NATURAL                },
 208     /* left    */ { 6,  4, JT_LEFT|JT_OUTER          },
 209     /* outer   */ { 10, 5, JT_OUTER                  },
 210     /* right   */ { 14, 5, JT_RIGHT|JT_OUTER         },
 211     /* full    */ { 19, 4, JT_LEFT|JT_RIGHT|JT_OUTER },
 212     /* inner   */ { 23, 5, JT_INNER                  },
 213     /* cross   */ { 28, 5, JT_INNER|JT_CROSS         },
 214   };
 215   int i, j;
 216   apAll[0] = pA;
 217   apAll[1] = pB;
 218   apAll[2] = pC;
 219   for(i=0; i<3 && apAll[i]; i++){
 220     p = apAll[i];
 221     for(j=0; j<ArraySize(aKeyword); j++){
 222       if( p->n==aKeyword[j].nChar
 223           && sqlite3StrNICmp((char*)p->z, &zKeyText[aKeyword[j].i], p->n)==0 ){
 224         jointype |= aKeyword[j].code;
 225         break;
 226       }
 227     }
 228     testcase( j==0 || j==1 || j==2 || j==3 || j==4 || j==5 || j==6 );
 229     if( j>=ArraySize(aKeyword) ){
 230       jointype |= JT_ERROR;
 231       break;
 232     }
 233   }
 234   if(
 235      (jointype & (JT_INNER|JT_OUTER))==(JT_INNER|JT_OUTER) ||
 236      (jointype & JT_ERROR)!=0
 237   ){
 238     const char *zSp = " ";
 239     assert( pB!=0 );
 240     if( pC==0 ){ zSp++; }
 241     sqlite3ErrorMsg(pParse, "unknown or unsupported join type: "
 242        "%T %T%s%T", pA, pB, zSp, pC);
 243     jointype = JT_INNER;
 244   }else if( (jointype & JT_OUTER)!=0
 245          && (jointype & (JT_LEFT|JT_RIGHT))!=JT_LEFT ){
 246     sqlite3ErrorMsg(pParse,
 247       "RIGHT and FULL OUTER JOINs are not currently supported");
 248     jointype = JT_INNER;
 249   }
 250   return jointype;
 251 }
 252
 253 /*
 254 ** Return the index of a column in a table.  Return -1 if the column
 255 ** is not contained in the table.
 256 */
 257 static int columnIndex(Table *pTab, const char *zCol){
 258   int i;
 259   for(i=0; i<pTab->nCol; i++){
 260     if( sqlite3StrICmp(pTab->aCol[i].zName, zCol)==0 ) return i;
 261   }
 262   return -1;
 263 }
 264
 265 /*
 266 ** Search the first N tables in pSrc, from left to right, looking for a
 267 ** table that has a column named zCol.
 268 **
 269 ** When found, set *piTab and *piCol to the table index and column index
 270 ** of the matching column and return TRUE.
 271 **
 272 ** If not found, return FALSE.
 273 */
 274 static int tableAndColumnIndex(
 275   SrcList *pSrc,       /* Array of tables to search */
 276   int N,               /* Number of tables in pSrc->a[] to search */
 277   const char *zCol,    /* Name of the column we are looking for */
 278   int *piTab,          /* Write index of pSrc->a[] here */
 279   int *piCol           /* Write index of pSrc->a[*piTab].pTab->aCol[] here */
 280 ){
 281   int i;               /* For looping over tables in pSrc */
 282   int iCol;            /* Index of column matching zCol */
 283
 284   assert( (piTab==0)==(piCol==0) );  /* Both or neither are NULL */
 285   for(i=0; i<N; i++){
 286     iCol = columnIndex(pSrc->a[i].pTab, zCol);
 287     if( iCol>=0 ){
 288       if( piTab ){
 289         *piTab = i;
 290         *piCol = iCol;
 291       }
 292       return 1;
 293     }
 294   }
 295   return 0;
 296 }
 297
 298 /*
 299 ** This function is used to add terms implied by JOIN syntax to the
 300 ** WHERE clause expression of a SELECT statement. The new term, which
 301 ** is ANDed with the existing WHERE clause, is of the form:
 302 **
 303 **    (tab1.col1 = tab2.col2)
 304 **
 305 ** where tab1 is the iSrc'th table in SrcList pSrc and tab2 is the
 306 ** (iSrc+1)'th. Column col1 is column iColLeft of tab1, and col2 is
 307 ** column iColRight of tab2.
 308 */
 309 static void addWhereTerm(
 310   Parse *pParse,                  /* Parsing context */
 311   SrcList *pSrc,                  /* List of tables in FROM clause */
 312   int iLeft,                      /* Index of first table to join in pSrc */
 313   int iColLeft,                   /* Index of column in first table */
 314   int iRight,                     /* Index of second table in pSrc */
 315   int iColRight,                  /* Index of column in second table */
 316   int isOuterJoin,                /* True if this is an OUTER join */
 317   Expr **ppWhere                  /* IN/OUT: The WHERE clause to add to */
 318 ){
 319   sqlite3 *db = pParse->db;
 320   Expr *pE1;
 321   Expr *pE2;
 322   Expr *pEq;
 323
 324   assert( iLeft<iRight );
 325   assert( pSrc->nSrc>iRight );
 326   assert( pSrc->a[iLeft].pTab );
 327   assert( pSrc->a[iRight].pTab );
 328
 329   pE1 = sqlite3CreateColumnExpr(db, pSrc, iLeft, iColLeft);
 330   pE2 = sqlite3CreateColumnExpr(db, pSrc, iRight, iColRight);
 331
 332   pEq = sqlite3PExpr(pParse, TK_EQ, pE1, pE2);
 333   if( pEq && isOuterJoin ){
 334     ExprSetProperty(pEq, EP_FromJoin);
 335     assert( !ExprHasProperty(pEq, EP_TokenOnly|EP_Reduced) );
 336     ExprSetVVAProperty(pEq, EP_NoReduce);
 337     pEq->iRightJoinTable = (i16)pE2->iTable;
 338   }
 339   *ppWhere = sqlite3ExprAnd(db, *ppWhere, pEq);
 340 }
 341
 342 /*
 343 ** Set the EP_FromJoin property on all terms of the given expression.
 344 ** And set the Expr.iRightJoinTable to iTable for every term in the
 345 ** expression.
 346 **
 347 ** The EP_FromJoin property is used on terms of an expression to tell
 348 ** the LEFT OUTER JOIN processing logic that this term is part of the
 349 ** join restriction specified in the ON or USING clause and not a part
 350 ** of the more general WHERE clause.  These terms are moved over to the
 351 ** WHERE clause during join processing but we need to remember that they
 352 ** originated in the ON or USING clause.
 353 **
 354 ** The Expr.iRightJoinTable tells the WHERE clause processing that the
 355 ** expression depends on table iRightJoinTable even if that table is not
 356 ** explicitly mentioned in the expression.  That information is needed
 357 ** for cases like this:
 358 **
 359 **    SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.b AND t1.x=5
 360 **
 361 ** The where clause needs to defer the handling of the t1.x=5
 362 ** term until after the t2 loop of the join.  In that way, a
 363 ** NULL t2 row will be inserted whenever t1.x!=5.  If we do not
 364 ** defer the handling of t1.x=5, it will be processed immediately
 365 ** after the t1 loop and rows with t1.x!=5 will never appear in
 366 ** the output, which is incorrect.
 367 */
 368 static void setJoinExpr(Expr *p, int iTable){
 369   while( p ){
 370     ExprSetProperty(p, EP_FromJoin);
 371     assert( !ExprHasProperty(p, EP_TokenOnly|EP_Reduced) );
 372     ExprSetVVAProperty(p, EP_NoReduce);
 373     p->iRightJoinTable = (i16)iTable;
 374     if( p->op==TK_FUNCTION && p->x.pList ){
 375       int i;
 376       for(i=0; i<p->x.pList->nExpr; i++){
 377         setJoinExpr(p->x.pList->a[i].pExpr, iTable);
 378       }
 379     }
 380     setJoinExpr(p->pLeft, iTable);
 381     p = p->pRight;
 382   }
 383 }
 384
 385 /*
 386 ** This routine processes the join information for a SELECT statement.
 387 ** ON and USING clauses are converted into extra terms of the WHERE clause.
 388 ** NATURAL joins also create extra WHERE clause terms.
 389 **
 390 ** The terms of a FROM clause are contained in the Select.pSrc structure.
 391 ** The left most table is the first entry in Select.pSrc.  The right-most
 392 ** table is the last entry.  The join operator is held in the entry to
 393 ** the left.  Thus entry 0 contains the join operator for the join between
 394 ** entries 0 and 1.  Any ON or USING clauses associated with the join are
 395 ** also attached to the left entry.
 396 **
 397 ** This routine returns the number of errors encountered.
 398 */
 399 static int sqliteProcessJoin(Parse *pParse, Select *p){
 400   SrcList *pSrc;                  /* All tables in the FROM clause */
 401   int i, j;                       /* Loop counters */
 402   struct SrcList_item *pLeft;     /* Left table being joined */
 403   struct SrcList_item *pRight;    /* Right table being joined */
 404
 405   pSrc = p->pSrc;
 406   pLeft = &pSrc->a[0];
 407   pRight = &pLeft[1];
 408   for(i=0; i<pSrc->nSrc-1; i++, pRight++, pLeft++){
 409     Table *pRightTab = pRight->pTab;
 410     int isOuter;
 411
 412     if( NEVER(pLeft->pTab==0 || pRightTab==0) ) continue;
 413     isOuter = (pRight->fg.jointype & JT_OUTER)!=0;
 414
 415     /* When the NATURAL keyword is present, add WHERE clause terms for
 416     ** every column that the two tables have in common.
 417     */
 418     if( pRight->fg.jointype & JT_NATURAL ){
 419       if( pRight->pOn || pRight->pUsing ){
 420         sqlite3ErrorMsg(pParse, "a NATURAL join may not have "
 421            "an ON or USING clause", 0);
 422         return 1;
 423       }
 424       for(j=0; j<pRightTab->nCol; j++){
 425         char *zName;   /* Name of column in the right table */
 426         int iLeft;     /* Matching left table */
 427         int iLeftCol;  /* Matching column in the left table */
 428
 429         zName = pRightTab->aCol[j].zName;
 430         if( tableAndColumnIndex(pSrc, i+1, zName, &iLeft, &iLeftCol) ){
 431           addWhereTerm(pParse, pSrc, iLeft, iLeftCol, i+1, j,
 432                        isOuter, &p->pWhere);
 433         }
 434       }
 435     }
 436
 437     /* Disallow both ON and USING clauses in the same join
 438     */
 439     if( pRight->pOn && pRight->pUsing ){
 440       sqlite3ErrorMsg(pParse, "cannot have both ON and USING "
 441         "clauses in the same join");
 442       return 1;
 443     }
 444
 445     /* Add the ON clause to the end of the WHERE clause, connected by
 446     ** an AND operator.
 447     */
 448     if( pRight->pOn ){
 449       if( isOuter ) setJoinExpr(pRight->pOn, pRight->iCursor);
 450       p->pWhere = sqlite3ExprAnd(pParse->db, p->pWhere, pRight->pOn);
 451       pRight->pOn = 0;
 452     }
 453
 454     /* Create extra terms on the WHERE clause for each column named
 455     ** in the USING clause.  Example: If the two tables to be joined are
 456     ** A and B and the USING clause names X, Y, and Z, then add this
 457     ** to the WHERE clause:    A.X=B.X AND A.Y=B.Y AND A.Z=B.Z
 458     ** Report an error if any column mentioned in the USING clause is
 459     ** not contained in both tables to be joined.
 460     */
 461     if( pRight->pUsing ){
 462       IdList *pList = pRight->pUsing;
 463       for(j=0; j<pList->nId; j++){
 464         char *zName;     /* Name of the term in the USING clause */
 465         int iLeft;       /* Table on the left with matching column name */
 466         int iLeftCol;    /* Column number of matching column on the left */
 467         int iRightCol;   /* Column number of matching column on the right */
 468
 469         zName = pList->a[j].zName;
 470         iRightCol = columnIndex(pRightTab, zName);
 471         if( iRightCol<0
 472          || !tableAndColumnIndex(pSrc, i+1, zName, &iLeft, &iLeftCol)
 473         ){
 474           sqlite3ErrorMsg(pParse, "cannot join using column %s - column "
 475             "not present in both tables", zName);
 476           return 1;
 477         }
 478         addWhereTerm(pParse, pSrc, iLeft, iLeftCol, i+1, iRightCol,
 479                      isOuter, &p->pWhere);
 480       }
 481     }
 482   }
 483   return 0;
 484 }
 485
 486 /* Forward reference */
 487 static KeyInfo *keyInfoFromExprList(
 488   Parse *pParse,       /* Parsing context */
 489   ExprList *pList,     /* Form the KeyInfo object from this ExprList */
 490   int iStart,          /* Begin with this column of pList */
 491   int nExtra           /* Add this many extra columns to the end */
 492 );
 493
 494 /*
 495 ** Generate code that will push the record in registers regData
 496 ** through regData+nData-1 onto the sorter.
 497 */
 498 static void pushOntoSorter(
 499   Parse *pParse,         /* Parser context */
 500   SortCtx *pSort,        /* Information about the ORDER BY clause */
 501   Select *pSelect,       /* The whole SELECT statement */
 502   int regData,           /* First register holding data to be sorted */
 503   int regOrigData,       /* First register holding data before packing */
 504   int nData,             /* Number of elements in the data array */
 505   int nPrefixReg         /* No. of reg prior to regData available for use */
 506 ){
 507   Vdbe *v = pParse->pVdbe;                         /* Stmt under construction */
 508   int bSeq = ((pSort->sortFlags & SORTFLAG_UseSorter)==0);
 509   int nExpr = pSort->pOrderBy->nExpr;              /* No. of ORDER BY terms */
 510   int nBase = nExpr + bSeq + nData;                /* Fields in sorter record */
 511   int regBase;                                     /* Regs for sorter record */
 512   int regRecord = ++pParse->nMem;                  /* Assembled sorter record */
 513   int nOBSat = pSort->nOBSat;                      /* ORDER BY terms to skip */
 514   int op;                            /* Opcode to add sorter record to sorter */
 515   int iLimit;                        /* LIMIT counter */
 516
 517   assert( bSeq==0 || bSeq==1 );
 518   assert( nData==1 || regData==regOrigData || regOrigData==0 );
 519   if( nPrefixReg ){
 520     assert( nPrefixReg==nExpr+bSeq );
 521     regBase = regData - nExpr - bSeq;
 522   }else{
 523     regBase = pParse->nMem + 1;
 524     pParse->nMem += nBase;
 525   }
 526   assert( pSelect->iOffset==0 || pSelect->iLimit!=0 );
 527   iLimit = pSelect->iOffset ? pSelect->iOffset+1 : pSelect->iLimit;
 528   pSort->labelDone = sqlite3VdbeMakeLabel(v);
 529   sqlite3ExprCodeExprList(pParse, pSort->pOrderBy, regBase, regOrigData,
 530                           SQLITE_ECEL_DUP | (regOrigData? SQLITE_ECEL_REF : 0));
 531   if( bSeq ){
 532     sqlite3VdbeAddOp2(v, OP_Sequence, pSort->iECursor, regBase+nExpr);
 533   }
 534   if( nPrefixReg==0 && nData>0 ){
 535     sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+bSeq, nData);
 536   }
 537   sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nBase-nOBSat, regRecord);
 538   if( nOBSat>0 ){
 539     int regPrevKey;   /* The first nOBSat columns of the previous row */
 540     int addrFirst;    /* Address of the OP_IfNot opcode */
 541     int addrJmp;      /* Address of the OP_Jump opcode */
 542     VdbeOp *pOp;      /* Opcode that opens the sorter */
 543     int nKey;         /* Number of sorting key columns, including OP_Sequence */
 544     KeyInfo *pKI;     /* Original KeyInfo on the sorter table */
 545
 546     regPrevKey = pParse->nMem+1;
 547     pParse->nMem += pSort->nOBSat;
 548     nKey = nExpr - pSort->nOBSat + bSeq;
 549     if( bSeq ){
 550       addrFirst = sqlite3VdbeAddOp1(v, OP_IfNot, regBase+nExpr);
 551     }else{
 552       addrFirst = sqlite3VdbeAddOp1(v, OP_SequenceTest, pSort->iECursor);
 553     }
 554     VdbeCoverage(v);
 555     sqlite3VdbeAddOp3(v, OP_Compare, regPrevKey, regBase, pSort->nOBSat);
 556     pOp = sqlite3VdbeGetOp(v, pSort->addrSortIndex);
 557     if( pParse->db->mallocFailed ) return;
 558     pOp->p2 = nKey + nData;
 559     pKI = pOp->p4.pKeyInfo;
 560     memset(pKI->aSortOrder, 0, pKI->nKeyField); /* Makes OP_Jump testable */
 561     sqlite3VdbeChangeP4(v, -1, (char*)pKI, P4_KEYINFO);
 562     testcase( pKI->nAllField > pKI->nKeyField+2 );
 563     pOp->p4.pKeyInfo = keyInfoFromExprList(pParse, pSort->pOrderBy, nOBSat,
 564                                            pKI->nAllField-pKI->nKeyField-1);
 565     addrJmp = sqlite3VdbeCurrentAddr(v);
 566     sqlite3VdbeAddOp3(v, OP_Jump, addrJmp+1, 0, addrJmp+1); VdbeCoverage(v);
 567     pSort->labelBkOut = sqlite3VdbeMakeLabel(v);
 568     pSort->regReturn = ++pParse->nMem;
 569     sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut);
 570     sqlite3VdbeAddOp1(v, OP_ResetSorter, pSort->iECursor);
 571     if( iLimit ){
 572       sqlite3VdbeAddOp2(v, OP_IfNot, iLimit, pSort->labelDone);
 573       VdbeCoverage(v);
 574     }
 575     sqlite3VdbeJumpHere(v, addrFirst);
 576     sqlite3ExprCodeMove(pParse, regBase, regPrevKey, pSort->nOBSat);
 577     sqlite3VdbeJumpHere(v, addrJmp);
 578   }
 579   if( pSort->sortFlags & SORTFLAG_UseSorter ){
 580     op = OP_SorterInsert;
 581   }else{
 582     op = OP_IdxInsert;
 583   }
 584   sqlite3VdbeAddOp4Int(v, op, pSort->iECursor, regRecord,
 585                        regBase+nOBSat, nBase-nOBSat);
 586   if( iLimit ){
 587     int addr;
 588     int r1 = 0;
 589     /* Fill the sorter until it contains LIMIT+OFFSET entries.  (The iLimit
 590     ** register is initialized with value of LIMIT+OFFSET.)  After the sorter
 591     ** fills up, delete the least entry in the sorter after each insert.
 592     ** Thus we never hold more than the LIMIT+OFFSET rows in memory at once */
 593     addr = sqlite3VdbeAddOp1(v, OP_IfNotZero, iLimit); VdbeCoverage(v);
 594     sqlite3VdbeAddOp1(v, OP_Last, pSort->iECursor);
 595     if( pSort->bOrderedInnerLoop ){
 596       r1 = ++pParse->nMem;
 597       sqlite3VdbeAddOp3(v, OP_Column, pSort->iECursor, nExpr, r1);
 598       VdbeComment((v, "seq"));
 599     }
 600     sqlite3VdbeAddOp1(v, OP_Delete, pSort->iECursor);
 601     if( pSort->bOrderedInnerLoop ){
 602       /* If the inner loop is driven by an index such that values from
 603       ** the same iteration of the inner loop are in sorted order, then
 604       ** immediately jump to the next iteration of an inner loop if the
 605       ** entry from the current iteration does not fit into the top
 606       ** LIMIT+OFFSET entries of the sorter. */
 607       int iBrk = sqlite3VdbeCurrentAddr(v) + 2;
 608       sqlite3VdbeAddOp3(v, OP_Eq, regBase+nExpr, iBrk, r1);
 609       sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);
 610       VdbeCoverage(v);
 611     }
 612     sqlite3VdbeJumpHere(v, addr);
 613   }
 614 }
 615
 616 /*
 617 ** Add code to implement the OFFSET
 618 */
 619 static void codeOffset(
 620   Vdbe *v,          /* Generate code into this VM */
 621   int iOffset,      /* Register holding the offset counter */
 622   int iContinue     /* Jump here to skip the current record */
 623 ){
 624   if( iOffset>0 ){
 625     sqlite3VdbeAddOp3(v, OP_IfPos, iOffset, iContinue, 1); VdbeCoverage(v);
 626     VdbeComment((v, "OFFSET"));
 627   }
 628 }
 629
 630 /*
 631 ** Add code that will check to make sure the N registers starting at iMem
 632 ** form a distinct entry.  iTab is a sorting index that holds previously
 633 ** seen combinations of the N values.  A new entry is made in iTab
 634 ** if the current N values are new.
 635 **
 636 ** A jump to addrRepeat is made and the N+1 values are popped from the
 637 ** stack if the top N elements are not distinct.
 638 */
 639 static void codeDistinct(
 640   Parse *pParse,     /* Parsing and code generating context */
 641   int iTab,          /* A sorting index used to test for distinctness */
 642   int addrRepeat,    /* Jump to here if not distinct */
 643   int N,             /* Number of elements */
 644   int iMem           /* First element */
 645 ){
 646   Vdbe *v;
 647   int r1;
 648
 649   v = pParse->pVdbe;
 650   r1 = sqlite3GetTempReg(pParse);
 651   sqlite3VdbeAddOp4Int(v, OP_Found, iTab, addrRepeat, iMem, N); VdbeCoverage(v);
 652   sqlite3VdbeAddOp3(v, OP_MakeRecord, iMem, N, r1);
 653   sqlite3VdbeAddOp4Int(v, OP_IdxInsert, iTab, r1, iMem, N);
 654   sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
 655   sqlite3ReleaseTempReg(pParse, r1);
 656 }
 657
 658 /*
 659 ** This routine generates the code for the inside of the inner loop
 660 ** of a SELECT.
 661 **
 662 ** If srcTab is negative, then the p->pEList expressions
 663 ** are evaluated in order to get the data for this row.  If srcTab is
 664 ** zero or more, then data is pulled from srcTab and p->pEList is used only
 665 ** to get the number of columns and the collation sequence for each column.
 666 */
 667 static void selectInnerLoop(
 668   Parse *pParse,          /* The parser context */
 669   Select *p,              /* The complete select statement being coded */
 670   int srcTab,             /* Pull data from this table if non-negative */
 671   SortCtx *pSort,         /* If not NULL, info on how to process ORDER BY */
 672   DistinctCtx *pDistinct, /* If not NULL, info on how to process DISTINCT */
 673   SelectDest *pDest,      /* How to dispose of the results */
 674   int iContinue,          /* Jump here to continue with next row */
 675   int iBreak              /* Jump here to break out of the inner loop */
 676 ){
 677   Vdbe *v = pParse->pVdbe;
 678   int i;
 679   int hasDistinct;            /* True if the DISTINCT keyword is present */
 680   int eDest = pDest->eDest;   /* How to dispose of results */
 681   int iParm = pDest->iSDParm; /* First argument to disposal method */
 682   int nResultCol;             /* Number of result columns */
 683   int nPrefixReg = 0;         /* Number of extra registers before regResult */
 684
 685   /* Usually, regResult is the first cell in an array of memory cells
 686   ** containing the current result row. In this case regOrig is set to the
 687   ** same value. However, if the results are being sent to the sorter, the
 688   ** values for any expressions that are also part of the sort-key are omitted
 689   ** from this array. In this case regOrig is set to zero.  */
 690   int regResult;              /* Start of memory holding current results */
 691   int regOrig;                /* Start of memory holding full result (or 0) */
 692
 693   assert( v );
 694   assert( p->pEList!=0 );
 695   hasDistinct = pDistinct ? pDistinct->eTnctType : WHERE_DISTINCT_NOOP;
 696   if( pSort && pSort->pOrderBy==0 ) pSort = 0;
 697   if( pSort==0 && !hasDistinct ){
 698     assert( iContinue!=0 );
 699     codeOffset(v, p->iOffset, iContinue);
 700   }
 701
 702   /* Pull the requested columns.
 703   */
 704   nResultCol = p->pEList->nExpr;
 705
 706   if( pDest->iSdst==0 ){
 707     if( pSort ){
 708       nPrefixReg = pSort->pOrderBy->nExpr;
 709       if( !(pSort->sortFlags & SORTFLAG_UseSorter) ) nPrefixReg++;
 710       pParse->nMem += nPrefixReg;
 711     }
 712     pDest->iSdst = pParse->nMem+1;
 713     pParse->nMem += nResultCol;
 714   }else if( pDest->iSdst+nResultCol > pParse->nMem ){
 715     /* This is an error condition that can result, for example, when a SELECT
 716     ** on the right-hand side of an INSERT contains more result columns than
 717     ** there are columns in the table on the left.  The error will be caught
 718     ** and reported later.  But we need to make sure enough memory is allocated
 719     ** to avoid other spurious errors in the meantime. */
 720     pParse->nMem += nResultCol;
 721   }
 722   pDest->nSdst = nResultCol;
 723   regOrig = regResult = pDest->iSdst;
 724   if( srcTab>=0 ){
 725     for(i=0; i<nResultCol; i++){
 726       sqlite3VdbeAddOp3(v, OP_Column, srcTab, i, regResult+i);
 727       VdbeComment((v, "%s", p->pEList->a[i].zName));
 728     }
 729   }else if( eDest!=SRT_Exists ){
 730     /* If the destination is an EXISTS(...) expression, the actual
 731     ** values returned by the SELECT are not required.
 732     */
 733     u8 ecelFlags;
 734     if( eDest==SRT_Mem || eDest==SRT_Output || eDest==SRT_Coroutine ){
 735       ecelFlags = SQLITE_ECEL_DUP;
 736     }else{
 737       ecelFlags = 0;
 738     }
 739     if( pSort && hasDistinct==0 && eDest!=SRT_EphemTab && eDest!=SRT_Table ){
 740       /* For each expression in p->pEList that is a copy of an expression in
 741       ** the ORDER BY clause (pSort->pOrderBy), set the associated
 742       ** iOrderByCol value to one more than the index of the ORDER BY
 743       ** expression within the sort-key that pushOntoSorter() will generate.
 744       ** This allows the p->pEList field to be omitted from the sorted record,
 745       ** saving space and CPU cycles.  */
 746       ecelFlags |= (SQLITE_ECEL_OMITREF|SQLITE_ECEL_REF);
 747       for(i=pSort->nOBSat; i<pSort->pOrderBy->nExpr; i++){
 748         int j;
 749         if( (j = pSort->pOrderBy->a[i].u.x.iOrderByCol)>0 ){
 750           p->pEList->a[j-1].u.x.iOrderByCol = i+1-pSort->nOBSat;
 751         }
 752       }
 753       regOrig = 0;
 754       assert( eDest==SRT_Set || eDest==SRT_Mem
 755            || eDest==SRT_Coroutine || eDest==SRT_Output );
 756     }
 757     nResultCol = sqlite3ExprCodeExprList(pParse,p->pEList,regResult,
 758                                          0,ecelFlags);
 759   }
 760
 761   /* If the DISTINCT keyword was present on the SELECT statement
 762   ** and this row has been seen before, then do not make this row
 763   ** part of the result.
 764   */
 765   if( hasDistinct ){
 766     switch( pDistinct->eTnctType ){
 767       case WHERE_DISTINCT_ORDERED: {
 768         VdbeOp *pOp;            /* No longer required OpenEphemeral instr. */
 769         int iJump;              /* Jump destination */
 770         int regPrev;            /* Previous row content */
 771
 772         /* Allocate space for the previous row */
 773         regPrev = pParse->nMem+1;
 774         pParse->nMem += nResultCol;
 775
 776         /* Change the OP_OpenEphemeral coded earlier to an OP_Null
 777         ** sets the MEM_Cleared bit on the first register of the
 778         ** previous value.  This will cause the OP_Ne below to always
 779         ** fail on the first iteration of the loop even if the first
 780         ** row is all NULLs.
 781         */
 782         sqlite3VdbeChangeToNoop(v, pDistinct->addrTnct);
 783         pOp = sqlite3VdbeGetOp(v, pDistinct->addrTnct);
 784         pOp->opcode = OP_Null;
 785         pOp->p1 = 1;
 786         pOp->p2 = regPrev;
 787
 788         iJump = sqlite3VdbeCurrentAddr(v) + nResultCol;
 789         for(i=0; i<nResultCol; i++){
 790           CollSeq *pColl = sqlite3ExprCollSeq(pParse, p->pEList->a[i].pExpr);
 791           if( i<nResultCol-1 ){
 792             sqlite3VdbeAddOp3(v, OP_Ne, regResult+i, iJump, regPrev+i);
 793             VdbeCoverage(v);
 794           }else{
 795             sqlite3VdbeAddOp3(v, OP_Eq, regResult+i, iContinue, regPrev+i);
 796             VdbeCoverage(v);
 797            }
 798           sqlite3VdbeChangeP4(v, -1, (const char *)pColl, P4_COLLSEQ);
 799           sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);
 800         }
 801         assert( sqlite3VdbeCurrentAddr(v)==iJump || pParse->db->mallocFailed );
 802         sqlite3VdbeAddOp3(v, OP_Copy, regResult, regPrev, nResultCol-1);
 803         break;
 804       }
 805
 806       case WHERE_DISTINCT_UNIQUE: {
 807         sqlite3VdbeChangeToNoop(v, pDistinct->addrTnct);
 808         break;
 809       }
 810
 811       default: {
 812         assert( pDistinct->eTnctType==WHERE_DISTINCT_UNORDERED );
 813         codeDistinct(pParse, pDistinct->tabTnct, iContinue, nResultCol,
 814                      regResult);
 815         break;
 816       }
 817     }
 818     if( pSort==0 ){
 819       codeOffset(v, p->iOffset, iContinue);
 820     }
 821   }
 822
 823   switch( eDest ){
 824     /* In this mode, write each query result to the key of the temporary
 825     ** table iParm.
 826     */
 827 #ifndef SQLITE_OMIT_COMPOUND_SELECT
 828     case SRT_Union: {
 829       int r1;
 830       r1 = sqlite3GetTempReg(pParse);
 831       sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1);
 832       sqlite3VdbeAddOp4Int(v, OP_IdxInsert, iParm, r1, regResult, nResultCol);
 833       sqlite3ReleaseTempReg(pParse, r1);
 834       break;
 835     }
 836
 837     /* Construct a record from the query result, but instead of
 838     ** saving that record, use it as a key to delete elements from
 839     ** the temporary table iParm.
 840     */
 841     case SRT_Except: {
 842       sqlite3VdbeAddOp3(v, OP_IdxDelete, iParm, regResult, nResultCol);
 843       break;
 844     }
 845 #endif /* SQLITE_OMIT_COMPOUND_SELECT */
 846
 847     /* Store the result as data using a unique key.
 848     */
 849     case SRT_Fifo:
 850     case SRT_DistFifo:
 851     case SRT_Table:
 852     case SRT_EphemTab: {
 853       int r1 = sqlite3GetTempRange(pParse, nPrefixReg+1);
 854       testcase( eDest==SRT_Table );
 855       testcase( eDest==SRT_EphemTab );
 856       testcase( eDest==SRT_Fifo );
 857       testcase( eDest==SRT_DistFifo );
 858       sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1+nPrefixReg);
 859 #ifndef SQLITE_OMIT_CTE
 860       if( eDest==SRT_DistFifo ){
 861         /* If the destination is DistFifo, then cursor (iParm+1) is open
 862         ** on an ephemeral index. If the current row is already present
 863         ** in the index, do not write it to the output. If not, add the
 864         ** current row to the index and proceed with writing it to the
 865         ** output table as well.  */
 866         int addr = sqlite3VdbeCurrentAddr(v) + 4;
 867         sqlite3VdbeAddOp4Int(v, OP_Found, iParm+1, addr, r1, 0);
 868         VdbeCoverage(v);
 869         sqlite3VdbeAddOp4Int(v, OP_IdxInsert, iParm+1, r1,regResult,nResultCol);
 870         assert( pSort==0 );
 871       }
 872 #endif
 873       if( pSort ){
 874         pushOntoSorter(pParse, pSort, p, r1+nPrefixReg,regResult,1,nPrefixReg);
 875       }else{
 876         int r2 = sqlite3GetTempReg(pParse);
 877         sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, r2);
 878         sqlite3VdbeAddOp3(v, OP_Insert, iParm, r1, r2);
 879         sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
 880         sqlite3ReleaseTempReg(pParse, r2);
 881       }
 882       sqlite3ReleaseTempRange(pParse, r1, nPrefixReg+1);
 883       break;
 884     }
 885
 886 #ifndef SQLITE_OMIT_SUBQUERY
 887     /* If we are creating a set for an "expr IN (SELECT ...)" construct,
 888     ** then there should be a single item on the stack.  Write this
 889     ** item into the set table with bogus data.
 890     */
 891     case SRT_Set: {
 892       if( pSort ){
 893         /* At first glance you would think we could optimize out the
 894         ** ORDER BY in this case since the order of entries in the set
 895         ** does not matter.  But there might be a LIMIT clause, in which
 896         ** case the order does matter */
 897         pushOntoSorter(
 898             pParse, pSort, p, regResult, regOrig, nResultCol, nPrefixReg);
 899       }else{
 900         int r1 = sqlite3GetTempReg(pParse);
 901         assert( sqlite3Strlen30(pDest->zAffSdst)==nResultCol );
 902         sqlite3VdbeAddOp4(v, OP_MakeRecord, regResult, nResultCol,
 903             r1, pDest->zAffSdst, nResultCol);
 904         sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol);
 905         sqlite3VdbeAddOp4Int(v, OP_IdxInsert, iParm, r1, regResult, nResultCol);
 906         sqlite3ReleaseTempReg(pParse, r1);
 907       }
 908       break;
 909     }
 910
 911     /* If any row exist in the result set, record that fact and abort.
 912     */
 913     case SRT_Exists: {
 914       sqlite3VdbeAddOp2(v, OP_Integer, 1, iParm);
 915       /* The LIMIT clause will terminate the loop for us */
 916       break;
 917     }
 918
 919     /* If this is a scalar select that is part of an expression, then
 920     ** store the results in the appropriate memory cell or array of
 921     ** memory cells and break out of the scan loop.
 922     */
 923     case SRT_Mem: {
 924       if( pSort ){
 925         assert( nResultCol<=pDest->nSdst );
 926         pushOntoSorter(
 927             pParse, pSort, p, regResult, regOrig, nResultCol, nPrefixReg);
 928       }else{
 929         assert( nResultCol==pDest->nSdst );
 930         assert( regResult==iParm );
 931         /* The LIMIT clause will jump out of the loop for us */
 932       }
 933       break;
 934     }
 935 #endif /* #ifndef SQLITE_OMIT_SUBQUERY */
 936
 937     case SRT_Coroutine:       /* Send data to a co-routine */
 938     case SRT_Output: {        /* Return the results */
 939       testcase( eDest==SRT_Coroutine );
 940       testcase( eDest==SRT_Output );
 941       if( pSort ){
 942         pushOntoSorter(pParse, pSort, p, regResult, regOrig, nResultCol,
 943                        nPrefixReg);
 944       }else if( eDest==SRT_Coroutine ){
 945         sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm);
 946       }else{
 947         sqlite3VdbeAddOp2(v, OP_ResultRow, regResult, nResultCol);
 948         sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol);
 949       }
 950       break;
 951     }
 952
 953 #ifndef SQLITE_OMIT_CTE
 954     /* Write the results into a priority queue that is order according to
 955     ** pDest->pOrderBy (in pSO).  pDest->iSDParm (in iParm) is the cursor for an
 956     ** index with pSO->nExpr+2 columns.  Build a key using pSO for the first
 957     ** pSO->nExpr columns, then make sure all keys are unique by adding a
 958     ** final OP_Sequence column.  The last column is the record as a blob.
 959     */
 960     case SRT_DistQueue:
 961     case SRT_Queue: {
 962       int nKey;
 963       int r1, r2, r3;
 964       int addrTest = 0;
 965       ExprList *pSO;
 966       pSO = pDest->pOrderBy;
 967       assert( pSO );
 968       nKey = pSO->nExpr;
 969       r1 = sqlite3GetTempReg(pParse);
 970       r2 = sqlite3GetTempRange(pParse, nKey+2);
 971       r3 = r2+nKey+1;
 972       if( eDest==SRT_DistQueue ){
 973         /* If the destination is DistQueue, then cursor (iParm+1) is open
 974         ** on a second ephemeral index that holds all values every previously
 975         ** added to the queue. */
 976         addrTest = sqlite3VdbeAddOp4Int(v, OP_Found, iParm+1, 0,
 977                                         regResult, nResultCol);
 978         VdbeCoverage(v);
 979       }
 980       sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r3);
 981       if( eDest==SRT_DistQueue ){
 982         sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm+1, r3);
 983         sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
 984       }
 985       for(i=0; i<nKey; i++){
 986         sqlite3VdbeAddOp2(v, OP_SCopy,
 987                           regResult + pSO->a[i].u.x.iOrderByCol - 1,
 988                           r2+i);
 989       }
 990       sqlite3VdbeAddOp2(v, OP_Sequence, iParm, r2+nKey);
 991       sqlite3VdbeAddOp3(v, OP_MakeRecord, r2, nKey+2, r1);
 992       sqlite3VdbeAddOp4Int(v, OP_IdxInsert, iParm, r1, r2, nKey+2);
 993       if( addrTest ) sqlite3VdbeJumpHere(v, addrTest);
 994       sqlite3ReleaseTempReg(pParse, r1);
 995       sqlite3ReleaseTempRange(pParse, r2, nKey+2);
 996       break;
 997     }
 998 #endif /* SQLITE_OMIT_CTE */
 999
1000
1001
1002 #if !defined(SQLITE_OMIT_TRIGGER)
1003     /* Discard the results.  This is used for SELECT statements inside
1004     ** the body of a TRIGGER.  The purpose of such selects is to call
1005     ** user-defined functions that have side effects.  We do not care
1006     ** about the actual results of the select.
1007     */
1008     default: {
1009       assert( eDest==SRT_Discard );
1010       break;
1011     }
1012 #endif
1013   }
1014
1015   /* Jump to the end of the loop if the LIMIT is reached.  Except, if
1016   ** there is a sorter, in which case the sorter has already limited
1017   ** the output for us.
1018   */
1019   if( pSort==0 && p->iLimit ){
1020     sqlite3VdbeAddOp2(v, OP_DecrJumpZero, p->iLimit, iBreak); VdbeCoverage(v);
1021   }
1022 }
1023
1024 /*
1025 ** Allocate a KeyInfo object sufficient for an index of N key columns and
1026 ** X extra columns.
1027 */
1028 KeyInfo *sqlite3KeyInfoAlloc(sqlite3 *db, int N, int X){
1029   int nExtra = (N+X)*(sizeof(CollSeq*)+1) - sizeof(CollSeq*);
1030   KeyInfo *p = sqlite3DbMallocRawNN(db, sizeof(KeyInfo) + nExtra);
1031   if( p ){
1032     p->aSortOrder = (u8*)&p->aColl[N+X];
1033     p->nKeyField = (u16)N;
1034     p->nAllField = (u16)(N+X);
1035     p->enc = ENC(db);
1036     p->db = db;
1037     p->nRef = 1;
1038     memset(&p[1], 0, nExtra);
1039   }else{
1040     sqlite3OomFault(db);
1041   }
1042   return p;
1043 }
1044
1045 /*
1046 ** Deallocate a KeyInfo object
1047 */
1048 void sqlite3KeyInfoUnref(KeyInfo *p){
1049   if( p ){
1050     assert( p->nRef>0 );
1051     p->nRef--;
1052     if( p->nRef==0 ) sqlite3DbFreeNN(p->db, p);
1053   }
1054 }
1055
1056 /*
1057 ** Make a new pointer to a KeyInfo object
1058 */
1059 KeyInfo *sqlite3KeyInfoRef(KeyInfo *p){
1060   if( p ){
1061     assert( p->nRef>0 );
1062     p->nRef++;
1063   }
1064   return p;
1065 }
1066
1067 #ifdef SQLITE_DEBUG
1068 /*
1069 ** Return TRUE if a KeyInfo object can be change.  The KeyInfo object
1070 ** can only be changed if this is just a single reference to the object.
1071 **
1072 ** This routine is used only inside of assert() statements.
1073 */
1074 int sqlite3KeyInfoIsWriteable(KeyInfo *p){ return p->nRef==1; }
1075 #endif /* SQLITE_DEBUG */
1076
1077 /*
1078 ** Given an expression list, generate a KeyInfo structure that records
1079 ** the collating sequence for each expression in that expression list.
1080 **
1081 ** If the ExprList is an ORDER BY or GROUP BY clause then the resulting
1082 ** KeyInfo structure is appropriate for initializing a virtual index to
1083 ** implement that clause.  If the ExprList is the result set of a SELECT
1084 ** then the KeyInfo structure is appropriate for initializing a virtual
1085 ** index to implement a DISTINCT test.
1086 **
1087 ** Space to hold the KeyInfo structure is obtained from malloc.  The calling
1088 ** function is responsible for seeing that this structure is eventually
1089 ** freed.
1090 */
1091 static KeyInfo *keyInfoFromExprList(
1092   Parse *pParse,       /* Parsing context */
1093   ExprList *pList,     /* Form the KeyInfo object from this ExprList */
1094   int iStart,          /* Begin with this column of pList */
1095   int nExtra           /* Add this many extra columns to the end */
1096 ){
1097   int nExpr;
1098   KeyInfo *pInfo;
1099   struct ExprList_item *pItem;
1100   sqlite3 *db = pParse->db;
1101   int i;
1102
1103   nExpr = pList->nExpr;
1104   pInfo = sqlite3KeyInfoAlloc(db, nExpr-iStart, nExtra+1);
1105   if( pInfo ){
1106     assert( sqlite3KeyInfoIsWriteable(pInfo) );
1107     for(i=iStart, pItem=pList->a+iStart; i<nExpr; i++, pItem++){
1108       pInfo->aColl[i-iStart] = sqlite3ExprNNCollSeq(pParse, pItem->pExpr);
1109       pInfo->aSortOrder[i-iStart] = pItem->sortOrder;
1110     }
1111   }
1112   return pInfo;
1113 }
1114
1115 /*
1116 ** Name of the connection operator, used for error messages.
1117 */
1118 static const char *selectOpName(int id){
1119   char *z;
1120   switch( id ){
1121     case TK_ALL:       z = "UNION ALL";   break;
1122     case TK_INTERSECT: z = "INTERSECT";   break;
1123     case TK_EXCEPT:    z = "EXCEPT";      break;
1124     default:           z = "UNION";       break;
1125   }
1126   return z;
1127 }
1128
1129 #ifndef SQLITE_OMIT_EXPLAIN
1130 /*
1131 ** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function
1132 ** is a no-op. Otherwise, it adds a single row of output to the EQP result,
1133 ** where the caption is of the form:
1134 **
1135 **   "USE TEMP B-TREE FOR xxx"
1136 **
1137 ** where xxx is one of "DISTINCT", "ORDER BY" or "GROUP BY". Exactly which
1138 ** is determined by the zUsage argument.
1139 */
1140 static void explainTempTable(Parse *pParse, const char *zUsage){
1141   if( pParse->explain==2 ){
1142     Vdbe *v = pParse->pVdbe;
1143     char *zMsg = sqlite3MPrintf(pParse->db, "USE TEMP B-TREE FOR %s", zUsage);
1144     sqlite3VdbeAddOp4(v, OP_Explain, pParse->iSelectId, 0, 0, zMsg, P4_DYNAMIC);
1145   }
1146 }
1147
1148 /*
1149 ** Assign expression b to lvalue a. A second, no-op, version of this macro
1150 ** is provided when SQLITE_OMIT_EXPLAIN is defined. This allows the code
1151 ** in sqlite3Select() to assign values to structure member variables that
1152 ** only exist if SQLITE_OMIT_EXPLAIN is not defined without polluting the
1153 ** code with #ifndef directives.
1154 */
1155 # define explainSetInteger(a, b) a = b
1156
1157 #else
1158 /* No-op versions of the explainXXX() functions and macros. */
1159 # define explainTempTable(y,z)
1160 # define explainSetInteger(y,z)
1161 #endif
1162
1163 #if !defined(SQLITE_OMIT_EXPLAIN) && !defined(SQLITE_OMIT_COMPOUND_SELECT)
1164 /*
1165 ** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function
1166 ** is a no-op. Otherwise, it adds a single row of output to the EQP result,
1167 ** where the caption is of one of the two forms:
1168 **
1169 **   "COMPOSITE SUBQUERIES iSub1 and iSub2 (op)"
1170 **   "COMPOSITE SUBQUERIES iSub1 and iSub2 USING TEMP B-TREE (op)"
1171 **
1172 ** where iSub1 and iSub2 are the integers passed as the corresponding
1173 ** function parameters, and op is the text representation of the parameter
1174 ** of the same name. The parameter "op" must be one of TK_UNION, TK_EXCEPT,
1175 ** TK_INTERSECT or TK_ALL. The first form is used if argument bUseTmp is
1176 ** false, or the second form if it is true.
1177 */
1178 static void explainComposite(
1179   Parse *pParse,                  /* Parse context */
1180   int op,                         /* One of TK_UNION, TK_EXCEPT etc. */
1181   int iSub1,                      /* Subquery id 1 */
1182   int iSub2,                      /* Subquery id 2 */
1183   int bUseTmp                     /* True if a temp table was used */
1184 ){
1185   assert( op==TK_UNION || op==TK_EXCEPT || op==TK_INTERSECT || op==TK_ALL );
1186   if( pParse->explain==2 ){
1187     Vdbe *v = pParse->pVdbe;
1188     char *zMsg = sqlite3MPrintf(
1189         pParse->db, "COMPOUND SUBQUERIES %d AND %d %s(%s)", iSub1, iSub2,
1190         bUseTmp?"USING TEMP B-TREE ":"", selectOpName(op)
1191     );
1192     sqlite3VdbeAddOp4(v, OP_Explain, pParse->iSelectId, 0, 0, zMsg, P4_DYNAMIC);
1193   }
1194 }
1195 #else
1196 /* No-op versions of the explainXXX() functions and macros. */
1197 # define explainComposite(v,w,x,y,z)
1198 #endif
1199
1200 /*
1201 ** If the inner loop was generated using a non-null pOrderBy argument,
1202 ** then the results were placed in a sorter.  After the loop is terminated
1203 ** we need to run the sorter and output the results.  The following
1204 ** routine generates the code needed to do that.
1205 */
1206 static void generateSortTail(
1207   Parse *pParse,    /* Parsing context */
1208   Select *p,        /* The SELECT statement */
1209   SortCtx *pSort,   /* Information on the ORDER BY clause */
1210   int nColumn,      /* Number of columns of data */
1211   SelectDest *pDest /* Write the sorted results here */
1212 ){
1213   Vdbe *v = pParse->pVdbe;                     /* The prepared statement */
1214   int addrBreak = pSort->labelDone;            /* Jump here to exit loop */
1215   int addrContinue = sqlite3VdbeMakeLabel(v);  /* Jump here for next cycle */
1216   int addr;
1217   int addrOnce = 0;
1218   int iTab;
1219   ExprList *pOrderBy = pSort->pOrderBy;
1220   int eDest = pDest->eDest;
1221   int iParm = pDest->iSDParm;
1222   int regRow;
1223   int regRowid;
1224   int iCol;
1225   int nKey;
1226   int iSortTab;                   /* Sorter cursor to read from */
1227   int nSortData;                  /* Trailing values to read from sorter */
1228   int i;
1229   int bSeq;                       /* True if sorter record includes seq. no. */
1230   struct ExprList_item *aOutEx = p->pEList->a;
1231
1232   assert( addrBreak<0 );
1233   if( pSort->labelBkOut ){
1234     sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut);
1235     sqlite3VdbeGoto(v, addrBreak);
1236     sqlite3VdbeResolveLabel(v, pSort->labelBkOut);
1237   }
1238   iTab = pSort->iECursor;
1239   if( eDest==SRT_Output || eDest==SRT_Coroutine || eDest==SRT_Mem ){
1240     regRowid = 0;
1241     regRow = pDest->iSdst;
1242     nSortData = nColumn;
1243   }else{
1244     regRowid = sqlite3GetTempReg(pParse);
1245     regRow = sqlite3GetTempRange(pParse, nColumn);
1246     nSortData = nColumn;
1247   }
1248   nKey = pOrderBy->nExpr - pSort->nOBSat;
1249   if( pSort->sortFlags & SORTFLAG_UseSorter ){
1250     int regSortOut = ++pParse->nMem;
1251     iSortTab = pParse->nTab++;
1252     if( pSort->labelBkOut ){
1253       addrOnce = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
1254     }
1255     sqlite3VdbeAddOp3(v, OP_OpenPseudo, iSortTab, regSortOut, nKey+1+nSortData);
1256     if( addrOnce ) sqlite3VdbeJumpHere(v, addrOnce);
1257     addr = 1 + sqlite3VdbeAddOp2(v, OP_SorterSort, iTab, addrBreak);
1258     VdbeCoverage(v);
1259     codeOffset(v, p->iOffset, addrContinue);
1260     sqlite3VdbeAddOp3(v, OP_SorterData, iTab, regSortOut, iSortTab);
1261     bSeq = 0;
1262   }else{
1263     addr = 1 + sqlite3VdbeAddOp2(v, OP_Sort, iTab, addrBreak); VdbeCoverage(v);
1264     codeOffset(v, p->iOffset, addrContinue);
1265     iSortTab = iTab;
1266     bSeq = 1;
1267   }
1268   for(i=0, iCol=nKey+bSeq-1; i<nSortData; i++){
1269     if( aOutEx[i].u.x.iOrderByCol==0 ) iCol++;
1270   }
1271   for(i=nSortData-1; i>=0; i--){
1272     int iRead;
1273     if( aOutEx[i].u.x.iOrderByCol ){
1274       iRead = aOutEx[i].u.x.iOrderByCol-1;
1275     }else{
1276       iRead = iCol--;
1277     }
1278     sqlite3VdbeAddOp3(v, OP_Column, iSortTab, iRead, regRow+i);
1279     VdbeComment((v, "%s", aOutEx[i].zName ? aOutEx[i].zName : aOutEx[i].zSpan));
1280   }
1281   switch( eDest ){
1282     case SRT_Table:
1283     case SRT_EphemTab: {
1284       sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, regRowid);
1285       sqlite3VdbeAddOp3(v, OP_Insert, iParm, regRow, regRowid);
1286       sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
1287       break;
1288     }
1289 #ifndef SQLITE_OMIT_SUBQUERY
1290     case SRT_Set: {
1291       assert( nColumn==sqlite3Strlen30(pDest->zAffSdst) );
1292       sqlite3VdbeAddOp4(v, OP_MakeRecord, regRow, nColumn, regRowid,
1293                         pDest->zAffSdst, nColumn);
1294       sqlite3ExprCacheAffinityChange(pParse, regRow, nColumn);
1295       sqlite3VdbeAddOp4Int(v, OP_IdxInsert, iParm, regRowid, regRow, nColumn);
1296       break;
1297     }
1298     case SRT_Mem: {
1299       /* The LIMIT clause will terminate the loop for us */
1300       break;
1301     }
1302 #endif
1303     default: {
1304       assert( eDest==SRT_Output || eDest==SRT_Coroutine );
1305       testcase( eDest==SRT_Output );
1306       testcase( eDest==SRT_Coroutine );
1307       if( eDest==SRT_Output ){
1308         sqlite3VdbeAddOp2(v, OP_ResultRow, pDest->iSdst, nColumn);
1309         sqlite3ExprCacheAffinityChange(pParse, pDest->iSdst, nColumn);
1310       }else{
1311         sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm);
1312       }
1313       break;
1314     }
1315   }
1316   if( regRowid ){
1317     if( eDest==SRT_Set ){
1318       sqlite3ReleaseTempRange(pParse, regRow, nColumn);
1319     }else{
1320       sqlite3ReleaseTempReg(pParse, regRow);
1321     }
1322     sqlite3ReleaseTempReg(pParse, regRowid);
1323   }
1324   /* The bottom of the loop
1325   */
1326   sqlite3VdbeResolveLabel(v, addrContinue);
1327   if( pSort->sortFlags & SORTFLAG_UseSorter ){
1328     sqlite3VdbeAddOp2(v, OP_SorterNext, iTab, addr); VdbeCoverage(v);
1329   }else{
1330     sqlite3VdbeAddOp2(v, OP_Next, iTab, addr); VdbeCoverage(v);
1331   }
1332   if( pSort->regReturn ) sqlite3VdbeAddOp1(v, OP_Return, pSort->regReturn);
1333   sqlite3VdbeResolveLabel(v, addrBreak);
1334 }
1335
1336 /*
1337 ** Return a pointer to a string containing the 'declaration type' of the
1338 ** expression pExpr. The string may be treated as static by the caller.
1339 **
1340 ** Also try to estimate the size of the returned value and return that
1341 ** result in *pEstWidth.
1342 **
1343 ** The declaration type is the exact datatype definition extracted from the
1344 ** original CREATE TABLE statement if the expression is a column. The
1345 ** declaration type for a ROWID field is INTEGER. Exactly when an expression
1346 ** is considered a column can be complex in the presence of subqueries. The
1347 ** result-set expression in all of the following SELECT statements is
1348 ** considered a column by this function.
1349 **
1350 **   SELECT col FROM tbl;
1351 **   SELECT (SELECT col FROM tbl;
1352 **   SELECT (SELECT col FROM tbl);
1353 **   SELECT abc FROM (SELECT col AS abc FROM tbl);
1354 **
1355 ** The declaration type for any expression other than a column is NULL.
1356 **
1357 ** This routine has either 3 or 6 parameters depending on whether or not
1358 ** the SQLITE_ENABLE_COLUMN_METADATA compile-time option is used.
1359 */
1360 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1361 # define columnType(A,B,C,D,E) columnTypeImpl(A,B,C,D,E)
1362 #else /* if !defined(SQLITE_ENABLE_COLUMN_METADATA) */
1363 # define columnType(A,B,C,D,E) columnTypeImpl(A,B)
1364 #endif
1365 static const char *columnTypeImpl(
1366   NameContext *pNC,
1367 #ifndef SQLITE_ENABLE_COLUMN_METADATA
1368   Expr *pExpr
1369 #else
1370   Expr *pExpr,
1371   const char **pzOrigDb,
1372   const char **pzOrigTab,
1373   const char **pzOrigCol
1374 #endif
1375 ){
1376   char const *zType = 0;
1377   int j;
1378 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1379   char const *zOrigDb = 0;
1380   char const *zOrigTab = 0;
1381   char const *zOrigCol = 0;
1382 #endif
1383
1384   assert( pExpr!=0 );
1385   assert( pNC->pSrcList!=0 );
1386   assert( pExpr->op!=TK_AGG_COLUMN );  /* This routine runes before aggregates
1387                                        ** are processed */
1388   switch( pExpr->op ){
1389     case TK_COLUMN: {
1390       /* The expression is a column. Locate the table the column is being
1391       ** extracted from in NameContext.pSrcList. This table may be real
1392       ** database table or a subquery.
1393       */
1394       Table *pTab = 0;            /* Table structure column is extracted from */
1395       Select *pS = 0;             /* Select the column is extracted from */
1396       int iCol = pExpr->iColumn;  /* Index of column in pTab */
1397       while( pNC && !pTab ){
1398         SrcList *pTabList = pNC->pSrcList;
1399         for(j=0;j<pTabList->nSrc && pTabList->a[j].iCursor!=pExpr->iTable;j++);
1400         if( j<pTabList->nSrc ){
1401           pTab = pTabList->a[j].pTab;
1402           pS = pTabList->a[j].pSelect;
1403         }else{
1404           pNC = pNC->pNext;
1405         }
1406       }
1407
1408       if( pTab==0 ){
1409         /* At one time, code such as "SELECT new.x" within a trigger would
1410         ** cause this condition to run.  Since then, we have restructured how
1411         ** trigger code is generated and so this condition is no longer
1412         ** possible. However, it can still be true for statements like
1413         ** the following:
1414         **
1415         **   CREATE TABLE t1(col INTEGER);
1416         **   SELECT (SELECT t1.col) FROM FROM t1;
1417         **
1418         ** when columnType() is called on the expression "t1.col" in the
1419         ** sub-select. In this case, set the column type to NULL, even
1420         ** though it should really be "INTEGER".
1421         **
1422         ** This is not a problem, as the column type of "t1.col" is never
1423         ** used. When columnType() is called on the expression
1424         ** "(SELECT t1.col)", the correct type is returned (see the TK_SELECT
1425         ** branch below.  */
1426         break;
1427       }
1428
1429       assert( pTab && pExpr->pTab==pTab );
1430       if( pS ){
1431         /* The "table" is actually a sub-select or a view in the FROM clause
1432         ** of the SELECT statement. Return the declaration type and origin
1433         ** data for the result-set column of the sub-select.
1434         */
1435         if( iCol>=0 && iCol<pS->pEList->nExpr ){
1436           /* If iCol is less than zero, then the expression requests the
1437           ** rowid of the sub-select or view. This expression is legal (see
1438           ** test case misc2.2.2) - it always evaluates to NULL.
1439           */
1440           NameContext sNC;
1441           Expr *p = pS->pEList->a[iCol].pExpr;
1442           sNC.pSrcList = pS->pSrc;
1443           sNC.pNext = pNC;
1444           sNC.pParse = pNC->pParse;
1445           zType = columnType(&sNC, p,&zOrigDb,&zOrigTab,&zOrigCol);
1446         }
1447       }else{
1448         /* A real table or a CTE table */
1449         assert( !pS );
1450 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1451         if( iCol<0 ) iCol = pTab->iPKey;
1452         assert( iCol==XN_ROWID || (iCol>=0 && iCol<pTab->nCol) );
1453         if( iCol<0 ){
1454           zType = "INTEGER";
1455           zOrigCol = "rowid";
1456         }else{
1457           zOrigCol = pTab->aCol[iCol].zName;
1458           zType = sqlite3ColumnType(&pTab->aCol[iCol],0);
1459         }
1460         zOrigTab = pTab->zName;
1461         if( pNC->pParse && pTab->pSchema ){
1462           int iDb = sqlite3SchemaToIndex(pNC->pParse->db, pTab->pSchema);
1463           zOrigDb = pNC->pParse->db->aDb[iDb].zDbSName;
1464         }
1465 #else
1466         assert( iCol==XN_ROWID || (iCol>=0 && iCol<pTab->nCol) );
1467         if( iCol<0 ){
1468           zType = "INTEGER";
1469         }else{
1470           zType = sqlite3ColumnType(&pTab->aCol[iCol],0);
1471         }
1472 #endif
1473       }
1474       break;
1475     }
1476 #ifndef SQLITE_OMIT_SUBQUERY
1477     case TK_SELECT: {
1478       /* The expression is a sub-select. Return the declaration type and
1479       ** origin info for the single column in the result set of the SELECT
1480       ** statement.
1481       */
1482       NameContext sNC;
1483       Select *pS = pExpr->x.pSelect;
1484       Expr *p = pS->pEList->a[0].pExpr;
1485       assert( ExprHasProperty(pExpr, EP_xIsSelect) );
1486       sNC.pSrcList = pS->pSrc;
1487       sNC.pNext = pNC;
1488       sNC.pParse = pNC->pParse;
1489       zType = columnType(&sNC, p, &zOrigDb, &zOrigTab, &zOrigCol);
1490       break;
1491     }
1492 #endif
1493   }
1494
1495 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1496   if( pzOrigDb ){
1497     assert( pzOrigTab && pzOrigCol );
1498     *pzOrigDb = zOrigDb;
1499     *pzOrigTab = zOrigTab;
1500     *pzOrigCol = zOrigCol;
1501   }
1502 #endif
1503   return zType;
1504 }
1505
1506 /*
1507 ** Generate code that will tell the VDBE the declaration types of columns
1508 ** in the result set.
1509 */
1510 static void generateColumnTypes(
1511   Parse *pParse,      /* Parser context */
1512   SrcList *pTabList,  /* List of tables */
1513   ExprList *pEList    /* Expressions defining the result set */
1514 ){
1515 #ifndef SQLITE_OMIT_DECLTYPE
1516   Vdbe *v = pParse->pVdbe;
1517   int i;
1518   NameContext sNC;
1519   sNC.pSrcList = pTabList;
1520   sNC.pParse = pParse;
1521   sNC.pNext = 0;
1522   for(i=0; i<pEList->nExpr; i++){
1523     Expr *p = pEList->a[i].pExpr;
1524     const char *zType;
1525 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1526     const char *zOrigDb = 0;
1527     const char *zOrigTab = 0;
1528     const char *zOrigCol = 0;
1529     zType = columnType(&sNC, p, &zOrigDb, &zOrigTab, &zOrigCol);
1530
1531     /* The vdbe must make its own copy of the column-type and other
1532     ** column specific strings, in case the schema is reset before this
1533     ** virtual machine is deleted.
1534     */
1535     sqlite3VdbeSetColName(v, i, COLNAME_DATABASE, zOrigDb, SQLITE_TRANSIENT);
1536     sqlite3VdbeSetColName(v, i, COLNAME_TABLE, zOrigTab, SQLITE_TRANSIENT);
1537     sqlite3VdbeSetColName(v, i, COLNAME_COLUMN, zOrigCol, SQLITE_TRANSIENT);
1538 #else
1539     zType = columnType(&sNC, p, 0, 0, 0);
1540 #endif
1541     sqlite3VdbeSetColName(v, i, COLNAME_DECLTYPE, zType, SQLITE_TRANSIENT);
1542   }
1543 #endif /* !defined(SQLITE_OMIT_DECLTYPE) */
1544 }
1545
1546
1547 /*
1548 ** Compute the column names for a SELECT statement.
1549 **
1550 ** The only guarantee that SQLite makes about column names is that if the
1551 ** column has an AS clause assigning it a name, that will be the name used.
1552 ** That is the only documented guarantee.  However, countless applications
1553 ** developed over the years have made baseless assumptions about column names
1554 ** and will break if those assumptions changes.  Hence, use extreme caution
1555 ** when modifying this routine to avoid breaking legacy.
1556 **
1557 ** See Also: sqlite3ColumnsFromExprList()
1558 **
1559 ** The PRAGMA short_column_names and PRAGMA full_column_names settings are
1560 ** deprecated.  The default setting is short=ON, full=OFF.  99.9% of all
1561 ** applications should operate this way.  Nevertheless, we need to support the
1562 ** other modes for legacy:
1563 **
1564 **    short=OFF, full=OFF:      Column name is the text of the expression has it
1565 **                              originally appears in the SELECT statement.  In
1566 **                              other words, the zSpan of the result expression.
1567 **
1568 **    short=ON, full=OFF:       (This is the default setting).  If the result
1569 **                              refers directly to a table column, then the
1570 **                              result column name is just the table column
1571 **                              name: COLUMN.  Otherwise use zSpan.
1572 **
1573 **    full=ON, short=ANY:       If the result refers directly to a table column,
1574 **                              then the result column name with the table name
1575 **                              prefix, ex: TABLE.COLUMN.  Otherwise use zSpan.
1576 */
1577 static void generateColumnNames(
1578   Parse *pParse,      /* Parser context */
1579   Select *pSelect     /* Generate column names for this SELECT statement */
1580 ){
1581   Vdbe *v = pParse->pVdbe;
1582   int i;
1583   Table *pTab;
1584   SrcList *pTabList;
1585   ExprList *pEList;
1586   sqlite3 *db = pParse->db;
1587   int fullName;    /* TABLE.COLUMN if no AS clause and is a direct table ref */
1588   int srcName;     /* COLUMN or TABLE.COLUMN if no AS clause and is direct */
1589
1590 #ifndef SQLITE_OMIT_EXPLAIN
1591   /* If this is an EXPLAIN, skip this step */
1592   if( pParse->explain ){
1593     return;
1594   }
1595 #endif
1596
1597   if( pParse->colNamesSet || db->mallocFailed ) return;
1598   /* Column names are determined by the left-most term of a compound select */
1599   while( pSelect->pPrior ) pSelect = pSelect->pPrior;
1600   SELECTTRACE(1,pParse,pSelect,("generating column names\n"));
1601   pTabList = pSelect->pSrc;
1602   pEList = pSelect->pEList;
1603   assert( v!=0 );
1604   assert( pTabList!=0 );
1605   pParse->colNamesSet = 1;
1606   fullName = (db->flags & SQLITE_FullColNames)!=0;
1607   srcName = (db->flags & SQLITE_ShortColNames)!=0 || fullName;
1608   sqlite3VdbeSetNumCols(v, pEList->nExpr);
1609   for(i=0; i<pEList->nExpr; i++){
1610     Expr *p = pEList->a[i].pExpr;
1611
1612     assert( p!=0 );
1613     assert( p->op!=TK_AGG_COLUMN );  /* Agg processing has not run yet */
1614     assert( p->op!=TK_COLUMN || p->pTab!=0 ); /* Covering idx not yet coded */
1615     if( pEList->a[i].zName ){
1616       /* An AS clause always takes first priority */
1617       char *zName = pEList->a[i].zName;
1618       sqlite3VdbeSetColName(v, i, COLNAME_NAME, zName, SQLITE_TRANSIENT);
1619     }else if( srcName && p->op==TK_COLUMN ){
1620       char *zCol;
1621       int iCol = p->iColumn;
1622       pTab = p->pTab;
1623       assert( pTab!=0 );
1624       if( iCol<0 ) iCol = pTab->iPKey;
1625       assert( iCol==-1 || (iCol>=0 && iCol<pTab->nCol) );
1626       if( iCol<0 ){
1627         zCol = "rowid";
1628       }else{
1629         zCol = pTab->aCol[iCol].zName;
1630       }
1631       if( fullName ){
1632         char *zName = 0;
1633         zName = sqlite3MPrintf(db, "%s.%s", pTab->zName, zCol);
1634         sqlite3VdbeSetColName(v, i, COLNAME_NAME, zName, SQLITE_DYNAMIC);
1635       }else{
1636         sqlite3VdbeSetColName(v, i, COLNAME_NAME, zCol, SQLITE_TRANSIENT);
1637       }
1638     }else{
1639       const char *z = pEList->a[i].zSpan;
1640       z = z==0 ? sqlite3MPrintf(db, "column%d", i+1) : sqlite3DbStrDup(db, z);
1641       sqlite3VdbeSetColName(v, i, COLNAME_NAME, z, SQLITE_DYNAMIC);
1642     }
1643   }
1644   generateColumnTypes(pParse, pTabList, pEList);
1645 }
1646
1647 /*
1648 ** Given an expression list (which is really the list of expressions
1649 ** that form the result set of a SELECT statement) compute appropriate
1650 ** column names for a table that would hold the expression list.
1651 **
1652 ** All column names will be unique.
1653 **
1654 ** Only the column names are computed.  Column.zType, Column.zColl,
1655 ** and other fields of Column are zeroed.
1656 **
1657 ** Return SQLITE_OK on success.  If a memory allocation error occurs,
1658 ** store NULL in *paCol and 0 in *pnCol and return SQLITE_NOMEM.
1659 **
1660 ** The only guarantee that SQLite makes about column names is that if the
1661 ** column has an AS clause assigning it a name, that will be the name used.
1662 ** That is the only documented guarantee.  However, countless applications
1663 ** developed over the years have made baseless assumptions about column names
1664 ** and will break if those assumptions changes.  Hence, use extreme caution
1665 ** when modifying this routine to avoid breaking legacy.
1666 **
1667 ** See Also: generateColumnNames()
1668 */
1669 int sqlite3ColumnsFromExprList(
1670   Parse *pParse,          /* Parsing context */
1671   ExprList *pEList,       /* Expr list from which to derive column names */
1672   i16 *pnCol,             /* Write the number of columns here */
1673   Column **paCol          /* Write the new column list here */
1674 ){
1675   sqlite3 *db = pParse->db;   /* Database connection */
1676   int i, j;                   /* Loop counters */
1677   u32 cnt;                    /* Index added to make the name unique */
1678   Column *aCol, *pCol;        /* For looping over result columns */
1679   int nCol;                   /* Number of columns in the result set */
1680   char *zName;                /* Column name */
1681   int nName;                  /* Size of name in zName[] */
1682   Hash ht;                    /* Hash table of column names */
1683
1684   sqlite3HashInit(&ht);
1685   if( pEList ){
1686     nCol = pEList->nExpr;
1687     aCol = sqlite3DbMallocZero(db, sizeof(aCol[0])*nCol);
1688     testcase( aCol==0 );
1689     if( nCol>32767 ) nCol = 32767;
1690   }else{
1691     nCol = 0;
1692     aCol = 0;
1693   }
1694   assert( nCol==(i16)nCol );
1695   *pnCol = nCol;
1696   *paCol = aCol;
1697
1698   for(i=0, pCol=aCol; i<nCol && !db->mallocFailed; i++, pCol++){
1699     /* Get an appropriate name for the column
1700     */
1701     if( (zName = pEList->a[i].zName)!=0 ){
1702       /* If the column contains an "AS <name>" phrase, use <name> as the name */
1703     }else{
1704       Expr *pColExpr = sqlite3ExprSkipCollate(pEList->a[i].pExpr);
1705       while( pColExpr->op==TK_DOT ){
1706         pColExpr = pColExpr->pRight;
1707         assert( pColExpr!=0 );
1708       }
1709       assert( pColExpr->op!=TK_AGG_COLUMN );
1710       if( pColExpr->op==TK_COLUMN ){
1711         /* For columns use the column name name */
1712         int iCol = pColExpr->iColumn;
1713         Table *pTab = pColExpr->pTab;
1714         assert( pTab!=0 );
1715         if( iCol<0 ) iCol = pTab->iPKey;
1716         zName = iCol>=0 ? pTab->aCol[iCol].zName : "rowid";
1717       }else if( pColExpr->op==TK_ID ){
1718         assert( !ExprHasProperty(pColExpr, EP_IntValue) );
1719         zName = pColExpr->u.zToken;
1720       }else{
1721         /* Use the original text of the column expression as its name */
1722         zName = pEList->a[i].zSpan;
1723       }
1724     }
1725     if( zName ){
1726       zName = sqlite3DbStrDup(db, zName);
1727     }else{
1728       zName = sqlite3MPrintf(db,"column%d",i+1);
1729     }
1730
1731     /* Make sure the column name is unique.  If the name is not unique,
1732     ** append an integer to the name so that it becomes unique.
1733     */
1734     cnt = 0;
1735     while( zName && sqlite3HashFind(&ht, zName)!=0 ){
1736       nName = sqlite3Strlen30(zName);
1737       if( nName>0 ){
1738         for(j=nName-1; j>0 && sqlite3Isdigit(zName[j]); j--){}
1739         if( zName[j]==':' ) nName = j;
1740       }
1741       zName = sqlite3MPrintf(db, "%.*z:%u", nName, zName, ++cnt);
1742       if( cnt>3 ) sqlite3_randomness(sizeof(cnt), &cnt);
1743     }
1744     pCol->zName = zName;
1745     sqlite3ColumnPropertiesFromName(0, pCol);
1746     if( zName && sqlite3HashInsert(&ht, zName, pCol)==pCol ){
1747       sqlite3OomFault(db);
1748     }
1749   }
1750   sqlite3HashClear(&ht);
1751   if( db->mallocFailed ){
1752     for(j=0; j<i; j++){
1753       sqlite3DbFree(db, aCol[j].zName);
1754     }
1755     sqlite3DbFree(db, aCol);
1756     *paCol = 0;
1757     *pnCol = 0;
1758     return SQLITE_NOMEM_BKPT;
1759   }
1760   return SQLITE_OK;
1761 }
1762
1763 /*
1764 ** Add type and collation information to a column list based on
1765 ** a SELECT statement.
1766 **
1767 ** The column list presumably came from selectColumnNamesFromExprList().
1768 ** The column list has only names, not types or collations.  This
1769 ** routine goes through and adds the types and collations.
1770 **
1771 ** This routine requires that all identifiers in the SELECT
1772 ** statement be resolved.
1773 */
1774 void sqlite3SelectAddColumnTypeAndCollation(
1775   Parse *pParse,        /* Parsing contexts */
1776   Table *pTab,          /* Add column type information to this table */
1777   Select *pSelect       /* SELECT used to determine types and collations */
1778 ){
1779   sqlite3 *db = pParse->db;
1780   NameContext sNC;
1781   Column *pCol;
1782   CollSeq *pColl;
1783   int i;
1784   Expr *p;
1785   struct ExprList_item *a;
1786
1787   assert( pSelect!=0 );
1788   assert( (pSelect->selFlags & SF_Resolved)!=0 );
1789   assert( pTab->nCol==pSelect->pEList->nExpr || db->mallocFailed );
1790   if( db->mallocFailed ) return;
1791   memset(&sNC, 0, sizeof(sNC));
1792   sNC.pSrcList = pSelect->pSrc;
1793   a = pSelect->pEList->a;
1794   for(i=0, pCol=pTab->aCol; i<pTab->nCol; i++, pCol++){
1795     const char *zType;
1796     int n, m;
1797     p = a[i].pExpr;
1798     zType = columnType(&sNC, p, 0, 0, 0);
1799     /* pCol->szEst = ... // Column size est for SELECT tables never used */
1800     pCol->affinity = sqlite3ExprAffinity(p);
1801     if( zType ){
1802       m = sqlite3Strlen30(zType);
1803       n = sqlite3Strlen30(pCol->zName);
1804       pCol->zName = sqlite3DbReallocOrFree(db, pCol->zName, n+m+2);
1805       if( pCol->zName ){
1806         memcpy(&pCol->zName[n+1], zType, m+1);
1807         pCol->colFlags |= COLFLAG_HASTYPE;
1808       }
1809     }
1810     if( pCol->affinity==0 ) pCol->affinity = SQLITE_AFF_BLOB;
1811     pColl = sqlite3ExprCollSeq(pParse, p);
1812     if( pColl && pCol->zColl==0 ){
1813       pCol->zColl = sqlite3DbStrDup(db, pColl->zName);
1814     }
1815   }
1816   pTab->szTabRow = 1; /* Any non-zero value works */
1817 }
1818
1819 /*
1820 ** Given a SELECT statement, generate a Table structure that describes
1821 ** the result set of that SELECT.
1822 */
1823 Table *sqlite3ResultSetOfSelect(Parse *pParse, Select *pSelect){
1824   Table *pTab;
1825   sqlite3 *db = pParse->db;
1826   int savedFlags;
1827
1828   savedFlags = db->flags;
1829   db->flags &= ~SQLITE_FullColNames;
1830   db->flags |= SQLITE_ShortColNames;
1831   sqlite3SelectPrep(pParse, pSelect, 0);
1832   if( pParse->nErr ) return 0;
1833   while( pSelect->pPrior ) pSelect = pSelect->pPrior;
1834   db->flags = savedFlags;
1835   pTab = sqlite3DbMallocZero(db, sizeof(Table) );
1836   if( pTab==0 ){
1837     return 0;
1838   }
1839   /* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside
1840   ** is disabled */
1841   assert( db->lookaside.bDisable );
1842   pTab->nTabRef = 1;
1843   pTab->zName = 0;
1844   pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );
1845   sqlite3ColumnsFromExprList(pParse, pSelect->pEList, &pTab->nCol, &pTab->aCol);
1846   sqlite3SelectAddColumnTypeAndCollation(pParse, pTab, pSelect);
1847   pTab->iPKey = -1;
1848   if( db->mallocFailed ){
1849     sqlite3DeleteTable(db, pTab);
1850     return 0;
1851   }
1852   return pTab;
1853 }
1854
1855 /*
1856 ** Get a VDBE for the given parser context.  Create a new one if necessary.
1857 ** If an error occurs, return NULL and leave a message in pParse.
1858 */
1859 Vdbe *sqlite3GetVdbe(Parse *pParse){
1860   if( pParse->pVdbe ){
1861     return pParse->pVdbe;
1862   }
1863   if( pParse->pToplevel==0
1864    && OptimizationEnabled(pParse->db,SQLITE_FactorOutConst)
1865   ){
1866     pParse->okConstFactor = 1;
1867   }
1868   return sqlite3VdbeCreate(pParse);
1869 }
1870
1871
1872 /*
1873 ** Compute the iLimit and iOffset fields of the SELECT based on the
1874 ** pLimit expressions.  pLimit->pLeft and pLimit->pRight hold the expressions
1875 ** that appear in the original SQL statement after the LIMIT and OFFSET
1876 ** keywords.  Or NULL if those keywords are omitted. iLimit and iOffset
1877 ** are the integer memory register numbers for counters used to compute
1878 ** the limit and offset.  If there is no limit and/or offset, then
1879 ** iLimit and iOffset are negative.
1880 **
1881 ** This routine changes the values of iLimit and iOffset only if
1882 ** a limit or offset is defined by pLimit->pLeft and pLimit->pRight.  iLimit
1883 ** and iOffset should have been preset to appropriate default values (zero)
1884 ** prior to calling this routine.
1885 **
1886 ** The iOffset register (if it exists) is initialized to the value
1887 ** of the OFFSET.  The iLimit register is initialized to LIMIT.  Register
1888 ** iOffset+1 is initialized to LIMIT+OFFSET.
1889 **
1890 ** Only if pLimit->pLeft!=0 do the limit registers get
1891 ** redefined.  The UNION ALL operator uses this property to force
1892 ** the reuse of the same limit and offset registers across multiple
1893 ** SELECT statements.
1894 */
1895 static void computeLimitRegisters(Parse *pParse, Select *p, int iBreak){
1896   Vdbe *v = 0;
1897   int iLimit = 0;
1898   int iOffset;
1899   int n;
1900   Expr *pLimit = p->pLimit;
1901
1902   if( p->iLimit ) return;
1903
1904   /*
1905   ** "LIMIT -1" always shows all rows.  There is some
1906   ** controversy about what the correct behavior should be.
1907   ** The current implementation interprets "LIMIT 0" to mean
1908   ** no rows.
1909   */
1910   sqlite3ExprCacheClear(pParse);
1911   if( pLimit ){
1912     assert( pLimit->op==TK_LIMIT );
1913     assert( pLimit->pLeft!=0 );
1914     p->iLimit = iLimit = ++pParse->nMem;
1915     v = sqlite3GetVdbe(pParse);
1916     assert( v!=0 );
1917     if( sqlite3ExprIsInteger(pLimit->pLeft, &n) ){
1918       sqlite3VdbeAddOp2(v, OP_Integer, n, iLimit);
1919       VdbeComment((v, "LIMIT counter"));
1920       if( n==0 ){
1921         sqlite3VdbeGoto(v, iBreak);
1922       }else if( n>=0 && p->nSelectRow>sqlite3LogEst((u64)n) ){
1923         p->nSelectRow = sqlite3LogEst((u64)n);
1924         p->selFlags |= SF_FixedLimit;
1925       }
1926     }else{
1927       sqlite3ExprCode(pParse, pLimit->pLeft, iLimit);
1928       sqlite3VdbeAddOp1(v, OP_MustBeInt, iLimit); VdbeCoverage(v);
1929       VdbeComment((v, "LIMIT counter"));
1930       sqlite3VdbeAddOp2(v, OP_IfNot, iLimit, iBreak); VdbeCoverage(v);
1931     }
1932     if( pLimit->pRight ){
1933       p->iOffset = iOffset = ++pParse->nMem;
1934       pParse->nMem++;   /* Allocate an extra register for limit+offset */
1935       sqlite3ExprCode(pParse, pLimit->pRight, iOffset);
1936       sqlite3VdbeAddOp1(v, OP_MustBeInt, iOffset); VdbeCoverage(v);
1937       VdbeComment((v, "OFFSET counter"));
1938       sqlite3VdbeAddOp3(v, OP_OffsetLimit, iLimit, iOffset+1, iOffset);
1939       VdbeComment((v, "LIMIT+OFFSET"));
1940     }
1941   }
1942 }
1943
1944 #ifndef SQLITE_OMIT_COMPOUND_SELECT
1945 /*
1946 ** Return the appropriate collating sequence for the iCol-th column of
1947 ** the result set for the compound-select statement "p".  Return NULL if
1948 ** the column has no default collating sequence.
1949 **
1950 ** The collating sequence for the compound select is taken from the
1951 ** left-most term of the select that has a collating sequence.
1952 */
1953 static CollSeq *multiSelectCollSeq(Parse *pParse, Select *p, int iCol){
1954   CollSeq *pRet;
1955   if( p->pPrior ){
1956     pRet = multiSelectCollSeq(pParse, p->pPrior, iCol);
1957   }else{
1958     pRet = 0;
1959   }
1960   assert( iCol>=0 );
1961   /* iCol must be less than p->pEList->nExpr.  Otherwise an error would
1962   ** have been thrown during name resolution and we would not have gotten
1963   ** this far */
1964   if( pRet==0 && ALWAYS(iCol<p->pEList->nExpr) ){
1965     pRet = sqlite3ExprCollSeq(pParse, p->pEList->a[iCol].pExpr);
1966   }
1967   return pRet;
1968 }
1969
1970 /*
1971 ** The select statement passed as the second parameter is a compound SELECT
1972 ** with an ORDER BY clause. This function allocates and returns a KeyInfo
1973 ** structure suitable for implementing the ORDER BY.
1974 **
1975 ** Space to hold the KeyInfo structure is obtained from malloc. The calling
1976 ** function is responsible for ensuring that this structure is eventually
1977 ** freed.
1978 */
1979 static KeyInfo *multiSelectOrderByKeyInfo(Parse *pParse, Select *p, int nExtra){
1980   ExprList *pOrderBy = p->pOrderBy;
1981   int nOrderBy = p->pOrderBy->nExpr;
1982   sqlite3 *db = pParse->db;
1983   KeyInfo *pRet = sqlite3KeyInfoAlloc(db, nOrderBy+nExtra, 1);
1984   if( pRet ){
1985     int i;
1986     for(i=0; i<nOrderBy; i++){
1987       struct ExprList_item *pItem = &pOrderBy->a[i];
1988       Expr *pTerm = pItem->pExpr;
1989       CollSeq *pColl;
1990
1991       if( pTerm->flags & EP_Collate ){
1992         pColl = sqlite3ExprCollSeq(pParse, pTerm);
1993       }else{
1994         pColl = multiSelectCollSeq(pParse, p, pItem->u.x.iOrderByCol-1);
1995         if( pColl==0 ) pColl = db->pDfltColl;
1996         pOrderBy->a[i].pExpr =
1997           sqlite3ExprAddCollateString(pParse, pTerm, pColl->zName);
1998       }
1999       assert( sqlite3KeyInfoIsWriteable(pRet) );
2000       pRet->aColl[i] = pColl;
2001       pRet->aSortOrder[i] = pOrderBy->a[i].sortOrder;
2002     }
2003   }
2004
2005   return pRet;
2006 }
2007
2008 #ifndef SQLITE_OMIT_CTE
2009 /*
2010 ** This routine generates VDBE code to compute the content of a WITH RECURSIVE
2011 ** query of the form:
2012 **
2013 **   <recursive-table> AS (<setup-query> UNION [ALL] <recursive-query>)
2014 **                         \___________/             \_______________/
2015 **                           p->pPrior                      p
2016 **
2017 **
2018 ** There is exactly one reference to the recursive-table in the FROM clause
2019 ** of recursive-query, marked with the SrcList->a[].fg.isRecursive flag.
2020 **
2021 ** The setup-query runs once to generate an initial set of rows that go
2022 ** into a Queue table.  Rows are extracted from the Queue table one by
2023 ** one.  Each row extracted from Queue is output to pDest.  Then the single
2024 ** extracted row (now in the iCurrent table) becomes the content of the
2025 ** recursive-table for a recursive-query run.  The output of the recursive-query
2026 ** is added back into the Queue table.  Then another row is extracted from Queue
2027 ** and the iteration continues until the Queue table is empty.
2028 **
2029 ** If the compound query operator is UNION then no duplicate rows are ever
2030 ** inserted into the Queue table.  The iDistinct table keeps a copy of all rows
2031 ** that have ever been inserted into Queue and causes duplicates to be
2032 ** discarded.  If the operator is UNION ALL, then duplicates are allowed.
2033 **
2034 ** If the query has an ORDER BY, then entries in the Queue table are kept in
2035 ** ORDER BY order and the first entry is extracted for each cycle.  Without
2036 ** an ORDER BY, the Queue table is just a FIFO.
2037 **
2038 ** If a LIMIT clause is provided, then the iteration stops after LIMIT rows
2039 ** have been output to pDest.  A LIMIT of zero means to output no rows and a
2040 ** negative LIMIT means to output all rows.  If there is also an OFFSET clause
2041 ** with a positive value, then the first OFFSET outputs are discarded rather
2042 ** than being sent to pDest.  The LIMIT count does not begin until after OFFSET
2043 ** rows have been skipped.
2044 */
2045 static void generateWithRecursiveQuery(
2046   Parse *pParse,        /* Parsing context */
2047   Select *p,            /* The recursive SELECT to be coded */
2048   SelectDest *pDest     /* What to do with query results */
2049 ){
2050   SrcList *pSrc = p->pSrc;      /* The FROM clause of the recursive query */
2051   int nCol = p->pEList->nExpr;  /* Number of columns in the recursive table */
2052   Vdbe *v = pParse->pVdbe;      /* The prepared statement under construction */
2053   Select *pSetup = p->pPrior;   /* The setup query */
2054   int addrTop;                  /* Top of the loop */
2055   int addrCont, addrBreak;      /* CONTINUE and BREAK addresses */
2056   int iCurrent = 0;             /* The Current table */
2057   int regCurrent;               /* Register holding Current table */
2058   int iQueue;                   /* The Queue table */
2059   int iDistinct = 0;            /* To ensure unique results if UNION */
2060   int eDest = SRT_Fifo;         /* How to write to Queue */
2061   SelectDest destQueue;         /* SelectDest targetting the Queue table */
2062   int i;                        /* Loop counter */
2063   int rc;                       /* Result code */
2064   ExprList *pOrderBy;           /* The ORDER BY clause */
2065   Expr *pLimit;                 /* Saved LIMIT and OFFSET */
2066   int regLimit, regOffset;      /* Registers used by LIMIT and OFFSET */
2067
2068   /* Obtain authorization to do a recursive query */
2069   if( sqlite3AuthCheck(pParse, SQLITE_RECURSIVE, 0, 0, 0) ) return;
2070
2071   /* Process the LIMIT and OFFSET clauses, if they exist */
2072   addrBreak = sqlite3VdbeMakeLabel(v);
2073   p->nSelectRow = 320;  /* 4 billion rows */
2074   computeLimitRegisters(pParse, p, addrBreak);
2075   pLimit = p->pLimit;
2076   regLimit = p->iLimit;
2077   regOffset = p->iOffset;
2078   p->pLimit = 0;
2079   p->iLimit = p->iOffset = 0;
2080   pOrderBy = p->pOrderBy;
2081
2082   /* Locate the cursor number of the Current table */
2083   for(i=0; ALWAYS(i<pSrc->nSrc); i++){
2084     if( pSrc->a[i].fg.isRecursive ){
2085       iCurrent = pSrc->a[i].iCursor;
2086       break;
2087     }
2088   }
2089
2090   /* Allocate cursors numbers for Queue and Distinct.  The cursor number for
2091   ** the Distinct table must be exactly one greater than Queue in order
2092   ** for the SRT_DistFifo and SRT_DistQueue destinations to work. */
2093   iQueue = pParse->nTab++;
2094   if( p->op==TK_UNION ){
2095     eDest = pOrderBy ? SRT_DistQueue : SRT_DistFifo;
2096     iDistinct = pParse->nTab++;
2097   }else{
2098     eDest = pOrderBy ? SRT_Queue : SRT_Fifo;
2099   }
2100   sqlite3SelectDestInit(&destQueue, eDest, iQueue);
2101
2102   /* Allocate cursors for Current, Queue, and Distinct. */
2103   regCurrent = ++pParse->nMem;
2104   sqlite3VdbeAddOp3(v, OP_OpenPseudo, iCurrent, regCurrent, nCol);
2105   if( pOrderBy ){
2106     KeyInfo *pKeyInfo = multiSelectOrderByKeyInfo(pParse, p, 1);
2107     sqlite3VdbeAddOp4(v, OP_OpenEphemeral, iQueue, pOrderBy->nExpr+2, 0,
2108                       (char*)pKeyInfo, P4_KEYINFO);
2109     destQueue.pOrderBy = pOrderBy;
2110   }else{
2111     sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iQueue, nCol);
2112   }
2113   VdbeComment((v, "Queue table"));
2114   if( iDistinct ){
2115     p->addrOpenEphm[0] = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iDistinct, 0);
2116     p->selFlags |= SF_UsesEphemeral;
2117   }
2118
2119   /* Detach the ORDER BY clause from the compound SELECT */
2120   p->pOrderBy = 0;
2121
2122   /* Store the results of the setup-query in Queue. */
2123   pSetup->pNext = 0;
2124   rc = sqlite3Select(pParse, pSetup, &destQueue);
2125   pSetup->pNext = p;
2126   if( rc ) goto end_of_recursive_query;
2127
2128   /* Find the next row in the Queue and output that row */
2129   addrTop = sqlite3VdbeAddOp2(v, OP_Rewind, iQueue, addrBreak); VdbeCoverage(v);
2130
2131   /* Transfer the next row in Queue over to Current */
2132   sqlite3VdbeAddOp1(v, OP_NullRow, iCurrent); /* To reset column cache */
2133   if( pOrderBy ){
2134     sqlite3VdbeAddOp3(v, OP_Column, iQueue, pOrderBy->nExpr+1, regCurrent);
2135   }else{
2136     sqlite3VdbeAddOp2(v, OP_RowData, iQueue, regCurrent);
2137   }
2138   sqlite3VdbeAddOp1(v, OP_Delete, iQueue);
2139
2140   /* Output the single row in Current */
2141   addrCont = sqlite3VdbeMakeLabel(v);
2142   codeOffset(v, regOffset, addrCont);
2143   selectInnerLoop(pParse, p, iCurrent,
2144       0, 0, pDest, addrCont, addrBreak);
2145   if( regLimit ){
2146     sqlite3VdbeAddOp2(v, OP_DecrJumpZero, regLimit, addrBreak);
2147     VdbeCoverage(v);
2148   }
2149   sqlite3VdbeResolveLabel(v, addrCont);
2150
2151   /* Execute the recursive SELECT taking the single row in Current as
2152   ** the value for the recursive-table. Store the results in the Queue.
2153   */
2154   if( p->selFlags & SF_Aggregate ){
2155     sqlite3ErrorMsg(pParse, "recursive aggregate queries not supported");
2156   }else{
2157     p->pPrior = 0;
2158     sqlite3Select(pParse, p, &destQueue);
2159     assert( p->pPrior==0 );
2160     p->pPrior = pSetup;
2161   }
2162
2163   /* Keep running the loop until the Queue is empty */
2164   sqlite3VdbeGoto(v, addrTop);
2165   sqlite3VdbeResolveLabel(v, addrBreak);
2166
2167 end_of_recursive_query:
2168   sqlite3ExprListDelete(pParse->db, p->pOrderBy);
2169   p->pOrderBy = pOrderBy;
2170   p->pLimit = pLimit;
2171   return;
2172 }
2173 #endif /* SQLITE_OMIT_CTE */
2174
2175 /* Forward references */
2176 static int multiSelectOrderBy(
2177   Parse *pParse,        /* Parsing context */
2178   Select *p,            /* The right-most of SELECTs to be coded */
2179   SelectDest *pDest     /* What to do with query results */
2180 );
2181
2182 /*
2183 ** Handle the special case of a compound-select that originates from a
2184 ** VALUES clause.  By handling this as a special case, we avoid deep
2185 ** recursion, and thus do not need to enforce the SQLITE_LIMIT_COMPOUND_SELECT
2186 ** on a VALUES clause.
2187 **
2188 ** Because the Select object originates from a VALUES clause:
2189 **   (1) There is no LIMIT or OFFSET or else there is a LIMIT of exactly 1
2190 **   (2) All terms are UNION ALL
2191 **   (3) There is no ORDER BY clause
2192 **
2193 ** The "LIMIT of exactly 1" case of condition (1) comes about when a VALUES
2194 ** clause occurs within scalar expression (ex: "SELECT (VALUES(1),(2),(3))").
2195 ** The sqlite3CodeSubselect will have added the LIMIT 1 clause in tht case.
2196 ** Since the limit is exactly 1, we only need to evalutes the left-most VALUES.
2197 */
2198 static int multiSelectValues(
2199   Parse *pParse,        /* Parsing context */
2200   Select *p,            /* The right-most of SELECTs to be coded */
2201   SelectDest *pDest     /* What to do with query results */
2202 ){
2203   Select *pPrior;
2204   Select *pRightmost = p;
2205   int nRow = 1;
2206   int rc = 0;
2207   assert( p->selFlags & SF_MultiValue );
2208   do{
2209     assert( p->selFlags & SF_Values );
2210     assert( p->op==TK_ALL || (p->op==TK_SELECT && p->pPrior==0) );
2211     assert( p->pNext==0 || p->pEList->nExpr==p->pNext->pEList->nExpr );
2212     if( p->pPrior==0 ) break;
2213     assert( p->pPrior->pNext==p );
2214     p = p->pPrior;
2215     nRow++;
2216   }while(1);
2217   while( p ){
2218     pPrior = p->pPrior;
2219     p->pPrior = 0;
2220     rc = sqlite3Select(pParse, p, pDest);
2221     p->pPrior = pPrior;
2222     if( rc || pRightmost->pLimit ) break;
2223     p->nSelectRow = nRow;
2224     p = p->pNext;
2225   }
2226   return rc;
2227 }
2228
2229 /*
2230 ** This routine is called to process a compound query form from
2231 ** two or more separate queries using UNION, UNION ALL, EXCEPT, or
2232 ** INTERSECT
2233 **
2234 ** "p" points to the right-most of the two queries.  the query on the
2235 ** left is p->pPrior.  The left query could also be a compound query
2236 ** in which case this routine will be called recursively.
2237 **
2238 ** The results of the total query are to be written into a destination
2239 ** of type eDest with parameter iParm.
2240 **
2241 ** Example 1:  Consider a three-way compound SQL statement.
2242 **
2243 **     SELECT a FROM t1 UNION SELECT b FROM t2 UNION SELECT c FROM t3
2244 **
2245 ** This statement is parsed up as follows:
2246 **
2247 **     SELECT c FROM t3
2248 **      |
2249 **      `----->  SELECT b FROM t2
2250 **                |
2251 **                `------>  SELECT a FROM t1
2252 **
2253 ** The arrows in the diagram above represent the Select.pPrior pointer.
2254 ** So if this routine is called with p equal to the t3 query, then
2255 ** pPrior will be the t2 query.  p->op will be TK_UNION in this case.
2256 **
2257 ** Notice that because of the way SQLite parses compound SELECTs, the
2258 ** individual selects always group from left to right.
2259 */
2260 static int multiSelect(
2261   Parse *pParse,        /* Parsing context */
2262   Select *p,            /* The right-most of SELECTs to be coded */
2263   SelectDest *pDest     /* What to do with query results */
2264 ){
2265   int rc = SQLITE_OK;   /* Success code from a subroutine */
2266   Select *pPrior;       /* Another SELECT immediately to our left */
2267   Vdbe *v;              /* Generate code to this VDBE */
2268   SelectDest dest;      /* Alternative data destination */
2269   Select *pDelete = 0;  /* Chain of simple selects to delete */
2270   sqlite3 *db;          /* Database connection */
2271 #ifndef SQLITE_OMIT_EXPLAIN
2272   int iSub1 = 0;        /* EQP id of left-hand query */
2273   int iSub2 = 0;        /* EQP id of right-hand query */
2274 #endif
2275
2276   /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs.  Only
2277   ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT.
2278   */
2279   assert( p && p->pPrior );  /* Calling function guarantees this much */
2280   assert( (p->selFlags & SF_Recursive)==0 || p->op==TK_ALL || p->op==TK_UNION );
2281   db = pParse->db;
2282   pPrior = p->pPrior;
2283   dest = *pDest;
2284   if( pPrior->pOrderBy || pPrior->pLimit ){
2285     sqlite3ErrorMsg(pParse,"%s clause should come after %s not before",
2286       pPrior->pOrderBy!=0 ? "ORDER BY" : "LIMIT", selectOpName(p->op));
2287     rc = 1;
2288     goto multi_select_end;
2289   }
2290
2291   v = sqlite3GetVdbe(pParse);
2292   assert( v!=0 );  /* The VDBE already created by calling function */
2293
2294   /* Create the destination temporary table if necessary
2295   */
2296   if( dest.eDest==SRT_EphemTab ){
2297     assert( p->pEList );
2298     sqlite3VdbeAddOp2(v, OP_OpenEphemeral, dest.iSDParm, p->pEList->nExpr);
2299     dest.eDest = SRT_Table;
2300   }
2301
2302   /* Special handling for a compound-select that originates as a VALUES clause.
2303   */
2304   if( p->selFlags & SF_MultiValue ){
2305     rc = multiSelectValues(pParse, p, &dest);
2306     goto multi_select_end;
2307   }
2308
2309   /* Make sure all SELECTs in the statement have the same number of elements
2310   ** in their result sets.
2311   */
2312   assert( p->pEList && pPrior->pEList );
2313   assert( p->pEList->nExpr==pPrior->pEList->nExpr );
2314
2315 #ifndef SQLITE_OMIT_CTE
2316   if( p->selFlags & SF_Recursive ){
2317     generateWithRecursiveQuery(pParse, p, &dest);
2318   }else
2319 #endif
2320
2321   /* Compound SELECTs that have an ORDER BY clause are handled separately.
2322   */
2323   if( p->pOrderBy ){
2324     return multiSelectOrderBy(pParse, p, pDest);
2325   }else
2326
2327   /* Generate code for the left and right SELECT statements.
2328   */
2329   switch( p->op ){
2330     case TK_ALL: {
2331       int addr = 0;
2332       int nLimit;
2333       assert( !pPrior->pLimit );
2334       pPrior->iLimit = p->iLimit;
2335       pPrior->iOffset = p->iOffset;
2336       pPrior->pLimit = p->pLimit;
2337       explainSetInteger(iSub1, pParse->iNextSelectId);
2338       rc = sqlite3Select(pParse, pPrior, &dest);
2339       p->pLimit = 0;
2340       if( rc ){
2341         goto multi_select_end;
2342       }
2343       p->pPrior = 0;
2344       p->iLimit = pPrior->iLimit;
2345       p->iOffset = pPrior->iOffset;
2346       if( p->iLimit ){
2347         addr = sqlite3VdbeAddOp1(v, OP_IfNot, p->iLimit); VdbeCoverage(v);
2348         VdbeComment((v, "Jump ahead if LIMIT reached"));
2349         if( p->iOffset ){
2350           sqlite3VdbeAddOp3(v, OP_OffsetLimit,
2351                             p->iLimit, p->iOffset+1, p->iOffset);
2352         }
2353       }
2354       explainSetInteger(iSub2, pParse->iNextSelectId);
2355       rc = sqlite3Select(pParse, p, &dest);
2356       testcase( rc!=SQLITE_OK );
2357       pDelete = p->pPrior;
2358       p->pPrior = pPrior;
2359       p->nSelectRow = sqlite3LogEstAdd(p->nSelectRow, pPrior->nSelectRow);
2360       if( pPrior->pLimit
2361        && sqlite3ExprIsInteger(pPrior->pLimit->pLeft, &nLimit)
2362        && nLimit>0 && p->nSelectRow > sqlite3LogEst((u64)nLimit)
2363       ){
2364         p->nSelectRow = sqlite3LogEst((u64)nLimit);
2365       }
2366       if( addr ){
2367         sqlite3VdbeJumpHere(v, addr);
2368       }
2369       break;
2370     }
2371     case TK_EXCEPT:
2372     case TK_UNION: {
2373       int unionTab;    /* Cursor number of the temporary table holding result */
2374       u8 op = 0;       /* One of the SRT_ operations to apply to self */
2375       int priorOp;     /* The SRT_ operation to apply to prior selects */
2376       Expr *pLimit;    /* Saved values of p->nLimit  */
2377       int addr;
2378       SelectDest uniondest;
2379
2380       testcase( p->op==TK_EXCEPT );
2381       testcase( p->op==TK_UNION );
2382       priorOp = SRT_Union;
2383       if( dest.eDest==priorOp ){
2384         /* We can reuse a temporary table generated by a SELECT to our
2385         ** right.
2386         */
2387         assert( p->pLimit==0 );      /* Not allowed on leftward elements */
2388         unionTab = dest.iSDParm;
2389       }else{
2390         /* We will need to create our own temporary table to hold the
2391         ** intermediate results.
2392         */
2393         unionTab = pParse->nTab++;
2394         assert( p->pOrderBy==0 );
2395         addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, unionTab, 0);
2396         assert( p->addrOpenEphm[0] == -1 );
2397         p->addrOpenEphm[0] = addr;
2398         findRightmost(p)->selFlags |= SF_UsesEphemeral;
2399         assert( p->pEList );
2400       }
2401
2402       /* Code the SELECT statements to our left
2403       */
2404       assert( !pPrior->pOrderBy );
2405       sqlite3SelectDestInit(&uniondest, priorOp, unionTab);
2406       explainSetInteger(iSub1, pParse->iNextSelectId);
2407       rc = sqlite3Select(pParse, pPrior, &uniondest);
2408       if( rc ){
2409         goto multi_select_end;
2410       }
2411
2412       /* Code the current SELECT statement
2413       */
2414       if( p->op==TK_EXCEPT ){
2415         op = SRT_Except;
2416       }else{
2417         assert( p->op==TK_UNION );
2418         op = SRT_Union;
2419       }
2420       p->pPrior = 0;
2421       pLimit = p->pLimit;
2422       p->pLimit = 0;
2423       uniondest.eDest = op;
2424       explainSetInteger(iSub2, pParse->iNextSelectId);
2425       rc = sqlite3Select(pParse, p, &uniondest);
2426       testcase( rc!=SQLITE_OK );
2427       /* Query flattening in sqlite3Select() might refill p->pOrderBy.
2428       ** Be sure to delete p->pOrderBy, therefore, to avoid a memory leak. */
2429       sqlite3ExprListDelete(db, p->pOrderBy);
2430       pDelete = p->pPrior;
2431       p->pPrior = pPrior;
2432       p->pOrderBy = 0;
2433       if( p->op==TK_UNION ){
2434         p->nSelectRow = sqlite3LogEstAdd(p->nSelectRow, pPrior->nSelectRow);
2435       }
2436       sqlite3ExprDelete(db, p->pLimit);
2437       p->pLimit = pLimit;
2438       p->iLimit = 0;
2439       p->iOffset = 0;
2440
2441       /* Convert the data in the temporary table into whatever form
2442       ** it is that we currently need.
2443       */
2444       assert( unionTab==dest.iSDParm || dest.eDest!=priorOp );
2445       if( dest.eDest!=priorOp ){
2446         int iCont, iBreak, iStart;
2447         assert( p->pEList );
2448         iBreak = sqlite3VdbeMakeLabel(v);
2449         iCont = sqlite3VdbeMakeLabel(v);
2450         computeLimitRegisters(pParse, p, iBreak);
2451         sqlite3VdbeAddOp2(v, OP_Rewind, unionTab, iBreak); VdbeCoverage(v);
2452         iStart = sqlite3VdbeCurrentAddr(v);
2453         selectInnerLoop(pParse, p, unionTab,
2454                         0, 0, &dest, iCont, iBreak);
2455         sqlite3VdbeResolveLabel(v, iCont);
2456         sqlite3VdbeAddOp2(v, OP_Next, unionTab, iStart); VdbeCoverage(v);
2457         sqlite3VdbeResolveLabel(v, iBreak);
2458         sqlite3VdbeAddOp2(v, OP_Close, unionTab, 0);
2459       }
2460       break;
2461     }
2462     default: assert( p->op==TK_INTERSECT ); {
2463       int tab1, tab2;
2464       int iCont, iBreak, iStart;
2465       Expr *pLimit;
2466       int addr;
2467       SelectDest intersectdest;
2468       int r1;
2469
2470       /* INTERSECT is different from the others since it requires
2471       ** two temporary tables.  Hence it has its own case.  Begin
2472       ** by allocating the tables we will need.
2473       */
2474       tab1 = pParse->nTab++;
2475       tab2 = pParse->nTab++;
2476       assert( p->pOrderBy==0 );
2477
2478       addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tab1, 0);
2479       assert( p->addrOpenEphm[0] == -1 );
2480       p->addrOpenEphm[0] = addr;
2481       findRightmost(p)->selFlags |= SF_UsesEphemeral;
2482       assert( p->pEList );
2483
2484       /* Code the SELECTs to our left into temporary table "tab1".
2485       */
2486       sqlite3SelectDestInit(&intersectdest, SRT_Union, tab1);
2487       explainSetInteger(iSub1, pParse->iNextSelectId);
2488       rc = sqlite3Select(pParse, pPrior, &intersectdest);
2489       if( rc ){
2490         goto multi_select_end;
2491       }
2492
2493       /* Code the current SELECT into temporary table "tab2"
2494       */
2495       addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tab2, 0);
2496       assert( p->addrOpenEphm[1] == -1 );
2497       p->addrOpenEphm[1] = addr;
2498       p->pPrior = 0;
2499       pLimit = p->pLimit;
2500       p->pLimit = 0;
2501       intersectdest.iSDParm = tab2;
2502       explainSetInteger(iSub2, pParse->iNextSelectId);
2503       rc = sqlite3Select(pParse, p, &intersectdest);
2504       testcase( rc!=SQLITE_OK );
2505       pDelete = p->pPrior;
2506       p->pPrior = pPrior;
2507       if( p->nSelectRow>pPrior->nSelectRow ) p->nSelectRow = pPrior->nSelectRow;
2508       sqlite3ExprDelete(db, p->pLimit);
2509       p->pLimit = pLimit;
2510
2511       /* Generate code to take the intersection of the two temporary
2512       ** tables.
2513       */
2514       assert( p->pEList );
2515       iBreak = sqlite3VdbeMakeLabel(v);
2516       iCont = sqlite3VdbeMakeLabel(v);
2517       computeLimitRegisters(pParse, p, iBreak);
2518       sqlite3VdbeAddOp2(v, OP_Rewind, tab1, iBreak); VdbeCoverage(v);
2519       r1 = sqlite3GetTempReg(pParse);
2520       iStart = sqlite3VdbeAddOp2(v, OP_RowData, tab1, r1);
2521       sqlite3VdbeAddOp4Int(v, OP_NotFound, tab2, iCont, r1, 0); VdbeCoverage(v);
2522       sqlite3ReleaseTempReg(pParse, r1);
2523       selectInnerLoop(pParse, p, tab1,
2524                       0, 0, &dest, iCont, iBreak);
2525       sqlite3VdbeResolveLabel(v, iCont);
2526       sqlite3VdbeAddOp2(v, OP_Next, tab1, iStart); VdbeCoverage(v);
2527       sqlite3VdbeResolveLabel(v, iBreak);
2528       sqlite3VdbeAddOp2(v, OP_Close, tab2, 0);
2529       sqlite3VdbeAddOp2(v, OP_Close, tab1, 0);
2530       break;
2531     }
2532   }
2533
2534   explainComposite(pParse, p->op, iSub1, iSub2, p->op!=TK_ALL);
2535
2536   /* Compute collating sequences used by
2537   ** temporary tables needed to implement the compound select.
2538   ** Attach the KeyInfo structure to all temporary tables.
2539   **
2540   ** This section is run by the right-most SELECT statement only.
2541   ** SELECT statements to the left always skip this part.  The right-most
2542   ** SELECT might also skip this part if it has no ORDER BY clause and
2543   ** no temp tables are required.
2544   */
2545   if( p->selFlags & SF_UsesEphemeral ){
2546     int i;                        /* Loop counter */
2547     KeyInfo *pKeyInfo;            /* Collating sequence for the result set */
2548     Select *pLoop;                /* For looping through SELECT statements */
2549     CollSeq **apColl;             /* For looping through pKeyInfo->aColl[] */
2550     int nCol;                     /* Number of columns in result set */
2551
2552     assert( p->pNext==0 );
2553     nCol = p->pEList->nExpr;
2554     pKeyInfo = sqlite3KeyInfoAlloc(db, nCol, 1);
2555     if( !pKeyInfo ){
2556       rc = SQLITE_NOMEM_BKPT;
2557       goto multi_select_end;
2558     }
2559     for(i=0, apColl=pKeyInfo->aColl; i<nCol; i++, apColl++){
2560       *apColl = multiSelectCollSeq(pParse, p, i);
2561       if( 0==*apColl ){
2562         *apColl = db->pDfltColl;
2563       }
2564     }
2565
2566     for(pLoop=p; pLoop; pLoop=pLoop->pPrior){
2567       for(i=0; i<2; i++){
2568         int addr = pLoop->addrOpenEphm[i];
2569         if( addr<0 ){
2570           /* If [0] is unused then [1] is also unused.  So we can
2571           ** always safely abort as soon as the first unused slot is found */
2572           assert( pLoop->addrOpenEphm[1]<0 );
2573           break;
2574         }
2575         sqlite3VdbeChangeP2(v, addr, nCol);
2576         sqlite3VdbeChangeP4(v, addr, (char*)sqlite3KeyInfoRef(pKeyInfo),
2577                             P4_KEYINFO);
2578         pLoop->addrOpenEphm[i] = -1;
2579       }
2580     }
2581     sqlite3KeyInfoUnref(pKeyInfo);
2582   }
2583
2584 multi_select_end:
2585   pDest->iSdst = dest.iSdst;
2586   pDest->nSdst = dest.nSdst;
2587   sqlite3SelectDelete(db, pDelete);
2588   return rc;
2589 }
2590 #endif /* SQLITE_OMIT_COMPOUND_SELECT */
2591
2592 /*
2593 ** Error message for when two or more terms of a compound select have different
2594 ** size result sets.
2595 */
2596 void sqlite3SelectWrongNumTermsError(Parse *pParse, Select *p){
2597   if( p->selFlags & SF_Values ){
2598     sqlite3ErrorMsg(pParse, "all VALUES must have the same number of terms");
2599   }else{
2600     sqlite3ErrorMsg(pParse, "SELECTs to the left and right of %s"
2601       " do not have the same number of result columns", selectOpName(p->op));
2602   }
2603 }
2604
2605 /*
2606 ** Code an output subroutine for a coroutine implementation of a
2607 ** SELECT statment.
2608 **
2609 ** The data to be output is contained in pIn->iSdst.  There are
2610 ** pIn->nSdst columns to be output.  pDest is where the output should
2611 ** be sent.
2612 **
2613 ** regReturn is the number of the register holding the subroutine
2614 ** return address.
2615 **
2616 ** If regPrev>0 then it is the first register in a vector that
2617 ** records the previous output.  mem[regPrev] is a flag that is false
2618 ** if there has been no previous output.  If regPrev>0 then code is
2619 ** generated to suppress duplicates.  pKeyInfo is used for comparing
2620 ** keys.
2621 **
2622 ** If the LIMIT found in p->iLimit is reached, jump immediately to
2623 ** iBreak.
2624 */
2625 static int generateOutputSubroutine(
2626   Parse *pParse,          /* Parsing context */
2627   Select *p,              /* The SELECT statement */
2628   SelectDest *pIn,        /* Coroutine supplying data */
2629   SelectDest *pDest,      /* Where to send the data */
2630   int regReturn,          /* The return address register */
2631   int regPrev,            /* Previous result register.  No uniqueness if 0 */
2632   KeyInfo *pKeyInfo,      /* For comparing with previous entry */
2633   int iBreak              /* Jump here if we hit the LIMIT */
2634 ){
2635   Vdbe *v = pParse->pVdbe;
2636   int iContinue;
2637   int addr;
2638
2639   addr = sqlite3VdbeCurrentAddr(v);
2640   iContinue = sqlite3VdbeMakeLabel(v);
2641
2642   /* Suppress duplicates for UNION, EXCEPT, and INTERSECT
2643   */
2644   if( regPrev ){
2645     int addr1, addr2;
2646     addr1 = sqlite3VdbeAddOp1(v, OP_IfNot, regPrev); VdbeCoverage(v);
2647     addr2 = sqlite3VdbeAddOp4(v, OP_Compare, pIn->iSdst, regPrev+1, pIn->nSdst,
2648                               (char*)sqlite3KeyInfoRef(pKeyInfo), P4_KEYINFO);
2649     sqlite3VdbeAddOp3(v, OP_Jump, addr2+2, iContinue, addr2+2); VdbeCoverage(v);
2650     sqlite3VdbeJumpHere(v, addr1);
2651     sqlite3VdbeAddOp3(v, OP_Copy, pIn->iSdst, regPrev+1, pIn->nSdst-1);
2652     sqlite3VdbeAddOp2(v, OP_Integer, 1, regPrev);
2653   }
2654   if( pParse->db->mallocFailed ) return 0;
2655
2656   /* Suppress the first OFFSET entries if there is an OFFSET clause
2657   */
2658   codeOffset(v, p->iOffset, iContinue);
2659
2660   assert( pDest->eDest!=SRT_Exists );
2661   assert( pDest->eDest!=SRT_Table );
2662   switch( pDest->eDest ){
2663     /* Store the result as data using a unique key.
2664     */
2665     case SRT_EphemTab: {
2666       int r1 = sqlite3GetTempReg(pParse);
2667       int r2 = sqlite3GetTempReg(pParse);
2668       sqlite3VdbeAddOp3(v, OP_MakeRecord, pIn->iSdst, pIn->nSdst, r1);
2669       sqlite3VdbeAddOp2(v, OP_NewRowid, pDest->iSDParm, r2);
2670       sqlite3VdbeAddOp3(v, OP_Insert, pDest->iSDParm, r1, r2);
2671       sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
2672       sqlite3ReleaseTempReg(pParse, r2);
2673       sqlite3ReleaseTempReg(pParse, r1);
2674       break;
2675     }
2676
2677 #ifndef SQLITE_OMIT_SUBQUERY
2678     /* If we are creating a set for an "expr IN (SELECT ...)".
2679     */
2680     case SRT_Set: {
2681       int r1;
2682       testcase( pIn->nSdst>1 );
2683       r1 = sqlite3GetTempReg(pParse);
2684       sqlite3VdbeAddOp4(v, OP_MakeRecord, pIn->iSdst, pIn->nSdst,
2685           r1, pDest->zAffSdst, pIn->nSdst);
2686       sqlite3ExprCacheAffinityChange(pParse, pIn->iSdst, pIn->nSdst);
2687       sqlite3VdbeAddOp4Int(v, OP_IdxInsert, pDest->iSDParm, r1,
2688                            pIn->iSdst, pIn->nSdst);
2689       sqlite3ReleaseTempReg(pParse, r1);
2690       break;
2691     }
2692
2693     /* If this is a scalar select that is part of an expression, then
2694     ** store the results in the appropriate memory cell and break out
2695     ** of the scan loop.
2696     */
2697     case SRT_Mem: {
2698       assert( pIn->nSdst==1 || pParse->nErr>0 );  testcase( pIn->nSdst!=1 );
2699       sqlite3ExprCodeMove(pParse, pIn->iSdst, pDest->iSDParm, 1);
2700       /* The LIMIT clause will jump out of the loop for us */
2701       break;
2702     }
2703 #endif /* #ifndef SQLITE_OMIT_SUBQUERY */
2704
2705     /* The results are stored in a sequence of registers
2706     ** starting at pDest->iSdst.  Then the co-routine yields.
2707     */
2708     case SRT_Coroutine: {
2709       if( pDest->iSdst==0 ){
2710         pDest->iSdst = sqlite3GetTempRange(pParse, pIn->nSdst);
2711         pDest->nSdst = pIn->nSdst;
2712       }
2713       sqlite3ExprCodeMove(pParse, pIn->iSdst, pDest->iSdst, pIn->nSdst);
2714       sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm);
2715       break;
2716     }
2717
2718     /* If none of the above, then the result destination must be
2719     ** SRT_Output.  This routine is never called with any other
2720     ** destination other than the ones handled above or SRT_Output.
2721     **
2722     ** For SRT_Output, results are stored in a sequence of registers.
2723     ** Then the OP_ResultRow opcode is used to cause sqlite3_step() to
2724     ** return the next row of result.
2725     */
2726     default: {
2727       assert( pDest->eDest==SRT_Output );
2728       sqlite3VdbeAddOp2(v, OP_ResultRow, pIn->iSdst, pIn->nSdst);
2729       sqlite3ExprCacheAffinityChange(pParse, pIn->iSdst, pIn->nSdst);
2730       break;
2731     }
2732   }
2733
2734   /* Jump to the end of the loop if the LIMIT is reached.
2735   */
2736   if( p->iLimit ){
2737     sqlite3VdbeAddOp2(v, OP_DecrJumpZero, p->iLimit, iBreak); VdbeCoverage(v);
2738   }
2739
2740   /* Generate the subroutine return
2741   */
2742   sqlite3VdbeResolveLabel(v, iContinue);
2743   sqlite3VdbeAddOp1(v, OP_Return, regReturn);
2744
2745   return addr;
2746 }
2747
2748 /*
2749 ** Alternative compound select code generator for cases when there
2750 ** is an ORDER BY clause.
2751 **
2752 ** We assume a query of the following form:
2753 **
2754 **      <selectA>  <operator>  <selectB>  ORDER BY <orderbylist>
2755 **
2756 ** <operator> is one of UNION ALL, UNION, EXCEPT, or INTERSECT.  The idea
2757 ** is to code both <selectA> and <selectB> with the ORDER BY clause as
2758 ** co-routines.  Then run the co-routines in parallel and merge the results
2759 ** into the output.  In addition to the two coroutines (called selectA and
2760 ** selectB) there are 7 subroutines:
2761 **
2762 **    outA:    Move the output of the selectA coroutine into the output
2763 **             of the compound query.
2764 **
2765 **    outB:    Move the output of the selectB coroutine into the output
2766 **             of the compound query.  (Only generated for UNION and
2767 **             UNION ALL.  EXCEPT and INSERTSECT never output a row that
2768 **             appears only in B.)
2769 **
2770 **    AltB:    Called when there is data from both coroutines and A<B.
2771 **
2772 **    AeqB:    Called when there is data from both coroutines and A==B.
2773 **
2774 **    AgtB:    Called when there is data from both coroutines and A>B.
2775 **
2776 **    EofA:    Called when data is exhausted from selectA.
2777 **
2778 **    EofB:    Called when data is exhausted from selectB.
2779 **
2780 ** The implementation of the latter five subroutines depend on which
2781 ** <operator> is used:
2782 **
2783 **
2784 **             UNION ALL         UNION            EXCEPT          INTERSECT
2785 **          -------------  -----------------  --------------  -----------------
2786 **   AltB:   outA, nextA      outA, nextA       outA, nextA         nextA
2787 **
2788 **   AeqB:   outA, nextA         nextA             nextA         outA, nextA
2789 **
2790 **   AgtB:   outB, nextB      outB, nextB          nextB            nextB
2791 **
2792 **   EofA:   outB, nextB      outB, nextB          halt             halt
2793 **
2794 **   EofB:   outA, nextA      outA, nextA       outA, nextA         halt
2795 **
2796 ** In the AltB, AeqB, and AgtB subroutines, an EOF on A following nextA
2797 ** causes an immediate jump to EofA and an EOF on B following nextB causes
2798 ** an immediate jump to EofB.  Within EofA and EofB, and EOF on entry or
2799 ** following nextX causes a jump to the end of the select processing.
2800 **
2801 ** Duplicate removal in the UNION, EXCEPT, and INTERSECT cases is handled
2802 ** within the output subroutine.  The regPrev register set holds the previously
2803 ** output value.  A comparison is made against this value and the output
2804 ** is skipped if the next results would be the same as the previous.
2805 **
2806 ** The implementation plan is to implement the two coroutines and seven
2807 ** subroutines first, then put the control logic at the bottom.  Like this:
2808 **
2809 **          goto Init
2810 **     coA: coroutine for left query (A)
2811 **     coB: coroutine for right query (B)
2812 **    outA: output one row of A
2813 **    outB: output one row of B (UNION and UNION ALL only)
2814 **    EofA: ...
2815 **    EofB: ...
2816 **    AltB: ...
2817 **    AeqB: ...
2818 **    AgtB: ...
2819 **    Init: initialize coroutine registers
2820 **          yield coA
2821 **          if eof(A) goto EofA
2822 **          yield coB
2823 **          if eof(B) goto EofB
2824 **    Cmpr: Compare A, B
2825 **          Jump AltB, AeqB, AgtB
2826 **     End: ...
2827 **
2828 ** We call AltB, AeqB, AgtB, EofA, and EofB "subroutines" but they are not
2829 ** actually called using Gosub and they do not Return.  EofA and EofB loop
2830 ** until all data is exhausted then jump to the "end" labe.  AltB, AeqB,
2831 ** and AgtB jump to either L2 or to one of EofA or EofB.
2832 */
2833 #ifndef SQLITE_OMIT_COMPOUND_SELECT
2834 static int multiSelectOrderBy(
2835   Parse *pParse,        /* Parsing context */
2836   Select *p,            /* The right-most of SELECTs to be coded */
2837   SelectDest *pDest     /* What to do with query results */
2838 ){
2839   int i, j;             /* Loop counters */
2840   Select *pPrior;       /* Another SELECT immediately to our left */
2841   Vdbe *v;              /* Generate code to this VDBE */
2842   SelectDest destA;     /* Destination for coroutine A */
2843   SelectDest destB;     /* Destination for coroutine B */
2844   int regAddrA;         /* Address register for select-A coroutine */
2845   int regAddrB;         /* Address register for select-B coroutine */
2846   int addrSelectA;      /* Address of the select-A coroutine */
2847   int addrSelectB;      /* Address of the select-B coroutine */
2848   int regOutA;          /* Address register for the output-A subroutine */
2849   int regOutB;          /* Address register for the output-B subroutine */
2850   int addrOutA;         /* Address of the output-A subroutine */
2851   int addrOutB = 0;     /* Address of the output-B subroutine */
2852   int addrEofA;         /* Address of the select-A-exhausted subroutine */
2853   int addrEofA_noB;     /* Alternate addrEofA if B is uninitialized */
2854   int addrEofB;         /* Address of the select-B-exhausted subroutine */
2855   int addrAltB;         /* Address of the A<B subroutine */
2856   int addrAeqB;         /* Address of the A==B subroutine */
2857   int addrAgtB;         /* Address of the A>B subroutine */
2858   int regLimitA;        /* Limit register for select-A */
2859   int regLimitB;        /* Limit register for select-A */
2860   int regPrev;          /* A range of registers to hold previous output */
2861   int savedLimit;       /* Saved value of p->iLimit */
2862   int savedOffset;      /* Saved value of p->iOffset */
2863   int labelCmpr;        /* Label for the start of the merge algorithm */
2864   int labelEnd;         /* Label for the end of the overall SELECT stmt */
2865   int addr1;            /* Jump instructions that get retargetted */
2866   int op;               /* One of TK_ALL, TK_UNION, TK_EXCEPT, TK_INTERSECT */
2867   KeyInfo *pKeyDup = 0; /* Comparison information for duplicate removal */
2868   KeyInfo *pKeyMerge;   /* Comparison information for merging rows */
2869   sqlite3 *db;          /* Database connection */
2870   ExprList *pOrderBy;   /* The ORDER BY clause */
2871   int nOrderBy;         /* Number of terms in the ORDER BY clause */
2872   int *aPermute;        /* Mapping from ORDER BY terms to result set columns */
2873 #ifndef SQLITE_OMIT_EXPLAIN
2874   int iSub1;            /* EQP id of left-hand query */
2875   int iSub2;            /* EQP id of right-hand query */
2876 #endif
2877
2878   assert( p->pOrderBy!=0 );
2879   assert( pKeyDup==0 ); /* "Managed" code needs this.  Ticket #3382. */
2880   db = pParse->db;
2881   v = pParse->pVdbe;
2882   assert( v!=0 );       /* Already thrown the error if VDBE alloc failed */
2883   labelEnd = sqlite3VdbeMakeLabel(v);
2884   labelCmpr = sqlite3VdbeMakeLabel(v);
2885
2886
2887   /* Patch up the ORDER BY clause
2888   */
2889   op = p->op;
2890   pPrior = p->pPrior;
2891   assert( pPrior->pOrderBy==0 );
2892   pOrderBy = p->pOrderBy;
2893   assert( pOrderBy );
2894   nOrderBy = pOrderBy->nExpr;
2895
2896   /* For operators other than UNION ALL we have to make sure that
2897   ** the ORDER BY clause covers every term of the result set.  Add
2898   ** terms to the ORDER BY clause as necessary.
2899   */
2900   if( op!=TK_ALL ){
2901     for(i=1; db->mallocFailed==0 && i<=p->pEList->nExpr; i++){
2902       struct ExprList_item *pItem;
2903       for(j=0, pItem=pOrderBy->a; j<nOrderBy; j++, pItem++){
2904         assert( pItem->u.x.iOrderByCol>0 );
2905         if( pItem->u.x.iOrderByCol==i ) break;
2906       }
2907       if( j==nOrderBy ){
2908         Expr *pNew = sqlite3Expr(db, TK_INTEGER, 0);
2909         if( pNew==0 ) return SQLITE_NOMEM_BKPT;
2910         pNew->flags |= EP_IntValue;
2911         pNew->u.iValue = i;
2912         p->pOrderBy = pOrderBy = sqlite3ExprListAppend(pParse, pOrderBy, pNew);
2913         if( pOrderBy ) pOrderBy->a[nOrderBy++].u.x.iOrderByCol = (u16)i;
2914       }
2915     }
2916   }
2917
2918   /* Compute the comparison permutation and keyinfo that is used with
2919   ** the permutation used to determine if the next
2920   ** row of results comes from selectA or selectB.  Also add explicit
2921   ** collations to the ORDER BY clause terms so that when the subqueries
2922   ** to the right and the left are evaluated, they use the correct
2923   ** collation.
2924   */
2925   aPermute = sqlite3DbMallocRawNN(db, sizeof(int)*(nOrderBy + 1));
2926   if( aPermute ){
2927     struct ExprList_item *pItem;
2928     aPermute[0] = nOrderBy;
2929     for(i=1, pItem=pOrderBy->a; i<=nOrderBy; i++, pItem++){
2930       assert( pItem->u.x.iOrderByCol>0 );
2931       assert( pItem->u.x.iOrderByCol<=p->pEList->nExpr );
2932       aPermute[i] = pItem->u.x.iOrderByCol - 1;
2933     }
2934     pKeyMerge = multiSelectOrderByKeyInfo(pParse, p, 1);
2935   }else{
2936     pKeyMerge = 0;
2937   }
2938
2939   /* Reattach the ORDER BY clause to the query.
2940   */
2941   p->pOrderBy = pOrderBy;
2942   pPrior->pOrderBy = sqlite3ExprListDup(pParse->db, pOrderBy, 0);
2943
2944   /* Allocate a range of temporary registers and the KeyInfo needed
2945   ** for the logic that removes duplicate result rows when the
2946   ** operator is UNION, EXCEPT, or INTERSECT (but not UNION ALL).
2947   */
2948   if( op==TK_ALL ){
2949     regPrev = 0;
2950   }else{
2951     int nExpr = p->pEList->nExpr;
2952     assert( nOrderBy>=nExpr || db->mallocFailed );
2953     regPrev = pParse->nMem+1;
2954     pParse->nMem += nExpr+1;
2955     sqlite3VdbeAddOp2(v, OP_Integer, 0, regPrev);
2956     pKeyDup = sqlite3KeyInfoAlloc(db, nExpr, 1);
2957     if( pKeyDup ){
2958       assert( sqlite3KeyInfoIsWriteable(pKeyDup) );
2959       for(i=0; i<nExpr; i++){
2960         pKeyDup->aColl[i] = multiSelectCollSeq(pParse, p, i);
2961         pKeyDup->aSortOrder[i] = 0;
2962       }
2963     }
2964   }
2965
2966   /* Separate the left and the right query from one another
2967   */
2968   p->pPrior = 0;
2969   pPrior->pNext = 0;
2970   sqlite3ResolveOrderGroupBy(pParse, p, p->pOrderBy, "ORDER");
2971   if( pPrior->pPrior==0 ){
2972     sqlite3ResolveOrderGroupBy(pParse, pPrior, pPrior->pOrderBy, "ORDER");
2973   }
2974
2975   /* Compute the limit registers */
2976   computeLimitRegisters(pParse, p, labelEnd);
2977   if( p->iLimit && op==TK_ALL ){
2978     regLimitA = ++pParse->nMem;
2979     regLimitB = ++pParse->nMem;
2980     sqlite3VdbeAddOp2(v, OP_Copy, p->iOffset ? p->iOffset+1 : p->iLimit,
2981                                   regLimitA);
2982     sqlite3VdbeAddOp2(v, OP_Copy, regLimitA, regLimitB);
2983   }else{
2984     regLimitA = regLimitB = 0;
2985   }
2986   sqlite3ExprDelete(db, p->pLimit);
2987   p->pLimit = 0;
2988
2989   regAddrA = ++pParse->nMem;
2990   regAddrB = ++pParse->nMem;
2991   regOutA = ++pParse->nMem;
2992   regOutB = ++pParse->nMem;
2993   sqlite3SelectDestInit(&destA, SRT_Coroutine, regAddrA);
2994   sqlite3SelectDestInit(&destB, SRT_Coroutine, regAddrB);
2995
2996   /* Generate a coroutine to evaluate the SELECT statement to the
2997   ** left of the compound operator - the "A" select.
2998   */
2999   addrSelectA = sqlite3VdbeCurrentAddr(v) + 1;
3000   addr1 = sqlite3VdbeAddOp3(v, OP_InitCoroutine, regAddrA, 0, addrSelectA);
3001   VdbeComment((v, "left SELECT"));
3002   pPrior->iLimit = regLimitA;
3003   explainSetInteger(iSub1, pParse->iNextSelectId);
3004   sqlite3Select(pParse, pPrior, &destA);
3005   sqlite3VdbeEndCoroutine(v, regAddrA);
3006   sqlite3VdbeJumpHere(v, addr1);
3007
3008   /* Generate a coroutine to evaluate the SELECT statement on
3009   ** the right - the "B" select
3010   */
3011   addrSelectB = sqlite3VdbeCurrentAddr(v) + 1;
3012   addr1 = sqlite3VdbeAddOp3(v, OP_InitCoroutine, regAddrB, 0, addrSelectB);
3013   VdbeComment((v, "right SELECT"));
3014   savedLimit = p->iLimit;
3015   savedOffset = p->iOffset;
3016   p->iLimit = regLimitB;
3017   p->iOffset = 0;
3018   explainSetInteger(iSub2, pParse->iNextSelectId);
3019   sqlite3Select(pParse, p, &destB);
3020   p->iLimit = savedLimit;
3021   p->iOffset = savedOffset;
3022   sqlite3VdbeEndCoroutine(v, regAddrB);
3023
3024   /* Generate a subroutine that outputs the current row of the A
3025   ** select as the next output row of the compound select.
3026   */
3027   VdbeNoopComment((v, "Output routine for A"));
3028   addrOutA = generateOutputSubroutine(pParse,
3029                  p, &destA, pDest, regOutA,
3030                  regPrev, pKeyDup, labelEnd);
3031
3032   /* Generate a subroutine that outputs the current row of the B
3033   ** select as the next output row of the compound select.
3034   */
3035   if( op==TK_ALL || op==TK_UNION ){
3036     VdbeNoopComment((v, "Output routine for B"));
3037     addrOutB = generateOutputSubroutine(pParse,
3038                  p, &destB, pDest, regOutB,
3039                  regPrev, pKeyDup, labelEnd);
3040   }
3041   sqlite3KeyInfoUnref(pKeyDup);
3042
3043   /* Generate a subroutine to run when the results from select A
3044   ** are exhausted and only data in select B remains.
3045   */
3046   if( op==TK_EXCEPT || op==TK_INTERSECT ){
3047     addrEofA_noB = addrEofA = labelEnd;
3048   }else{
3049     VdbeNoopComment((v, "eof-A subroutine"));
3050     addrEofA = sqlite3VdbeAddOp2(v, OP_Gosub, regOutB, addrOutB);
3051     addrEofA_noB = sqlite3VdbeAddOp2(v, OP_Yield, regAddrB, labelEnd);
3052                                      VdbeCoverage(v);
3053     sqlite3VdbeGoto(v, addrEofA);
3054     p->nSelectRow = sqlite3LogEstAdd(p->nSelectRow, pPrior->nSelectRow);
3055   }
3056
3057   /* Generate a subroutine to run when the results from select B
3058   ** are exhausted and only data in select A remains.
3059   */
3060   if( op==TK_INTERSECT ){
3061     addrEofB = addrEofA;
3062     if( p->nSelectRow > pPrior->nSelectRow ) p->nSelectRow = pPrior->nSelectRow;
3063   }else{
3064     VdbeNoopComment((v, "eof-B subroutine"));
3065     addrEofB = sqlite3VdbeAddOp2(v, OP_Gosub, regOutA, addrOutA);
3066     sqlite3VdbeAddOp2(v, OP_Yield, regAddrA, labelEnd); VdbeCoverage(v);
3067     sqlite3VdbeGoto(v, addrEofB);
3068   }
3069
3070   /* Generate code to handle the case of A<B
3071   */
3072   VdbeNoopComment((v, "A-lt-B subroutine"));
3073   addrAltB = sqlite3VdbeAddOp2(v, OP_Gosub, regOutA, addrOutA);
3074   sqlite3VdbeAddOp2(v, OP_Yield, regAddrA, addrEofA); VdbeCoverage(v);
3075   sqlite3VdbeGoto(v, labelCmpr);
3076
3077   /* Generate code to handle the case of A==B
3078   */
3079   if( op==TK_ALL ){
3080     addrAeqB = addrAltB;
3081   }else if( op==TK_INTERSECT ){
3082     addrAeqB = addrAltB;
3083     addrAltB++;
3084   }else{
3085     VdbeNoopComment((v, "A-eq-B subroutine"));
3086     addrAeqB =
3087     sqlite3VdbeAddOp2(v, OP_Yield, regAddrA, addrEofA); VdbeCoverage(v);
3088     sqlite3VdbeGoto(v, labelCmpr);
3089   }
3090
3091   /* Generate code to handle the case of A>B
3092   */
3093   VdbeNoopComment((v, "A-gt-B subroutine"));
3094   addrAgtB = sqlite3VdbeCurrentAddr(v);
3095   if( op==TK_ALL || op==TK_UNION ){
3096     sqlite3VdbeAddOp2(v, OP_Gosub, regOutB, addrOutB);
3097   }
3098   sqlite3VdbeAddOp2(v, OP_Yield, regAddrB, addrEofB); VdbeCoverage(v);
3099   sqlite3VdbeGoto(v, labelCmpr);
3100
3101   /* This code runs once to initialize everything.
3102   */
3103   sqlite3VdbeJumpHere(v, addr1);
3104   sqlite3VdbeAddOp2(v, OP_Yield, regAddrA, addrEofA_noB); VdbeCoverage(v);
3105   sqlite3VdbeAddOp2(v, OP_Yield, regAddrB, addrEofB); VdbeCoverage(v);
3106
3107   /* Implement the main merge loop
3108   */
3109   sqlite3VdbeResolveLabel(v, labelCmpr);
3110   sqlite3VdbeAddOp4(v, OP_Permutation, 0, 0, 0, (char*)aPermute, P4_INTARRAY);
3111   sqlite3VdbeAddOp4(v, OP_Compare, destA.iSdst, destB.iSdst, nOrderBy,
3112                          (char*)pKeyMerge, P4_KEYINFO);
3113   sqlite3VdbeChangeP5(v, OPFLAG_PERMUTE);
3114   sqlite3VdbeAddOp3(v, OP_Jump, addrAltB, addrAeqB, addrAgtB); VdbeCoverage(v);
3115
3116   /* Jump to the this point in order to terminate the query.
3117   */
3118   sqlite3VdbeResolveLabel(v, labelEnd);
3119
3120   /* Reassembly the compound query so that it will be freed correctly
3121   ** by the calling function */
3122   if( p->pPrior ){
3123     sqlite3SelectDelete(db, p->pPrior);
3124   }
3125   p->pPrior = pPrior;
3126   pPrior->pNext = p;
3127
3128   /*** TBD:  Insert subroutine calls to close cursors on incomplete
3129   **** subqueries ****/
3130   explainComposite(pParse, p->op, iSub1, iSub2, 0);
3131   return pParse->nErr!=0;
3132 }
3133 #endif
3134
3135 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3136
3137 /* An instance of the SubstContext object describes an substitution edit
3138 ** to be performed on a parse tree.
3139 **
3140 ** All references to columns in table iTable are to be replaced by corresponding
3141 ** expressions in pEList.
3142 */
3143 typedef struct SubstContext {
3144   Parse *pParse;            /* The parsing context */
3145   int iTable;               /* Replace references to this table */
3146   int iNewTable;            /* New table number */
3147   int isLeftJoin;           /* Add TK_IF_NULL_ROW opcodes on each replacement */
3148   ExprList *pEList;         /* Replacement expressions */
3149 } SubstContext;
3150
3151 /* Forward Declarations */
3152 static void substExprList(SubstContext*, ExprList*);
3153 static void substSelect(SubstContext*, Select*, int);
3154
3155 /*
3156 ** Scan through the expression pExpr.  Replace every reference to
3157 ** a column in table number iTable with a copy of the iColumn-th
3158 ** entry in pEList.  (But leave references to the ROWID column
3159 ** unchanged.)
3160 **
3161 ** This routine is part of the flattening procedure.  A subquery
3162 ** whose result set is defined by pEList appears as entry in the
3163 ** FROM clause of a SELECT such that the VDBE cursor assigned to that
3164 ** FORM clause entry is iTable.  This routine makes the necessary
3165 ** changes to pExpr so that it refers directly to the source table
3166 ** of the subquery rather the result set of the subquery.
3167 */
3168 static Expr *substExpr(
3169   SubstContext *pSubst,  /* Description of the substitution */
3170   Expr *pExpr            /* Expr in which substitution occurs */
3171 ){
3172   if( pExpr==0 ) return 0;
3173   if( ExprHasProperty(pExpr, EP_FromJoin)
3174    && pExpr->iRightJoinTable==pSubst->iTable
3175   ){
3176     pExpr->iRightJoinTable = pSubst->iNewTable;
3177   }
3178   if( pExpr->op==TK_COLUMN && pExpr->iTable==pSubst->iTable ){
3179     if( pExpr->iColumn<0 ){
3180       pExpr->op = TK_NULL;
3181     }else{
3182       Expr *pNew;
3183       Expr *pCopy = pSubst->pEList->a[pExpr->iColumn].pExpr;
3184       Expr ifNullRow;
3185       assert( pSubst->pEList!=0 && pExpr->iColumn<pSubst->pEList->nExpr );
3186       assert( pExpr->pLeft==0 && pExpr->pRight==0 );
3187       if( sqlite3ExprIsVector(pCopy) ){
3188         sqlite3VectorErrorMsg(pSubst->pParse, pCopy);
3189       }else{
3190         sqlite3 *db = pSubst->pParse->db;
3191         if( pSubst->isLeftJoin && pCopy->op!=TK_COLUMN ){
3192           memset(&ifNullRow, 0, sizeof(ifNullRow));
3193           ifNullRow.op = TK_IF_NULL_ROW;
3194           ifNullRow.pLeft = pCopy;
3195           ifNullRow.iTable = pSubst->iNewTable;
3196           pCopy = &ifNullRow;
3197         }
3198         pNew = sqlite3ExprDup(db, pCopy, 0);
3199         if( pNew && pSubst->isLeftJoin ){
3200           ExprSetProperty(pNew, EP_CanBeNull);
3201         }
3202         if( pNew && ExprHasProperty(pExpr,EP_FromJoin) ){
3203           pNew->iRightJoinTable = pExpr->iRightJoinTable;
3204           ExprSetProperty(pNew, EP_FromJoin);
3205         }
3206         sqlite3ExprDelete(db, pExpr);
3207         pExpr = pNew;
3208       }
3209     }
3210   }else{
3211     if( pExpr->op==TK_IF_NULL_ROW && pExpr->iTable==pSubst->iTable ){
3212       pExpr->iTable = pSubst->iNewTable;
3213     }
3214     pExpr->pLeft = substExpr(pSubst, pExpr->pLeft);
3215     pExpr->pRight = substExpr(pSubst, pExpr->pRight);
3216     if( ExprHasProperty(pExpr, EP_xIsSelect) ){
3217       substSelect(pSubst, pExpr->x.pSelect, 1);
3218     }else{
3219       substExprList(pSubst, pExpr->x.pList);
3220     }
3221   }
3222   return pExpr;
3223 }
3224 static void substExprList(
3225   SubstContext *pSubst, /* Description of the substitution */
3226   ExprList *pList       /* List to scan and in which to make substitutes */
3227 ){
3228   int i;
3229   if( pList==0 ) return;
3230   for(i=0; i<pList->nExpr; i++){
3231     pList->a[i].pExpr = substExpr(pSubst, pList->a[i].pExpr);
3232   }
3233 }
3234 static void substSelect(
3235   SubstContext *pSubst, /* Description of the substitution */
3236   Select *p,            /* SELECT statement in which to make substitutions */
3237   int doPrior           /* Do substitutes on p->pPrior too */
3238 ){
3239   SrcList *pSrc;
3240   struct SrcList_item *pItem;
3241   int i;
3242   if( !p ) return;
3243   do{
3244     substExprList(pSubst, p->pEList);
3245     substExprList(pSubst, p->pGroupBy);
3246     substExprList(pSubst, p->pOrderBy);
3247     p->pHaving = substExpr(pSubst, p->pHaving);
3248     p->pWhere = substExpr(pSubst, p->pWhere);
3249     pSrc = p->pSrc;
3250     assert( pSrc!=0 );
3251     for(i=pSrc->nSrc, pItem=pSrc->a; i>0; i--, pItem++){
3252       substSelect(pSubst, pItem->pSelect, 1);
3253       if( pItem->fg.isTabFunc ){
3254         substExprList(pSubst, pItem->u1.pFuncArg);
3255       }
3256     }
3257   }while( doPrior && (p = p->pPrior)!=0 );
3258 }
3259 #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */
3260
3261 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3262 /*
3263 ** This routine attempts to flatten subqueries as a performance optimization.
3264 ** This routine returns 1 if it makes changes and 0 if no flattening occurs.
3265 **
3266 ** To understand the concept of flattening, consider the following
3267 ** query:
3268 **
3269 **     SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5
3270 **
3271 ** The default way of implementing this query is to execute the
3272 ** subquery first and store the results in a temporary table, then
3273 ** run the outer query on that temporary table.  This requires two
3274 ** passes over the data.  Furthermore, because the temporary table
3275 ** has no indices, the WHERE clause on the outer query cannot be
3276 ** optimized.
3277 **
3278 ** This routine attempts to rewrite queries such as the above into
3279 ** a single flat select, like this:
3280 **
3281 **     SELECT x+y AS a FROM t1 WHERE z<100 AND a>5
3282 **
3283 ** The code generated for this simplification gives the same result
3284 ** but only has to scan the data once.  And because indices might
3285 ** exist on the table t1, a complete scan of the data might be
3286 ** avoided.
3287 **
3288 ** Flattening is subject to the following constraints:
3289 **
3290 **  (**)  We no longer attempt to flatten aggregate subqueries. Was:
3291 **        The subquery and the outer query cannot both be aggregates.
3292 **
3293 **  (**)  We no longer attempt to flatten aggregate subqueries. Was:
3294 **        (2) If the subquery is an aggregate then
3295 **        (2a) the outer query must not be a join and
3296 **        (2b) the outer query must not use subqueries
3297 **             other than the one FROM-clause subquery that is a candidate
3298 **             for flattening.  (This is due to ticket [2f7170d73bf9abf80]
3299 **             from 2015-02-09.)
3300 **
3301 **   (3)  If the subquery is the right operand of a LEFT JOIN then
3302 **        (3a) the subquery may not be a join and
3303 **        (3b) the FROM clause of the subquery may not contain a virtual
3304 **             table and
3305 **        (3c) the outer query may not be an aggregate.
3306 **
3307 **   (4)  The subquery can not be DISTINCT.
3308 **
3309 **  (**)  At one point restrictions (4) and (5) defined a subset of DISTINCT
3310 **        sub-queries that were excluded from this optimization. Restriction
3311 **        (4) has since been expanded to exclude all DISTINCT subqueries.
3312 **
3313 **  (**)  We no longer attempt to flatten aggregate subqueries.  Was:
3314 **        If the subquery is aggregate, the outer query may not be DISTINCT.
3315 **
3316 **   (7)  The subquery must have a FROM clause.  TODO:  For subqueries without
3317 **        A FROM clause, consider adding a FROM clause with the special
3318 **        table sqlite_once that consists of a single row containing a
3319 **        single NULL.
3320 **
3321 **   (8)  If the subquery uses LIMIT then the outer query may not be a join.
3322 **
3323 **   (9)  If the subquery uses LIMIT then the outer query may not be aggregate.
3324 **
3325 **  (**)  Restriction (10) was removed from the code on 2005-02-05 but we
3326 **        accidently carried the comment forward until 2014-09-15.  Original
3327 **        constraint: "If the subquery is aggregate then the outer query
3328 **        may not use LIMIT."
3329 **
3330 **  (11)  The subquery and the outer query may not both have ORDER BY clauses.
3331 **
3332 **  (**)  Not implemented.  Subsumed into restriction (3).  Was previously
3333 **        a separate restriction deriving from ticket #350.
3334 **
3335 **  (13)  The subquery and outer query may not both use LIMIT.
3336 **
3337 **  (14)  The subquery may not use OFFSET.
3338 **
3339 **  (15)  If the outer query is part of a compound select, then the
3340 **        subquery may not use LIMIT.
3341 **        (See ticket #2339 and ticket [02a8e81d44]).
3342 **
3343 **  (16)  If the outer query is aggregate, then the subquery may not
3344 **        use ORDER BY.  (Ticket #2942)  This used to not matter
3345 **        until we introduced the group_concat() function.
3346 **
3347 **  (17)  If the subquery is a compound select, then
3348 **        (17a) all compound operators must be a UNION ALL, and
3349 **        (17b) no terms within the subquery compound may be aggregate
3350 **              or DISTINCT, and
3351 **        (17c) every term within the subquery compound must have a FROM clause
3352 **        (17d) the outer query may not be
3353 **              (17d1) aggregate, or
3354 **              (17d2) DISTINCT, or
3355 **              (17d3) a join.
3356 **
3357 **        The parent and sub-query may contain WHERE clauses. Subject to
3358 **        rules (11), (13) and (14), they may also contain ORDER BY,
3359 **        LIMIT and OFFSET clauses.  The subquery cannot use any compound
3360 **        operator other than UNION ALL because all the other compound
3361 **        operators have an implied DISTINCT which is disallowed by
3362 **        restriction (4).
3363 **
3364 **        Also, each component of the sub-query must return the same number
3365 **        of result columns. This is actually a requirement for any compound
3366 **        SELECT statement, but all the code here does is make sure that no
3367 **        such (illegal) sub-query is flattened. The caller will detect the
3368 **        syntax error and return a detailed message.
3369 **
3370 **  (18)  If the sub-query is a compound select, then all terms of the
3371 **        ORDER BY clause of the parent must be simple references to
3372 **        columns of the sub-query.
3373 **
3374 **  (19)  If the subquery uses LIMIT then the outer query may not
3375 **        have a WHERE clause.
3376 **
3377 **  (20)  If the sub-query is a compound select, then it must not use
3378 **        an ORDER BY clause.  Ticket #3773.  We could relax this constraint
3379 **        somewhat by saying that the terms of the ORDER BY clause must
3380 **        appear as unmodified result columns in the outer query.  But we
3381 **        have other optimizations in mind to deal with that case.
3382 **
3383 **  (21)  If the subquery uses LIMIT then the outer query may not be
3384 **        DISTINCT.  (See ticket [752e1646fc]).
3385 **
3386 **  (22)  The subquery may not be a recursive CTE.
3387 **
3388 **  (**)  Subsumed into restriction (17d3).  Was: If the outer query is
3389 **        a recursive CTE, then the sub-query may not be a compound query.
3390 **        This restriction is because transforming the
3391 **        parent to a compound query confuses the code that handles
3392 **        recursive queries in multiSelect().
3393 **
3394 **  (**)  We no longer attempt to flatten aggregate subqueries.  Was:
3395 **        The subquery may not be an aggregate that uses the built-in min() or
3396 **        or max() functions.  (Without this restriction, a query like:
3397 **        "SELECT x FROM (SELECT max(y), x FROM t1)" would not necessarily
3398 **        return the value X for which Y was maximal.)
3399 **
3400 **
3401 ** In this routine, the "p" parameter is a pointer to the outer query.
3402 ** The subquery is p->pSrc->a[iFrom].  isAgg is true if the outer query
3403 ** uses aggregates.
3404 **
3405 ** If flattening is not attempted, this routine is a no-op and returns 0.
3406 ** If flattening is attempted this routine returns 1.
3407 **
3408 ** All of the expression analysis must occur on both the outer query and
3409 ** the subquery before this routine runs.
3410 */
3411 static int flattenSubquery(
3412   Parse *pParse,       /* Parsing context */
3413   Select *p,           /* The parent or outer SELECT statement */
3414   int iFrom,           /* Index in p->pSrc->a[] of the inner subquery */
3415   int isAgg            /* True if outer SELECT uses aggregate functions */
3416 ){
3417   const char *zSavedAuthContext = pParse->zAuthContext;
3418   Select *pParent;    /* Current UNION ALL term of the other query */
3419   Select *pSub;       /* The inner query or "subquery" */
3420   Select *pSub1;      /* Pointer to the rightmost select in sub-query */
3421   SrcList *pSrc;      /* The FROM clause of the outer query */
3422   SrcList *pSubSrc;   /* The FROM clause of the subquery */
3423   int iParent;        /* VDBE cursor number of the pSub result set temp table */
3424   int iNewParent = -1;/* Replacement table for iParent */
3425   int isLeftJoin = 0; /* True if pSub is the right side of a LEFT JOIN */
3426   int i;              /* Loop counter */
3427   Expr *pWhere;                    /* The WHERE clause */
3428   struct SrcList_item *pSubitem;   /* The subquery */
3429   sqlite3 *db = pParse->db;
3430
3431   /* Check to see if flattening is permitted.  Return 0 if not.
3432   */
3433   assert( p!=0 );
3434   assert( p->pPrior==0 );
3435   if( OptimizationDisabled(db, SQLITE_QueryFlattener) ) return 0;
3436   pSrc = p->pSrc;
3437   assert( pSrc && iFrom>=0 && iFrom<pSrc->nSrc );
3438   pSubitem = &pSrc->a[iFrom];
3439   iParent = pSubitem->iCursor;
3440   pSub = pSubitem->pSelect;
3441   assert( pSub!=0 );
3442
3443   pSubSrc = pSub->pSrc;
3444   assert( pSubSrc );
3445   /* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,
3446   ** not arbitrary expressions, we allowed some combining of LIMIT and OFFSET
3447   ** because they could be computed at compile-time.  But when LIMIT and OFFSET
3448   ** became arbitrary expressions, we were forced to add restrictions (13)
3449   ** and (14). */
3450   if( pSub->pLimit && p->pLimit ) return 0;              /* Restriction (13) */
3451   if( pSub->pLimit && pSub->pLimit->pRight ) return 0;   /* Restriction (14) */
3452   if( (p->selFlags & SF_Compound)!=0 && pSub->pLimit ){
3453     return 0;                                            /* Restriction (15) */
3454   }
3455   if( pSubSrc->nSrc==0 ) return 0;                       /* Restriction (7)  */
3456   if( pSub->selFlags & SF_Distinct ) return 0;           /* Restriction (4)  */
3457   if( pSub->pLimit && (pSrc->nSrc>1 || isAgg) ){
3458      return 0;         /* Restrictions (8)(9) */
3459   }
3460   if( p->pOrderBy && pSub->pOrderBy ){
3461      return 0;                                           /* Restriction (11) */
3462   }
3463   if( isAgg && pSub->pOrderBy ) return 0;                /* Restriction (16) */
3464   if( pSub->pLimit && p->pWhere ) return 0;              /* Restriction (19) */
3465   if( pSub->pLimit && (p->selFlags & SF_Distinct)!=0 ){
3466      return 0;         /* Restriction (21) */
3467   }
3468   if( pSub->selFlags & (SF_Recursive) ){
3469     return 0; /* Restrictions (22) */
3470   }
3471
3472   /*
3473   ** If the subquery is the right operand of a LEFT JOIN, then the
3474   ** subquery may not be a join itself (3a). Example of why this is not
3475   ** allowed:
3476   **
3477   **         t1 LEFT OUTER JOIN (t2 JOIN t3)
3478   **
3479   ** If we flatten the above, we would get
3480   **
3481   **         (t1 LEFT OUTER JOIN t2) JOIN t3
3482   **
3483   ** which is not at all the same thing.
3484   **
3485   ** If the subquery is the right operand of a LEFT JOIN, then the outer
3486   ** query cannot be an aggregate. (3c)  This is an artifact of the way
3487   ** aggregates are processed - there is no mechanism to determine if
3488   ** the LEFT JOIN table should be all-NULL.
3489   **
3490   ** See also tickets #306, #350, and #3300.
3491   */
3492   if( (pSubitem->fg.jointype & JT_OUTER)!=0 ){
3493     isLeftJoin = 1;
3494     if( pSubSrc->nSrc>1 || isAgg || IsVirtual(pSubSrc->a[0].pTab) ){
3495       /*  (3a)             (3c)     (3b) */
3496       return 0;
3497     }
3498   }
3499 #ifdef SQLITE_EXTRA_IFNULLROW
3500   else if( iFrom>0 && !isAgg ){
3501     /* Setting isLeftJoin to -1 causes OP_IfNullRow opcodes to be generated for
3502     ** every reference to any result column from subquery in a join, even
3503     ** though they are not necessary.  This will stress-test the OP_IfNullRow
3504     ** opcode. */
3505     isLeftJoin = -1;
3506   }
3507 #endif
3508
3509   /* Restriction (17): If the sub-query is a compound SELECT, then it must
3510   ** use only the UNION ALL operator. And none of the simple select queries
3511   ** that make up the compound SELECT are allowed to be aggregate or distinct
3512   ** queries.
3513   */
3514   if( pSub->pPrior ){
3515     if( pSub->pOrderBy ){
3516       return 0;  /* Restriction (20) */
3517     }
3518     if( isAgg || (p->selFlags & SF_Distinct)!=0 || pSrc->nSrc!=1 ){
3519       return 0; /* (17d1), (17d2), or (17d3) */
3520     }
3521     for(pSub1=pSub; pSub1; pSub1=pSub1->pPrior){
3522       testcase( (pSub1->selFlags & (SF_Distinct|SF_Aggregate))==SF_Distinct );
3523       testcase( (pSub1->selFlags & (SF_Distinct|SF_Aggregate))==SF_Aggregate );
3524       assert( pSub->pSrc!=0 );
3525       assert( pSub->pEList->nExpr==pSub1->pEList->nExpr );
3526       if( (pSub1->selFlags & (SF_Distinct|SF_Aggregate))!=0    /* (17b) */
3527        || (pSub1->pPrior && pSub1->op!=TK_ALL)                 /* (17a) */
3528        || pSub1->pSrc->nSrc<1                                  /* (17c) */
3529       ){
3530         return 0;
3531       }
3532       testcase( pSub1->pSrc->nSrc>1 );
3533     }
3534
3535     /* Restriction (18). */
3536     if( p->pOrderBy ){
3537       int ii;
3538       for(ii=0; ii<p->pOrderBy->nExpr; ii++){
3539         if( p->pOrderBy->a[ii].u.x.iOrderByCol==0 ) return 0;
3540       }
3541     }
3542   }
3543
3544   /* Ex-restriction (23):
3545   ** The only way that the recursive part of a CTE can contain a compound
3546   ** subquery is for the subquery to be one term of a join.  But if the
3547   ** subquery is a join, then the flattening has already been stopped by
3548   ** restriction (17d3)
3549   */
3550   assert( (p->selFlags & SF_Recursive)==0 || pSub->pPrior==0 );
3551
3552   /***** If we reach this point, flattening is permitted. *****/
3553   SELECTTRACE(1,pParse,p,("flatten %s.%p from term %d\n",
3554                    pSub->zSelName, pSub, iFrom));
3555
3556   /* Authorize the subquery */
3557   pParse->zAuthContext = pSubitem->zName;
3558   TESTONLY(i =) sqlite3AuthCheck(pParse, SQLITE_SELECT, 0, 0, 0);
3559   testcase( i==SQLITE_DENY );
3560   pParse->zAuthContext = zSavedAuthContext;
3561
3562   /* If the sub-query is a compound SELECT statement, then (by restrictions
3563   ** 17 and 18 above) it must be a UNION ALL and the parent query must
3564   ** be of the form:
3565   **
3566   **     SELECT <expr-list> FROM (<sub-query>) <where-clause>
3567   **
3568   ** followed by any ORDER BY, LIMIT and/or OFFSET clauses. This block
3569   ** creates N-1 copies of the parent query without any ORDER BY, LIMIT or
3570   ** OFFSET clauses and joins them to the left-hand-side of the original
3571   ** using UNION ALL operators. In this case N is the number of simple
3572   ** select statements in the compound sub-query.
3573   **
3574   ** Example:
3575   **
3576   **     SELECT a+1 FROM (
3577   **        SELECT x FROM tab
3578   **        UNION ALL
3579   **        SELECT y FROM tab
3580   **        UNION ALL
3581   **        SELECT abs(z*2) FROM tab2
3582   **     ) WHERE a!=5 ORDER BY 1
3583   **
3584   ** Transformed into:
3585   **
3586   **     SELECT x+1 FROM tab WHERE x+1!=5
3587   **     UNION ALL
3588   **     SELECT y+1 FROM tab WHERE y+1!=5
3589   **     UNION ALL
3590   **     SELECT abs(z*2)+1 FROM tab2 WHERE abs(z*2)+1!=5
3591   **     ORDER BY 1
3592   **
3593   ** We call this the "compound-subquery flattening".
3594   */
3595   for(pSub=pSub->pPrior; pSub; pSub=pSub->pPrior){
3596     Select *pNew;
3597     ExprList *pOrderBy = p->pOrderBy;
3598     Expr *pLimit = p->pLimit;
3599     Select *pPrior = p->pPrior;
3600     p->pOrderBy = 0;
3601     p->pSrc = 0;
3602     p->pPrior = 0;
3603     p->pLimit = 0;
3604     pNew = sqlite3SelectDup(db, p, 0);
3605     sqlite3SelectSetName(pNew, pSub->zSelName);
3606     p->pLimit = pLimit;
3607     p->pOrderBy = pOrderBy;
3608     p->pSrc = pSrc;
3609     p->op = TK_ALL;
3610     if( pNew==0 ){
3611       p->pPrior = pPrior;
3612     }else{
3613       pNew->pPrior = pPrior;
3614       if( pPrior ) pPrior->pNext = pNew;
3615       pNew->pNext = p;
3616       p->pPrior = pNew;
3617       SELECTTRACE(2,pParse,p,
3618          ("compound-subquery flattener creates %s.%p as peer\n",
3619          pNew->zSelName, pNew));
3620     }
3621     if( db->mallocFailed ) return 1;
3622   }
3623
3624   /* Begin flattening the iFrom-th entry of the FROM clause
3625   ** in the outer query.
3626   */
3627   pSub = pSub1 = pSubitem->pSelect;
3628
3629   /* Delete the transient table structure associated with the
3630   ** subquery
3631   */
3632   sqlite3DbFree(db, pSubitem->zDatabase);
3633   sqlite3DbFree(db, pSubitem->zName);
3634   sqlite3DbFree(db, pSubitem->zAlias);
3635   pSubitem->zDatabase = 0;
3636   pSubitem->zName = 0;
3637   pSubitem->zAlias = 0;
3638   pSubitem->pSelect = 0;
3639
3640   /* Defer deleting the Table object associated with the
3641   ** subquery until code generation is
3642   ** complete, since there may still exist Expr.pTab entries that
3643   ** refer to the subquery even after flattening.  Ticket #3346.
3644   **
3645   ** pSubitem->pTab is always non-NULL by test restrictions and tests above.
3646   */
3647   if( ALWAYS(pSubitem->pTab!=0) ){
3648     Table *pTabToDel = pSubitem->pTab;
3649     if( pTabToDel->nTabRef==1 ){
3650       Parse *pToplevel = sqlite3ParseToplevel(pParse);
3651       pTabToDel->pNextZombie = pToplevel->pZombieTab;
3652       pToplevel->pZombieTab = pTabToDel;
3653     }else{
3654       pTabToDel->nTabRef--;
3655     }
3656     pSubitem->pTab = 0;
3657   }
3658
3659   /* The following loop runs once for each term in a compound-subquery
3660   ** flattening (as described above).  If we are doing a different kind
3661   ** of flattening - a flattening other than a compound-subquery flattening -
3662   ** then this loop only runs once.
3663   **
3664   ** This loop moves all of the FROM elements of the subquery into the
3665   ** the FROM clause of the outer query.  Before doing this, remember
3666   ** the cursor number for the original outer query FROM element in
3667   ** iParent.  The iParent cursor will never be used.  Subsequent code
3668   ** will scan expressions looking for iParent references and replace
3669   ** those references with expressions that resolve to the subquery FROM
3670   ** elements we are now copying in.
3671   */
3672   for(pParent=p; pParent; pParent=pParent->pPrior, pSub=pSub->pPrior){
3673     int nSubSrc;
3674     u8 jointype = 0;
3675     pSubSrc = pSub->pSrc;     /* FROM clause of subquery */
3676     nSubSrc = pSubSrc->nSrc;  /* Number of terms in subquery FROM clause */
3677     pSrc = pParent->pSrc;     /* FROM clause of the outer query */
3678
3679     if( pSrc ){
3680       assert( pParent==p );  /* First time through the loop */
3681       jointype = pSubitem->fg.jointype;
3682     }else{
3683       assert( pParent!=p );  /* 2nd and subsequent times through the loop */
3684       pSrc = pParent->pSrc = sqlite3SrcListAppend(db, 0, 0, 0);
3685       if( pSrc==0 ){
3686         assert( db->mallocFailed );
3687         break;
3688       }
3689     }
3690
3691     /* The subquery uses a single slot of the FROM clause of the outer
3692     ** query.  If the subquery has more than one element in its FROM clause,
3693     ** then expand the outer query to make space for it to hold all elements
3694     ** of the subquery.
3695     **
3696     ** Example:
3697     **
3698     **    SELECT * FROM tabA, (SELECT * FROM sub1, sub2), tabB;
3699     **
3700     ** The outer query has 3 slots in its FROM clause.  One slot of the
3701     ** outer query (the middle slot) is used by the subquery.  The next
3702     ** block of code will expand the outer query FROM clause to 4 slots.
3703     ** The middle slot is expanded to two slots in order to make space
3704     ** for the two elements in the FROM clause of the subquery.
3705     */
3706     if( nSubSrc>1 ){
3707       pParent->pSrc = pSrc = sqlite3SrcListEnlarge(db, pSrc, nSubSrc-1,iFrom+1);
3708       if( db->mallocFailed ){
3709         break;
3710       }
3711     }
3712
3713     /* Transfer the FROM clause terms from the subquery into the
3714     ** outer query.
3715     */
3716     for(i=0; i<nSubSrc; i++){
3717       sqlite3IdListDelete(db, pSrc->a[i+iFrom].pUsing);
3718       assert( pSrc->a[i+iFrom].fg.isTabFunc==0 );
3719       pSrc->a[i+iFrom] = pSubSrc->a[i];
3720       iNewParent = pSubSrc->a[i].iCursor;
3721       memset(&pSubSrc->a[i], 0, sizeof(pSubSrc->a[i]));
3722     }
3723     pSrc->a[iFrom].fg.jointype = jointype;
3724
3725     /* Now begin substituting subquery result set expressions for
3726     ** references to the iParent in the outer query.
3727     **
3728     ** Example:
3729     **
3730     **   SELECT a+5, b*10 FROM (SELECT x*3 AS a, y+10 AS b FROM t1) WHERE a>b;
3731     **   \                     \_____________ subquery __________/          /
3732     **    \_____________________ outer query ______________________________/
3733     **
3734     ** We look at every expression in the outer query and every place we see
3735     ** "a" we substitute "x*3" and every place we see "b" we substitute "y+10".
3736     */
3737     if( pSub->pOrderBy ){
3738       /* At this point, any non-zero iOrderByCol values indicate that the
3739       ** ORDER BY column expression is identical to the iOrderByCol'th
3740       ** expression returned by SELECT statement pSub. Since these values
3741       ** do not necessarily correspond to columns in SELECT statement pParent,
3742       ** zero them before transfering the ORDER BY clause.
3743       **
3744       ** Not doing this may cause an error if a subsequent call to this
3745       ** function attempts to flatten a compound sub-query into pParent
3746       ** (the only way this can happen is if the compound sub-query is
3747       ** currently part of pSub->pSrc). See ticket [d11a6e908f].  */
3748       ExprList *pOrderBy = pSub->pOrderBy;
3749       for(i=0; i<pOrderBy->nExpr; i++){
3750         pOrderBy->a[i].u.x.iOrderByCol = 0;
3751       }
3752       assert( pParent->pOrderBy==0 );
3753       assert( pSub->pPrior==0 );
3754       pParent->pOrderBy = pOrderBy;
3755       pSub->pOrderBy = 0;
3756     }
3757     pWhere = sqlite3ExprDup(db, pSub->pWhere, 0);
3758     if( isLeftJoin>0 ){
3759       setJoinExpr(pWhere, iNewParent);
3760     }
3761     pParent->pWhere = sqlite3ExprAnd(db, pWhere, pParent->pWhere);
3762     if( db->mallocFailed==0 ){
3763       SubstContext x;
3764       x.pParse = pParse;
3765       x.iTable = iParent;
3766       x.iNewTable = iNewParent;
3767       x.isLeftJoin = isLeftJoin;
3768       x.pEList = pSub->pEList;
3769       substSelect(&x, pParent, 0);
3770     }
3771
3772     /* The flattened query is distinct if either the inner or the
3773     ** outer query is distinct.
3774     */
3775     pParent->selFlags |= pSub->selFlags & SF_Distinct;
3776
3777     /*
3778     ** SELECT ... FROM (SELECT ... LIMIT a OFFSET b) LIMIT x OFFSET y;
3779     **
3780     ** One is tempted to try to add a and b to combine the limits.  But this
3781     ** does not work if either limit is negative.
3782     */
3783     if( pSub->pLimit ){
3784       pParent->pLimit = pSub->pLimit;
3785       pSub->pLimit = 0;
3786     }
3787   }
3788
3789   /* Finially, delete what is left of the subquery and return
3790   ** success.
3791   */
3792   sqlite3SelectDelete(db, pSub1);
3793
3794 #if SELECTTRACE_ENABLED
3795   if( sqlite3SelectTrace & 0x100 ){
3796     SELECTTRACE(0x100,pParse,p,("After flattening:\n"));
3797     sqlite3TreeViewSelect(0, p, 0);
3798   }
3799 #endif
3800
3801   return 1;
3802 }
3803 #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */
3804
3805
3806
3807 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3808 /*
3809 ** Make copies of relevant WHERE clause terms of the outer query into
3810 ** the WHERE clause of subquery.  Example:
3811 **
3812 **    SELECT * FROM (SELECT a AS x, c-d AS y FROM t1) WHERE x=5 AND y=10;
3813 **
3814 ** Transformed into:
3815 **
3816 **    SELECT * FROM (SELECT a AS x, c-d AS y FROM t1 WHERE a=5 AND c-d=10)
3817 **     WHERE x=5 AND y=10;
3818 **
3819 ** The hope is that the terms added to the inner query will make it more
3820 ** efficient.
3821 **
3822 ** Do not attempt this optimization if:
3823 **
3824 **   (1) (** This restriction was removed on 2017-09-29.  We used to
3825 **           disallow this optimization for aggregate subqueries, but now
3826 **           it is allowed by putting the extra terms on the HAVING clause.
3827 **           The added HAVING clause is pointless if the subquery lacks
3828 **           a GROUP BY clause.  But such a HAVING clause is also harmless
3829 **           so there does not appear to be any reason to add extra logic
3830 **           to suppress it. **)
3831 **
3832 **   (2) The inner query is the recursive part of a common table expression.
3833 **
3834 **   (3) The inner query has a LIMIT clause (since the changes to the WHERE
3835 **       close would change the meaning of the LIMIT).
3836 **
3837 **   (4) The inner query is the right operand of a LEFT JOIN.  (The caller
3838 **       enforces this restriction since this routine does not have enough
3839 **       information to know.)
3840 **
3841 **   (5) The WHERE clause expression originates in the ON or USING clause
3842 **       of a LEFT JOIN.
3843 **
3844 ** Return 0 if no changes are made and non-zero if one or more WHERE clause
3845 ** terms are duplicated into the subquery.
3846 */
3847 static int pushDownWhereTerms(
3848   Parse *pParse,        /* Parse context (for malloc() and error reporting) */
3849   Select *pSubq,        /* The subquery whose WHERE clause is to be augmented */
3850   Expr *pWhere,         /* The WHERE clause of the outer query */
3851   int iCursor           /* Cursor number of the subquery */
3852 ){
3853   Expr *pNew;
3854   int nChng = 0;
3855   if( pWhere==0 ) return 0;
3856   if( pSubq->selFlags & SF_Recursive ) return 0;  /* restriction (2) */
3857
3858 #ifdef SQLITE_DEBUG
3859   /* Only the first term of a compound can have a WITH clause.  But make
3860   ** sure no other terms are marked SF_Recursive in case something changes
3861   ** in the future.
3862   */
3863   {
3864     Select *pX;
3865     for(pX=pSubq; pX; pX=pX->pPrior){
3866       assert( (pX->selFlags & (SF_Recursive))==0 );
3867     }
3868   }
3869 #endif
3870
3871   if( pSubq->pLimit!=0 ){
3872     return 0; /* restriction (3) */
3873   }
3874   while( pWhere->op==TK_AND ){
3875     nChng += pushDownWhereTerms(pParse, pSubq, pWhere->pRight, iCursor);
3876     pWhere = pWhere->pLeft;
3877   }
3878   if( ExprHasProperty(pWhere,EP_FromJoin) ) return 0; /* restriction (5) */
3879   if( sqlite3ExprIsTableConstant(pWhere, iCursor) ){
3880     nChng++;
3881     while( pSubq ){
3882       SubstContext x;
3883       pNew = sqlite3ExprDup(pParse->db, pWhere, 0);
3884       x.pParse = pParse;
3885       x.iTable = iCursor;
3886       x.iNewTable = iCursor;
3887       x.isLeftJoin = 0;
3888       x.pEList = pSubq->pEList;
3889       pNew = substExpr(&x, pNew);
3890       if( pSubq->selFlags & SF_Aggregate ){
3891         pSubq->pHaving = sqlite3ExprAnd(pParse->db, pSubq->pHaving, pNew);
3892       }else{
3893         pSubq->pWhere = sqlite3ExprAnd(pParse->db, pSubq->pWhere, pNew);
3894       }
3895       pSubq = pSubq->pPrior;
3896     }
3897   }
3898   return nChng;
3899 }
3900 #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */
3901
3902 /*
3903 ** The pFunc is the only aggregate function in the query.  Check to see
3904 ** if the query is a candidate for the min/max optimization.
3905 **
3906 ** If the query is a candidate for the min/max optimization, then set
3907 ** *ppMinMax to be an ORDER BY clause to be used for the optimization
3908 ** and return either WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX depending on
3909 ** whether pFunc is a min() or max() function.
3910 **
3911 ** If the query is not a candidate for the min/max optimization, return
3912 ** WHERE_ORDERBY_NORMAL (which must be zero).
3913 **
3914 ** This routine must be called after aggregate functions have been
3915 ** located but before their arguments have been subjected to aggregate
3916 ** analysis.
3917 */
3918 static u8 minMaxQuery(sqlite3 *db, Expr *pFunc, ExprList **ppMinMax){
3919   int eRet = WHERE_ORDERBY_NORMAL;      /* Return value */
3920   ExprList *pEList = pFunc->x.pList;    /* Arguments to agg function */
3921   const char *zFunc;                    /* Name of aggregate function pFunc */
3922   ExprList *pOrderBy;
3923   u8 sortOrder;
3924
3925   assert( *ppMinMax==0 );
3926   assert( pFunc->op==TK_AGG_FUNCTION );
3927   if( pEList==0 || pEList->nExpr!=1 ) return eRet;
3928   zFunc = pFunc->u.zToken;
3929   if( sqlite3StrICmp(zFunc, "min")==0 ){
3930     eRet = WHERE_ORDERBY_MIN;
3931     sortOrder = SQLITE_SO_ASC;
3932   }else if( sqlite3StrICmp(zFunc, "max")==0 ){
3933     eRet = WHERE_ORDERBY_MAX;
3934     sortOrder = SQLITE_SO_DESC;
3935   }else{
3936     return eRet;
3937   }
3938   *ppMinMax = pOrderBy = sqlite3ExprListDup(db, pEList, 0);
3939   assert( pOrderBy!=0 || db->mallocFailed );
3940   if( pOrderBy ) pOrderBy->a[0].sortOrder = sortOrder;
3941   return eRet;
3942 }
3943
3944 /*
3945 ** The select statement passed as the first argument is an aggregate query.
3946 ** The second argument is the associated aggregate-info object. This
3947 ** function tests if the SELECT is of the form:
3948 **
3949 **   SELECT count(*) FROM <tbl>
3950 **
3951 ** where table is a database table, not a sub-select or view. If the query
3952 ** does match this pattern, then a pointer to the Table object representing
3953 ** <tbl> is returned. Otherwise, 0 is returned.
3954 */
3955 static Table *isSimpleCount(Select *p, AggInfo *pAggInfo){
3956   Table *pTab;
3957   Expr *pExpr;
3958
3959   assert( !p->pGroupBy );
3960
3961   if( p->pWhere || p->pEList->nExpr!=1
3962    || p->pSrc->nSrc!=1 || p->pSrc->a[0].pSelect
3963   ){
3964     return 0;
3965   }
3966   pTab = p->pSrc->a[0].pTab;
3967   pExpr = p->pEList->a[0].pExpr;
3968   assert( pTab && !pTab->pSelect && pExpr );
3969
3970   if( IsVirtual(pTab) ) return 0;
3971   if( pExpr->op!=TK_AGG_FUNCTION ) return 0;
3972   if( NEVER(pAggInfo->nFunc==0) ) return 0;
3973   if( (pAggInfo->aFunc[0].pFunc->funcFlags&SQLITE_FUNC_COUNT)==0 ) return 0;
3974   if( pExpr->flags&EP_Distinct ) return 0;
3975
3976   return pTab;
3977 }
3978
3979 /*
3980 ** If the source-list item passed as an argument was augmented with an
3981 ** INDEXED BY clause, then try to locate the specified index. If there
3982 ** was such a clause and the named index cannot be found, return
3983 ** SQLITE_ERROR and leave an error in pParse. Otherwise, populate
3984 ** pFrom->pIndex and return SQLITE_OK.
3985 */
3986 int sqlite3IndexedByLookup(Parse *pParse, struct SrcList_item *pFrom){
3987   if( pFrom->pTab && pFrom->fg.isIndexedBy ){
3988     Table *pTab = pFrom->pTab;
3989     char *zIndexedBy = pFrom->u1.zIndexedBy;
3990     Index *pIdx;
3991     for(pIdx=pTab->pIndex;
3992         pIdx && sqlite3StrICmp(pIdx->zName, zIndexedBy);
3993         pIdx=pIdx->pNext
3994     );
3995     if( !pIdx ){
3996       sqlite3ErrorMsg(pParse, "no such index: %s", zIndexedBy, 0);
3997       pParse->checkSchema = 1;
3998       return SQLITE_ERROR;
3999     }
4000     pFrom->pIBIndex = pIdx;
4001   }
4002   return SQLITE_OK;
4003 }
4004 /*
4005 ** Detect compound SELECT statements that use an ORDER BY clause with
4006 ** an alternative collating sequence.
4007 **
4008 **    SELECT ... FROM t1 EXCEPT SELECT ... FROM t2 ORDER BY .. COLLATE ...
4009 **
4010 ** These are rewritten as a subquery:
4011 **
4012 **    SELECT * FROM (SELECT ... FROM t1 EXCEPT SELECT ... FROM t2)
4013 **     ORDER BY ... COLLATE ...
4014 **
4015 ** This transformation is necessary because the multiSelectOrderBy() routine
4016 ** above that generates the code for a compound SELECT with an ORDER BY clause
4017 ** uses a merge algorithm that requires the same collating sequence on the
4018 ** result columns as on the ORDER BY clause.  See ticket
4019 ** http://www.sqlite.org/src/info/6709574d2a
4020 **
4021 ** This transformation is only needed for EXCEPT, INTERSECT, and UNION.
4022 ** The UNION ALL operator works fine with multiSelectOrderBy() even when
4023 ** there are COLLATE terms in the ORDER BY.
4024 */
4025 static int convertCompoundSelectToSubquery(Walker *pWalker, Select *p){
4026   int i;
4027   Select *pNew;
4028   Select *pX;
4029   sqlite3 *db;
4030   struct ExprList_item *a;
4031   SrcList *pNewSrc;
4032   Parse *pParse;
4033   Token dummy;
4034
4035   if( p->pPrior==0 ) return WRC_Continue;
4036   if( p->pOrderBy==0 ) return WRC_Continue;
4037   for(pX=p; pX && (pX->op==TK_ALL || pX->op==TK_SELECT); pX=pX->pPrior){}
4038   if( pX==0 ) return WRC_Continue;
4039   a = p->pOrderBy->a;
4040   for(i=p->pOrderBy->nExpr-1; i>=0; i--){
4041     if( a[i].pExpr->flags & EP_Collate ) break;
4042   }
4043   if( i<0 ) return WRC_Continue;
4044
4045   /* If we reach this point, that means the transformation is required. */
4046
4047   pParse = pWalker->pParse;
4048   db = pParse->db;
4049   pNew = sqlite3DbMallocZero(db, sizeof(*pNew) );
4050   if( pNew==0 ) return WRC_Abort;
4051   memset(&dummy, 0, sizeof(dummy));
4052   pNewSrc = sqlite3SrcListAppendFromTerm(pParse,0,0,0,&dummy,pNew,0,0);
4053   if( pNewSrc==0 ) return WRC_Abort;
4054   *pNew = *p;
4055   p->pSrc = pNewSrc;
4056   p->pEList = sqlite3ExprListAppend(pParse, 0, sqlite3Expr(db, TK_ASTERISK, 0));
4057   p->op = TK_SELECT;
4058   p->pWhere = 0;
4059   pNew->pGroupBy = 0;
4060   pNew->pHaving = 0;
4061   pNew->pOrderBy = 0;
4062   p->pPrior = 0;
4063   p->pNext = 0;
4064   p->pWith = 0;
4065   p->selFlags &= ~SF_Compound;
4066   assert( (p->selFlags & SF_Converted)==0 );
4067   p->selFlags |= SF_Converted;
4068   assert( pNew->pPrior!=0 );
4069   pNew->pPrior->pNext = pNew;
4070   pNew->pLimit = 0;
4071   return WRC_Continue;
4072 }
4073
4074 /*
4075 ** Check to see if the FROM clause term pFrom has table-valued function
4076 ** arguments.  If it does, leave an error message in pParse and return
4077 ** non-zero, since pFrom is not allowed to be a table-valued function.
4078 */
4079 static int cannotBeFunction(Parse *pParse, struct SrcList_item *pFrom){
4080   if( pFrom->fg.isTabFunc ){
4081     sqlite3ErrorMsg(pParse, "'%s' is not a function", pFrom->zName);
4082     return 1;
4083   }
4084   return 0;
4085 }
4086
4087 #ifndef SQLITE_OMIT_CTE
4088 /*
4089 ** Argument pWith (which may be NULL) points to a linked list of nested
4090 ** WITH contexts, from inner to outermost. If the table identified by
4091 ** FROM clause element pItem is really a common-table-expression (CTE)
4092 ** then return a pointer to the CTE definition for that table. Otherwise
4093 ** return NULL.
4094 **
4095 ** If a non-NULL value is returned, set *ppContext to point to the With
4096 ** object that the returned CTE belongs to.
4097 */
4098 static struct Cte *searchWith(
4099   With *pWith,                    /* Current innermost WITH clause */
4100   struct SrcList_item *pItem,     /* FROM clause element to resolve */
4101   With **ppContext                /* OUT: WITH clause return value belongs to */
4102 ){
4103   const char *zName;
4104   if( pItem->zDatabase==0 && (zName = pItem->zName)!=0 ){
4105     With *p;
4106     for(p=pWith; p; p=p->pOuter){
4107       int i;
4108       for(i=0; i<p->nCte; i++){
4109         if( sqlite3StrICmp(zName, p->a[i].zName)==0 ){
4110           *ppContext = p;
4111           return &p->a[i];
4112         }
4113       }
4114     }
4115   }
4116   return 0;
4117 }
4118
4119 /* The code generator maintains a stack of active WITH clauses
4120 ** with the inner-most WITH clause being at the top of the stack.
4121 **
4122 ** This routine pushes the WITH clause passed as the second argument
4123 ** onto the top of the stack. If argument bFree is true, then this
4124 ** WITH clause will never be popped from the stack. In this case it
4125 ** should be freed along with the Parse object. In other cases, when
4126 ** bFree==0, the With object will be freed along with the SELECT
4127 ** statement with which it is associated.
4128 */
4129 void sqlite3WithPush(Parse *pParse, With *pWith, u8 bFree){
4130   assert( bFree==0 || (pParse->pWith==0 && pParse->pWithToFree==0) );
4131   if( pWith ){
4132     assert( pParse->pWith!=pWith );
4133     pWith->pOuter = pParse->pWith;
4134     pParse->pWith = pWith;
4135     if( bFree ) pParse->pWithToFree = pWith;
4136   }
4137 }
4138
4139 /*
4140 ** This function checks if argument pFrom refers to a CTE declared by
4141 ** a WITH clause on the stack currently maintained by the parser. And,
4142 ** if currently processing a CTE expression, if it is a recursive
4143 ** reference to the current CTE.
4144 **
4145 ** If pFrom falls into either of the two categories above, pFrom->pTab
4146 ** and other fields are populated accordingly. The caller should check
4147 ** (pFrom->pTab!=0) to determine whether or not a successful match
4148 ** was found.
4149 **
4150 ** Whether or not a match is found, SQLITE_OK is returned if no error
4151 ** occurs. If an error does occur, an error message is stored in the
4152 ** parser and some error code other than SQLITE_OK returned.
4153 */
4154 static int withExpand(
4155   Walker *pWalker,
4156   struct SrcList_item *pFrom
4157 ){
4158   Parse *pParse = pWalker->pParse;
4159   sqlite3 *db = pParse->db;
4160   struct Cte *pCte;               /* Matched CTE (or NULL if no match) */
4161   With *pWith;                    /* WITH clause that pCte belongs to */
4162
4163   assert( pFrom->pTab==0 );
4164
4165   pCte = searchWith(pParse->pWith, pFrom, &pWith);
4166   if( pCte ){
4167     Table *pTab;
4168     ExprList *pEList;
4169     Select *pSel;
4170     Select *pLeft;                /* Left-most SELECT statement */
4171     int bMayRecursive;            /* True if compound joined by UNION [ALL] */
4172     With *pSavedWith;             /* Initial value of pParse->pWith */
4173
4174     /* If pCte->zCteErr is non-NULL at this point, then this is an illegal
4175     ** recursive reference to CTE pCte. Leave an error in pParse and return
4176     ** early. If pCte->zCteErr is NULL, then this is not a recursive reference.
4177     ** In this case, proceed.  */
4178     if( pCte->zCteErr ){
4179       sqlite3ErrorMsg(pParse, pCte->zCteErr, pCte->zName);
4180       return SQLITE_ERROR;
4181     }
4182     if( cannotBeFunction(pParse, pFrom) ) return SQLITE_ERROR;
4183
4184     assert( pFrom->pTab==0 );
4185     pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));
4186     if( pTab==0 ) return WRC_Abort;
4187     pTab->nTabRef = 1;
4188     pTab->zName = sqlite3DbStrDup(db, pCte->zName);
4189     pTab->iPKey = -1;
4190     pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );
4191     pTab->tabFlags |= TF_Ephemeral | TF_NoVisibleRowid;
4192     pFrom->pSelect = sqlite3SelectDup(db, pCte->pSelect, 0);
4193     if( db->mallocFailed ) return SQLITE_NOMEM_BKPT;
4194     assert( pFrom->pSelect );
4195
4196     /* Check if this is a recursive CTE. */
4197     pSel = pFrom->pSelect;
4198     bMayRecursive = ( pSel->op==TK_ALL || pSel->op==TK_UNION );
4199     if( bMayRecursive ){
4200       int i;
4201       SrcList *pSrc = pFrom->pSelect->pSrc;
4202       for(i=0; i<pSrc->nSrc; i++){
4203         struct SrcList_item *pItem = &pSrc->a[i];
4204         if( pItem->zDatabase==0
4205          && pItem->zName!=0
4206          && 0==sqlite3StrICmp(pItem->zName, pCte->zName)
4207           ){
4208           pItem->pTab = pTab;
4209           pItem->fg.isRecursive = 1;
4210           pTab->nTabRef++;
4211           pSel->selFlags |= SF_Recursive;
4212         }
4213       }
4214     }
4215
4216     /* Only one recursive reference is permitted. */
4217     if( pTab->nTabRef>2 ){
4218       sqlite3ErrorMsg(
4219           pParse, "multiple references to recursive table: %s", pCte->zName
4220       );
4221       return SQLITE_ERROR;
4222     }
4223     assert( pTab->nTabRef==1 ||
4224             ((pSel->selFlags&SF_Recursive) && pTab->nTabRef==2 ));
4225
4226     pCte->zCteErr = "circular reference: %s";
4227     pSavedWith = pParse->pWith;
4228     pParse->pWith = pWith;
4229     if( bMayRecursive ){
4230       Select *pPrior = pSel->pPrior;
4231       assert( pPrior->pWith==0 );
4232       pPrior->pWith = pSel->pWith;
4233       sqlite3WalkSelect(pWalker, pPrior);
4234       pPrior->pWith = 0;
4235     }else{
4236       sqlite3WalkSelect(pWalker, pSel);
4237     }
4238     pParse->pWith = pWith;
4239
4240     for(pLeft=pSel; pLeft->pPrior; pLeft=pLeft->pPrior);
4241     pEList = pLeft->pEList;
4242     if( pCte->pCols ){
4243       if( pEList && pEList->nExpr!=pCte->pCols->nExpr ){
4244         sqlite3ErrorMsg(pParse, "table %s has %d values for %d columns",
4245             pCte->zName, pEList->nExpr, pCte->pCols->nExpr
4246         );
4247         pParse->pWith = pSavedWith;
4248         return SQLITE_ERROR;
4249       }
4250       pEList = pCte->pCols;
4251     }
4252
4253     sqlite3ColumnsFromExprList(pParse, pEList, &pTab->nCol, &pTab->aCol);
4254     if( bMayRecursive ){
4255       if( pSel->selFlags & SF_Recursive ){
4256         pCte->zCteErr = "multiple recursive references: %s";
4257       }else{
4258         pCte->zCteErr = "recursive reference in a subquery: %s";
4259       }
4260       sqlite3WalkSelect(pWalker, pSel);
4261     }
4262     pCte->zCteErr = 0;
4263     pParse->pWith = pSavedWith;
4264   }
4265
4266   return SQLITE_OK;
4267 }
4268 #endif
4269
4270 #ifndef SQLITE_OMIT_CTE
4271 /*
4272 ** If the SELECT passed as the second argument has an associated WITH
4273 ** clause, pop it from the stack stored as part of the Parse object.
4274 **
4275 ** This function is used as the xSelectCallback2() callback by
4276 ** sqlite3SelectExpand() when walking a SELECT tree to resolve table
4277 ** names and other FROM clause elements.
4278 */
4279 static void selectPopWith(Walker *pWalker, Select *p){
4280   Parse *pParse = pWalker->pParse;
4281   if( OK_IF_ALWAYS_TRUE(pParse->pWith) && p->pPrior==0 ){
4282     With *pWith = findRightmost(p)->pWith;
4283     if( pWith!=0 ){
4284       assert( pParse->pWith==pWith );
4285       pParse->pWith = pWith->pOuter;
4286     }
4287   }
4288 }
4289 #else
4290 #define selectPopWith 0
4291 #endif
4292
4293 /*
4294 ** This routine is a Walker callback for "expanding" a SELECT statement.
4295 ** "Expanding" means to do the following:
4296 **
4297 **    (1)  Make sure VDBE cursor numbers have been assigned to every
4298 **         element of the FROM clause.
4299 **
4300 **    (2)  Fill in the pTabList->a[].pTab fields in the SrcList that
4301 **         defines FROM clause.  When views appear in the FROM clause,
4302 **         fill pTabList->a[].pSelect with a copy of the SELECT statement
4303 **         that implements the view.  A copy is made of the view's SELECT
4304 **         statement so that we can freely modify or delete that statement
4305 **         without worrying about messing up the persistent representation
4306 **         of the view.
4307 **
4308 **    (3)  Add terms to the WHERE clause to accommodate the NATURAL keyword
4309 **         on joins and the ON and USING clause of joins.
4310 **
4311 **    (4)  Scan the list of columns in the result set (pEList) looking
4312 **         for instances of the "*" operator or the TABLE.* operator.
4313 **         If found, expand each "*" to be every column in every table
4314 **         and TABLE.* to be every column in TABLE.
4315 **
4316 */
4317 static int selectExpander(Walker *pWalker, Select *p){
4318   Parse *pParse = pWalker->pParse;
4319   int i, j, k;
4320   SrcList *pTabList;
4321   ExprList *pEList;
4322   struct SrcList_item *pFrom;
4323   sqlite3 *db = pParse->db;
4324   Expr *pE, *pRight, *pExpr;
4325   u16 selFlags = p->selFlags;
4326   u32 elistFlags = 0;
4327
4328   p->selFlags |= SF_Expanded;
4329   if( db->mallocFailed  ){
4330     return WRC_Abort;
4331   }
4332   assert( p->pSrc!=0 );
4333   if( (selFlags & SF_Expanded)!=0 ){
4334     return WRC_Prune;
4335   }
4336   pTabList = p->pSrc;
4337   pEList = p->pEList;
4338   if( OK_IF_ALWAYS_TRUE(p->pWith) ){
4339     sqlite3WithPush(pParse, p->pWith, 0);
4340   }
4341
4342   /* Make sure cursor numbers have been assigned to all entries in
4343   ** the FROM clause of the SELECT statement.
4344   */
4345   sqlite3SrcListAssignCursors(pParse, pTabList);
4346
4347   /* Look up every table named in the FROM clause of the select.  If
4348   ** an entry of the FROM clause is a subquery instead of a table or view,
4349   ** then create a transient table structure to describe the subquery.
4350   */
4351   for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){
4352     Table *pTab;
4353     assert( pFrom->fg.isRecursive==0 || pFrom->pTab!=0 );
4354     if( pFrom->fg.isRecursive ) continue;
4355     assert( pFrom->pTab==0 );
4356 #ifndef SQLITE_OMIT_CTE
4357     if( withExpand(pWalker, pFrom) ) return WRC_Abort;
4358     if( pFrom->pTab ) {} else
4359 #endif
4360     if( pFrom->zName==0 ){
4361 #ifndef SQLITE_OMIT_SUBQUERY
4362       Select *pSel = pFrom->pSelect;
4363       /* A sub-query in the FROM clause of a SELECT */
4364       assert( pSel!=0 );
4365       assert( pFrom->pTab==0 );
4366       if( sqlite3WalkSelect(pWalker, pSel) ) return WRC_Abort;
4367       pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));
4368       if( pTab==0 ) return WRC_Abort;
4369       pTab->nTabRef = 1;
4370       if( pFrom->zAlias ){
4371         pTab->zName = sqlite3DbStrDup(db, pFrom->zAlias);
4372       }else{
4373         pTab->zName = sqlite3MPrintf(db, "subquery_%p", (void*)pTab);
4374       }
4375       while( pSel->pPrior ){ pSel = pSel->pPrior; }
4376       sqlite3ColumnsFromExprList(pParse, pSel->pEList,&pTab->nCol,&pTab->aCol);
4377       pTab->iPKey = -1;
4378       pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );
4379       pTab->tabFlags |= TF_Ephemeral;
4380 #endif
4381     }else{
4382       /* An ordinary table or view name in the FROM clause */
4383       assert( pFrom->pTab==0 );
4384       pFrom->pTab = pTab = sqlite3LocateTableItem(pParse, 0, pFrom);
4385       if( pTab==0 ) return WRC_Abort;
4386       if( pTab->nTabRef>=0xffff ){
4387         sqlite3ErrorMsg(pParse, "too many references to \"%s\": max 65535",
4388            pTab->zName);
4389         pFrom->pTab = 0;
4390         return WRC_Abort;
4391       }
4392       pTab->nTabRef++;
4393       if( !IsVirtual(pTab) && cannotBeFunction(pParse, pFrom) ){
4394         return WRC_Abort;
4395       }
4396 #if !defined(SQLITE_OMIT_VIEW) || !defined (SQLITE_OMIT_VIRTUALTABLE)
4397       if( IsVirtual(pTab) || pTab->pSelect ){
4398         i16 nCol;
4399         if( sqlite3ViewGetColumnNames(pParse, pTab) ) return WRC_Abort;
4400         assert( pFrom->pSelect==0 );
4401         pFrom->pSelect = sqlite3SelectDup(db, pTab->pSelect, 0);
4402         sqlite3SelectSetName(pFrom->pSelect, pTab->zName);
4403         nCol = pTab->nCol;
4404         pTab->nCol = -1;
4405         sqlite3WalkSelect(pWalker, pFrom->pSelect);
4406         pTab->nCol = nCol;
4407       }
4408 #endif
4409     }
4410
4411     /* Locate the index named by the INDEXED BY clause, if any. */
4412     if( sqlite3IndexedByLookup(pParse, pFrom) ){
4413       return WRC_Abort;
4414     }
4415   }
4416
4417   /* Process NATURAL keywords, and ON and USING clauses of joins.
4418   */
4419   if( db->mallocFailed || sqliteProcessJoin(pParse, p) ){
4420     return WRC_Abort;
4421   }
4422
4423   /* For every "*" that occurs in the column list, insert the names of
4424   ** all columns in all tables.  And for every TABLE.* insert the names
4425   ** of all columns in TABLE.  The parser inserted a special expression
4426   ** with the TK_ASTERISK operator for each "*" that it found in the column
4427   ** list.  The following code just has to locate the TK_ASTERISK
4428   ** expressions and expand each one to the list of all columns in
4429   ** all tables.
4430   **
4431   ** The first loop just checks to see if there are any "*" operators
4432   ** that need expanding.
4433   */
4434   for(k=0; k<pEList->nExpr; k++){
4435     pE = pEList->a[k].pExpr;
4436     if( pE->op==TK_ASTERISK ) break;
4437     assert( pE->op!=TK_DOT || pE->pRight!=0 );
4438     assert( pE->op!=TK_DOT || (pE->pLeft!=0 && pE->pLeft->op==TK_ID) );
4439     if( pE->op==TK_DOT && pE->pRight->op==TK_ASTERISK ) break;
4440     elistFlags |= pE->flags;
4441   }
4442   if( k<pEList->nExpr ){
4443     /*
4444     ** If we get here it means the result set contains one or more "*"
4445     ** operators that need to be expanded.  Loop through each expression
4446     ** in the result set and expand them one by one.
4447     */
4448     struct ExprList_item *a = pEList->a;
4449     ExprList *pNew = 0;
4450     int flags = pParse->db->flags;
4451     int longNames = (flags & SQLITE_FullColNames)!=0
4452                       && (flags & SQLITE_ShortColNames)==0;
4453
4454     for(k=0; k<pEList->nExpr; k++){
4455       pE = a[k].pExpr;
4456       elistFlags |= pE->flags;
4457       pRight = pE->pRight;
4458       assert( pE->op!=TK_DOT || pRight!=0 );
4459       if( pE->op!=TK_ASTERISK
4460        && (pE->op!=TK_DOT || pRight->op!=TK_ASTERISK)
4461       ){
4462         /* This particular expression does not need to be expanded.
4463         */
4464         pNew = sqlite3ExprListAppend(pParse, pNew, a[k].pExpr);
4465         if( pNew ){
4466           pNew->a[pNew->nExpr-1].zName = a[k].zName;
4467           pNew->a[pNew->nExpr-1].zSpan = a[k].zSpan;
4468           a[k].zName = 0;
4469           a[k].zSpan = 0;
4470         }
4471         a[k].pExpr = 0;
4472       }else{
4473         /* This expression is a "*" or a "TABLE.*" and needs to be
4474         ** expanded. */
4475         int tableSeen = 0;      /* Set to 1 when TABLE matches */
4476         char *zTName = 0;       /* text of name of TABLE */
4477         if( pE->op==TK_DOT ){
4478           assert( pE->pLeft!=0 );
4479           assert( !ExprHasProperty(pE->pLeft, EP_IntValue) );
4480           zTName = pE->pLeft->u.zToken;
4481         }
4482         for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){
4483           Table *pTab = pFrom->pTab;
4484           Select *pSub = pFrom->pSelect;
4485           char *zTabName = pFrom->zAlias;
4486           const char *zSchemaName = 0;
4487           int iDb;
4488           if( zTabName==0 ){
4489             zTabName = pTab->zName;
4490           }
4491           if( db->mallocFailed ) break;
4492           if( pSub==0 || (pSub->selFlags & SF_NestedFrom)==0 ){
4493             pSub = 0;
4494             if( zTName && sqlite3StrICmp(zTName, zTabName)!=0 ){
4495               continue;
4496             }
4497             iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
4498             zSchemaName = iDb>=0 ? db->aDb[iDb].zDbSName : "*";
4499           }
4500           for(j=0; j<pTab->nCol; j++){
4501             char *zName = pTab->aCol[j].zName;
4502             char *zColname;  /* The computed column name */
4503             char *zToFree;   /* Malloced string that needs to be freed */
4504             Token sColname;  /* Computed column name as a token */
4505
4506             assert( zName );
4507             if( zTName && pSub
4508              && sqlite3MatchSpanName(pSub->pEList->a[j].zSpan, 0, zTName, 0)==0
4509             ){
4510               continue;
4511             }
4512
4513             /* If a column is marked as 'hidden', omit it from the expanded
4514             ** result-set list unless the SELECT has the SF_IncludeHidden
4515             ** bit set.
4516             */
4517             if( (p->selFlags & SF_IncludeHidden)==0
4518              && IsHiddenColumn(&pTab->aCol[j])
4519             ){
4520               continue;
4521             }
4522             tableSeen = 1;
4523
4524             if( i>0 && zTName==0 ){
4525               if( (pFrom->fg.jointype & JT_NATURAL)!=0
4526                 && tableAndColumnIndex(pTabList, i, zName, 0, 0)
4527               ){
4528                 /* In a NATURAL join, omit the join columns from the
4529                 ** table to the right of the join */
4530                 continue;
4531               }
4532               if( sqlite3IdListIndex(pFrom->pUsing, zName)>=0 ){
4533                 /* In a join with a USING clause, omit columns in the
4534                 ** using clause from the table on the right. */
4535                 continue;
4536               }
4537             }
4538             pRight = sqlite3Expr(db, TK_ID, zName);
4539             zColname = zName;
4540             zToFree = 0;
4541             if( longNames || pTabList->nSrc>1 ){
4542               Expr *pLeft;
4543               pLeft = sqlite3Expr(db, TK_ID, zTabName);
4544               pExpr = sqlite3PExpr(pParse, TK_DOT, pLeft, pRight);
4545               if( zSchemaName ){
4546                 pLeft = sqlite3Expr(db, TK_ID, zSchemaName);
4547                 pExpr = sqlite3PExpr(pParse, TK_DOT, pLeft, pExpr);
4548               }
4549               if( longNames ){
4550                 zColname = sqlite3MPrintf(db, "%s.%s", zTabName, zName);
4551                 zToFree = zColname;
4552               }
4553             }else{
4554               pExpr = pRight;
4555             }
4556             pNew = sqlite3ExprListAppend(pParse, pNew, pExpr);
4557             sqlite3TokenInit(&sColname, zColname);
4558             sqlite3ExprListSetName(pParse, pNew, &sColname, 0);
4559             if( pNew && (p->selFlags & SF_NestedFrom)!=0 ){
4560               struct ExprList_item *pX = &pNew->a[pNew->nExpr-1];
4561               if( pSub ){
4562                 pX->zSpan = sqlite3DbStrDup(db, pSub->pEList->a[j].zSpan);
4563                 testcase( pX->zSpan==0 );
4564               }else{
4565                 pX->zSpan = sqlite3MPrintf(db, "%s.%s.%s",
4566                                            zSchemaName, zTabName, zColname);
4567                 testcase( pX->zSpan==0 );
4568               }
4569               pX->bSpanIsTab = 1;
4570             }
4571             sqlite3DbFree(db, zToFree);
4572           }
4573         }
4574         if( !tableSeen ){
4575           if( zTName ){
4576             sqlite3ErrorMsg(pParse, "no such table: %s", zTName);
4577           }else{
4578             sqlite3ErrorMsg(pParse, "no tables specified");
4579           }
4580         }
4581       }
4582     }
4583     sqlite3ExprListDelete(db, pEList);
4584     p->pEList = pNew;
4585   }
4586   if( p->pEList ){
4587     if( p->pEList->nExpr>db->aLimit[SQLITE_LIMIT_COLUMN] ){
4588       sqlite3ErrorMsg(pParse, "too many columns in result set");
4589       return WRC_Abort;
4590     }
4591     if( (elistFlags & (EP_HasFunc|EP_Subquery))!=0 ){
4592       p->selFlags |= SF_ComplexResult;
4593     }
4594   }
4595   return WRC_Continue;
4596 }
4597
4598 /*
4599 ** No-op routine for the parse-tree walker.
4600 **
4601 ** When this routine is the Walker.xExprCallback then expression trees
4602 ** are walked without any actions being taken at each node.  Presumably,
4603 ** when this routine is used for Walker.xExprCallback then
4604 ** Walker.xSelectCallback is set to do something useful for every
4605 ** subquery in the parser tree.
4606 */
4607 int sqlite3ExprWalkNoop(Walker *NotUsed, Expr *NotUsed2){
4608   UNUSED_PARAMETER2(NotUsed, NotUsed2);
4609   return WRC_Continue;
4610 }
4611
4612 /*
4613 ** No-op routine for the parse-tree walker for SELECT statements.
4614 ** subquery in the parser tree.
4615 */
4616 int sqlite3SelectWalkNoop(Walker *NotUsed, Select *NotUsed2){
4617   UNUSED_PARAMETER2(NotUsed, NotUsed2);
4618   return WRC_Continue;
4619 }
4620
4621 #if SQLITE_DEBUG
4622 /*
4623 ** Always assert.  This xSelectCallback2 implementation proves that the
4624 ** xSelectCallback2 is never invoked.
4625 */
4626 void sqlite3SelectWalkAssert2(Walker *NotUsed, Select *NotUsed2){
4627   UNUSED_PARAMETER2(NotUsed, NotUsed2);
4628   assert( 0 );
4629 }
4630 #endif
4631 /*
4632 ** This routine "expands" a SELECT statement and all of its subqueries.
4633 ** For additional information on what it means to "expand" a SELECT
4634 ** statement, see the comment on the selectExpand worker callback above.
4635 **
4636 ** Expanding a SELECT statement is the first step in processing a
4637 ** SELECT statement.  The SELECT statement must be expanded before
4638 ** name resolution is performed.
4639 **
4640 ** If anything goes wrong, an error message is written into pParse.
4641 ** The calling function can detect the problem by looking at pParse->nErr
4642 ** and/or pParse->db->mallocFailed.
4643 */
4644 static void sqlite3SelectExpand(Parse *pParse, Select *pSelect){
4645   Walker w;
4646   w.xExprCallback = sqlite3ExprWalkNoop;
4647   w.pParse = pParse;
4648   if( OK_IF_ALWAYS_TRUE(pParse->hasCompound) ){
4649     w.xSelectCallback = convertCompoundSelectToSubquery;
4650     w.xSelectCallback2 = 0;
4651     sqlite3WalkSelect(&w, pSelect);
4652   }
4653   w.xSelectCallback = selectExpander;
4654   w.xSelectCallback2 = selectPopWith;
4655   sqlite3WalkSelect(&w, pSelect);
4656 }
4657
4658
4659 #ifndef SQLITE_OMIT_SUBQUERY
4660 /*
4661 ** This is a Walker.xSelectCallback callback for the sqlite3SelectTypeInfo()
4662 ** interface.
4663 **
4664 ** For each FROM-clause subquery, add Column.zType and Column.zColl
4665 ** information to the Table structure that represents the result set
4666 ** of that subquery.
4667 **
4668 ** The Table structure that represents the result set was constructed
4669 ** by selectExpander() but the type and collation information was omitted
4670 ** at that point because identifiers had not yet been resolved.  This
4671 ** routine is called after identifier resolution.
4672 */
4673 static void selectAddSubqueryTypeInfo(Walker *pWalker, Select *p){
4674   Parse *pParse;
4675   int i;
4676   SrcList *pTabList;
4677   struct SrcList_item *pFrom;
4678
4679   assert( p->selFlags & SF_Resolved );
4680   assert( (p->selFlags & SF_HasTypeInfo)==0 );
4681   p->selFlags |= SF_HasTypeInfo;
4682   pParse = pWalker->pParse;
4683   pTabList = p->pSrc;
4684   for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){
4685     Table *pTab = pFrom->pTab;
4686     assert( pTab!=0 );
4687     if( (pTab->tabFlags & TF_Ephemeral)!=0 ){
4688       /* A sub-query in the FROM clause of a SELECT */
4689       Select *pSel = pFrom->pSelect;
4690       if( pSel ){
4691         while( pSel->pPrior ) pSel = pSel->pPrior;
4692         sqlite3SelectAddColumnTypeAndCollation(pParse, pTab, pSel);
4693       }
4694     }
4695   }
4696 }
4697 #endif
4698
4699
4700 /*
4701 ** This routine adds datatype and collating sequence information to
4702 ** the Table structures of all FROM-clause subqueries in a
4703 ** SELECT statement.
4704 **
4705 ** Use this routine after name resolution.
4706 */
4707 static void sqlite3SelectAddTypeInfo(Parse *pParse, Select *pSelect){
4708 #ifndef SQLITE_OMIT_SUBQUERY
4709   Walker w;
4710   w.xSelectCallback = sqlite3SelectWalkNoop;
4711   w.xSelectCallback2 = selectAddSubqueryTypeInfo;
4712   w.xExprCallback = sqlite3ExprWalkNoop;
4713   w.pParse = pParse;
4714   sqlite3WalkSelect(&w, pSelect);
4715 #endif
4716 }
4717
4718
4719 /*
4720 ** This routine sets up a SELECT statement for processing.  The
4721 ** following is accomplished:
4722 **
4723 **     *  VDBE Cursor numbers are assigned to all FROM-clause terms.
4724 **     *  Ephemeral Table objects are created for all FROM-clause subqueries.
4725 **     *  ON and USING clauses are shifted into WHERE statements
4726 **     *  Wildcards "*" and "TABLE.*" in result sets are expanded.
4727 **     *  Identifiers in expression are matched to tables.
4728 **
4729 ** This routine acts recursively on all subqueries within the SELECT.
4730 */
4731 void sqlite3SelectPrep(
4732   Parse *pParse,         /* The parser context */
4733   Select *p,             /* The SELECT statement being coded. */
4734   NameContext *pOuterNC  /* Name context for container */
4735 ){
4736   assert( p!=0 || pParse->db->mallocFailed );
4737   if( pParse->db->mallocFailed ) return;
4738   if( p->selFlags & SF_HasTypeInfo ) return;
4739   sqlite3SelectExpand(pParse, p);
4740   if( pParse->nErr || pParse->db->mallocFailed ) return;
4741   sqlite3ResolveSelectNames(pParse, p, pOuterNC);
4742   if( pParse->nErr || pParse->db->mallocFailed ) return;
4743   sqlite3SelectAddTypeInfo(pParse, p);
4744 }
4745
4746 /*
4747 ** Reset the aggregate accumulator.
4748 **
4749 ** The aggregate accumulator is a set of memory cells that hold
4750 ** intermediate results while calculating an aggregate.  This
4751 ** routine generates code that stores NULLs in all of those memory
4752 ** cells.
4753 */
4754 static void resetAccumulator(Parse *pParse, AggInfo *pAggInfo){
4755   Vdbe *v = pParse->pVdbe;
4756   int i;
4757   struct AggInfo_func *pFunc;
4758   int nReg = pAggInfo->nFunc + pAggInfo->nColumn;
4759   if( nReg==0 ) return;
4760 #ifdef SQLITE_DEBUG
4761   /* Verify that all AggInfo registers are within the range specified by
4762   ** AggInfo.mnReg..AggInfo.mxReg */
4763   assert( nReg==pAggInfo->mxReg-pAggInfo->mnReg+1 );
4764   for(i=0; i<pAggInfo->nColumn; i++){
4765     assert( pAggInfo->aCol[i].iMem>=pAggInfo->mnReg
4766          && pAggInfo->aCol[i].iMem<=pAggInfo->mxReg );
4767   }
4768   for(i=0; i<pAggInfo->nFunc; i++){
4769     assert( pAggInfo->aFunc[i].iMem>=pAggInfo->mnReg
4770          && pAggInfo->aFunc[i].iMem<=pAggInfo->mxReg );
4771   }
4772 #endif
4773   sqlite3VdbeAddOp3(v, OP_Null, 0, pAggInfo->mnReg, pAggInfo->mxReg);
4774   for(pFunc=pAggInfo->aFunc, i=0; i<pAggInfo->nFunc; i++, pFunc++){
4775     if( pFunc->iDistinct>=0 ){
4776       Expr *pE = pFunc->pExpr;
4777       assert( !ExprHasProperty(pE, EP_xIsSelect) );
4778       if( pE->x.pList==0 || pE->x.pList->nExpr!=1 ){
4779         sqlite3ErrorMsg(pParse, "DISTINCT aggregates must have exactly one "
4780            "argument");
4781         pFunc->iDistinct = -1;
4782       }else{
4783         KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pE->x.pList, 0, 0);
4784         sqlite3VdbeAddOp4(v, OP_OpenEphemeral, pFunc->iDistinct, 0, 0,
4785                           (char*)pKeyInfo, P4_KEYINFO);
4786       }
4787     }
4788   }
4789 }
4790
4791 /*
4792 ** Invoke the OP_AggFinalize opcode for every aggregate function
4793 ** in the AggInfo structure.
4794 */
4795 static void finalizeAggFunctions(Parse *pParse, AggInfo *pAggInfo){
4796   Vdbe *v = pParse->pVdbe;
4797   int i;
4798   struct AggInfo_func *pF;
4799   for(i=0, pF=pAggInfo->aFunc; i<pAggInfo->nFunc; i++, pF++){
4800     ExprList *pList = pF->pExpr->x.pList;
4801     assert( !ExprHasProperty(pF->pExpr, EP_xIsSelect) );
4802     sqlite3VdbeAddOp2(v, OP_AggFinal, pF->iMem, pList ? pList->nExpr : 0);
4803     sqlite3VdbeAppendP4(v, pF->pFunc, P4_FUNCDEF);
4804   }
4805 }
4806
4807 /*
4808 ** Update the accumulator memory cells for an aggregate based on
4809 ** the current cursor position.
4810 */
4811 static void updateAccumulator(Parse *pParse, AggInfo *pAggInfo){
4812   Vdbe *v = pParse->pVdbe;
4813   int i;
4814   int regHit = 0;
4815   int addrHitTest = 0;
4816   struct AggInfo_func *pF;
4817   struct AggInfo_col *pC;
4818
4819   pAggInfo->directMode = 1;
4820   for(i=0, pF=pAggInfo->aFunc; i<pAggInfo->nFunc; i++, pF++){
4821     int nArg;
4822     int addrNext = 0;
4823     int regAgg;
4824     ExprList *pList = pF->pExpr->x.pList;
4825     assert( !ExprHasProperty(pF->pExpr, EP_xIsSelect) );
4826     if( pList ){
4827       nArg = pList->nExpr;
4828       regAgg = sqlite3GetTempRange(pParse, nArg);
4829       sqlite3ExprCodeExprList(pParse, pList, regAgg, 0, SQLITE_ECEL_DUP);
4830     }else{
4831       nArg = 0;
4832       regAgg = 0;
4833     }
4834     if( pF->iDistinct>=0 ){
4835       addrNext = sqlite3VdbeMakeLabel(v);
4836       testcase( nArg==0 );  /* Error condition */
4837       testcase( nArg>1 );   /* Also an error */
4838       codeDistinct(pParse, pF->iDistinct, addrNext, 1, regAgg);
4839     }
4840     if( pF->pFunc->funcFlags & SQLITE_FUNC_NEEDCOLL ){
4841       CollSeq *pColl = 0;
4842       struct ExprList_item *pItem;
4843       int j;
4844       assert( pList!=0 );  /* pList!=0 if pF->pFunc has NEEDCOLL */
4845       for(j=0, pItem=pList->a; !pColl && j<nArg; j++, pItem++){
4846         pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);
4847       }
4848       if( !pColl ){
4849         pColl = pParse->db->pDfltColl;
4850       }
4851       if( regHit==0 && pAggInfo->nAccumulator ) regHit = ++pParse->nMem;
4852       sqlite3VdbeAddOp4(v, OP_CollSeq, regHit, 0, 0, (char *)pColl, P4_COLLSEQ);
4853     }
4854     sqlite3VdbeAddOp3(v, OP_AggStep0, 0, regAgg, pF->iMem);
4855     sqlite3VdbeAppendP4(v, pF->pFunc, P4_FUNCDEF);
4856     sqlite3VdbeChangeP5(v, (u8)nArg);
4857     sqlite3ExprCacheAffinityChange(pParse, regAgg, nArg);
4858     sqlite3ReleaseTempRange(pParse, regAgg, nArg);
4859     if( addrNext ){
4860       sqlite3VdbeResolveLabel(v, addrNext);
4861       sqlite3ExprCacheClear(pParse);
4862     }
4863   }
4864
4865   /* Before populating the accumulator registers, clear the column cache.
4866   ** Otherwise, if any of the required column values are already present
4867   ** in registers, sqlite3ExprCode() may use OP_SCopy to copy the value
4868   ** to pC->iMem. But by the time the value is used, the original register
4869   ** may have been used, invalidating the underlying buffer holding the
4870   ** text or blob value. See ticket [883034dcb5].
4871   **
4872   ** Another solution would be to change the OP_SCopy used to copy cached
4873   ** values to an OP_Copy.
4874   */
4875   if( regHit ){
4876     addrHitTest = sqlite3VdbeAddOp1(v, OP_If, regHit); VdbeCoverage(v);
4877   }
4878   sqlite3ExprCacheClear(pParse);
4879   for(i=0, pC=pAggInfo->aCol; i<pAggInfo->nAccumulator; i++, pC++){
4880     sqlite3ExprCode(pParse, pC->pExpr, pC->iMem);
4881   }
4882   pAggInfo->directMode = 0;
4883   sqlite3ExprCacheClear(pParse);
4884   if( addrHitTest ){
4885     sqlite3VdbeJumpHere(v, addrHitTest);
4886   }
4887 }
4888
4889 /*
4890 ** Add a single OP_Explain instruction to the VDBE to explain a simple
4891 ** count(*) query ("SELECT count(*) FROM pTab").
4892 */
4893 #ifndef SQLITE_OMIT_EXPLAIN
4894 static void explainSimpleCount(
4895   Parse *pParse,                  /* Parse context */
4896   Table *pTab,                    /* Table being queried */
4897   Index *pIdx                     /* Index used to optimize scan, or NULL */
4898 ){
4899   if( pParse->explain==2 ){
4900     int bCover = (pIdx!=0 && (HasRowid(pTab) || !IsPrimaryKeyIndex(pIdx)));
4901     char *zEqp = sqlite3MPrintf(pParse->db, "SCAN TABLE %s%s%s",
4902         pTab->zName,
4903         bCover ? " USING COVERING INDEX " : "",
4904         bCover ? pIdx->zName : ""
4905     );
4906     sqlite3VdbeAddOp4(
4907         pParse->pVdbe, OP_Explain, pParse->iSelectId, 0, 0, zEqp, P4_DYNAMIC
4908     );
4909   }
4910 }
4911 #else
4912 # define explainSimpleCount(a,b,c)
4913 #endif
4914
4915 /*
4916 ** Context object for havingToWhereExprCb().
4917 */
4918 struct HavingToWhereCtx {
4919   Expr **ppWhere;
4920   ExprList *pGroupBy;
4921 };
4922
4923 /*
4924 ** sqlite3WalkExpr() callback used by havingToWhere().
4925 **
4926 ** If the node passed to the callback is a TK_AND node, return
4927 ** WRC_Continue to tell sqlite3WalkExpr() to iterate through child nodes.
4928 **
4929 ** Otherwise, return WRC_Prune. In this case, also check if the
4930 ** sub-expression matches the criteria for being moved to the WHERE
4931 ** clause. If so, add it to the WHERE clause and replace the sub-expression
4932 ** within the HAVING expression with a constant "1".
4933 */
4934 static int havingToWhereExprCb(Walker *pWalker, Expr *pExpr){
4935   if( pExpr->op!=TK_AND ){
4936     struct HavingToWhereCtx *p = pWalker->u.pHavingCtx;
4937     if( sqlite3ExprIsConstantOrGroupBy(pWalker->pParse, pExpr, p->pGroupBy) ){
4938       sqlite3 *db = pWalker->pParse->db;
4939       Expr *pNew = sqlite3ExprAlloc(db, TK_INTEGER, &sqlite3IntTokens[1], 0);
4940       if( pNew ){
4941         Expr *pWhere = *(p->ppWhere);
4942         SWAP(Expr, *pNew, *pExpr);
4943         pNew = sqlite3ExprAnd(db, pWhere, pNew);
4944         *(p->ppWhere) = pNew;
4945       }
4946     }
4947     return WRC_Prune;
4948   }
4949   return WRC_Continue;
4950 }
4951
4952 /*
4953 ** Transfer eligible terms from the HAVING clause of a query, which is
4954 ** processed after grouping, to the WHERE clause, which is processed before
4955 ** grouping. For example, the query:
4956 **
4957 **   SELECT * FROM <tables> WHERE a=? GROUP BY b HAVING b=? AND c=?
4958 **
4959 ** can be rewritten as:
4960 **
4961 **   SELECT * FROM <tables> WHERE a=? AND b=? GROUP BY b HAVING c=?
4962 **
4963 ** A term of the HAVING expression is eligible for transfer if it consists
4964 ** entirely of constants and expressions that are also GROUP BY terms that
4965 ** use the "BINARY" collation sequence.
4966 */
4967 static void havingToWhere(
4968   Parse *pParse,
4969   ExprList *pGroupBy,
4970   Expr *pHaving,
4971   Expr **ppWhere
4972 ){
4973   struct HavingToWhereCtx sCtx;
4974   Walker sWalker;
4975
4976   sCtx.ppWhere = ppWhere;
4977   sCtx.pGroupBy = pGroupBy;
4978
4979   memset(&sWalker, 0, sizeof(sWalker));
4980   sWalker.pParse = pParse;
4981   sWalker.xExprCallback = havingToWhereExprCb;
4982   sWalker.u.pHavingCtx = &sCtx;
4983   sqlite3WalkExpr(&sWalker, pHaving);
4984 }
4985
4986 /*
4987 ** Check to see if the pThis entry of pTabList is a self-join of a prior view.
4988 ** If it is, then return the SrcList_item for the prior view.  If it is not,
4989 ** then return 0.
4990 */
4991 static struct SrcList_item *isSelfJoinView(
4992   SrcList *pTabList,           /* Search for self-joins in this FROM clause */
4993   struct SrcList_item *pThis   /* Search for prior reference to this subquery */
4994 ){
4995   struct SrcList_item *pItem;
4996   for(pItem = pTabList->a; pItem<pThis; pItem++){
4997     if( pItem->pSelect==0 ) continue;
4998     if( pItem->fg.viaCoroutine ) continue;
4999     if( pItem->zName==0 ) continue;
5000     if( sqlite3_stricmp(pItem->zDatabase, pThis->zDatabase)!=0 ) continue;
5001     if( sqlite3_stricmp(pItem->zName, pThis->zName)!=0 ) continue;
5002     if( sqlite3ExprCompare(0,
5003           pThis->pSelect->pWhere, pItem->pSelect->pWhere, -1)
5004     ){
5005       /* The view was modified by some other optimization such as
5006       ** pushDownWhereTerms() */
5007       continue;
5008     }
5009     return pItem;
5010   }
5011   return 0;
5012 }
5013
5014 #ifdef SQLITE_COUNTOFVIEW_OPTIMIZATION
5015 /*
5016 ** Attempt to transform a query of the form
5017 **
5018 **    SELECT count(*) FROM (SELECT x FROM t1 UNION ALL SELECT y FROM t2)
5019 **
5020 ** Into this:
5021 **
5022 **    SELECT (SELECT count(*) FROM t1)+(SELECT count(*) FROM t2)
5023 **
5024 ** The transformation only works if all of the following are true:
5025 **
5026 **   *  The subquery is a UNION ALL of two or more terms
5027 **   *  There is no WHERE or GROUP BY or HAVING clauses on the subqueries
5028 **   *  The outer query is a simple count(*)
5029 **
5030 ** Return TRUE if the optimization is undertaken.
5031 */
5032 static int countOfViewOptimization(Parse *pParse, Select *p){
5033   Select *pSub, *pPrior;
5034   Expr *pExpr;
5035   Expr *pCount;
5036   sqlite3 *db;
5037   if( (p->selFlags & SF_Aggregate)==0 ) return 0;   /* This is an aggregate */
5038   if( p->pEList->nExpr!=1 ) return 0;               /* Single result column */
5039   pExpr = p->pEList->a[0].pExpr;
5040   if( pExpr->op!=TK_AGG_FUNCTION ) return 0;        /* Result is an aggregate */
5041   if( sqlite3_stricmp(pExpr->u.zToken,"count") ) return 0;  /* Is count() */
5042   if( pExpr->x.pList!=0 ) return 0;                 /* Must be count(*) */
5043   if( p->pSrc->nSrc!=1 ) return 0;                  /* One table in FROM  */
5044   pSub = p->pSrc->a[0].pSelect;
5045   if( pSub==0 ) return 0;                           /* The FROM is a subquery */
5046   if( pSub->pPrior==0 ) return 0;                   /* Must be a compound ry */
5047   do{
5048     if( pSub->op!=TK_ALL && pSub->pPrior ) return 0;  /* Must be UNION ALL */
5049     if( pSub->pWhere ) return 0;                      /* No WHERE clause */
5050     if( pSub->selFlags & SF_Aggregate ) return 0;     /* Not an aggregate */
5051     pSub = pSub->pPrior;                              /* Repeat over compound */
5052   }while( pSub );
5053
5054   /* If we reach this point then it is OK to perform the transformation */
5055
5056   db = pParse->db;
5057   pCount = pExpr;
5058   pExpr = 0;
5059   pSub = p->pSrc->a[0].pSelect;
5060   p->pSrc->a[0].pSelect = 0;
5061   sqlite3SrcListDelete(db, p->pSrc);
5062   p->pSrc = sqlite3DbMallocZero(pParse->db, sizeof(*p->pSrc));
5063   while( pSub ){
5064     Expr *pTerm;
5065     pPrior = pSub->pPrior;
5066     pSub->pPrior = 0;
5067     pSub->pNext = 0;
5068     pSub->selFlags |= SF_Aggregate;
5069     pSub->selFlags &= ~SF_Compound;
5070     pSub->nSelectRow = 0;
5071     sqlite3ExprListDelete(db, pSub->pEList);
5072     pTerm = pPrior ? sqlite3ExprDup(db, pCount, 0) : pCount;
5073     pSub->pEList = sqlite3ExprListAppend(pParse, 0, pTerm);
5074     pTerm = sqlite3PExpr(pParse, TK_SELECT, 0, 0);
5075     sqlite3PExprAddSelect(pParse, pTerm, pSub);
5076     if( pExpr==0 ){
5077       pExpr = pTerm;
5078     }else{
5079       pExpr = sqlite3PExpr(pParse, TK_PLUS, pTerm, pExpr);
5080     }
5081     pSub = pPrior;
5082   }
5083   p->pEList->a[0].pExpr = pExpr;
5084   p->selFlags &= ~SF_Aggregate;
5085
5086 #if SELECTTRACE_ENABLED
5087   if( sqlite3SelectTrace & 0x400 ){
5088     SELECTTRACE(0x400,pParse,p,("After count-of-view optimization:\n"));
5089     sqlite3TreeViewSelect(0, p, 0);
5090   }
5091 #endif
5092   return 1;
5093 }
5094 #endif /* SQLITE_COUNTOFVIEW_OPTIMIZATION */
5095
5096 /*
5097 ** Generate code for the SELECT statement given in the p argument.
5098 **
5099 ** The results are returned according to the SelectDest structure.
5100 ** See comments in sqliteInt.h for further information.
5101 **
5102 ** This routine returns the number of errors.  If any errors are
5103 ** encountered, then an appropriate error message is left in
5104 ** pParse->zErrMsg.
5105 **
5106 ** This routine does NOT free the Select structure passed in.  The
5107 ** calling function needs to do that.
5108 */
5109 int sqlite3Select(
5110   Parse *pParse,         /* The parser context */
5111   Select *p,             /* The SELECT statement being coded. */
5112   SelectDest *pDest      /* What to do with the query results */
5113 ){
5114   int i, j;              /* Loop counters */
5115   WhereInfo *pWInfo;     /* Return from sqlite3WhereBegin() */
5116   Vdbe *v;               /* The virtual machine under construction */
5117   int isAgg;             /* True for select lists like "count(*)" */
5118   ExprList *pEList = 0;  /* List of columns to extract. */
5119   SrcList *pTabList;     /* List of tables to select from */
5120   Expr *pWhere;          /* The WHERE clause.  May be NULL */
5121   ExprList *pGroupBy;    /* The GROUP BY clause.  May be NULL */
5122   Expr *pHaving;         /* The HAVING clause.  May be NULL */
5123   int rc = 1;            /* Value to return from this function */
5124   DistinctCtx sDistinct; /* Info on how to code the DISTINCT keyword */
5125   SortCtx sSort;         /* Info on how to code the ORDER BY clause */
5126   AggInfo sAggInfo;      /* Information used by aggregate queries */
5127   int iEnd;              /* Address of the end of the query */
5128   sqlite3 *db;           /* The database connection */
5129   ExprList *pMinMaxOrderBy = 0;  /* Added ORDER BY for min/max queries */
5130   u8 minMaxFlag;                 /* Flag for min/max queries */
5131
5132 #ifndef SQLITE_OMIT_EXPLAIN
5133   int iRestoreSelectId = pParse->iSelectId;
5134   pParse->iSelectId = pParse->iNextSelectId++;
5135 #endif
5136
5137   db = pParse->db;
5138   if( p==0 || db->mallocFailed || pParse->nErr ){
5139     return 1;
5140   }
5141   if( sqlite3AuthCheck(pParse, SQLITE_SELECT, 0, 0, 0) ) return 1;
5142   memset(&sAggInfo, 0, sizeof(sAggInfo));
5143 #if SELECTTRACE_ENABLED
5144   SELECTTRACE(1,pParse,p, ("begin processing:\n"));
5145   if( sqlite3SelectTrace & 0x100 ){
5146     sqlite3TreeViewSelect(0, p, 0);
5147   }
5148 #endif
5149
5150   assert( p->pOrderBy==0 || pDest->eDest!=SRT_DistFifo );
5151   assert( p->pOrderBy==0 || pDest->eDest!=SRT_Fifo );
5152   assert( p->pOrderBy==0 || pDest->eDest!=SRT_DistQueue );
5153   assert( p->pOrderBy==0 || pDest->eDest!=SRT_Queue );
5154   if( IgnorableOrderby(pDest) ){
5155     assert(pDest->eDest==SRT_Exists || pDest->eDest==SRT_Union ||
5156            pDest->eDest==SRT_Except || pDest->eDest==SRT_Discard ||
5157            pDest->eDest==SRT_Queue  || pDest->eDest==SRT_DistFifo ||
5158            pDest->eDest==SRT_DistQueue || pDest->eDest==SRT_Fifo);
5159     /* If ORDER BY makes no difference in the output then neither does
5160     ** DISTINCT so it can be removed too. */
5161     sqlite3ExprListDelete(db, p->pOrderBy);
5162     p->pOrderBy = 0;
5163     p->selFlags &= ~SF_Distinct;
5164   }
5165   sqlite3SelectPrep(pParse, p, 0);
5166   memset(&sSort, 0, sizeof(sSort));
5167   sSort.pOrderBy = p->pOrderBy;
5168   pTabList = p->pSrc;
5169   if( pParse->nErr || db->mallocFailed ){
5170     goto select_end;
5171   }
5172   assert( p->pEList!=0 );
5173   isAgg = (p->selFlags & SF_Aggregate)!=0;
5174 #if SELECTTRACE_ENABLED
5175   if( sqlite3SelectTrace & 0x100 ){
5176     SELECTTRACE(0x100,pParse,p, ("after name resolution:\n"));
5177     sqlite3TreeViewSelect(0, p, 0);
5178   }
5179 #endif
5180
5181   /* Get a pointer the VDBE under construction, allocating a new VDBE if one
5182   ** does not already exist */
5183   v = sqlite3GetVdbe(pParse);
5184   if( v==0 ) goto select_end;
5185   if( pDest->eDest==SRT_Output ){
5186     generateColumnNames(pParse, p);
5187   }
5188
5189   /* Try to flatten subqueries in the FROM clause up into the main query
5190   */
5191 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
5192   for(i=0; !p->pPrior && i<pTabList->nSrc; i++){
5193     struct SrcList_item *pItem = &pTabList->a[i];
5194     Select *pSub = pItem->pSelect;
5195     Table *pTab = pItem->pTab;
5196     if( pSub==0 ) continue;
5197
5198     /* Catch mismatch in the declared columns of a view and the number of
5199     ** columns in the SELECT on the RHS */
5200     if( pTab->nCol!=pSub->pEList->nExpr ){
5201       sqlite3ErrorMsg(pParse, "expected %d columns for '%s' but got %d",
5202                       pTab->nCol, pTab->zName, pSub->pEList->nExpr);
5203       goto select_end;
5204     }
5205
5206     /* Do not try to flatten an aggregate subquery.
5207     **
5208     ** Flattening an aggregate subquery is only possible if the outer query
5209     ** is not a join.  But if the outer query is not a join, then the subquery
5210     ** will be implemented as a co-routine and there is no advantage to
5211     ** flattening in that case.
5212     */
5213     if( (pSub->selFlags & SF_Aggregate)!=0 ) continue;
5214     assert( pSub->pGroupBy==0 );
5215
5216     /* If the outer query contains a "complex" result set (that is,
5217     ** if the result set of the outer query uses functions or subqueries)
5218     ** and if the subquery contains an ORDER BY clause and if
5219     ** it will be implemented as a co-routine, then do not flatten.  This
5220     ** restriction allows SQL constructs like this:
5221     **
5222     **  SELECT expensive_function(x)
5223     **    FROM (SELECT x FROM tab ORDER BY y LIMIT 10);
5224     **
5225     ** The expensive_function() is only computed on the 10 rows that
5226     ** are output, rather than every row of the table.
5227     **
5228     ** The requirement that the outer query have a complex result set
5229     ** means that flattening does occur on simpler SQL constraints without
5230     ** the expensive_function() like:
5231     **
5232     **  SELECT x FROM (SELECT x FROM tab ORDER BY y LIMIT 10);
5233     */
5234     if( pSub->pOrderBy!=0
5235      && i==0
5236      && (p->selFlags & SF_ComplexResult)!=0
5237      && (pTabList->nSrc==1
5238          || (pTabList->a[1].fg.jointype&(JT_LEFT|JT_CROSS))!=0)
5239     ){
5240       continue;
5241     }
5242
5243     if( flattenSubquery(pParse, p, i, isAgg) ){
5244       /* This subquery can be absorbed into its parent. */
5245       i = -1;
5246     }
5247     pTabList = p->pSrc;
5248     if( db->mallocFailed ) goto select_end;
5249     if( !IgnorableOrderby(pDest) ){
5250       sSort.pOrderBy = p->pOrderBy;
5251     }
5252   }
5253 #endif
5254
5255 #ifndef SQLITE_OMIT_COMPOUND_SELECT
5256   /* Handle compound SELECT statements using the separate multiSelect()
5257   ** procedure.
5258   */
5259   if( p->pPrior ){
5260     rc = multiSelect(pParse, p, pDest);
5261     explainSetInteger(pParse->iSelectId, iRestoreSelectId);
5262 #if SELECTTRACE_ENABLED
5263     SELECTTRACE(1,pParse,p,("end compound-select processing\n"));
5264 #endif
5265     return rc;
5266   }
5267 #endif
5268
5269   /* For each term in the FROM clause, do two things:
5270   ** (1) Authorized unreferenced tables
5271   ** (2) Generate code for all sub-queries
5272   */
5273   for(i=0; i<pTabList->nSrc; i++){
5274     struct SrcList_item *pItem = &pTabList->a[i];
5275     SelectDest dest;
5276     Select *pSub;
5277 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
5278     const char *zSavedAuthContext;
5279 #endif
5280
5281     /* Issue SQLITE_READ authorizations with a fake column name for any
5282     ** tables that are referenced but from which no values are extracted.
5283     ** Examples of where these kinds of null SQLITE_READ authorizations
5284     ** would occur:
5285     **
5286     **     SELECT count(*) FROM t1;   -- SQLITE_READ t1.""
5287     **     SELECT t1.* FROM t1, t2;   -- SQLITE_READ t2.""
5288     **
5289     ** The fake column name is an empty string.  It is possible for a table to
5290     ** have a column named by the empty string, in which case there is no way to
5291     ** distinguish between an unreferenced table and an actual reference to the
5292     ** "" column. The original design was for the fake column name to be a NULL,
5293     ** which would be unambiguous.  But legacy authorization callbacks might
5294     ** assume the column name is non-NULL and segfault.  The use of an empty
5295     ** string for the fake column name seems safer.
5296     */
5297     if( pItem->colUsed==0 ){
5298       sqlite3AuthCheck(pParse, SQLITE_READ, pItem->zName, "", pItem->zDatabase);
5299     }
5300
5301 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
5302     /* Generate code for all sub-queries in the FROM clause
5303     */
5304     pSub = pItem->pSelect;
5305     if( pSub==0 ) continue;
5306
5307     /* Sometimes the code for a subquery will be generated more than
5308     ** once, if the subquery is part of the WHERE clause in a LEFT JOIN,
5309     ** for example.  In that case, do not regenerate the code to manifest
5310     ** a view or the co-routine to implement a view.  The first instance
5311     ** is sufficient, though the subroutine to manifest the view does need
5312     ** to be invoked again. */
5313     if( pItem->addrFillSub ){
5314       if( pItem->fg.viaCoroutine==0 ){
5315         /* The subroutine that manifests the view might be a one-time routine,
5316         ** or it might need to be rerun on each iteration because it
5317         ** encodes a correlated subquery. */
5318         testcase( sqlite3VdbeGetOp(v, pItem->addrFillSub)->opcode==OP_Once );
5319         sqlite3VdbeAddOp2(v, OP_Gosub, pItem->regReturn, pItem->addrFillSub);
5320       }
5321       continue;
5322     }
5323
5324     /* Increment Parse.nHeight by the height of the largest expression
5325     ** tree referred to by this, the parent select. The child select
5326     ** may contain expression trees of at most
5327     ** (SQLITE_MAX_EXPR_DEPTH-Parse.nHeight) height. This is a bit
5328     ** more conservative than necessary, but much easier than enforcing
5329     ** an exact limit.
5330     */
5331     pParse->nHeight += sqlite3SelectExprHeight(p);
5332
5333     /* Make copies of constant WHERE-clause terms in the outer query down
5334     ** inside the subquery.  This can help the subquery to run more efficiently.
5335     */
5336     if( (pItem->fg.jointype & JT_OUTER)==0
5337      && OptimizationEnabled(db, SQLITE_PushDown)
5338      && pushDownWhereTerms(pParse, pSub, p->pWhere, pItem->iCursor)
5339     ){
5340 #if SELECTTRACE_ENABLED
5341       if( sqlite3SelectTrace & 0x100 ){
5342         SELECTTRACE(0x100,pParse,p,("After WHERE-clause push-down:\n"));
5343         sqlite3TreeViewSelect(0, p, 0);
5344       }
5345 #endif
5346     }else{
5347       SELECTTRACE(0x100,pParse,p,("Push-down not possible\n"));
5348     }
5349
5350     zSavedAuthContext = pParse->zAuthContext;
5351     pParse->zAuthContext = pItem->zName;
5352
5353     /* Generate code to implement the subquery
5354     **
5355     ** The subquery is implemented as a co-routine if the subquery is
5356     ** guaranteed to be the outer loop (so that it does not need to be
5357     ** computed more than once)
5358     **
5359     ** TODO: Are there other reasons beside (1) to use a co-routine
5360     ** implementation?
5361     */
5362     if( i==0
5363      && (pTabList->nSrc==1
5364             || (pTabList->a[1].fg.jointype&(JT_LEFT|JT_CROSS))!=0)  /* (1) */
5365     ){
5366       /* Implement a co-routine that will return a single row of the result
5367       ** set on each invocation.
5368       */
5369       int addrTop = sqlite3VdbeCurrentAddr(v)+1;
5370
5371       pItem->regReturn = ++pParse->nMem;
5372       sqlite3VdbeAddOp3(v, OP_InitCoroutine, pItem->regReturn, 0, addrTop);
5373       VdbeComment((v, "%s", pItem->pTab->zName));
5374       pItem->addrFillSub = addrTop;
5375       sqlite3SelectDestInit(&dest, SRT_Coroutine, pItem->regReturn);
5376       explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);
5377       sqlite3Select(pParse, pSub, &dest);
5378       pItem->pTab->nRowLogEst = pSub->nSelectRow;
5379       pItem->fg.viaCoroutine = 1;
5380       pItem->regResult = dest.iSdst;
5381       sqlite3VdbeEndCoroutine(v, pItem->regReturn);
5382       sqlite3VdbeJumpHere(v, addrTop-1);
5383       sqlite3ClearTempRegCache(pParse);
5384     }else{
5385       /* Generate a subroutine that will fill an ephemeral table with
5386       ** the content of this subquery.  pItem->addrFillSub will point
5387       ** to the address of the generated subroutine.  pItem->regReturn
5388       ** is a register allocated to hold the subroutine return address
5389       */
5390       int topAddr;
5391       int onceAddr = 0;
5392       int retAddr;
5393       struct SrcList_item *pPrior;
5394
5395       assert( pItem->addrFillSub==0 );
5396       pItem->regReturn = ++pParse->nMem;
5397       topAddr = sqlite3VdbeAddOp2(v, OP_Integer, 0, pItem->regReturn);
5398       pItem->addrFillSub = topAddr+1;
5399       if( pItem->fg.isCorrelated==0 ){
5400         /* If the subquery is not correlated and if we are not inside of
5401         ** a trigger, then we only need to compute the value of the subquery
5402         ** once. */
5403         onceAddr = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
5404         VdbeComment((v, "materialize \"%s\"", pItem->pTab->zName));
5405       }else{
5406         VdbeNoopComment((v, "materialize \"%s\"", pItem->pTab->zName));
5407       }
5408       pPrior = isSelfJoinView(pTabList, pItem);
5409       if( pPrior ){
5410         sqlite3VdbeAddOp2(v, OP_OpenDup, pItem->iCursor, pPrior->iCursor);
5411         explainSetInteger(pItem->iSelectId, pPrior->iSelectId);
5412         assert( pPrior->pSelect!=0 );
5413         pSub->nSelectRow = pPrior->pSelect->nSelectRow;
5414       }else{
5415         sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor);
5416         explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);
5417         sqlite3Select(pParse, pSub, &dest);
5418       }
5419       pItem->pTab->nRowLogEst = pSub->nSelectRow;
5420       if( onceAddr ) sqlite3VdbeJumpHere(v, onceAddr);
5421       retAddr = sqlite3VdbeAddOp1(v, OP_Return, pItem->regReturn);
5422       VdbeComment((v, "end %s", pItem->pTab->zName));
5423       sqlite3VdbeChangeP1(v, topAddr, retAddr);
5424       sqlite3ClearTempRegCache(pParse);
5425     }
5426     if( db->mallocFailed ) goto select_end;
5427     pParse->nHeight -= sqlite3SelectExprHeight(p);
5428     pParse->zAuthContext = zSavedAuthContext;
5429 #endif
5430   }
5431
5432   /* Various elements of the SELECT copied into local variables for
5433   ** convenience */
5434   pEList = p->pEList;
5435   pWhere = p->pWhere;
5436   pGroupBy = p->pGroupBy;
5437   pHaving = p->pHaving;
5438   sDistinct.isTnct = (p->selFlags & SF_Distinct)!=0;
5439
5440 #if SELECTTRACE_ENABLED
5441   if( sqlite3SelectTrace & 0x400 ){
5442     SELECTTRACE(0x400,pParse,p,("After all FROM-clause analysis:\n"));
5443     sqlite3TreeViewSelect(0, p, 0);
5444   }
5445 #endif
5446
5447 #ifdef SQLITE_COUNTOFVIEW_OPTIMIZATION
5448   if( OptimizationEnabled(db, SQLITE_QueryFlattener|SQLITE_CountOfView)
5449    && countOfViewOptimization(pParse, p)
5450   ){
5451     if( db->mallocFailed ) goto select_end;
5452     pEList = p->pEList;
5453     pTabList = p->pSrc;
5454   }
5455 #endif
5456
5457   /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and
5458   ** if the select-list is the same as the ORDER BY list, then this query
5459   ** can be rewritten as a GROUP BY. In other words, this:
5460   **
5461   **     SELECT DISTINCT xyz FROM ... ORDER BY xyz
5462   **
5463   ** is transformed to:
5464   **
5465   **     SELECT xyz FROM ... GROUP BY xyz ORDER BY xyz
5466   **
5467   ** The second form is preferred as a single index (or temp-table) may be
5468   ** used for both the ORDER BY and DISTINCT processing. As originally
5469   ** written the query must use a temp-table for at least one of the ORDER
5470   ** BY and DISTINCT, and an index or separate temp-table for the other.
5471   */
5472   if( (p->selFlags & (SF_Distinct|SF_Aggregate))==SF_Distinct
5473    && sqlite3ExprListCompare(sSort.pOrderBy, pEList, -1)==0
5474   ){
5475     p->selFlags &= ~SF_Distinct;
5476     pGroupBy = p->pGroupBy = sqlite3ExprListDup(db, pEList, 0);
5477     /* Notice that even thought SF_Distinct has been cleared from p->selFlags,
5478     ** the sDistinct.isTnct is still set.  Hence, isTnct represents the
5479     ** original setting of the SF_Distinct flag, not the current setting */
5480     assert( sDistinct.isTnct );
5481
5482 #if SELECTTRACE_ENABLED
5483     if( sqlite3SelectTrace & 0x400 ){
5484       SELECTTRACE(0x400,pParse,p,("Transform DISTINCT into GROUP BY:\n"));
5485       sqlite3TreeViewSelect(0, p, 0);
5486     }
5487 #endif
5488   }
5489
5490   /* If there is an ORDER BY clause, then create an ephemeral index to
5491   ** do the sorting.  But this sorting ephemeral index might end up
5492   ** being unused if the data can be extracted in pre-sorted order.
5493   ** If that is the case, then the OP_OpenEphemeral instruction will be
5494   ** changed to an OP_Noop once we figure out that the sorting index is
5495   ** not needed.  The sSort.addrSortIndex variable is used to facilitate
5496   ** that change.
5497   */
5498   if( sSort.pOrderBy ){
5499     KeyInfo *pKeyInfo;
5500     pKeyInfo = keyInfoFromExprList(pParse, sSort.pOrderBy, 0, pEList->nExpr);
5501     sSort.iECursor = pParse->nTab++;
5502     sSort.addrSortIndex =
5503       sqlite3VdbeAddOp4(v, OP_OpenEphemeral,
5504           sSort.iECursor, sSort.pOrderBy->nExpr+1+pEList->nExpr, 0,
5505           (char*)pKeyInfo, P4_KEYINFO
5506       );
5507   }else{
5508     sSort.addrSortIndex = -1;
5509   }
5510
5511   /* If the output is destined for a temporary table, open that table.
5512   */
5513   if( pDest->eDest==SRT_EphemTab ){
5514     sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pDest->iSDParm, pEList->nExpr);
5515   }
5516
5517   /* Set the limiter.
5518   */
5519   iEnd = sqlite3VdbeMakeLabel(v);
5520   if( (p->selFlags & SF_FixedLimit)==0 ){
5521     p->nSelectRow = 320;  /* 4 billion rows */
5522   }
5523   computeLimitRegisters(pParse, p, iEnd);
5524   if( p->iLimit==0 && sSort.addrSortIndex>=0 ){
5525     sqlite3VdbeChangeOpcode(v, sSort.addrSortIndex, OP_SorterOpen);
5526     sSort.sortFlags |= SORTFLAG_UseSorter;
5527   }
5528
5529   /* Open an ephemeral index to use for the distinct set.
5530   */
5531   if( p->selFlags & SF_Distinct ){
5532     sDistinct.tabTnct = pParse->nTab++;
5533     sDistinct.addrTnct = sqlite3VdbeAddOp4(v, OP_OpenEphemeral,
5534                              sDistinct.tabTnct, 0, 0,
5535                              (char*)keyInfoFromExprList(pParse, p->pEList,0,0),
5536                              P4_KEYINFO);
5537     sqlite3VdbeChangeP5(v, BTREE_UNORDERED);
5538     sDistinct.eTnctType = WHERE_DISTINCT_UNORDERED;
5539   }else{
5540     sDistinct.eTnctType = WHERE_DISTINCT_NOOP;
5541   }
5542
5543   if( !isAgg && pGroupBy==0 ){
5544     /* No aggregate functions and no GROUP BY clause */
5545     u16 wctrlFlags = (sDistinct.isTnct ? WHERE_WANT_DISTINCT : 0);
5546     assert( WHERE_USE_LIMIT==SF_FixedLimit );
5547     wctrlFlags |= p->selFlags & SF_FixedLimit;
5548
5549     /* Begin the database scan. */
5550     SELECTTRACE(1,pParse,p,("WhereBegin\n"));
5551     pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, sSort.pOrderBy,
5552                                p->pEList, wctrlFlags, p->nSelectRow);
5553     if( pWInfo==0 ) goto select_end;
5554     if( sqlite3WhereOutputRowCount(pWInfo) < p->nSelectRow ){
5555       p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo);
5556     }
5557     if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){
5558       sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo);
5559     }
5560     if( sSort.pOrderBy ){
5561       sSort.nOBSat = sqlite3WhereIsOrdered(pWInfo);
5562       sSort.bOrderedInnerLoop = sqlite3WhereOrderedInnerLoop(pWInfo);
5563       if( sSort.nOBSat==sSort.pOrderBy->nExpr ){
5564         sSort.pOrderBy = 0;
5565       }
5566     }
5567
5568     /* If sorting index that was created by a prior OP_OpenEphemeral
5569     ** instruction ended up not being needed, then change the OP_OpenEphemeral
5570     ** into an OP_Noop.
5571     */
5572     if( sSort.addrSortIndex>=0 && sSort.pOrderBy==0 ){
5573       sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);
5574     }
5575
5576     /* Use the standard inner loop. */
5577     assert( p->pEList==pEList );
5578     selectInnerLoop(pParse, p, -1, &sSort, &sDistinct, pDest,
5579                     sqlite3WhereContinueLabel(pWInfo),
5580                     sqlite3WhereBreakLabel(pWInfo));
5581
5582     /* End the database scan loop.
5583     */
5584     sqlite3WhereEnd(pWInfo);
5585   }else{
5586     /* This case when there exist aggregate functions or a GROUP BY clause
5587     ** or both */
5588     NameContext sNC;    /* Name context for processing aggregate information */
5589     int iAMem;          /* First Mem address for storing current GROUP BY */
5590     int iBMem;          /* First Mem address for previous GROUP BY */
5591     int iUseFlag;       /* Mem address holding flag indicating that at least
5592                         ** one row of the input to the aggregator has been
5593                         ** processed */
5594     int iAbortFlag;     /* Mem address which causes query abort if positive */
5595     int groupBySort;    /* Rows come from source in GROUP BY order */
5596     int addrEnd;        /* End of processing for this SELECT */
5597     int sortPTab = 0;   /* Pseudotable used to decode sorting results */
5598     int sortOut = 0;    /* Output register from the sorter */
5599     int orderByGrp = 0; /* True if the GROUP BY and ORDER BY are the same */
5600
5601     /* Remove any and all aliases between the result set and the
5602     ** GROUP BY clause.
5603     */
5604     if( pGroupBy ){
5605       int k;                        /* Loop counter */
5606       struct ExprList_item *pItem;  /* For looping over expression in a list */
5607
5608       for(k=p->pEList->nExpr, pItem=p->pEList->a; k>0; k--, pItem++){
5609         pItem->u.x.iAlias = 0;
5610       }
5611       for(k=pGroupBy->nExpr, pItem=pGroupBy->a; k>0; k--, pItem++){
5612         pItem->u.x.iAlias = 0;
5613       }
5614       assert( 66==sqlite3LogEst(100) );
5615       if( p->nSelectRow>66 ) p->nSelectRow = 66;
5616     }else{
5617       assert( 0==sqlite3LogEst(1) );
5618       p->nSelectRow = 0;
5619     }
5620
5621     /* If there is both a GROUP BY and an ORDER BY clause and they are
5622     ** identical, then it may be possible to disable the ORDER BY clause
5623     ** on the grounds that the GROUP BY will cause elements to come out
5624     ** in the correct order. It also may not - the GROUP BY might use a
5625     ** database index that causes rows to be grouped together as required
5626     ** but not actually sorted. Either way, record the fact that the
5627     ** ORDER BY and GROUP BY clauses are the same by setting the orderByGrp
5628     ** variable.  */
5629     if( sqlite3ExprListCompare(pGroupBy, sSort.pOrderBy, -1)==0 ){
5630       orderByGrp = 1;
5631     }
5632
5633     /* Create a label to jump to when we want to abort the query */
5634     addrEnd = sqlite3VdbeMakeLabel(v);
5635
5636     /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in
5637     ** sAggInfo for all TK_AGG_FUNCTION nodes in expressions of the
5638     ** SELECT statement.
5639     */
5640     memset(&sNC, 0, sizeof(sNC));
5641     sNC.pParse = pParse;
5642     sNC.pSrcList = pTabList;
5643     sNC.pAggInfo = &sAggInfo;
5644     sAggInfo.mnReg = pParse->nMem+1;
5645     sAggInfo.nSortingColumn = pGroupBy ? pGroupBy->nExpr : 0;
5646     sAggInfo.pGroupBy = pGroupBy;
5647     sqlite3ExprAnalyzeAggList(&sNC, pEList);
5648     sqlite3ExprAnalyzeAggList(&sNC, sSort.pOrderBy);
5649     if( pHaving ){
5650       if( pGroupBy ){
5651         assert( pWhere==p->pWhere );
5652         havingToWhere(pParse, pGroupBy, pHaving, &p->pWhere);
5653         pWhere = p->pWhere;
5654       }
5655       sqlite3ExprAnalyzeAggregates(&sNC, pHaving);
5656     }
5657     sAggInfo.nAccumulator = sAggInfo.nColumn;
5658     if( p->pGroupBy==0 && p->pHaving==0 && sAggInfo.nFunc==1 ){
5659       minMaxFlag = minMaxQuery(db, sAggInfo.aFunc[0].pExpr, &pMinMaxOrderBy);
5660     }else{
5661       minMaxFlag = WHERE_ORDERBY_NORMAL;
5662     }
5663     for(i=0; i<sAggInfo.nFunc; i++){
5664       assert( !ExprHasProperty(sAggInfo.aFunc[i].pExpr, EP_xIsSelect) );
5665       sNC.ncFlags |= NC_InAggFunc;
5666       sqlite3ExprAnalyzeAggList(&sNC, sAggInfo.aFunc[i].pExpr->x.pList);
5667       sNC.ncFlags &= ~NC_InAggFunc;
5668     }
5669     sAggInfo.mxReg = pParse->nMem;
5670     if( db->mallocFailed ) goto select_end;
5671 #if SELECTTRACE_ENABLED
5672     if( sqlite3SelectTrace & 0x400 ){
5673       int ii;
5674       SELECTTRACE(0x400,pParse,p,("After aggregate analysis:\n"));
5675       sqlite3TreeViewSelect(0, p, 0);
5676       for(ii=0; ii<sAggInfo.nColumn; ii++){
5677         sqlite3DebugPrintf("agg-column[%d] iMem=%d\n",
5678             ii, sAggInfo.aCol[ii].iMem);
5679         sqlite3TreeViewExpr(0, sAggInfo.aCol[ii].pExpr, 0);
5680       }
5681       for(ii=0; ii<sAggInfo.nFunc; ii++){
5682         sqlite3DebugPrintf("agg-func[%d]: iMem=%d\n",
5683             ii, sAggInfo.aFunc[ii].iMem);
5684         sqlite3TreeViewExpr(0, sAggInfo.aFunc[ii].pExpr, 0);
5685       }
5686     }
5687 #endif
5688
5689
5690     /* Processing for aggregates with GROUP BY is very different and
5691     ** much more complex than aggregates without a GROUP BY.
5692     */
5693     if( pGroupBy ){
5694       KeyInfo *pKeyInfo;  /* Keying information for the group by clause */
5695       int addr1;          /* A-vs-B comparision jump */
5696       int addrOutputRow;  /* Start of subroutine that outputs a result row */
5697       int regOutputRow;   /* Return address register for output subroutine */
5698       int addrSetAbort;   /* Set the abort flag and return */
5699       int addrTopOfLoop;  /* Top of the input loop */
5700       int addrSortingIdx; /* The OP_OpenEphemeral for the sorting index */
5701       int addrReset;      /* Subroutine for resetting the accumulator */
5702       int regReset;       /* Return address register for reset subroutine */
5703
5704       /* If there is a GROUP BY clause we might need a sorting index to
5705       ** implement it.  Allocate that sorting index now.  If it turns out
5706       ** that we do not need it after all, the OP_SorterOpen instruction
5707       ** will be converted into a Noop.
5708       */
5709       sAggInfo.sortingIdx = pParse->nTab++;
5710       pKeyInfo = keyInfoFromExprList(pParse, pGroupBy, 0, sAggInfo.nColumn);
5711       addrSortingIdx = sqlite3VdbeAddOp4(v, OP_SorterOpen,
5712           sAggInfo.sortingIdx, sAggInfo.nSortingColumn,
5713           0, (char*)pKeyInfo, P4_KEYINFO);
5714
5715       /* Initialize memory locations used by GROUP BY aggregate processing
5716       */
5717       iUseFlag = ++pParse->nMem;
5718       iAbortFlag = ++pParse->nMem;
5719       regOutputRow = ++pParse->nMem;
5720       addrOutputRow = sqlite3VdbeMakeLabel(v);
5721       regReset = ++pParse->nMem;
5722       addrReset = sqlite3VdbeMakeLabel(v);
5723       iAMem = pParse->nMem + 1;
5724       pParse->nMem += pGroupBy->nExpr;
5725       iBMem = pParse->nMem + 1;
5726       pParse->nMem += pGroupBy->nExpr;
5727       sqlite3VdbeAddOp2(v, OP_Integer, 0, iAbortFlag);
5728       VdbeComment((v, "clear abort flag"));
5729       sqlite3VdbeAddOp2(v, OP_Integer, 0, iUseFlag);
5730       VdbeComment((v, "indicate accumulator empty"));
5731       sqlite3VdbeAddOp3(v, OP_Null, 0, iAMem, iAMem+pGroupBy->nExpr-1);
5732
5733       /* Begin a loop that will extract all source rows in GROUP BY order.
5734       ** This might involve two separate loops with an OP_Sort in between, or
5735       ** it might be a single loop that uses an index to extract information
5736       ** in the right order to begin with.
5737       */
5738       sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);
5739       SELECTTRACE(1,pParse,p,("WhereBegin\n"));
5740       pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0,
5741           WHERE_GROUPBY | (orderByGrp ? WHERE_SORTBYGROUP : 0), 0
5742       );
5743       if( pWInfo==0 ) goto select_end;
5744       if( sqlite3WhereIsOrdered(pWInfo)==pGroupBy->nExpr ){
5745         /* The optimizer is able to deliver rows in group by order so
5746         ** we do not have to sort.  The OP_OpenEphemeral table will be
5747         ** cancelled later because we still need to use the pKeyInfo
5748         */
5749         groupBySort = 0;
5750       }else{
5751         /* Rows are coming out in undetermined order.  We have to push
5752         ** each row into a sorting index, terminate the first loop,
5753         ** then loop over the sorting index in order to get the output
5754         ** in sorted order
5755         */
5756         int regBase;
5757         int regRecord;
5758         int nCol;
5759         int nGroupBy;
5760
5761         explainTempTable(pParse,
5762             (sDistinct.isTnct && (p->selFlags&SF_Distinct)==0) ?
5763                     "DISTINCT" : "GROUP BY");
5764
5765         groupBySort = 1;
5766         nGroupBy = pGroupBy->nExpr;
5767         nCol = nGroupBy;
5768         j = nGroupBy;
5769         for(i=0; i<sAggInfo.nColumn; i++){
5770           if( sAggInfo.aCol[i].iSorterColumn>=j ){
5771             nCol++;
5772             j++;
5773           }
5774         }
5775         regBase = sqlite3GetTempRange(pParse, nCol);
5776         sqlite3ExprCacheClear(pParse);
5777         sqlite3ExprCodeExprList(pParse, pGroupBy, regBase, 0, 0);
5778         j = nGroupBy;
5779         for(i=0; i<sAggInfo.nColumn; i++){
5780           struct AggInfo_col *pCol = &sAggInfo.aCol[i];
5781           if( pCol->iSorterColumn>=j ){
5782             int r1 = j + regBase;
5783             sqlite3ExprCodeGetColumnToReg(pParse,
5784                                pCol->pTab, pCol->iColumn, pCol->iTable, r1);
5785             j++;
5786           }
5787         }
5788         regRecord = sqlite3GetTempReg(pParse);
5789         sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nCol, regRecord);
5790         sqlite3VdbeAddOp2(v, OP_SorterInsert, sAggInfo.sortingIdx, regRecord);
5791         sqlite3ReleaseTempReg(pParse, regRecord);
5792         sqlite3ReleaseTempRange(pParse, regBase, nCol);
5793         sqlite3WhereEnd(pWInfo);
5794         sAggInfo.sortingIdxPTab = sortPTab = pParse->nTab++;
5795         sortOut = sqlite3GetTempReg(pParse);
5796         sqlite3VdbeAddOp3(v, OP_OpenPseudo, sortPTab, sortOut, nCol);
5797         sqlite3VdbeAddOp2(v, OP_SorterSort, sAggInfo.sortingIdx, addrEnd);
5798         VdbeComment((v, "GROUP BY sort")); VdbeCoverage(v);
5799         sAggInfo.useSortingIdx = 1;
5800         sqlite3ExprCacheClear(pParse);
5801
5802       }
5803
5804       /* If the index or temporary table used by the GROUP BY sort
5805       ** will naturally deliver rows in the order required by the ORDER BY
5806       ** clause, cancel the ephemeral table open coded earlier.
5807       **
5808       ** This is an optimization - the correct answer should result regardless.
5809       ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER to
5810       ** disable this optimization for testing purposes.  */
5811       if( orderByGrp && OptimizationEnabled(db, SQLITE_GroupByOrder)
5812        && (groupBySort || sqlite3WhereIsSorted(pWInfo))
5813       ){
5814         sSort.pOrderBy = 0;
5815         sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);
5816       }
5817
5818       /* Evaluate the current GROUP BY terms and store in b0, b1, b2...
5819       ** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth)
5820       ** Then compare the current GROUP BY terms against the GROUP BY terms
5821       ** from the previous row currently stored in a0, a1, a2...
5822       */
5823       addrTopOfLoop = sqlite3VdbeCurrentAddr(v);
5824       sqlite3ExprCacheClear(pParse);
5825       if( groupBySort ){
5826         sqlite3VdbeAddOp3(v, OP_SorterData, sAggInfo.sortingIdx,
5827                           sortOut, sortPTab);
5828       }
5829       for(j=0; j<pGroupBy->nExpr; j++){
5830         if( groupBySort ){
5831           sqlite3VdbeAddOp3(v, OP_Column, sortPTab, j, iBMem+j);
5832         }else{
5833           sAggInfo.directMode = 1;
5834           sqlite3ExprCode(pParse, pGroupBy->a[j].pExpr, iBMem+j);
5835         }
5836       }
5837       sqlite3VdbeAddOp4(v, OP_Compare, iAMem, iBMem, pGroupBy->nExpr,
5838                           (char*)sqlite3KeyInfoRef(pKeyInfo), P4_KEYINFO);
5839       addr1 = sqlite3VdbeCurrentAddr(v);
5840       sqlite3VdbeAddOp3(v, OP_Jump, addr1+1, 0, addr1+1); VdbeCoverage(v);
5841
5842       /* Generate code that runs whenever the GROUP BY changes.
5843       ** Changes in the GROUP BY are detected by the previous code
5844       ** block.  If there were no changes, this block is skipped.
5845       **
5846       ** This code copies current group by terms in b0,b1,b2,...
5847       ** over to a0,a1,a2.  It then calls the output subroutine
5848       ** and resets the aggregate accumulator registers in preparation
5849       ** for the next GROUP BY batch.
5850       */
5851       sqlite3ExprCodeMove(pParse, iBMem, iAMem, pGroupBy->nExpr);
5852       sqlite3VdbeAddOp2(v, OP_Gosub, regOutputRow, addrOutputRow);
5853       VdbeComment((v, "output one row"));
5854       sqlite3VdbeAddOp2(v, OP_IfPos, iAbortFlag, addrEnd); VdbeCoverage(v);
5855       VdbeComment((v, "check abort flag"));
5856       sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);
5857       VdbeComment((v, "reset accumulator"));
5858
5859       /* Update the aggregate accumulators based on the content of
5860       ** the current row
5861       */
5862       sqlite3VdbeJumpHere(v, addr1);
5863       updateAccumulator(pParse, &sAggInfo);
5864       sqlite3VdbeAddOp2(v, OP_Integer, 1, iUseFlag);
5865       VdbeComment((v, "indicate data in accumulator"));
5866
5867       /* End of the loop
5868       */
5869       if( groupBySort ){
5870         sqlite3VdbeAddOp2(v, OP_SorterNext, sAggInfo.sortingIdx, addrTopOfLoop);
5871         VdbeCoverage(v);
5872       }else{
5873         sqlite3WhereEnd(pWInfo);
5874         sqlite3VdbeChangeToNoop(v, addrSortingIdx);
5875       }
5876
5877       /* Output the final row of result
5878       */
5879       sqlite3VdbeAddOp2(v, OP_Gosub, regOutputRow, addrOutputRow);
5880       VdbeComment((v, "output final row"));
5881
5882       /* Jump over the subroutines
5883       */
5884       sqlite3VdbeGoto(v, addrEnd);
5885
5886       /* Generate a subroutine that outputs a single row of the result
5887       ** set.  This subroutine first looks at the iUseFlag.  If iUseFlag
5888       ** is less than or equal to zero, the subroutine is a no-op.  If
5889       ** the processing calls for the query to abort, this subroutine
5890       ** increments the iAbortFlag memory location before returning in
5891       ** order to signal the caller to abort.
5892       */
5893       addrSetAbort = sqlite3VdbeCurrentAddr(v);
5894       sqlite3VdbeAddOp2(v, OP_Integer, 1, iAbortFlag);
5895       VdbeComment((v, "set abort flag"));
5896       sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);
5897       sqlite3VdbeResolveLabel(v, addrOutputRow);
5898       addrOutputRow = sqlite3VdbeCurrentAddr(v);
5899       sqlite3VdbeAddOp2(v, OP_IfPos, iUseFlag, addrOutputRow+2);
5900       VdbeCoverage(v);
5901       VdbeComment((v, "Groupby result generator entry point"));
5902       sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);
5903       finalizeAggFunctions(pParse, &sAggInfo);
5904       sqlite3ExprIfFalse(pParse, pHaving, addrOutputRow+1, SQLITE_JUMPIFNULL);
5905       selectInnerLoop(pParse, p, -1, &sSort,
5906                       &sDistinct, pDest,
5907                       addrOutputRow+1, addrSetAbort);
5908       sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);
5909       VdbeComment((v, "end groupby result generator"));
5910
5911       /* Generate a subroutine that will reset the group-by accumulator
5912       */
5913       sqlite3VdbeResolveLabel(v, addrReset);
5914       resetAccumulator(pParse, &sAggInfo);
5915       sqlite3VdbeAddOp1(v, OP_Return, regReset);
5916
5917     } /* endif pGroupBy.  Begin aggregate queries without GROUP BY: */
5918     else {
5919 #ifndef SQLITE_OMIT_BTREECOUNT
5920       Table *pTab;
5921       if( (pTab = isSimpleCount(p, &sAggInfo))!=0 ){
5922         /* If isSimpleCount() returns a pointer to a Table structure, then
5923         ** the SQL statement is of the form:
5924         **
5925         **   SELECT count(*) FROM <tbl>
5926         **
5927         ** where the Table structure returned represents table <tbl>.
5928         **
5929         ** This statement is so common that it is optimized specially. The
5930         ** OP_Count instruction is executed either on the intkey table that
5931         ** contains the data for table <tbl> or on one of its indexes. It
5932         ** is better to execute the op on an index, as indexes are almost
5933         ** always spread across less pages than their corresponding tables.
5934         */
5935         const int iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
5936         const int iCsr = pParse->nTab++;     /* Cursor to scan b-tree */
5937         Index *pIdx;                         /* Iterator variable */
5938         KeyInfo *pKeyInfo = 0;               /* Keyinfo for scanned index */
5939         Index *pBest = 0;                    /* Best index found so far */
5940         int iRoot = pTab->tnum;              /* Root page of scanned b-tree */
5941
5942         sqlite3CodeVerifySchema(pParse, iDb);
5943         sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
5944
5945         /* Search for the index that has the lowest scan cost.
5946         **
5947         ** (2011-04-15) Do not do a full scan of an unordered index.
5948         **
5949         ** (2013-10-03) Do not count the entries in a partial index.
5950         **
5951         ** In practice the KeyInfo structure will not be used. It is only
5952         ** passed to keep OP_OpenRead happy.
5953         */
5954         if( !HasRowid(pTab) ) pBest = sqlite3PrimaryKeyIndex(pTab);
5955         for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
5956           if( pIdx->bUnordered==0
5957            && pIdx->szIdxRow<pTab->szTabRow
5958            && pIdx->pPartIdxWhere==0
5959            && (!pBest || pIdx->szIdxRow<pBest->szIdxRow)
5960           ){
5961             pBest = pIdx;
5962           }
5963         }
5964         if( pBest ){
5965           iRoot = pBest->tnum;
5966           pKeyInfo = sqlite3KeyInfoOfIndex(pParse, pBest);
5967         }
5968
5969         /* Open a read-only cursor, execute the OP_Count, close the cursor. */
5970         sqlite3VdbeAddOp4Int(v, OP_OpenRead, iCsr, iRoot, iDb, 1);
5971         if( pKeyInfo ){
5972           sqlite3VdbeChangeP4(v, -1, (char *)pKeyInfo, P4_KEYINFO);
5973         }
5974         sqlite3VdbeAddOp2(v, OP_Count, iCsr, sAggInfo.aFunc[0].iMem);
5975         sqlite3VdbeAddOp1(v, OP_Close, iCsr);
5976         explainSimpleCount(pParse, pTab, pBest);
5977       }else
5978 #endif /* SQLITE_OMIT_BTREECOUNT */
5979       {
5980         /* This case runs if the aggregate has no GROUP BY clause.  The
5981         ** processing is much simpler since there is only a single row
5982         ** of output.
5983         */
5984         assert( p->pGroupBy==0 );
5985         resetAccumulator(pParse, &sAggInfo);
5986
5987         /* If this query is a candidate for the min/max optimization, then
5988         ** minMaxFlag will have been previously set to either
5989         ** WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX and pMinMaxOrderBy will
5990         ** be an appropriate ORDER BY expression for the optimization.
5991         */
5992         assert( minMaxFlag==WHERE_ORDERBY_NORMAL || pMinMaxOrderBy!=0 );
5993         assert( pMinMaxOrderBy==0 || pMinMaxOrderBy->nExpr==1 );
5994
5995         SELECTTRACE(1,pParse,p,("WhereBegin\n"));
5996         pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pMinMaxOrderBy,
5997                                    0, minMaxFlag, 0);
5998         if( pWInfo==0 ){
5999           goto select_end;
6000         }
6001         updateAccumulator(pParse, &sAggInfo);
6002         if( sqlite3WhereIsOrdered(pWInfo)>0 ){
6003           sqlite3VdbeGoto(v, sqlite3WhereBreakLabel(pWInfo));
6004           VdbeComment((v, "%s() by index",
6005                 (minMaxFlag==WHERE_ORDERBY_MIN?"min":"max")));
6006         }
6007         sqlite3WhereEnd(pWInfo);
6008         finalizeAggFunctions(pParse, &sAggInfo);
6009       }
6010
6011       sSort.pOrderBy = 0;
6012       sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL);
6013       selectInnerLoop(pParse, p, -1, 0, 0,
6014                       pDest, addrEnd, addrEnd);
6015     }
6016     sqlite3VdbeResolveLabel(v, addrEnd);
6017
6018   } /* endif aggregate query */
6019
6020   if( sDistinct.eTnctType==WHERE_DISTINCT_UNORDERED ){
6021     explainTempTable(pParse, "DISTINCT");
6022   }
6023
6024   /* If there is an ORDER BY clause, then we need to sort the results
6025   ** and send them to the callback one by one.
6026   */
6027   if( sSort.pOrderBy ){
6028     explainTempTable(pParse,
6029                      sSort.nOBSat>0 ? "RIGHT PART OF ORDER BY":"ORDER BY");
6030     generateSortTail(pParse, p, &sSort, pEList->nExpr, pDest);
6031   }
6032
6033   /* Jump here to skip this query
6034   */
6035   sqlite3VdbeResolveLabel(v, iEnd);
6036
6037   /* The SELECT has been coded. If there is an error in the Parse structure,
6038   ** set the return code to 1. Otherwise 0. */
6039   rc = (pParse->nErr>0);
6040
6041   /* Control jumps to here if an error is encountered above, or upon
6042   ** successful coding of the SELECT.
6043   */
6044 select_end:
6045   explainSetInteger(pParse->iSelectId, iRestoreSelectId);
6046   sqlite3ExprListDelete(db, pMinMaxOrderBy);
6047   sqlite3DbFree(db, sAggInfo.aCol);
6048   sqlite3DbFree(db, sAggInfo.aFunc);
6049 #if SELECTTRACE_ENABLED
6050   SELECTTRACE(1,pParse,p,("end processing\n"));
6051 #endif
6052   return rc;
6053 }