/ Check-in [0278e420]
Login

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

Overview
Comment:Factor out common operations into whereLoopAddAll(). Add stubs for missing features.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: 0278e420614e02fb2d8474ed99b0904275882dfe
User & Date: drh 2013-05-10 03:30:49
Context
2013-05-10
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
03:30
Factor out common operations into whereLoopAddAll(). Add stubs for missing features. check-in: 0278e420 user: drh tags: nextgen-query-plan-exp
02:11
Merge in the latest trunk changes. check-in: 5ed31c82 user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

5305
5306
5307
5308
5309
5310
5311
5312
5313
5314
5315
5316
5317
5318
5319
5320
5321
5322
5323
5324
5325
5326
5327
5328
5329
5330
5331
5332
5333
5334
....
5349
5350
5351
5352
5353
5354
5355
5356
5357
5358
5359
5360
5361
5362
5363
5364
5365
5366


5367
5368
5369
5370
5371
5372
5373
5374
5375
5376
5377
5378
5379
....
5382
5383
5384
5385
5386
5387
5388
5389
5390
5391
5392
5393
5394
5395
5396
5397
5398
5399
....
5403
5404
5405
5406
5407
5408
5409
5410
5411
5412
5413
5414
5415
5416
5417
....
5421
5422
5423
5424
5425
5426
5427
5428
5429
5430
5431
5432
5433

5434
5435
5436
5437
5438
5439
5440
5441
5442
5443
5444
5445
5446
5447
5448
5449
5450
5451
5452
5453
5454
5455
....
5567
5568
5569
5570
5571
5572
5573

5574
5575
5576
5577
5578
5579
5580
5581

5582
5583


5584
5585
5586
5587











5588
5589

5590
5591
5592
5593
5594
5595
5596

/*
** Add all WhereLoop objects for the iTab-th table of the join.  That
** table is guaranteed to be a b-tree table, not a virtual table.
*/
static int whereLoopAddBtree(
  WhereLoopBuilder *pBuilder, /* WHERE clause information */
  int iTab,                   /* The table to process */
  Bitmask mExtra              /* Extra prerequesites for using this table */
){
  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 */
  sqlite3 *db;                /* The database connection */
  WhereLoop *pNew;            /* Template WhereLoop object */
  int rc = SQLITE_OK;         /* Return code */

  pNew = pBuilder->pNew;
  db = pBuilder->db;
  pSrc = pBuilder->pTabList->a + iTab;
  pNew->maskSelf = getMask(pBuilder->pWC->pMaskSet, pSrc->iCursor);

  if( pSrc->pIndex ){
    /* An INDEXED BY clause specifies a particular index to use */
    pProbe = pSrc->pIndex;
  }else{
    /* There is no INDEXED BY clause.  Create a fake Index object in local
    ** variable sPk to represent the rowid primary key index.  Make this
................................................................................
      ** NOT INDEXED qualifier is omitted from the FROM clause */
      sPk.pNext = pFirst;
    }
    pProbe = &sPk;
  }

  /* Insert a full table scan */
  pNew->iTab = iTab;
  pNew->u.btree.nEq = 0;
  pNew->nTerm = 0;
  pNew->rSetup = (double)0;
  pNew->prereq = 0;
  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);



  /* Loop over all indices
  */
  for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext){
    WhereTerm **paTerm;
    pNew->prereq = mExtra;
    pNew->iTab = iTab;
    pNew->u.btree.nEq = 0;
    pNew->nTerm = 0;
    if( pProbe->tnum<=0 ){
      /* Integer primary key index */
      pNew->wsFlags = WHERE_IPK;
    }else{
      Bitmask m = pSrc->colUsed;
................................................................................
        int x = pProbe->aiColumn[j];
        if( x<BMS-1 ){
          m &= ~(((Bitmask)1)<<x);
        }
      }
      pNew->wsFlags = m==0 ? WHERE_IDX_ONLY : 0;
    }
    paTerm = sqlite3DbRealloc(db, pNew->aTerm,
                              (pProbe->nColumn+2)*sizeof(pNew->aTerm[0]));
    if( paTerm==0 ){ rc = SQLITE_NOMEM; break; }
    pNew->aTerm = paTerm;
    pNew->u.btree.pIndex = pProbe;

    rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 1);

    /* If there was an INDEXED BY clause, then only that one index is
    ** considered. */
    if( pSrc->pIndex ) break;
................................................................................

/*
** Add all WhereLoop objects for the iTab-th table of the join.  That
** table is guaranteed to be a virtual table.
*/
static int whereLoopAddVirtual(
  WhereLoopBuilder *pBuilder,  /* WHERE clause information */
  int iTab,                    /* The table to process */
  Bitmask mExtra               /* Extra prerequesites for using this table */
){
  Parse *pParse;               /* The parsing context */
  WhereClause *pWC;            /* The WHERE clause */
  struct SrcList_item *pSrc;   /* The FROM clause term to search */
  Table *pTab;
  sqlite3 *db;
................................................................................
  WhereTerm *pTerm;
  int i, j;
  int iTerm, mxTerm;
  int seenIn = 0;              /* True if an IN operator is seen */
  int seenVar = 0;             /* True if a non-constant constraint is seen */
  int iPhase;                  /* 0: const w/o IN, 1: const, 2: no IN,  2: IN */
  WhereLoop *pNew;
  WhereTerm **paTerm;
  int rc = SQLITE_OK;

  pParse = pBuilder->pParse;
  db = pParse->db;
  pWC = pBuilder->pWC;

  pSrc = &pBuilder->pTabList->a[iTab];
  pTab = pSrc->pTab;
  pNew = pBuilder->pNew;
  pIdxInfo = allocateIndexInfo(pParse,pWC,pSrc,pBuilder->pOrderBy);
  if( pIdxInfo==0 ) return SQLITE_NOMEM;
  paTerm = sqlite3DbRealloc(db, pNew->aTerm,
                            (pIdxInfo->nConstraint+1)*sizeof(pNew->aTerm[0]));
  if( paTerm==0 ){
    sqlite3DbFree(db, pIdxInfo);
    return SQLITE_NOMEM;
  }
  pNew->aTerm = paTerm;
  pNew->prereq = 0;
  pNew->iTab = iTab;
  pNew->maskSelf = getMask(pBuilder->pWC->pMaskSet, pSrc->iCursor);
  pNew->rSetup = 0;
  pNew->wsFlags = WHERE_VIRTUALTABLE;
  pNew->nTerm = 0;
  pNew->u.vtab.needFree = 0;
  pUsage = pIdxInfo->aConstraintUsage;

  for(iPhase=0; iPhase<=2; iPhase++){
................................................................................
  int iTab;
  SrcList *pTabList = pBuilder->pTabList;
  struct SrcList_item *pItem;
  WhereClause *pWC = pBuilder->pWC;
  sqlite3 *db = pBuilder->db;
  int nTabList = pBuilder->pWInfo->nLevel;
  int rc = SQLITE_OK;


  /* Loop over the tables in the join, from left to right */
  pBuilder->pNew = sqlite3DbMallocZero(db, sizeof(WhereLoop));
  if( pBuilder->pNew==0 ) return SQLITE_NOMEM;
  for(iTab=0, pItem=pTabList->a; iTab<nTabList; iTab++, pItem++){
    if( IsVirtual(pItem->pTab) ){
      rc = whereLoopAddVirtual(pBuilder, iTab, mExtra);
    }else{

      rc = whereLoopAddBtree(pBuilder, iTab, mExtra);
    }


    mPrior |= getMask(pWC->pMaskSet, pItem->iCursor);
    if( (pItem->jointype & (JT_LEFT|JT_CROSS))!=0 ){
      mExtra = mPrior;
    }











    if( rc || db->mallocFailed ) break;
  }

  whereLoopDelete(db, pBuilder->pNew);
  pBuilder->pNew = 0;
  return rc;
}

/*
** Examine a WherePath to see if it outputs rows in the requested ORDER BY







<







<




<
|
<







 







<



|






>
>



<
<
<







 







<
<
<
<







 







<







 







<





>
|

<
|

<
<
<
<
<
<
<

<
<







 







>


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



>
>
>
>
>
>
>
>
>
>
>


>







5305
5306
5307
5308
5309
5310
5311

5312
5313
5314
5315
5316
5317
5318

5319
5320
5321
5322

5323

5324
5325
5326
5327
5328
5329
5330
....
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
5371
5372
5373
....
5376
5377
5378
5379
5380
5381
5382




5383
5384
5385
5386
5387
5388
5389
....
5393
5394
5395
5396
5397
5398
5399

5400
5401
5402
5403
5404
5405
5406
....
5410
5411
5412
5413
5414
5415
5416

5417
5418
5419
5420
5421
5422
5423
5424

5425
5426







5427


5428
5429
5430
5431
5432
5433
5434
....
5546
5547
5548
5549
5550
5551
5552
5553
5554
5555
5556
5557

5558
5559

5560
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
5588
5589

/*
** Add all WhereLoop objects for the iTab-th table of the join.  That
** table is guaranteed to be a b-tree table, not a virtual table.
*/
static int whereLoopAddBtree(
  WhereLoopBuilder *pBuilder, /* WHERE clause information */

  Bitmask mExtra              /* Extra prerequesites for using this table */
){
  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;
  }else{
    /* There is no INDEXED BY clause.  Create a fake Index object in local
    ** variable sPk to represent the rowid primary key index.  Make this
................................................................................
      ** 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 */
      pNew->wsFlags = WHERE_IPK;
    }else{
      Bitmask m = pSrc->colUsed;
................................................................................
        int x = pProbe->aiColumn[j];
        if( x<BMS-1 ){
          m &= ~(((Bitmask)1)<<x);
        }
      }
      pNew->wsFlags = m==0 ? WHERE_IDX_ONLY : 0;
    }




    pNew->u.btree.pIndex = pProbe;

    rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 1);

    /* If there was an INDEXED BY clause, then only that one index is
    ** considered. */
    if( pSrc->pIndex ) break;
................................................................................

/*
** Add all WhereLoop objects for the iTab-th table of the join.  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 */
){
  Parse *pParse;               /* The parsing context */
  WhereClause *pWC;            /* The WHERE clause */
  struct SrcList_item *pSrc;   /* The FROM clause term to search */
  Table *pTab;
  sqlite3 *db;
................................................................................
  WhereTerm *pTerm;
  int i, j;
  int iTerm, mxTerm;
  int seenIn = 0;              /* True if an IN operator is seen */
  int seenVar = 0;             /* True if a non-constant constraint is seen */
  int iPhase;                  /* 0: const w/o IN, 1: const, 2: no IN,  2: IN */
  WhereLoop *pNew;

  int rc = SQLITE_OK;

  pParse = pBuilder->pParse;
  db = pParse->db;
  pWC = pBuilder->pWC;
  pNew = pBuilder->pNew;
  pSrc = &pBuilder->pTabList->a[pNew->iTab];
  pTab = pSrc->pTab;

  pIdxInfo = allocateIndexInfo(pParse, pWC, pSrc, pBuilder->pOrderBy);
  if( pIdxInfo==0 ) return SQLITE_NOMEM;







  pNew->prereq = 0;


  pNew->rSetup = 0;
  pNew->wsFlags = WHERE_VIRTUALTABLE;
  pNew->nTerm = 0;
  pNew->u.vtab.needFree = 0;
  pUsage = pIdxInfo->aConstraintUsage;

  for(iPhase=0; iPhase<=2; iPhase++){
................................................................................
  int iTab;
  SrcList *pTabList = pBuilder->pTabList;
  struct SrcList_item *pItem;
  WhereClause *pWC = pBuilder->pWC;
  sqlite3 *db = pBuilder->db;
  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);
    if( (pItem->jointype & (JT_LEFT|JT_CROSS))!=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;
}

/*
** Examine a WherePath to see if it outputs rows in the requested ORDER BY