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