/ Check-in [32e31b9b]
Login

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

Overview
Comment:The top of an index equality loop normally starts with OP_SeekGE and OP_IdxGT. This check-in adds a flag to OP_SeekGE such that it fails immediately if the key is not equal, then jumps over the OP_IdxGT, saving a call to the key comparison functions. Consider this check-in a proof-of-concept. It needs improvement before going on trunk. Some tests fail, but only because they new use fewer key comparisons than expected (which is a good thing!).
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | seekeq-experiment
Files: files | file ages | folders
SHA1: 32e31b9bc8664afcd326a1ff3892d86dc5202474
User & Date: drh 2015-11-05 20:25:09
Context
2015-11-05
22:30
Improvements and simplifications to the equality seek logic. Tests are adjusted so that they all pass now. Closed-Leaf check-in: 997ce6c9 user: drh tags: seekeq-experiment
20:25
The top of an index equality loop normally starts with OP_SeekGE and OP_IdxGT. This check-in adds a flag to OP_SeekGE such that it fails immediately if the key is not equal, then jumps over the OP_IdxGT, saving a call to the key comparison functions. Consider this check-in a proof-of-concept. It needs improvement before going on trunk. Some tests fail, but only because they new use fewer key comparisons than expected (which is a good thing!). check-in: 32e31b9b user: drh tags: seekeq-experiment
18:09
Add the 'hashsize' configuration option to fts5, for configuring the amount of memory allocated to the in-memory hash table while writing. check-in: 44548009 user: dan tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to main.mk.

   578    578   
   579    579   
   580    580   # Rules to build opcodes.c and opcodes.h
   581    581   #
   582    582   opcodes.c:	opcodes.h $(TOP)/tool/mkopcodec.tcl
   583    583   	tclsh $(TOP)/tool/mkopcodec.tcl opcodes.h >opcodes.c
   584    584   
   585         -opcodes.h:	parse.h $(TOP)/src/vdbe.c $(TOP)/tool/mkopcodeh.tcl
          585  +opcodes.h:	parse.h $(TOP)/tool/mkopcodeh.tcl
   586    586   	cat parse.h $(TOP)/src/vdbe.c | \
   587    587   		tclsh $(TOP)/tool/mkopcodeh.tcl >opcodes.h
   588    588   
   589    589   # Rules to build parse.c and parse.h - the outputs of lemon.
   590    590   #
   591    591   parse.h:	parse.c
   592    592   

Changes to src/sqliteInt.h.

  1826   1826   ** into its constituent fields.
  1827   1827   **
  1828   1828   ** The r1 and r2 member variables are only used by the optimized comparison
  1829   1829   ** functions vdbeRecordCompareInt() and vdbeRecordCompareString().
  1830   1830   */
  1831   1831   struct UnpackedRecord {
  1832   1832     KeyInfo *pKeyInfo;  /* Collation and sort-order information */
         1833  +  Mem *aMem;          /* Values */
  1833   1834     u16 nField;         /* Number of entries in apMem[] */
  1834   1835     i8 default_rc;      /* Comparison result if keys are equal */
  1835   1836     u8 errCode;         /* Error detected by xRecordCompare (CORRUPT or NOMEM) */
  1836         -  Mem *aMem;          /* Values */
  1837         -  int r1;             /* Value to return if (lhs > rhs) */
  1838         -  int r2;             /* Value to return if (rhs < lhs) */
         1837  +  i8 r1;              /* Value to return if (lhs > rhs) */
         1838  +  i8 r2;              /* Value to return if (rhs < lhs) */
         1839  +  u8 eqSeen;          /* True if an equality comparison has been seen */
  1839   1840   };
  1840   1841   
  1841   1842   
  1842   1843   /*
  1843   1844   ** Each SQL index is represented in memory by an
  1844   1845   ** instance of the following structure.
  1845   1846   **

Changes to src/vdbe.c.

  3687   3687     /* For a cursor with the BTREE_SEEK_EQ hint, only the OP_SeekGE and
  3688   3688     ** OP_SeekLE opcodes are allowed, and these must be immediately followed
  3689   3689     ** by an OP_IdxGT or OP_IdxLT opcode, respectively, with the same key.
  3690   3690     */
  3691   3691   #ifdef SQLITE_DEBUG
  3692   3692     if( sqlite3BtreeCursorHasHint(pC->pCursor, BTREE_SEEK_EQ) ){
  3693   3693       assert( pOp->opcode==OP_SeekGE || pOp->opcode==OP_SeekLE );
         3694  +#if 0
  3694   3695       assert( pOp[1].opcode==OP_IdxLT || pOp[1].opcode==OP_IdxGT );
  3695   3696       assert( pOp[1].p1==pOp[0].p1 );
  3696   3697       assert( pOp[1].p2==pOp[0].p2 );
  3697   3698       assert( pOp[1].p3==pOp[0].p3 );
  3698   3699       assert( pOp[1].p4.i==pOp[0].p4.i );
         3700  +#endif
  3699   3701     }
  3700   3702   #endif
  3701   3703    
  3702   3704     if( pC->isTable ){
  3703   3705       /* The input value in P3 might be of any type: integer, real, string,
  3704   3706       ** blob, or NULL.  But it needs to be an integer before we can do
  3705   3707       ** the seek, so convert it. */
................................................................................
  3768   3770       assert( oc!=OP_SeekLT || r.default_rc==+1 );
  3769   3771   
  3770   3772       r.aMem = &aMem[pOp->p3];
  3771   3773   #ifdef SQLITE_DEBUG
  3772   3774       { int i; for(i=0; i<r.nField; i++) assert( memIsValid(&r.aMem[i]) ); }
  3773   3775   #endif
  3774   3776       ExpandBlob(r.aMem);
         3777  +    r.eqSeen = 0;
  3775   3778       rc = sqlite3BtreeMovetoUnpacked(pC->pCursor, &r, 0, 0, &res);
  3776   3779       if( rc!=SQLITE_OK ){
  3777   3780         goto abort_due_to_error;
         3781  +    }
         3782  +    if( (pOp->p5 & OPFLAG_SEEKEQ)!=0 && r.eqSeen==0 ){
         3783  +      goto take_the_jump;
  3778   3784       }
  3779   3785     }
  3780   3786     pC->deferredMoveto = 0;
  3781   3787     pC->cacheStatus = CACHE_STALE;
  3782   3788   #ifdef SQLITE_TEST
  3783   3789     sqlite3_search_count++;
  3784   3790   #endif
................................................................................
  3799   3805       }else{
  3800   3806         /* res might be negative because the table is empty.  Check to
  3801   3807         ** see if this is the case.
  3802   3808         */
  3803   3809         res = sqlite3BtreeEof(pC->pCursor);
  3804   3810       }
  3805   3811     }
         3812  +take_the_jump:
  3806   3813     assert( pOp->p2>0 );
  3807   3814     VdbeBranchTaken(res!=0,2);
  3808   3815     if( res ){
  3809   3816       goto jump_to_p2;
  3810   3817     }
  3811   3818     break;
  3812   3819   }

Changes to src/vdbeaux.c.

  3965   3965     /* rc==0 here means that one or both of the keys ran out of fields and
  3966   3966     ** all the fields up to that point were equal. Return the default_rc
  3967   3967     ** value.  */
  3968   3968     assert( CORRUPT_DB 
  3969   3969          || vdbeRecordCompareDebug(nKey1, pKey1, pPKey2, pPKey2->default_rc) 
  3970   3970          || pKeyInfo->db->mallocFailed
  3971   3971     );
         3972  +  pPKey2->eqSeen = 1;
  3972   3973     return pPKey2->default_rc;
  3973   3974   }
  3974   3975   int sqlite3VdbeRecordCompare(
  3975   3976     int nKey1, const void *pKey1,   /* Left key */
  3976   3977     UnpackedRecord *pPKey2          /* Right key */
  3977   3978   ){
  3978   3979     return sqlite3VdbeRecordCompareWithSkip(nKey1, pKey1, pPKey2, 0);
................................................................................
  4064   4065       /* The first fields of the two keys are equal. Compare the trailing 
  4065   4066       ** fields.  */
  4066   4067       res = sqlite3VdbeRecordCompareWithSkip(nKey1, pKey1, pPKey2, 1);
  4067   4068     }else{
  4068   4069       /* The first fields of the two keys are equal and there are no trailing
  4069   4070       ** fields. Return pPKey2->default_rc in this case. */
  4070   4071       res = pPKey2->default_rc;
         4072  +    pPKey2->eqSeen = 1;
  4071   4073     }
  4072   4074   
  4073   4075     assert( vdbeRecordCompareDebug(nKey1, pKey1, pPKey2, res) );
  4074   4076     return res;
  4075   4077   }
  4076   4078   
  4077   4079   /*
................................................................................
  4110   4112       if( res==0 ){
  4111   4113         res = nStr - pPKey2->aMem[0].n;
  4112   4114         if( res==0 ){
  4113   4115           if( pPKey2->nField>1 ){
  4114   4116             res = sqlite3VdbeRecordCompareWithSkip(nKey1, pKey1, pPKey2, 1);
  4115   4117           }else{
  4116   4118             res = pPKey2->default_rc;
         4119  +          pPKey2->eqSeen = 1;
  4117   4120           }
  4118   4121         }else if( res>0 ){
  4119   4122           res = pPKey2->r2;
  4120   4123         }else{
  4121   4124           res = pPKey2->r1;
  4122   4125         }
  4123   4126       }else if( res>0 ){

Changes to src/wherecode.c.

  1022   1022       };
  1023   1023       u16 nEq = pLoop->u.btree.nEq;     /* Number of == or IN terms */
  1024   1024       int regBase;                 /* Base register holding constraint values */
  1025   1025       WhereTerm *pRangeStart = 0;  /* Inequality constraint at range start */
  1026   1026       WhereTerm *pRangeEnd = 0;    /* Inequality constraint at range end */
  1027   1027       int startEq;                 /* True if range start uses ==, >= or <= */
  1028   1028       int endEq;                   /* True if range end uses ==, >= or <= */
         1029  +    int eqOnly;                  /* True if uses only == */
  1029   1030       int start_constraints;       /* Start of range is constrained */
  1030   1031       int nConstraint;             /* Number of constraint terms */
  1031   1032       Index *pIdx;                 /* The index we will be using */
  1032   1033       int iIdxCur;                 /* The VDBE cursor for the index */
  1033   1034       int nExtraReg = 0;           /* Number of extra registers needed */
  1034   1035       int op;                      /* Instruction opcode */
  1035   1036       char *zStartAff;             /* Affinity for start of range constraint */
................................................................................
  1091   1092          && (j = pIdx->aiColumn[nEq])>=0 
  1092   1093          && pIdx->pTable->aCol[j].notNull==0
  1093   1094         ){
  1094   1095           bSeekPastNull = 1;
  1095   1096         }
  1096   1097       }
  1097   1098       assert( pRangeEnd==0 || (pRangeEnd->wtFlags & TERM_VNULL)==0 );
         1099  +    eqOnly = nEq>0 && (pLoop->wsFlags & WHERE_COLUMN_RANGE)==0
         1100  +                   && (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)==0;
  1098   1101   
  1099   1102       /* If we are doing a reverse order scan on an ascending index, or
  1100   1103       ** a forward order scan on a descending index, interchange the 
  1101   1104       ** start and end terms (pRangeStart and pRangeEnd).
  1102   1105       */
  1103   1106       if( (nEq<pIdx->nKeyCol && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC))
  1104   1107        || (bRev && pIdx->nKeyCol==nEq)
................................................................................
  1163   1166       VdbeCoverage(v);
  1164   1167       VdbeCoverageIf(v, op==OP_Rewind);  testcase( op==OP_Rewind );
  1165   1168       VdbeCoverageIf(v, op==OP_Last);    testcase( op==OP_Last );
  1166   1169       VdbeCoverageIf(v, op==OP_SeekGT);  testcase( op==OP_SeekGT );
  1167   1170       VdbeCoverageIf(v, op==OP_SeekGE);  testcase( op==OP_SeekGE );
  1168   1171       VdbeCoverageIf(v, op==OP_SeekLE);  testcase( op==OP_SeekLE );
  1169   1172       VdbeCoverageIf(v, op==OP_SeekLT);  testcase( op==OP_SeekLT );
         1173  +    if( eqOnly ) sqlite3VdbeChangeP5(v, OPFLAG_SEEKEQ);
  1170   1174   
  1171   1175       /* Load the value for the inequality constraint at the end of the
  1172   1176       ** range (if any).
  1173   1177       */
  1174   1178       nConstraint = nEq;
  1175   1179       if( pRangeEnd ){
  1176   1180         Expr *pRight = pRangeEnd->pExpr->pRight;
................................................................................
  1198   1202       sqlite3DbFree(db, zStartAff);
  1199   1203   
  1200   1204       /* Top of the loop body */
  1201   1205       pLevel->p2 = sqlite3VdbeCurrentAddr(v);
  1202   1206   
  1203   1207       /* Check if the index cursor is past the end of the range. */
  1204   1208       if( nConstraint ){
         1209  +      if( eqOnly ){
         1210  +        int bx = sqlite3VdbeCurrentAddr(v);
         1211  +        sqlite3VdbeAddOp2(v, OP_Goto, 0, bx+2);
         1212  +        pLevel->p2 = bx+1;
         1213  +      }
  1205   1214         op = aEndOp[bRev*2 + endEq];
  1206   1215         sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
  1207   1216         testcase( op==OP_IdxGT );  VdbeCoverageIf(v, op==OP_IdxGT );
  1208   1217         testcase( op==OP_IdxGE );  VdbeCoverageIf(v, op==OP_IdxGE );
  1209   1218         testcase( op==OP_IdxLT );  VdbeCoverageIf(v, op==OP_IdxLT );
  1210   1219         testcase( op==OP_IdxLE );  VdbeCoverageIf(v, op==OP_IdxLE );
  1211   1220       }