SQLite

Check-in [c5a6ec0a88]
Login

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

Overview
Comment:Changes to the way the planner calculates the costs of various table and index scans. Some test cases still failing.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | experimental-costs
Files: files | file ages | folders
SHA1: c5a6ec0a880652dc8f4593d9f7acd58ddc3dc5f3
User & Date: dan 2014-04-24 20:04:49.939
Context
2014-04-25
15:01
Store values loaded from the stat1 table as logarithmic values in memory. (check-in: 1bd74c49dd user: dan tags: experimental-costs)
2014-04-24
20:04
Changes to the way the planner calculates the costs of various table and index scans. Some test cases still failing. (check-in: c5a6ec0a88 user: dan tags: experimental-costs)
2014-04-21
13:36
Comment tweaks on the test case for the [b75a9ca6b0] bug fix. (check-in: 65d2544af9 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
    }
    pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
  }
  pTerm = &pWC->a[idx = pWC->nTerm++];
  if( p && ExprHasProperty(p, EP_Unlikely) ){
    pTerm->truthProb = sqlite3LogEst(p->iTable) - 99;
  }else{
    pTerm->truthProb = -1;
  }
  pTerm->pExpr = sqlite3ExprSkipCollate(p);
  pTerm->wtFlags = wtFlags;
  pTerm->pWC = pWC;
  pTerm->iParent = -1;
  return idx;
}







|







223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
    }
    pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
  }
  pTerm = &pWC->a[idx = pWC->nTerm++];
  if( p && ExprHasProperty(p, EP_Unlikely) ){
    pTerm->truthProb = sqlite3LogEst(p->iTable) - 99;
  }else{
    pTerm->truthProb = 1;
  }
  pTerm->pExpr = sqlite3ExprSkipCollate(p);
  pTerm->wtFlags = wtFlags;
  pTerm->pWC = pWC;
  pTerm->iParent = -1;
  return idx;
}
1970
1971
1972
1973
1974
1975
1976

























1977
1978
1979
1980
1981
1982
1983
    }else{
      iGap = iGap/3;
    }
    aStat[0] = iLower + iGap;
  }
}
#endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */


























/*
** This function is used to estimate the number of rows that will be visited
** by scanning an index for a range of values. The range may have an upper
** bound, a lower bound, or both. The WHERE clause terms that set the upper
** and lower bounds are represented by pLower and pUpper respectively. For
** example, assuming that index p is on t1(a):







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







1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
    }else{
      iGap = iGap/3;
    }
    aStat[0] = iLower + iGap;
  }
}
#endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */

/*
** If it is not NULL, pTerm is a term that provides an upper or lower
** bound on a range scan. Without considering pTerm, it is estimated 
** that the scan will visit nNew rows. This function returns the number
** estimated to be visited after taking pTerm into account.
**
** If the user explicitly specified a likelihood() value for this term,
** then the return value is the likelihood multiplied by the number of
** input rows. Otherwise, this function assumes that an "IS NOT NULL" term
** has a likelihood of 0.50, and any other term a likelihood of 0.25.
*/
static LogEst whereRangeAdjust(WhereTerm *pTerm, LogEst nNew){
  LogEst nRet = nNew;
  if( pTerm ){
    if( pTerm->truthProb<=0 ){
      nRet += pTerm->truthProb;
    }else if( pTerm->wtFlags & TERM_VNULL ){
      nRet -= 10;        assert( 10==sqlite3LogEst(2) );
    }else{
      nRet -= 20;        assert( 20==sqlite3LogEst(4) );
    }
  }
  return nRet;
}

/*
** This function is used to estimate the number of rows that will be visited
** by scanning an index for a range of values. The range may have an upper
** bound, a lower bound, or both. The WHERE clause terms that set the upper
** and lower bounds are represented by pLower and pUpper respectively. For
** example, assuming that index p is on t1(a):
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
    }
  }
#else
  UNUSED_PARAMETER(pParse);
  UNUSED_PARAMETER(pBuilder);
#endif
  assert( pLower || pUpper );
  /* TUNING:  Each inequality constraint reduces the search space 4-fold.
  ** A BETWEEN operator, therefore, reduces the search space 16-fold */
  nNew = nOut;
  if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ){
    nNew -= 20;        assert( 20==sqlite3LogEst(4) );
    nOut--;
  }
  if( pUpper ){
    nNew -= 20;        assert( 20==sqlite3LogEst(4) );
    nOut--;
  }
  if( nNew<10 ) nNew = 10;
  if( nNew<nOut ) nOut = nNew;
  pLoop->nOut = (LogEst)nOut;
  return rc;
}

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4







<
<
|
<
<
<
<
|
<
|
<







2148
2149
2150
2151
2152
2153
2154


2155




2156

2157

2158
2159
2160
2161
2162
2163
2164
    }
  }
#else
  UNUSED_PARAMETER(pParse);
  UNUSED_PARAMETER(pBuilder);
#endif
  assert( pLower || pUpper );


  nNew = whereRangeAdjust(pLower, nOut);




  nNew = whereRangeAdjust(pUpper, nNew);

  nOut -= (pLower!=0) + (pUpper!=0);

  if( nNew<10 ) nNew = 10;
  if( nNew<nOut ) nOut = nNew;
  pLoop->nOut = (LogEst)nOut;
  return rc;
}

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
3983
3984
3985
3986
3987
3988
3989
3990


3991
3992
3993
3994
3995
3996
3997
    if( (pTerm->prereqAll & notAllowed)!=0 ) continue;
    for(j=pLoop->nLTerm-1; j>=0; j--){
      pX = pLoop->aLTerm[j];
      if( pX==0 ) continue;
      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.
**







|
>
>







4000
4001
4002
4003
4004
4005
4006
4007
4008
4009
4010
4011
4012
4013
4014
4015
4016
    if( (pTerm->prereqAll & notAllowed)!=0 ) continue;
    for(j=pLoop->nLTerm-1; j>=0; j--){
      pX = pLoop->aLTerm[j];
      if( pX==0 ) continue;
      if( pX==pTerm ) break;
      if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break;
    }
    if( j<0 ){
      pLoop->nOut += (pTerm->truthProb<=0 ? pTerm->truthProb : -1);
    }
  }
}

/*
** We have so far matched pBuilder->pNew->u.btree.nEq terms of the index pIndex.
** Try to match one more.
**
4077
4078
4079
4080
4081
4082
4083

4084
4085
4086
4087
4088
4089
4090
    nIter = sqlite3LogEst(pProbe->aiRowEst[0]/pProbe->aiRowEst[saved_nEq+1]);
    pNew->rRun = rLogSize + nIter;
    pNew->nOut += nIter;
    whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter);
    pNew->nOut = saved_nOut;
  }
  for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){

    int nIn = 0;
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
    int nRecValid = pBuilder->nRecValid;
#endif
    if( (pTerm->eOperator==WO_ISNULL || (pTerm->wtFlags&TERM_VNULL)!=0)
     && (iCol<0 || pSrc->pTab->aCol[iCol].notNull)
    ){







>







4096
4097
4098
4099
4100
4101
4102
4103
4104
4105
4106
4107
4108
4109
4110
    nIter = sqlite3LogEst(pProbe->aiRowEst[0]/pProbe->aiRowEst[saved_nEq+1]);
    pNew->rRun = rLogSize + nIter;
    pNew->nOut += nIter;
    whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter);
    pNew->nOut = saved_nOut;
  }
  for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
    LogEst rCostIdx;
    int nIn = 0;
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
    int nRecValid = pBuilder->nRecValid;
#endif
    if( (pTerm->eOperator==WO_ISNULL || (pTerm->wtFlags&TERM_VNULL)!=0)
     && (iCol<0 || pSrc->pTab->aCol[iCol].notNull)
    ){
4150
4151
4152
4153
4154
4155
4156
4157

4158
4159
4160
4161
4162
4163
4164
      testcase( pTerm->eOperator & WO_LE );
      pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT;
      pTop = pTerm;
      pBtm = (pNew->wsFlags & WHERE_BTM_LIMIT)!=0 ?
                     pNew->aLTerm[pNew->nLTerm-2] : 0;
    }
    if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
      /* Adjust nOut and rRun for STAT3 range values */

      assert( pNew->nOut==saved_nOut );
      whereRangeScanEst(pParse, pBuilder, pBtm, pTop, pNew);
    }
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
    if( nInMul==0 
     && pProbe->nSample 
     && pNew->u.btree.nEq<=pProbe->nSampleCol







|
>







4170
4171
4172
4173
4174
4175
4176
4177
4178
4179
4180
4181
4182
4183
4184
4185
      testcase( pTerm->eOperator & WO_LE );
      pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT;
      pTop = pTerm;
      pBtm = (pNew->wsFlags & WHERE_BTM_LIMIT)!=0 ?
                     pNew->aLTerm[pNew->nLTerm-2] : 0;
    }
    if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
      /* Adjust nOut using stat3/stat4 data. Or, if there is no stat3/stat4
      ** data, using some other estimate.  */
      assert( pNew->nOut==saved_nOut );
      whereRangeScanEst(pParse, pBuilder, pBtm, pTop, pNew);
    }
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
    if( nInMul==0 
     && pProbe->nSample 
     && pNew->u.btree.nEq<=pProbe->nSampleCol
4177
4178
4179
4180
4181
4182
4183






4184
4185
4186
4187
4188
4189
4190
4191
4192
4193
4194
4195
4196
4197
      assert( nOut==0 || rc==SQLITE_OK );
      if( nOut ){
        pNew->nOut = sqlite3LogEst(nOut);
        if( pNew->nOut>saved_nOut ) pNew->nOut = saved_nOut;
      }
    }
#endif






    if( (pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK))==0 ){
      /* Each row involves a step of the index, then a binary search of
      ** the main table */
      pNew->rRun =  sqlite3LogEstAdd(pNew->rRun,rLogSize>27 ? rLogSize-17 : 10);
    }
    /* Step cost for each output row */
    pNew->rRun = sqlite3LogEstAdd(pNew->rRun, pNew->nOut);
    whereLoopOutputAdjust(pBuilder->pWC, pNew);
    rc = whereLoopInsert(pBuilder, pNew);
    if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
     && pNew->u.btree.nEq<(pProbe->nKeyCol + (pProbe->zName!=0))
    ){
      whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul+nIn);
    }







>
>
>
>
>
>

<
<
|

|
<







4198
4199
4200
4201
4202
4203
4204
4205
4206
4207
4208
4209
4210
4211


4212
4213
4214

4215
4216
4217
4218
4219
4220
4221
      assert( nOut==0 || rc==SQLITE_OK );
      if( nOut ){
        pNew->nOut = sqlite3LogEst(nOut);
        if( pNew->nOut>saved_nOut ) pNew->nOut = saved_nOut;
      }
    }
#endif
    /* Set rCostIdx to the cost of visiting selected rows in index. Add
    ** it to pNew->rRun, which is currently set to the cost of the index
    ** seek only. Then, if this is a non-covering index, add the cost of
    ** visiting the rows in the main table.  */
    rCostIdx = pNew->nOut + 1 + (15*pProbe->szIdxRow)/pSrc->pTab->szTabRow;
    pNew->rRun = sqlite3LogEstAdd(pNew->rRun, rCostIdx);
    if( (pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK))==0 ){


      pNew->rRun = sqlite3LogEstAdd(pNew->rRun, pNew->nOut + 16);
    }


    whereLoopOutputAdjust(pBuilder->pWC, pNew);
    rc = whereLoopInsert(pBuilder, pNew);
    if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
     && pNew->u.btree.nEq<(pProbe->nKeyCol + (pProbe->zName!=0))
    ){
      whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul+nIn);
    }
4315
4316
4317
4318
4319
4320
4321

4322
4323
4324
4325
4326
4327
4328
    Index *pFirst;                  /* First of real indices on the table */
    memset(&sPk, 0, sizeof(Index));
    sPk.nKeyCol = 1;
    sPk.aiColumn = &aiColumnPk;
    sPk.aiRowEst = aiRowEstPk;
    sPk.onError = OE_Replace;
    sPk.pTable = pTab;

    aiRowEstPk[0] = pTab->nRowEst;
    aiRowEstPk[1] = 1;
    pFirst = pSrc->pTab->pIndex;
    if( pSrc->notIndexed==0 ){
      /* The real indices of the table are only considered if the
      ** NOT INDEXED qualifier is omitted from the FROM clause */
      sPk.pNext = pFirst;







>







4339
4340
4341
4342
4343
4344
4345
4346
4347
4348
4349
4350
4351
4352
4353
    Index *pFirst;                  /* First of real indices on the table */
    memset(&sPk, 0, sizeof(Index));
    sPk.nKeyCol = 1;
    sPk.aiColumn = &aiColumnPk;
    sPk.aiRowEst = aiRowEstPk;
    sPk.onError = OE_Replace;
    sPk.pTable = pTab;
    sPk.szIdxRow = pTab->szTabRow;
    aiRowEstPk[0] = pTab->nRowEst;
    aiRowEstPk[1] = 1;
    pFirst = pSrc->pTab->pIndex;
    if( pSrc->notIndexed==0 ){
      /* The real indices of the table are only considered if the
      ** NOT INDEXED qualifier is omitted from the FROM clause */
      sPk.pNext = pFirst;
4392
4393
4394
4395
4396
4397
4398
4399
4400
4401
4402
4403
4404
4405
4406
4407
4408
4409
    assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || b==0 );
    if( pProbe->tnum<=0 ){
      /* Integer primary key index */
      pNew->wsFlags = WHERE_IPK;

      /* Full table scan */
      pNew->iSortIdx = b ? iSortIdx : 0;
      /* TUNING: Cost of full table scan is 3*(N + log2(N)).
      **  +  The extra 3 factor is to encourage the use of indexed lookups
      **     over full scans.  FIXME */
      pNew->rRun = sqlite3LogEstAdd(rSize,rLogSize) + 16;
      whereLoopOutputAdjust(pWC, pNew);
      rc = whereLoopInsert(pBuilder, pNew);
      pNew->nOut = rSize;
      if( rc ) break;
    }else{
      Bitmask m;
      if( pProbe->isCovering ){







|
<
<
|







4417
4418
4419
4420
4421
4422
4423
4424


4425
4426
4427
4428
4429
4430
4431
4432
    assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || b==0 );
    if( pProbe->tnum<=0 ){
      /* Integer primary key index */
      pNew->wsFlags = WHERE_IPK;

      /* Full table scan */
      pNew->iSortIdx = b ? iSortIdx : 0;
      /* TUNING: Cost of full table scan is (N*3.0). */


      pNew->rRun = rSize + 16;
      whereLoopOutputAdjust(pWC, pNew);
      rc = whereLoopInsert(pBuilder, pNew);
      pNew->nOut = rSize;
      if( rc ) break;
    }else{
      Bitmask m;
      if( pProbe->isCovering ){
4422
4423
4424
4425
4426
4427
4428
4429
4430
4431
4432
4433
4434
4435
4436
4437
4438
4439
4440
4441

4442
4443
4444
4445
4446
4447
4448
4449
4450
4451
4452
4453
4454
4455
4456
4457

4458
4459
4460
4461
4462
4463
4464
         && (pProbe->szIdxRow<pTab->szTabRow)
         && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
         && sqlite3GlobalConfig.bUseCis
         && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
          )
      ){
        pNew->iSortIdx = b ? iSortIdx : 0;
        /* TUNING:  The base cost of an index scan is N + log2(N).
        ** The log2(N) is for the initial seek to the beginning and the N
        ** is for the scan itself. */
        pNew->rRun = sqlite3LogEstAdd(rSize, rLogSize);
        if( m==0 ){
          /* TUNING: Cost of a covering index scan is K*(N + log2(N)).
          **  +  The extra factor K of between 1.1 and 3.0 that depends
          **     on the relative sizes of the table and the index.  K
          **     is smaller for smaller indices, thus favoring them.
          **     The upper bound on K (3.0) matches the penalty factor
          **     on a full table scan that tries to encourage the use of
          **     indexed lookups over full scans.
          */

          pNew->rRun +=  1 + (15*pProbe->szIdxRow)/pTab->szTabRow;
        }else{
          /* TUNING: The cost of scanning a non-covering index is multiplied
          ** by log2(N) to account for the binary search of the main table
          ** that must happen for each row of the index.
          ** TODO: Should there be a multiplier here, analogous to the 3x
          ** multiplier for a fulltable scan or covering index scan, to
          ** further discourage the use of an index scan?  Or is the log2(N)
          ** term sufficient discouragement?
          ** TODO: What if some or all of the WHERE clause terms can be
          ** computed without reference to the original table.  Then the
          ** penality should reduce to logK where K is the number of output
          ** rows.
          */
          pNew->rRun += rLogSize;
        }

        whereLoopOutputAdjust(pWC, pNew);
        rc = whereLoopInsert(pBuilder, pNew);
        pNew->nOut = rSize;
        if( rc ) break;
      }
    }








|
<
<
<
<
|
<
|
<
<
<
|
<
>
|
<
<
<
<
<
<
<
<
<
<
<
|
<
|

>







4445
4446
4447
4448
4449
4450
4451
4452




4453

4454



4455

4456
4457











4458

4459
4460
4461
4462
4463
4464
4465
4466
4467
4468
         && (pProbe->szIdxRow<pTab->szTabRow)
         && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
         && sqlite3GlobalConfig.bUseCis
         && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
          )
      ){
        pNew->iSortIdx = b ? iSortIdx : 0;





        /* The cost of visiting the index rows is N*K, where K is

        ** between 1.1 and 3.0, depending on the relative sizes of the



        ** index and table rows. If this is a non-covering index scan,

        ** also add the cost of visiting table rows (N*3.0).  */
        pNew->rRun = rSize + 1 + (15*pProbe->szIdxRow)/pTab->szTabRow;











        if( m!=0 ){

          pNew->rRun = sqlite3LogEstAdd(pNew->rRun, rSize+16);
        }

        whereLoopOutputAdjust(pWC, pNew);
        rc = whereLoopInsert(pBuilder, pNew);
        pNew->nOut = rSize;
        if( rc ) break;
      }
    }

4728
4729
4730
4731
4732
4733
4734
4735
4736
4737
4738
4739
4740
4741
4742
4743
      pNew->nLTerm = 1;
      pNew->aLTerm[0] = pTerm;
      pNew->wsFlags = WHERE_MULTI_OR;
      pNew->rSetup = 0;
      pNew->iSortIdx = 0;
      memset(&pNew->u, 0, sizeof(pNew->u));
      for(i=0; rc==SQLITE_OK && i<sSum.n; i++){
        /* TUNING: Multiple by 3.5 for the secondary table lookup */
        pNew->rRun = sSum.a[i].rRun + 18;
        pNew->nOut = sSum.a[i].nOut;
        pNew->prereq = sSum.a[i].prereq;
        rc = whereLoopInsert(pBuilder, pNew);
      }
    }
  }
  return rc;







<
|







4732
4733
4734
4735
4736
4737
4738

4739
4740
4741
4742
4743
4744
4745
4746
      pNew->nLTerm = 1;
      pNew->aLTerm[0] = pTerm;
      pNew->wsFlags = WHERE_MULTI_OR;
      pNew->rSetup = 0;
      pNew->iSortIdx = 0;
      memset(&pNew->u, 0, sizeof(pNew->u));
      for(i=0; rc==SQLITE_OK && i<sSum.n; i++){

        pNew->rRun = sSum.a[i].rRun;
        pNew->nOut = sSum.a[i].nOut;
        pNew->prereq = sSum.a[i].prereq;
        rc = whereLoopInsert(pBuilder, pNew);
      }
    }
  }
  return rc;
Changes to test/analyze9.test.
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
  for {set i 0} {$i<100} {incr i} {
    if {$i %2} {set a abc} else {set a def}
    execsql { INSERT INTO t1(rowid, a, b, c) VALUES($i, $a, $i, $i) }
  }
  execsql ANALYZE
} {}
do_eqp_test 13.2.1 {
  SELECT * FROM t1 WHERE a='abc' AND rowid<15 AND b<20
} {/SEARCH TABLE t1 USING INDEX i1/}
do_eqp_test 13.2.2 {
  SELECT * FROM t1 WHERE a='abc' AND rowid<'15' AND b<20
} {/SEARCH TABLE t1 USING INDEX i1/}
do_eqp_test 13.3.1 {
  SELECT * FROM t1 WHERE a='abc' AND rowid<100 AND b<20
} {/SEARCH TABLE t1 USING INDEX i2/}
do_eqp_test 13.3.2 {
  SELECT * FROM t1 WHERE a='abc' AND rowid<'100' AND b<20
} {/SEARCH TABLE t1 USING INDEX i2/}

#-------------------------------------------------------------------------
# Check also that affinities are taken into account when using stat4 data 
# to estimate the number of rows scanned by any other constraint on a 
# column other than the leftmost.
#







|


|


|


|







573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
  for {set i 0} {$i<100} {incr i} {
    if {$i %2} {set a abc} else {set a def}
    execsql { INSERT INTO t1(rowid, a, b, c) VALUES($i, $a, $i, $i) }
  }
  execsql ANALYZE
} {}
do_eqp_test 13.2.1 {
  SELECT * FROM t1 WHERE a='abc' AND rowid<15 AND b<12
} {/SEARCH TABLE t1 USING INDEX i1/}
do_eqp_test 13.2.2 {
  SELECT * FROM t1 WHERE a='abc' AND rowid<'15' AND b<12
} {/SEARCH TABLE t1 USING INDEX i1/}
do_eqp_test 13.3.1 {
  SELECT * FROM t1 WHERE a='abc' AND rowid<100 AND b<12
} {/SEARCH TABLE t1 USING INDEX i2/}
do_eqp_test 13.3.2 {
  SELECT * FROM t1 WHERE a='abc' AND rowid<'100' AND b<12
} {/SEARCH TABLE t1 USING INDEX i2/}

#-------------------------------------------------------------------------
# Check also that affinities are taken into account when using stat4 data 
# to estimate the number of rows scanned by any other constraint on a 
# column other than the leftmost.
#
Changes to test/autoindex1.test.
93
94
95
96
97
98
99


100
101
102
103
104
105
106
  db status autoindex
} {0}
do_test autoindex1-210 {
  db eval {
    PRAGMA automatic_index=ON;
    ANALYZE;
    UPDATE sqlite_stat1 SET stat='10000' WHERE tbl='t1';


    ANALYZE sqlite_master;
    SELECT b, (SELECT d FROM t2 WHERE c=a) FROM t1;
  }
} {11 911 22 922 33 933 44 944 55 955 66 966 77 977 88 988}
do_test autoindex1-211 {
  db status step
} {7}







>
>







93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
  db status autoindex
} {0}
do_test autoindex1-210 {
  db eval {
    PRAGMA automatic_index=ON;
    ANALYZE;
    UPDATE sqlite_stat1 SET stat='10000' WHERE tbl='t1';
    -- Table t2 actually contains 8 rows.
    UPDATE sqlite_stat1 SET stat='16' WHERE tbl='t2';
    ANALYZE sqlite_master;
    SELECT b, (SELECT d FROM t2 WHERE c=a) FROM t1;
  }
} {11 911 22 922 33 933 44 944 55 955 66 966 77 977 88 988}
do_test autoindex1-211 {
  db status step
} {7}
Changes to test/where3.test.
227
228
229
230
231
232
233

234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
# the planner into use a table for the outer loop that might be indexable
# if held until an inner loop.
# 
do_execsql_test where3-3.0 {
  CREATE TABLE t301(a INTEGER PRIMARY KEY,b,c);
  CREATE INDEX t301c ON t301(c);
  INSERT INTO t301 VALUES(1,2,3);

  CREATE TABLE t302(x, y);
  INSERT INTO t302 VALUES(4,5);
  ANALYZE;
  explain query plan SELECT * FROM t302, t301 WHERE t302.x=5 AND t301.a=t302.y;
} {
  0 0 0 {SCAN TABLE t302} 
  0 1 1 {SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?)}
}
do_execsql_test where3-3.1 {
  explain query plan
  SELECT * FROM t301, t302 WHERE t302.x=5 AND t301.a=t302.y;
} {
  0 0 1 {SCAN TABLE t302} 
  0 1 0 {SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?)}
}
do_execsql_test where3-3.2 {
  SELECT * FROM t301 WHERE c=3 AND a IS NULL;
} {}
do_execsql_test where3-3.3 {
  SELECT * FROM t301 WHERE c=3 AND a IS NOT NULL;
} {1 2 3}

if 0 {  # Query planner no longer does this
# Verify that when there are multiple tables in a join which must be
# full table scans that the query planner attempts put the table with
# the fewest number of output rows as the outer loop.
#
do_execsql_test where3-4.0 {







>




















|







227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
# the planner into use a table for the outer loop that might be indexable
# if held until an inner loop.
# 
do_execsql_test where3-3.0 {
  CREATE TABLE t301(a INTEGER PRIMARY KEY,b,c);
  CREATE INDEX t301c ON t301(c);
  INSERT INTO t301 VALUES(1,2,3);
  INSERT INTO t301 VALUES(2,2,3);
  CREATE TABLE t302(x, y);
  INSERT INTO t302 VALUES(4,5);
  ANALYZE;
  explain query plan SELECT * FROM t302, t301 WHERE t302.x=5 AND t301.a=t302.y;
} {
  0 0 0 {SCAN TABLE t302} 
  0 1 1 {SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?)}
}
do_execsql_test where3-3.1 {
  explain query plan
  SELECT * FROM t301, t302 WHERE t302.x=5 AND t301.a=t302.y;
} {
  0 0 1 {SCAN TABLE t302} 
  0 1 0 {SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?)}
}
do_execsql_test where3-3.2 {
  SELECT * FROM t301 WHERE c=3 AND a IS NULL;
} {}
do_execsql_test where3-3.3 {
  SELECT * FROM t301 WHERE c=3 AND a IS NOT NULL;
} {1 2 3 2 2 3}

if 0 {  # Query planner no longer does this
# Verify that when there are multiple tables in a join which must be
# full table scans that the query planner attempts put the table with
# the fewest number of output rows as the outer loop.
#
do_execsql_test where3-4.0 {
Changes to test/whereG.test.
10
11
12
13
14
15
16

17
18
19
20
21
22
23
#***********************************************************************
# 
# Test cases for query planning decisions and the unlikely() and
# likelihood() functions.

set testdir [file dirname $argv0]
source $testdir/tester.tcl


do_execsql_test whereG-1.0 {
  CREATE TABLE composer(
    cid INTEGER PRIMARY KEY,
    cname TEXT
  );
  CREATE TABLE album(







>







10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#***********************************************************************
# 
# Test cases for query planning decisions and the unlikely() and
# likelihood() functions.

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix whereG

do_execsql_test whereG-1.0 {
  CREATE TABLE composer(
    cid INTEGER PRIMARY KEY,
    cname TEXT
  );
  CREATE TABLE album(
175
176
177
178
179
180
181

182





























183

  INSERT INTO t4 VALUES('right'),('wrong');
  SELECT DISTINCT x
   FROM (SELECT x FROM t4 GROUP BY x)
   WHERE x='right'
   ORDER BY x;
} {right}
































finish_test








>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

>
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
  INSERT INTO t4 VALUES('right'),('wrong');
  SELECT DISTINCT x
   FROM (SELECT x FROM t4 GROUP BY x)
   WHERE x='right'
   ORDER BY x;
} {right}

#-------------------------------------------------------------------------
# 

reset_db
do_execsql_test 5.1 {
  CREATE TABLE t1(a, b, c);
  CREATE INDEX i1 ON t1(a, b);
}
do_eqp_test 5.1.2 {
  SELECT * FROM t1 WHERE a>?
} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a>?)}}
do_eqp_test 5.1.3 {
  SELECT * FROM t1 WHERE likelihood(a>?, 0.9)
} {0 0 0 {SCAN TABLE t1}}

do_test 5.2 {
  for {set i 0} {$i < 100} {incr i} {
    execsql { INSERT INTO t1 VALUES('abc', $i, $i); }
  }
  execsql { INSERT INTO t1 SELECT 'def', b, c FROM t1; }
  execsql { ANALYZE }
} {}

do_eqp_test 5.2.2 {
  SELECT * FROM t1 WHERE likelihood(b>?, 0.01)
} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (ANY(a) AND b>?)}}

do_eqp_test 5.2.3 {
  SELECT * FROM t1 WHERE likelihood(b>?, 0.9)
} {0 0 0 {SCAN TABLE t1}}

finish_test