/ Check-in [e5aa4894]
Login

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

Overview
Comment:The optimizer now uses only the index and ignores the table if it can get away with doing so, thus saving a single BTree search per row of result. This could potentially double the speed of certain queries. The code passes all regression tests but new tests to exercise the new functionality are yet to be added. (CVS 2170)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: e5aa489453bf31126da6473ef93c89ec27935cde
User & Date: drh 2004-12-19 00:11:35
Context
2004-12-20
19:01
Add PRAGMA 'temp_store_directory'. Added os_*.c function sqlite3OsIsDirWritable(), split pragma.c changeTempStorage() function into invalidateTempStorage(). (CVS 2171) check-in: 772e22cb user: tpoindex tags: trunk
2004-12-19
00:11
The optimizer now uses only the index and ignores the table if it can get away with doing so, thus saving a single BTree search per row of result. This could potentially double the speed of certain queries. The code passes all regression tests but new tests to exercise the new functionality are yet to be added. (CVS 2170) check-in: e5aa4894 user: drh tags: trunk
2004-12-18
18:40
Improvements to the query optimizer. This is a work in progress. (CVS 2169) check-in: 9b86993f user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/sqliteInt.h.

     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** Internal interface definitions for SQLite.
    13     13   **
    14         -** @(#) $Id: sqliteInt.h,v 1.347 2004/12/18 18:40:27 drh Exp $
           14  +** @(#) $Id: sqliteInt.h,v 1.348 2004/12/19 00:11:35 drh Exp $
    15     15   */
    16     16   #ifndef _SQLITEINT_H_
    17     17   #define _SQLITEINT_H_
    18     18   
    19     19   /*
    20     20   ** These #defines should enable >2GB file support on Posix if the
    21     21   ** underlying operating system supports it.  If the OS lacks
................................................................................
   305    305   typedef struct Db Db;
   306    306   typedef struct AuthContext AuthContext;
   307    307   typedef struct KeyClass KeyClass;
   308    308   typedef struct CollSeq CollSeq;
   309    309   typedef struct KeyInfo KeyInfo;
   310    310   typedef struct SqlCursor SqlCursor;
   311    311   typedef struct Fetch Fetch;
          312  +typedef struct CursorSubst CursorSubst;
   312    313   
   313    314   /*
   314    315   ** Each database file to be accessed by the system is an instance
   315    316   ** of the following structure.  There are normally two of these structures
   316    317   ** in the sqlite.aDb[] array.  aDb[0] is the main database file and
   317    318   ** aDb[1] is the database file used to hold temporary tables.  Additional
   318    319   ** databases may be attached.
................................................................................
   906    907   ** For each nested loop in a WHERE clause implementation, the WhereInfo
   907    908   ** structure contains a single instance of this structure.  This structure
   908    909   ** is intended to be private the the where.c module and should not be
   909    910   ** access or modified by other modules.
   910    911   */
   911    912   struct WhereLevel {
   912    913     int iMem;            /* Memory cell used by this level */
   913         -  Index *pIdx;         /* Index used */
   914         -  int iCur;            /* Cursor number used for this index */
          914  +  Index *pIdx;         /* Index used.  NULL if no index */
          915  +  int iTabCur;         /* The VDBE cursor used to access the table */
          916  +  int iIdxCur;         /* The VDBE cursor used to acesss pIdx */
   915    917     int score;           /* How well this indexed scored */
   916    918     int brk;             /* Jump here to break out of the loop */
   917    919     int cont;            /* Jump here to continue with the next loop cycle */
   918    920     int op, p1, p2;      /* Opcode used to terminate the loop */
   919    921     int iLeftJoin;       /* Memory cell used to implement LEFT OUTER JOIN */
   920    922     int top;             /* First instruction of interior of the loop */
   921    923     int inOp, inP1, inP2;/* Opcode used to implement an IN operator */
................................................................................
   928    930   ** half does the tail of the WHERE loop.  An instance of
   929    931   ** this structure is returned by the first half and passed
   930    932   ** into the second half to give some continuity.
   931    933   */
   932    934   struct WhereInfo {
   933    935     Parse *pParse;
   934    936     SrcList *pTabList;   /* List of tables in the join */
          937  +  int iTop;            /* The very beginning of the WHERE loop */
   935    938     int iContinue;       /* Jump here to continue with next record */
   936    939     int iBreak;          /* Jump here to break out of the loop */
   937    940     int nLevel;          /* Number of nested loop */
   938    941     WhereLevel a[1];     /* Information about each nest loop in the WHERE */
   939    942   };
   940    943   
   941    944   /*
................................................................................
  1063   1066     Token sLastToken;    /* The last token parsed */
  1064   1067     const char *zSql;    /* All SQL text */
  1065   1068     const char *zTail;   /* All SQL text past the last semicolon parsed */
  1066   1069     Table *pNewTable;    /* A table being constructed by CREATE TABLE */
  1067   1070     Trigger *pNewTrigger;     /* Trigger under construct by a CREATE TRIGGER */
  1068   1071     TriggerStack *trigStack;  /* Trigger actions being coded */
  1069   1072     const char *zAuthContext; /* The 6th parameter to db->xAuth callbacks */
  1070         -  
  1071   1073   };
  1072   1074   
  1073   1075   /*
  1074   1076   ** An instance of the following structure can be declared on a stack and used
  1075   1077   ** to save the Parse.zAuthContext value so that it can be restored later.
  1076   1078   */
  1077   1079   struct AuthContext {

Changes to src/vdbe.c.

    39     39   **
    40     40   ** Various scripts scan this source file in order to generate HTML
    41     41   ** documentation, headers files, or other derived files.  The formatting
    42     42   ** of the code in this file is, therefore, important.  See other comments
    43     43   ** in this file for details.  If in doubt, do not deviate from existing
    44     44   ** commenting and indentation practices when changing or adding code.
    45     45   **
    46         -** $Id: vdbe.c,v 1.433 2004/12/07 14:06:13 drh Exp $
           46  +** $Id: vdbe.c,v 1.434 2004/12/19 00:11:35 drh Exp $
    47     47   */
    48     48   #include "sqliteInt.h"
    49     49   #include "os.h"
    50     50   #include <ctype.h>
    51     51   #include "vdbeInt.h"
    52     52   
    53     53   /*
................................................................................
  1662   1662   case OP_SetNumColumns: {
  1663   1663     assert( (pOp->p1)<p->nCursor );
  1664   1664     assert( p->apCsr[pOp->p1]!=0 );
  1665   1665     p->apCsr[pOp->p1]->nField = pOp->p2;
  1666   1666     break;
  1667   1667   }
  1668   1668   
  1669         -/* Opcode: IdxColumn P1 * *
  1670         -**
  1671         -** P1 is a cursor opened on an index. Push the first field from the
  1672         -** current index key onto the stack.
  1673         -*/
  1674   1669   /* Opcode: Column P1 P2 *
  1675   1670   **
  1676   1671   ** Interpret the data that cursor P1 points to as a structure built using
  1677   1672   ** the MakeRecord instruction.  (See the MakeRecord opcode for additional
  1678   1673   ** information about the format of the data.) Push onto the stack the value
  1679   1674   ** of the P2-th column contained in the data.
  1680   1675   **
................................................................................
  1684   1679   ** If P1 is negative, then the record is stored on the stack rather than in
  1685   1680   ** a table.  For P1==-1, the top of the stack is used.  For P1==-2, the
  1686   1681   ** next on the stack is used.  And so forth.  The value pushed is always
  1687   1682   ** just a pointer into the record which is stored further down on the
  1688   1683   ** stack.  The column value is not copied. The number of columns in the
  1689   1684   ** record is stored on the stack just above the record itself.
  1690   1685   */
  1691         -case OP_IdxColumn:
  1692   1686   case OP_Column: {
  1693   1687     u32 payloadSize;   /* Number of bytes in the record */
  1694   1688     int p1 = pOp->p1;  /* P1 value of the opcode */
  1695   1689     int p2 = pOp->p2;  /* column number to retrieve */
  1696   1690     Cursor *pC = 0;    /* The VDBE cursor */
  1697   1691     char *zRec;        /* Pointer to complete record-data */
  1698   1692     BtCursor *pCrsr;   /* The BTree cursor */
................................................................................
  3478   3472     pTos--;
  3479   3473     break;
  3480   3474   }
  3481   3475   
  3482   3476   /* Opcode: IdxRecno P1 * *
  3483   3477   **
  3484   3478   ** Push onto the stack an integer which is the varint located at the
  3485         -** end of the index key pointed to by cursor P1.  These integer should be
         3479  +** end of the index key pointed to by cursor P1.  This integer should be
  3486   3480   ** the record number of the table entry to which this index entry points.
  3487   3481   **
  3488   3482   ** See also: Recno, MakeIdxKey.
  3489   3483   */
  3490   3484   case OP_IdxRecno: {
  3491   3485     int i = pOp->p1;
  3492   3486     BtCursor *pCrsr;

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.122 2004/12/18 18:40:27 drh Exp $
           19  +** $Id: where.c,v 1.123 2004/12/19 00:11:35 drh Exp $
    20     20   */
    21     21   #include "sqliteInt.h"
    22     22   
    23     23   /*
    24     24   ** The query generator uses an array of instances of this structure to
    25     25   ** help it analyze the subexpressions of the WHERE clause.  Each WHERE
    26     26   ** clause subexpression is separated from the others by an AND operator.
................................................................................
   292    292         SWAP(unsigned, pInfo->prereqLeft, pInfo->prereqRight);
   293    293         SWAP(short int, pInfo->idxLeft, pInfo->idxRight);
   294    294       }
   295    295     }      
   296    296   
   297    297   }
   298    298   
   299         -/*
   300         -** pOrderBy is an ORDER BY clause from a SELECT statement.  pTab is the
   301         -** left-most table in the FROM clause of that same SELECT statement and
   302         -** the table has a cursor number of "base".
   303         -**
   304         -** This routine attempts to find an index for pTab that generates the
   305         -** correct record sequence for the given ORDER BY clause.  The return value
   306         -** is a pointer to an index that does the job.  NULL is returned if the
   307         -** table has no index that will generate the correct sort order.
   308         -**
   309         -** If there are two or more indices that generate the correct sort order
   310         -** and pPreferredIdx is one of those indices, then return pPreferredIdx.
   311         -**
   312         -** nEqCol is the number of columns of pPreferredIdx that are used as
   313         -** equality constraints.  Any index returned must have exactly this same
   314         -** set of columns.  The ORDER BY clause only matches index columns beyond the
   315         -** the first nEqCol columns.
   316         -**
   317         -** All terms of the ORDER BY clause must be either ASC or DESC.  The
   318         -** *pbRev value is set to 1 if the ORDER BY clause is all DESC and it is
   319         -** set to 0 if the ORDER BY clause is all ASC.
   320         -**
   321         -** TODO:  If earlier terms of an ORDER BY clause match all terms of a
   322         -** UNIQUE index, then subsequent terms of the ORDER BY can be ignored.
   323         -** This optimization needs to be implemented.
   324         -*/
   325         -static Index *findSortingIndex(
   326         -  Parse *pParse,          /* Parsing context */
   327         -  Table *pTab,            /* The table to be sorted */
   328         -  int base,               /* Cursor number for pTab */
   329         -  ExprList *pOrderBy,     /* The ORDER BY clause */
   330         -  Index *pPreferredIdx,   /* Use this index, if possible and not NULL */
   331         -  int nEqCol,             /* Number of index columns used with == constraints */
   332         -  int *pbRev              /* Set to 1 if ORDER BY is DESC */
   333         -){
   334         -  int i, j;                    /* Loop counters */
   335         -  Index *pMatch;               /* Best matching index so far */
   336         -  Index *pIdx;                 /* Current index */
   337         -  int sortOrder;               /* Which direction we are sorting */
   338         -  sqlite3 *db = pParse->db;
   339         -
   340         -  assert( pOrderBy!=0 );
   341         -  assert( pOrderBy->nExpr>0 );
   342         -  assert( pPreferredIdx!=0 || nEqCol==0 );
   343         -  sortOrder = pOrderBy->a[0].sortOrder;
   344         -  for(i=0; i<pOrderBy->nExpr; i++){
   345         -    Expr *p;
   346         -    if( pOrderBy->a[i].sortOrder!=sortOrder ){
   347         -      /* Indices can only be used if all ORDER BY terms are either
   348         -      ** DESC or ASC.  Indices cannot be used on a mixture. */
   349         -      return 0;
   350         -    }
   351         -    p = pOrderBy->a[i].pExpr;
   352         -    if( p->op!=TK_COLUMN || p->iTable!=base ){
   353         -      /* Can not use an index sort on anything that is not a column in the
   354         -      ** left-most table of the FROM clause */
   355         -      return 0;
   356         -    }
   357         -  }
   358         -
   359         -  /* If we get this far, it means the ORDER BY clause consists of columns
   360         -  ** that are all either ascending or descending and which refer only to
   361         -  ** the left-most table of the FROM clause.  Find the index that is best
   362         -  ** used for sorting.
   363         -  */
   364         -  pMatch = 0;
   365         -  for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
   366         -    int nExpr = pOrderBy->nExpr;
   367         -    if( pIdx->nColumn < nEqCol || pIdx->nColumn < nExpr ) continue;
   368         -    for(i=j=0; i<nEqCol; i++){
   369         -      CollSeq *pColl = sqlite3ExprCollSeq(pParse, pOrderBy->a[j].pExpr);
   370         -      if( !pColl ) pColl = db->pDfltColl;
   371         -      if( pPreferredIdx->aiColumn[i]!=pIdx->aiColumn[i] ) break;
   372         -      if( pPreferredIdx->keyInfo.aColl[i]!=pIdx->keyInfo.aColl[i] ) break;
   373         -      if( j<nExpr && 
   374         -          pOrderBy->a[j].pExpr->iColumn==pIdx->aiColumn[i] &&
   375         -          pColl==pIdx->keyInfo.aColl[i]
   376         -      ){ 
   377         -        j++; 
   378         -      }
   379         -    }
   380         -    if( i<nEqCol ) continue;
   381         -    for(i=0; i+j<nExpr; i++){
   382         -      CollSeq *pColl = sqlite3ExprCollSeq(pParse, pOrderBy->a[i+j].pExpr);
   383         -      if( !pColl ) pColl = db->pDfltColl;
   384         -      if( pOrderBy->a[i+j].pExpr->iColumn!=pIdx->aiColumn[i+nEqCol] ||
   385         -          pColl!=pIdx->keyInfo.aColl[i+nEqCol] ) break;
   386         -    }
   387         -    if( i+j>=nExpr ){
   388         -      pMatch = pIdx;
   389         -      if( pIdx==pPreferredIdx ) break;
   390         -    }
   391         -  }
   392         -  *pbRev = sortOrder==SQLITE_SO_DESC;
   393         -  return pMatch;
   394         -}
   395         -
   396    299   /*
   397    300   ** This routine decides if pIdx can be used to satisfy the ORDER BY
   398    301   ** clause.  If it can, it returns 1.  If pIdx cannot satisfy the
   399    302   ** ORDER BY clause, this routine returns 0.
   400    303   **
   401    304   ** pOrderBy is an ORDER BY clause from a SELECT statement.  pTab is the
   402    305   ** left-most table in the FROM clause of that same SELECT statement and
................................................................................
   446    349       if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){
   447    350         /* Can not use an index sort on anything that is not a column in the
   448    351         ** left-most table of the FROM clause */
   449    352         return 0;
   450    353       }
   451    354       pColl = sqlite3ExprCollSeq(pParse, pExpr);
   452    355       if( !pColl ) pColl = db->pDfltColl;
   453         -    if( pExpr->iColumn!=pIdx->aiColumn[i] && pColl!=pIdx->keyInfo.aColl[i] ){
   454         -      if( i<=nEqCol ){
          356  +    if( pExpr->iColumn!=pIdx->aiColumn[i] || pColl!=pIdx->keyInfo.aColl[i] ){
          357  +      /* Term j of the ORDER BY clause does not match column i of the index */
          358  +      if( i<nEqCol ){
   455    359           /* If an index column that is constrained by == fails to match an
   456    360           ** ORDER BY term, that is OK.  Just ignore that column of the index
   457    361           */
   458    362           continue;
   459    363         }else{
   460    364           /* If an index column fails to match and is not constrained by ==
   461    365           ** then the index cannot satisfy the ORDER BY constraint.
................................................................................
   573    477       assert( pX->op==TK_EQ );
   574    478       sqlite3ExprCode(pParse, pX->pRight);
   575    479     }else{
   576    480       int iTab = pX->iTable;
   577    481       Vdbe *v = pParse->pVdbe;
   578    482       sqlite3VdbeAddOp(v, OP_Rewind, iTab, brk);
   579    483       sqlite3VdbeAddOp(v, OP_KeyAsData, iTab, 1);
   580         -    pLevel->inP2 = sqlite3VdbeAddOp(v, OP_IdxColumn, iTab, 0);
          484  +    pLevel->inP2 = sqlite3VdbeAddOp(v, OP_Column, iTab, 0);
   581    485       pLevel->inOp = OP_Next;
   582    486       pLevel->inP1 = iTab;
   583    487     }
   584    488     disableTerm(pLevel, &pTerm->p);
   585    489   }
   586    490   
   587    491   /*
................................................................................
   677    581   ){
   678    582     int i;                     /* Loop counter */
   679    583     WhereInfo *pWInfo;         /* Will become the return value of this function */
   680    584     Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
   681    585     int brk, cont = 0;         /* Addresses used during code generation */
   682    586     int nExpr;           /* Number of subexpressions in the WHERE clause */
   683    587     Bitmask loopMask;    /* One bit set for each outer loop */
   684         -  int haveKey = 0;     /* True if KEY is on the stack */
          588  +  int haveRowid = 0;   /* True if the ROWID is on the stack */
   685    589     ExprInfo *pTerm;     /* A single term in the WHERE clause; ptr to aExpr[] */
   686    590     ExprMaskSet maskSet; /* The expression mask set */
   687    591     int iDirectEq[BMS];  /* Term of the form ROWID==X for the N-th table */
   688    592     int iDirectLt[BMS];  /* Term of the form ROWID<X or ROWID<=X */
   689    593     int iDirectGt[BMS];  /* Term of the form ROWID>X or ROWID>=X */
   690    594     ExprInfo aExpr[101]; /* The WHERE clause is divided into these terms */
          595  +  struct SrcList_item *pTabItem;  /* A single entry from pTabList */
          596  +  WhereLevel *pLevel;             /* A single level in the pWInfo list */
   691    597   
   692    598     /* pushKey is only allowed if there is a single table (as in an INSERT or
   693    599     ** UPDATE statement)
   694    600     */
   695    601     assert( pushKey==0 || pTabList->nSrc==1 );
   696    602   
   697    603     /* Split the WHERE clause into separate subexpressions where each
................................................................................
   767    673     ** doing a second read of the actual database table.
   768    674     **
   769    675     ** Actually, if there are more than 32 tables in the join, only the
   770    676     ** first 32 tables are candidates for indices.  This is (again) due
   771    677     ** to the limit of 32 bits in an integer bitmask.
   772    678     */
   773    679     loopMask = 0;
   774         -  for(i=0; i<pTabList->nSrc && i<ARRAYSIZE(iDirectEq); i++){
          680  +  pTabItem = pTabList->a;
          681  +  pLevel = pWInfo->a;
          682  +  for(i=0; i<pTabList->nSrc && i<ARRAYSIZE(iDirectEq); i++,pTabItem++,pLevel++){
   775    683       int j;
   776         -    WhereLevel *pLevel = &pWInfo->a[i];
   777         -    int iCur = pTabList->a[i].iCursor;       /* The cursor for this table */
          684  +    int iCur = pTabItem->iCursor;            /* The cursor for this table */
   778    685       Bitmask mask = getMask(&maskSet, iCur);  /* Cursor mask for this table */
   779         -    Table *pTab = pTabList->a[i].pTab;
          686  +    Table *pTab = pTabItem->pTab;
   780    687       Index *pIdx;
   781    688       Index *pBestIdx = 0;
   782    689       int bestScore = 0;
   783    690       int bestRev = 0;
   784    691   
   785    692       /* Check to see if there is an expression that uses only the
   786    693       ** ROWID field of this table.  For terms of the form ROWID==expr
   787    694       ** set iDirectEq[i] to the index of the term.  For terms of the
   788    695       ** form ROWID<expr or ROWID<=expr set iDirectLt[i] to the term index.
   789    696       ** For terms like ROWID>expr or ROWID>=expr set iDirectGt[i].
   790    697       **
   791    698       ** (Added:) Treat ROWID IN expr like ROWID=expr.
   792    699       */
   793         -    pLevel->iCur = -1;
          700  +    pLevel->iIdxCur = -1;
   794    701       iDirectEq[i] = -1;
   795    702       iDirectLt[i] = -1;
   796    703       iDirectGt[i] = -1;
   797    704       for(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
   798    705         Expr *pX = pTerm->p;
   799    706         if( pTerm->idxLeft==iCur && pX->pLeft->iColumn<0
   800    707               && (pTerm->prereqRight & loopMask)==pTerm->prereqRight ){
................................................................................
   929    836         m = ((Bitmask)1)<<nEq;
   930    837         if( m & ltMask ) score+=4;    /* Increase score for a < constraint */
   931    838         if( m & gtMask ) score+=8;    /* Increase score for a > constraint */
   932    839         if( score==0 && inMask ) score = 16; /* Default score for IN constraint */
   933    840   
   934    841         /* Give bonus points if this index can be used for sorting
   935    842         */
   936         -      if( i==0 && score>0 && ppOrderBy && *ppOrderBy ){
          843  +      if( i==0 && score!=16 && ppOrderBy && *ppOrderBy ){
   937    844           int base = pTabList->a[0].iCursor;
   938    845           if( isSortingIndex(pParse, pIdx, pTab, base, *ppOrderBy, nEq, &bRev) ){
   939    846             score += 2;
   940    847           }
   941    848         }
          849  +
          850  +      /* Check to see if we can get away with using just the index without
          851  +      ** ever reading the table.  If that is the case, then add one bonus
          852  +      ** point to the score.
          853  +      */
          854  +      if( score && pTabItem->colUsed < (((Bitmask)1)<<(BMS-1)) ){
          855  +        for(m=0, j=0; j<pIdx->nColumn; j++){
          856  +          int x = pIdx->aiColumn[j];
          857  +          if( x<BMS-1 ){
          858  +            m |= ((Bitmask)1)<<x;
          859  +          }
          860  +        }
          861  +        if( (pTabItem->colUsed & m)==pTabItem->colUsed ){
          862  +          score++;
          863  +        }
          864  +      }
   942    865   
   943    866         /* If the score for this index is the best we have seen so far, then
   944    867         ** save it
   945    868         */
   946    869         if( score>bestScore ){
   947    870           pBestIdx = pIdx;
   948    871           bestScore = score;
................................................................................
   950    873         }
   951    874       }
   952    875       pLevel->pIdx = pBestIdx;
   953    876       pLevel->score = bestScore;
   954    877       pLevel->bRev = bestRev;
   955    878       loopMask |= mask;
   956    879       if( pBestIdx ){
   957         -      pLevel->iCur = pParse->nTab++;
          880  +      pLevel->iIdxCur = pParse->nTab++;
   958    881       }
   959    882     }
   960    883   
   961    884     /* Check to see if the ORDER BY clause is or can be satisfied by the
   962    885     ** use of an index on the first table.
   963    886     */
   964    887     if( ppOrderBy && *ppOrderBy && pTabList->nSrc>0 ){
   965         -     Index *pSortIdx = 0;     /* Index that satisfies the ORDER BY clause */
   966         -     Index *pIdx;             /* Index derived from the WHERE clause */
   967         -     Table *pTab;             /* Left-most table in the FROM clause */
   968         -     int bRev = 0;            /* True to reverse the output order */
   969         -     int iCur;                /* Btree-cursor that will be used by pTab */
   970         -     WhereLevel *pLevel0 = &pWInfo->a[0];
   971         -
   972         -     pTab = pTabList->a[0].pTab;
   973         -     pIdx = pLevel0->pIdx;
   974         -     iCur = pTabList->a[0].iCursor;
   975         -     if( pIdx==0 && sortableByRowid(iCur, *ppOrderBy, &bRev) ){
   976         -       /* The ORDER BY clause specifies ROWID order, which is what we
   977         -       ** were going to be doing anyway...
   978         -       */
   979         -       *ppOrderBy = 0;
   980         -       pLevel0->bRev = bRev;
   981         -     }else if( pLevel0->score==16 ){
   982         -       /* If there is already an IN index on the left-most table,
   983         -       ** it will not give the correct sort order.
   984         -       ** So, pretend that no suitable index is found.
   985         -       */
   986         -     }else if( iDirectEq[0]>=0 || iDirectLt[0]>=0 || iDirectGt[0]>=0 ){
   987         -       /* If the left-most column is accessed using its ROWID, then do
   988         -       ** not try to sort by index.  But do delete the ORDER BY clause
   989         -       ** if it is redundant.
   990         -       */
   991         -     }else{
   992         -       int nEqCol = (pLevel0->score+16)/32;
   993         -       pSortIdx = findSortingIndex(pParse, pTab, iCur, 
   994         -                                   *ppOrderBy, pIdx, nEqCol, &bRev);
   995         -     }
   996         -     if( pSortIdx && (pIdx==0 || pIdx==pSortIdx) ){
   997         -       if( pIdx==0 ){
   998         -         pLevel0->pIdx = pSortIdx;
   999         -         pLevel0->iCur = pParse->nTab++;
  1000         -       }
  1001         -       pLevel0->bRev = bRev;
  1002         -       *ppOrderBy = 0;
  1003         -     }
          888  +    Index *pIdx;             /* Index derived from the WHERE clause */
          889  +    Table *pTab;             /* Left-most table in the FROM clause */
          890  +    int bRev = 0;            /* True to reverse the output order */
          891  +    int iCur;                /* Btree-cursor that will be used by pTab */
          892  +    WhereLevel *pLevel0 = &pWInfo->a[0];
          893  +
          894  +    pTab = pTabList->a[0].pTab;
          895  +    pIdx = pLevel0->pIdx;
          896  +    iCur = pTabList->a[0].iCursor;
          897  +    if( pIdx==0 && sortableByRowid(iCur, *ppOrderBy, &bRev) ){
          898  +      /* The ORDER BY clause specifies ROWID order, which is what we
          899  +      ** were going to be doing anyway...
          900  +      */
          901  +      *ppOrderBy = 0;
          902  +      pLevel0->bRev = bRev;
          903  +    }else if( pLevel0->score==16 ){
          904  +      /* If there is already an IN index on the left-most table,
          905  +      ** it will not give the correct sort order.
          906  +      ** So, pretend that no suitable index is found.
          907  +      */
          908  +    }else if( iDirectEq[0]>=0 || iDirectLt[0]>=0 || iDirectGt[0]>=0 ){
          909  +      /* If the left-most column is accessed using its ROWID, then do
          910  +      ** not try to sort by index.  But do delete the ORDER BY clause
          911  +      ** if it is redundant.
          912  +      */
          913  +    }else if( (pLevel0->score&2)!=0 ){
          914  +      /* The index that was selected for searching will cause rows to
          915  +      ** appear in sorted order.
          916  +      */
          917  +      *ppOrderBy = 0;
          918  +    }
  1004    919     }
  1005    920   
  1006         -  /* Open all tables in the pTabList and all indices used by those tables.
          921  +  /* Open all tables in the pTabList and any indices selected for
          922  +  ** searching those tables.
  1007    923     */
  1008    924     sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  1009         -  for(i=0; i<pTabList->nSrc; i++){
          925  +  pLevel = pWInfo->a;
          926  +  for(i=0, pTabItem=pTabList->a; i<pTabList->nSrc; i++, pTabItem++, pLevel++){
  1010    927       Table *pTab;
  1011    928       Index *pIx;
          929  +    int iIdxCur = pLevel->iIdxCur;
  1012    930   
  1013         -    pTab = pTabList->a[i].pTab;
          931  +    pTab = pTabItem->pTab;
  1014    932       if( pTab->isTransient || pTab->pSelect ) continue;
  1015         -    sqlite3OpenTableForReading(v, pTabList->a[i].iCursor, pTab);
  1016         -    sqlite3CodeVerifySchema(pParse, pTab->iDb);
  1017         -    if( (pIx = pWInfo->a[i].pIdx)!=0 ){
          933  +    if( (pLevel->score & 1)==0 ){
          934  +      sqlite3OpenTableForReading(v, pTabItem->iCursor, pTab);
          935  +    }
          936  +    pLevel->iTabCur = pTabItem->iCursor;
          937  +    if( (pIx = pLevel->pIdx)!=0 ){
  1018    938         sqlite3VdbeAddOp(v, OP_Integer, pIx->iDb, 0);
  1019         -      sqlite3VdbeOp3(v, OP_OpenRead, pWInfo->a[i].iCur, pIx->tnum,
          939  +      sqlite3VdbeOp3(v, OP_OpenRead, iIdxCur, pIx->tnum,
  1020    940                        (char*)&pIx->keyInfo, P3_KEYINFO);
  1021    941       }
          942  +    if( (pLevel->score & 1)!=0 ){
          943  +      sqlite3VdbeAddOp(v, OP_KeyAsData, iIdxCur, 1);
          944  +      sqlite3VdbeAddOp(v, OP_SetNumColumns, iIdxCur, pIx->nColumn+1);
          945  +    }
          946  +    sqlite3CodeVerifySchema(pParse, pTab->iDb);
  1022    947     }
          948  +  pWInfo->iTop = sqlite3VdbeCurrentAddr(v);
  1023    949   
  1024    950     /* Generate the code to do the search
  1025    951     */
  1026    952     loopMask = 0;
  1027         -  for(i=0; i<pTabList->nSrc; i++){
          953  +  pLevel = pWInfo->a;
          954  +  pTabItem = pTabList->a;
          955  +  for(i=0; i<pTabList->nSrc; i++, pTabItem++, pLevel++){
  1028    956       int j, k;
  1029         -    int iCur = pTabList->a[i].iCursor;
  1030         -    Index *pIdx;
  1031         -    WhereLevel *pLevel = &pWInfo->a[i];
          957  +    int iCur = pTabItem->iCursor;  /* The VDBE cursor for the table */
          958  +    Index *pIdx;       /* The index we will be using */
          959  +    int iIdxCur;       /* The VDBE cursor for the index */
          960  +    int omitTable;     /* True if we use the index only */
          961  +
          962  +    pIdx = pLevel->pIdx;
          963  +    iIdxCur = pLevel->iIdxCur;
          964  +    pLevel->inOp = OP_Noop;
          965  +
          966  +    /* Check to see if it is appropriate to omit the use of the table
          967  +    ** here and use its index instead.
          968  +    */
          969  +    omitTable = (pLevel->score&1)!=0;
  1032    970   
  1033    971       /* If this is the right table of a LEFT OUTER JOIN, allocate and
  1034    972       ** initialize a memory cell that records if this table matches any
  1035    973       ** row of the left table of the join.
  1036    974       */
  1037    975       if( i>0 && (pTabList->a[i-1].jointype & JT_LEFT)!=0 ){
  1038    976         if( !pParse->nMem ) pParse->nMem++;
  1039    977         pLevel->iLeftJoin = pParse->nMem++;
  1040    978         sqlite3VdbeAddOp(v, OP_String8, 0, 0);
  1041    979         sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
  1042    980         VdbeComment((v, "# init LEFT JOIN no-match flag"));
  1043    981       }
  1044    982   
  1045         -    pIdx = pLevel->pIdx;
  1046         -    pLevel->inOp = OP_Noop;
  1047    983       if( i<ARRAYSIZE(iDirectEq) && (k = iDirectEq[i])>=0 ){
  1048    984         /* Case 1:  We can directly reference a single row using an
  1049    985         **          equality comparison against the ROWID field.  Or
  1050    986         **          we reference multiple rows using a "rowid IN (...)"
  1051    987         **          construct.
  1052    988         */
  1053    989         assert( k<nExpr );
  1054    990         pTerm = &aExpr[k];
  1055    991         assert( pTerm->p!=0 );
  1056    992         assert( pTerm->idxLeft==iCur );
          993  +      assert( omitTable==0 );
  1057    994         brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
  1058    995         codeEqualityTerm(pParse, pTerm, brk, pLevel);
  1059    996         cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
  1060    997         sqlite3VdbeAddOp(v, OP_MustBeInt, 1, brk);
  1061         -      haveKey = 0;
  1062    998         sqlite3VdbeAddOp(v, OP_NotExists, iCur, brk);
          999  +      haveRowid = 0;
  1063   1000         pLevel->op = OP_Noop;
  1064         -    }else if( pIdx!=0 && pLevel->score>0 && (pLevel->score&0x0c)==0 ){
         1001  +    }else if( pIdx!=0 && pLevel->score>3 && (pLevel->score&0x0c)==0 ){
  1065   1002         /* Case 2:  There is an index and all terms of the WHERE clause that
  1066   1003         **          refer to the index using the "==" or "IN" operators.
  1067   1004         */
  1068   1005         int start;
  1069   1006         int nColumn = (pLevel->score+16)/32;
  1070   1007         brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
  1071   1008   
................................................................................
  1096   1033         /* Generate code (1) to move to the first matching element of the table.
  1097   1034         ** Then generate code (2) that jumps to "brk" after the cursor is past
  1098   1035         ** the last matching element of the table.  The code (1) is executed
  1099   1036         ** once to initialize the search, the code (2) is executed before each
  1100   1037         ** iteration of the scan to see if the scan has finished. */
  1101   1038         if( pLevel->bRev ){
  1102   1039           /* Scan in reverse order */
  1103         -        sqlite3VdbeAddOp(v, OP_MoveLe, pLevel->iCur, brk);
         1040  +        sqlite3VdbeAddOp(v, OP_MoveLe, iIdxCur, brk);
  1104   1041           start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
  1105         -        sqlite3VdbeAddOp(v, OP_IdxLT, pLevel->iCur, brk);
         1042  +        sqlite3VdbeAddOp(v, OP_IdxLT, iIdxCur, brk);
  1106   1043           pLevel->op = OP_Prev;
  1107   1044         }else{
  1108   1045           /* Scan in the forward order */
  1109         -        sqlite3VdbeAddOp(v, OP_MoveGe, pLevel->iCur, brk);
         1046  +        sqlite3VdbeAddOp(v, OP_MoveGe, iIdxCur, brk);
  1110   1047           start = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
  1111         -        sqlite3VdbeOp3(v, OP_IdxGE, pLevel->iCur, brk, "+", P3_STATIC);
         1048  +        sqlite3VdbeOp3(v, OP_IdxGE, iIdxCur, brk, "+", P3_STATIC);
  1112   1049           pLevel->op = OP_Next;
  1113   1050         }
  1114         -      sqlite3VdbeAddOp(v, OP_RowKey, pLevel->iCur, 0);
         1051  +      sqlite3VdbeAddOp(v, OP_RowKey, iIdxCur, 0);
  1115   1052         sqlite3VdbeAddOp(v, OP_IdxIsNull, nColumn, cont);
  1116         -      sqlite3VdbeAddOp(v, OP_IdxRecno, pLevel->iCur, 0);
  1117         -      if( i==pTabList->nSrc-1 && pushKey ){
  1118         -        haveKey = 1;
         1053  +      if( omitTable ){
         1054  +        haveRowid = 0;
  1119   1055         }else{
  1120         -        sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
  1121         -        haveKey = 0;
         1056  +        sqlite3VdbeAddOp(v, OP_IdxRecno, iIdxCur, 0);
         1057  +        haveRowid = 1;
  1122   1058         }
  1123         -      pLevel->p1 = pLevel->iCur;
         1059  +      pLevel->p1 = iIdxCur;
  1124   1060         pLevel->p2 = start;
  1125   1061       }else if( i<ARRAYSIZE(iDirectLt) && (iDirectLt[i]>=0 || iDirectGt[i]>=0) ){
  1126   1062         /* Case 3:  We have an inequality comparison against the ROWID field.
  1127   1063         */
  1128   1064         int testOp = OP_Noop;
  1129   1065         int start;
  1130   1066         int bRev = pLevel->bRev;
  1131   1067   
         1068  +      assert( omitTable==0 );
  1132   1069         brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
  1133   1070         cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
  1134   1071         if( bRev ){
  1135   1072           int t = iDirectGt[i];
  1136   1073           iDirectGt[i] = iDirectLt[i];
  1137   1074           iDirectLt[i] = t;
  1138   1075         }
................................................................................
  1174   1111         pLevel->p1 = iCur;
  1175   1112         pLevel->p2 = start;
  1176   1113         if( testOp!=OP_Noop ){
  1177   1114           sqlite3VdbeAddOp(v, OP_Recno, iCur, 0);
  1178   1115           sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
  1179   1116           sqlite3VdbeAddOp(v, testOp, 0, brk);
  1180   1117         }
  1181         -      haveKey = 0;
         1118  +      haveRowid = 0;
  1182   1119       }else if( pIdx==0 ){
  1183   1120         /* Case 4:  There is no usable index.  We must do a complete
  1184   1121         **          scan of the entire database table.
  1185   1122         */
  1186   1123         int start;
  1187   1124         int opRewind;
  1188   1125   
         1126  +      assert( omitTable==0 );
  1189   1127         brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
  1190   1128         cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
  1191   1129         if( pLevel->bRev ){
  1192   1130           opRewind = OP_Last;
  1193   1131           pLevel->op = OP_Prev;
  1194   1132         }else{
  1195   1133           opRewind = OP_Rewind;
  1196   1134           pLevel->op = OP_Next;
  1197   1135         }
  1198   1136         sqlite3VdbeAddOp(v, opRewind, iCur, brk);
  1199   1137         start = sqlite3VdbeCurrentAddr(v);
  1200   1138         pLevel->p1 = iCur;
  1201   1139         pLevel->p2 = start;
  1202         -      haveKey = 0;
         1140  +      haveRowid = 0;
  1203   1141       }else{
  1204   1142         /* Case 5: The WHERE clause term that refers to the right-most
  1205   1143         **         column of the index is an inequality.  For example, if
  1206   1144         **         the index is on (x,y,z) and the WHERE clause is of the
  1207   1145         **         form "x=5 AND y<10" then this case is used.  Only the
  1208   1146         **         right-most column can be an inequality - the rest must
  1209   1147         **         use the "==" operator.
................................................................................
  1279   1217         }
  1280   1218         if( testOp!=OP_Noop ){
  1281   1219           int nCol = nEqColumn + ((score & 4)!=0);
  1282   1220           pLevel->iMem = pParse->nMem++;
  1283   1221           buildIndexProbe(v, nCol, brk, pIdx);
  1284   1222           if( pLevel->bRev ){
  1285   1223             int op = leFlag ? OP_MoveLe : OP_MoveLt;
  1286         -          sqlite3VdbeAddOp(v, op, pLevel->iCur, brk);
         1224  +          sqlite3VdbeAddOp(v, op, iIdxCur, brk);
  1287   1225           }else{
  1288   1226             sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
  1289   1227           }
  1290   1228         }else if( pLevel->bRev ){
  1291         -        sqlite3VdbeAddOp(v, OP_Last, pLevel->iCur, brk);
         1229  +        sqlite3VdbeAddOp(v, OP_Last, iIdxCur, brk);
  1292   1230         }
  1293   1231   
  1294   1232         /* Generate the start key.  This is the key that defines the lower
  1295   1233         ** bound on the search.  There is no start key if there are no
  1296   1234         ** equality terms and if there is no "X>..." term.  In
  1297   1235         ** that case, generate a "Rewind" instruction in place of the
  1298   1236         ** start key search.
................................................................................
  1323   1261           buildIndexProbe(v, nCol, brk, pIdx);
  1324   1262           if( pLevel->bRev ){
  1325   1263             pLevel->iMem = pParse->nMem++;
  1326   1264             sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
  1327   1265             testOp = OP_IdxLT;
  1328   1266           }else{
  1329   1267             int op = geFlag ? OP_MoveGe : OP_MoveGt;
  1330         -          sqlite3VdbeAddOp(v, op, pLevel->iCur, brk);
         1268  +          sqlite3VdbeAddOp(v, op, iIdxCur, brk);
  1331   1269           }
  1332   1270         }else if( pLevel->bRev ){
  1333   1271           testOp = OP_Noop;
  1334   1272         }else{
  1335         -        sqlite3VdbeAddOp(v, OP_Rewind, pLevel->iCur, brk);
         1273  +        sqlite3VdbeAddOp(v, OP_Rewind, iIdxCur, brk);
  1336   1274         }
  1337   1275   
  1338   1276         /* Generate the the top of the loop.  If there is a termination
  1339   1277         ** key we have to test for that key and abort at the top of the
  1340   1278         ** loop.
  1341   1279         */
  1342   1280         start = sqlite3VdbeCurrentAddr(v);
  1343   1281         if( testOp!=OP_Noop ){
  1344   1282           sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
  1345         -        sqlite3VdbeAddOp(v, testOp, pLevel->iCur, brk);
         1283  +        sqlite3VdbeAddOp(v, testOp, iIdxCur, brk);
  1346   1284           if( (leFlag && !pLevel->bRev) || (!geFlag && pLevel->bRev) ){
  1347   1285             sqlite3VdbeChangeP3(v, -1, "+", P3_STATIC);
  1348   1286           }
  1349   1287         }
  1350         -      sqlite3VdbeAddOp(v, OP_RowKey, pLevel->iCur, 0);
         1288  +      sqlite3VdbeAddOp(v, OP_RowKey, iIdxCur, 0);
  1351   1289         sqlite3VdbeAddOp(v, OP_IdxIsNull, nEqColumn + ((score&4)!=0), cont);
  1352         -      sqlite3VdbeAddOp(v, OP_IdxRecno, pLevel->iCur, 0);
  1353         -      if( i==pTabList->nSrc-1 && pushKey ){
  1354         -        haveKey = 1;
         1290  +      if( omitTable ){
         1291  +        haveRowid = 0;
  1355   1292         }else{
  1356         -        sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
  1357         -        haveKey = 0;
         1293  +        sqlite3VdbeAddOp(v, OP_IdxRecno, iIdxCur, 0);
         1294  +        haveRowid = 1;
  1358   1295         }
  1359   1296   
  1360   1297         /* Record the instruction used to terminate the loop.
  1361   1298         */
  1362   1299         pLevel->op = pLevel->bRev ? OP_Prev : OP_Next;
  1363         -      pLevel->p1 = pLevel->iCur;
         1300  +      pLevel->p1 = iIdxCur;
  1364   1301         pLevel->p2 = start;
  1365   1302       }
  1366   1303       loopMask |= getMask(&maskSet, iCur);
  1367   1304   
  1368   1305       /* Insert code to test every subexpression that can be completely
  1369   1306       ** computed using the current set of tables.
  1370   1307       */
  1371   1308       for(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
  1372   1309         if( pTerm->p==0 ) continue;
  1373   1310         if( (pTerm->prereqAll & loopMask)!=pTerm->prereqAll ) continue;
  1374   1311         if( pLevel->iLeftJoin && !ExprHasProperty(pTerm->p,EP_FromJoin) ){
  1375   1312           continue;
  1376   1313         }
  1377         -      if( haveKey ){
  1378         -        haveKey = 0;
  1379         -        sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
         1314  +      if( haveRowid ){
         1315  +        haveRowid = 0;
         1316  +        if( omitTable ){
         1317  +          sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
         1318  +        }else{
         1319  +          sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
         1320  +        }
  1380   1321         }
  1381   1322         sqlite3ExprIfFalse(pParse, pTerm->p, cont, 1);
  1382   1323         pTerm->p = 0;
  1383   1324       }
  1384   1325       brk = cont;
  1385   1326   
  1386   1327       /* For a LEFT OUTER JOIN, generate code that will record the fact that
................................................................................
  1390   1331         pLevel->top = sqlite3VdbeCurrentAddr(v);
  1391   1332         sqlite3VdbeAddOp(v, OP_Integer, 1, 0);
  1392   1333         sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
  1393   1334         VdbeComment((v, "# record LEFT JOIN hit"));
  1394   1335         for(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
  1395   1336           if( pTerm->p==0 ) continue;
  1396   1337           if( (pTerm->prereqAll & loopMask)!=pTerm->prereqAll ) continue;
  1397         -        if( haveKey ){
  1398         -          /* Cannot happen.  "haveKey" can only be true if pushKey is true
         1338  +        if( haveRowid ){
         1339  +          /* Cannot happen.  "haveRowid" can only be true if pushKey is true
  1399   1340             ** an pushKey can only be true for DELETE and UPDATE and there are
  1400   1341             ** no outer joins with DELETE and UPDATE.
  1401   1342             */
  1402         -          haveKey = 0;
         1343  +          assert( 0 );
         1344  +          haveRowid = 0;
  1403   1345             sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
  1404   1346           }
  1405   1347           sqlite3ExprIfFalse(pParse, pTerm->p, cont, 1);
  1406   1348           pTerm->p = 0;
  1407   1349         }
  1408   1350       }
         1351  +
         1352  +    if( haveRowid && (i<pTabList->nSrc-1 || !pushKey) ){
         1353  +      haveRowid = 0;
         1354  +      if( omitTable ){
         1355  +        sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
         1356  +      }else{
         1357  +        sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
         1358  +      }
         1359  +    }    
  1409   1360     }
  1410   1361     pWInfo->iContinue = cont;
  1411         -  if( pushKey && !haveKey ){
         1362  +  if( pushKey && !haveRowid ){
  1412   1363       sqlite3VdbeAddOp(v, OP_Recno, pTabList->a[0].iCursor, 0);
  1413   1364     }
  1414   1365     freeMaskSet(&maskSet);
  1415   1366     return pWInfo;
  1416   1367   }
  1417   1368   
  1418   1369   /*
................................................................................
  1420   1371   ** sqlite3WhereBegin() for additional information.
  1421   1372   */
  1422   1373   void sqlite3WhereEnd(WhereInfo *pWInfo){
  1423   1374     Vdbe *v = pWInfo->pParse->pVdbe;
  1424   1375     int i;
  1425   1376     WhereLevel *pLevel;
  1426   1377     SrcList *pTabList = pWInfo->pTabList;
         1378  +  struct SrcList_item *pTabItem;
  1427   1379   
         1380  +  /* Generate loop termination code.
         1381  +  */
  1428   1382     for(i=pTabList->nSrc-1; i>=0; i--){
  1429   1383       pLevel = &pWInfo->a[i];
  1430   1384       sqlite3VdbeResolveLabel(v, pLevel->cont);
  1431   1385       if( pLevel->op!=OP_Noop ){
  1432   1386         sqlite3VdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2);
  1433   1387       }
  1434   1388       sqlite3VdbeResolveLabel(v, pLevel->brk);
  1435   1389       if( pLevel->inOp!=OP_Noop ){
  1436   1390         sqlite3VdbeAddOp(v, pLevel->inOp, pLevel->inP1, pLevel->inP2);
  1437   1391       }
  1438   1392       if( pLevel->iLeftJoin ){
  1439   1393         int addr;
  1440   1394         addr = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iLeftJoin, 0);
  1441         -      sqlite3VdbeAddOp(v, OP_NotNull, 1, addr+4 + (pLevel->iCur>=0));
         1395  +      sqlite3VdbeAddOp(v, OP_NotNull, 1, addr+4 + (pLevel->iIdxCur>=0));
  1442   1396         sqlite3VdbeAddOp(v, OP_NullRow, pTabList->a[i].iCursor, 0);
  1443         -      if( pLevel->iCur>=0 ){
  1444         -        sqlite3VdbeAddOp(v, OP_NullRow, pLevel->iCur, 0);
         1397  +      if( pLevel->iIdxCur>=0 ){
         1398  +        sqlite3VdbeAddOp(v, OP_NullRow, pLevel->iIdxCur, 0);
  1445   1399         }
  1446   1400         sqlite3VdbeAddOp(v, OP_Goto, 0, pLevel->top);
  1447   1401       }
  1448   1402     }
         1403  +
         1404  +  /* The "break" point is here, just past the end of the outer loop.
         1405  +  ** Set it.
         1406  +  */
  1449   1407     sqlite3VdbeResolveLabel(v, pWInfo->iBreak);
  1450         -  for(i=0; i<pTabList->nSrc; i++){
  1451         -    Table *pTab = pTabList->a[i].pTab;
         1408  +
         1409  +  /* Close all of the cursors
         1410  +  */
         1411  +  pLevel = pWInfo->a;
         1412  +  pTabItem = pTabList->a;
         1413  +  for(i=0; i<pTabList->nSrc; i++, pTabItem++, pLevel++){
         1414  +    Table *pTab = pTabItem->pTab;
  1452   1415       assert( pTab!=0 );
  1453   1416       if( pTab->isTransient || pTab->pSelect ) continue;
  1454         -    pLevel = &pWInfo->a[i];
  1455         -    sqlite3VdbeAddOp(v, OP_Close, pTabList->a[i].iCursor, 0);
         1417  +    if( (pLevel->score & 1)==0 ){
         1418  +      sqlite3VdbeAddOp(v, OP_Close, pTabItem->iCursor, 0);
         1419  +    }
  1456   1420       if( pLevel->pIdx!=0 ){
  1457         -      sqlite3VdbeAddOp(v, OP_Close, pLevel->iCur, 0);
         1421  +      sqlite3VdbeAddOp(v, OP_Close, pLevel->iIdxCur, 0);
         1422  +    }
         1423  +
         1424  +    /* Make all cursor substitutions for cases where we want to use
         1425  +    ** just the index and never reference the table.
         1426  +    ** 
         1427  +    ** Calls to the code generator in between sqlite3WhereBegin and
         1428  +    ** sqlite3WhereEnd will have created code that references the table
         1429  +    ** directly.  This loop scans all that code looking for opcodes
         1430  +    ** that reference the table and converts them into opcodes that
         1431  +    ** reference the index.
         1432  +    */
         1433  +    if( pLevel->score & 1 ){
         1434  +      int i, j, last;
         1435  +      VdbeOp *pOp;
         1436  +      Index *pIdx = pLevel->pIdx;
         1437  +
         1438  +      assert( pIdx!=0 );
         1439  +      pOp = sqlite3VdbeGetOp(v, pWInfo->iTop);
         1440  +      last = sqlite3VdbeCurrentAddr(v);
         1441  +      for(i=pWInfo->iTop; i<last; i++, pOp++){
         1442  +        if( pOp->p1!=pLevel->iTabCur ) continue;
         1443  +        if( pOp->opcode==OP_Column ){
         1444  +          pOp->p1 = pLevel->iIdxCur;
         1445  +          for(j=0; j<pIdx->nColumn; j++){
         1446  +            if( pOp->p2==pIdx->aiColumn[j] ){
         1447  +              pOp->p2 = j;
         1448  +              break;
         1449  +            }
         1450  +          }
         1451  +        }else if( pOp->opcode==OP_Recno ){
         1452  +          pOp->p1 = pLevel->iIdxCur;
         1453  +          pOp->opcode = OP_IdxRecno;
         1454  +        }
         1455  +      }
  1458   1456       }
  1459   1457     }
         1458  +
         1459  +  /* Final cleanup
         1460  +  */
  1460   1461     sqliteFree(pWInfo);
  1461   1462     return;
  1462   1463   }

Changes to test/collate4.test.

     8      8   #    May you find forgiveness for yourself and forgive others.
     9      9   #    May you share freely, never taking more than you give.
    10     10   #
    11     11   #***********************************************************************
    12     12   # This file implements regression tests for SQLite library.  The
    13     13   # focus of this script is page cache subsystem.
    14     14   #
    15         -# $Id: collate4.test,v 1.5 2004/11/22 19:12:21 drh Exp $
           15  +# $Id: collate4.test,v 1.6 2004/12/19 00:11:36 drh Exp $
    16     16   
    17     17   set testdir [file dirname $argv0]
    18     18   source $testdir/tester.tcl
    19     19   
    20     20   db collate TEXT text_collate
    21     21   proc text_collate {a b} {
    22     22     return [string compare $a $b]
................................................................................
   347    347   do_test collate4-2.1.2 {
   348    348     execsql {
   349    349       CREATE INDEX collate4i1 ON collate4t1(a);
   350    350     }
   351    351     count {
   352    352       SELECT * FROM collate4t2, collate4t1 WHERE a = b;
   353    353     }
   354         -} {A a A A 7}
          354  +} {A a A A 5}
   355    355   do_test collate4-2.1.3 {
   356    356     count {
   357    357       SELECT * FROM collate4t2, collate4t1 WHERE b = a;
   358    358     }
   359    359   } {A A 19}
   360    360   do_test collate4-2.1.4 {
   361    361     execsql {
................................................................................
   366    366       SELECT * FROM collate4t2, collate4t1 WHERE a = b;
   367    367     }
   368    368   } {A a A A 19}
   369    369   do_test collate4-2.1.5 {
   370    370     count {
   371    371       SELECT * FROM collate4t2, collate4t1 WHERE b = a;
   372    372     }
   373         -} {A A 5}
          373  +} {A A 4}
   374    374   do_test collate4-2.1.6 {
   375    375     count {
   376    376       SELECT a FROM collate4t1 WHERE a IN (SELECT * FROM collate4t2);
   377    377     }
   378    378   } {a A 10}
   379    379   do_test collate4-2.1.7 {
   380    380     execsql {
   381    381       DROP INDEX collate4i1;
   382    382       CREATE INDEX collate4i1 ON collate4t1(a);
   383    383     }
   384    384     count {
   385    385       SELECT a FROM collate4t1 WHERE a IN (SELECT * FROM collate4t2);
   386    386     }
   387         -} {a A 8}
          387  +} {a A 6}
   388    388   do_test collate4-2.1.8 {
   389    389     count {
   390    390       SELECT a FROM collate4t1 WHERE a IN ('z', 'a');
   391    391     }
   392         -} {a A 7}
          392  +} {a A 5}
   393    393   do_test collate4-2.1.9 {
   394    394     execsql {
   395    395       DROP INDEX collate4i1;
   396    396       CREATE INDEX collate4i1 ON collate4t1(a COLLATE TEXT);
   397    397     }
   398    398     count {
   399    399       SELECT a FROM collate4t1 WHERE a IN ('z', 'a');
................................................................................
   423    423     }
   424    424   } {}
   425    425   do_test collate4-2.2.1 {
   426    426     count {
   427    427       SELECT * FROM collate4t2 NATURAL JOIN collate4t1;
   428    428     }
   429    429   } {0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 63}
   430         -do_test collate4-2.2.1 {
          430  +do_test collate4-2.2.1b {
   431    431     execsql {
   432    432       CREATE INDEX collate4i1 ON collate4t1(a, b, c);
   433    433     }
   434    434     count {
   435    435       SELECT * FROM collate4t2 NATURAL JOIN collate4t1;
   436    436     }
   437         -} {0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 45}
          437  +} {0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 29}
   438    438   do_test collate4-2.2.2 {
   439    439     execsql {
   440    440       DROP INDEX collate4i1;
   441    441       CREATE INDEX collate4i1 ON collate4t1(a, b, c COLLATE text);
   442    442     }
   443    443     count {
   444    444       SELECT * FROM collate4t2 NATURAL JOIN collate4t1;

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.25 2004/12/18 18:40:28 drh Exp $
           14  +# $Id: where.test,v 1.26 2004/12/19 00:11:36 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 {
................................................................................
   147    147   do_test where-1.29 {
   148    148     count {SELECT w FROM t1 WHERE y==121}
   149    149   } {10 99}
   150    150   
   151    151   
   152    152   do_test where-1.30 {
   153    153     count {SELECT w FROM t1 WHERE w>97}
   154         -} {98 99 100 6}
          154  +} {98 99 100 3}
   155    155   do_test where-1.31 {
   156    156     count {SELECT w FROM t1 WHERE w>=97}
   157         -} {97 98 99 100 8}
          157  +} {97 98 99 100 4}
   158    158   do_test where-1.33 {
   159    159     count {SELECT w FROM t1 WHERE w==97}
   160         -} {97 3}
          160  +} {97 2}
   161    161   do_test where-1.34 {
   162    162     count {SELECT w FROM t1 WHERE w+1==98}
   163    163   } {97 99}
   164    164   do_test where-1.35 {
   165    165     count {SELECT w FROM t1 WHERE w<3}
   166         -} {1 2 4}
          166  +} {1 2 2}
   167    167   do_test where-1.36 {
   168    168     count {SELECT w FROM t1 WHERE w<=3}
   169         -} {1 2 3 6}
          169  +} {1 2 3 3}
   170    170   do_test where-1.37 {
   171    171     count {SELECT w FROM t1 WHERE w+1<=4 ORDER BY w}
   172         -} {1 2 3 199}
          172  +} {1 2 3 99}
   173    173   
   174    174   do_test where-1.38 {
   175    175     count {SELECT (w) FROM t1 WHERE (w)>(97)}
   176         -} {98 99 100 6}
          176  +} {98 99 100 3}
   177    177   do_test where-1.39 {
   178    178     count {SELECT (w) FROM t1 WHERE (w)>=(97)}
   179         -} {97 98 99 100 8}
          179  +} {97 98 99 100 4}
   180    180   do_test where-1.40 {
   181    181     count {SELECT (w) FROM t1 WHERE (w)==(97)}
   182         -} {97 3}
          182  +} {97 2}
   183    183   do_test where-1.41 {
   184    184     count {SELECT (w) FROM t1 WHERE ((w)+(1))==(98)}
   185    185   } {97 99}
   186    186   
   187    187   
   188    188   # Do the same kind of thing except use a join as the data source.
   189    189   #
................................................................................
   233    233   # Lets do a 3-way join.
   234    234   #
   235    235   do_test where-3.1 {
   236    236     count {
   237    237       SELECT A.w, B.p, C.w FROM t1 as A, t2 as B, t1 as C
   238    238       WHERE C.w=101-B.p AND B.r=10202-A.y AND A.w=11
   239    239     }
   240         -} {11 90 11 9}
          240  +} {11 90 11 8}
   241    241   do_test where-3.2 {
   242    242     count {
   243    243       SELECT A.w, B.p, C.w FROM t1 as A, t2 as B, t1 as C
   244    244       WHERE C.w=101-B.p AND B.r=10202-A.y AND A.w=12
   245    245     }
   246         -} {12 89 12 9}
          246  +} {12 89 12 8}
   247    247   do_test where-3.3 {
   248    248     count {
   249    249       SELECT A.w, B.p, C.w FROM t1 as A, t2 as B, t1 as C
   250    250       WHERE A.w=15 AND B.p=C.w AND B.r=10202-A.y
   251    251     }
   252         -} {15 86 86 9}
          252  +} {15 86 86 8}
   253    253   
   254    254   # Test to see that the special case of a constant WHERE clause is
   255    255   # handled.
   256    256   #
   257    257   do_test where-4.1 {
   258    258     count {
   259    259       SELECT * FROM t1 WHERE 0
................................................................................
   413    413       SELECT * FROM t3 WHERE b>0 ORDER BY a LIMIT 3
   414    414     }
   415    415   } {1 100 4 2 99 9 3 98 16 sort}
   416    416   do_test where-6.8 {
   417    417     cksort {
   418    418       SELECT * FROM t3 WHERE a IN (3,5,7,1,9,4,2) ORDER BY a LIMIT 3
   419    419     }
   420         -} {1 100 4 2 99 9 3 98 16 nosort}
          420  +} {1 100 4 2 99 9 3 98 16 sort}
   421    421   do_test where-6.9.1 {
   422    422     cksort {
   423    423       SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a LIMIT 3
   424    424     }
   425    425   } {1 100 4 nosort}
   426    426   do_test where-6.9.2 {
   427    427     cksort {
................................................................................
   453    453       SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY c,a LIMIT 3
   454    454     }
   455    455   } {1 100 4 sort}
   456    456   do_test where-6.9.8 {
   457    457     cksort {
   458    458       SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a DESC, c ASC LIMIT 3
   459    459     }
   460         -} {1 100 4 sort}
          460  +} {1 100 4 nosort}
   461    461   do_test where-6.9.9 {
   462    462     cksort {
   463    463       SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a ASC, c DESC LIMIT 3
   464    464     }
   465         -} {1 100 4 sort}
          465  +} {1 100 4 nosort}
   466    466   do_test where-6.10 {
   467    467     cksort {
   468    468       SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a LIMIT 3
   469    469     }
   470    470   } {1 100 4 nosort}
   471    471   do_test where-6.11 {
   472    472     cksort {