/ Check-in [e605c468]
Login

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

Overview
Comment:Refactor the ORDER BY optimizer in the NGQP so that it is easier to maintain and so that it can support optimizing out GROUP BY and DISTINCT clauses.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1:e605c468e3a1163167831c4a6220825c0b5d083b
User & Date: drh 2013-06-04 12:42:29
Context
2013-06-04
12:58
Fix a display issue with EXPLAIN QUERY PLAN. check-in: ff2fa407 user: drh tags: nextgen-query-plan-exp
12:42
Refactor the ORDER BY optimizer in the NGQP so that it is easier to maintain and so that it can support optimizing out GROUP BY and DISTINCT clauses. check-in: e605c468 user: drh tags: nextgen-query-plan-exp
2013-06-03
22:08
Remove more vestiges of sqlite_query_plan from the test cases. check-in: eb27086e user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/build.c.

  2691   2691     pIndex->aSortOrder = (u8 *)(&pIndex->aiColumn[nCol]);
  2692   2692     pIndex->zName = (char *)(&pIndex->aSortOrder[nCol]);
  2693   2693     zExtra = (char *)(&pIndex->zName[nName+1]);
  2694   2694     memcpy(pIndex->zName, zName, nName+1);
  2695   2695     pIndex->pTable = pTab;
  2696   2696     pIndex->nColumn = pList->nExpr;
  2697   2697     pIndex->onError = (u8)onError;
         2698  +  pIndex->uniqNotNull = onError==OE_Abort;
  2698   2699     pIndex->autoIndex = (u8)(pName==0);
  2699   2700     pIndex->pSchema = db->aDb[iDb].pSchema;
  2700   2701     assert( sqlite3SchemaMutexHeld(db, iDb, 0) );
  2701   2702   
  2702   2703     /* Check to see if we should honor DESC requests on index columns
  2703   2704     */
  2704   2705     if( pDb->pSchema->file_format>=4 ){
................................................................................
  2749   2750       }
  2750   2751       if( !db->init.busy && !sqlite3LocateCollSeq(pParse, zColl) ){
  2751   2752         goto exit_create_index;
  2752   2753       }
  2753   2754       pIndex->azColl[i] = zColl;
  2754   2755       requestedSortOrder = pListItem->sortOrder & sortOrderMask;
  2755   2756       pIndex->aSortOrder[i] = (u8)requestedSortOrder;
         2757  +    if( pTab->aCol[j].notNull==0 ) pIndex->uniqNotNull = 0;
  2756   2758     }
  2757   2759     sqlite3DefaultRowEst(pIndex);
  2758   2760   
  2759   2761     if( pTab==pParse->pNewTable ){
  2760   2762       /* This routine has been called to create an automatic index as a
  2761   2763       ** result of a PRIMARY KEY or UNIQUE clause on a column definition, or
  2762   2764       ** a PRIMARY KEY or UNIQUE clause following the column definitions.

Changes to src/sqliteInt.h.

  1540   1540     u8 *aSortOrder;          /* for each column: True==DESC, False==ASC */
  1541   1541     char **azColl;           /* Array of collation sequence names for index */
  1542   1542     int tnum;                /* DB Page containing root of this index */
  1543   1543     u16 nColumn;             /* Number of columns in table used by this index */
  1544   1544     u8 onError;              /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */
  1545   1545     unsigned autoIndex:2;    /* 1==UNIQUE, 2==PRIMARY KEY, 0==CREATE INDEX */
  1546   1546     unsigned bUnordered:1;   /* Use this index for == or IN queries only */
         1547  +  unsigned uniqNotNull:1;  /* True if UNIQUE and NOT NULL for all columns */
  1547   1548   #ifdef SQLITE_ENABLE_STAT3
  1548   1549     int nSample;             /* Number of elements in aSample[] */
  1549   1550     tRowcnt avgEq;           /* Average nEq value for key values not in aSample */
  1550   1551     IndexSample *aSample;    /* Samples of the left-most key */
  1551   1552   #endif
  1552   1553   };
  1553   1554   
................................................................................
  1885   1886   typedef u64 Bitmask;
  1886   1887   
  1887   1888   /*
  1888   1889   ** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
  1889   1890   */
  1890   1891   #define BMS  ((int)(sizeof(Bitmask)*8))
  1891   1892   
         1893  +/*
         1894  +** A bit in a Bitmask
         1895  +*/
         1896  +#define MASKBIT(n)   (((Bitmask)1)<<(n))
         1897  +
  1892   1898   /*
  1893   1899   ** The following structure describes the FROM clause of a SELECT statement.
  1894   1900   ** Each table or subquery in the FROM clause is a separate element of
  1895   1901   ** the SrcList.a[] array.
  1896   1902   **
  1897   1903   ** With the addition of multiple database support, the following structure
  1898   1904   ** can also be used to describe a particular table such as the table that

Changes to src/where.c.

   323    323   #define WHERE_BTM_LIMIT    0x00000020  /* x>EXPR or x>=EXPR constraint */
   324    324   #define WHERE_BOTH_LIMIT   0x00000030  /* Both x>EXPR and x<EXPR */
   325    325   #define WHERE_IDX_ONLY     0x00000040  /* Use index only - omit table */
   326    326   #define WHERE_IPK          0x00000100  /* x is the INTEGER PRIMARY KEY */
   327    327   #define WHERE_INDEXED      0x00000200  /* WhereLoop.u.btree.pIndex is valid */
   328    328   #define WHERE_VIRTUALTABLE 0x00000400  /* WhereLoop.u.vtab is valid */
   329    329   #define WHERE_IN_ABLE      0x00000800  /* Able to support an IN operator */
   330         -#define WHERE_UNIQUE       0x00001000  /* Selects no more than one row */
          330  +#define WHERE_ONEROW       0x00001000  /* Selects no more than one row */
   331    331   #define WHERE_MULTI_OR     0x00002000  /* OR using multiple indices */
   332    332   #define WHERE_TEMP_INDEX   0x00004000  /* Uses an ephemeral index */
   333    333   #define WHERE_COVER_SCAN   0x00008000  /* Full scan of a covering index */
   334    334   
   335    335   /*
   336    336   ** Initialize a preallocated WhereClause structure.
   337    337   */
................................................................................
   478    478   ** iCursor is not in the set.
   479    479   */
   480    480   static Bitmask getMask(WhereMaskSet *pMaskSet, int iCursor){
   481    481     int i;
   482    482     assert( pMaskSet->n<=(int)sizeof(Bitmask)*8 );
   483    483     for(i=0; i<pMaskSet->n; i++){
   484    484       if( pMaskSet->ix[i]==iCursor ){
   485         -      return ((Bitmask)1)<<i;
          485  +      return MASKBIT(i);
   486    486       }
   487    487     }
   488    488     return 0;
   489    489   }
   490    490   
   491    491   /*
   492    492   ** Create a new mask for cursor iCursor.
................................................................................
  1834   1834     idxCols = 0;
  1835   1835     pLoop->aTerm = sqlite3DbRealloc(pParse->db, pLoop->aTerm,
  1836   1836                                     mxConstraint*sizeof(pLoop->aTerm[0]));
  1837   1837     if( pLoop->aTerm==0 ) return;
  1838   1838     for(pTerm=pWC->a; pTerm<pWCEnd && pLoop->nTerm<mxConstraint; pTerm++){
  1839   1839       if( termCanDriveIndex(pTerm, pSrc, notReady) ){
  1840   1840         int iCol = pTerm->u.leftColumn;
  1841         -      Bitmask cMask = iCol>=BMS ? ((Bitmask)1)<<(BMS-1) : ((Bitmask)1)<<iCol;
         1841  +      Bitmask cMask = iCol>=BMS ? MASKBIT(BMS-1) : MASKBIT(iCol);
  1842   1842         testcase( iCol==BMS );
  1843   1843         testcase( iCol==BMS-1 );
  1844   1844         if( (idxCols & cMask)==0 ){
  1845   1845           pLoop->aTerm[nColumn++] = pTerm;
  1846   1846           idxCols |= cMask;
  1847   1847         }
  1848   1848       }
................................................................................
  1856   1856     ** covering index.  A "covering index" is an index that contains all
  1857   1857     ** columns that are needed by the query.  With a covering index, the
  1858   1858     ** original table never needs to be accessed.  Automatic indices must
  1859   1859     ** be a covering index because the index will not be updated if the
  1860   1860     ** original table changes and the index and table cannot both be used
  1861   1861     ** if they go out of sync.
  1862   1862     */
  1863         -  extraCols = pSrc->colUsed & (~idxCols | (((Bitmask)1)<<(BMS-1)));
         1863  +  extraCols = pSrc->colUsed & (~idxCols | MASKBIT(BMS-1));
  1864   1864     mxBitCol = (pTable->nCol >= BMS-1) ? BMS-1 : pTable->nCol;
  1865   1865     testcase( pTable->nCol==BMS-1 );
  1866   1866     testcase( pTable->nCol==BMS-2 );
  1867   1867     for(i=0; i<mxBitCol; i++){
  1868         -    if( extraCols & (((Bitmask)1)<<i) ) nColumn++;
         1868  +    if( extraCols & MASKBIT(i) ) nColumn++;
  1869   1869     }
  1870         -  if( pSrc->colUsed & (((Bitmask)1)<<(BMS-1)) ){
         1870  +  if( pSrc->colUsed & MASKBIT(BMS-1) ){
  1871   1871       nColumn += pTable->nCol - BMS + 1;
  1872   1872     }
  1873   1873     pLoop->wsFlags |= WHERE_COLUMN_EQ | WHERE_IDX_ONLY;
  1874   1874   
  1875   1875     /* Construct the Index object to describe this index */
  1876   1876     nByte = sizeof(Index);
  1877   1877     nByte += nColumn*sizeof(int);     /* Index.aiColumn */
................................................................................
  1887   1887     pIdx->nColumn = nColumn;
  1888   1888     pIdx->pTable = pTable;
  1889   1889     n = 0;
  1890   1890     idxCols = 0;
  1891   1891     for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
  1892   1892       if( termCanDriveIndex(pTerm, pSrc, notReady) ){
  1893   1893         int iCol = pTerm->u.leftColumn;
  1894         -      Bitmask cMask = iCol>=BMS ? ((Bitmask)1)<<(BMS-1) : ((Bitmask)1)<<iCol;
         1894  +      Bitmask cMask = iCol>=BMS ? MASKBIT(BMS-1) : MASKBIT(iCol);
  1895   1895         if( (idxCols & cMask)==0 ){
  1896   1896           Expr *pX = pTerm->pExpr;
  1897   1897           idxCols |= cMask;
  1898   1898           pIdx->aiColumn[n] = pTerm->u.leftColumn;
  1899   1899           pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
  1900   1900           pIdx->azColl[n] = ALWAYS(pColl) ? pColl->zName : "BINARY";
  1901   1901           n++;
................................................................................
  1903   1903       }
  1904   1904     }
  1905   1905     assert( (u32)n==pLoop->u.btree.nEq );
  1906   1906   
  1907   1907     /* Add additional columns needed to make the automatic index into
  1908   1908     ** a covering index */
  1909   1909     for(i=0; i<mxBitCol; i++){
  1910         -    if( extraCols & (((Bitmask)1)<<i) ){
         1910  +    if( extraCols & MASKBIT(i) ){
  1911   1911         pIdx->aiColumn[n] = i;
  1912   1912         pIdx->azColl[n] = "BINARY";
  1913   1913         n++;
  1914   1914       }
  1915   1915     }
  1916         -  if( pSrc->colUsed & (((Bitmask)1)<<(BMS-1)) ){
         1916  +  if( pSrc->colUsed & MASKBIT(BMS-1) ){
  1917   1917       for(i=BMS-1; i<pTable->nCol; i++){
  1918   1918         pIdx->aiColumn[n] = i;
  1919   1919         pIdx->azColl[n] = "BINARY";
  1920   1920         n++;
  1921   1921       }
  1922   1922     }
  1923   1923     assert( n==nColumn );
................................................................................
  3386   3386         sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
  3387   3387         sqlite3VdbeAddOp2(v, OP_Seek, iCur, iRowidReg);  /* Deferred seek */
  3388   3388       }
  3389   3389   
  3390   3390       /* Record the instruction used to terminate the loop. Disable 
  3391   3391       ** WHERE clause terms made redundant by the index range scan.
  3392   3392       */
  3393         -    if( pLoop->wsFlags & WHERE_UNIQUE ){
         3393  +    if( pLoop->wsFlags & WHERE_ONEROW ){
  3394   3394         pLevel->op = OP_Noop;
  3395   3395       }else if( bRev ){
  3396   3396         pLevel->op = OP_Prev;
  3397   3397       }else{
  3398   3398         pLevel->op = OP_Next;
  3399   3399       }
  3400   3400       pLevel->p1 = iIdxCur;
................................................................................
  4000   4000       if( pTerm->prereqRight & pNew->maskSelf ) continue;
  4001   4001       pNew->wsFlags = savedLoop.wsFlags;
  4002   4002       pNew->u.btree.nEq = savedLoop.u.btree.nEq;
  4003   4003       pNew->nTerm = savedLoop.nTerm;
  4004   4004       if( pNew->nTerm>=pBuilder->mxTerm ) break; /* Repeated column in index */
  4005   4005       pNew->aTerm[pNew->nTerm++] = pTerm;
  4006   4006       pNew->prereq = (savedLoop.prereq | pTerm->prereqRight) & ~pNew->maskSelf;
         4007  +    pNew->rRun = rLogSize;
  4007   4008       if( pTerm->eOperator & WO_IN ){
  4008   4009         Expr *pExpr = pTerm->pExpr;
  4009   4010         pNew->wsFlags |= WHERE_COLUMN_IN;
  4010   4011         if( ExprHasProperty(pExpr, EP_xIsSelect) ){
  4011   4012           /* "x IN (SELECT ...)":  Assume the SELECT returns 25 rows */
  4012   4013           nIn = 25;
  4013   4014         }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
  4014   4015           /* "x IN (value, value, ...)" */
  4015   4016           nIn = pExpr->x.pList->nExpr;
  4016   4017         }
         4018  +      pNew->rRun *= nIn;
  4017   4019         pNew->u.btree.nEq++;
  4018   4020         pNew->nOut = (double)iRowEst * nInMul * nIn;
  4019   4021       }else if( pTerm->eOperator & (WO_EQ) ){
         4022  +      assert( (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN))!=0
         4023  +                  || nInMul==1 );
  4020   4024         pNew->wsFlags |= WHERE_COLUMN_EQ;
  4021         -      if( iCol<0 
         4025  +      if( iCol<0  
  4022   4026          || (pProbe->onError==OE_Abort && nInMul==1
  4023   4027              && pNew->u.btree.nEq==pProbe->nColumn-1)
  4024   4028         ){
  4025         -        pNew->wsFlags |= WHERE_UNIQUE;
         4029  +        testcase( pNew->wsFlags & WHERE_COLUMN_IN );
         4030  +        pNew->wsFlags |= WHERE_ONEROW;
  4026   4031         }
  4027   4032         pNew->u.btree.nEq++;
  4028   4033         pNew->nOut = (double)iRowEst * nInMul;
  4029   4034       }else if( pTerm->eOperator & (WO_ISNULL) ){
  4030   4035         pNew->wsFlags |= WHERE_COLUMN_NULL;
  4031   4036         pNew->u.btree.nEq++;
  4032         -      pNew->nOut = (double)iRowEst * nInMul;
         4037  +      nIn = 2;  /* Assume IS NULL matches two rows */
         4038  +      pNew->nOut = (double)iRowEst * nInMul * nIn;
  4033   4039       }else if( pTerm->eOperator & (WO_GT|WO_GE) ){
  4034   4040         pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_BTM_LIMIT;
  4035   4041         pBtm = pTerm;
  4036   4042         pTop = 0;
  4037   4043       }else if( pTerm->eOperator & (WO_LT|WO_LE) ){
  4038   4044         pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT;
  4039   4045         pTop = pTerm;
  4040   4046         pBtm = (pNew->wsFlags & WHERE_BTM_LIMIT)!=0 ?
  4041   4047                        pNew->aTerm[pNew->nTerm-2] : 0;
  4042   4048       }
  4043         -    pNew->rRun = rLogSize*nIn;  /* Cost for nIn binary searches */
  4044   4049       if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
  4045   4050         /* Adjust nOut and rRun for STAT3 range values */
  4046   4051         double rDiv;
  4047   4052         whereRangeScanEst(pBuilder->pParse, pProbe, pNew->u.btree.nEq,
  4048   4053                           pBtm, pTop, &rDiv);
  4049   4054         pNew->nOut = savedLoop.nOut/rDiv;
  4050   4055       }
................................................................................
  4214   4219         if( rc ) break;
  4215   4220       }else{
  4216   4221         Bitmask m = pSrc->colUsed;
  4217   4222         int j;
  4218   4223         for(j=pProbe->nColumn-1; j>=0; j--){
  4219   4224           int x = pProbe->aiColumn[j];
  4220   4225           if( x<BMS-1 ){
  4221         -          m &= ~(((Bitmask)1)<<x);
         4226  +          m &= ~MASKBIT(x);
  4222   4227           }
  4223   4228         }
  4224   4229         pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED;
  4225   4230   
  4226   4231         /* Full scan via index */
  4227   4232         if( (m==0 || b)
  4228   4233          && pProbe->bUnordered==0
................................................................................
  4525   4530   whereLoopAddAll_end:
  4526   4531     whereLoopDelete(db, pBuilder->pNew);
  4527   4532     pBuilder->pNew = 0;
  4528   4533     return rc;
  4529   4534   }
  4530   4535   
  4531   4536   /*
  4532         -** Examine a WherePath (with the addition of the extra WhereLoop of the 4th
         4537  +** Examine a WherePath (with the addition of the extra WhereLoop of the 5th
  4533   4538   ** parameters) to see if it outputs rows in the requested ORDER BY
  4534   4539   ** (or GROUP BY) without requiring a separate source operation.  Return:
  4535   4540   ** 
  4536   4541   **    0:  ORDER BY is not satisfied.  Sorting required
  4537   4542   **    1:  ORDER BY is satisfied.      Omit sorting
  4538   4543   **   -1:  Unknown at this time
  4539   4544   **
  4540   4545   */
  4541   4546   static int wherePathSatisfiesOrderBy(
  4542   4547     WhereInfo *pWInfo,    /* The WHERE clause */
  4543   4548     WherePath *pPath,     /* The WherePath to check */
  4544   4549     int nLoop,            /* Number of entries in pPath->aLoop[] */
  4545         -  int isLastLoop,       /* True for the very last loop */
         4550  +  int isLastLoop,       /* True if pLast is the inner-most loop */
  4546   4551     WhereLoop *pLast,     /* Add this WhereLoop to the end of pPath->aLoop[] */
  4547   4552     Bitmask *pRevMask     /* Mask of WhereLoops to run in reverse order */
  4548   4553   ){
  4549   4554     u8 revSet;            /* True if rev is known */
  4550   4555     u8 rev;               /* Composite sort order */
  4551   4556     u8 revIdx;            /* Index sort order */
  4552         -  u8 isOneRow;          /* Current WhereLoop is a one-row loop */
  4553         -  u8 requireOneRow = 0; /* All subsequent loops must be one-row */
  4554         -  u8 isUniqueIdx;       /* Current WhereLoop uses a unique index */
  4555         -  u16 nColumn;
  4556         -  u16 nOrderBy;
  4557         -  int i, j;
  4558         -  int nUsed = 0;
  4559         -  int iCur;
  4560         -  int iColumn;
  4561         -  WhereLoop *pLoop;
  4562         -  ExprList *pOrderBy = pWInfo->pOrderBy;
  4563         -  Expr *pOBExpr;
  4564         -  CollSeq *pColl;
  4565         -  Index *pIndex;
  4566         -  sqlite3 *db = pWInfo->pParse->db;
  4567         -  Bitmask revMask = 0;
         4557  +  u8 isWellOrdered;     /* All WhereLoops are well-ordered so far */
         4558  +  u16 nColumn;          /* Number of columns in pIndex */
         4559  +  u16 nOrderBy;         /* Number terms in the ORDER BY clause */
         4560  +  int iLoop;            /* Index of WhereLoop in pPath being processed */
         4561  +  int i, j;             /* Loop counters */
         4562  +  int iCur;             /* Cursor number for current WhereLoop */
         4563  +  int iColumn;          /* A column number within table iCur */
         4564  +  WhereLoop *pLoop;     /* Current WhereLoop being processed. */
         4565  +  ExprList *pOrderBy = pWInfo->pOrderBy;  /* the ORDER BY clause */
         4566  +  WhereTerm *pTerm;     /* A single term of the WHERE clause */
         4567  +  Expr *pOBExpr;        /* An expression from the ORDER BY clause */
         4568  +  CollSeq *pColl;       /* COLLATE function from an ORDER BY clause term */
         4569  +  Index *pIndex;        /* The index associated with pLoop */
         4570  +  sqlite3 *db = pWInfo->pParse->db;  /* Database connection */
         4571  +  Bitmask obSat = 0;    /* Mask of ORDER BY terms satisfied so far */
         4572  +  Bitmask obDone;       /* Mask of all ORDER BY terms */
         4573  +  Bitmask orderedMask;  /* Mask of all well-ordered loops */
         4574  +  WhereMaskSet *pMaskSet; /* WhereMaskSet object for this where clause */
         4575  +  
  4568   4576   
  4569   4577     /*
  4570         -  ** We say the WhereLoop is "one-row" if all of the following are true:
         4578  +  ** We say the WhereLoop is "one-row" if it generates no more than one
         4579  +  ** row of output.  A WhereLoop is one-row if all of the following are true:
  4571   4580     **  (a) All index columns match with WHERE_COLUMN_EQ.
  4572   4581     **  (b) The index is unique
  4573         -  **
  4574         -  ** General rules:  (not an algorithm!)
         4582  +  ** Any WhereLoop with an WHERE_COLUMN_EQ constraint on the rowid is one-row.
         4583  +  ** Every one-row WhereLoop will have the WHERE_ONEROW bit set in wsFlags.
  4575   4584     **
  4576         -  **  (1) If the current WhereLoop is one-row, then match over any and all
  4577         -  **      ORDER BY terms for the current WhereLoop and proceed to the next
  4578         -  **      WhereLoop.
  4579         -  **
  4580         -  **  (2) If the current WhereLoop is not one-row, then all subsequent
  4581         -  **      WhereLoops must be one-row.
  4582         -  **
  4583         -  **  (3) Optionally match any ORDER BY terms against the first nEq columns
  4584         -  **      of the index.
  4585         -  **
  4586         -  **  (4) Index columns past nEq must match ORDER BY terms one-for-one.
  4587         -  **
  4588         -  **  (5) If all columns of a UNIQUE index have been matched against ORDER BY
  4589         -  **      terms, then any subsequent entries in the ORDER BY clause against the
  4590         -  **      same table can be skipped.
         4585  +  ** We say the WhereLoop is "well-ordered" if
         4586  +  **  (i)  it satisfies at least one term of the ORDER BY clause, and
         4587  +  **  (ii) every row output is distinct over the terms that match the
         4588  +  **       ORDER BY clause.
         4589  +  ** Every one-row WhereLoop is automatically well-ordered, even if it
         4590  +  ** does not match any terms of the ORDER BY clause.
         4591  +  ** For condition (ii), be mindful that a UNIQUE column can have multiple
         4592  +  ** rows that are NULL and so it not necessarily distinct.  The column
         4593  +  ** must be UNIQUE and NOT NULL. in order to be well-ordered.
  4591   4594     */
  4592   4595   
  4593   4596     assert( pOrderBy!=0 );
  4594   4597   
  4595   4598     /* Sortability of virtual tables is determined by the xBestIndex method
  4596   4599     ** of the virtual table itself */
  4597   4600     if( pLast->wsFlags & WHERE_VIRTUALTABLE ){
  4598         -    assert( nLoop==0 );
         4601  +    testcase( nLoop>0 );  /* True when outer loops are one-row and match 
         4602  +                          ** no ORDER BY terms */
  4599   4603       return pLast->u.vtab.isOrdered;
  4600   4604     }
         4605  +  if( nLoop && OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return 0;
  4601   4606   
  4602         -  /* Sorting is always required if any term of the ORDER BY is not a 
  4603         -  ** column reference */
  4604   4607     nOrderBy = pOrderBy->nExpr;
  4605         -#if 0
  4606         -  for(i=0; i<nOrderBy; i++){
  4607         -    pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
  4608         -    if( pOBExpr->op!=TK_COLUMN ) return 0;
  4609         -  }
  4610         -#endif
  4611         -    
  4612         -  for(i=0; i<=nLoop && nUsed<nOrderBy; i++){
  4613         -    pLoop = i<nLoop ? pPath->aLoop[i] : pLast;
         4608  +  if( nOrderBy>60 ) return 0;
         4609  +  isWellOrdered = 1;
         4610  +  obDone = MASKBIT(nOrderBy)-1;
         4611  +  orderedMask = 0;
         4612  +  pMaskSet = pWInfo->pWC->pMaskSet;
         4613  +  for(iLoop=0; isWellOrdered && obSat<obDone && iLoop<=nLoop; iLoop++){
         4614  +    pLoop = iLoop<nLoop ? pPath->aLoop[iLoop] : pLast;
  4614   4615       assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
  4615         -    isOneRow = isUniqueIdx = 1;
  4616         -    if( pLoop->wsFlags & WHERE_IPK ){
  4617         -      if( (pLoop->wsFlags & WHERE_COLUMN_IN)!=0 ) isOneRow = 0;
  4618         -      if( pLoop->u.btree.nEq!=1 ) isOneRow = 0;
  4619         -      pIndex = 0;
  4620         -      nColumn = 0;
  4621         -    }else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){
  4622         -      return 0;
  4623         -    }else{
  4624         -      nColumn = pIndex->nColumn;
  4625         -      if( pIndex->onError==OE_None ){
  4626         -        isOneRow = isUniqueIdx = 0;
  4627         -      }else if( (pLoop->wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_RANGE
  4628         -                                   |WHERE_COLUMN_NULL))!=0 ){
  4629         -        isOneRow = 0;
  4630         -      }else if( pLoop->u.btree.nEq < pIndex->nColumn ){
  4631         -        isOneRow = 0;
         4616  +    iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;
         4617  +    if( (pLoop->wsFlags & WHERE_ONEROW)==0 ){
         4618  +      if( pLoop->wsFlags & WHERE_IPK ){
         4619  +        pIndex = 0;
         4620  +        nColumn = 0;
         4621  +      }else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){
         4622  +        return 0;
         4623  +      }else{
         4624  +        nColumn = pIndex->nColumn;
         4625  +      }
         4626  +
         4627  +      /* For every term of the index that is constrained by == or IS NULL
         4628  +      ** mark off corresponding ORDER BY terms wherever they occur
         4629  +      ** in the ORDER BY clause.
         4630  +      */
         4631  +      for(i=0; i<pLoop->u.btree.nEq; i++){
         4632  +        pTerm = pLoop->aTerm[i];
         4633  +        if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))==0 ) continue;
         4634  +        iColumn = pTerm->u.leftColumn;
         4635  +        for(j=0; j<nOrderBy; j++){
         4636  +          if( MASKBIT(j) & obSat ) continue;
         4637  +          pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[j].pExpr);
         4638  +          if( pOBExpr->op!=TK_COLUMN ) continue;
         4639  +          if( pOBExpr->iTable!=iCur ) continue;
         4640  +          if( pOBExpr->iColumn!=iColumn ) continue;
         4641  +          if( iColumn>=0 ){
         4642  +            pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[j].pExpr);
         4643  +            if( !pColl ) pColl = db->pDfltColl;
         4644  +            if( sqlite3StrICmp(pColl->zName, pIndex->azColl[i])!=0 ) continue;
         4645  +          }
         4646  +          obSat |= MASKBIT(j);
         4647  +        }
         4648  +        if( obSat==obDone ) return 1;
  4632   4649         }
  4633         -    }
  4634         -    if( !isOneRow && requireOneRow ) return 0;
  4635         -    requireOneRow = !isOneRow;
  4636         -    iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;
  4637         -    j = 0;
  4638         -    revSet = rev = 0;
  4639         -    for(j=0; j<=nColumn && nUsed<nOrderBy; j++, nUsed++){
  4640         -      int skipable;
  4641         -      pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[nUsed].pExpr);
  4642         -      if( pOBExpr->op!=TK_COLUMN ) return 0;
  4643         -      if( pOBExpr->iTable!=iCur ) break;
  4644         -      if( isOneRow ){ j--; continue; }
  4645         -      if( j<nColumn ){
  4646         -        /* Normal index columns */
  4647         -        iColumn = pIndex->aiColumn[j];
  4648         -        revIdx = pIndex->aSortOrder[j];
  4649         -        if( iColumn==pIndex->pTable->iPKey ) iColumn = -1;
  4650         -      }else{
  4651         -        /* The ROWID column at the end */
  4652         -        iColumn = -1;
  4653         -        revIdx = 0;
  4654         -      }
  4655         -      skipable = j<pLoop->u.btree.nEq && pLoop->aTerm[j]->eOperator!=WO_IN;
  4656         -      if( pOBExpr->iColumn!=iColumn ){
  4657         -        if( skipable ){ nUsed--; continue; }
  4658         -        return 0;
  4659         -      }
  4660         -      if( iColumn>=0 ){
  4661         -        pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[nUsed].pExpr);
  4662         -        if( !pColl ) pColl = db->pDfltColl;
  4663         -        if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ){
  4664         -          return 0;
         4650  +
         4651  +      /* Loop through all columns of the index and deal with the ones
         4652  +      ** that are not constrained by == or IN.
         4653  +      */
         4654  +      rev = revSet = 0;
         4655  +      for(j=0; j<=nColumn; j++){
         4656  +        u8 bOnce;   /* True to run the ORDER BY search loop */
         4657  +
         4658  +        if( j<pLoop->u.btree.nEq
         4659  +         && (pLoop->aTerm[j]->eOperator & (WO_EQ|WO_ISNULL))!=0
         4660  +        ){
         4661  +          continue;  /* Skip == and IS NULL terms already processed */
         4662  +        }
         4663  +
         4664  +        /* Get the column number in the table and sort order for the
         4665  +        ** j-th column of the index for this WhereLoop
         4666  +        */
         4667  +        if( j<nColumn ){
         4668  +          /* Normal index columns */
         4669  +          iColumn = pIndex->aiColumn[j];
         4670  +          revIdx = pIndex->aSortOrder[j];
         4671  +          if( iColumn==pIndex->pTable->iPKey ) iColumn = -1;
         4672  +        }else{
         4673  +          /* The ROWID column at the end */
         4674  +          iColumn = -1;
         4675  +          revIdx = 0;
         4676  +        }
         4677  +
         4678  +        /* An unconstrained column that might be NULL means that this
         4679  +        ** WhereLoop is not well-ordered 
         4680  +        */
         4681  +        if( iColumn>=0
         4682  +         && j>=pLoop->u.btree.nEq
         4683  +         && pIndex->pTable->aCol[iColumn].notNull==0
         4684  +        ){
         4685  +          isWellOrdered = 0;
         4686  +        }
         4687  +
         4688  +        /* Find the ORDER BY term that corresponds to the j-th column
         4689  +        ** of the index and and mark that ORDER BY term off 
         4690  +        */
         4691  +        bOnce = 1;
         4692  +        for(i=0; bOnce && i<nOrderBy; i++){
         4693  +          if( MASKBIT(i) & obSat ) continue;
         4694  +          pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
         4695  +          if( pOBExpr->op!=TK_COLUMN ) continue;
         4696  +          if( (pWInfo->wctrlFlags & WHERE_GROUPBY)==0 ) bOnce = 0;
         4697  +          if( pOBExpr->iTable!=iCur ) continue;
         4698  +          if( pOBExpr->iColumn!=iColumn ) continue;
         4699  +          if( iColumn>=0 ){
         4700  +            pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);
         4701  +            if( !pColl ) pColl = db->pDfltColl;
         4702  +            if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) continue;
         4703  +          }
         4704  +          bOnce = 1;
         4705  +          break;
         4706  +        }
         4707  +        if( bOnce && i<nOrderBy ){
         4708  +          if( iColumn<0 ) isWellOrdered = 1;
         4709  +          obSat |= MASKBIT(i);
         4710  +          if( (pWInfo->wctrlFlags & WHERE_GROUPBY)==0 ){
         4711  +            /* If we have an ORDER BY clause, we must match the next available
         4712  +            ** column of the ORDER BY */
         4713  +            if( revSet ){
         4714  +              if( (rev ^ revIdx)!=pOrderBy->a[i].sortOrder ) return 0;
         4715  +            }else{
         4716  +              rev = revIdx ^ pOrderBy->a[i].sortOrder;
         4717  +              if( rev ) *pRevMask |= MASKBIT(iLoop);
         4718  +              revSet = 1;
         4719  +            }
         4720  +          }
         4721  +        }else{
         4722  +          /* No match found */
         4723  +          if( j<nColumn || pIndex==0 || pIndex->onError!=OE_Abort ){
         4724  +            isWellOrdered = 0;
         4725  +          }
         4726  +          break;
         4727  +        }
         4728  +      } /* end Loop over all index columns */
         4729  +    } /* end-if not one-row */
         4730  +
         4731  +    /* Mark off any other ORDER BY terms that reference pLoop */
         4732  +    if( isWellOrdered ){
         4733  +      orderedMask |= pLoop->maskSelf;
         4734  +      for(i=0; i<nOrderBy; i++){
         4735  +        Expr *p;
         4736  +        if( MASKBIT(i) & obSat ) continue;
         4737  +        p = pOrderBy->a[i].pExpr;
         4738  +        if( (exprTableUsage(pMaskSet, p)&~orderedMask)==0 ){
         4739  +          obSat |= MASKBIT(i);
  4665   4740           }
  4666   4741         }
  4667         -      if( !skipable ){
  4668         -        if( revSet ){
  4669         -          if( (rev ^ revIdx)!=pOrderBy->a[nUsed].sortOrder ) return 0;
  4670         -        }else{
  4671         -          rev = revIdx ^ pOrderBy->a[nUsed].sortOrder;
  4672         -          revSet = 1;
  4673         -        }
  4674         -      }
  4675         -      if( j>=nColumn-1 && isUniqueIdx ){
  4676         -        if( isLastLoop && i==nLoop ) break;
  4677         -        j--;
  4678         -        isOneRow = 1;
  4679         -      }
  4680   4742       }
  4681         -    if( rev ) revMask |= ((Bitmask)1)<<i;
  4682   4743     }
  4683         -  if( isLastLoop || nUsed==nOrderBy ){
  4684         -    *pRevMask = revMask;
  4685         -    return 1;
  4686         -  }
         4744  +  if( obSat==obDone ) return 1;
         4745  +  if( !isWellOrdered ) return 0;
         4746  +  if( isLastLoop ) return 1;
  4687   4747     return -1;
  4688   4748   }
  4689   4749   
  4690   4750   #ifdef WHERETRACE_ENABLED
  4691   4751   /* For debugging use only: */
  4692   4752   static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){
  4693   4753     static char zName[65];
................................................................................
  5212   5272   #if 0  /* FIXME: Add this back in? */
  5213   5273     /* If the caller is an UPDATE or DELETE statement that is requesting
  5214   5274     ** to use a one-pass algorithm, determine if this is appropriate.
  5215   5275     ** The one-pass algorithm only works if the WHERE clause constraints
  5216   5276     ** the statement to update a single row.
  5217   5277     */
  5218   5278     assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
  5219         -  if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){
         5279  +  if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_ONEROW)!=0 ){
  5220   5280       pWInfo->okOnePass = 1;
  5221   5281       pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY;
  5222   5282     }
  5223   5283   #endif
  5224   5284   
  5225   5285     /* Open all tables in the pTabList and any indices selected for
  5226   5286     ** searching those tables.

Changes to test/tkt-2a5629202f.test.

    42     42   } {null/four null/three a/one b/two}
    43     43   
    44     44   do_execsql_test 1.3 {
    45     45     CREATE UNIQUE INDEX i1 ON t8(b);
    46     46     SELECT coalesce(b, 'null') || '/' || c FROM t8 x ORDER BY x.b, x.c
    47     47   } {null/four null/three a/one b/two}
    48     48   
           49  +do_execsql_test 1.4 {
           50  +  DROP INDEX t8;
           51  +  CREATE UNIQUE INDEX i1 ON t8(b, c);
           52  +  SELECT coalesce(b, 'null') || '/' || c FROM t8 x ORDER BY x.b, x.c
           53  +} {null/four null/three a/one b/two}
           54  +
    49     55   #-------------------------------------------------------------------------
    50     56   #
    51     57   
    52     58   do_execsql_test 2.1 {
    53     59     CREATE TABLE t2(a, b NOT NULL, c);
    54     60     CREATE UNIQUE INDEX t2ab ON t2(a, b);
    55     61     CREATE UNIQUE INDEX t2ba ON t2(b, a);
................................................................................
    64     70   } {sort}
    65     71   
    66     72   do_test 2.4 {
    67     73     cksort { SELECT * FROM t2 WHERE a IS NULL ORDER BY a, b, c }
    68     74   } {sort}
    69     75   
    70     76   finish_test
    71         -