/ Check-in [82d50e19]
Login

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

Overview
Comment:Free up bits of wsFlags for reuse. Install the ORDER BY optimization infrastructure for the NGQP.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1:82d50e198025a2fdb8ee733edb8419d388ee5362
User & Date: drh 2013-05-10 02:00:35
Context
2013-05-10
02:11
Merge in the latest trunk changes. check-in: 5ed31c82 user: drh tags: nextgen-query-plan-exp
02:00
Free up bits of wsFlags for reuse. Install the ORDER BY optimization infrastructure for the NGQP. check-in: 82d50e19 user: drh tags: nextgen-query-plan-exp
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
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/sqliteInt.h.

2041
2042
2043
2044
2045
2046
2047

2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058


2059
2060
2061
2062
2063
2064
2065
#define WHERE_ORDERBY_MAX      0x0002 /* ORDER BY processing for max() func */
#define WHERE_ONEPASS_DESIRED  0x0004 /* Want to do one-pass UPDATE/DELETE */
#define WHERE_DUPLICATES_OK    0x0008 /* Ok to return a row more than once */
#define WHERE_OMIT_OPEN_CLOSE  0x0010 /* Table cursors are already open */
#define WHERE_FORCE_TABLE      0x0020 /* Do not use an index-only search */
#define WHERE_ONETABLE_ONLY    0x0040 /* Only code the 1st table in pTabList */
#define WHERE_AND_ONLY         0x0080 /* Don't use indices for OR terms */


/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed
** into the second half to give some continuity.
*/
struct WhereInfo {
  Parse *pParse;            /* Parsing and code generating context */
  SrcList *pTabList;        /* List of tables in the join */


  u16 nOBSat;               /* Number of ORDER BY terms satisfied by indices */
  u16 wctrlFlags;           /* Flags originally passed to sqlite3WhereBegin() */
  u8 okOnePass;             /* Ok to use one-pass algorithm for UPDATE/DELETE */
  u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
  u8 eDistinct;             /* One of the WHERE_DISTINCT_* values below */
  int iTop;                 /* The very beginning of the WHERE loop */
  int iContinue;            /* Jump here to continue with next record */







>











>
>







2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
#define WHERE_ORDERBY_MAX      0x0002 /* ORDER BY processing for max() func */
#define WHERE_ONEPASS_DESIRED  0x0004 /* Want to do one-pass UPDATE/DELETE */
#define WHERE_DUPLICATES_OK    0x0008 /* Ok to return a row more than once */
#define WHERE_OMIT_OPEN_CLOSE  0x0010 /* Table cursors are already open */
#define WHERE_FORCE_TABLE      0x0020 /* Do not use an index-only search */
#define WHERE_ONETABLE_ONLY    0x0040 /* Only code the 1st table in pTabList */
#define WHERE_AND_ONLY         0x0080 /* Don't use indices for OR terms */
#define WHREE_GROUPBY          0x0100 /* pOrderBy is really a GROUP BY */

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed
** into the second half to give some continuity.
*/
struct WhereInfo {
  Parse *pParse;            /* Parsing and code generating context */
  SrcList *pTabList;        /* List of tables in the join */
  ExprList *pOrderBy;       /* The ORDER BY clause or NULL */
  ExprList *pDistinct;      /* DISTINCT ON values, or NULL */
  u16 nOBSat;               /* Number of ORDER BY terms satisfied by indices */
  u16 wctrlFlags;           /* Flags originally passed to sqlite3WhereBegin() */
  u8 okOnePass;             /* Ok to use one-pass algorithm for UPDATE/DELETE */
  u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
  u8 eDistinct;             /* One of the WHERE_DISTINCT_* values below */
  int iTop;                 /* The very beginning of the WHERE loop */
  int iContinue;            /* Jump here to continue with next record */

Changes to src/where.c.

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
..
82
83
84
85
86
87
88


89
90
91
92
93
94
95
...
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327

328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351

352
353
354
355
356
357
358
....
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
....
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
....
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
....
3811
3812
3813
3814
3815
3816
3817
3818
3819
3820
3821
3822
3823
3824
3825
....
4062
4063
4064
4065
4066
4067
4068

4069
4070
4071
4072
4073
4074
4075
....
4081
4082
4083
4084
4085
4086
4087


4088
4089
4090
4091
4092
4093
4094
4095
4096
4097
4098
....
5086
5087
5088
5089
5090
5091
5092
5093
5094
5095
5096
5097
5098
5099
5100
5101
....
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
....
5360
5361
5362
5363
5364
5365
5366
5367
5368
5369
5370
5371
5372
5373
5374
....
5447
5448
5449
5450
5451
5452
5453
5454
5455
5456
5457
5458
5459
5460
5461
5462
....
5543
5544
5545
5546
5547
5548
5549
5550
5551
5552
5553
5554
5555
5556
5557
5558
5559
5560
5561
5562
....
5599
5600
5601
5602
5603
5604
5605























5606
5607
5608
5609
5610
5611
5612
....
5616
5617
5618
5619
5620
5621
5622

5623
5624
5625
5626
5627
5628

5629
5630
5631
5632
5633
5634
5635
....
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
....
5691
5692
5693
5694
5695
5696
5697
5698
5699
5700
5701
5702
5703
5704
5705
5706
5707
5708
5709
5710
5711
5712
5713
5714
5715

5716
5717
5718



5719
5720
5721
5722
5723
5724
5725
....
5878
5879
5880
5881
5882
5883
5884


5885
5886
5887
5888
5889
5890
5891
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.  
*/
struct WherePath {
  Bitmask maskLoop;     /* Bitmask of all WhereLoop objects in this path */
  double nRow;          /* Estimated number of rows generated by this path */
  double rCost;         /* Total cost of this path */


  WhereLoop **aLoop;    /* Array of WhereLoop objects implementing this path */
};

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by AND operators,
................................................................................
#define WO_ALL    0xfff       /* Mask of all possible WO_* values */
#define WO_SINGLE 0x0ff       /* Mask of all non-compound WO_* values */

/*
** Value for wsFlags returned by bestIndex() and stored in
** WhereLevel.wsFlags.  These flags determine which search
** strategies are appropriate.
**
** The least significant 12 bits is reserved as a mask for WO_ values above.
** The WhereLevel.wsFlags field is usually set to WO_IN|WO_EQ|WO_ISNULL.
** But if the table is the right table of a left join, WhereLevel.wsFlags
** 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_TOP_LIMIT    0x00100000  /* x<EXPR or x<=EXPR constraint */
#define WHERE_BTM_LIMIT    0x00200000  /* x>EXPR or x>=EXPR constraint */
#define WHERE_BOTH_LIMIT   0x00300000  /* Both x>EXPR and x<EXPR */
#define WHERE_IDX_ONLY     0x00400000  /* Use index only - omit table */
#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
** find the best indices to use for accessing a particular table in a query.
** An instance of the following structure holds context information about the
** index search so that it can be more easily passed between the various
** routines.
................................................................................
    if( (pTerm->eOperator & WO_OR)!=0
     && ((pTerm->prereqAll & ~maskSrc) & p->notReady)==0
     && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 
    ){
      WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
      WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
      WhereTerm *pOrTerm;
      int flags = WHERE_MULTI_OR;
      double rTotal = 0;
      double nRow = 0;
      Bitmask used = 0;
      WhereBestIdx sBOI;

      sBOI = *p;
      sBOI.pOrderBy = 0;
................................................................................
      ** of pCost. */
      /*WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));*/
      if( rTotal<p->cost.rCost ){
        p->cost.rCost = rTotal;
        p->cost.used = used;
        p->cost.plan.nRow = nRow;
        p->cost.plan.nOBSat = p->i ? p->aLevel[p->i-1].plan.nOBSat : 0;
        p->cost.plan.wsFlags = flags;
        p->cost.plan.u.pTerm = pTerm;
      }
    }
  }
#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
}

................................................................................
  testcase( pTable->nCol==BMS-2 );
  for(i=0; i<mxBitCol; i++){
    if( extraCols & (((Bitmask)1)<<i) ) nColumn++;
  }
  if( pSrc->colUsed & (((Bitmask)1)<<(BMS-1)) ){
    nColumn += pTable->nCol - BMS + 1;
  }
  pLevel->plan.wsFlags |= WHERE_COLUMN_EQ | WHERE_IDX_ONLY | WO_EQ;

  /* Construct the Index object to describe this index */
  nByte = sizeof(Index);
  nByte += nColumn*sizeof(int);     /* Index.aiColumn */
  nByte += nColumn*sizeof(char*);   /* Index.azColl */
  nByte += nColumn;                 /* Index.aSortOrder */
  pIdx = sqlite3DbMallocZero(pParse->db, nByte);
................................................................................

  /*WHERETRACE(("   best index is %s cost=%.1f\n",
         p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk",
         p->cost.rCost));*/
  
  bestOrClauseIndex(p);
  bestAutomaticIndex(p);
  p->cost.plan.wsFlags |= eqTermMask;
}

/*
** Find the query plan for accessing table pSrc->pTab. Write the
** best query plan and its cost into the WhereCost object supplied 
** as the last parameter. This function may calculate the cost of
** both real and virtual table scans.
................................................................................
  Index *pIdx;                  /* The index being used for this loop */
  int iCur = pLevel->iTabCur;   /* The cursor of the table */
  WhereTerm *pTerm;             /* A single constraint term */
  int j;                        /* Loop counter */
  int regBase;                  /* Base register */
  int nReg;                     /* Number of registers to allocate */
  char *zAff;                   /* Affinity string to return */


  /* This module is only called on query plans that use an index. */
  assert( pLevel->plan.wsFlags & WHERE_INDEXED );
  pIdx = pLevel->plan.u.pIdx;

  /* Figure out how many memory cells we will need then allocate them.
  */
................................................................................
  if( !zAff ){
    pParse->db->mallocFailed = 1;
  }

  /* Evaluate the equality constraints
  */
  assert( pIdx->nColumn>=nEq );


  for(j=0; j<nEq; j++){
    int r1;
    int k = pIdx->aiColumn[j];
    pTerm = findTerm(pWC, iCur, k, notReady, pLevel->plan.wsFlags, pIdx);
    if( pTerm==0 ) break;
    /* The following true for indices with redundant columns. 
    ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
    testcase( (pTerm->wtFlags & TERM_CODED)!=0 );
    testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
    r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, regBase+j);
    if( r1!=regBase+j ){
................................................................................
      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
................................................................................

  /* 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
     && p->nOb>=pTemplate->nOb
     && p->iOb==pTemplate->iOb
     && p->rSetup<=pTemplate->rSetup
     && p->rRun<=pTemplate->rRun
    ){
      /* Already holding an equal or better WhereLoop.
      ** Return without changing or adding anything */
      return SQLITE_OK;
    }
    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;
................................................................................
  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){
................................................................................
    sqlite3DbFree(db, pIdxInfo);
    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( 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;
................................................................................
    }
    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.
**
** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
................................................................................
  const int mxChoice = 10;  /* Maximum number of simultaneous paths tracked */
  int nLoop;                /* Number of terms in the join */
  sqlite3 *db;              /* The database connection */
  int iLoop;                /* Loop counter over the terms of the join */
  int ii, jj;               /* Loop counters */
  double rCost;             /* Cost of a path */
  double mxCost;            /* Maximum cost of a set of paths */

  int nTo, nFrom;           /* Number of valid entries in aTo[] and aFrom[] */
  WherePath *aFrom;         /* All nFrom paths at the previous level */
  WherePath *aTo;           /* The nTo best paths at the current level */
  WherePath *pFrom;         /* An element of aFrom[] that we are working on */
  WherePath *pTo;           /* An element of aTo[] that we are working on */
  WhereLoop *pWLoop;        /* One of the WhereLoop objects */

  WhereLoop **pX;           /* Used to divy up the pSpace memory */
  char *pSpace;             /* Temporary memory used by this routine */

  db = pWInfo->pParse->db;
  nLoop = pWInfo->nLevel;
  assert( nLoop<=pWInfo->pTabList->nSrc );

................................................................................
  aFrom = aTo+mxChoice;
  memset(aFrom, 0, sizeof(aFrom[0]));
  pX = (WhereLoop**)(aFrom+mxChoice);
  for(ii=0, pFrom=aTo; ii<mxChoice*2; ii++, pFrom++, pX += nLoop){
    pFrom->aLoop = pX;
  }


  aFrom[0].nRow = (double)1;
  nFrom = 1;
























  for(iLoop=0; iLoop<nLoop; iLoop++){
    nTo = 0;
    for(ii=0, pFrom=aFrom; ii<nFrom; ii++, pFrom++){
      for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pWLoop->pNextLoop){
        Bitmask maskNew;


        if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
        if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;


        rCost = pWLoop->rSetup + pWLoop->rRun*pFrom->nRow + pFrom->rCost;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
















        for(jj=0, pTo=aTo; jj<nTo && pTo->maskLoop!=maskNew; jj++){}




        if( jj>=nTo ){
          if( nTo>=mxChoice && rCost>=mxCost ) continue;
          if( nTo<mxChoice ){
            jj = nTo++;
          }else{
            for(jj=nTo-1; aTo[jj].rCost<mxCost; jj--){ assert(jj>0); }
          }
          pTo = &aTo[jj];
        }else{
          if( pTo->rCost<=rCost ) continue;
        }

        pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf;
        pTo->nRow = pFrom->nRow * pWLoop->nOut;
        pTo->rCost = rCost;


        memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop);
        pTo->aLoop[iLoop] = pWLoop;
        if( nTo>=mxChoice ){
          mxCost = aTo[0].rCost;
          for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){
            if( pTo->rCost>mxCost ) mxCost = pTo->rCost;
          }
................................................................................
        for(jj=0; jj<=iLoop; jj++){
          whereLoopPrint(aTo[ii].aLoop[jj], pWInfo->pTabList);
        }
      }
    }
#endif

    /* Swap the roles of aFrom and aTo in preparation for the next
    ** cycle. */
    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];
  }
  assert( pWInfo->nLevel==nLoop );

  for(iLoop=0; iLoop<nLoop; iLoop++){
    pWInfo->a[iLoop].pWLoop = pFrom->aLoop[iLoop];
  }




  /* Free temporary memory and return success */
  sqlite3DbFree(db, pSpace);
  return SQLITE_OK;
}

/*
................................................................................
    sqlite3DbFree(db, pWInfo);
    pWInfo = 0;
    goto whereBeginError;
  }
  pWInfo->nLevel = nTabList;
  pWInfo->pParse = pParse;
  pWInfo->pTabList = pTabList;


  pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
  pWInfo->pWC = sWBI.pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
  pWInfo->wctrlFlags = wctrlFlags;
  pWInfo->savedNQueryLoop = pParse->nQueryLoop;
  pMaskSet = (WhereMaskSet*)&sWBI.pWC[1];
  sWBI.aLevel = pWInfo->a;
  sWLB.pWInfo = pWInfo;







|







|



<





|

|
>







 







>
>







 







<
<
<
<
<
<
<
<

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

|
<
|
|
|
|
>







 







<







 







|







 







|







 







|







 







>







 







>
>



|







 







|
<







 







<
<








<
<







 







<







 







<
<







 







<
<
|
<
<
<







 







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







 







>






>







 







>


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





>
>


>
>


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











>



>
>







 







|
<










|





>



>
>
>







 







>
>







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
..
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
...
312
313
314
315
316
317
318








319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341

342
343
344
345
346
347
348
349
350
351
352
353
....
1904
1905
1906
1907
1908
1909
1910

1911
1912
1913
1914
1915
1916
1917
....
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
....
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
....
3805
3806
3807
3808
3809
3810
3811
3812
3813
3814
3815
3816
3817
3818
3819
....
4056
4057
4058
4059
4060
4061
4062
4063
4064
4065
4066
4067
4068
4069
4070
....
4076
4077
4078
4079
4080
4081
4082
4083
4084
4085
4086
4087
4088
4089
4090
4091
4092
4093
4094
4095
....
5083
5084
5085
5086
5087
5088
5089
5090

5091
5092
5093
5094
5095
5096
5097
....
5164
5165
5166
5167
5168
5169
5170


5171
5172
5173
5174
5175
5176
5177
5178


5179
5180
5181
5182
5183
5184
5185
....
5352
5353
5354
5355
5356
5357
5358

5359
5360
5361
5362
5363
5364
5365
....
5438
5439
5440
5441
5442
5443
5444


5445
5446
5447
5448
5449
5450
5451
....
5532
5533
5534
5535
5536
5537
5538


5539



5540
5541
5542
5543
5544
5545
5546
....
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
....
5623
5624
5625
5626
5627
5628
5629
5630
5631
5632
5633
5634
5635
5636
5637
5638
5639
5640
5641
5642
5643
5644
....
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
5687
5688
5689
5690
5691
5692
5693
5694
5695
5696
5697
5698
5699
5700
5701
5702
5703
5704
5705
5706
5707
5708
5709
5710
5711
5712
5713
5714
5715
5716
5717
5718
5719
5720
5721
5722
5723
5724
5725
5726
5727
5728
5729
5730
5731
5732
5733
5734
5735
5736
5737
5738
5739
5740
5741
....
5752
5753
5754
5755
5756
5757
5758
5759

5760
5761
5762
5763
5764
5765
5766
5767
5768
5769
5770
5771
5772
5773
5774
5775
5776
5777
5778
5779
5780
5781
5782
5783
5784
5785
5786
5787
5788
5789
....
5942
5943
5944
5945
5946
5947
5948
5949
5950
5951
5952
5953
5954
5955
5956
5957
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 (maskSelf,prereq,) 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[] */
  u32 wsFlags;          /* WHERE_* flags describing the plan */
  double rSetup;        /* One-time setup cost (ex: create transient index) */
  double rRun;          /* Cost of running each loop */
  double nOut;          /* Estimated number of output rows */

  union {
    struct {               /* Information for internal btree tables */
      int nEq;               /* Number of equality constraints */
      Index *pIndex;         /* Index used, or NULL */
    } btree;
    struct {               /* Information for virtual tables */
      int idxNum;            /* Index number */
      u8 needFree;           /* True if sqlite3_free(idxStr) is needed */
      u8 isOrdered;          /* True if satisfies ORDER BY */
      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.  
*/
struct WherePath {
  Bitmask maskLoop;     /* Bitmask of all WhereLoop objects in this path */
  double nRow;          /* Estimated number of rows generated by this path */
  double rCost;         /* Total cost of this path */
  u8 isOrdered;         /* True if this path satisfies ORDER BY */
  u8 isOrderedValid;    /* True if the isOrdered field is valid */
  WhereLoop **aLoop;    /* Array of WhereLoop objects implementing this path */
};

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by AND operators,
................................................................................
#define WO_ALL    0xfff       /* Mask of all possible WO_* values */
#define WO_SINGLE 0x0ff       /* Mask of all non-compound WO_* values */

/*
** Value for wsFlags returned by bestIndex() and stored in
** WhereLevel.wsFlags.  These flags determine which search
** strategies are appropriate.








*/
#define WHERE_ROWID_EQ     0x00000001  /* rowid=EXPR or rowid IN (...) */
#define WHERE_ROWID_RANGE  0x00000002  /* rowid<EXPR and/or rowid>EXPR */
#define WHERE_NULL_OK      0x00000004  /* Ok to use WO_ISNULL */
#define WHERE_IPK          0x00000008  /* x is the INTEGER PRIMARY KEY */
#define WHERE_COLUMN_EQ    0x00000010  /* x=EXPR or x IN (...) or x IS NULL */
#define WHERE_COLUMN_RANGE 0x00000020  /* x<EXPR and/or x>EXPR */
#define WHERE_COLUMN_IN    0x00000040  /* x IN (...) */
#define WHERE_COLUMN_NULL  0x00000080  /* x IS NULL */
#define WHERE_INDEXED      0x000000f0  /* Anything that uses an index */
#define WHERE_NOT_FULLSCAN 0x000200f3  /* Does not do a full table scan */
#define WHERE_IN_ABLE      0x000100f1  /* Able to support an IN operator */
#define WHERE_TOP_LIMIT    0x00000100  /* x<EXPR or x<=EXPR constraint */
#define WHERE_BTM_LIMIT    0x00000200  /* x>EXPR or x>=EXPR constraint */
#define WHERE_BOTH_LIMIT   0x00000300  /* Both x>EXPR and x<EXPR */
#define WHERE_IDX_ONLY     0x00000400  /* Use index only - omit table */
#define WHERE_ORDERED      0x00000800  /* Output will appear in correct order */
#define WHERE_REVERSE      0x00001000  /* Scan in reverse order */
#define WHERE_UNIQUE       0x00002000  /* Selects no more than one row */
#define WHERE_ALL_UNIQUE   0x00004000  /* This and all prior have one row */
#define WHERE_OB_UNIQUE    0x00008000  /* Values in ORDER BY columns are 
                                       ** different for every output row */
#define WHERE_VIRTUALTABLE 0x00010000  /* Use virtual-table processing */

#define WHERE_MULTI_OR     0x00020000  /* OR using multiple indices */
#define WHERE_TEMP_INDEX   0x00040000  /* Uses an ephemeral index */
#define WHERE_DISTINCT     0x00080000  /* Correct order for DISTINCT */
#define WHERE_COVER_SCAN   0x00100000  /* Full scan of a covering index */
#define WHERE_SINGLE_ROW   0x00200000  /* No more than one row guaranteed */

/*
** This module contains many separate subroutines that work together to
** find the best indices to use for accessing a particular table in a query.
** An instance of the following structure holds context information about the
** index search so that it can be more easily passed between the various
** routines.
................................................................................
    if( (pTerm->eOperator & WO_OR)!=0
     && ((pTerm->prereqAll & ~maskSrc) & p->notReady)==0
     && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 
    ){
      WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
      WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
      WhereTerm *pOrTerm;

      double rTotal = 0;
      double nRow = 0;
      Bitmask used = 0;
      WhereBestIdx sBOI;

      sBOI = *p;
      sBOI.pOrderBy = 0;
................................................................................
      ** of pCost. */
      /*WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));*/
      if( rTotal<p->cost.rCost ){
        p->cost.rCost = rTotal;
        p->cost.used = used;
        p->cost.plan.nRow = nRow;
        p->cost.plan.nOBSat = p->i ? p->aLevel[p->i-1].plan.nOBSat : 0;
        p->cost.plan.wsFlags = WHERE_MULTI_OR;
        p->cost.plan.u.pTerm = pTerm;
      }
    }
  }
#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
}

................................................................................
  testcase( pTable->nCol==BMS-2 );
  for(i=0; i<mxBitCol; i++){
    if( extraCols & (((Bitmask)1)<<i) ) nColumn++;
  }
  if( pSrc->colUsed & (((Bitmask)1)<<(BMS-1)) ){
    nColumn += pTable->nCol - BMS + 1;
  }
  pLevel->plan.wsFlags |= WHERE_COLUMN_EQ | WHERE_IDX_ONLY;

  /* Construct the Index object to describe this index */
  nByte = sizeof(Index);
  nByte += nColumn*sizeof(int);     /* Index.aiColumn */
  nByte += nColumn*sizeof(char*);   /* Index.azColl */
  nByte += nColumn;                 /* Index.aSortOrder */
  pIdx = sqlite3DbMallocZero(pParse->db, nByte);
................................................................................

  /*WHERETRACE(("   best index is %s cost=%.1f\n",
         p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk",
         p->cost.rCost));*/
  
  bestOrClauseIndex(p);
  bestAutomaticIndex(p);
  if( eqTermMask & WO_ISNULL ) p->cost.plan.wsFlags |= WHERE_NULL_OK;
}

/*
** Find the query plan for accessing table pSrc->pTab. Write the
** best query plan and its cost into the WhereCost object supplied 
** as the last parameter. This function may calculate the cost of
** both real and virtual table scans.
................................................................................
  Index *pIdx;                  /* The index being used for this loop */
  int iCur = pLevel->iTabCur;   /* The cursor of the table */
  WhereTerm *pTerm;             /* A single constraint term */
  int j;                        /* Loop counter */
  int regBase;                  /* Base register */
  int nReg;                     /* Number of registers to allocate */
  char *zAff;                   /* Affinity string to return */
  int eqFlags;                  /* WO_EQ|WO_IN and maybe also WO_ISNULL */

  /* This module is only called on query plans that use an index. */
  assert( pLevel->plan.wsFlags & WHERE_INDEXED );
  pIdx = pLevel->plan.u.pIdx;

  /* Figure out how many memory cells we will need then allocate them.
  */
................................................................................
  if( !zAff ){
    pParse->db->mallocFailed = 1;
  }

  /* Evaluate the equality constraints
  */
  assert( pIdx->nColumn>=nEq );
  eqFlags = (pLevel->plan.wsFlags&WHERE_NULL_OK) ? (WO_EQ|WO_IN|WO_ISNULL)
                                                 : (WO_EQ|WO_IN);
  for(j=0; j<nEq; j++){
    int r1;
    int k = pIdx->aiColumn[j];
    pTerm = findTerm(pWC, iCur, k, notReady, eqFlags, pIdx);
    if( pTerm==0 ) break;
    /* The following true for indices with redundant columns. 
    ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
    testcase( (pTerm->wtFlags & TERM_CODED)!=0 );
    testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
    r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, regBase+j);
    if( r1!=regBase+j ){
................................................................................
      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 N %2d", p->wsFlags, 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
................................................................................

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


     && p->rSetup<=pTemplate->rSetup
     && p->rRun<=pTemplate->rRun
    ){
      /* Already holding an equal or better WhereLoop.
      ** Return without changing or adding anything */
      return SQLITE_OK;
    }
    if( (p->prereq & pTemplate->prereq)==pTemplate->prereq


     && p->rSetup>=pTemplate->rSetup
     && p->rRun>=pTemplate->rRun
    ){
      /* Overwrite an existing WhereLoop with a better one */
      pNext = p->pNextLoop;
      whereLoopClear(db, p);
      break;
................................................................................
  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){
................................................................................
    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++){
................................................................................
    }
    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->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;
................................................................................
    }
    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
** (or GROUP BY) without requiring a separate source operation.  Return 1
** if it does and 0 if it does not and -1 if we cannot tell.
*/
static int wherePathSatisfiesOrderBy(
  WhereInfo *pWInfo,    /* The WHERE clause */
  WherePath *pPath,     /* The WherePath to check */
  int nLoop,            /* Number of entries in pPath->aLoop[] */
  WhereLoop *pLoop      /* Add this WhereLoop to the end of pPath->aLoop[] */
){
  if( pLoop->wsFlags & WHERE_VIRTUALTABLE ){
    return nLoop==0 && pLoop->u.vtab.isOrdered;
  }else{
    /* TBD: Check to see if pFrom + pWLoop satisfies the ORDER BY.
    **  (1)  If yes:   set isOrderedValid and isOrdered to 1.
    **  (2)  If no:    set isOrderedValid to 1 and isOrdered to 0.
    **  (3)  unknown:  no-op */
    return 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.
**
** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
................................................................................
  const int mxChoice = 10;  /* Maximum number of simultaneous paths tracked */
  int nLoop;                /* Number of terms in the join */
  sqlite3 *db;              /* The database connection */
  int iLoop;                /* Loop counter over the terms of the join */
  int ii, jj;               /* Loop counters */
  double rCost;             /* Cost of a path */
  double mxCost;            /* Maximum cost of a set of paths */
  double rSortCost;         /* Cost to do a sort */
  int nTo, nFrom;           /* Number of valid entries in aTo[] and aFrom[] */
  WherePath *aFrom;         /* All nFrom paths at the previous level */
  WherePath *aTo;           /* The nTo best paths at the current level */
  WherePath *pFrom;         /* An element of aFrom[] that we are working on */
  WherePath *pTo;           /* An element of aTo[] that we are working on */
  WhereLoop *pWLoop;        /* One of the WhereLoop objects */
  WhereLoop *pNext;         /* Next loop */
  WhereLoop **pX;           /* Used to divy up the pSpace memory */
  char *pSpace;             /* Temporary memory used by this routine */

  db = pWInfo->pParse->db;
  nLoop = pWInfo->nLevel;
  assert( nLoop<=pWInfo->pTabList->nSrc );

................................................................................
  aFrom = aTo+mxChoice;
  memset(aFrom, 0, sizeof(aFrom[0]));
  pX = (WhereLoop**)(aFrom+mxChoice);
  for(ii=0, pFrom=aTo; ii<mxChoice*2; ii++, pFrom++, pX += nLoop){
    pFrom->aLoop = pX;
  }

  /* Seed the search with a single WherePath containing zero WhereLoops */
  aFrom[0].nRow = (double)1;
  nFrom = 1;

  /* Precompute the cost of sorting the final result set, if the caller
  ** to sqlite3WhereBegin() was concerned about sorting */
  rSortCost = (double)0;
  if( pWInfo->pOrderBy==0 ){
    aFrom[0].isOrderedValid = 1;
  }else{
    /* Compute an estimate on the cost to sort the entire result set */
    rSortCost = (double)1;
    for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pNext){
      pNext = pWLoop->pNextLoop;
      rCost = pWLoop->nOut;
      while( pNext && pNext->iTab==pWLoop->iTab ){
        if( pNext->nOut<rCost ) rCost = pNext->nOut;
        pNext = pNext->pNextLoop;
      }
      rSortCost *= rCost;
    }
    rSortCost *= estLog(rSortCost);
  }

  /* Compute successively longer WherePaths using the previous generation
  ** of WherePaths as the basis for the next.  Keep track of the mxChoice
  ** best paths at each generation */
  for(iLoop=0; iLoop<nLoop; iLoop++){
    nTo = 0;
    for(ii=0, pFrom=aFrom; ii<nFrom; ii++, pFrom++){
      for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pWLoop->pNextLoop){
        Bitmask maskNew;
        u8 isOrderedValid = pFrom->isOrderedValid;
        u8 isOrdered = pFrom->isOrdered;
        if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
        if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
        /* At this point, pWLoop is a candidate to be the next loop. 
        ** Compute its cost */
        rCost = pWLoop->rSetup + pWLoop->rRun*pFrom->nRow + pFrom->rCost;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( !isOrderedValid ){
          switch( wherePathSatisfiesOrderBy(pWInfo, pFrom, iLoop, pWLoop) ){
            case 1:  /* Yes.  pFrom+pWLoop does satisfy the ORDER BY clause */
              isOrdered = 1;
              isOrderedValid = 1;
              break;
            case 0:  /* No.  pFrom+pWLoop will require a separate sort */
              isOrdered = 0;
              isOrderedValid = 1;
              rCost += rSortCost;
              break;
            default: /* Cannot tell yet.  Try again on the next iteration */
              break;
          }
        }
        /* Check to see if pWLoop should be added to the mxChoice best so far */
        for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){
          if( pTo->maskLoop==maskNew && pTo->isOrderedValid==isOrderedValid ){
            break;
          }
        }
        if( jj>=nTo ){
          if( nTo>=mxChoice && rCost>=mxCost ) continue;
          if( nTo<mxChoice ){
            jj = nTo++;
          }else{
            for(jj=nTo-1; aTo[jj].rCost<mxCost; jj--){ assert(jj>0); }
          }
          pTo = &aTo[jj];
        }else{
          if( pTo->rCost<=rCost ) continue;
        }
        /* pWLoop is a winner.  Add it to the set of best so far */
        pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf;
        pTo->nRow = pFrom->nRow * pWLoop->nOut;
        pTo->rCost = rCost;
        pTo->isOrderedValid = isOrderedValid;
        pTo->isOrdered = isOrdered;
        memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop);
        pTo->aLoop[iLoop] = pWLoop;
        if( nTo>=mxChoice ){
          mxCost = aTo[0].rCost;
          for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){
            if( pTo->rCost>mxCost ) mxCost = pTo->rCost;
          }
................................................................................
        for(jj=0; jj<=iLoop; jj++){
          whereLoopPrint(aTo[ii].aLoop[jj], pWInfo->pTabList);
        }
      }
    }
#endif

    /* Swap the roles of aFrom and aTo for the next generation */

    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.  pFrom will be left pointing to that path */
  pFrom = aFrom;
  for(ii=1; ii<nFrom; ii++){
    if( pFrom->rCost>aFrom[ii].rCost ) pFrom = &aFrom[ii];
  }
  assert( pWInfo->nLevel==nLoop );
  /* Load the lowest cost path into pWInfo */
  for(iLoop=0; iLoop<nLoop; iLoop++){
    pWInfo->a[iLoop].pWLoop = pFrom->aLoop[iLoop];
  }
  if( pFrom->isOrdered ){
    pWInfo->nOBSat = pWInfo->pOrderBy->nExpr;
  }

  /* Free temporary memory and return success */
  sqlite3DbFree(db, pSpace);
  return SQLITE_OK;
}

/*
................................................................................
    sqlite3DbFree(db, pWInfo);
    pWInfo = 0;
    goto whereBeginError;
  }
  pWInfo->nLevel = nTabList;
  pWInfo->pParse = pParse;
  pWInfo->pTabList = pTabList;
  pWInfo->pOrderBy = pOrderBy;
  pWInfo->pDistinct = pDistinct;
  pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
  pWInfo->pWC = sWBI.pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
  pWInfo->wctrlFlags = wctrlFlags;
  pWInfo->savedNQueryLoop = pParse->nQueryLoop;
  pMaskSet = (WhereMaskSet*)&sWBI.pWC[1];
  sWBI.aLevel = pWInfo->a;
  sWLB.pWInfo = pWInfo;