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

Changes to src/where.c.

    38     38   typedef struct WhereMaskSet WhereMaskSet;
    39     39   typedef struct WhereOrInfo WhereOrInfo;
    40     40   typedef struct WhereAndInfo WhereAndInfo;
    41     41   typedef struct WhereCost WhereCost;
    42     42   typedef struct WhereLoop WhereLoop;
    43     43   typedef struct WherePath WherePath;
    44     44   typedef struct WhereTerm WhereTerm;
           45  +typedef struct WhereLoopBuilder WhereLoopBuilder;
           46  +typedef struct WhereScan WhereScan;
    45     47   
    46     48   /*
    47     49   ** Each instance of this object represents a way of evaluating one
    48     50   ** term of a join.  The WhereClause object holds a table of these
    49     51   ** objects using (iTab,prereq,iOb,nOb) as the primary key.  Note that the
    50     52   ** same join term might have multiple associated WhereLoop objects.
    51     53   */
................................................................................
    56     58     double rSetup;        /* One-time setup cost (ex: create transient index) */
    57     59     double rRun;          /* Cost of running each loop */
    58     60     double nOut;          /* Estimated number of output rows */
    59     61     u32 wsFlags;          /* WHERE_* flags describing the plan */
    60     62     u16 nEq;              /* Number of equality constraints */
    61     63     u16 nTerm;            /* Number of entries in aTerm[] */
    62     64     Index *pIndex;        /* Index used */
    63         -  WhereTerm *aTerm;     /* WhereTerms used */
           65  +  WhereTerm **aTerm;    /* WhereTerms used */
    64     66     WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */
    65     67   };
    66     68   
    67     69   /*
    68     70   ** Each instance of this object holds a sequence of WhereLoop objects
    69     71   ** that implement some or all of the entire query plan.  
    70     72   */
................................................................................
   157    159   #define TERM_OR_OK      0x40   /* Used during OR-clause processing */
   158    160   #ifdef SQLITE_ENABLE_STAT3
   159    161   #  define TERM_VNULL    0x80   /* Manufactured x>NULL or x<=NULL term */
   160    162   #else
   161    163   #  define TERM_VNULL    0x00   /* Disabled if not using stat3 */
   162    164   #endif
   163    165   
          166  +/*
          167  +** An instance of the WhereScan object is used as an iterator for locating
          168  +** terms in the WHERE clause that are useful to the query planner.
          169  +*/
          170  +struct WhereScan {
          171  +  WhereTerm *pCurrent;       /* Most recent match */
          172  +  WhereClause *pOrigWC;      /* Original, innermost WhereClause */
          173  +  WhereClause *pWC;          /* WhereClause currently being scanned */
          174  +  char *zCollName;           /* Must have this collating sequence, if not NULL */
          175  +  char idxaff;               /* Must match this affinity, if zCollName!=NULL */
          176  +  unsigned char nEquiv;      /* Number of entries in aEquiv[] */
          177  +  unsigned char iEquiv;      /* Next unused slot in aEquiv[] */
          178  +  u32 opMask;                /* Acceptable operators */
          179  +  int k;                     /* Resume scanning at this->pWC->a[this->k] */
          180  +  int aEquiv[22];            /* Cursor,Column pairs for equivalence classes */
          181  +};
          182  +
   164    183   /*
   165    184   ** An instance of the following structure holds all information about a
   166    185   ** WHERE clause.  Mostly this is a container for one or more WhereTerms.
   167    186   **
   168    187   ** Explanation of pOuter:  For a WHERE clause of the form
   169    188   **
   170    189   **           a AND ((b AND c) OR (d AND e)) AND f
................................................................................
   242    261   ** cost of pursuing that strategy.
   243    262   */
   244    263   struct WhereCost {
   245    264     WherePlan plan;    /* The lookup strategy */
   246    265     double rCost;      /* Overall cost of pursuing this search strategy */
   247    266     Bitmask used;      /* Bitmask of cursors used by this plan */
   248    267   };
          268  +
          269  +/*
          270  +** This object is a factory for WhereLoop objects for a particular query.
          271  +*/
          272  +struct WhereLoopBuilder {
          273  +  WhereInfo *pWInfo;        /* Information about this WHERE */
          274  +  sqlite3 *db;              /* Database connection */
          275  +  Parse *pParse;            /* Parsing context */
          276  +  WhereClause *pWC;         /* WHERE clause terms */
          277  +  SrcList *pTabList;        /* FROM clause */
          278  +  ExprList *pOrderBy;       /* ORDER BY clause */
          279  +  WhereLoop *pNew;          /* Template WhereLoop */
          280  +};
   249    281   
   250    282   /*
   251    283   ** Bitmasks for the operators that indices are able to exploit.  An
   252    284   ** OR-ed combination of these values can be used when searching for
   253    285   ** terms in the where clause.
   254    286   */
   255    287   #define WO_IN     0x001
................................................................................
   656    688     assert( op!=TK_EQ || c==WO_EQ );
   657    689     assert( op!=TK_LT || c==WO_LT );
   658    690     assert( op!=TK_LE || c==WO_LE );
   659    691     assert( op!=TK_GT || c==WO_GT );
   660    692     assert( op!=TK_GE || c==WO_GE );
   661    693     return c;
   662    694   }
          695  +
          696  +/*
          697  +** Advance to the next WhereTerm that matches according to the criteria
          698  +** established when the pScan object was initialized by whereScanInit().
          699  +** Return NULL if there are no more matching WhereTerms.
          700  +*/
          701  +WhereTerm *whereScanNext(WhereScan *pScan){
          702  +  int iCur;            /* The cursor on the LHS of the term */
          703  +  int iColumn;         /* The column on the LHS of the term.  -1 for IPK */
          704  +  Expr *pX;            /* An expression being tested */
          705  +  WhereClause *pWC;    /* Shorthand for pScan->pWC */
          706  +  WhereTerm *pTerm;    /* The term being tested */
          707  +
          708  +  while( pScan->iEquiv<=pScan->nEquiv ){
          709  +    iCur = pScan->aEquiv[pScan->iEquiv-2];
          710  +    iColumn = pScan->aEquiv[pScan->iEquiv-1];
          711  +    while( (pWC = pScan->pWC)!=0 ){
          712  +      for(pTerm=pWC->a+pScan->k; pScan->k<pWC->nTerm; pScan->k++, pTerm++){
          713  +        if( pTerm->leftCursor==iCur && pTerm->u.leftColumn==iColumn ){
          714  +          if( (pTerm->eOperator & WO_EQUIV)!=0
          715  +           && pScan->nEquiv<ArraySize(pScan->aEquiv)
          716  +          ){
          717  +            int j;
          718  +            pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight);
          719  +            assert( pX->op==TK_COLUMN );
          720  +            for(j=0; j<pScan->nEquiv; j+=2){
          721  +              if( pScan->aEquiv[j]==pX->iTable
          722  +               && pScan->aEquiv[j+1]==pX->iColumn ){
          723  +                  break;
          724  +              }
          725  +            }
          726  +            if( j==pScan->nEquiv ){
          727  +              pScan->aEquiv[j] = pX->iTable;
          728  +              pScan->aEquiv[j+1] = pX->iColumn;
          729  +              pScan->nEquiv += 2;
          730  +            }
          731  +          }
          732  +          if( (pTerm->eOperator & pScan->opMask)!=0 ){
          733  +            /* Verify the affinity and collating sequence match */
          734  +            if( pScan->zCollName && (pTerm->eOperator & WO_ISNULL)==0 ){
          735  +              CollSeq *pColl;
          736  +              pX = pTerm->pExpr;
          737  +              if( !sqlite3IndexAffinityOk(pX, pScan->idxaff) ){
          738  +                continue;
          739  +              }
          740  +              assert(pX->pLeft);
          741  +              pColl = sqlite3BinaryCompareCollSeq(pWC->pParse,
          742  +                                                  pX->pLeft, pX->pRight);
          743  +              if( pColl==0 ) pColl = pWC->pParse->db->pDfltColl;
          744  +              if( sqlite3StrICmp(pColl->zName, pScan->zCollName) ){
          745  +                continue;
          746  +              }
          747  +            }
          748  +            pScan->pCurrent = pTerm;
          749  +            pScan->k++;
          750  +            return pTerm;
          751  +          }
          752  +        }
          753  +      }
          754  +      pWC = pScan->pWC = pScan->pWC->pOuter;
          755  +      pScan->k = 0;
          756  +    }
          757  +    pScan->pWC = pScan->pOrigWC;
          758  +    pScan->k = 0;
          759  +    pScan->iEquiv += 2;
          760  +  }
          761  +  pScan->pCurrent = 0;
          762  +  return 0;
          763  +}
          764  +
          765  +/*
          766  +** Initialize a WHERE clause scanner object.  Return a pointer to the
          767  +** first match.  Return NULL if there are no matches.
          768  +**
          769  +** The scanner will be searching the WHERE clause pWC.  It will look
          770  +** for terms of the form "X <op> <expr>" where X is column iColumn of table
          771  +** iCur.  The <op> must be one of the operators described by opMask.
          772  +**
          773  +** If X is not the INTEGER PRIMARY KEY then X must be compatible with
          774  +** index pIdx.
          775  +*/
          776  +WhereTerm *whereScanInit(
          777  +  WhereScan *pScan,       /* The WhereScan object being initialized */
          778  +  WhereClause *pWC,       /* The WHERE clause to be scanned */
          779  +  int iCur,               /* Cursor to scan for */
          780  +  int iColumn,            /* Column to scan for */
          781  +  u32 opMask,             /* Operator(s) to scan for */
          782  +  Index *pIdx             /* Must be compatible with this index */
          783  +){
          784  +  int j;
          785  +
          786  +  memset(pScan, 0, sizeof(*pScan));
          787  +  pScan->pOrigWC = pWC;
          788  +  pScan->pWC = pWC;
          789  +  if( pIdx && iColumn>=0 ){
          790  +    pScan->idxaff = pIdx->pTable->aCol[iColumn].affinity;
          791  +    for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
          792  +      if( NEVER(j>=pIdx->nColumn) ) return 0;
          793  +    }
          794  +    pScan->zCollName = pIdx->azColl[j];
          795  +  }
          796  +  pScan->opMask = opMask;
          797  +  pScan->aEquiv[0] = iCur;
          798  +  pScan->aEquiv[1] = iColumn;
          799  +  pScan->nEquiv = 2;
          800  +  pScan->iEquiv = 2;
          801  +  return whereScanNext(pScan);
          802  +}
   663    803   
   664    804   /*
   665    805   ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
   666    806   ** where X is a reference to the iColumn of table iCur and <op> is one of
   667    807   ** the WO_xx operator codes specified by the op parameter.
   668    808   ** Return a pointer to the term.  Return 0 if not found.
   669    809   **
................................................................................
   688    828     WhereClause *pWC,     /* The WHERE clause to be searched */
   689    829     int iCur,             /* Cursor number of LHS */
   690    830     int iColumn,          /* Column number of LHS */
   691    831     Bitmask notReady,     /* RHS must not overlap with this mask */
   692    832     u32 op,               /* Mask of WO_xx values describing operator */
   693    833     Index *pIdx           /* Must be compatible with this index, if not NULL */
   694    834   ){
   695         -  WhereTerm *pTerm;            /* Term being examined as possible result */
   696         -  WhereTerm *pResult = 0;      /* The answer to return */
   697         -  WhereClause *pWCOrig = pWC;  /* Original pWC value */
   698         -  int j, k;                    /* Loop counters */
   699         -  Expr *pX;                /* Pointer to an expression */
   700         -  Parse *pParse;           /* Parsing context */
   701         -  int iOrigCol = iColumn;  /* Original value of iColumn */
   702         -  int nEquiv = 2;          /* Number of entires in aEquiv[] */
   703         -  int iEquiv = 2;          /* Number of entries of aEquiv[] processed so far */
   704         -  int aEquiv[22];          /* iCur,iColumn and up to 10 other equivalents */
   705         -
   706         -  assert( iCur>=0 );
   707         -  aEquiv[0] = iCur;
   708         -  aEquiv[1] = iColumn;
   709         -  for(;;){
   710         -    for(pWC=pWCOrig; pWC; pWC=pWC->pOuter){
   711         -      for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
   712         -        if( pTerm->leftCursor==iCur
   713         -          && pTerm->u.leftColumn==iColumn
   714         -        ){
   715         -          if( (pTerm->prereqRight & notReady)==0
   716         -           && (pTerm->eOperator & op & WO_ALL)!=0
   717         -          ){
   718         -            if( iOrigCol>=0 && pIdx && (pTerm->eOperator & WO_ISNULL)==0 ){
   719         -              CollSeq *pColl;
   720         -              char idxaff;
   721         -      
   722         -              pX = pTerm->pExpr;
   723         -              pParse = pWC->pParse;
   724         -              idxaff = pIdx->pTable->aCol[iOrigCol].affinity;
   725         -              if( !sqlite3IndexAffinityOk(pX, idxaff) ){
   726         -                continue;
   727         -              }
   728         -      
   729         -              /* Figure out the collation sequence required from an index for
   730         -              ** it to be useful for optimising expression pX. Store this
   731         -              ** value in variable pColl.
   732         -              */
   733         -              assert(pX->pLeft);
   734         -              pColl = sqlite3BinaryCompareCollSeq(pParse,pX->pLeft,pX->pRight);
   735         -              if( pColl==0 ) pColl = pParse->db->pDfltColl;
   736         -      
   737         -              for(j=0; pIdx->aiColumn[j]!=iOrigCol; j++){
   738         -                if( NEVER(j>=pIdx->nColumn) ) return 0;
   739         -              }
   740         -              if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ){
   741         -                continue;
   742         -              }
   743         -            }
   744         -            if( pTerm->prereqRight==0 && (pTerm->eOperator&WO_EQ)!=0 ){
   745         -              pResult = pTerm;
   746         -              goto findTerm_success;
   747         -            }else if( pResult==0 ){
   748         -              pResult = pTerm;
   749         -            }
   750         -          }
   751         -          if( (pTerm->eOperator & WO_EQUIV)!=0
   752         -           && nEquiv<ArraySize(aEquiv)
   753         -          ){
   754         -            pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight);
   755         -            assert( pX->op==TK_COLUMN );
   756         -            for(j=0; j<nEquiv; j+=2){
   757         -              if( aEquiv[j]==pX->iTable && aEquiv[j+1]==pX->iColumn ) break;
   758         -            }
   759         -            if( j==nEquiv ){
   760         -              aEquiv[j] = pX->iTable;
   761         -              aEquiv[j+1] = pX->iColumn;
   762         -              nEquiv += 2;
   763         -            }
   764         -          }
   765         -        }
   766         -      }
   767         -    }
   768         -    if( iEquiv>=nEquiv ) break;
   769         -    iCur = aEquiv[iEquiv++];
   770         -    iColumn = aEquiv[iEquiv++];
   771         -  }
   772         -findTerm_success:
          835  +  WhereTerm *pResult = 0;
          836  +  WhereTerm *p;
          837  +  WhereScan scan;
          838  +
          839  +  p = whereScanInit(&scan, pWC, iCur, iColumn, op, pIdx);
          840  +  while( p ){
          841  +    if( (p->prereqRight & notReady)==0 ){
          842  +      if( p->prereqRight==0 && (p->eOperator&WO_EQ)!=0 ){
          843  +        return p;
          844  +      }
          845  +      if( pResult==0 ) pResult = p;
          846  +    }
          847  +    p = whereScanNext(&scan);
          848  +  }
   773    849     return pResult;
   774    850   }
   775    851   
   776    852   /* Forward reference */
   777    853   static void exprAnalyze(SrcList*, WhereClause*, int);
   778    854   
   779    855   /*
................................................................................
  5054   5130       p = sqlite3DbMallocRaw(db, sizeof(WhereLoop));
  5055   5131       if( p==0 ) return SQLITE_NOMEM;
  5056   5132     }
  5057   5133     *p = *pTemplate;
  5058   5134     p->pNextLoop = pWInfo->pLoops;
  5059   5135     pWInfo->pLoops = p;
  5060   5136     if( pTemplate->nTerm<=0 ) return SQLITE_OK;
         5137  +  if( p->pIndex && p->pIndex->tnum==0 ) p->pIndex = 0;
  5061   5138     p->aTerm = sqlite3DbMallocRaw(db, pTemplate->nTerm*sizeof(p->aTerm[0]));
  5062   5139     if( p->aTerm==0 ){
  5063   5140       p->nTerm = 0;
         5141  +    sqlite3DbFree(db, p);
  5064   5142       return SQLITE_NOMEM;
  5065   5143     }
  5066   5144     memcpy(p->aTerm, pTemplate->aTerm, pTemplate->nTerm*sizeof(p->aTerm[0]));
  5067   5145     return SQLITE_OK;
  5068   5146   }
         5147  +
         5148  +/*
         5149  +** We have so far matched pBuilder->pNew->nEq terms of the index pIndex.
         5150  +** Try to match one more.
         5151  +**
         5152  +** If pProbe->tnum==0, that means pIndex is a fake index used for the
         5153  +** INTEGER PRIMARY KEY.
         5154  +*/
         5155  +static void whereLoopAddBtreeIndex(
         5156  +  WhereLoopBuilder *pBuilder,     /* The WhereLoop factory */
         5157  +  struct SrcList_item *pSrc,      /* FROM clause term being analyzed */
         5158  +  Index *pProbe,                  /* An index on pSrc */
         5159  +  int nInMul                      /* Number of iterations due to IN */
         5160  +){
         5161  +  sqlite3 *db;                    /* Database connection malloc context */
         5162  +  WhereLoop *pNew;                /* Template WhereLoop under construction */
         5163  +  WhereTerm *pTerm;               /* A WhereTerm under consideration */
         5164  +  int eqTermMask;                 /* Valid equality operators */
         5165  +  WhereScan scan;                 /* Iterator for WHERE terms */
         5166  +
         5167  +  db = pBuilder->db;
         5168  +  pNew = pBuilder->pNew;
         5169  +  if( db->mallocFailed ) return;
         5170  +
         5171  +  if( pProbe->tnum<=0 || (pSrc->jointype & JT_LEFT)!=0 ){
         5172  +    eqTermMask = WO_EQ|WO_IN;
         5173  +  }else{
         5174  +    eqTermMask = WO_EQ|WO_IN|WO_ISNULL;
         5175  +  }
         5176  +
         5177  +
         5178  +  if( pNew->nEq<pProbe->nColumn ){
         5179  +    int iCol;            /* Index of the column in the table */
         5180  +
         5181  +
         5182  +    iCol = pProbe->aiColumn[pNew->nEq];
         5183  +    pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol,
         5184  +                          eqTermMask, iCol>=0 ? pProbe : 0);
         5185  +    pNew->nEq++;
         5186  +    for(; pTerm!=0; pTerm = whereScanNext(&scan)){
         5187  +      pNew->aTerm[pNew->nEq-1] = pTerm;
         5188  +      
         5189  +    }
         5190  +    pNew->nEq--;
         5191  +
         5192  +  }
         5193  +}
  5069   5194   
  5070   5195   /*
  5071   5196   ** Add all WhereLoop objects for the iTab-th table of the join.  That
  5072   5197   ** table is guaranteed to be a b-tree table, not a virtual table.
  5073   5198   */
  5074   5199   static void whereLoopAddBtree(
  5075         -  WhereInfo *pWInfo,        /* WHERE clause information */
  5076         -  int iTab,                 /* The table to process */
  5077         -  Bitmask mExtra            /* Extra prerequesites for using this table */
         5200  +  WhereLoopBuilder *pBuilder, /* WHERE clause information */
         5201  +  int iTab,                   /* The table to process */
         5202  +  Bitmask mExtra              /* Extra prerequesites for using this table */
  5078   5203   ){
  5079         -  WhereLoop *pNew;          /* Template WhereLoop object */
  5080         -  sqlite3 *db = pWInfo->pParse->db;
         5204  +  Index *pProbe;              /* An index we are evaluating */
         5205  +  int eqTermMask;             /* Current mask of valid equality operators */
         5206  +  Index sPk;                  /* A fake index object for the primary key */
         5207  +  tRowcnt aiRowEstPk[2];      /* The aiRowEst[] value for the sPk index */
         5208  +  int aiColumnPk = -1;        /* The aColumn[] value for the sPk index */
         5209  +  struct SrcList_item *pSrc;  /* The FROM clause btree term to add */
         5210  +  sqlite3 *db;                /* The database connection */
         5211  +  WhereLoop *pNew;            /* Template WhereLoop object */
  5081   5212   
  5082         -  pNew = sqlite3DbMallocZero(db, sizeof(*pNew));
  5083         -  if( pNew==0 ) return;
  5084         -  
         5213  +  pNew = pBuilder->pNew;
         5214  +  db = pBuilder->db;
         5215  +  pSrc = pBuilder->pTabList->a + iTab;
         5216  +
         5217  +  if( pSrc->pIndex ){
         5218  +    /* An INDEXED BY clause specifies a particular index to use */
         5219  +    pProbe = pSrc->pIndex;
         5220  +  }else{
         5221  +    /* There is no INDEXED BY clause.  Create a fake Index object in local
         5222  +    ** variable sPk to represent the rowid primary key index.  Make this
         5223  +    ** fake index the first in a chain of Index objects with all of the real
         5224  +    ** indices to follow */
         5225  +    Index *pFirst;                  /* First of real indices on the table */
         5226  +    memset(&sPk, 0, sizeof(Index));
         5227  +    sPk.nColumn = 1;
         5228  +    sPk.aiColumn = &aiColumnPk;
         5229  +    sPk.aiRowEst = aiRowEstPk;
         5230  +    sPk.onError = OE_Replace;
         5231  +    sPk.pTable = pSrc->pTab;
         5232  +    aiRowEstPk[0] = pSrc->pTab->nRowEst;
         5233  +    aiRowEstPk[1] = 1;
         5234  +    pFirst = pSrc->pTab->pIndex;
         5235  +    if( pSrc->notIndexed==0 ){
         5236  +      /* The real indices of the table are only considered if the
         5237  +      ** NOT INDEXED qualifier is omitted from the FROM clause */
         5238  +      sPk.pNext = pFirst;
         5239  +    }
         5240  +    pProbe = &sPk;
         5241  +  }
         5242  +
         5243  +  /* Loop over all indices
         5244  +  */
         5245  +  for(; pProbe; pProbe=pProbe->pNext){
         5246  +    pNew->prereq = mExtra;
         5247  +    pNew->iTab = iTab;
         5248  +    pNew->nEq = 0;
         5249  +    pNew->nTerm = 0;
         5250  +    pNew->aTerm = sqlite3DbRealloc(db, pNew->aTerm,
         5251  +                                   (pProbe->nColumn+1)*sizeof(pNew->aTerm[0]));
         5252  +    if( pNew->aTerm==0 ) break;
         5253  +    pNew->pIndex = pProbe;
         5254  +
         5255  +    whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 1);
         5256  +
         5257  +    /* If there was an INDEXED BY clause, then only that one index is
         5258  +    ** considered. */
         5259  +    if( pSrc->pIndex ) break;
         5260  +  }
         5261  +
         5262  +#if 0  
  5085   5263     /* Insert a full table scan */
  5086   5264     pNew->iTab = iTab;
  5087   5265     pNew->rSetup = (double)0;
  5088   5266     pNew->rRun = (double)1000000;
  5089   5267     pNew->nOut = (double)1000000;
  5090         -  whereLoopInsert(pWInfo, pNew);
  5091         -
  5092         -  whereLoopDelete(db, pNew);
         5268  +  whereLoopInsert(pBuilder->pWInfo, pNew);
         5269  +#endif
  5093   5270   }
  5094   5271   
  5095   5272   /*
  5096   5273   ** Add all WhereLoop objects for the iTab-th table of the join.  That
  5097   5274   ** table is guaranteed to be a virtual table.
  5098   5275   */
  5099   5276   static void whereLoopAddVirtual(
  5100         -  WhereInfo *pWInfo,        /* WHERE clause information */
  5101         -  int iTab,                 /* The table to process */
  5102         -  Bitmask mExtra            /* Extra prerequesites for using this table */
         5277  +  WhereLoopBuilder *pBuilder,  /* WHERE clause information */
         5278  +  int iTab,                    /* The table to process */
         5279  +  Bitmask mExtra               /* Extra prerequesites for using this table */
  5103   5280   ){
  5104   5281   }
  5105   5282   
  5106   5283   /*
  5107   5284   ** Add all WhereLoop objects for all tables 
  5108   5285   */
  5109         -static void whereLoopAddAll(WhereInfo *pWInfo){
         5286  +static void whereLoopAddAll(WhereLoopBuilder *pBuilder){
  5110   5287     Bitmask mExtra = 0;
  5111   5288     Bitmask mPrior = 0;
  5112   5289     int iTab;
  5113         -  SrcList *pTabList = pWInfo->pTabList;
         5290  +  SrcList *pTabList = pBuilder->pTabList;
  5114   5291     struct SrcList_item *pItem;
  5115         -  WhereClause *pWC = pWInfo->pWC;
  5116         -  sqlite3 *db = pWInfo->pParse->db;
         5292  +  WhereClause *pWC = pBuilder->pWC;
         5293  +  sqlite3 *db = pBuilder->db;
  5117   5294   
  5118   5295     /* Loop over the tables in the join, from left to right */
         5296  +  pBuilder->pNew = sqlite3DbMallocZero(db, sizeof(WhereLoop));
         5297  +  if( pBuilder->pNew==0 ) return;
  5119   5298     for(iTab=0, pItem=pTabList->a; iTab<pTabList->nSrc; iTab++, pItem++){
  5120   5299       if( IsVirtual(pItem->pTab) ){
  5121         -      whereLoopAddVirtual(pWInfo, iTab, mExtra);
         5300  +      whereLoopAddVirtual(pBuilder, iTab, mExtra);
  5122   5301       }else{
  5123         -      whereLoopAddBtree(pWInfo, iTab, mExtra);
         5302  +      whereLoopAddBtree(pBuilder, iTab, mExtra);
  5124   5303       }
  5125   5304       mPrior |= getMask(pWC->pMaskSet, pItem->iCursor);
  5126   5305       if( (pItem->jointype & (JT_LEFT|JT_CROSS))!=0 ){
  5127   5306         mExtra = mPrior;
  5128   5307       }
  5129   5308       if( db->mallocFailed ) break;
  5130   5309     }
         5310  +  whereLoopDelete(db, pBuilder->pNew);
         5311  +  pBuilder->pNew = 0;
  5131   5312   }
  5132   5313   
  5133   5314   
  5134   5315   /*
  5135   5316   ** Generate the beginning of the loop used for WHERE clause processing.
  5136   5317   ** The return value is a pointer to an opaque structure that contains
  5137   5318   ** information needed to terminate the loop.  Later, the calling routine
................................................................................
  5230   5411   ){
  5231   5412     int nByteWInfo;            /* Num. bytes allocated for WhereInfo struct */
  5232   5413     int nTabList;              /* Number of elements in pTabList */
  5233   5414     WhereInfo *pWInfo;         /* Will become the return value of this function */
  5234   5415     Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  5235   5416     Bitmask notReady;          /* Cursors that are not yet positioned */
  5236   5417     WhereBestIdx sWBI;         /* Best index search context */
         5418  +  WhereLoopBuilder sWLB;     /* The WhereLoop builder */
  5237   5419     WhereMaskSet *pMaskSet;    /* The expression mask set */
  5238   5420     WhereLevel *pLevel;        /* A single level in pWInfo->a[] */
  5239   5421     int iFrom;                 /* First unused FROM clause element */
  5240   5422     int andFlags;              /* AND-ed combination of all pWC->a[].wtFlags */
  5241   5423     int ii;                    /* Loop counter */
  5242   5424     sqlite3 *db;               /* Database connection */
  5243   5425   
  5244   5426   
  5245   5427     /* Variable initialization */
  5246   5428     memset(&sWBI, 0, sizeof(sWBI));
  5247   5429     sWBI.pParse = pParse;
         5430  +  memset(&sWLB, 0, sizeof(sWLB));
         5431  +  sWLB.pParse = pParse;
         5432  +  sWLB.db = pParse->db;
         5433  +  sWLB.pTabList = pTabList;
         5434  +  sWLB.pOrderBy = pOrderBy;
  5248   5435   
  5249   5436     /* The number of tables in the FROM clause is limited by the number of
  5250   5437     ** bits in a Bitmask 
  5251   5438     */
  5252   5439     testcase( pTabList->nSrc==BMS );
  5253   5440     if( pTabList->nSrc>BMS ){
  5254   5441       sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);
................................................................................
  5286   5473     pWInfo->pTabList = pTabList;
  5287   5474     pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
  5288   5475     pWInfo->pWC = sWBI.pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
  5289   5476     pWInfo->wctrlFlags = wctrlFlags;
  5290   5477     pWInfo->savedNQueryLoop = pParse->nQueryLoop;
  5291   5478     pMaskSet = (WhereMaskSet*)&sWBI.pWC[1];
  5292   5479     sWBI.aLevel = pWInfo->a;
         5480  +  sWLB.pWInfo = pWInfo;
         5481  +  sWLB.pWC = pWInfo->pWC;
  5293   5482   
  5294   5483     /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
  5295   5484     ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
  5296   5485     if( OptimizationDisabled(db, SQLITE_DistinctOpt) ) pDistinct = 0;
  5297   5486   
  5298   5487     /* Split the WHERE clause into separate subexpressions where each
  5299   5488     ** subexpression is separated by an AND operator.
................................................................................
  5358   5547     if( pDistinct && isDistinctRedundant(pParse, pTabList, sWBI.pWC, pDistinct) ){
  5359   5548       pDistinct = 0;
  5360   5549       pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
  5361   5550     }
  5362   5551   
  5363   5552     /* Construct the WhereLoop objects */
  5364   5553     WHERETRACE(("*** Optimizer Start ***\n"));
  5365         -  whereLoopAddAll(pWInfo);
         5554  +  /*whereLoopAddAll(&sWLB);*/
  5366   5555   
  5367   5556     /* Display all of the WhereLoop objects if wheretrace is enabled */
  5368   5557   #if defined(SQLITE_DEBUG) \
  5369   5558       && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
  5370   5559     if( sqlite3WhereTrace ){
  5371   5560       WhereLoop *p;
  5372   5561       int nb = 2*((nTabList+15)/16);