SQLite

Check-in [e612664aa2]
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
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.263
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: 36373b85f9 user: drh tags: nextgen-query-plan-logcost)
01:50
Handle virtual tables correctly when using logarithmic costs. Fixes to test cases. (check-in: e612664aa2 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: aa580e368e user: drh tags: nextgen-query-plan-logcost)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
1878
1879
1880
1881
1882
1883
1884

















1885
1886
1887
1888
1889
1890
1891
  }else{
    while( x>255 ){ y += 40; x >>= 4; }
    while( x>15 ){  y += 10; x >>= 1; }
  }
  return a[x&7] + y - 10;
}


















/*
** Prepare a crude estimate of the logarithm of the input value.
** The results need not be exact.  This is only used for estimating
** the total cost of performing operations with O(logN) or O(NlogN)
** complexity.  Because N is just a guess, it is no great tragedy if
** logN is a little off.
*/







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







1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
  }else{
    while( x>255 ){ y += 40; x >>= 4; }
    while( x>15 ){  y += 10; x >>= 1; }
  }
  return a[x&7] + y - 10;
}

#ifndef SQLITE_OMIT_VIRTUALTABLE
/*
** Convert a double (as received from xBestIndex of a virtual table)
** into a WhereCost
*/
static WhereCost whereCostFromDouble(double x){
  u64 a;
  WhereCost e;
  assert( sizeof(x)==8 && sizeof(a)==8 );
  if( x<=1 ) return 0;
  if( x<=2000000000 ) return whereCostFromInt((tRowcnt)x);
  memcpy(&a, &x, 8);
  e = (a>>52) - 1022;
  return e*10;
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/*
** Prepare a crude estimate of the logarithm of the input value.
** The results need not be exact.  This is only used for estimating
** the total cost of performing operations with O(logN) or O(NlogN)
** complexity.  Because N is just a guess, it is no great tragedy if
** logN is a little off.
*/
4084
4085
4086
4087
4088
4089
4090








4091
4092
4093
4094
4095
4096
4097
       && p->u.btree.pIndex==pTemplate->u.btree.pIndex
       && p->prereq==pTemplate->prereq
      ){
        /* 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







>
>
>
>
>
>
>
>







4101
4102
4103
4104
4105
4106
4107
4108
4109
4110
4111
4112
4113
4114
4115
4116
4117
4118
4119
4120
4121
4122
       && p->u.btree.pIndex==pTemplate->u.btree.pIndex
       && p->prereq==pTemplate->prereq
      ){
        /* Overwrite an existing WhereLoop with an similar one that uses
        ** more terms of the index */
        pNext = p->pNextLoop;
        break;
      }else if( p->nOut>pTemplate->nOut
       && p->rSetup==pTemplate->rSetup
       && p->rRun==pTemplate->rRun
      ){
        /* Overwrite an existing WhereLoop with the same cost but more
        ** outputs */
        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
4259
4260
4261
4262
4263
4264
4265
4266
4267
4268
4269
4270
4271
4272
4273
                     pNew->aLTerm[pNew->nLTerm-2] : 0;
    }
    if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
      /* Adjust nOut and rRun for STAT3 range values */
      WhereCost rDiv;
      whereRangeScanEst(pParse, pProbe, pNew->u.btree.nEq,
                        pBtm, pTop, &rDiv);
      pNew->nOut = saved_nOut - rDiv;
    }
#ifdef SQLITE_ENABLE_STAT3
    if( pNew->u.btree.nEq==1 && pProbe->nSample ){
      tRowcnt nOut = 0;
      if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))!=0 ){
        rc = whereEqualScanEst(pParse, pProbe, pTerm->pExpr->pRight, &nOut);
      }else if( (pTerm->eOperator & WO_IN)







|







4284
4285
4286
4287
4288
4289
4290
4291
4292
4293
4294
4295
4296
4297
4298
                     pNew->aLTerm[pNew->nLTerm-2] : 0;
    }
    if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
      /* Adjust nOut and rRun for STAT3 range values */
      WhereCost rDiv;
      whereRangeScanEst(pParse, pProbe, pNew->u.btree.nEq,
                        pBtm, pTop, &rDiv);
      pNew->nOut = saved_nOut>rDiv+10 ? saved_nOut - rDiv : 10;
    }
#ifdef SQLITE_ENABLE_STAT3
    if( pNew->u.btree.nEq==1 && pProbe->nSample ){
      tRowcnt nOut = 0;
      if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))!=0 ){
        rc = whereEqualScanEst(pParse, pProbe, pTerm->pExpr->pRight, &nOut);
      }else if( (pTerm->eOperator & WO_IN)
4478
4479
4480
4481
4482
4483
4484

4485
4486
4487
4488
4489
4490
4491
    /* If there was an INDEXED BY clause, then only that one index is
    ** considered. */
    if( pSrc->pIndex ) break;
  }
  return rc;
}


/*
** Add all WhereLoop objects for a table of the join identified by
** pBuilder->pNew->iTab.  That table is guaranteed to be a virtual table.
*/
static int whereLoopAddVirtual(
  WhereLoopBuilder *pBuilder,  /* WHERE clause information */
  Bitmask mExtra               /* Extra prerequesites for using this table */







>







4503
4504
4505
4506
4507
4508
4509
4510
4511
4512
4513
4514
4515
4516
4517
    /* If there was an INDEXED BY clause, then only that one index is
    ** considered. */
    if( pSrc->pIndex ) break;
  }
  return rc;
}

#ifndef SQLITE_OMIT_VIRTUALTABLE
/*
** Add all WhereLoop objects for a table of the join identified by
** pBuilder->pNew->iTab.  That table is guaranteed to be a virtual table.
*/
static int whereLoopAddVirtual(
  WhereLoopBuilder *pBuilder,  /* WHERE clause information */
  Bitmask mExtra               /* Extra prerequesites for using this table */
4565
4566
4567
4568
4569
4570
4571
4572
4573
4574
4575
4576
4577
4578
4579
4580
    }
    memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
    if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr);
    pIdxInfo->idxStr = 0;
    pIdxInfo->idxNum = 0;
    pIdxInfo->needToFreeIdxStr = 0;
    pIdxInfo->orderByConsumed = 0;
    /* ((WhereCost)2) In case of SQLITE_OMIT_FLOATING_POINT... */
    pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((WhereCost)2);
    rc = vtabBestIndex(pParse, pTab, pIdxInfo);
    if( rc ) goto whereLoopAddVtab_exit;
    pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
    pNew->prereq = 0;
    mxTerm = -1;
    assert( pNew->nLSlot>=nConstraint );
    for(i=0; i<nConstraint; i++) pNew->aLTerm[i] = 0;







<
|







4591
4592
4593
4594
4595
4596
4597

4598
4599
4600
4601
4602
4603
4604
4605
    }
    memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
    if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr);
    pIdxInfo->idxStr = 0;
    pIdxInfo->idxNum = 0;
    pIdxInfo->needToFreeIdxStr = 0;
    pIdxInfo->orderByConsumed = 0;

    pIdxInfo->estimatedCost = SQLITE_BIG_DBL / (double)2;
    rc = vtabBestIndex(pParse, pTab, pIdxInfo);
    if( rc ) goto whereLoopAddVtab_exit;
    pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
    pNew->prereq = 0;
    mxTerm = -1;
    assert( pNew->nLSlot>=nConstraint );
    for(i=0; i<nConstraint; i++) pNew->aLTerm[i] = 0;
4620
4621
4622
4623
4624
4625
4626
4627
4628
4629
4630
4631
4632
4633
4634
4635
4636
4637
4638
4639
4640
4641

4642
4643
4644
4645
4646
4647
4648
      pNew->u.vtab.idxNum = pIdxInfo->idxNum;
      pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr;
      pIdxInfo->needToFreeIdxStr = 0;
      pNew->u.vtab.idxStr = pIdxInfo->idxStr;
      pNew->u.vtab.isOrdered = (u8)((pIdxInfo->nOrderBy!=0)
                                     && pIdxInfo->orderByConsumed);
      pNew->rSetup = 0;
      pNew->rRun = whereCostFromInt((tRowcnt)pIdxInfo->estimatedCost);
      pNew->nOut = 46;  assert( 46 == whereCostFromInt(25) );
      whereLoopInsert(pBuilder, pNew);
      if( pNew->u.vtab.needFree ){
        sqlite3_free(pNew->u.vtab.idxStr);
        pNew->u.vtab.needFree = 0;
      }
    }
  }  

whereLoopAddVtab_exit:
  if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr);
  sqlite3DbFree(db, pIdxInfo);
  return rc;
}


/*
** Add WhereLoop entries to handle OR terms.  This works for either
** btrees or virtual tables.
*/
static int whereLoopAddOr(WhereLoopBuilder *pBuilder, Bitmask mExtra){
  WhereInfo *pWInfo = pBuilder->pWInfo;







|














>







4645
4646
4647
4648
4649
4650
4651
4652
4653
4654
4655
4656
4657
4658
4659
4660
4661
4662
4663
4664
4665
4666
4667
4668
4669
4670
4671
4672
4673
4674
      pNew->u.vtab.idxNum = pIdxInfo->idxNum;
      pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr;
      pIdxInfo->needToFreeIdxStr = 0;
      pNew->u.vtab.idxStr = pIdxInfo->idxStr;
      pNew->u.vtab.isOrdered = (u8)((pIdxInfo->nOrderBy!=0)
                                     && pIdxInfo->orderByConsumed);
      pNew->rSetup = 0;
      pNew->rRun = whereCostFromDouble(pIdxInfo->estimatedCost);
      pNew->nOut = 46;  assert( 46 == whereCostFromInt(25) );
      whereLoopInsert(pBuilder, pNew);
      if( pNew->u.vtab.needFree ){
        sqlite3_free(pNew->u.vtab.idxStr);
        pNew->u.vtab.needFree = 0;
      }
    }
  }  

whereLoopAddVtab_exit:
  if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr);
  sqlite3DbFree(db, pIdxInfo);
  return rc;
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/*
** Add WhereLoop entries to handle OR terms.  This works for either
** btrees or virtual tables.
*/
static int whereLoopAddOr(WhereLoopBuilder *pBuilder, Bitmask mExtra){
  WhereInfo *pWInfo = pBuilder->pWInfo;
4691
4692
4693
4694
4695
4696
4697

4698
4699
4700


4701
4702
4703
4704
4705
4706
4707
          sSubBuild.pWC = &tempWC;
        }else{
          continue;
        }
        sBest.maskSelf = 0;
        sBest.rSetup = 0;
        sBest.rRun = 0;

        if( IsVirtual(pItem->pTab) ){
          rc = whereLoopAddVirtual(&sSubBuild, mExtra);
        }else{


          rc = whereLoopAddBtree(&sSubBuild, mExtra);
        }
        if( sBest.maskSelf==0 ) break;
        assert( sBest.rSetup==0 );
        rTotal = whereCostAdd(rTotal, sBest.rRun);
        nRow = whereCostAdd(nRow, sBest.nOut);
        prereq |= sBest.prereq;







>


|
>
>







4717
4718
4719
4720
4721
4722
4723
4724
4725
4726
4727
4728
4729
4730
4731
4732
4733
4734
4735
4736
          sSubBuild.pWC = &tempWC;
        }else{
          continue;
        }
        sBest.maskSelf = 0;
        sBest.rSetup = 0;
        sBest.rRun = 0;
#ifndef SQLITE_OMIT_VIRTUALTABLE
        if( IsVirtual(pItem->pTab) ){
          rc = whereLoopAddVirtual(&sSubBuild, mExtra);
        }else
#endif
        {
          rc = whereLoopAddBtree(&sSubBuild, mExtra);
        }
        if( sBest.maskSelf==0 ) break;
        assert( sBest.rSetup==0 );
        rTotal = whereCostAdd(rTotal, sBest.rRun);
        nRow = whereCostAdd(nRow, sBest.nOut);
        prereq |= sBest.prereq;
Changes to test/analyze5.test.
152
153
154
155
156
157
158

159
160
161
162
163
164
165
166
167
168
169
170
171
172
  301  {y=1}                 t1y   26
  302  {y=0.1}               t1y    1

  400  {x IS NULL}           t1x  400

} {
  # Verify that the expected index is used with the expected row count

  do_test analyze5-1.${testid}a {
    set x [lindex [eqp "SELECT * FROM t1 WHERE $where"] 3]
    set idx {}
    regexp {INDEX (t1.) } $x all idx
    regexp {~([0-9]+) rows} $x all nrow
    list $idx $nrow
  } [list $index $rows]

  # Verify that the same result is achieved regardless of whether or not
  # the index is used
  do_test analyze5-1.${testid}b {
    set w2 [string map {y +y z +z} $where]
    set a1 [db eval "SELECT rowid FROM t1 NOT INDEXED WHERE $w2\
                     ORDER BY +rowid"]







>
|
|
|
|
|
|
|







152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
  301  {y=1}                 t1y   26
  302  {y=0.1}               t1y    1

  400  {x IS NULL}           t1x  400

} {
  # Verify that the expected index is used with the expected row count
  # No longer valid due to an EXPLAIN QUERY PLAN output format change
  # do_test analyze5-1.${testid}a {
  #   set x [lindex [eqp "SELECT * FROM t1 WHERE $where"] 3]
  #   set idx {}
  #   regexp {INDEX (t1.) } $x all idx
  #   regexp {~([0-9]+) rows} $x all nrow
  #   list $idx $nrow
  # } [list $index $rows]

  # Verify that the same result is achieved regardless of whether or not
  # the index is used
  do_test analyze5-1.${testid}b {
    set w2 [string map {y +y z +z} $where]
    set a1 [db eval "SELECT rowid FROM t1 NOT INDEXED WHERE $w2\
                     ORDER BY +rowid"]
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
  503  {x=1}                               t1x   1
  504  {x IS NOT NULL}                     t1x   2
  505  {+x IS NOT NULL}                     {} 500
  506  {upper(x) IS NOT NULL}               {} 500

} {
  # Verify that the expected index is used with the expected row count
if {$testid==50299} {breakpoint; set sqlite_where_trace 1}
  do_test analyze5-1.${testid}a {
    set x [lindex [eqp "SELECT * FROM t1 WHERE $where"] 3]
    set idx {}
    regexp {INDEX (t1.) } $x all idx
    regexp {~([0-9]+) rows} $x all nrow
    list $idx $nrow
  } [list $index $rows]
if {$testid==50299} exit

  # Verify that the same result is achieved regardless of whether or not
  # the index is used
  do_test analyze5-1.${testid}b {
    set w2 [string map {y +y z +z} $where]
    set a1 [db eval "SELECT rowid FROM t1 NOT INDEXED WHERE $w2\
                     ORDER BY +rowid"]







|
|
|
|
|
|
|
|
<







199
200
201
202
203
204
205
206
207
208
209
210
211
212
213

214
215
216
217
218
219
220
  503  {x=1}                               t1x   1
  504  {x IS NOT NULL}                     t1x   2
  505  {+x IS NOT NULL}                     {} 500
  506  {upper(x) IS NOT NULL}               {} 500

} {
  # Verify that the expected index is used with the expected row count
  # No longer valid due to an EXPLAIN QUERY PLAN format change
  # do_test analyze5-1.${testid}a {
  #   set x [lindex [eqp "SELECT * FROM t1 WHERE $where"] 3]
  #   set idx {}
  #   regexp {INDEX (t1.) } $x all idx
  #   regexp {~([0-9]+) rows} $x all nrow
  #   list $idx $nrow
  # } [list $index $rows]


  # Verify that the same result is achieved regardless of whether or not
  # the index is used
  do_test analyze5-1.${testid}b {
    set w2 [string map {y +y z +z} $where]
    set a1 [db eval "SELECT rowid FROM t1 NOT INDEXED WHERE $w2\
                     ORDER BY +rowid"]
Changes to test/between.test.
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
  set ::sqlite_sort_count 0
  set data [execsql $sql]
  if {$::sqlite_sort_count} {set x sort} {set x nosort}
  lappend data $x
  set eqp [execsql "EXPLAIN QUERY PLAN $sql"]
  # puts eqp=$eqp
  foreach {a b c x} $eqp {
    if {[regexp { TABLE (\w+ AS )?(\w+) USING.* INDEX (\w+)\W} \
        $x all as tab idx]} {
      lappend data $tab $idx
    } elseif {[regexp { TABLE (\w+ AS )?(\w+)\W} $x all as tab]} {
      lappend data $tab *
    }
  }
  return $data   
}

do_test between-1.1.1 {







|


|







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

do_test between-1.1.1 {
Changes to test/eqp.test.
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
}

det 7.1 "SELECT count(*) FROM t1" {
  0 0 0 {SCAN TABLE t1}
}

det 7.2 "SELECT count(*) FROM t2" {
  0 0 0 {SCAN TABLE t2 USING COVERING INDEX i1(~1000000 rows)}
}

do_execsql_test 7.3 {
  INSERT INTO t1 VALUES(1, 2);
  INSERT INTO t1 VALUES(3, 4);

  INSERT INTO t2 VALUES(1, 2);







|







550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
}

det 7.1 "SELECT count(*) FROM t1" {
  0 0 0 {SCAN TABLE t1}
}

det 7.2 "SELECT count(*) FROM t2" {
  0 0 0 {SCAN TABLE t2 USING COVERING INDEX i1}
}

do_execsql_test 7.3 {
  INSERT INTO t1 VALUES(1, 2);
  INSERT INTO t1 VALUES(3, 4);

  INSERT INTO t2 VALUES(1, 2);
572
573
574
575
576
577
578
579
580
581
582
583
sqlite3 db test.db

det 7.4 "SELECT count(*) FROM t1" {
  0 0 0 {SCAN TABLE t1}
}

det 7.5 "SELECT count(*) FROM t2" {
  0 0 0 {SCAN TABLE t2 USING COVERING INDEX i1(~3 rows)}
}


finish_test







|




572
573
574
575
576
577
578
579
580
581
582
583
sqlite3 db test.db

det 7.4 "SELECT count(*) FROM t1" {
  0 0 0 {SCAN TABLE t1}
}

det 7.5 "SELECT count(*) FROM t2" {
  0 0 0 {SCAN TABLE t2 USING COVERING INDEX i1}
}


finish_test