/ Check-in [bd9327a9]
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:NGQP working with virtual tables, though many legacy tests fail and there are yet some memory leaks.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: bd9327a9684b99978734ccd561eea1ad864ab13b
User & Date: drh 2013-05-08 14:14:26
Original Comment: NGQP working with virtualt tables, though many legacy tests fail and there are yet some memory leaks.
Context
2013-05-08
20:05
Fix memory leaks in the NGQP logic for virtual tables. check-in: 3c2e83a4 user: drh tags: nextgen-query-plan-exp
14:14
NGQP working with virtual tables, though many legacy tests fail and there are yet some memory leaks. check-in: bd9327a9 user: drh tags: nextgen-query-plan-exp
14:13
Fix the wholenumber virtual table so that it returns higher costs for unconstrained usage. check-in: ceff8955 user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

40
41
42
43
44
45
46


47
48
49
50
51
52
53
54
55
56
57

58
59
60
61
62


63
64
65







66
67
68
69
70
71
72
...
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
...
329
330
331
332
333
334
335

336
337
338
339
340
341
342
....
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225

2226
2227
2228
2229
2230
2231
2232
....
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
....
5056
5057
5058
5059
5060
5061
5062
5063

5064

5065
5066










5067
5068
5069
5070
5071
5072
5073














5074
5075
5076
5077
5078
5079
5080
5081
5082
5083
5084
5085
5086
....
5145
5146
5147
5148
5149
5150
5151
5152
5153
5154
5155

5156
5157
5158
5159
5160
5161
5162
....
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

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
....
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
....
5341
5342
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






















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
....
5497
5498
5499
5500
5501
5502
5503
5504
5505
5506
5507
5508
5509
5510
5511
....
5625
5626
5627
5628
5629
5630
5631

5632
5633
5634
5635
5636
5637
5638
....
5754
5755
5756
5757
5758
5759
5760
5761
5762
5763
5764
5765
5766
5767
5768
5769
typedef struct WhereAndInfo WhereAndInfo;
typedef struct WhereCost WhereCost;
typedef struct WhereLoop WhereLoop;
typedef struct WherePath WherePath;
typedef struct WhereTerm WhereTerm;
typedef struct WhereLoopBuilder WhereLoopBuilder;
typedef struct WhereScan WhereScan;



/*
** Each instance of this object represents a way of evaluating one
** term of a join.  The WhereClause object holds a table of these
** objects using (iTab,prereq,iOb,nOb) as the primary key.  Note that the
** same join term might have multiple associated WhereLoop objects.
*/
struct WhereLoop {
  Bitmask prereq;       /* Bitmask of other loops that must run first */
  Bitmask maskSelf;     /* Bitmask identifying table iTab */
  int iTab;             /* Index of the table coded by this loop */

  u16 iOb, nOb;         /* ORDER BY terms satisfied by this strategy */
  double rSetup;        /* One-time setup cost (ex: create transient index) */
  double rRun;          /* Cost of running each loop */
  double nOut;          /* Estimated number of output rows */
  u32 wsFlags;          /* WHERE_* flags describing the plan */


  u16 nEq;              /* Number of equality constraints */
  u16 nTerm;            /* Number of entries in aTerm[] */
  Index *pIndex;        /* Index used */







  WhereTerm **aTerm;    /* WhereTerms used */
  WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */
};

/*
** Each instance of this object holds a sequence of WhereLoop objects
** that implement some or all of the entire query plan.  
................................................................................
** 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 */
................................................................................
#define WHERE_ORDERED      0x00800000  /* Output will appear in correct order */
#define WHERE_REVERSE      0x01000000  /* Scan in reverse order */
#define WHERE_UNIQUE       0x02000000  /* Selects no more than one row */
#define WHERE_ALL_UNIQUE   0x04000000  /* This and all prior have one row */
#define WHERE_OB_UNIQUE    0x00004000  /* Values in ORDER BY columns are 
                                       ** different for every output row */
#define WHERE_VIRTUALTABLE 0x08000000  /* Use virtual-table processing */

#define WHERE_MULTI_OR     0x10000000  /* OR using multiple indices */
#define WHERE_TEMP_INDEX   0x20000000  /* Uses an ephemeral index */
#define WHERE_DISTINCT     0x40000000  /* Correct order for DISTINCT */
#define WHERE_COVER_SCAN   0x80000000  /* Full scan of a covering index */

/*
** This module contains many separate subroutines that work together to
................................................................................

#ifndef SQLITE_OMIT_VIRTUALTABLE
/*
** Allocate and populate an sqlite3_index_info structure. It is the 
** responsibility of the caller to eventually release the structure
** by passing the pointer returned by this function to sqlite3_free().
*/
static sqlite3_index_info *allocateIndexInfo(WhereBestIdx *p){
  Parse *pParse = p->pParse; 
  WhereClause *pWC = p->pWC;
  struct SrcList_item *pSrc = p->pSrc;
  ExprList *pOrderBy = p->pOrderBy;

  int i, j;
  int nTerm;
  struct sqlite3_index_constraint *pIdxCons;
  struct sqlite3_index_orderby *pIdxOrderBy;
  struct sqlite3_index_constraint_usage *pUsage;
  WhereTerm *pTerm;
  int nOrderBy;
................................................................................
  p->cost.plan.wsFlags = WHERE_VIRTUALTABLE;

  /* If the sqlite3_index_info structure has not been previously
  ** allocated and initialized, then allocate and initialize it now.
  */
  pIdxInfo = *p->ppIdxInfo;
  if( pIdxInfo==0 ){
    *p->ppIdxInfo = pIdxInfo = allocateIndexInfo(p);
  }
  if( pIdxInfo==0 ){
    return;
  }

  /* At this point, the sqlite3_index_info structure that pIdxInfo points
  ** to will have been initialized, either during the current invocation or
................................................................................
  int nb = 2*((pTabList->nSrc+15)/16);
  struct SrcList_item *pItem = pTabList->a + p->iTab;
  Table *pTab = pItem->pTab;
  sqlite3DebugPrintf("%2d.%0*llx.%0*llx",
                     p->iTab, nb, p->maskSelf, nb, p->prereq);
  sqlite3DebugPrintf(" %8s",
                     pItem->zAlias ? pItem->zAlias : pTab->zName);
  if( p->pIndex ){

    sqlite3DebugPrintf(".%-12s %2d", p->pIndex->zName, p->nEq);

  }else{
    sqlite3DebugPrintf("%16s","");










  }
  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















/*
** Delete a WhereLoop object
*/
static void whereLoopDelete(sqlite3 *db, WhereLoop *p){
  sqlite3DbFree(db, p->aTerm);
  sqlite3DbFree(db, p);
}

/*
** Free a WhereInfo structure
*/
static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){
................................................................................
    if( (p->prereq & pTemplate->prereq)==pTemplate->prereq
     && 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);
      p->aTerm = 0;
      p->nTerm = 0;
      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.
................................................................................
      return SQLITE_NOMEM;
    }
  }
  *p = *pTemplate;
  p->pNextLoop = pNext;
  *ppPrev = p;
  p->aTerm = paTerm;
  if( p->pIndex && p->pIndex->tnum==0 ) p->pIndex = 0;
  if( pTemplate->nTerm ){
    memcpy(p->aTerm, pTemplate->aTerm, pTemplate->nTerm*sizeof(p->aTerm[0]));





  }
  return SQLITE_OK;
}

/*
** We have so far matched pBuilder->pNew->nEq terms of the index pIndex.
** 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 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 */


  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;
  }

  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) & ~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 */
        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, pSrc, pProbe, nInMul*nIn);
    }
  }
  *pNew = savedLoop;

}

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


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

  if( pSrc->pIndex ){
................................................................................
      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;
................................................................................
        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, 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(
  WhereLoopBuilder *pBuilder,  /* WHERE clause information */
  int iTab,                    /* The table to process */
  Bitmask mExtra               /* Extra prerequesites for using this table */
){

















}






































































































































/*
** Add all WhereLoop objects for all tables 
*/
static void whereLoopAddAll(WhereLoopBuilder *pBuilder){
  Bitmask mExtra = 0;
  Bitmask mPrior = 0;
  int iTab;
  SrcList *pTabList = pBuilder->pTabList;
  struct SrcList_item *pItem;
  WhereClause *pWC = pBuilder->pWC;
  sqlite3 *db = pBuilder->db;
  int nTabList = pBuilder->pWInfo->nLevel;


  /* Loop over the tables in the join, from left to right */
  pBuilder->pNew = sqlite3DbMallocZero(db, sizeof(WhereLoop));
  if( pBuilder->pNew==0 ) return;
  for(iTab=0, pItem=pTabList->a; iTab<nTabList; iTab++, pItem++){
    if( IsVirtual(pItem->pTab) ){
      whereLoopAddVirtual(pBuilder, iTab, mExtra);
    }else{
      whereLoopAddBtree(pBuilder, iTab, mExtra);
    }
    mPrior |= getMask(pWC->pMaskSet, pItem->iCursor);
    if( (pItem->jointype & (JT_LEFT|JT_CROSS))!=0 ){
      mExtra = mPrior;
    }
    if( db->mallocFailed ) break;
  }
  whereLoopDelete(db, pBuilder->pNew);
  pBuilder->pNew = 0;

}

/*
** Given the list of WhereLoop objects on pWInfo->pLoops, this routine
** attempts to find the lowest cost path that visits each WhereLoop
** once.  This path is then loaded into the pWInfo->a[].pWLoop fields.
**
................................................................................
    pFrom = aTo;
    aTo = aFrom;
    aFrom = pFrom;
    nFrom = nTo;
  }

  /* TEMPORARY */
  if( nFrom==0 ){ sqlite3DbFree(db, pSpace); return SQLITE_ERROR; }
  assert( nFrom>0 );
  
  /* Find the lowest cost path and load it into pWInfo->a[].pWLoop */
  pFrom = aFrom;
  for(ii=1; ii<nFrom; ii++){
    if( pFrom->rCost>aFrom[ii].rCost ) pFrom = &aFrom[ii];
  }
................................................................................
  WhereLoopBuilder sWLB;     /* The WhereLoop builder */
  WhereMaskSet *pMaskSet;    /* The expression mask set */
  WhereLevel *pLevel;        /* A single level in pWInfo->a[] */
  int iFrom;                 /* First unused FROM clause element */
  int andFlags;              /* AND-ed combination of all pWC->a[].wtFlags */
  int ii;                    /* Loop counter */
  sqlite3 *db;               /* Database connection */



  /* Variable initialization */
  memset(&sWBI, 0, sizeof(sWBI));
  sWBI.pParse = pParse;
  memset(&sWLB, 0, sizeof(sWLB));
  sWLB.pParse = pParse;
................................................................................
  if( pDistinct && isDistinctRedundant(pParse, pTabList, sWBI.pWC, pDistinct) ){
    pDistinct = 0;
    pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
  }

  /* Construct the WhereLoop objects */
  WHERETRACE(("*** Optimizer Start ***\n"));
  whereLoopAddAll(&sWLB);
  if( db->mallocFailed ) goto whereBeginError;

  /* Display all of the WhereLoop objects if wheretrace is enabled */
#if defined(SQLITE_DEBUG) \
    && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
  if( sqlite3WhereTrace ){
    WhereLoop *p;
    for(p=pWInfo->pLoops; p; p=p->pNextLoop){







>
>










|
>





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







 







|







 







>







 







|
|
|
|
|
>







 







|







 







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







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





|







 







<
<
<

>







 







<


>
>
>
>
>





|





|












>



|

>
|









|




|

|













|
|


|
|








|
|
>
>




>






|











>







 







|



|




|



|



|







 







|
|

|

|





>






|




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

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



|








>



|


|

|





|



>







 







|







 







>







 







|
|







40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
...
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
...
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
....
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
....
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
....
5069
5070
5071
5072
5073
5074
5075
5076
5077
5078
5079
5080
5081
5082
5083
5084
5085
5086
5087
5088
5089
5090
5091
5092
5093
5094
5095
5096
5097
5098
5099
5100
5101
5102
5103
5104
5105
5106
5107
5108
5109
5110
5111
5112
5113
5114
5115
5116
5117
5118
5119
5120
5121
5122
5123
5124
5125
....
5184
5185
5186
5187
5188
5189
5190



5191
5192
5193
5194
5195
5196
5197
5198
5199
....
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
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
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
....
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
5380
5381
5382
5383
5384
5385
....
5388
5389
5390
5391
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
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
5456
5457
5458
5459
5460
5461
5462
5463
5464
5465
5466
5467
5468
5469
5470
5471
5472
5473
5474
5475
5476
5477
5478
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
5519
5520
5521
5522
5523
5524
5525
5526
5527
5528
5529
5530
5531
5532
5533
5534
5535
5536
5537
5538
5539
5540
5541
5542
5543
5544
5545
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
5590
5591
5592
5593
5594
5595
5596
5597
5598
5599
5600
5601
5602
5603
5604
5605
5606
5607
5608
....
5697
5698
5699
5700
5701
5702
5703
5704
5705
5706
5707
5708
5709
5710
5711
....
5825
5826
5827
5828
5829
5830
5831
5832
5833
5834
5835
5836
5837
5838
5839
....
5955
5956
5957
5958
5959
5960
5961
5962
5963
5964
5965
5966
5967
5968
5969
5970
typedef struct WhereAndInfo WhereAndInfo;
typedef struct WhereCost WhereCost;
typedef struct WhereLoop WhereLoop;
typedef struct WherePath WherePath;
typedef struct WhereTerm WhereTerm;
typedef struct WhereLoopBuilder WhereLoopBuilder;
typedef struct WhereScan WhereScan;
typedef struct WhereVtabPlan WhereVtabPlan;


/*
** Each instance of this object represents a way of evaluating one
** term of a join.  The WhereClause object holds a table of these
** objects using (iTab,prereq,iOb,nOb) as the primary key.  Note that the
** same join term might have multiple associated WhereLoop objects.
*/
struct WhereLoop {
  Bitmask prereq;       /* Bitmask of other loops that must run first */
  Bitmask maskSelf;     /* Bitmask identifying table iTab */
  u16 iTab;             /* Index of the table coded by this loop */
  u16 nTerm;            /* Number of entries in aTerm[] */
  u16 iOb, nOb;         /* ORDER BY terms satisfied by this strategy */
  double rSetup;        /* One-time setup cost (ex: create transient index) */
  double rRun;          /* Cost of running each loop */
  double nOut;          /* Estimated number of output rows */
  u32 wsFlags;          /* WHERE_* flags describing the plan */
  union {
    struct {               /* Information for internal btree tables */
      int nEq;               /* Number of equality constraints */

      Index *pIndex;         /* Index used, or NULL */
    } btree;
    struct {               /* Information for virtualt tables */
      int idxNum;            /* Index number */
      int needFree;          /* True if sqlite3_free(idxStr) is needed */
      char *idxStr;          /* Index identifier string */
    } vtab;
  } u;
  WhereTerm **aTerm;    /* WhereTerms used */
  WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */
};

/*
** Each instance of this object holds a sequence of WhereLoop objects
** that implement some or all of the entire query plan.  
................................................................................
** 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          0x00008000  /* 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 */
................................................................................
#define WHERE_ORDERED      0x00800000  /* Output will appear in correct order */
#define WHERE_REVERSE      0x01000000  /* Scan in reverse order */
#define WHERE_UNIQUE       0x02000000  /* Selects no more than one row */
#define WHERE_ALL_UNIQUE   0x04000000  /* This and all prior have one row */
#define WHERE_OB_UNIQUE    0x00004000  /* Values in ORDER BY columns are 
                                       ** different for every output row */
#define WHERE_VIRTUALTABLE 0x08000000  /* Use virtual-table processing */
#define WHERE_FREEIDXSTR   0x04000000  /* neeed to free WhereLoop.u.idxStr */
#define WHERE_MULTI_OR     0x10000000  /* OR using multiple indices */
#define WHERE_TEMP_INDEX   0x20000000  /* Uses an ephemeral index */
#define WHERE_DISTINCT     0x40000000  /* Correct order for DISTINCT */
#define WHERE_COVER_SCAN   0x80000000  /* Full scan of a covering index */

/*
** This module contains many separate subroutines that work together to
................................................................................

#ifndef SQLITE_OMIT_VIRTUALTABLE
/*
** Allocate and populate an sqlite3_index_info structure. It is the 
** responsibility of the caller to eventually release the structure
** by passing the pointer returned by this function to sqlite3_free().
*/
static sqlite3_index_info *allocateIndexInfo(
  Parse *pParse,
  WhereClause *pWC,
  struct SrcList_item *pSrc,
  ExprList *pOrderBy
){
  int i, j;
  int nTerm;
  struct sqlite3_index_constraint *pIdxCons;
  struct sqlite3_index_orderby *pIdxOrderBy;
  struct sqlite3_index_constraint_usage *pUsage;
  WhereTerm *pTerm;
  int nOrderBy;
................................................................................
  p->cost.plan.wsFlags = WHERE_VIRTUALTABLE;

  /* If the sqlite3_index_info structure has not been previously
  ** allocated and initialized, then allocate and initialize it now.
  */
  pIdxInfo = *p->ppIdxInfo;
  if( pIdxInfo==0 ){
    *p->ppIdxInfo = pIdxInfo = allocateIndexInfo(pParse,pWC,pSrc,p->pOrderBy);
  }
  if( pIdxInfo==0 ){
    return;
  }

  /* At this point, the sqlite3_index_info structure that pIdxInfo points
  ** to will have been initialized, either during the current invocation or
................................................................................
  int nb = 2*((pTabList->nSrc+15)/16);
  struct SrcList_item *pItem = pTabList->a + p->iTab;
  Table *pTab = pItem->pTab;
  sqlite3DebugPrintf("%2d.%0*llx.%0*llx",
                     p->iTab, nb, p->maskSelf, nb, p->prereq);
  sqlite3DebugPrintf(" %8s",
                     pItem->zAlias ? pItem->zAlias : pTab->zName);
  if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
    if( p->u.btree.pIndex ){
      sqlite3DebugPrintf(".%-12s %2d",
                         p->u.btree.pIndex->zName, p->u.btree.nEq);
    }else{
      sqlite3DebugPrintf("%16s","");
    }
  }else{
    char *z;
    if( p->u.vtab.idxStr ){
      z = sqlite3_mprintf("(%d,\"%s\")", p->u.vtab.idxNum,p->u.vtab.idxStr);
    }else{
      z = sqlite3_mprintf("(%d)", p->u.vtab.idxNum);
    }
    sqlite3DebugPrintf(" %-15s", z);
    sqlite3_free(z);
  }
  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

/*
** Deallocate internal memory used by a WhereLoop object
*/
static void whereLoopClear(sqlite3 *db, WhereLoop *p){
  sqlite3DbFree(db, p->aTerm);
  p->aTerm = 0;
  p->nTerm = 0;
  if( (p->wsFlags & WHERE_VIRTUALTABLE)!=0 ){
    if( p->u.vtab.needFree ) sqlite3_free(p->u.vtab.idxStr);
    p->u.vtab.needFree = 0;
    p->u.vtab.idxStr = 0;
  }
}

/*
** Delete a WhereLoop object
*/
static void whereLoopDelete(sqlite3 *db, WhereLoop *p){
  whereLoopClear(db, p);
  sqlite3DbFree(db, p);
}

/*
** Free a WhereInfo structure
*/
static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){
................................................................................
    if( (p->prereq & pTemplate->prereq)==pTemplate->prereq
     && p->nOb<=pTemplate->nOb
     && p->iOb==pTemplate->iOb
     && p->rSetup>=pTemplate->rSetup
     && p->rRun>=pTemplate->rRun
    ){
      /* Overwrite an existing WhereLoop with a better one */



      pNext = p->pNextLoop;
      whereLoopClear(db, p);
      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.
................................................................................
      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;
}

/*
** We have so far matched pBuilder->pNew->u.btree.nEq terms of the index pIndex.
** Try to match one more.
**
** If pProbe->tnum==0, that means pIndex is a fake index used for the
** INTEGER PRIMARY KEY.
*/
static int 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 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 );
  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;
  }

  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 */
        nIn = 25;
      }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
        /* "x IN (value, value, ...)" */
        nIn = pExpr->x.pList->nExpr;
      }
      pNew->u.btree.nEq++;
      pNew->nOut = (double)pProbe->aiRowEst[pNew->u.btree.nEq] * nInMul * nIn;
    }else if( pTerm->eOperator & (WO_EQ|WO_ISNULL) ){
      pNew->wsFlags |= WHERE_COLUMN_EQ;
      pNew->u.btree.nEq++;
      pNew->nOut = (double)pProbe->aiRowEst[pNew->u.btree.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;
    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;
  return rc;
}

/*
** 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 ){
................................................................................
      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->iOb = pNew->nOb = 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 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;
  }
  return rc;
}

/*
** 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;
  sqlite3_index_info *pIdxInfo;
  struct sqlite3_index_constraint *pIdxCons;
  struct sqlite3_index_constraint_usage *pUsage;
  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*sizeof(pNew->aTerm[0]));
  if( paTerm==0 ) return SQLITE_NOMEM;
  pNew->aTerm = paTerm;
  pNew->prereq = 0;
  pNew->iTab = iTab;
  pNew->maskSelf = getMask(pBuilder->pWC->pMaskSet, pSrc->iCursor);
  pNew->iOb = 0;
  pNew->nOb = 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++){
    if( !seenIn && (iPhase&1)!=0 ){
      iPhase++;
      if( iPhase>3 ) break;
    }
    if( !seenVar && iPhase>1 ) break;
    pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
    for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
      j = pIdxCons->iTermOffset;
      pTerm = &pWC->a[j];
      switch( iPhase ){
        case 0:    /* Constants without IN operator */
          pIdxCons->usable = 0;
          if( (pTerm->eOperator & WO_IN)!=0 ){
            seenIn = 1;
          }else if( pTerm->prereqRight!=0 ){
            seenVar = 1;
          }else{
            pIdxCons->usable = 1;
          }
          break;
        case 1:    /* Constants with IN operators */
          assert( seenIn );
          pIdxCons->usable = (pTerm->prereqRight==0);
          break;
        case 2:    /* Variables without IN */
          assert( seenVar );
          pIdxCons->usable = (pTerm->eOperator & WO_IN)==0;
          break;
        default:   /* Variables with IN */
          assert( seenVar && seenIn );
          pIdxCons->usable = 1;
          break;
      }
    }
    memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
    if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr);
    pIdxInfo->idxStr = 0;
    pIdxInfo->idxNum = 0;
    pIdxInfo->needToFreeIdxStr = 0;
    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 = 0;
    for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
      if( (iTerm = pUsage[i].argvIndex - 1)>=0 ){
        j = pIdxCons->iTermOffset;
        if( iTerm>=pIdxInfo->nConstraint
         || j<0
         || j>=pWC->nTerm
         || pNew->aTerm[iTerm]!=0
        ){
          rc = SQLITE_ERROR;
          sqlite3ErrorMsg(pParse, "%s.xBestIndex() malfunction", pTab->zName);
          goto whereLoopAddVtab_exit;
        }
        pTerm = &pWC->a[j];
        pNew->prereq |= pTerm->prereqRight;
        pNew->aTerm[iTerm] = pTerm;
        if( iTerm>mxTerm ) mxTerm = iTerm;
        if( (pTerm->eOperator & WO_IN)!=0 ){
          if( pUsage[i].omit==0 ){
            /* Do not attempt to use an IN constraint if the virtual table
            ** says that the equivalent EQ constraint cannot be safely omitted.
            ** If we do attempt to use such a constraint, some rows might be
            ** repeated in the output. */
            break;
          }
          /* A virtual table that is constrained by an IN clause may not
          ** consume the ORDER BY clause because (1) the order of IN terms
          ** is not necessarily related to the order of output terms and
          ** (2) Multiple outputs from a single IN value will not merge
          ** together.  */
          pIdxInfo->orderByConsumed = 0;
        }
      }
    }
    if( i>=pIdxInfo->nConstraint ){
      pNew->nTerm = mxTerm+1;
      pNew->u.vtab.idxNum = pIdxInfo->idxNum;
      pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr;
      pIdxInfo->needToFreeIdxStr = 0;
      pNew->u.vtab.idxStr = pIdxInfo->idxStr;
      pNew->iOb = 0;
      if( pIdxInfo->orderByConsumed ){
        pNew->nOb = (u16)(pIdxInfo->nOrderBy&0xffff);
      }else{
        pNew->nOb = 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;
  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;
}

/*
** Given the list of WhereLoop objects on pWInfo->pLoops, this routine
** attempts to find the lowest cost path that visits each WhereLoop
** once.  This path is then loaded into the pWInfo->a[].pWLoop fields.
**
................................................................................
    pFrom = aTo;
    aTo = aFrom;
    aFrom = pFrom;
    nFrom = nTo;
  }

  /* TEMPORARY */
//  if( nFrom==0 ){ sqlite3DbFree(db, pSpace); return SQLITE_ERROR; }
  assert( nFrom>0 );
  
  /* Find the lowest cost path and load it into pWInfo->a[].pWLoop */
  pFrom = aFrom;
  for(ii=1; ii<nFrom; ii++){
    if( pFrom->rCost>aFrom[ii].rCost ) pFrom = &aFrom[ii];
  }
................................................................................
  WhereLoopBuilder sWLB;     /* The WhereLoop builder */
  WhereMaskSet *pMaskSet;    /* The expression mask set */
  WhereLevel *pLevel;        /* A single level in pWInfo->a[] */
  int iFrom;                 /* First unused FROM clause element */
  int andFlags;              /* AND-ed combination of all pWC->a[].wtFlags */
  int ii;                    /* Loop counter */
  sqlite3 *db;               /* Database connection */
  int rc;                    /* Return code */


  /* Variable initialization */
  memset(&sWBI, 0, sizeof(sWBI));
  sWBI.pParse = pParse;
  memset(&sWLB, 0, sizeof(sWLB));
  sWLB.pParse = pParse;
................................................................................
  if( pDistinct && isDistinctRedundant(pParse, pTabList, sWBI.pWC, pDistinct) ){
    pDistinct = 0;
    pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
  }

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

  /* Display all of the WhereLoop objects if wheretrace is enabled */
#if defined(SQLITE_DEBUG) \
    && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
  if( sqlite3WhereTrace ){
    WhereLoop *p;
    for(p=pWInfo->pLoops; p; p=p->pNextLoop){