SQLite

Check-in [586b55d8d7]
Login

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

Overview
Comment:Update the NGQP so that it can produce plans that include automatic indices.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: 586b55d8d7722de1c0530b3b832bae0511e6d05c
User & Date: drh 2013-05-10 15:16:30.669
Context
2013-05-10
20:26
Now generating OR-clause plans. (check-in: e17003fcfe user: drh tags: nextgen-query-plan-exp)
15:16
Update the NGQP so that it can produce plans that include automatic indices. (check-in: 586b55d8d7 user: drh tags: nextgen-query-plan-exp)
03:30
Factor out common operations into whereLoopAddAll(). Add stubs for missing features. (check-in: 0278e42061 user: drh tags: nextgen-query-plan-exp)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
285
286
287
288
289
290
291

292
293
294
295
296
297
298
  WhereInfo *pWInfo;        /* Information about this WHERE */
  sqlite3 *db;              /* Database connection */
  Parse *pParse;            /* Parsing context */
  WhereClause *pWC;         /* WHERE clause terms */
  SrcList *pTabList;        /* FROM clause */
  ExprList *pOrderBy;       /* ORDER BY clause */
  WhereLoop *pNew;          /* Template WhereLoop */

};

/*
** Bitmasks for the operators that indices are able to exploit.  An
** OR-ed combination of these values can be used when searching for
** terms in the where clause.
*/







>







285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
  WhereInfo *pWInfo;        /* Information about this WHERE */
  sqlite3 *db;              /* Database connection */
  Parse *pParse;            /* Parsing context */
  WhereClause *pWC;         /* WHERE clause terms */
  SrcList *pTabList;        /* FROM clause */
  ExprList *pOrderBy;       /* ORDER BY clause */
  WhereLoop *pNew;          /* Template WhereLoop */
  int mxTerm;               /* Maximum number of aTerm[] entries on pNew */
};

/*
** Bitmasks for the operators that indices are able to exploit.  An
** OR-ed combination of these values can be used when searching for
** terms in the where clause.
*/
5237
5238
5239
5240
5241
5242
5243

5244
5245
5246
5247
5248
5249
5250
  WhereLoop *pNew;                /* Template WhereLoop under construction */
  WhereTerm *pTerm;               /* A WhereTerm under consideration */
  int opMask;                     /* Valid operators for constraints */
  WhereScan scan;                 /* Iterator for WHERE terms */
  WhereLoop savedLoop;            /* Saved original content of pNew[] */
  int iCol;                       /* Index of the column in the table */
  int rc = SQLITE_OK;             /* Return code */


  db = pBuilder->db;
  pNew = pBuilder->pNew;
  if( db->mallocFailed ) return SQLITE_NOMEM;

  assert( (pNew->wsFlags & WHERE_VIRTUALTABLE)==0 );
  assert( pNew->u.btree.nEq<pProbe->nColumn );







>







5238
5239
5240
5241
5242
5243
5244
5245
5246
5247
5248
5249
5250
5251
5252
  WhereLoop *pNew;                /* Template WhereLoop under construction */
  WhereTerm *pTerm;               /* A WhereTerm under consideration */
  int opMask;                     /* Valid operators for constraints */
  WhereScan scan;                 /* Iterator for WHERE terms */
  WhereLoop savedLoop;            /* Saved original content of pNew[] */
  int iCol;                       /* Index of the column in the table */
  int rc = SQLITE_OK;             /* Return code */
  double rLogSize;                /* Logarithm of table size */

  db = pBuilder->db;
  pNew = pBuilder->pNew;
  if( db->mallocFailed ) return SQLITE_NOMEM;

  assert( (pNew->wsFlags & WHERE_VIRTUALTABLE)==0 );
  assert( pNew->u.btree.nEq<pProbe->nColumn );
5258
5259
5260
5261
5262
5263
5264

5265
5266
5267
5268

5269
5270
5271
5272
5273
5274
5275
  }

  iCol = pProbe->aiColumn[pNew->u.btree.nEq];
  pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol,
                        opMask, iCol>=0 ? pProbe : 0);
  savedLoop = *pNew;
  pNew->rSetup = (double)0;

  for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
    int nIn = 1;
    pNew->u.btree.nEq = savedLoop.u.btree.nEq;
    pNew->nTerm = savedLoop.nTerm;

    pNew->aTerm[pNew->nTerm++] = pTerm;
    pNew->prereq = (savedLoop.prereq | pTerm->prereqRight) & ~pNew->maskSelf;
    if( pTerm->eOperator & WO_IN ){
      Expr *pExpr = pTerm->pExpr;
      pNew->wsFlags |= WHERE_COLUMN_IN;
      if( ExprHasProperty(pExpr, EP_xIsSelect) ){
        /* "x IN (SELECT ...)":  Assume the SELECT returns 25 rows */







>




>







5260
5261
5262
5263
5264
5265
5266
5267
5268
5269
5270
5271
5272
5273
5274
5275
5276
5277
5278
5279
  }

  iCol = pProbe->aiColumn[pNew->u.btree.nEq];
  pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol,
                        opMask, iCol>=0 ? pProbe : 0);
  savedLoop = *pNew;
  pNew->rSetup = (double)0;
  rLogSize = estLog(pProbe->aiRowEst[0]);
  for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
    int nIn = 1;
    pNew->u.btree.nEq = savedLoop.u.btree.nEq;
    pNew->nTerm = savedLoop.nTerm;
    if( pNew->nTerm>=pBuilder->mxTerm ) break; /* Repeated column in index */
    pNew->aTerm[pNew->nTerm++] = pTerm;
    pNew->prereq = (savedLoop.prereq | pTerm->prereqRight) & ~pNew->maskSelf;
    if( pTerm->eOperator & WO_IN ){
      Expr *pExpr = pTerm->pExpr;
      pNew->wsFlags |= WHERE_COLUMN_IN;
      if( ExprHasProperty(pExpr, EP_xIsSelect) ){
        /* "x IN (SELECT ...)":  Assume the SELECT returns 25 rows */
5287
5288
5289
5290
5291
5292
5293






5294



5295
5296
5297
5298
5299
5300
5301
    }else if( pTerm->eOperator & (WO_GT|WO_GE) ){
      pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_BTM_LIMIT;
      pNew->nOut = savedLoop.nOut/3;
    }else if( pTerm->eOperator & (WO_LT|WO_LE) ){
      pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT;
      pNew->nOut = savedLoop.nOut/3;
    }






    pNew->rRun = pNew->nOut + estLog(pProbe->aiRowEst[0])*nIn;



    rc = whereLoopInsert(pBuilder->pWInfo, pNew);
    if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
     && pNew->u.btree.nEq<pProbe->nColumn
    ){
      whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul*nIn);
    }
  }







>
>
>
>
>
>
|
>
>
>







5291
5292
5293
5294
5295
5296
5297
5298
5299
5300
5301
5302
5303
5304
5305
5306
5307
5308
5309
5310
5311
5312
5313
5314
    }else if( pTerm->eOperator & (WO_GT|WO_GE) ){
      pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_BTM_LIMIT;
      pNew->nOut = savedLoop.nOut/3;
    }else if( pTerm->eOperator & (WO_LT|WO_LE) ){
      pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT;
      pNew->nOut = savedLoop.nOut/3;
    }
    pNew->rRun = rLogSize*nIn;  /* Cost for nIn binary searches */
    if( pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK) ){
      pNew->rRun += pNew->nOut;  /* Unit step cost to reach each row */
    }else{
      /* Each row involves a step of the index, then a binary search of
      ** the main table */
      pNew->rRun += pNew->nOut*(1 + rLogSize);
    }
    /* TBD: Adjust nOut and rRun for STAT3 range values */
    /* TBD: Adjust nOut for additional constraints */
    rc = whereLoopInsert(pBuilder->pWInfo, pNew);
    if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
     && pNew->u.btree.nEq<pProbe->nColumn
    ){
      whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul*nIn);
    }
  }
5314
5315
5316
5317
5318
5319
5320


5321
5322
5323
5324
5325
5326
5327
  Index *pProbe;              /* An index we are evaluating */
  Index sPk;                  /* A fake index object for the primary key */
  tRowcnt aiRowEstPk[2];      /* The aiRowEst[] value for the sPk index */
  int aiColumnPk = -1;        /* The aColumn[] value for the sPk index */
  struct SrcList_item *pSrc;  /* The FROM clause btree term to add */
  WhereLoop *pNew;            /* Template WhereLoop object */
  int rc = SQLITE_OK;         /* Return code */



  pNew = pBuilder->pNew;
  pSrc = pBuilder->pTabList->a + pNew->iTab;

  if( pSrc->pIndex ){
    /* An INDEXED BY clause specifies a particular index to use */
    pProbe = pSrc->pIndex;







>
>







5327
5328
5329
5330
5331
5332
5333
5334
5335
5336
5337
5338
5339
5340
5341
5342
  Index *pProbe;              /* An index we are evaluating */
  Index sPk;                  /* A fake index object for the primary key */
  tRowcnt aiRowEstPk[2];      /* The aiRowEst[] value for the sPk index */
  int aiColumnPk = -1;        /* The aColumn[] value for the sPk index */
  struct SrcList_item *pSrc;  /* The FROM clause btree term to add */
  WhereLoop *pNew;            /* Template WhereLoop object */
  int rc = SQLITE_OK;         /* Return code */
  double rSize;               /* number of rows in the table */
  double rLogSize;            /* Logarithm of the number of rows in the table */

  pNew = pBuilder->pNew;
  pSrc = pBuilder->pTabList->a + pNew->iTab;

  if( pSrc->pIndex ){
    /* An INDEXED BY clause specifies a particular index to use */
    pProbe = pSrc->pIndex;
5343
5344
5345
5346
5347
5348
5349



























5350
5351
5352
5353
5354
5355
5356
5357
5358
5359


5360
5361
5362
5363
5364
5365
5366
5367
5368
5369
5370
    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;
    }
    pProbe = &sPk;
  }




























  /* Insert a full table scan */
  pNew->u.btree.nEq = 0;
  pNew->nTerm = 0;
  pNew->rSetup = (double)0;
  pNew->prereq = mExtra;
  pNew->u.btree.pIndex = 0;
  pNew->wsFlags = 0;
  pNew->rRun = (double)pSrc->pTab->nRowEst;
  pNew->nOut = (double)pSrc->pTab->nRowEst;


  rc = whereLoopInsert(pBuilder->pWInfo, pNew);

  /* TBD: Insert automatic index opportunities */

  /* Loop over all indices
  */
  for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext){
    pNew->u.btree.nEq = 0;
    pNew->nTerm = 0;
    if( pProbe->tnum<=0 ){
      /* Integer primary key index */







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








<
|
>
>


<
<







5358
5359
5360
5361
5362
5363
5364
5365
5366
5367
5368
5369
5370
5371
5372
5373
5374
5375
5376
5377
5378
5379
5380
5381
5382
5383
5384
5385
5386
5387
5388
5389
5390
5391
5392
5393
5394
5395
5396
5397
5398
5399

5400
5401
5402
5403
5404


5405
5406
5407
5408
5409
5410
5411
    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;
    }
    pProbe = &sPk;
  }
  rSize = (double)pSrc->pTab->nRowEst;
  rLogSize = estLog(rSize);

  /* Automatic indexes */
  if( (pBuilder->pParse->db->flags & SQLITE_AutoIndex)!=0 
   && !pSrc->viaCoroutine
   && !pSrc->notIndexed
   && !pSrc->isCorrelated
  ){
    /* Generate auto-index WhereLoops */
    WhereClause *pWC = pBuilder->pWC;
    WhereTerm *pTerm;
    WhereTerm *pWCEnd = pWC->a + pWC->nTerm;
    for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){
      if( termCanDriveIndex(pTerm, pSrc, 0) ){
        pNew->u.btree.nEq = 1;
        pNew->nTerm = 1;
        pNew->aTerm[0] = pTerm;
        pNew->rSetup = 2*rLogSize*pSrc->pTab->nRowEst;
        pNew->nOut = (double)10;
        pNew->rRun = rLogSize + pNew->nOut;
        pNew->wsFlags = WHERE_TEMP_INDEX;
        pNew->prereq = mExtra | pTerm->prereqRight;
        rc = whereLoopInsert(pBuilder->pWInfo, pNew);
      }
    }
  }

  /* Insert a full table scan */
  pNew->u.btree.nEq = 0;
  pNew->nTerm = 0;
  pNew->rSetup = (double)0;
  pNew->prereq = mExtra;
  pNew->u.btree.pIndex = 0;
  pNew->wsFlags = 0;

  pNew->nOut = rSize;
  pNew->rRun = rSize + rLogSize;
  /* TBD: Reduce nOut using constraints */
  rc = whereLoopInsert(pBuilder->pWInfo, pNew);



  /* Loop over all indices
  */
  for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext){
    pNew->u.btree.nEq = 0;
    pNew->nTerm = 0;
    if( pProbe->tnum<=0 ){
      /* Integer primary key index */
5474
5475
5476
5477
5478
5479
5480

5481
5482
5483
5484
5485
5486
5487
    pIdxInfo->orderByConsumed = 0;
    /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */
    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;

    for(i=0; i<pIdxInfo->nConstraint; i++) pNew->aTerm[i] = 0;
    mxTerm = -1;
    for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
      if( (iTerm = pUsage[i].argvIndex - 1)>=0 ){
        j = pIdxCons->iTermOffset;
        if( iTerm>=pIdxInfo->nConstraint
         || j<0







>







5515
5516
5517
5518
5519
5520
5521
5522
5523
5524
5525
5526
5527
5528
5529
    pIdxInfo->orderByConsumed = 0;
    /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */
    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;
    assert( pIdxInfo->nConstraint<=pBuilder->mxTerm );
    for(i=0; i<pIdxInfo->nConstraint; i++) pNew->aTerm[i] = 0;
    mxTerm = -1;
    for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
      if( (iTerm = pUsage[i].argvIndex - 1)>=0 ){
        j = pIdxCons->iTermOffset;
        if( iTerm>=pIdxInfo->nConstraint
         || j<0
5551
5552
5553
5554
5555
5556
5557






5558
5559
5560
5561
5562
5563
5564
5565
  int nTabList = pBuilder->pWInfo->nLevel;
  int rc = SQLITE_OK;
  WhereLoop *pNew;

  /* Loop over the tables in the join, from left to right */
  pBuilder->pNew = pNew = sqlite3DbMallocZero(db, sizeof(WhereLoop));
  if( pNew==0 ) return SQLITE_NOMEM;






  pNew->aTerm = sqlite3DbMallocZero(db, (pWC->nTerm+1)*sizeof(pNew->aTerm[0]));
  if( pNew->aTerm==0 ){
    rc = SQLITE_NOMEM;
    goto whereLoopAddAll_end;
  }
  for(iTab=0, pItem=pTabList->a; iTab<nTabList; iTab++, pItem++){
    pNew->iTab = iTab;
    pNew->maskSelf = getMask(pWC->pMaskSet, pItem->iCursor);







>
>
>
>
>
>
|







5593
5594
5595
5596
5597
5598
5599
5600
5601
5602
5603
5604
5605
5606
5607
5608
5609
5610
5611
5612
5613
  int nTabList = pBuilder->pWInfo->nLevel;
  int rc = SQLITE_OK;
  WhereLoop *pNew;

  /* Loop over the tables in the join, from left to right */
  pBuilder->pNew = pNew = sqlite3DbMallocZero(db, sizeof(WhereLoop));
  if( pNew==0 ) return SQLITE_NOMEM;
  pBuilder->mxTerm = pWC->nTerm+1;
  while( pWC->pOuter ){
    pWC = pWC->pOuter;
    pBuilder->mxTerm += pWC->nTerm;
  }
  pWC = pBuilder->pWC;
  pNew->aTerm = sqlite3DbMallocZero(db,pBuilder->mxTerm*sizeof(pNew->aTerm[0]));
  if( pNew->aTerm==0 ){
    rc = SQLITE_NOMEM;
    goto whereLoopAddAll_end;
  }
  for(iTab=0, pItem=pTabList->a; iTab<nTabList; iTab++, pItem++){
    pNew->iTab = iTab;
    pNew->maskSelf = getMask(pWC->pMaskSet, pItem->iCursor);
6327
6328
6329
6330
6331
6332
6333











6334
6335
6336
6337
6338
6339
6340
  */
  assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
  if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){
    pWInfo->okOnePass = 1;
    pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY;
  }












  /* Open all tables in the pTabList and any indices selected for
  ** searching those tables.
  */
  sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  notReady = ~(Bitmask)0;
  pWInfo->nRowOut = (double)1;
  for(ii=0, pLevel=pWInfo->a; ii<nTabList; ii++, pLevel++){







>
>
>
>
>
>
>
>
>
>
>







6375
6376
6377
6378
6379
6380
6381
6382
6383
6384
6385
6386
6387
6388
6389
6390
6391
6392
6393
6394
6395
6396
6397
6398
6399
  */
  assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
  if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){
    pWInfo->okOnePass = 1;
    pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY;
  }

#if 0
  /* Scaffolding:  Check the new query plan against the old.  Report any
  ** discrepencies */
  for(ii=0; ii<nTabList; ii++){
    if( pWInfo->a[ii].iFrom!=pWInfo->a[ii].pWLoop->iTab ){
      sqlite3DebugPrintf("(QP-Mismatch)");
      break;
    }
  }
#endif

  /* Open all tables in the pTabList and any indices selected for
  ** searching those tables.
  */
  sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  notReady = ~(Bitmask)0;
  pWInfo->nRowOut = (double)1;
  for(ii=0, pLevel=pWInfo->a; ii<nTabList; ii++, pLevel++){