/ Check-in [8d1ba309]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Add a high-speed bypass for the NGQP for the common case of a simply query with quality constraints that outputs a single row.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: 8d1ba309211e8afa8be5520bbc1eecf6deacae07
User & Date: drh 2013-06-10 12:17:03
Context
2013-06-10
12:34
Performance improvements for whereScan methods. check-in: aae14350 user: drh tags: nextgen-query-plan-exp
12:17
Add a high-speed bypass for the NGQP for the common case of a simply query with quality constraints that outputs a single row. check-in: 8d1ba309 user: drh tags: nextgen-query-plan-exp
12:15
Minor problems in the high-speed NGQP fixed. Closed-Leaf check-in: 20eeccf1 user: drh tags: nextgen-query-plan-fast
2013-06-07
02:04
Must faster computation of estimated logarithm. check-in: dfbca3ac user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

4276
4277
4278
4279
4280
4281
4282















4283
4284
4285
4286
4287
4288
4289
....
4384
4385
4386
4387
4388
4389
4390
4391
4392
4393
4394
4395
4396
4397
4398
4399
4400
4401
4402
4403
4404
4405
....
5163
5164
5165
5166
5167
5168
5169













































































5170
5171
5172
5173
5174
5175
5176
....
5303
5304
5305
5306
5307
5308
5309
5310
5311
5312
5313
5314
5315
5316
5317
....
5320
5321
5322
5323
5324
5325
5326


5327
5328
5329
5330
5331
5332
5333
....
5392
5393
5394
5395
5396
5397
5398
5399
5400
5401
5402
5403
5404
5405
5406
5407
5408
5409
5410
5411
5412
5413
5414
5415
5416
5417
5418
5419
5420
5421


5422
5423
5424
5425
5426
5427
5428
5429
    if( pExpr->iTable==iCursor ){
      if( pExpr->iColumn==iCol ) return 1;
      return 0;
    }
  }
  return 0;
}
















/*
** Add all WhereLoop objects a single table of the join were the table
** is idenfied by pBuilder->pNew->iTab.  That table is guaranteed to be
** a b-tree table, not a virtual table.
*/
static int whereLoopAddBtree(
................................................................................
      /* Full table scan */
      pNew->iSortIdx = b ? iSortIdx : 0;
      pNew->nOut = rSize;
      pNew->rRun = (rSize + rLogSize)*(3+b); /* 4x penalty for a full-scan */
      rc = whereLoopInsert(pBuilder, pNew);
      if( rc ) break;
    }else{
      Bitmask m = pSrc->colUsed;
      int j;
      for(j=pProbe->nColumn-1; j>=0; j--){
        int x = pProbe->aiColumn[j];
        if( x<BMS-1 ){
          m &= ~MASKBIT(x);
        }
      }
      pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED;

      /* Full scan via index */
      if( (m==0 || b)
       && pProbe->bUnordered==0
       && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
       && sqlite3GlobalConfig.bUseCis
................................................................................
  }
  pWInfo->nRowOut = pFrom->nRow;

  /* Free temporary memory and return success */
  sqlite3DbFree(db, pSpace);
  return SQLITE_OK;
}














































































/*
** Generate the beginning of the loop used for WHERE clause processing.
** The return value is a pointer to an opaque structure that contains
** information needed to terminate the loop.  Later, the calling routine
** should invoke sqlite3WhereEnd() with the return value of this function
** in order to complete the WHERE clause processing.
................................................................................
  ** struct, the contents of WhereInfo.a[], the WhereClause structure
  ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
  ** field (type Bitmask) it must be aligned on an 8-byte boundary on
  ** some architectures. Hence the ROUND8() below.
  */
  db = pParse->db;
  nByteWInfo = ROUND8(sizeof(WhereInfo)+(nTabList-1)*sizeof(WhereLevel));
  pWInfo = sqlite3DbMallocZero(db, nByteWInfo);
  if( db->mallocFailed ){
    sqlite3DbFree(db, pWInfo);
    pWInfo = 0;
    goto whereBeginError;
  }
  pWInfo->nLevel = nTabList;
  pWInfo->pParse = pParse;
................................................................................
  pWInfo->pDistinct = pDistinct;
  pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
  pWInfo->wctrlFlags = wctrlFlags;
  pWInfo->savedNQueryLoop = pParse->nQueryLoop;
  pMaskSet = &pWInfo->sMaskSet;
  sWLB.pWInfo = pWInfo;
  sWLB.pWC = &pWInfo->sWC;



  /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
  ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
  if( OptimizationDisabled(db, SQLITE_DistinctOpt) ) pDistinct = 0;

  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.
................................................................................
  if( pDistinct && isDistinctRedundant(pParse,pTabList,&pWInfo->sWC,pDistinct) ){
    pDistinct = 0;
    pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
  }

  /* Construct the WhereLoop objects */
  WHERETRACE(("*** Optimizer Start ***\n"));
  /* TBD: if( nTablist==1 ) whereCommonCase(&sWLB); */
  rc = whereLoopAddAll(&sWLB);
  if( rc ) goto whereBeginError;

  /* Display all of the WhereLoop objects if wheretrace is enabled */
#ifdef WHERETRACE_ENABLED
  if( sqlite3WhereTrace ){
    WhereLoop *p;
    int i = 0;
    static char zLabel[] = "0123456789abcdefghijklmnopqrstuvwyxz"
                                     "ABCDEFGHIJKLMNOPQRSTUVWYXZ";
    for(p=pWInfo->pLoops; p; p=p->pNextLoop){
      p->cId = zLabel[(i++)%sizeof(zLabel)];
      whereLoopPrint(p, pTabList);
    }
  }
#endif

  wherePathSolver(pWInfo, -1);
  if( db->mallocFailed ) goto whereBeginError;
  if( pWInfo->pOrderBy ){
     wherePathSolver(pWInfo, pWInfo->nRowOut);
     if( db->mallocFailed ) goto whereBeginError;


  }else if( db->flags & SQLITE_ReverseOrder ){
     pWInfo->revMask = (Bitmask)(-1);
  }
  if( pParse->nErr || db->mallocFailed ){
    goto whereBeginError;
  }
#ifdef WHERETRACE_ENABLED
  if( sqlite3WhereTrace ){







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







 







|
<
<
<
<
<
<
<







 







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







 







|







 







>
>







 







|
|
|
|
|

|
|
|
|
|
|
|
|
|
|

|
|
|
|
|
|
>
>
|







4276
4277
4278
4279
4280
4281
4282
4283
4284
4285
4286
4287
4288
4289
4290
4291
4292
4293
4294
4295
4296
4297
4298
4299
4300
4301
4302
4303
4304
....
4399
4400
4401
4402
4403
4404
4405
4406







4407
4408
4409
4410
4411
4412
4413
....
5171
5172
5173
5174
5175
5176
5177
5178
5179
5180
5181
5182
5183
5184
5185
5186
5187
5188
5189
5190
5191
5192
5193
5194
5195
5196
5197
5198
5199
5200
5201
5202
5203
5204
5205
5206
5207
5208
5209
5210
5211
5212
5213
5214
5215
5216
5217
5218
5219
5220
5221
5222
5223
5224
5225
5226
5227
5228
5229
5230
5231
5232
5233
5234
5235
5236
5237
5238
5239
5240
5241
5242
5243
5244
5245
5246
5247
5248
5249
5250
5251
5252
5253
5254
5255
5256
5257
5258
5259
5260
5261
....
5388
5389
5390
5391
5392
5393
5394
5395
5396
5397
5398
5399
5400
5401
5402
....
5405
5406
5407
5408
5409
5410
5411
5412
5413
5414
5415
5416
5417
5418
5419
5420
....
5479
5480
5481
5482
5483
5484
5485
5486
5487
5488
5489
5490
5491
5492
5493
5494
5495
5496
5497
5498
5499
5500
5501
5502
5503
5504
5505
5506
5507
5508
5509
5510
5511
5512
5513
5514
5515
5516
5517
5518
    if( pExpr->iTable==iCursor ){
      if( pExpr->iColumn==iCol ) return 1;
      return 0;
    }
  }
  return 0;
}

/*
** Return a bitmask where 1s indicate that the corresponding column of
** the table is used by an index.  Only the first 63 columns are considered.
*/
static Bitmask columnsUsedByIndex(Index *pIdx){
  Bitmask m = 0;
  int j;
  for(j=pIdx->nColumn-1; j>=0; j--){
    int x = pIdx->aiColumn[j];
    if( x<BMS-1 ) m |= MASKBIT(x);
  }
  return m;
}


/*
** Add all WhereLoop objects a single table of the join were the table
** is idenfied by pBuilder->pNew->iTab.  That table is guaranteed to be
** a b-tree table, not a virtual table.
*/
static int whereLoopAddBtree(
................................................................................
      /* Full table scan */
      pNew->iSortIdx = b ? iSortIdx : 0;
      pNew->nOut = rSize;
      pNew->rRun = (rSize + rLogSize)*(3+b); /* 4x penalty for a full-scan */
      rc = whereLoopInsert(pBuilder, pNew);
      if( rc ) break;
    }else{
      Bitmask m = pSrc->colUsed & ~columnsUsedByIndex(pProbe);







      pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED;

      /* Full scan via index */
      if( (m==0 || b)
       && pProbe->bUnordered==0
       && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
       && sqlite3GlobalConfig.bUseCis
................................................................................
  }
  pWInfo->nRowOut = pFrom->nRow;

  /* Free temporary memory and return success */
  sqlite3DbFree(db, pSpace);
  return SQLITE_OK;
}

/*
** Most queries use only a single table (they are not joins) and have
** simple == constraints against indexed fields.  This routine attempts
** to plan those simple cases using much less ceremony than the
** general-purpose query planner, and thereby yield faster sqlite3_prepare()
** times for the common case.
**
** Return non-zero on success, if this query can be handled by this
** no-frills query planner.  Return zero if this query needs the 
** general-purpose query planner.
*/
static int whereSimpleFastCase(WhereLoopBuilder *pBuilder){
  WhereInfo *pWInfo;
  struct SrcList_item *pItem;
  WhereClause *pWC;
  WhereTerm *pTerm;
  WhereLoop *pLoop;
  int iCur;
  int j;
  int nOrderBy;
  Table *pTab;
  Index *pIdx;
  
  pWInfo = pBuilder->pWInfo;
  assert( pWInfo->pTabList->nSrc>=1 );
  pItem = pWInfo->pTabList->a;
  pTab = pItem->pTab;
  if( IsVirtual(pTab) ) return 0;
  if( pItem->zIndex ) return 0;
  iCur = pItem->iCursor;
  pWC = &pWInfo->sWC;
  pLoop = pBuilder->pNew;
  pWInfo->a[0].pWLoop = pLoop;
  pLoop->wsFlags = 0;
  pLoop->maskSelf = getMask(&pWInfo->sMaskSet, iCur);
  pWInfo->a[0].iTabCur = iCur;
#ifdef SQLITE_DEBUG
  pLoop->cId = '0';
#endif
  nOrderBy = pWInfo->pOrderBy ? pWInfo->pOrderBy->nExpr : 0;
  pTerm = findTerm(pWC, iCur, -1, 1, WO_EQ, 0);
  if( pTerm ){
    pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_IPK|WHERE_ONEROW;
    pLoop->aLTerm[0] = pTerm;
    pLoop->nLTerm = 1;
    pLoop->u.btree.nEq = 1;
    pLoop->rRun = (WhereCost)10;
    pLoop->nOut = (WhereCost)1;
    pWInfo->nRowOut = 1;
    pWInfo->nOBSat = nOrderBy;
  }else{
    for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
      if( pIdx->onError==OE_None ) continue;
      for(j=0; j<pIdx->nColumn; j++){
        pTerm = findTerm(pWC, iCur, pIdx->aiColumn[j], 1, WO_EQ, pIdx);
        if( pTerm==0 ) break;
        whereLoopResize(pWInfo->pParse->db, pLoop, j);
        pLoop->aLTerm[j] = pTerm;
      }
      if( j!=pIdx->nColumn ) continue;
      pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_ONEROW|WHERE_INDEXED;
      if( (pItem->colUsed & ~columnsUsedByIndex(pIdx))==0 ){
        pLoop->wsFlags |= WHERE_IDX_ONLY;
      }
      pLoop->nLTerm = j;
      pLoop->u.btree.nEq = j;
      pLoop->u.btree.pIndex = pIdx;
      pLoop->rRun = (WhereCost)15;
      pLoop->nOut = (WhereCost)1;
      pWInfo->nRowOut = 1;
      pWInfo->nOBSat = nOrderBy;
      break;
    }
  }
  return pLoop->wsFlags!=0;
}

/*
** Generate the beginning of the loop used for WHERE clause processing.
** The return value is a pointer to an opaque structure that contains
** information needed to terminate the loop.  Later, the calling routine
** should invoke sqlite3WhereEnd() with the return value of this function
** in order to complete the WHERE clause processing.
................................................................................
  ** struct, the contents of WhereInfo.a[], the WhereClause structure
  ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
  ** field (type Bitmask) it must be aligned on an 8-byte boundary on
  ** some architectures. Hence the ROUND8() below.
  */
  db = pParse->db;
  nByteWInfo = ROUND8(sizeof(WhereInfo)+(nTabList-1)*sizeof(WhereLevel));
  pWInfo = sqlite3DbMallocZero(db, nByteWInfo + sizeof(WhereLoop));
  if( db->mallocFailed ){
    sqlite3DbFree(db, pWInfo);
    pWInfo = 0;
    goto whereBeginError;
  }
  pWInfo->nLevel = nTabList;
  pWInfo->pParse = pParse;
................................................................................
  pWInfo->pDistinct = pDistinct;
  pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
  pWInfo->wctrlFlags = wctrlFlags;
  pWInfo->savedNQueryLoop = pParse->nQueryLoop;
  pMaskSet = &pWInfo->sMaskSet;
  sWLB.pWInfo = pWInfo;
  sWLB.pWC = &pWInfo->sWC;
  sWLB.pNew = (WhereLoop*)&pWInfo->a[nTabList];
  whereLoopInit(sWLB.pNew);

  /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
  ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
  if( OptimizationDisabled(db, SQLITE_DistinctOpt) ) pDistinct = 0;

  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.
................................................................................
  if( pDistinct && isDistinctRedundant(pParse,pTabList,&pWInfo->sWC,pDistinct) ){
    pDistinct = 0;
    pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
  }

  /* Construct the WhereLoop objects */
  WHERETRACE(("*** Optimizer Start ***\n"));
  if( nTabList!=1 || whereSimpleFastCase(&sWLB)==0 ){
    rc = whereLoopAddAll(&sWLB);
    if( rc ) goto whereBeginError;
  
    /* Display all of the WhereLoop objects if wheretrace is enabled */
#ifdef WHERETRACE_ENABLED
    if( sqlite3WhereTrace ){
      WhereLoop *p;
      int i = 0;
      static char zLabel[] = "0123456789abcdefghijklmnopqrstuvwyxz"
                                       "ABCDEFGHIJKLMNOPQRSTUVWYXZ";
      for(p=pWInfo->pLoops; p; p=p->pNextLoop){
        p->cId = zLabel[(i++)%sizeof(zLabel)];
        whereLoopPrint(p, pTabList);
      }
    }
#endif
  
    wherePathSolver(pWInfo, -1);
    if( db->mallocFailed ) goto whereBeginError;
    if( pWInfo->pOrderBy ){
       wherePathSolver(pWInfo, pWInfo->nRowOut);
       if( db->mallocFailed ) goto whereBeginError;
    }
  }
  if( pWInfo->pOrderBy==0 && (db->flags & SQLITE_ReverseOrder)!=0 ){
     pWInfo->revMask = (Bitmask)(-1);
  }
  if( pParse->nErr || db->mallocFailed ){
    goto whereBeginError;
  }
#ifdef WHERETRACE_ENABLED
  if( sqlite3WhereTrace ){