Experimental attempt to make better use of covering indexes within OR queries.

FossilOrigin-Name: a323ac3a9d42bd5cb38d724c7e1180584b91054c

4 files changed, 76 insertions, 8 deletions

diff --git a/src/vdbe.c b/src/vdbe.c
index cfff895c3..8ad1a17c3 100644
--- a/src/vdbe.c
+++ b/src/vdbe.c
@@ -2376,12 +2376,16 @@ case OP_Column: {
   u32 t;             /* A type code from the record header */
   Mem *pReg;         /* PseudoTable input register */
 
+  pC = p->apCsr[pOp->p1];
   p2 = pOp->p2;
+
+  /* If the cursor cache is stale, bring it up-to-date */
+  rc = sqlite3VdbeCursorMoveto(&pC, &p2);
+
   assert( pOp->p3>0 && pOp->p3<=(p->nMem-p->nCursor) );
   pDest = &aMem[pOp->p3];
   memAboutToChange(p, pDest);
   assert( pOp->p1>=0 && pOp->p1<p->nCursor );
-  pC = p->apCsr[pOp->p1];
   assert( pC!=0 );
   assert( p2<pC->nField );
   aOffset = pC->aOffset;
@@ -2390,8 +2394,6 @@ case OP_Column: {
   assert( pC->eCurType!=CURTYPE_SORTER );
   pCrsr = pC->uc.pCursor;
 
-  /* If the cursor cache is stale, bring it up-to-date */
-  rc = sqlite3VdbeCursorMoveto(pC);
   if( rc ) goto abort_due_to_error;
   if( pC->cacheStatus!=p->cacheCtr ){
     if( pC->nullRow ){
@@ -3846,7 +3848,7 @@ seek_not_found:
   break;
 }
 
-/* Opcode: Seek P1 P2 * * *
+/* Opcode: Seek P1 P2 P3 P4 *
 ** Synopsis:  intkey=r[P2]
 **
 ** P1 is an open table cursor and P2 is a rowid integer.  Arrange
@@ -3855,6 +3857,13 @@ seek_not_found:
 ** This is actually a deferred seek.  Nothing actually happens until
 ** the cursor is used to read a record.  That way, if no reads
 ** occur, no unnecessary I/O happens.
+**
+** P4 may contain an array of integers (type P4_INTARRAY) containing
+** one entry for each column in the table P1 is open on. If so, then
+** parameter P3 is a cursor open on a database index. If array entry
+** a[i] is non-zero, then reading column (a[i]-1) from cursor P3 is 
+** equivalent to performing the deferred seek and then reading column i 
+** from P1.
 */
 case OP_Seek: {    /* in2 */
   VdbeCursor *pC;
@@ -3869,6 +3878,9 @@ case OP_Seek: {    /* in2 */
   pIn2 = &aMem[pOp->p2];
   pC->movetoTarget = sqlite3VdbeIntValue(pIn2);
   pC->deferredMoveto = 1;
+  assert( pOp->p4type==P4_INTARRAY || pOp->p4.ai==0 );
+  pC->aAltMap = pOp->p4.ai;
+  pC->pAltCursor = p->apCsr[pOp->p3];
   break;
 }
   
diff --git a/src/vdbeInt.h b/src/vdbeInt.h
index b231cf908..e1c6d0656 100644
--- a/src/vdbeInt.h
+++ b/src/vdbeInt.h
@@ -74,6 +74,7 @@ typedef struct AuxData AuxData;
 **      * A virtual table
 **      * A one-row "pseudotable" stored in a single register
 */
+typedef struct VdbeCursor VdbeCursor;
 struct VdbeCursor {
   u8 eCurType;          /* One of the CURTYPE_* values above */
   i8 iDb;               /* Index of cursor database in db->aDb[] (or -1) */
@@ -100,6 +101,8 @@ struct VdbeCursor {
   int seekResult;       /* Result of previous sqlite3BtreeMoveto() */
   i64 seqCount;         /* Sequence counter */
   i64 movetoTarget;     /* Argument to the deferred sqlite3BtreeMoveto() */
+  VdbeCursor *pAltCursor; /* Set by OP_Seek */
+  int *aAltMap;           /* Set by OP_Seek */
 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
   u64 maskUsed;         /* Mask of columns used by this cursor */
 #endif
@@ -124,7 +127,6 @@ struct VdbeCursor {
   ** static element declared in the structure.  nField total array slots for
   ** aType[] and nField+1 array slots for aOffset[] */
 };
-typedef struct VdbeCursor VdbeCursor;
 
 /*
 ** When a sub-program is executed (OP_Program), a structure of this type
@@ -423,7 +425,7 @@ struct Vdbe {
 void sqlite3VdbeError(Vdbe*, const char *, ...);
 void sqlite3VdbeFreeCursor(Vdbe *, VdbeCursor*);
 void sqliteVdbePopStack(Vdbe*,int);
-int sqlite3VdbeCursorMoveto(VdbeCursor*);
+int sqlite3VdbeCursorMoveto(VdbeCursor**, int*);
 int sqlite3VdbeCursorRestore(VdbeCursor*);
 #if defined(SQLITE_DEBUG) || defined(VDBE_PROFILE)
 void sqlite3VdbePrintOp(FILE*, int, Op*);
diff --git a/src/vdbeaux.c b/src/vdbeaux.c
index 3bbc5aad5..6e368cfdb 100644
--- a/src/vdbeaux.c
+++ b/src/vdbeaux.c
@@ -3008,9 +3008,15 @@ int sqlite3VdbeCursorRestore(VdbeCursor *p){
 ** If the cursor is already pointing to the correct row and that row has
 ** not been deleted out from under the cursor, then this routine is a no-op.
 */
-int sqlite3VdbeCursorMoveto(VdbeCursor *p){
+int sqlite3VdbeCursorMoveto(VdbeCursor **pp, int *piCol){
+  VdbeCursor *p = *pp;
   if( p->eCurType==CURTYPE_BTREE ){
     if( p->deferredMoveto ){
+      if( p->aAltMap && p->aAltMap[*piCol] ){
+        *pp = p->pAltCursor;
+        *piCol = p->aAltMap[*piCol] - 1;
+        return SQLITE_OK;
+      }
       return handleDeferredMoveto(p);
     }
     if( sqlite3BtreeCursorHasMoved(p->uc.pCursor) ){
diff --git a/src/wherecode.c b/src/wherecode.c
index 4fd7399ef..eacd6d08d 100644
--- a/src/wherecode.c
+++ b/src/wherecode.c
@@ -747,6 +747,54 @@ static void codeCursorHint(
 #endif /* SQLITE_ENABLE_CURSOR_HINTS */
 
 /*
+** Cursor iCur is open on an intkey b-tree (a table). Register iRowid contains
+** a rowid value just read from cursor iIdxCur, open on index pIdx. This
+** function generates code to do a deferred seek of cursor iCur to the 
+** rowid stored in register iRowid.
+**
+** Normally, this is just:
+**
+**   OP_Seek $iCur $iRowid
+**
+** However, if the scan currently being coded is a branch of an OR-loop and
+** the statement currently being coded is a SELECT, then P3 of the OP_Seek
+** is set to iIdxCur and P4 is set to point to an array of integers
+** containing one entry for each column of the table cursor iCur is open 
+** on. For each table column, if the column is the i'th column of the 
+** index, then the corresponding array entry is set to (i+1). If the column
+** does not appear in the index at all, the array entry is set to 0.
+*/
+static void codeDeferredSeek(
+  WhereInfo *pWInfo,              /* Where clause context */
+  Index *pIdx,                    /* Index scan is using */
+  int iCur,                       /* Cursor for IPK b-tree */
+  int iRowid,                     /* Register containing rowid to seek to */
+  int iIdxCur                     /* Index cursor */
+){
+  Parse *pParse = pWInfo->pParse; /* Parse context */
+  Vdbe *v = pParse->pVdbe;        /* Vdbe to generate code within */
+
+  assert( iIdxCur>0 );
+  assert( pIdx->aiColumn[pIdx->nColumn-1]==-1 );
+  
+  sqlite3VdbeAddOp3(v, OP_Seek, iCur, iRowid, iIdxCur);
+  if( (pWInfo->wctrlFlags & WHERE_FORCE_TABLE)
+   && sqlite3ParseToplevel(pParse)->writeMask==0 
+  ){
+    int i;
+    Table *pTab = pIdx->pTable;
+    int *ai = (int*)sqlite3DbMallocZero(pParse->db, sizeof(int) * pTab->nCol);
+    if( ai ){
+      for(i=0; i<pIdx->nColumn-1; i++){
+        assert( pIdx->aiColumn[i]<pTab->nCol );
+        if( pIdx->aiColumn[i]>=0 ) ai[pIdx->aiColumn[i]] = i+1;
+      }
+      sqlite3VdbeChangeP4(v, -1, (char*)ai, P4_INTARRAY);
+    }
+  }
+}
+
+/*
 ** Generate code for the start of the iLevel-th loop in the WHERE clause
 ** implementation described by pWInfo.
 */
@@ -1232,7 +1280,7 @@ Bitmask sqlite3WhereCodeOneLoopStart(
         sqlite3VdbeAddOp3(v, OP_NotExists, iCur, 0, iRowidReg);
         VdbeCoverage(v);
       }else{
-        sqlite3VdbeAddOp2(v, OP_Seek, iCur, iRowidReg);  /* Deferred seek */
+        codeDeferredSeek(pWInfo, pIdx, iCur, iRowidReg, iIdxCur);
       }
     }else if( iCur!=iIdxCur ){
       Index *pPk = sqlite3PrimaryKeyIndex(pIdx->pTable);