/ Check-in [e612664a]

Overview
Comment: Handle virtual tables correctly when using logarithmic costs. Fixes to test cases. Tarball | ZIP archive | SQL archive family | ancestors | descendants | both | nextgen-query-plan-logcost files | file ages | folders e612664aa2e24ed5e222be2c7fe16e210ac9bded 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

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   */
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
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   */
4648   4674     WhereInfo *pWInfo = pBuilder->pWInfo;
................................................................................
4691   4717             sSubBuild.pWC = &tempWC;
4692   4718           }else{
4693   4719             continue;
4694   4720           }
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

```