/ Check-in [b65dc534]
Login

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

Overview
Comment:Continuing refinements of the logic to take WHERE clause terms not used for indexing into account when computing the number of output rows from each table.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | unlikely-func
Files: files | file ages | folders
SHA1:b65dc53415f42d8402d0ec7f4bedf59d7b39b486
User & Date: drh 2013-09-07 00:29:06
Context
2013-09-10
01:53
Merge trunk fixes into the unlikely-func branch. check-in: a51d7515 user: drh tags: unlikely-func
2013-09-07
00:29
Continuing refinements of the logic to take WHERE clause terms not used for indexing into account when computing the number of output rows from each table. check-in: b65dc534 user: drh tags: unlikely-func
2013-09-06
17:45
Enhance the plan solver to take into account the number of output rows when computing the set of paths to retain for the next cycle. check-in: 1a46a724 user: drh tags: unlikely-func
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/resolve.c.

701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
            pExpr->iTable = exprProbability(pList->a[1].pExpr);
            if( pExpr->iTable<0 ){
              sqlite3ErrorMsg(pParse, "second parameter to unlikely() must be "
                                      "between 0.0 and 1.0");
              pNC->nErr++;
            }
          }else{
            pExpr->iTable = 75;
          }             
        }
      }
#ifndef SQLITE_OMIT_AUTHORIZATION
      if( pDef ){
        auth = sqlite3AuthCheck(pParse, SQLITE_FUNCTION, 0, pDef->zName, 0);
        if( auth!=SQLITE_OK ){







|







701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
            pExpr->iTable = exprProbability(pList->a[1].pExpr);
            if( pExpr->iTable<0 ){
              sqlite3ErrorMsg(pParse, "second parameter to unlikely() must be "
                                      "between 0.0 and 1.0");
              pNC->nErr++;
            }
          }else{
            pExpr->iTable = 75;  /* TUNING:  Default 2nd arg to unlikely() is 0.075 */
          }             
        }
      }
#ifndef SQLITE_OMIT_AUTHORIZATION
      if( pDef ){
        auth = sqlite3AuthCheck(pParse, SQLITE_FUNCTION, 0, pDef->zName, 0);
        if( auth!=SQLITE_OK ){

Changes to src/sqliteInt.h.

1028
1029
1030
1031
1032
1033
1034

1035
1036
1037
1038
1039
1040
1041
#define SQLITE_DistinctOpt    0x0020   /* DISTINCT using indexes */
#define SQLITE_CoverIdxScan   0x0040   /* Covering index scans */
#define SQLITE_OrderByIdxJoin 0x0080   /* ORDER BY of joins via index */
#define SQLITE_SubqCoroutine  0x0100   /* Evaluate subqueries as coroutines */
#define SQLITE_Transitive     0x0200   /* Transitive constraints */
#define SQLITE_OmitNoopJoin   0x0400   /* Omit unused tables in joins */
#define SQLITE_Stat3          0x0800   /* Use the SQLITE_STAT3 table */

#define SQLITE_AllOpts        0xffff   /* All optimizations */

/*
** Macros for testing whether or not optimizations are enabled or disabled.
*/
#ifndef SQLITE_OMIT_BUILTIN_TEST
#define OptimizationDisabled(db, mask)  (((db)->dbOptFlags&(mask))!=0)







>







1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
#define SQLITE_DistinctOpt    0x0020   /* DISTINCT using indexes */
#define SQLITE_CoverIdxScan   0x0040   /* Covering index scans */
#define SQLITE_OrderByIdxJoin 0x0080   /* ORDER BY of joins via index */
#define SQLITE_SubqCoroutine  0x0100   /* Evaluate subqueries as coroutines */
#define SQLITE_Transitive     0x0200   /* Transitive constraints */
#define SQLITE_OmitNoopJoin   0x0400   /* Omit unused tables in joins */
#define SQLITE_Stat3          0x0800   /* Use the SQLITE_STAT3 table */
#define SQLITE_AdjustOutEst   0x1000   /* Adjust output estimates using WHERE */
#define SQLITE_AllOpts        0xffff   /* All optimizations */

/*
** Macros for testing whether or not optimizations are enabled or disabled.
*/
#ifndef SQLITE_OMIT_BUILTIN_TEST
#define OptimizationDisabled(db, mask)  (((db)->dbOptFlags&(mask))!=0)

Changes to src/where.c.

684
685
686
687
688
689
690


691
692
693
694
695
696
697
698
....
4194
4195
4196
4197
4198
4199
4200
4201
4202
4203

4204
4205
4206
4207
4208
4209
4210
....
4211
4212
4213
4214
4215
4216
4217
4218
4219
4220
4221
4222
4223

4224
4225
4226
4227
4228
4229
4230
....
4277
4278
4279
4280
4281
4282
4283




4284
4285
4286
4287
4288
4289
4290
    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;
................................................................................
    ){
      /* This branch taken when p is equal or better than pTemplate in 
      ** all of (1) dependencies (2) setup-cost, (3) run-cost, and
      ** (4) number of output rows. */
      assert( p->rSetup==pTemplate->rSetup );
      if( p->prereq==pTemplate->prereq
       && p->nLTerm<pTemplate->nLTerm
       && (p->wsFlags & WHERE_INDEXED)!=0
       && (pTemplate->wsFlags & WHERE_INDEXED)!=0
       && p->u.btree.pIndex==pTemplate->u.btree.pIndex

      ){
        /* Overwrite an existing WhereLoop with an similar one that uses
        ** more terms of the index */
        pNext = p->pNextLoop;
        break;
      }else{
        /* pTemplate is not helpful.
................................................................................
        ** Return without changing or adding anything */
        goto whereLoopInsert_noop;
      }
    }
    if( (p->prereq & pTemplate->prereq)==pTemplate->prereq
     && p->rRun>=pTemplate->rRun
     && p->nOut>=pTemplate->nOut
     && ALWAYS(p->rSetup>=pTemplate->rSetup) /* See SETUP-INVARIANT above */
    ){
      /* Overwrite an existing WhereLoop with a better one: one that is
      ** better at one of (1) dependencies, (2) setup-cost, (3) run-cost
      ** or (4) number of output rows, and is no worse in any of those
      ** categories. */

      pNext = p->pNextLoop;
      break;
    }
  }

  /* If we reach this point it means that either p[] should be overwritten
  ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
................................................................................
** 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;




  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--){







>
>
|







 







<
|
|
>







 







<





>







 







>
>
>
>







684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
....
4196
4197
4198
4199
4200
4201
4202

4203
4204
4205
4206
4207
4208
4209
4210
4211
4212
....
4213
4214
4215
4216
4217
4218
4219

4220
4221
4222
4223
4224
4225
4226
4227
4228
4229
4230
4231
4232
....
4279
4280
4281
4282
4283
4284
4285
4286
4287
4288
4289
4290
4291
4292
4293
4294
4295
4296
    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( 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;
................................................................................
    ){
      /* This branch taken when p is equal or better than pTemplate in 
      ** all of (1) dependencies (2) setup-cost, (3) run-cost, and
      ** (4) number of output rows. */
      assert( p->rSetup==pTemplate->rSetup );
      if( p->prereq==pTemplate->prereq
       && p->nLTerm<pTemplate->nLTerm

       && (p->wsFlags & pTemplate->wsFlags & WHERE_INDEXED)!=0
       && (p->u.btree.pIndex==pTemplate->u.btree.pIndex
           || p->u.btree.pIndex->nColumn>=pTemplate->u.btree.pIndex->nColumn)
      ){
        /* Overwrite an existing WhereLoop with an similar one that uses
        ** more terms of the index */
        pNext = p->pNextLoop;
        break;
      }else{
        /* pTemplate is not helpful.
................................................................................
        ** Return without changing or adding anything */
        goto whereLoopInsert_noop;
      }
    }
    if( (p->prereq & pTemplate->prereq)==pTemplate->prereq
     && p->rRun>=pTemplate->rRun
     && p->nOut>=pTemplate->nOut

    ){
      /* Overwrite an existing WhereLoop with a better one: one that is
      ** better at one of (1) dependencies, (2) setup-cost, (3) run-cost
      ** or (4) number of output rows, and is no worse in any of those
      ** categories. */
      assert( p->rSetup>=pTemplate->rSetup ); /* SETUP-INVARIANT above */
      pNext = p->pNextLoop;
      break;
    }
  }

  /* If we reach this point it means that either p[] should be overwritten
  ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
................................................................................
** 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--){