/ Check-in [e612664a]
Login

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

Overview
Comment:Handle virtual tables correctly when using logarithmic costs. Fixes to test cases.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-logcost
Files: files | file ages | folders
SHA1:e612664aa2e24ed5e222be2c7fe16e210ac9bded
User & Date: drh 2013-06-11 01:50:08
Context
2013-06-11
02:32
Fixes to EXPLAIN QUERY PLAN output. Change weights back to something closer to what they are in legacy. More test case fixes. Closed-Leaf check-in: 36373b85 user: drh tags: nextgen-query-plan-logcost
01:50
Handle virtual tables correctly when using logarithmic costs. Fixes to test cases. check-in: e612664a user: drh tags: nextgen-query-plan-logcost
2013-06-10
23:30
Fix test cases for the new EXPLAIN QUERY PLAN format. Add the wherecosttest tool. Other fixes to logarithm cost. check-in: aa580e36 user: drh tags: nextgen-query-plan-logcost
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

  1878   1878     }else{
  1879   1879       while( x>255 ){ y += 40; x >>= 4; }
  1880   1880       while( x>15 ){  y += 10; x >>= 1; }
  1881   1881     }
  1882   1882     return a[x&7] + y - 10;
  1883   1883   }
  1884   1884   
         1885  +#ifndef SQLITE_OMIT_VIRTUALTABLE
         1886  +/*
         1887  +** Convert a double (as received from xBestIndex of a virtual table)
         1888  +** into a WhereCost
         1889  +*/
         1890  +static WhereCost whereCostFromDouble(double x){
         1891  +  u64 a;
         1892  +  WhereCost e;
         1893  +  assert( sizeof(x)==8 && sizeof(a)==8 );
         1894  +  if( x<=1 ) return 0;
         1895  +  if( x<=2000000000 ) return whereCostFromInt((tRowcnt)x);
         1896  +  memcpy(&a, &x, 8);
         1897  +  e = (a>>52) - 1022;
         1898  +  return e*10;
         1899  +}
         1900  +#endif /* SQLITE_OMIT_VIRTUALTABLE */
         1901  +
  1885   1902   /*
  1886   1903   ** Prepare a crude estimate of the logarithm of the input value.
  1887   1904   ** The results need not be exact.  This is only used for estimating
  1888   1905   ** the total cost of performing operations with O(logN) or O(NlogN)
  1889   1906   ** complexity.  Because N is just a guess, it is no great tragedy if
  1890   1907   ** logN is a little off.
  1891   1908   */
................................................................................
  4084   4101          && p->u.btree.pIndex==pTemplate->u.btree.pIndex
  4085   4102          && p->prereq==pTemplate->prereq
  4086   4103         ){
  4087   4104           /* Overwrite an existing WhereLoop with an similar one that uses
  4088   4105           ** more terms of the index */
  4089   4106           pNext = p->pNextLoop;
  4090   4107           break;
         4108  +      }else if( p->nOut>pTemplate->nOut
         4109  +       && p->rSetup==pTemplate->rSetup
         4110  +       && p->rRun==pTemplate->rRun
         4111  +      ){
         4112  +        /* Overwrite an existing WhereLoop with the same cost but more
         4113  +        ** outputs */
         4114  +        pNext = p->pNextLoop;
         4115  +        break;
  4091   4116         }else{
  4092   4117           /* pTemplate is not helpful.
  4093   4118           ** Return without changing or adding anything */
  4094   4119           goto whereLoopInsert_noop;
  4095   4120         }
  4096   4121       }
  4097   4122       if( (p->prereq & pTemplate->prereq)==pTemplate->prereq
................................................................................
  4259   4284                        pNew->aLTerm[pNew->nLTerm-2] : 0;
  4260   4285       }
  4261   4286       if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
  4262   4287         /* Adjust nOut and rRun for STAT3 range values */
  4263   4288         WhereCost rDiv;
  4264   4289         whereRangeScanEst(pParse, pProbe, pNew->u.btree.nEq,
  4265   4290                           pBtm, pTop, &rDiv);
  4266         -      pNew->nOut = saved_nOut - rDiv;
         4291  +      pNew->nOut = saved_nOut>rDiv+10 ? saved_nOut - rDiv : 10;
  4267   4292       }
  4268   4293   #ifdef SQLITE_ENABLE_STAT3
  4269   4294       if( pNew->u.btree.nEq==1 && pProbe->nSample ){
  4270   4295         tRowcnt nOut = 0;
  4271   4296         if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))!=0 ){
  4272   4297           rc = whereEqualScanEst(pParse, pProbe, pTerm->pExpr->pRight, &nOut);
  4273   4298         }else if( (pTerm->eOperator & WO_IN)
................................................................................
  4478   4503       /* If there was an INDEXED BY clause, then only that one index is
  4479   4504       ** considered. */
  4480   4505       if( pSrc->pIndex ) break;
  4481   4506     }
  4482   4507     return rc;
  4483   4508   }
  4484   4509   
         4510  +#ifndef SQLITE_OMIT_VIRTUALTABLE
  4485   4511   /*
  4486   4512   ** Add all WhereLoop objects for a table of the join identified by
  4487   4513   ** pBuilder->pNew->iTab.  That table is guaranteed to be a virtual table.
  4488   4514   */
  4489   4515   static int whereLoopAddVirtual(
  4490   4516     WhereLoopBuilder *pBuilder,  /* WHERE clause information */
  4491   4517     Bitmask mExtra               /* Extra prerequesites for using this table */
................................................................................
  4565   4591       }
  4566   4592       memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
  4567   4593       if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr);
  4568   4594       pIdxInfo->idxStr = 0;
  4569   4595       pIdxInfo->idxNum = 0;
  4570   4596       pIdxInfo->needToFreeIdxStr = 0;
  4571   4597       pIdxInfo->orderByConsumed = 0;
  4572         -    /* ((WhereCost)2) In case of SQLITE_OMIT_FLOATING_POINT... */
  4573         -    pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((WhereCost)2);
         4598  +    pIdxInfo->estimatedCost = SQLITE_BIG_DBL / (double)2;
  4574   4599       rc = vtabBestIndex(pParse, pTab, pIdxInfo);
  4575   4600       if( rc ) goto whereLoopAddVtab_exit;
  4576   4601       pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  4577   4602       pNew->prereq = 0;
  4578   4603       mxTerm = -1;
  4579   4604       assert( pNew->nLSlot>=nConstraint );
  4580   4605       for(i=0; i<nConstraint; i++) pNew->aLTerm[i] = 0;
................................................................................
  4620   4645         pNew->u.vtab.idxNum = pIdxInfo->idxNum;
  4621   4646         pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr;
  4622   4647         pIdxInfo->needToFreeIdxStr = 0;
  4623   4648         pNew->u.vtab.idxStr = pIdxInfo->idxStr;
  4624   4649         pNew->u.vtab.isOrdered = (u8)((pIdxInfo->nOrderBy!=0)
  4625   4650                                        && pIdxInfo->orderByConsumed);
  4626   4651         pNew->rSetup = 0;
  4627         -      pNew->rRun = whereCostFromInt((tRowcnt)pIdxInfo->estimatedCost);
         4652  +      pNew->rRun = whereCostFromDouble(pIdxInfo->estimatedCost);
  4628   4653         pNew->nOut = 46;  assert( 46 == whereCostFromInt(25) );
  4629   4654         whereLoopInsert(pBuilder, pNew);
  4630   4655         if( pNew->u.vtab.needFree ){
  4631   4656           sqlite3_free(pNew->u.vtab.idxStr);
  4632   4657           pNew->u.vtab.needFree = 0;
  4633   4658         }
  4634   4659       }
................................................................................
  4635   4660     }  
  4636   4661   
  4637   4662   whereLoopAddVtab_exit:
  4638   4663     if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr);
  4639   4664     sqlite3DbFree(db, pIdxInfo);
  4640   4665     return rc;
  4641   4666   }
         4667  +#endif /* SQLITE_OMIT_VIRTUALTABLE */
  4642   4668   
  4643   4669   /*
  4644   4670   ** Add WhereLoop entries to handle OR terms.  This works for either
  4645   4671   ** btrees or virtual tables.
  4646   4672   */
  4647   4673   static int whereLoopAddOr(WhereLoopBuilder *pBuilder, Bitmask mExtra){
  4648   4674     WhereInfo *pWInfo = pBuilder->pWInfo;
................................................................................
  4691   4717             sSubBuild.pWC = &tempWC;
  4692   4718           }else{
  4693   4719             continue;
  4694   4720           }
  4695   4721           sBest.maskSelf = 0;
  4696   4722           sBest.rSetup = 0;
  4697   4723           sBest.rRun = 0;
         4724  +#ifndef SQLITE_OMIT_VIRTUALTABLE
  4698   4725           if( IsVirtual(pItem->pTab) ){
  4699   4726             rc = whereLoopAddVirtual(&sSubBuild, mExtra);
  4700         -        }else{
         4727  +        }else
         4728  +#endif
         4729  +        {
  4701   4730             rc = whereLoopAddBtree(&sSubBuild, mExtra);
  4702   4731           }
  4703   4732           if( sBest.maskSelf==0 ) break;
  4704   4733           assert( sBest.rSetup==0 );
  4705   4734           rTotal = whereCostAdd(rTotal, sBest.rRun);
  4706   4735           nRow = whereCostAdd(nRow, sBest.nOut);
  4707   4736           prereq |= sBest.prereq;

Changes to test/analyze5.test.

   152    152     301  {y=1}                 t1y   26
   153    153     302  {y=0.1}               t1y    1
   154    154   
   155    155     400  {x IS NULL}           t1x  400
   156    156   
   157    157   } {
   158    158     # Verify that the expected index is used with the expected row count
   159         -  do_test analyze5-1.${testid}a {
   160         -    set x [lindex [eqp "SELECT * FROM t1 WHERE $where"] 3]
   161         -    set idx {}
   162         -    regexp {INDEX (t1.) } $x all idx
   163         -    regexp {~([0-9]+) rows} $x all nrow
   164         -    list $idx $nrow
   165         -  } [list $index $rows]
          159  +  # No longer valid due to an EXPLAIN QUERY PLAN output format change
          160  +  # do_test analyze5-1.${testid}a {
          161  +  #   set x [lindex [eqp "SELECT * FROM t1 WHERE $where"] 3]
          162  +  #   set idx {}
          163  +  #   regexp {INDEX (t1.) } $x all idx
          164  +  #   regexp {~([0-9]+) rows} $x all nrow
          165  +  #   list $idx $nrow
          166  +  # } [list $index $rows]
   166    167   
   167    168     # Verify that the same result is achieved regardless of whether or not
   168    169     # the index is used
   169    170     do_test analyze5-1.${testid}b {
   170    171       set w2 [string map {y +y z +z} $where]
   171    172       set a1 [db eval "SELECT rowid FROM t1 NOT INDEXED WHERE $w2\
   172    173                        ORDER BY +rowid"]
................................................................................
   198    199     503  {x=1}                               t1x   1
   199    200     504  {x IS NOT NULL}                     t1x   2
   200    201     505  {+x IS NOT NULL}                     {} 500
   201    202     506  {upper(x) IS NOT NULL}               {} 500
   202    203   
   203    204   } {
   204    205     # Verify that the expected index is used with the expected row count
   205         -if {$testid==50299} {breakpoint; set sqlite_where_trace 1}
   206         -  do_test analyze5-1.${testid}a {
   207         -    set x [lindex [eqp "SELECT * FROM t1 WHERE $where"] 3]
   208         -    set idx {}
   209         -    regexp {INDEX (t1.) } $x all idx
   210         -    regexp {~([0-9]+) rows} $x all nrow
   211         -    list $idx $nrow
   212         -  } [list $index $rows]
   213         -if {$testid==50299} exit
          206  +  # No longer valid due to an EXPLAIN QUERY PLAN format change
          207  +  # do_test analyze5-1.${testid}a {
          208  +  #   set x [lindex [eqp "SELECT * FROM t1 WHERE $where"] 3]
          209  +  #   set idx {}
          210  +  #   regexp {INDEX (t1.) } $x all idx
          211  +  #   regexp {~([0-9]+) rows} $x all nrow
          212  +  #   list $idx $nrow
          213  +  # } [list $index $rows]
   214    214   
   215    215     # Verify that the same result is achieved regardless of whether or not
   216    216     # the index is used
   217    217     do_test analyze5-1.${testid}b {
   218    218       set w2 [string map {y +y z +z} $where]
   219    219       set a1 [db eval "SELECT rowid FROM t1 NOT INDEXED WHERE $w2\
   220    220                        ORDER BY +rowid"]

Changes to test/between.test.

    54     54     set ::sqlite_sort_count 0
    55     55     set data [execsql $sql]
    56     56     if {$::sqlite_sort_count} {set x sort} {set x nosort}
    57     57     lappend data $x
    58     58     set eqp [execsql "EXPLAIN QUERY PLAN $sql"]
    59     59     # puts eqp=$eqp
    60     60     foreach {a b c x} $eqp {
    61         -    if {[regexp { TABLE (\w+ AS )?(\w+) USING.* INDEX (\w+)\W} \
           61  +    if {[regexp { TABLE (\w+ AS )?(\w+) USING.* INDEX (\w+)\y} \
    62     62           $x all as tab idx]} {
    63     63         lappend data $tab $idx
    64         -    } elseif {[regexp { TABLE (\w+ AS )?(\w+)\W} $x all as tab]} {
           64  +    } elseif {[regexp { TABLE (\w+ AS )?(\w+)\y} $x all as tab]} {
    65     65         lappend data $tab *
    66     66       }
    67     67     }
    68     68     return $data   
    69     69   }
    70     70   
    71     71   do_test between-1.1.1 {

Changes to test/eqp.test.

   550    550   }
   551    551   
   552    552   det 7.1 "SELECT count(*) FROM t1" {
   553    553     0 0 0 {SCAN TABLE t1}
   554    554   }
   555    555   
   556    556   det 7.2 "SELECT count(*) FROM t2" {
   557         -  0 0 0 {SCAN TABLE t2 USING COVERING INDEX i1(~1000000 rows)}
          557  +  0 0 0 {SCAN TABLE t2 USING COVERING INDEX i1}
   558    558   }
   559    559   
   560    560   do_execsql_test 7.3 {
   561    561     INSERT INTO t1 VALUES(1, 2);
   562    562     INSERT INTO t1 VALUES(3, 4);
   563    563   
   564    564     INSERT INTO t2 VALUES(1, 2);
................................................................................
   572    572   sqlite3 db test.db
   573    573   
   574    574   det 7.4 "SELECT count(*) FROM t1" {
   575    575     0 0 0 {SCAN TABLE t1}
   576    576   }
   577    577   
   578    578   det 7.5 "SELECT count(*) FROM t2" {
   579         -  0 0 0 {SCAN TABLE t2 USING COVERING INDEX i1(~3 rows)}
          579  +  0 0 0 {SCAN TABLE t2 USING COVERING INDEX i1}
   580    580   }
   581    581   
   582    582   
   583    583   finish_test