/ Check-in [15cc8a16]
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:Continued progress on generating good WhereLoop objects for the new query planner.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: 15cc8a16482777d8e138c4d0863faf8d54fef33a
User & Date: drh 2013-05-07 23:06:23
Context
2013-05-08
03:05
Add the NGQP solver. check-in: 5d37587c user: drh tags: nextgen-query-plan-exp
2013-05-07
23:06
Continued progress on generating good WhereLoop objects for the new query planner. check-in: 15cc8a16 user: drh tags: nextgen-query-plan-exp
19:44
Inserting a few WhereLoop objects without leaking memory. Costs are not correct. Inequality and IN constraints are not implemented. check-in: e8881a8b user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

311
312
313
314
315
316
317

318
319
320
321
322
323
324
...
706
707
708
709
710
711
712









713
714
715
716
717
718
719
....
5087
5088
5089
5090
5091
5092
5093
5094
5095
5096
5097
5098
5099
5100
5101
....
5113
5114
5115
5116
5117
5118
5119
5120
5121
5122
5123
5124
5125
5126
5127
5128
5129
5130
5131
5132
5133
5134
5135
5136
5137

5138
5139
5140
5141
5142
5143
5144
5145
5146
5147
5148
....
5150
5151
5152
5153
5154
5155
5156

5157
5158
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
5194

5195
5196
5197









5198








5199

5200
5201
5202
5203
5204
5205
5206
5207
5208
5209
....
5218
5219
5220
5221
5222
5223
5224

5225
5226
5227
5228

5229
5230
5231
5232
5233
5234
5235
....
5249
5250
5251
5252
5253
5254
5255













5256
5257
5258
5259
5260
5261
5262
5263














5264
5265
5266
5267
5268
5269
5270
5271
5272
5273
5274
5275
5276
5277
5278
5279
5280
5281
5282
5283
5284
5285
5286
5287
5288
5289
5290
5291
....
5574
5575
5576
5577
5578
5579
5580
5581
5582
5583
5584
5585
5586
5587
5588
5589
5590
5591
5592
5593
5594
5595
5596
5597
** is set to WO_IN|WO_EQ.  The WhereLevel.wsFlags field can then be used as
** the "op" parameter to findTerm when we are resolving equality constraints.
** ISNULL constraints will then not be used on the right table of a left
** join.  Tickets #2177 and #2189.
*/
#define WHERE_ROWID_EQ     0x00001000  /* rowid=EXPR or rowid IN (...) */
#define WHERE_ROWID_RANGE  0x00002000  /* rowid<EXPR and/or rowid>EXPR */

#define WHERE_COLUMN_EQ    0x00010000  /* x=EXPR or x IN (...) or x IS NULL */
#define WHERE_COLUMN_RANGE 0x00020000  /* x<EXPR and/or x>EXPR */
#define WHERE_COLUMN_IN    0x00040000  /* x IN (...) */
#define WHERE_COLUMN_NULL  0x00080000  /* x IS NULL */
#define WHERE_INDEXED      0x000f0000  /* Anything that uses an index */
#define WHERE_NOT_FULLSCAN 0x100f3000  /* Does not do a full table scan */
#define WHERE_IN_ABLE      0x080f1000  /* Able to support an IN operator */
................................................................................
  WhereTerm *pTerm;    /* The term being tested */

  while( pScan->iEquiv<=pScan->nEquiv ){
    iCur = pScan->aEquiv[pScan->iEquiv-2];
    iColumn = pScan->aEquiv[pScan->iEquiv-1];
    while( (pWC = pScan->pWC)!=0 ){
      for(pTerm=pWC->a+pScan->k; pScan->k<pWC->nTerm; pScan->k++, pTerm++){









        if( pTerm->leftCursor==iCur && pTerm->u.leftColumn==iColumn ){
          if( (pTerm->eOperator & WO_EQUIV)!=0
           && pScan->nEquiv<ArraySize(pScan->aEquiv)
          ){
            int j;
            pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight);
            assert( pX->op==TK_COLUMN );
................................................................................
** 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;
  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;
................................................................................
     && p->nOb<=pTemplate->nOb
     && p->iOb==pTemplate->iOb
     && p->rSetup>=pTemplate->rSetup
     && p->rRun>=pTemplate->rRun
    ){
      /* Overwrite an existing WhereLoop with a better one */
      sqlite3DbFree(db, p->aTerm);
      *ppPrev = p->pNextLoop;
      break;
    }
  }

  /* If we reach this point it means that either p[] should be overwritten
  ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
  ** WhereLoop and insert it.
  */
  if( p==0 ){
    p = sqlite3DbMallocRaw(db, sizeof(WhereLoop));
    if( p==0 ) return SQLITE_NOMEM;
  }
  *p = *pTemplate;
  p->pNextLoop = pWInfo->pLoops;
  pWInfo->pLoops = p;
  if( pTemplate->nTerm<=0 ) return SQLITE_OK;
  if( p->pIndex && p->pIndex->tnum==0 ) p->pIndex = 0;

  p->aTerm = sqlite3DbMallocRaw(db, pTemplate->nTerm*sizeof(p->aTerm[0]));
  if( p->aTerm==0 ){
    p->nTerm = 0;
    sqlite3DbFree(db, p);
    return SQLITE_NOMEM;
  }
  memcpy(p->aTerm, pTemplate->aTerm, pTemplate->nTerm*sizeof(p->aTerm[0]));
  return SQLITE_OK;
}

/*
................................................................................
** Try to match one more.
**
** If pProbe->tnum==0, that means pIndex is a fake index used for the
** INTEGER PRIMARY KEY.
*/
static void whereLoopAddBtreeIndex(
  WhereLoopBuilder *pBuilder,     /* The WhereLoop factory */

  struct SrcList_item *pSrc,      /* FROM clause term being analyzed */
  Index *pProbe,                  /* An index on pSrc */
  int nInMul                      /* Number of iterations due to IN */
){
  sqlite3 *db;                    /* Database connection malloc context */
  WhereLoop *pNew;                /* Template WhereLoop under construction */
  WhereTerm *pTerm;               /* A WhereTerm under consideration */
  int eqTermMask;                 /* Valid equality operators */
  WhereScan scan;                 /* Iterator for WHERE terms */
  WhereLoop savedLoop;

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





  if( pProbe->tnum<=0 || (pSrc->jointype & JT_LEFT)!=0 ){
    eqTermMask = WO_EQ|WO_IN;
  }else{
    eqTermMask = WO_EQ|WO_IN|WO_ISNULL;
  }


  if( pNew->nEq<pProbe->nColumn ){
    int iCol;            /* Index of the column in the table */


    iCol = pProbe->aiColumn[pNew->nEq];
    pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol,
                          eqTermMask, iCol>=0 ? pProbe : 0);
    savedLoop = *pNew;
    pNew->nEq++;
    pNew->nTerm++;
    for(; pTerm!=0; pTerm = whereScanNext(&scan)){

      pNew->aTerm[pNew->nEq-1] = pTerm;
      pNew->nOut = (double)(pProbe->aiRowEst[pNew->nEq] * nInMul);
      pNew->rSetup = (double)0;
      pNew->rRun = pNew->nOut;
      pNew->prereq = savedLoop.prereq | pTerm->prereqRight;

      if( pProbe->tnum<=0 ){
        pNew->wsFlags = savedLoop.wsFlags | WHERE_ROWID_EQ;
      }else{









        pNew->wsFlags = savedLoop.wsFlags | WHERE_COLUMN_EQ;








      }

      whereLoopInsert(pBuilder->pWInfo, pNew);
      if( pNew->nEq<pProbe->nColumn ){
        whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul);
      }
    }
    *pNew = savedLoop;
  }
}

/*
................................................................................
  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 */


  pNew = pBuilder->pNew;
  db = pBuilder->db;
  pSrc = pBuilder->pTabList->a + 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
................................................................................
      /* 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;
  }














  /* Loop over all indices
  */
  for(; pProbe; pProbe=pProbe->pNext){
    WhereTerm **paTerm;
    pNew->prereq = mExtra;
    pNew->iTab = iTab;
    pNew->nEq = 0;
    pNew->nTerm = 0;














    paTerm = sqlite3DbRealloc(db, pNew->aTerm,
                              (pProbe->nColumn+1)*sizeof(pNew->aTerm[0]));
    if( paTerm==0 ) break;
    pNew->aTerm = paTerm;
    pNew->pIndex = pProbe;

    whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 1);

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

#if 0  
  /* Insert a full table scan */
  pNew->iTab = iTab;
  pNew->rSetup = (double)0;
  pNew->rRun = (double)1000000;
  pNew->nOut = (double)1000000;
  whereLoopInsert(pBuilder->pWInfo, pNew);
#endif
}

/*
** Add all WhereLoop objects for the iTab-th table of the join.  That
** table is guaranteed to be a virtual table.
*/
static void whereLoopAddVirtual(
................................................................................
  if( sqlite3WhereTrace ){
    WhereLoop *p;
    int nb = 2*((nTabList+15)/16);
    for(p=pWInfo->pLoops; p; p=p->pNextLoop){
      struct SrcList_item *pItem = pTabList->a + p->iTab;
       Table *pTab = pItem->pTab;
      sqlite3DebugPrintf("%02d.%0*llx", p->iTab, nb, p->prereq);
      sqlite3DebugPrintf(" %5s",
                         pItem->zAlias ? pItem->zAlias : pTab->zName);
      if( p->pIndex ){
        sqlite3DebugPrintf(".%-5s %2d", p->pIndex->zName, p->nEq);
      }else{
        sqlite3DebugPrintf("%9s","");
      }
      sqlite3DebugPrintf(" fg %08x OB %d,%d N %2d",
                         p->wsFlags, p->iOb, p->nOb, p->nTerm);
      sqlite3DebugPrintf(" cost %.2g+%.2g,%.2g\n",
                         p->prereq, p->rSetup, p->rRun, p->nOut);
    }
  }
#endif

  /* Chose the best index to use for each table in the FROM clause.
  **







>







 







>
>
>
>
>
>
>
>
>







 







|







 







|









|



|
|
|

>



|







 







>







|

|





>
>
>
>
|
|

|









|

|
<

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

>

|
|







 







>




>







 







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








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






|





<
<
<
<
<
<
<
<
<







 







|


|

|



|







311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
...
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
....
5097
5098
5099
5100
5101
5102
5103
5104
5105
5106
5107
5108
5109
5110
5111
....
5123
5124
5125
5126
5127
5128
5129
5130
5131
5132
5133
5134
5135
5136
5137
5138
5139
5140
5141
5142
5143
5144
5145
5146
5147
5148
5149
5150
5151
5152
5153
5154
5155
5156
5157
5158
5159
....
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
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
....
5252
5253
5254
5255
5256
5257
5258
5259
5260
5261
5262
5263
5264
5265
5266
5267
5268
5269
5270
5271
....
5285
5286
5287
5288
5289
5290
5291
5292
5293
5294
5295
5296
5297
5298
5299
5300
5301
5302
5303
5304
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
5335
5336
5337
5338









5339
5340
5341
5342
5343
5344
5345
....
5628
5629
5630
5631
5632
5633
5634
5635
5636
5637
5638
5639
5640
5641
5642
5643
5644
5645
5646
5647
5648
5649
5650
5651
** is set to WO_IN|WO_EQ.  The WhereLevel.wsFlags field can then be used as
** the "op" parameter to findTerm when we are resolving equality constraints.
** ISNULL constraints will then not be used on the right table of a left
** join.  Tickets #2177 and #2189.
*/
#define WHERE_ROWID_EQ     0x00001000  /* rowid=EXPR or rowid IN (...) */
#define WHERE_ROWID_RANGE  0x00002000  /* rowid<EXPR and/or rowid>EXPR */
#define WHERE_IPK          0x00004000  /* x is the INTEGER PRIMARY KEY */
#define WHERE_COLUMN_EQ    0x00010000  /* x=EXPR or x IN (...) or x IS NULL */
#define WHERE_COLUMN_RANGE 0x00020000  /* x<EXPR and/or x>EXPR */
#define WHERE_COLUMN_IN    0x00040000  /* x IN (...) */
#define WHERE_COLUMN_NULL  0x00080000  /* x IS NULL */
#define WHERE_INDEXED      0x000f0000  /* Anything that uses an index */
#define WHERE_NOT_FULLSCAN 0x100f3000  /* Does not do a full table scan */
#define WHERE_IN_ABLE      0x080f1000  /* Able to support an IN operator */
................................................................................
  WhereTerm *pTerm;    /* The term being tested */

  while( pScan->iEquiv<=pScan->nEquiv ){
    iCur = pScan->aEquiv[pScan->iEquiv-2];
    iColumn = pScan->aEquiv[pScan->iEquiv-1];
    while( (pWC = pScan->pWC)!=0 ){
      for(pTerm=pWC->a+pScan->k; pScan->k<pWC->nTerm; pScan->k++, pTerm++){
        if( pTerm->iParent>=0 ){
          WhereTerm *pParent = &pWC->a[pTerm->iParent];
          int j;
          for(j=pScan->iEquiv-4; j>=0; j-=2 ){
            if( pParent->leftCursor==pScan->aEquiv[j]
             && pParent->u.leftColumn==pScan->aEquiv[j+1] ) break;
          }
          if( j>=0 ) continue;
        }
        if( pTerm->leftCursor==iCur && pTerm->u.leftColumn==iColumn ){
          if( (pTerm->eOperator & WO_EQUIV)!=0
           && pScan->nEquiv<ArraySize(pScan->aEquiv)
          ){
            int j;
            pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight);
            assert( pX->op==TK_COLUMN );
................................................................................
** 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;
  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;
................................................................................
     && p->nOb<=pTemplate->nOb
     && p->iOb==pTemplate->iOb
     && p->rSetup>=pTemplate->rSetup
     && p->rRun>=pTemplate->rRun
    ){
      /* Overwrite an existing WhereLoop with a better one */
      sqlite3DbFree(db, p->aTerm);
      pNext = p->pNextLoop;
      break;
    }
  }

  /* If we reach this point it means that either p[] should be overwritten
  ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
  ** WhereLoop and insert it.
  */
  if( p==0 ){
    p = pToFree = sqlite3DbMallocRaw(db, sizeof(WhereLoop));
    if( p==0 ) return SQLITE_NOMEM;
  }
  *p = *pTemplate;
  p->pNextLoop = pNext;
  *ppPrev = p;
  p->aTerm = 0;
  if( p->pIndex && p->pIndex->tnum==0 ) p->pIndex = 0;
  if( pTemplate->nTerm<=0 ) return SQLITE_OK;
  p->aTerm = sqlite3DbMallocRaw(db, pTemplate->nTerm*sizeof(p->aTerm[0]));
  if( p->aTerm==0 ){
    p->nTerm = 0;
    sqlite3DbFree(db, pToFree);
    return SQLITE_NOMEM;
  }
  memcpy(p->aTerm, pTemplate->aTerm, pTemplate->nTerm*sizeof(p->aTerm[0]));
  return SQLITE_OK;
}

/*
................................................................................
** Try to match one more.
**
** If pProbe->tnum==0, that means pIndex is a fake index used for the
** INTEGER PRIMARY KEY.
*/
static void whereLoopAddBtreeIndex(
  WhereLoopBuilder *pBuilder,     /* The WhereLoop factory */
  Bitmask maskSelf,               /* Bitmask for table being scanned */
  struct SrcList_item *pSrc,      /* FROM clause term being analyzed */
  Index *pProbe,                  /* An index on pSrc */
  int nInMul                      /* Number of iterations due to IN */
){
  sqlite3 *db;                    /* Database connection malloc context */
  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[] */

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

  assert( pNew->nEq<pProbe->nColumn );
  assert( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 );
  if( pNew->wsFlags & WHERE_BTM_LIMIT ){
    opMask = WO_LT|WO_LE;
  }else if( pProbe->tnum<=0 || (pSrc->jointype & JT_LEFT)!=0 ){
    opMask = WO_EQ|WO_IN|WO_GT|WO_GE|WO_LT|WO_LE;
  }else{
    opMask = WO_EQ|WO_IN|WO_ISNULL|WO_GT|WO_GE|WO_LT|WO_LE;
  }


  if( pNew->nEq<pProbe->nColumn ){
    int iCol;            /* Index of the column in the table */


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

    for(; pTerm!=0; pTerm = whereScanNext(&scan)){
      int nIn = 1;
      pNew->nEq = savedLoop.nEq;
      pNew->nTerm = savedLoop.nTerm;
      pNew->aTerm[pNew->nTerm++] = pTerm;

      pNew->prereq = (savedLoop.prereq | pTerm->prereqRight) & ~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 */
          nIn = 25;
        }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
          /* "x IN (value, value, ...)" */
          nIn = pExpr->x.pList->nExpr;
        }
        pNew->nEq++;
        pNew->nOut = (double)pProbe->aiRowEst[pNew->nEq] * nInMul * nIn;
      }else if( pTerm->eOperator & (WO_EQ|WO_ISNULL) ){
        pNew->wsFlags |= WHERE_COLUMN_EQ;
        pNew->nEq++;
        pNew->nOut = (double)pProbe->aiRowEst[pNew->nEq] * nInMul;
      }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;
      whereLoopInsert(pBuilder->pWInfo, pNew);
      if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 && pNew->nEq<pProbe->nColumn ){
        whereLoopAddBtreeIndex(pBuilder, maskSelf, pSrc, pProbe, nInMul*nIn);
      }
    }
    *pNew = savedLoop;
  }
}

/*
................................................................................
  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 */
  Bitmask maskSelf;           /* Mask for iTab */

  pNew = pBuilder->pNew;
  db = pBuilder->db;
  pSrc = pBuilder->pTabList->a + iTab;
  maskSelf = getMask(pBuilder->pWC->pMaskSet, 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
................................................................................
      /* 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->iTab = iTab;
  pNew->nEq = 0;
  pNew->nTerm = 0;
  pNew->rSetup = (double)0;
  pNew->prereq = 0;
  pNew->pIndex = 0;
  pNew->wsFlags = 0;
  pNew->iOb = pNew->nOb = 0;
  pNew->rRun = (double)pSrc->pTab->nRowEst;
  pNew->nOut = (double)pSrc->pTab->nRowEst;
  whereLoopInsert(pBuilder->pWInfo, pNew);

  /* Loop over all indices
  */
  for(; pProbe; pProbe=pProbe->pNext){
    WhereTerm **paTerm;
    pNew->prereq = mExtra;
    pNew->iTab = iTab;
    pNew->nEq = 0;
    pNew->nTerm = 0;
    if( pProbe->tnum<=0 ){
      /* Integer primary key index */
      pNew->wsFlags = WHERE_IPK;
    }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 &= ~(((Bitmask)1)<<x);
        }
      }
      pNew->wsFlags = m==0 ? WHERE_IDX_ONLY : 0;
    }
    paTerm = sqlite3DbRealloc(db, pNew->aTerm,
                              (pProbe->nColumn+1)*sizeof(pNew->aTerm[0]));
    if( paTerm==0 ) break;
    pNew->aTerm = paTerm;
    pNew->pIndex = pProbe;

    whereLoopAddBtreeIndex(pBuilder, maskSelf, 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 void whereLoopAddVirtual(
................................................................................
  if( sqlite3WhereTrace ){
    WhereLoop *p;
    int nb = 2*((nTabList+15)/16);
    for(p=pWInfo->pLoops; p; p=p->pNextLoop){
      struct SrcList_item *pItem = pTabList->a + p->iTab;
       Table *pTab = pItem->pTab;
      sqlite3DebugPrintf("%02d.%0*llx", p->iTab, nb, p->prereq);
      sqlite3DebugPrintf(" %6s",
                         pItem->zAlias ? pItem->zAlias : pTab->zName);
      if( p->pIndex ){
        sqlite3DebugPrintf(".%-8s %2d", p->pIndex->zName, p->nEq);
      }else{
        sqlite3DebugPrintf("%12s","");
      }
      sqlite3DebugPrintf(" fg %08x OB %d,%d N %2d",
                         p->wsFlags, p->iOb, p->nOb, p->nTerm);
      sqlite3DebugPrintf(" cost %.4g,%.4g,%.4g\n",
                         p->prereq, p->rSetup, p->rRun, p->nOut);
    }
  }
#endif

  /* Chose the best index to use for each table in the FROM clause.
  **