/ Check-in [8f1709ff]
Login

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

Overview
Comment:Improved ORDER BY optimization for WITHOUT ROWID tables.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | omit-rowid
Files: files | file ages | folders
SHA1: 8f1709ff2d52d5ceca3da6a2a4e06da204d9e65a
User & Date: drh 2013-11-06 12:56:04
Context
2013-11-06
14:05
Minor optimization to the OP_Halt opcode. check-in: d70c7881 user: drh tags: omit-rowid
12:56
Improved ORDER BY optimization for WITHOUT ROWID tables. check-in: 8f1709ff user: drh tags: omit-rowid
12:05
Disable the OR optimization for WITHOUT ROWID tables, since it relies on the use of rowids. check-in: 6055dad2 user: drh tags: omit-rowid
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

  5020   5020   ){
  5021   5021     u8 revSet;            /* True if rev is known */
  5022   5022     u8 rev;               /* Composite sort order */
  5023   5023     u8 revIdx;            /* Index sort order */
  5024   5024     u8 isOrderDistinct;   /* All prior WhereLoops are order-distinct */
  5025   5025     u8 distinctColumns;   /* True if the loop has UNIQUE NOT NULL columns */
  5026   5026     u8 isMatch;           /* iColumn matches a term of the ORDER BY clause */
  5027         -  u16 nKeyCol;          /* Number of columns in pIndex */
         5027  +  u16 nKeyCol;          /* Number of key columns in pIndex */
         5028  +  u16 nColumn;          /* Total number of ordered columns in the index */
  5028   5029     u16 nOrderBy;         /* Number terms in the ORDER BY clause */
  5029   5030     int iLoop;            /* Index of WhereLoop in pPath being processed */
  5030   5031     int i, j;             /* Loop counters */
  5031   5032     int iCur;             /* Cursor number for current WhereLoop */
  5032   5033     int iColumn;          /* A column number within table iCur */
  5033   5034     WhereLoop *pLoop = 0; /* Current WhereLoop being processed. */
  5034   5035     WhereTerm *pTerm;     /* A single term of the WHERE clause */
................................................................................
  5113   5114         obSat |= MASKBIT(i);
  5114   5115       }
  5115   5116   
  5116   5117       if( (pLoop->wsFlags & WHERE_ONEROW)==0 ){
  5117   5118         if( pLoop->wsFlags & WHERE_IPK ){
  5118   5119           pIndex = 0;
  5119   5120           nKeyCol = 0;
         5121  +        nColumn = 1;
  5120   5122         }else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){
  5121   5123           return 0;
  5122   5124         }else{
  5123   5125           nKeyCol = pIndex->nKeyCol;
         5126  +        nColumn = pIndex->nColumn;
         5127  +        assert( nColumn==nKeyCol+1 || !HasRowid(pIndex->pTable) );
         5128  +        assert( pIndex->aiColumn[nColumn-1]==(-1) || !HasRowid(pIndex->pTable));
  5124   5129           isOrderDistinct = pIndex->onError!=OE_None;
  5125   5130         }
  5126   5131   
  5127   5132         /* Loop through all columns of the index and deal with the ones
  5128   5133         ** that are not constrained by == or IN.
  5129   5134         */
  5130   5135         rev = revSet = 0;
  5131   5136         distinctColumns = 0;
  5132         -      for(j=0; j<=nKeyCol; j++){
         5137  +      for(j=0; j<nColumn; j++){
  5133   5138           u8 bOnce;   /* True to run the ORDER BY search loop */
  5134   5139   
  5135   5140           /* Skip over == and IS NULL terms */
  5136   5141           if( j<pLoop->u.btree.nEq
  5137   5142            && ((i = pLoop->aLTerm[j]->eOperator) & (WO_EQ|WO_ISNULL))!=0
  5138   5143           ){
  5139   5144             if( i & WO_ISNULL ){
................................................................................
  5142   5147             }
  5143   5148             continue;  
  5144   5149           }
  5145   5150   
  5146   5151           /* Get the column number in the table (iColumn) and sort order
  5147   5152           ** (revIdx) for the j-th column of the index.
  5148   5153           */
  5149         -        if( j<nKeyCol ){
  5150         -          /* Normal index columns */
         5154  +        if( pIndex ){
  5151   5155             iColumn = pIndex->aiColumn[j];
  5152   5156             revIdx = pIndex->aSortOrder[j];
  5153   5157             if( iColumn==pIndex->pTable->iPKey ) iColumn = -1;
  5154   5158           }else{
  5155         -          /* The ROWID column at the end */
  5156         -          assert( j==nKeyCol );
  5157   5159             iColumn = -1;
  5158   5160             revIdx = 0;
  5159   5161           }
  5160   5162   
  5161   5163           /* An unconstrained column that might be NULL means that this
  5162         -        ** WhereLoop is not well-ordered 
         5164  +        ** WhereLoop is not well-ordered
  5163   5165           */
  5164   5166           if( isOrderDistinct
  5165   5167            && iColumn>=0
  5166   5168            && j>=pLoop->u.btree.nEq
  5167   5169            && pIndex->pTable->aCol[iColumn].notNull==0
  5168   5170           ){
  5169   5171             isOrderDistinct = 0;

Changes to test/orderby5.test.

    89     89     SELECT * FROM t1 WHERE a=0 ORDER BY c, a, b;
    90     90   } {/B-TREE/}
    91     91   do_execsql_test 2.7 {
    92     92     EXPLAIN QUERY PLAN
    93     93     SELECT * FROM t1 WHERE a=0 ORDER BY c, b, a;
    94     94   } {/B-TREE/}
    95     95   
           96  +
           97  +do_execsql_test 3.0 {
           98  +  CREATE TABLE t3(a INTEGER PRIMARY KEY, b, c, d, e, f);
           99  +  CREATE INDEX t3bcde ON t3(b, c, d, e);
          100  +  EXPLAIN QUERY PLAN
          101  +  SELECT a FROM t3 WHERE b=2 AND c=3 ORDER BY d DESC, e DESC, b, c, a DESC;
          102  +} {~/B-TREE/}
          103  +do_execsql_test 3.1 {
          104  +  DROP TABLE t3;
          105  +  CREATE TABLE t3(a INTEGER PRIMARY KEY, b, c, d, e, f) WITHOUT rowid;
          106  +  CREATE INDEX t3bcde ON t3(b, c, d, e);
          107  +  EXPLAIN QUERY PLAN
          108  +  SELECT a FROM t3 WHERE b=2 AND c=3 ORDER BY d DESC, e DESC, b, c, a DESC;
          109  +} {~/B-TREE/}
          110  +
    96    111   
    97    112   finish_test