/ Check-in [f245f5c2]
Login

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

Overview
Comment:The query optimizer does a better job of optimizing out ORDER BY clauses that contain the rowid or which use indices that contain the rowid. Ticket #2116. (CVS 3536)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: f245f5c2c2d337fe6458824beb7f9e721837765f
User & Date: drh 2006-12-20 03:24:19
Context
2006-12-20
03:37
Patch to get extension loading working on wince. Ticket #2023. (CVS 3537) check-in: a81f3ddf user: drh tags: trunk
03:24
The query optimizer does a better job of optimizing out ORDER BY clauses that contain the rowid or which use indices that contain the rowid. Ticket #2116. (CVS 3536) check-in: f245f5c2 user: drh tags: trunk
02:15
Allow constraint names on DEFAULT values in a table definition. Ticket #2109. (CVS 3535) check-in: 893d58c2 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

    12     12   ** This module contains C code that generates VDBE code used to process
    13     13   ** the WHERE clause of SQL statements.  This module is reponsible for
    14     14   ** generating the code that loops through a table looking for applicable
    15     15   ** rows.  Indices are selected and used to speed the search when doing
    16     16   ** so is applicable.  Because this module is responsible for selecting
    17     17   ** indices, you might also think of this module as the "query optimizer".
    18     18   **
    19         -** $Id: where.c,v 1.233 2006/12/16 16:25:16 drh Exp $
           19  +** $Id: where.c,v 1.234 2006/12/20 03:24:19 drh Exp $
    20     20   */
    21     21   #include "sqliteInt.h"
    22     22   
    23     23   /*
    24     24   ** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
    25     25   */
    26     26   #define BMS  (sizeof(Bitmask)*8)
................................................................................
   864    864   
   865    865     assert( pOrderBy!=0 );
   866    866     nTerm = pOrderBy->nExpr;
   867    867     assert( nTerm>0 );
   868    868   
   869    869     /* Match terms of the ORDER BY clause against columns of
   870    870     ** the index.
          871  +  **
          872  +  ** Note that indices have pIdx->nColumn regular columns plus
          873  +  ** one additional column containing the rowid.  The rowid column
          874  +  ** of the index is also allowed to match against the ORDER BY
          875  +  ** clause.
   871    876     */
   872         -  for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<pIdx->nColumn; i++){
          877  +  for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<=pIdx->nColumn; i++){
   873    878       Expr *pExpr;       /* The expression of the ORDER BY pTerm */
   874    879       CollSeq *pColl;    /* The collating sequence of pExpr */
   875    880       int termSortOrder; /* Sort order for this term */
          881  +    int iColumn;       /* The i-th column of the index.  -1 for rowid */
          882  +    int iSortOrder;    /* 1 for DESC, 0 for ASC on the i-th index term */
          883  +    const char *zColl; /* Name of the collating sequence for i-th index term */
   876    884   
   877    885       pExpr = pTerm->pExpr;
   878    886       if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){
   879    887         /* Can not use an index sort on anything that is not a column in the
   880    888         ** left-most table of the FROM clause */
   881    889         return 0;
   882    890       }
   883    891       pColl = sqlite3ExprCollSeq(pParse, pExpr);
   884         -    if( !pColl ) pColl = db->pDfltColl;
   885         -    if( pExpr->iColumn!=pIdx->aiColumn[i] || 
   886         -        sqlite3StrICmp(pColl->zName, pIdx->azColl[i]) ){
          892  +    if( !pColl ){
          893  +      pColl = db->pDfltColl;
          894  +    }
          895  +    if( i<pIdx->nColumn ){
          896  +      iColumn = pIdx->aiColumn[i];
          897  +      if( iColumn==pIdx->pTable->iPKey ){
          898  +        iColumn = -1;
          899  +      }
          900  +      iSortOrder = pIdx->aSortOrder[i];
          901  +      zColl = pIdx->azColl[i];
          902  +    }else{
          903  +      iColumn = -1;
          904  +      iSortOrder = 0;
          905  +      zColl = pColl->zName;
          906  +    }
          907  +    if( pExpr->iColumn!=iColumn || sqlite3StrICmp(pColl->zName, zColl) ){
   887    908         /* Term j of the ORDER BY clause does not match column i of the index */
   888    909         if( i<nEqCol ){
   889    910           /* If an index column that is constrained by == fails to match an
   890    911           ** ORDER BY term, that is OK.  Just ignore that column of the index
   891    912           */
   892    913           continue;
   893    914         }else{
................................................................................
   895    916           ** then the index cannot satisfy the ORDER BY constraint.
   896    917           */
   897    918           return 0;
   898    919         }
   899    920       }
   900    921       assert( pIdx->aSortOrder!=0 );
   901    922       assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );
   902         -    assert( pIdx->aSortOrder[i]==0 || pIdx->aSortOrder[i]==1 );
   903         -    termSortOrder = pIdx->aSortOrder[i] ^ pTerm->sortOrder;
          923  +    assert( iSortOrder==0 || iSortOrder==1 );
          924  +    termSortOrder = iSortOrder ^ pTerm->sortOrder;
   904    925       if( i>nEqCol ){
   905    926         if( termSortOrder!=sortOrder ){
   906    927           /* Indices can only be used if all ORDER BY terms past the
   907    928           ** equality constraints are all either DESC or ASC. */
   908    929           return 0;
   909    930         }
   910    931       }else{
   911    932         sortOrder = termSortOrder;
   912    933       }
   913    934       j++;
   914    935       pTerm++;
          936  +    if( iColumn<0 ){
          937  +      /* If the indexed column is the primary key and everything matches
          938  +      ** so far, then we are assured that the index can be used to sort
          939  +      ** because the primary key is unique and so none of the other columns
          940  +      ** will make any difference
          941  +      */
          942  +      j = nTerm;
          943  +    }
   915    944     }
   916    945   
   917         -  /* The index can be used for sorting if all terms of the ORDER BY clause
   918         -  ** are covered.
   919         -  */
          946  +  *pbRev = sortOrder!=0;
   920    947     if( j>=nTerm ){
   921         -    *pbRev = sortOrder!=0;
          948  +    /* All terms of the ORDER BY clause are covered by this index so
          949  +    ** this index can be used for sorting. */
          950  +    return 1;
          951  +  }
          952  +  if( j==pIdx->nColumn && pIdx->onError!=OE_None ){
          953  +    /* All terms of this index match some prefix of the ORDER BY clause
          954  +    ** and this index is UNIQUE, so this index can be used for sorting. */
   922    955       return 1;
   923    956     }
   924    957     return 0;
   925    958   }
   926    959   
   927    960   /*
   928    961   ** Check table to see if the ORDER BY clause in pOrderBy can be satisfied
................................................................................
   935    968     int *pbRev              /* Set to 1 if ORDER BY is DESC */
   936    969   ){
   937    970     Expr *p;
   938    971   
   939    972     assert( pOrderBy!=0 );
   940    973     assert( pOrderBy->nExpr>0 );
   941    974     p = pOrderBy->a[0].pExpr;
   942         -  if( pOrderBy->nExpr==1 && p->op==TK_COLUMN && p->iTable==base
   943         -          && p->iColumn==-1 ){
          975  +  if( p->op==TK_COLUMN && p->iTable==base && p->iColumn==-1 ){
   944    976       *pbRev = pOrderBy->a[0].sortOrder;
   945    977       return 1;
   946    978     }
   947    979     return 0;
   948    980   }
   949    981   
   950    982   /*

Changes to test/where.test.

     7      7   #    May you find forgiveness for yourself and forgive others.
     8      8   #    May you share freely, never taking more than you give.
     9      9   #
    10     10   #***********************************************************************
    11     11   # This file implements regression tests for SQLite library.  The
    12     12   # focus of this file is testing the use of indices in WHERE clases.
    13     13   #
    14         -# $Id: where.test,v 1.38 2005/11/14 22:29:06 drh Exp $
           14  +# $Id: where.test,v 1.39 2006/12/20 03:24:19 drh Exp $
    15     15   
    16     16   set testdir [file dirname $argv0]
    17     17   source $testdir/tester.tcl
    18     18   
    19     19   # Build some test data
    20     20   #
    21     21   do_test where-1.0 {
................................................................................
   585    585       SELECT y FROM t1 ORDER BY rowid LIMIT 3;
   586    586     }
   587    587   } {4 9 16 nosort}
   588    588   do_test where-6.21 {
   589    589     cksort {
   590    590       SELECT y FROM t1 ORDER BY rowid, y LIMIT 3;
   591    591     }
   592         -} {4 9 16 sort}
          592  +} {4 9 16 nosort}
   593    593   do_test where-6.22 {
   594    594     cksort {
   595    595       SELECT y FROM t1 ORDER BY rowid, y DESC LIMIT 3;
   596    596     }
   597         -} {4 9 16 sort}
          597  +} {4 9 16 nosort}
   598    598   do_test where-6.23 {
   599    599     cksort {
   600    600       SELECT y FROM t1 WHERE y>4 ORDER BY rowid, w, x LIMIT 3;
   601    601     }
   602         -} {9 16 25 sort}
          602  +} {9 16 25 nosort}
   603    603   do_test where-6.24 {
   604    604     cksort {
   605    605       SELECT y FROM t1 WHERE y>=9 ORDER BY rowid, x DESC, w LIMIT 3;
   606    606     }
   607         -} {9 16 25 sort}
          607  +} {9 16 25 nosort}
   608    608   do_test where-6.25 {
   609    609     cksort {
   610    610       SELECT y FROM t1 WHERE y>4 AND y<25 ORDER BY rowid;
   611    611     }
   612    612   } {9 16 nosort}
   613    613   do_test where-6.26 {
   614    614     cksort {
................................................................................
   615    615       SELECT y FROM t1 WHERE y>=4 AND y<=25 ORDER BY oid;
   616    616     }
   617    617   } {4 9 16 25 nosort}
   618    618   do_test where-6.27 {
   619    619     cksort {
   620    620       SELECT y FROM t1 WHERE y<=25 ORDER BY _rowid_, w+y;
   621    621     }
   622         -} {4 9 16 25 sort}
          622  +} {4 9 16 25 nosort}
   623    623   
   624    624   
   625    625   # Tests for reverse-order sorting.
   626    626   #
   627    627   do_test where-7.1 {
   628    628     cksort {
   629    629       SELECT w FROM t1 WHERE x=3 ORDER BY y;
................................................................................
   789    789       SELECT y FROM t1 WHERE y<=25 ORDER BY rowid DESC
   790    790     }
   791    791   } {25 16 9 4 nosort}
   792    792   do_test where-7.34 {
   793    793     cksort {
   794    794       SELECT y FROM t1 WHERE y<25 AND y>4 ORDER BY rowid DESC, y DESC
   795    795     }
   796         -} {16 9 sort}
          796  +} {16 9 nosort}
   797    797   do_test where-7.35 {
   798    798     cksort {
   799    799       SELECT y FROM t1 WHERE y<25 AND y>=4 ORDER BY rowid DESC
   800    800     }
   801    801   } {16 9 4 nosort}
   802    802   
   803    803   do_test where-8.1 {
................................................................................
   870    870   
   871    871   # Ticket #1376.  The query below was causing a segfault.
   872    872   # The problem was the age-old error of calling realloc() on an
   873    873   # array while there are still pointers to individual elements of
   874    874   # that array.
   875    875   #
   876    876   do_test where-11.1 {
   877         -btree_breakpoint
   878    877     execsql {
   879    878      CREATE TABLE t99(Dte INT, X INT);
   880    879      DELETE FROM t99 WHERE (Dte = 2451337) OR (Dte = 2451339) OR
   881    880        (Dte BETWEEN 2451345 AND 2451347) OR (Dte = 2451351) OR 
   882    881        (Dte BETWEEN 2451355 AND 2451356) OR (Dte = 2451358) OR
   883    882        (Dte = 2451362) OR (Dte = 2451365) OR (Dte = 2451367) OR
   884    883        (Dte BETWEEN 2451372 AND 2451376) OR (Dte BETWEEN 2451382 AND 2451384) OR
................................................................................
   897    896        (Dte BETWEEN 2451565 AND 2451566) OR (Dte BETWEEN 2451569 AND 2451571) OR 
   898    897        (Dte = 2451573) OR (Dte = 2451575) OR (Dte = 2451577) OR (Dte = 2451581) OR
   899    898        (Dte BETWEEN 2451583 AND 2451586) OR (Dte BETWEEN 2451588 AND 2451592) OR 
   900    899        (Dte BETWEEN 2451596 AND 2451598) OR (Dte = 2451600) OR
   901    900        (Dte BETWEEN 2451602 AND 2451603) OR (Dte = 2451606) OR (Dte = 2451611);
   902    901     }
   903    902   } {}
          903  +
          904  +# Ticket #2116:  Make sure sorting by index works well with nn INTEGER PRIMARY
          905  +# KEY.
          906  +#
          907  +do_test where-12.1 {
          908  +  execsql {
          909  +    CREATE TABLE t6(a INTEGER PRIMARY KEY, b TEXT);
          910  +    INSERT INTO t6 VALUES(1,'one');
          911  +    INSERT INTO t6 VALUES(4,'four');
          912  +    CREATE INDEX t6i1 ON t6(b);
          913  +  }
          914  +  cksort {
          915  +    SELECT * FROM t6 ORDER BY b;
          916  +  }
          917  +} {4 four 1 one nosort}
          918  +do_test where-12.2 {
          919  +  cksort {
          920  +    SELECT * FROM t6 ORDER BY b, a;
          921  +  }
          922  +} {4 four 1 one nosort}
          923  +do_test where-12.3 {
          924  +  cksort {
          925  +    SELECT * FROM t6 ORDER BY a;
          926  +  }
          927  +} {1 one 4 four nosort}
          928  +do_test where-12.4 {
          929  +  cksort {
          930  +    SELECT * FROM t6 ORDER BY a, b;
          931  +  }
          932  +} {1 one 4 four nosort}
          933  +do_test where-12.5 {
          934  +  cksort {
          935  +    SELECT * FROM t6 ORDER BY b DESC;
          936  +  }
          937  +} {1 one 4 four nosort}
          938  +do_test where-12.6 {
          939  +  cksort {
          940  +    SELECT * FROM t6 ORDER BY b DESC, a DESC;
          941  +  }
          942  +} {1 one 4 four nosort}
          943  +do_test where-12.7 {
          944  +  cksort {
          945  +    SELECT * FROM t6 ORDER BY b DESC, a ASC;
          946  +  }
          947  +} {1 one 4 four sort}
          948  +do_test where-12.8 {
          949  +  cksort {
          950  +    SELECT * FROM t6 ORDER BY b ASC, a DESC;
          951  +  }
          952  +} {4 four 1 one sort}
          953  +do_test where-12.9 {
          954  +  cksort {
          955  +    SELECT * FROM t6 ORDER BY a DESC;
          956  +  }
          957  +} {4 four 1 one nosort}
          958  +do_test where-12.10 {
          959  +  cksort {
          960  +    SELECT * FROM t6 ORDER BY a DESC, b DESC;
          961  +  }
          962  +} {4 four 1 one nosort}
          963  +do_test where-12.11 {
          964  +  cksort {
          965  +    SELECT * FROM t6 ORDER BY a DESC, b ASC;
          966  +  }
          967  +} {4 four 1 one nosort}
          968  +do_test where-12.12 {
          969  +  cksort {
          970  +    SELECT * FROM t6 ORDER BY a ASC, b DESC;
          971  +  }
          972  +} {1 one 4 four nosort}
          973  +do_test where-13.1 {
          974  +  execsql {
          975  +    CREATE TABLE t7(a INTEGER PRIMARY KEY, b TEXT);
          976  +    INSERT INTO t7 VALUES(1,'one');
          977  +    INSERT INTO t7 VALUES(4,'four');
          978  +    CREATE INDEX t7i1 ON t7(b);
          979  +  }
          980  +  cksort {
          981  +    SELECT * FROM t7 ORDER BY b;
          982  +  }
          983  +} {4 four 1 one nosort}
          984  +do_test where-13.2 {
          985  +  cksort {
          986  +    SELECT * FROM t7 ORDER BY b, a;
          987  +  }
          988  +} {4 four 1 one nosort}
          989  +do_test where-13.3 {
          990  +  cksort {
          991  +    SELECT * FROM t7 ORDER BY a;
          992  +  }
          993  +} {1 one 4 four nosort}
          994  +do_test where-13.4 {
          995  +  cksort {
          996  +    SELECT * FROM t7 ORDER BY a, b;
          997  +  }
          998  +} {1 one 4 four nosort}
          999  +do_test where-13.5 {
         1000  +  cksort {
         1001  +    SELECT * FROM t7 ORDER BY b DESC;
         1002  +  }
         1003  +} {1 one 4 four nosort}
         1004  +do_test where-13.6 {
         1005  +  cksort {
         1006  +    SELECT * FROM t7 ORDER BY b DESC, a DESC;
         1007  +  }
         1008  +} {1 one 4 four nosort}
         1009  +do_test where-13.7 {
         1010  +  cksort {
         1011  +    SELECT * FROM t7 ORDER BY b DESC, a ASC;
         1012  +  }
         1013  +} {1 one 4 four sort}
         1014  +do_test where-13.8 {
         1015  +  cksort {
         1016  +    SELECT * FROM t7 ORDER BY b ASC, a DESC;
         1017  +  }
         1018  +} {4 four 1 one sort}
         1019  +do_test where-13.9 {
         1020  +  cksort {
         1021  +    SELECT * FROM t7 ORDER BY a DESC;
         1022  +  }
         1023  +} {4 four 1 one nosort}
         1024  +do_test where-13.10 {
         1025  +  cksort {
         1026  +    SELECT * FROM t7 ORDER BY a DESC, b DESC;
         1027  +  }
         1028  +} {4 four 1 one nosort}
         1029  +do_test where-13.11 {
         1030  +  cksort {
         1031  +    SELECT * FROM t7 ORDER BY a DESC, b ASC;
         1032  +  }
         1033  +} {4 four 1 one nosort}
         1034  +do_test where-13.12 {
         1035  +  cksort {
         1036  +    SELECT * FROM t7 ORDER BY a ASC, b DESC;
         1037  +  }
         1038  +} {1 one 4 four nosort}
         1039  +
   904   1040   
   905   1041   
   906   1042   integrity_check {where-99.0}
   907   1043   
   908   1044   finish_test