SQLite

Check-in [6e6bded055]
Login

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
Timelines: family | ancestors | descendants | both | unlikely-func
Files: files | file ages | folders
SHA1: 6e6bded055cdbc902731687c86d92c39a3ba5904
User & Date: drh 2013-09-11 17:39:09.434
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: 4c84d1b4c2 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: 6e6bded055 user: drh tags: unlikely-func)
14:34
Additional unlikely() test cases. Logic tweaks to support test coverage. (check-in: 5d00cce74a user: drh tags: unlikely-func)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
︙︙
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701

    memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
    if( pOld!=pWC->aStatic ){
      sqlite3DbFree(db, pOld);
    }
    pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
  }
  pTerm = &pWC->a[idx = pWC->nTerm++];
  if( wtFlags & TERM_VIRTUAL ){
    pTerm->truthProb = 0;
  }else if( ALWAYS(p) && ExprHasAnyProperty(p, EP_Hint) ){
    pTerm->truthProb = whereCost(p->iTable) - 99;
  }else{
    pTerm->truthProb = -1;
  }
  pTerm->pExpr = sqlite3ExprSkipCollate(p);
  pTerm->wtFlags = wtFlags;
  pTerm->pWC = pWC;








<
<
|








685
686
687
688
689
690
691


692
693
694
695
696
697
698
699

    memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
    if( pOld!=pWC->aStatic ){
      sqlite3DbFree(db, pOld);
    }
    pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
  }
  pTerm = &pWC->a[idx = pWC->nTerm++];


  if( p && ExprHasAnyProperty(p, EP_Hint) ){
    pTerm->truthProb = whereCost(p->iTable) - 99;
  }else{
    pTerm->truthProb = -1;
  }
  pTerm->pExpr = sqlite3ExprSkipCollate(p);
  pTerm->wtFlags = wtFlags;
  pTerm->pWC = pWC;
︙︙
4282
4283
4284
4285
4286
4287
4288
4289
4290
4291
4292
4293
4294
4295
4296
4297
4298
4299
4300
4301
4302
4303
4304


4305
4306

4307
4308
4309
4310
4311
4312
4313

** index.
**
** In the current implementation, the first extra WHERE clause term reduces
** the number of output rows by a factor of 10 and each additional term
** reduces the number of output rows by sqrt(2).
*/
static void whereLoopOutputAdjust(WhereClause *pWC, WhereLoop *pLoop, int iCur){
  WhereTerm *pTerm;
  Bitmask notAllowed = ~(pLoop->prereq|pLoop->maskSelf);
  int x = 0;
  int i;

  if( !OptimizationEnabled(pWC->pWInfo->pParse->db, SQLITE_AdjustOutEst) ){
    return;
  }
  for(i=pWC->nTerm, pTerm=pWC->a; i>0; i--, pTerm++){
    if( (pTerm->wtFlags & TERM_VIRTUAL)!=0 ) continue;
    if( (pTerm->prereqAll & pLoop->maskSelf)==0 ) continue;
    if( (pTerm->prereqAll & notAllowed)!=0 ) continue;
    x += pTerm->truthProb;
  }
  for(i=pLoop->nLTerm-1; i>=0; i--){
    x -= pLoop->aLTerm[i]->truthProb;


  }
  if( x<0 ) pLoop->nOut += x;

}

/*
** We have so far matched pBuilder->pNew->u.btree.nEq terms of the index pIndex.
** Try to match one more.
**
** If pProbe->tnum==0, that means pIndex is a fake index used for the








|

<
|





|


<
<
|
|
>
>
|
|
>








4280
4281
4282
4283
4284
4285
4286
4287
4288

4289
4290
4291
4292
4293
4294
4295
4296
4297


4298
4299
4300
4301
4302
4303
4304
4305
4306
4307
4308
4309
4310
4311

** index.
**
** In the current implementation, the first extra WHERE clause term reduces
** the number of output rows by a factor of 10 and each additional term
** reduces the number of output rows by sqrt(2).
*/
static void whereLoopOutputAdjust(WhereClause *pWC, WhereLoop *pLoop, int iCur){
  WhereTerm *pTerm, *pX;
  Bitmask notAllowed = ~(pLoop->prereq|pLoop->maskSelf);

  int i, j;

  if( !OptimizationEnabled(pWC->pWInfo->pParse->db, SQLITE_AdjustOutEst) ){
    return;
  }
  for(i=pWC->nTerm, pTerm=pWC->a; i>0; i--, pTerm++){
    if( (pTerm->wtFlags & TERM_VIRTUAL)!=0 ) break;
    if( (pTerm->prereqAll & pLoop->maskSelf)==0 ) continue;
    if( (pTerm->prereqAll & notAllowed)!=0 ) continue;


    for(j=pLoop->nLTerm-1; j>=0; j--){
      pX = pLoop->aLTerm[j];
      if( pX==pTerm ) break;
      if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break;
    }
    if( j<0 ) pLoop->nOut += pTerm->truthProb;
  }
}

/*
** We have so far matched pBuilder->pNew->u.btree.nEq terms of the index pIndex.
** Try to match one more.
**
** If pProbe->tnum==0, that means pIndex is a fake index used for the
︙︙
5422
5423
5424
5425
5426
5427
5428
5429
5430
5431
5432
5433
5434
5435
5436
5437
5438

                (pTo->rCost>=rCost && pTo->nRow>=nOut))
          ){
            testcase( jj==nTo-1 );
            break;
          }
        }
        if( jj>=nTo ){
          if( nTo>=mxChoice 
           && (rCost>mxCost || (rCost==mxCost && nOut>=mxOut))
          ){
#ifdef WHERETRACE_ENABLED
            if( sqlite3WhereTrace&0x4 ){
              sqlite3DebugPrintf("Skip   %s cost=%-3d,%3d order=%c\n",
                  wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
                  isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
            }
#endif








|
<
<








5420
5421
5422
5423
5424
5425
5426
5427


5428
5429
5430
5431
5432
5433
5434

                (pTo->rCost>=rCost && pTo->nRow>=nOut))
          ){
            testcase( jj==nTo-1 );
            break;
          }
        }
        if( jj>=nTo ){
          if( nTo>=mxChoice && rCost>=mxCost ){


#ifdef WHERETRACE_ENABLED
            if( sqlite3WhereTrace&0x4 ){
              sqlite3DebugPrintf("Skip   %s cost=%-3d,%3d order=%c\n",
                  wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
                  isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
            }
#endif
︙︙
Changes to test/whereG.test.
︙︙
142
143
144
145
146
147
148




















149
150

    SELECT DISTINCT aname
      FROM album, composer, track
     WHERE likelihood(cname LIKE '%bach%', track.cid)
       AND composer.cid=track.cid
       AND album.aid=track.aid;
  }
} {1 {second argument to likelihood() must be a constant between 0.0 and 1.0}}





















finish_test








>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>



142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170

    SELECT DISTINCT aname
      FROM album, composer, track
     WHERE likelihood(cname LIKE '%bach%', track.cid)
       AND composer.cid=track.cid
       AND album.aid=track.aid;
  }
} {1 {second argument to likelihood() must be a constant between 0.0 and 1.0}}

# Commuting a term of the WHERE clause should not change the query plan
#
do_execsql_test whereG-3.0 {
  CREATE TABLE a(a1 PRIMARY KEY, a2);
  CREATE TABLE b(b1 PRIMARY KEY, b2);
} {}
do_eqp_test whereG-3.1 {
  SELECT * FROM a, b WHERE b1=a1 AND a2=5;
} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}
do_eqp_test whereG-3.2 {
  SELECT * FROM a, b WHERE a1=b1 AND a2=5;
} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}
do_eqp_test whereG-3.3 {
  SELECT * FROM a, b WHERE a2=5 AND b1=a1;
} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}
do_eqp_test whereG-3.4 {
  SELECT * FROM a, b WHERE a2=5 AND a1=b1;
} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}


finish_test