/ Check-in [6e6bded0]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Improvements to likelihood processing so that commuting an unindexed term in the WHERE clause does not change the query plan.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | unlikely-func
Files: files | file ages | folders
SHA1: 6e6bded055cdbc902731687c86d92c39a3ba5904
User & Date: drh 2013-09-11 17:39:09
Context
2013-09-12
17:29
Merge in the Expr.flags expansion to 32-bits. Use an extra bit to help optimize the sqlite3ExprSkipCollate() routine. check-in: 4c84d1b4 user: drh tags: unlikely-func
2013-09-11
17:39
Improvements to likelihood processing so that commuting an unindexed term in the WHERE clause does not change the query plan. check-in: 6e6bded0 user: drh tags: unlikely-func
14:34
Additional unlikely() test cases. Logic tweaks to support test coverage. check-in: 5d00cce7 user: drh tags: unlikely-func
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

   685    685       memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
   686    686       if( pOld!=pWC->aStatic ){
   687    687         sqlite3DbFree(db, pOld);
   688    688       }
   689    689       pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
   690    690     }
   691    691     pTerm = &pWC->a[idx = pWC->nTerm++];
   692         -  if( wtFlags & TERM_VIRTUAL ){
   693         -    pTerm->truthProb = 0;
   694         -  }else if( ALWAYS(p) && ExprHasAnyProperty(p, EP_Hint) ){
          692  +  if( p && ExprHasAnyProperty(p, EP_Hint) ){
   695    693       pTerm->truthProb = whereCost(p->iTable) - 99;
   696    694     }else{
   697    695       pTerm->truthProb = -1;
   698    696     }
   699    697     pTerm->pExpr = sqlite3ExprSkipCollate(p);
   700    698     pTerm->wtFlags = wtFlags;
   701    699     pTerm->pWC = pWC;
................................................................................
  4282   4280   ** index.
  4283   4281   **
  4284   4282   ** In the current implementation, the first extra WHERE clause term reduces
  4285   4283   ** the number of output rows by a factor of 10 and each additional term
  4286   4284   ** reduces the number of output rows by sqrt(2).
  4287   4285   */
  4288   4286   static void whereLoopOutputAdjust(WhereClause *pWC, WhereLoop *pLoop, int iCur){
  4289         -  WhereTerm *pTerm;
         4287  +  WhereTerm *pTerm, *pX;
  4290   4288     Bitmask notAllowed = ~(pLoop->prereq|pLoop->maskSelf);
  4291         -  int x = 0;
  4292         -  int i;
         4289  +  int i, j;
  4293   4290   
  4294   4291     if( !OptimizationEnabled(pWC->pWInfo->pParse->db, SQLITE_AdjustOutEst) ){
  4295   4292       return;
  4296   4293     }
  4297   4294     for(i=pWC->nTerm, pTerm=pWC->a; i>0; i--, pTerm++){
  4298         -    if( (pTerm->wtFlags & TERM_VIRTUAL)!=0 ) continue;
         4295  +    if( (pTerm->wtFlags & TERM_VIRTUAL)!=0 ) break;
  4299   4296       if( (pTerm->prereqAll & pLoop->maskSelf)==0 ) continue;
  4300   4297       if( (pTerm->prereqAll & notAllowed)!=0 ) continue;
  4301         -    x += pTerm->truthProb;
         4298  +    for(j=pLoop->nLTerm-1; j>=0; j--){
         4299  +      pX = pLoop->aLTerm[j];
         4300  +      if( pX==pTerm ) break;
         4301  +      if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break;
         4302  +    }
         4303  +    if( j<0 ) pLoop->nOut += pTerm->truthProb;
  4302   4304     }
  4303         -  for(i=pLoop->nLTerm-1; i>=0; i--){
  4304         -    x -= pLoop->aLTerm[i]->truthProb;
  4305         -  }
  4306         -  if( x<0 ) pLoop->nOut += x;
  4307   4305   }
  4308   4306   
  4309   4307   /*
  4310   4308   ** We have so far matched pBuilder->pNew->u.btree.nEq terms of the index pIndex.
  4311   4309   ** Try to match one more.
  4312   4310   **
  4313   4311   ** If pProbe->tnum==0, that means pIndex is a fake index used for the
................................................................................
  5422   5420                   (pTo->rCost>=rCost && pTo->nRow>=nOut))
  5423   5421             ){
  5424   5422               testcase( jj==nTo-1 );
  5425   5423               break;
  5426   5424             }
  5427   5425           }
  5428   5426           if( jj>=nTo ){
  5429         -          if( nTo>=mxChoice 
  5430         -           && (rCost>mxCost || (rCost==mxCost && nOut>=mxOut))
  5431         -          ){
         5427  +          if( nTo>=mxChoice && rCost>=mxCost ){
  5432   5428   #ifdef WHERETRACE_ENABLED
  5433   5429               if( sqlite3WhereTrace&0x4 ){
  5434   5430                 sqlite3DebugPrintf("Skip   %s cost=%-3d,%3d order=%c\n",
  5435   5431                     wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
  5436   5432                     isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
  5437   5433               }
  5438   5434   #endif

Changes to test/whereG.test.

   142    142       SELECT DISTINCT aname
   143    143         FROM album, composer, track
   144    144        WHERE likelihood(cname LIKE '%bach%', track.cid)
   145    145          AND composer.cid=track.cid
   146    146          AND album.aid=track.aid;
   147    147     }
   148    148   } {1 {second argument to likelihood() must be a constant between 0.0 and 1.0}}
          149  +
          150  +# Commuting a term of the WHERE clause should not change the query plan
          151  +#
          152  +do_execsql_test whereG-3.0 {
          153  +  CREATE TABLE a(a1 PRIMARY KEY, a2);
          154  +  CREATE TABLE b(b1 PRIMARY KEY, b2);
          155  +} {}
          156  +do_eqp_test whereG-3.1 {
          157  +  SELECT * FROM a, b WHERE b1=a1 AND a2=5;
          158  +} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}
          159  +do_eqp_test whereG-3.2 {
          160  +  SELECT * FROM a, b WHERE a1=b1 AND a2=5;
          161  +} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}
          162  +do_eqp_test whereG-3.3 {
          163  +  SELECT * FROM a, b WHERE a2=5 AND b1=a1;
          164  +} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}
          165  +do_eqp_test whereG-3.4 {
          166  +  SELECT * FROM a, b WHERE a2=5 AND a1=b1;
          167  +} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}
          168  +
   149    169   
   150    170   finish_test