/ Check-in [e17003fc]
Login

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

Overview
Comment:Now generating OR-clause plans.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: e17003fcfec0c0b524b1b9ff8e15e7ee83efa571
User & Date: drh 2013-05-10 20:26:22
Context
2013-05-11
00:06
Minor fixes to the OR-clause processing in the NGQP. check-in: d6946f33 user: drh tags: nextgen-query-plan-exp
2013-05-10
20:26
Now generating OR-clause plans. check-in: e17003fc user: drh tags: nextgen-query-plan-exp
15:16
Update the NGQP so that it can produce plans that include automatic indices. check-in: 586b55d8 user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

285
286
287
288
289
290
291

292
293
294
295
296
297
298
....
5158
5159
5160
5161
5162
5163
5164
5165
5166
5167
5168

















5169
5170
5171
5172
5173
5174
5175
....
5206
5207
5208
5209
5210
5211
5212
5213
5214
5215
5216
5217


5218
5219
5220
5221
5222
5223
5224
....
5301
5302
5303
5304
5305
5306
5307
5308
5309
5310
5311
5312
5313
5314
5315
....
5362
5363
5364
5365
5366
5367
5368

5369
5370
5371
5372
5373
5374
5375
5376
....
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
....
5561
5562
5563
5564
5565
5566
5567
5568
5569
5570
5571
5572
5573
5574
5575
5576
5577
5578
5579
5580














































































5581
5582
5583
5584
5585
5586
5587
....
5615
5616
5617
5618
5619
5620
5621
5622
5623
5624
5625
5626
5627
5628
5629
5630
5631
5632
5633
  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.
................................................................................
**
** An existing WhereLoop entry might be overwritten if the new template
** is better and has fewer dependencies.  Or the template will be ignored
** and no insert will occur if an existing WhereLoop is faster and has
** fewer dependencies than the template.  Otherwise a new WhereLoop is
** added based no the template.
*/
static int whereLoopInsert(WhereInfo *pWInfo, WhereLoop *pTemplate){
  WhereLoop **ppPrev, *p, *pNext = 0, *pToFree = 0;
  WhereTerm **paTerm = 0;
  sqlite3 *db = pWInfo->pParse->db;


















  /* Search for an existing WhereLoop to overwrite, or which takes
  ** priority over pTemplate.
  */
  for(ppPrev=&pWInfo->pLoops, p=*ppPrev; p; ppPrev=&p->pNextLoop, p=*ppPrev){
    if( p->iTab!=pTemplate->iTab ) continue;
    if( (p->prereq & pTemplate->prereq)==p->prereq
................................................................................
      return SQLITE_NOMEM;
    }
  }
  *p = *pTemplate;
  p->pNextLoop = pNext;
  *ppPrev = p;
  p->aTerm = paTerm;
  if( pTemplate->nTerm ){
    memcpy(p->aTerm, pTemplate->aTerm, pTemplate->nTerm*sizeof(p->aTerm[0]));
  }
  if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
    if( p->u.btree.pIndex && p->u.btree.pIndex->tnum==0 ) p->u.btree.pIndex = 0;


  }else{
    pTemplate->u.vtab.needFree = 0;
  }
  return SQLITE_OK;
}

/*
................................................................................
    }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);
    }
  }
  *pNew = savedLoop;
................................................................................
    }
    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;
................................................................................
        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 ){
................................................................................
      pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr;
      pIdxInfo->needToFreeIdxStr = 0;
      pNew->u.vtab.idxStr = pIdxInfo->idxStr;
      pNew->u.vtab.isOrdered = (u8)(pIdxInfo->nOrderBy!=0);
      pNew->rSetup = (double)0;
      pNew->rRun = pIdxInfo->estimatedCost;
      pNew->nOut = (double)25;
      whereLoopInsert(pBuilder->pWInfo, 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 all WhereLoop objects for all tables 
*/
static int whereLoopAddAll(WhereLoopBuilder *pBuilder){
  Bitmask mExtra = 0;
  Bitmask mPrior = 0;
................................................................................
      mExtra = mPrior;
    }
    if( IsVirtual(pItem->pTab) ){
      rc = whereLoopAddVirtual(pBuilder, mExtra);
    }else{
      rc = whereLoopAddBtree(pBuilder, mExtra);
    }
#if 0
    if( rc==SQLITE_OK ){
      rc = whereLoopAddOr(pBuilder, mExtra);
    }
#endif
    mPrior |= pNew->maskSelf;
    if( rc || db->mallocFailed ) break;
  }
whereLoopAddAll_end:
  whereLoopDelete(db, pBuilder->pNew);
  pBuilder->pNew = 0;
  return rc;







>







 







|


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







 







|
|


|
>
>







 







|







 







>
|







 







|







 







|







 







|












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







 







<



<







285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
....
5159
5160
5161
5162
5163
5164
5165
5166
5167
5168
5169
5170
5171
5172
5173
5174
5175
5176
5177
5178
5179
5180
5181
5182
5183
5184
5185
5186
5187
5188
5189
5190
5191
5192
5193
....
5224
5225
5226
5227
5228
5229
5230
5231
5232
5233
5234
5235
5236
5237
5238
5239
5240
5241
5242
5243
5244
....
5321
5322
5323
5324
5325
5326
5327
5328
5329
5330
5331
5332
5333
5334
5335
....
5382
5383
5384
5385
5386
5387
5388
5389
5390
5391
5392
5393
5394
5395
5396
5397
....
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
5430
5431
....
5582
5583
5584
5585
5586
5587
5588
5589
5590
5591
5592
5593
5594
5595
5596
5597
5598
5599
5600
5601
5602
5603
5604
5605
5606
5607
5608
5609
5610
5611
5612
5613
5614
5615
5616
5617
5618
5619
5620
5621
5622
5623
5624
5625
5626
5627
5628
5629
5630
5631
5632
5633
5634
5635
5636
5637
5638
5639
5640
5641
5642
5643
5644
5645
5646
5647
5648
5649
5650
5651
5652
5653
5654
5655
5656
5657
5658
5659
5660
5661
5662
5663
5664
5665
5666
5667
5668
5669
5670
5671
5672
5673
5674
5675
5676
5677
5678
5679
5680
5681
5682
5683
5684
5685
5686
....
5714
5715
5716
5717
5718
5719
5720

5721
5722
5723

5724
5725
5726
5727
5728
5729
5730
  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 */
  WhereLoop *pBest;         /* If non-NULL, store single best loop here */
  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.
................................................................................
**
** An existing WhereLoop entry might be overwritten if the new template
** is better and has fewer dependencies.  Or the template will be ignored
** and no insert will occur if an existing WhereLoop is faster and has
** fewer dependencies than the template.  Otherwise a new WhereLoop is
** added based no the template.
*/
static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
  WhereLoop **ppPrev, *p, *pNext = 0, *pToFree = 0;
  WhereTerm **paTerm = 0;
  sqlite3 *db = pBuilder->db;
  WhereInfo *pWInfo = pBuilder->pWInfo;

  if( (p = pBuilder->pBest)!=0 ){
    if( p->maskSelf!=0 ){
      if( p->rRun+p->rSetup < pTemplate->rRun+pTemplate->rSetup ){
        return SQLITE_OK;
      }
      if( p->rRun+p->rSetup == pTemplate->rRun+pTemplate->rSetup
       && p->prereq <= pTemplate->prereq ){
        return SQLITE_OK;
      }
    }
    *p = *pTemplate;
    p->aTerm = 0;
    p->u.vtab.needFree = 0;
    return SQLITE_OK;
  }

  /* Search for an existing WhereLoop to overwrite, or which takes
  ** priority over pTemplate.
  */
  for(ppPrev=&pWInfo->pLoops, p=*ppPrev; p; ppPrev=&p->pNextLoop, p=*ppPrev){
    if( p->iTab!=pTemplate->iTab ) continue;
    if( (p->prereq & pTemplate->prereq)==p->prereq
................................................................................
      return SQLITE_NOMEM;
    }
  }
  *p = *pTemplate;
  p->pNextLoop = pNext;
  *ppPrev = p;
  p->aTerm = paTerm;
  if( p->nTerm ){
    memcpy(p->aTerm, pTemplate->aTerm, p->nTerm*sizeof(p->aTerm[0]));
  }
  if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
    if( p->u.btree.pIndex && p->u.btree.pIndex->tnum==0 ){
      p->u.btree.pIndex = 0;
    }
  }else{
    pTemplate->u.vtab.needFree = 0;
  }
  return SQLITE_OK;
}

/*
................................................................................
    }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, pNew);
    if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
     && pNew->u.btree.nEq<pProbe->nColumn
    ){
      whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul*nIn);
    }
  }
  *pNew = savedLoop;
................................................................................
    }
    pProbe = &sPk;
  }
  rSize = (double)pSrc->pTab->nRowEst;
  rLogSize = estLog(rSize);

  /* Automatic indexes */
  if( !pBuilder->pBest
   && (pBuilder->pParse->db->flags & SQLITE_AutoIndex)!=0 
   && !pSrc->viaCoroutine
   && !pSrc->notIndexed
   && !pSrc->isCorrelated
  ){
    /* Generate auto-index WhereLoops */
    WhereClause *pWC = pBuilder->pWC;
    WhereTerm *pTerm;
................................................................................
        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, 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, 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 ){
................................................................................
      pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr;
      pIdxInfo->needToFreeIdxStr = 0;
      pNew->u.vtab.idxStr = pIdxInfo->idxStr;
      pNew->u.vtab.isOrdered = (u8)(pIdxInfo->nOrderBy!=0);
      pNew->rSetup = (double)0;
      pNew->rRun = pIdxInfo->estimatedCost;
      pNew->nOut = (double)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){
  WhereClause *pWC;
  WhereLoop *pNew;
  WhereTerm *pTerm, *pWCEnd;
  int rc = SQLITE_OK;
  int iCur;
  WhereClause tempWC;
  WhereLoopBuilder sSubBuild;
  WhereLoop sBest;
  struct SrcList_item *pItem;
  

  pWC = pBuilder->pWC;
  if( pWC->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK;
  pWCEnd = pWC->a + pWC->nTerm;
  pNew = pBuilder->pNew;
  pItem = pBuilder->pTabList->a + pNew->iTab;
  iCur = pItem->iCursor;
  sSubBuild = *pBuilder;
  sSubBuild.pOrderBy = 0;
  sSubBuild.pBest = &sBest;
  tempWC.pParse = pWC->pParse;
  tempWC.pMaskSet = pWC->pMaskSet;
  tempWC.pOuter = pWC;
  tempWC.op = TK_AND;
  tempWC.wctrlFlags = 0;
  tempWC.nTerm = 1;

  for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){
    if( (pTerm->eOperator & WO_OR)!=0
     && (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0 
    ){
      WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
      WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
      WhereTerm *pOrTerm;
      double rTotal = 0;
      double nRow = 0;
      Bitmask prereq = mExtra;


      for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
        if( (pOrTerm->eOperator& WO_AND)!=0 ){
          sSubBuild.pWC = &pOrTerm->u.pAndInfo->wc;
        }else if( pOrTerm->leftCursor==iCur ){
          tempWC.a = pOrTerm;
          sSubBuild.pWC = &tempWC;
        }else{
          continue;
        }
        sBest.maskSelf = 0;
        if( IsVirtual(pItem->pTab) ){
          rc = whereLoopAddVirtual(&sSubBuild, mExtra);
        }else{
          rc = whereLoopAddBtree(&sSubBuild, mExtra);
        }
        if( sBest.maskSelf==0 ) break;
        assert( sBest.rSetup==(double)0 );
        rTotal += sBest.rRun;
        nRow += sBest.nOut;
        prereq |= sBest.prereq;
      }
      pNew->nTerm = 1;
      pNew->aTerm[0] = pTerm;
      pNew->wsFlags = WHERE_MULTI_OR;
      pNew->rSetup = (double)0;
      pNew->rRun = rTotal;
      pNew->nOut = nRow;
      pNew->prereq = prereq;
      rc = whereLoopInsert(pBuilder, pNew);
    }
  }
  return rc;
}

/*
** Add all WhereLoop objects for all tables 
*/
static int whereLoopAddAll(WhereLoopBuilder *pBuilder){
  Bitmask mExtra = 0;
  Bitmask mPrior = 0;
................................................................................
      mExtra = mPrior;
    }
    if( IsVirtual(pItem->pTab) ){
      rc = whereLoopAddVirtual(pBuilder, mExtra);
    }else{
      rc = whereLoopAddBtree(pBuilder, mExtra);
    }

    if( rc==SQLITE_OK ){
      rc = whereLoopAddOr(pBuilder, mExtra);
    }

    mPrior |= pNew->maskSelf;
    if( rc || db->mallocFailed ) break;
  }
whereLoopAddAll_end:
  whereLoopDelete(db, pBuilder->pNew);
  pBuilder->pNew = 0;
  return rc;