/ Check-in [ccaf4c3f]
Login

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

Overview
Comment:Begin inserting some experimental code for the next generation query planner.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: ccaf4c3f7e1ec45e058d594d9b5c26818a37722a
User & Date: drh 2013-05-02 00:15:01
Context
2013-05-04
20:25
In where.c, make findTerm() a wrapper around methods to a new WhereScan object which is capable of finding all suitable matching terms, not just the first. This check-in includes some prototype functions for building WhereLoop objects. check-in: dd92b8fa user: drh tags: nextgen-query-plan-exp
2013-05-02
00:15
Begin inserting some experimental code for the next generation query planner. check-in: ccaf4c3f user: drh tags: nextgen-query-plan-exp
2013-05-01
17:58
Do not use a transitive constraint to an IN operator where the RHS is a constant if there exists a direct == operator to another table in an outer loop. check-in: faedaeac user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/sqliteInt.h.

  2061   2061     u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
  2062   2062     u8 eDistinct;             /* One of the WHERE_DISTINCT_* values below */
  2063   2063     int iTop;                 /* The very beginning of the WHERE loop */
  2064   2064     int iContinue;            /* Jump here to continue with next record */
  2065   2065     int iBreak;               /* Jump here to break out of the loop */
  2066   2066     int nLevel;               /* Number of nested loop */
  2067   2067     struct WhereClause *pWC;  /* Decomposition of the WHERE clause */
         2068  +  struct WhereLoop *pLoops; /* List of all WhereLoop objects */
  2068   2069     double savedNQueryLoop;   /* pParse->nQueryLoop outside the WHERE loop */
  2069   2070     double nRowOut;           /* Estimated number of output rows */
  2070   2071     WhereLevel a[1];          /* Information about each nest loop in WHERE */
  2071   2072   };
  2072   2073   
  2073   2074   /* Allowed values for WhereInfo.eDistinct and DistinctCtx.eTnctType */
  2074   2075   #define WHERE_DISTINCT_NOOP      0  /* DISTINCT keyword not used */

Changes to src/where.c.

    35     35   /* Forward reference
    36     36   */
    37     37   typedef struct WhereClause WhereClause;
    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  +typedef struct WhereLoop WhereLoop;
           43  +typedef struct WherePath WherePath;
           44  +typedef struct WhereTerm WhereTerm;
           45  +
           46  +/*
           47  +** Each instance of this object represents a way of evaluating one
           48  +** term of a join.  The WhereClause object holds a table of these
           49  +** objects using (iTab,prereq,iOb,nOb) as the primary key.  Note that the
           50  +** same join term might have multiple associated WhereLoop objects.
           51  +*/
           52  +struct WhereLoop {
           53  +  Bitmask prereq;       /* Bitmask of other loops that must run first */
           54  +  int iTab;             /* Index of the table coded by this loop */
           55  +  u16 iOb, nOb;         /* ORDER BY terms satisfied by this strategy */
           56  +  double rSetup;        /* One-time setup cost (ex: create transient index) */
           57  +  double rRun;          /* Cost of running each loop */
           58  +  double nOut;          /* Estimated number of output rows */
           59  +  u32 wsFlags;          /* WHERE_* flags describing the plan */
           60  +  u16 nEq;              /* Number of equality constraints */
           61  +  u16 nTerm;            /* Number of entries in aTerm[] */
           62  +  Index *pIndex;        /* Index used */
           63  +  WhereTerm *aTerm;     /* WhereTerms used */
           64  +  WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */
           65  +};
           66  +
           67  +/*
           68  +** Each instance of this object holds a sequence of WhereLoop objects
           69  +** that implement some or all of the entire query plan.  
           70  +*/
           71  +struct WherePath {
           72  +  Bitmask maskLoop;     /* Bitmask of all WhereLoop objects in this path */
           73  +  double nRow;          /* Estimated number of rows generated by this path */
           74  +  double rCost;         /* Total cost of this path */
           75  +  WhereLoop *aLoop[1];  /* Array of WhereLoop objects implementing this path */
           76  +  WherePath *pNextPath; /* Next path in order of increasing cost */
           77  +  WherePath *pPrevPath; /* Previous path in cost order */
           78  +};
    42     79   
    43     80   /*
    44     81   ** The query generator uses an array of instances of this structure to
    45     82   ** help it analyze the subexpressions of the WHERE clause.  Each WHERE
    46     83   ** clause subexpression is separated from the others by AND operators,
    47     84   ** usually, or sometimes subexpressions separated by OR.
    48     85   **
................................................................................
    87    124   ** bits in the Bitmask.  So, in the example above, the cursor numbers
    88    125   ** would be mapped into integers 0 through 7.
    89    126   **
    90    127   ** The number of terms in a join is limited by the number of bits
    91    128   ** in prereqRight and prereqAll.  The default is 64 bits, hence SQLite
    92    129   ** is only able to process joins with 64 or fewer tables.
    93    130   */
    94         -typedef struct WhereTerm WhereTerm;
    95    131   struct WhereTerm {
    96    132     Expr *pExpr;            /* Pointer to the subexpression that is this term */
    97    133     int iParent;            /* Disable pWC->a[iParent] when this term disabled */
    98    134     int leftCursor;         /* Cursor number of X in "X <op> <expr>" */
    99    135     union {
   100    136       int leftColumn;         /* Column number of X in "X <op> <expr>" */
   101    137       WhereOrInfo *pOrInfo;   /* Extra information if (eOperator & WO_OR)!=0 */
................................................................................
  1789   1825         WhereBestIdx sBOI;
  1790   1826   
  1791   1827         sBOI = *p;
  1792   1828         sBOI.pOrderBy = 0;
  1793   1829         sBOI.pDistinct = 0;
  1794   1830         sBOI.ppIdxInfo = 0;
  1795   1831         for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
  1796         -        WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", 
         1832  +        /*WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", 
  1797   1833             (pOrTerm - pOrWC->a), (pTerm - pWC->a)
  1798         -        ));
         1834  +        ));*/
  1799   1835           if( (pOrTerm->eOperator& WO_AND)!=0 ){
  1800   1836             sBOI.pWC = &pOrTerm->u.pAndInfo->wc;
  1801   1837             bestIndex(&sBOI);
  1802   1838           }else if( pOrTerm->leftCursor==iCur ){
  1803   1839             WhereClause tempWC;
  1804   1840             tempWC.pParse = pWC->pParse;
  1805   1841             tempWC.pMaskSet = pWC->pMaskSet;
................................................................................
  1818   1854           used |= sBOI.cost.used;
  1819   1855           if( rTotal>=p->cost.rCost ) break;
  1820   1856         }
  1821   1857   
  1822   1858         /* If there is an ORDER BY clause, increase the scan cost to account 
  1823   1859         ** for the cost of the sort. */
  1824   1860         if( p->pOrderBy!=0 ){
  1825         -        WHERETRACE(("... sorting increases OR cost %.9g to %.9g\n",
  1826         -                    rTotal, rTotal+nRow*estLog(nRow)));
         1861  +        /*WHERETRACE(("... sorting increases OR cost %.9g to %.9g\n",
         1862  +                    rTotal, rTotal+nRow*estLog(nRow)));*/
  1827   1863           rTotal += nRow*estLog(nRow);
  1828   1864         }
  1829   1865   
  1830   1866         /* If the cost of scanning using this OR term for optimization is
  1831   1867         ** less than the current cost stored in pCost, replace the contents
  1832   1868         ** of pCost. */
  1833         -      WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));
         1869  +      /*WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));*/
  1834   1870         if( rTotal<p->cost.rCost ){
  1835   1871           p->cost.rCost = rTotal;
  1836   1872           p->cost.used = used;
  1837   1873           p->cost.plan.nRow = nRow;
  1838   1874           p->cost.plan.nOBSat = p->i ? p->aLevel[p->i-1].plan.nOBSat : 0;
  1839   1875           p->cost.plan.wsFlags = flags;
  1840   1876           p->cost.plan.u.pTerm = pTerm;
................................................................................
  1923   1959       return;
  1924   1960     }
  1925   1961   
  1926   1962     /* Search for any equality comparison term */
  1927   1963     pWCEnd = &pWC->a[pWC->nTerm];
  1928   1964     for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
  1929   1965       if( termCanDriveIndex(pTerm, pSrc, p->notReady) ){
  1930         -      WHERETRACE(("auto-index reduces cost from %.1f to %.1f\n",
  1931         -                    p->cost.rCost, costTempIdx));
         1966  +      /*WHERETRACE(("auto-index reduces cost from %.1f to %.1f\n",
         1967  +                    p->cost.rCost, costTempIdx));*/
  1932   1968         p->cost.rCost = costTempIdx;
  1933   1969         p->cost.plan.nRow = logN + 1;
  1934   1970         p->cost.plan.wsFlags = WHERE_TEMP_INDEX;
  1935   1971         p->cost.used = pTerm->prereqRight;
  1936   1972         break;
  1937   1973       }
  1938   1974     }
................................................................................
  2109   2145     struct sqlite3_index_constraint *pIdxCons;
  2110   2146     struct sqlite3_index_orderby *pIdxOrderBy;
  2111   2147     struct sqlite3_index_constraint_usage *pUsage;
  2112   2148     WhereTerm *pTerm;
  2113   2149     int nOrderBy;
  2114   2150     sqlite3_index_info *pIdxInfo;
  2115   2151   
  2116         -  WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName));
         2152  +  /*WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName));*/
  2117   2153   
  2118   2154     /* Count the number of possible WHERE clause constraints referring
  2119   2155     ** to this virtual table */
  2120   2156     for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
  2121   2157       if( pTerm->leftCursor != pSrc->iCursor ) continue;
  2122   2158       assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
  2123   2159       testcase( pTerm->eOperator & WO_IN );
................................................................................
  2218   2254   ** that this is required.
  2219   2255   */
  2220   2256   static int vtabBestIndex(Parse *pParse, Table *pTab, sqlite3_index_info *p){
  2221   2257     sqlite3_vtab *pVtab = sqlite3GetVTable(pParse->db, pTab)->pVtab;
  2222   2258     int i;
  2223   2259     int rc;
  2224   2260   
  2225         -  WHERETRACE(("xBestIndex for %s\n", pTab->zName));
         2261  +  /*WHERETRACE(("xBestIndex for %s\n", pTab->zName));*/
  2226   2262     TRACE_IDX_INPUTS(p);
  2227   2263     rc = pVtab->pModule->xBestIndex(pVtab, p);
  2228   2264     TRACE_IDX_OUTPUTS(p);
  2229   2265   
  2230   2266     if( rc!=SQLITE_OK ){
  2231   2267       if( rc==SQLITE_NOMEM ){
  2232   2268         pParse->db->mallocFailed = 1;
................................................................................
  2729   2765       }
  2730   2766       if( rc==SQLITE_OK ){
  2731   2767         if( iUpper<=iLower ){
  2732   2768           *pRangeDiv = (double)p->aiRowEst[0];
  2733   2769         }else{
  2734   2770           *pRangeDiv = (double)p->aiRowEst[0]/(double)(iUpper - iLower);
  2735   2771         }
  2736         -      WHERETRACE(("range scan regions: %u..%u  div=%g\n",
  2737         -                  (u32)iLower, (u32)iUpper, *pRangeDiv));
         2772  +      /*WHERETRACE(("range scan regions: %u..%u  div=%g\n",
         2773  +                  (u32)iLower, (u32)iUpper, *pRangeDiv));*/
  2738   2774         return SQLITE_OK;
  2739   2775       }
  2740   2776     }
  2741   2777   #else
  2742   2778     UNUSED_PARAMETER(pParse);
  2743   2779     UNUSED_PARAMETER(p);
  2744   2780     UNUSED_PARAMETER(nEq);
................................................................................
  2787   2823       if( rc ) goto whereEqualScanEst_cancel;
  2788   2824     }else{
  2789   2825       pRhs = sqlite3ValueNew(pParse->db);
  2790   2826     }
  2791   2827     if( pRhs==0 ) return SQLITE_NOTFOUND;
  2792   2828     rc = whereKeyStats(pParse, p, pRhs, 0, a);
  2793   2829     if( rc==SQLITE_OK ){
  2794         -    WHERETRACE(("equality scan regions: %d\n", (int)a[1]));
         2830  +    /*WHERETRACE(("equality scan regions: %d\n", (int)a[1]));*/
  2795   2831       *pnRow = a[1];
  2796   2832     }
  2797   2833   whereEqualScanEst_cancel:
  2798   2834     sqlite3ValueFree(pRhs);
  2799   2835     return rc;
  2800   2836   }
  2801   2837   #endif /* defined(SQLITE_ENABLE_STAT3) */
................................................................................
  2833   2869       nEst = p->aiRowEst[0];
  2834   2870       rc = whereEqualScanEst(pParse, p, pList->a[i].pExpr, &nEst);
  2835   2871       nRowEst += nEst;
  2836   2872     }
  2837   2873     if( rc==SQLITE_OK ){
  2838   2874       if( nRowEst > p->aiRowEst[0] ) nRowEst = p->aiRowEst[0];
  2839   2875       *pnRow = nRowEst;
  2840         -    WHERETRACE(("IN row estimate: est=%g\n", nRowEst));
         2876  +    /*WHERETRACE(("IN row estimate: est=%g\n", nRowEst));*/
  2841   2877     }
  2842   2878     return rc;
  2843   2879   }
  2844   2880   #endif /* defined(SQLITE_ENABLE_STAT3) */
  2845   2881   
  2846   2882   /*
  2847   2883   ** Check to see if column iCol of the table with cursor iTab will appear
................................................................................
  3045   3081         uniqueNotNull = 0;
  3046   3082         isEq = 1;  /* "X IS NULL" means X has only a single value */
  3047   3083       }else if( pConstraint->prereqRight==0 ){
  3048   3084         isEq = 1;  /* Constraint "X=constant" means X has only a single value */
  3049   3085       }else{
  3050   3086         Expr *pRight = pConstraint->pExpr->pRight;
  3051   3087         if( pRight->op==TK_COLUMN ){
  3052         -        WHERETRACE(("       .. isOrderedColumn(tab=%d,col=%d)",
  3053         -                    pRight->iTable, pRight->iColumn));
         3088  +        /*WHERETRACE(("       .. isOrderedColumn(tab=%d,col=%d)",
         3089  +                    pRight->iTable, pRight->iColumn));*/
  3054   3090           isEq = isOrderedColumn(p, pRight->iTable, pRight->iColumn);
  3055         -        WHERETRACE((" -> isEq=%d\n", isEq));
         3091  +        /*WHERETRACE((" -> isEq=%d\n", isEq));*/
  3056   3092   
  3057   3093           /* If the constraint is of the form X=Y where Y is an ordered value
  3058   3094           ** in an outer loop, then make sure the sort order of Y matches the
  3059   3095           ** sort order required for X. */
  3060   3096           if( isMatch && isEq>=2 && isEq!=pOBItem->sortOrder+2 ){
  3061   3097             testcase( isEq==2 );
  3062   3098             testcase( isEq==3 );
................................................................................
  3315   3351       char bDist = bDistInit;       /* True if index cannot help with DISTINCT */
  3316   3352       char bLookup = 0;             /* True if not a covering index */
  3317   3353       WhereTerm *pTerm;             /* A single term of the WHERE clause */
  3318   3354   #ifdef SQLITE_ENABLE_STAT3
  3319   3355       WhereTerm *pFirstTerm = 0;    /* First term matching the index */
  3320   3356   #endif
  3321   3357   
  3322         -    WHERETRACE((
         3358  +    /*WHERETRACE((
  3323   3359         "   %s(%s):\n",
  3324   3360         pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk")
  3325         -    ));
         3361  +    ));*/
  3326   3362       memset(&pc, 0, sizeof(pc));
  3327   3363       pc.plan.nOBSat = nPriorSat;
  3328   3364   
  3329   3365       /* Determine the values of pc.plan.nEq and nInMul */
  3330   3366       for(pc.plan.nEq=0; pc.plan.nEq<pProbe->nColumn; pc.plan.nEq++){
  3331   3367         int j = pProbe->aiColumn[pc.plan.nEq];
  3332   3368         pTerm = findTerm(pWC, iCur, j, p->notReady, eqTermMask, pIdx);
................................................................................
  3399   3435       ** naturally scan rows in the required order, set the appropriate flags
  3400   3436       ** in pc.plan.wsFlags. Otherwise, if there is an ORDER BY clause but
  3401   3437       ** the index will scan rows in a different order, set the bSort
  3402   3438       ** variable.  */
  3403   3439       if( bSort && (pSrc->jointype & JT_LEFT)==0 ){
  3404   3440         int bRev = 2;
  3405   3441         int bObUnique = 0;
  3406         -      WHERETRACE(("      --> before isSortIndex: nPriorSat=%d\n",nPriorSat));
         3442  +      /*WHERETRACE(("      --> before isSortIndex: nPriorSat=%d\n",nPriorSat));*/
  3407   3443         pc.plan.nOBSat = isSortingIndex(p, pProbe, iCur, &bRev, &bObUnique);
  3408         -      WHERETRACE(("      --> after  isSortIndex: bRev=%d bObU=%d nOBSat=%d\n",
  3409         -                  bRev, bObUnique, pc.plan.nOBSat));
         3444  +      /*WHERETRACE(("      --> after  isSortIndex: bRev=%d bObU=%d nOBSat=%d\n",
         3445  +                  bRev, bObUnique, pc.plan.nOBSat));*/
  3410   3446         if( nPriorSat<pc.plan.nOBSat || (pc.plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
  3411   3447           pc.plan.wsFlags |= WHERE_ORDERED;
  3412   3448           if( bObUnique ) pc.plan.wsFlags |= WHERE_OB_UNIQUE;
  3413   3449         }
  3414   3450         if( nOrderBy==pc.plan.nOBSat ){
  3415   3451           bSort = 0;
  3416   3452           pc.plan.wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE;
................................................................................
  3630   3666             pc.plan.nRow /= 2;
  3631   3667           }
  3632   3668         }
  3633   3669         if( pc.plan.nRow<2 ) pc.plan.nRow = 2;
  3634   3670       }
  3635   3671   
  3636   3672   
  3637         -    WHERETRACE((
         3673  +    /*WHERETRACE((
  3638   3674         "      nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%08x\n"
  3639   3675         "      notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f\n"
  3640   3676         "      used=0x%llx nOBSat=%d\n",
  3641   3677         pc.plan.nEq, nInMul, (int)rangeDiv, bSort, bLookup, pc.plan.wsFlags,
  3642   3678         p->notReady, log10N, pc.plan.nRow, pc.rCost, pc.used,
  3643   3679         pc.plan.nOBSat
  3644         -    ));
         3680  +    ));*/
  3645   3681   
  3646   3682       /* If this index is the best we have seen so far, then record this
  3647   3683       ** index and its cost in the p->cost structure.
  3648   3684       */
  3649   3685       if( (!pIdx || pc.plan.wsFlags) && compareCost(&pc, &p->cost) ){
  3650   3686         p->cost = pc;
  3651   3687         p->cost.plan.wsFlags &= wsFlagMask;
................................................................................
  3673   3709     assert( p->pOrderBy || (p->cost.plan.wsFlags&WHERE_ORDERED)==0 );
  3674   3710     assert( p->cost.plan.u.pIdx==0 || (p->cost.plan.wsFlags&WHERE_ROWID_EQ)==0 );
  3675   3711     assert( pSrc->pIndex==0 
  3676   3712          || p->cost.plan.u.pIdx==0 
  3677   3713          || p->cost.plan.u.pIdx==pSrc->pIndex 
  3678   3714     );
  3679   3715   
  3680         -  WHERETRACE(("   best index is %s cost=%.1f\n",
         3716  +  /*WHERETRACE(("   best index is %s cost=%.1f\n",
  3681   3717            p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk",
  3682         -         p->cost.rCost));
         3718  +         p->cost.rCost));*/
  3683   3719     
  3684   3720     bestOrClauseIndex(p);
  3685   3721     bestAutomaticIndex(p);
  3686   3722     p->cost.plan.wsFlags |= eqTermMask;
  3687   3723   }
  3688   3724   
  3689   3725   /*
................................................................................
  4924   4960   ** analysis only.
  4925   4961   */
  4926   4962   char sqlite3_query_plan[BMS*2*40];  /* Text of the join */
  4927   4963   static int nQPlan = 0;              /* Next free slow in _query_plan[] */
  4928   4964   
  4929   4965   #endif /* SQLITE_TEST */
  4930   4966   
         4967  +/*
         4968  +** Delete a WhereLoop object
         4969  +*/
         4970  +static void whereLoopDelete(sqlite3 *db, WhereLoop *p){
         4971  +  sqlite3DbFree(db, p->aTerm);
         4972  +  sqlite3DbFree(db, p);
         4973  +}
  4931   4974   
  4932   4975   /*
  4933   4976   ** Free a WhereInfo structure
  4934   4977   */
  4935   4978   static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){
  4936   4979     if( ALWAYS(pWInfo) ){
  4937   4980       int i;
................................................................................
  4949   4992           if( pIdx ){
  4950   4993             sqlite3DbFree(db, pIdx->zColAff);
  4951   4994             sqlite3DbFree(db, pIdx);
  4952   4995           }
  4953   4996         }
  4954   4997       }
  4955   4998       whereClauseClear(pWInfo->pWC);
         4999  +    while( pWInfo->pLoops ){
         5000  +      WhereLoop *p = pWInfo->pLoops;
         5001  +      pWInfo->pLoops = p->pNextLoop;
         5002  +      whereLoopDelete(db, p);
         5003  +    }
  4956   5004       sqlite3DbFree(db, pWInfo);
  4957   5005     }
  4958   5006   }
         5007  +
         5008  +/*
         5009  +** Insert or replace a WhereLoop entry using the template supplied.
         5010  +**
         5011  +** An existing WhereLoop entry might be overwritten if the new template
         5012  +** is better and has fewer dependencies.  Or the template will be ignored
         5013  +** and no insert will occur if an existing WhereLoop is faster and has
         5014  +** fewer dependencies than the template.  Otherwise a new WhereLoop is
         5015  +** added based no the template.
         5016  +*/
         5017  +static int whereLoopInsert(WhereInfo *pWInfo, WhereLoop *pTemplate){
         5018  +  WhereLoop **ppPrev, *p;
         5019  +  sqlite3 *db = pWInfo->pParse->db;
         5020  +
         5021  +  /* Search for an existing WhereLoop to overwrite, or which takes
         5022  +  ** priority over pTemplate.
         5023  +  */
         5024  +  for(ppPrev=&pWInfo->pLoops, p=*ppPrev; p; ppPrev=&p->pNextLoop, p=*ppPrev){
         5025  +    if( p->iTab!=pTemplate->iTab ) continue;
         5026  +    if( (p->prereq & pTemplate->prereq)==p->prereq
         5027  +     && p->nOb>=pTemplate->nOb
         5028  +     && p->iOb==pTemplate->iOb
         5029  +     && p->rSetup<=pTemplate->rSetup
         5030  +     && p->rRun<=pTemplate->rRun
         5031  +    ){
         5032  +      /* Already holding an equal or better WhereLoop.
         5033  +      ** Return without changing or adding anything */
         5034  +      return SQLITE_OK;
         5035  +    }
         5036  +    if( (p->prereq & pTemplate->prereq)==pTemplate->prereq
         5037  +     && p->nOb<=pTemplate->nOb
         5038  +     && p->iOb==pTemplate->iOb
         5039  +     && p->rSetup>=pTemplate->rSetup
         5040  +     && p->rRun>=pTemplate->rRun
         5041  +    ){
         5042  +      /* Overwrite an existing WhereLoop with a better one */
         5043  +      sqlite3DbFree(db, p->aTerm);
         5044  +      *ppPrev = p->pNextLoop;
         5045  +      break;
         5046  +    }
         5047  +  }
         5048  +
         5049  +  /* If we reach this point it means that either p[] should be overwritten
         5050  +  ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
         5051  +  ** WhereLoop and insert it.
         5052  +  */
         5053  +  if( p==0 ){
         5054  +    p = sqlite3DbMallocRaw(db, sizeof(WhereLoop));
         5055  +    if( p==0 ) return SQLITE_NOMEM;
         5056  +  }
         5057  +  *p = *pTemplate;
         5058  +  p->pNextLoop = pWInfo->pLoops;
         5059  +  pWInfo->pLoops = p;
         5060  +  if( pTemplate->nTerm<=0 ) return SQLITE_OK;
         5061  +  p->aTerm = sqlite3DbMallocRaw(db, pTemplate->nTerm*sizeof(p->aTerm[0]));
         5062  +  if( p->aTerm==0 ){
         5063  +    p->nTerm = 0;
         5064  +    return SQLITE_NOMEM;
         5065  +  }
         5066  +  memcpy(p->aTerm, pTemplate->aTerm, pTemplate->nTerm*sizeof(p->aTerm[0]));
         5067  +  return SQLITE_OK;
         5068  +}
         5069  +
         5070  +/*
         5071  +** Add all WhereLoop objects for the iTab-th table of the join.  That
         5072  +** table is guaranteed to be a b-tree table, not a virtual table.
         5073  +*/
         5074  +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 */
         5078  +){
         5079  +  WhereLoop *pNew;          /* Template WhereLoop object */
         5080  +  sqlite3 *db = pWInfo->pParse->db;
         5081  +
         5082  +  pNew = sqlite3DbMallocZero(db, sizeof(*pNew));
         5083  +  if( pNew==0 ) return;
         5084  +  
         5085  +  /* Insert a full table scan */
         5086  +  pNew->iTab = iTab;
         5087  +  pNew->rSetup = (double)0;
         5088  +  pNew->rRun = (double)1000000;
         5089  +  pNew->nOut = (double)1000000;
         5090  +  whereLoopInsert(pWInfo, pNew);
         5091  +
         5092  +  whereLoopDelete(db, pNew);
         5093  +}
         5094  +
         5095  +/*
         5096  +** Add all WhereLoop objects for the iTab-th table of the join.  That
         5097  +** table is guaranteed to be a virtual table.
         5098  +*/
         5099  +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 */
         5103  +){
         5104  +}
         5105  +
         5106  +/*
         5107  +** Add all WhereLoop objects for all tables 
         5108  +*/
         5109  +static void whereLoopAddAll(WhereInfo *pWInfo){
         5110  +  Bitmask mExtra = 0;
         5111  +  Bitmask mPrior = 0;
         5112  +  int iTab;
         5113  +  SrcList *pTabList = pWInfo->pTabList;
         5114  +  struct SrcList_item *pItem;
         5115  +  WhereClause *pWC = pWInfo->pWC;
         5116  +  sqlite3 *db = pWInfo->pParse->db;
         5117  +
         5118  +  /* Loop over the tables in the join, from left to right */
         5119  +  for(iTab=0, pItem=pTabList->a; iTab<pTabList->nSrc; iTab++, pItem++){
         5120  +    if( IsVirtual(pItem->pTab) ){
         5121  +      whereLoopAddVirtual(pWInfo, iTab, mExtra);
         5122  +    }else{
         5123  +      whereLoopAddBtree(pWInfo, iTab, mExtra);
         5124  +    }
         5125  +    mPrior |= getMask(pWC->pMaskSet, pItem->iCursor);
         5126  +    if( (pItem->jointype & (JT_LEFT|JT_CROSS))!=0 ){
         5127  +      mExtra = mPrior;
         5128  +    }
         5129  +    if( db->mallocFailed ) break;
         5130  +  }
         5131  +}
  4959   5132   
  4960   5133   
  4961   5134   /*
  4962   5135   ** Generate the beginning of the loop used for WHERE clause processing.
  4963   5136   ** The return value is a pointer to an opaque structure that contains
  4964   5137   ** information needed to terminate the loop.  Later, the calling routine
  4965   5138   ** should invoke sqlite3WhereEnd() with the return value of this function
................................................................................
  5182   5355     ** If it is, then set pDistinct to NULL and WhereInfo.eDistinct to
  5183   5356     ** WHERE_DISTINCT_UNIQUE to tell the caller to ignore the DISTINCT.
  5184   5357     */
  5185   5358     if( pDistinct && isDistinctRedundant(pParse, pTabList, sWBI.pWC, pDistinct) ){
  5186   5359       pDistinct = 0;
  5187   5360       pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
  5188   5361     }
         5362  +
         5363  +  /* Construct the WhereLoop objects */
         5364  +  WHERETRACE(("*** Optimizer Start ***\n"));
         5365  +  whereLoopAddAll(pWInfo);
         5366  +
         5367  +  /* Display all of the WhereLoop objects if wheretrace is enabled */
         5368  +#if defined(SQLITE_DEBUG) \
         5369  +    && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
         5370  +  if( sqlite3WhereTrace ){
         5371  +    WhereLoop *p;
         5372  +    int nb = 2*((nTabList+15)/16);
         5373  +    for(p=pWInfo->pLoops; p; p=p->pNextLoop){
         5374  +      struct SrcList_item *pItem = pTabList->a + p->iTab;
         5375  +       Table *pTab = pItem->pTab;
         5376  +      sqlite3DebugPrintf("%02d.%0*llx", p->iTab, nb, p->prereq);
         5377  +      sqlite3DebugPrintf("     %s",
         5378  +                         pItem->zAlias ? pItem->zAlias : pTab->zName);
         5379  +      if( p->pIndex ){
         5380  +        sqlite3DebugPrintf(" index %s nEq %d", p->pIndex->zName, p->nEq);
         5381  +      }else{
         5382  +        sqlite3DebugPrintf("\n");
         5383  +      }
         5384  +      sqlite3DebugPrintf("     wsFlags %08x OB %d,%d nTerm %d\n",
         5385  +                         p->wsFlags, p->iOb, p->nOb, p->nTerm);
         5386  +      sqlite3DebugPrintf("     cost %.2e + %.2e nOut %.2e\n",
         5387  +                         p->prereq, p->rSetup, p->rRun, p->nOut);
         5388  +    }
         5389  +  }
         5390  +#endif
  5189   5391   
  5190   5392     /* Chose the best index to use for each table in the FROM clause.
  5191   5393     **
  5192   5394     ** This loop fills in the following fields:
  5193   5395     **
  5194   5396     **   pWInfo->a[].pIdx      The index to use for this level of the loop.
  5195   5397     **   pWInfo->a[].wsFlags   WHERE_xxx flags associated with pIdx
................................................................................
  5203   5405     ** clause.
  5204   5406     */
  5205   5407     sWBI.notValid = ~(Bitmask)0;
  5206   5408     sWBI.pOrderBy = pOrderBy;
  5207   5409     sWBI.n = nTabList;
  5208   5410     sWBI.pDistinct = pDistinct;
  5209   5411     andFlags = ~0;
  5210         -  WHERETRACE(("*** Optimizer Start ***\n"));
  5211   5412     for(sWBI.i=iFrom=0, pLevel=pWInfo->a; sWBI.i<nTabList; sWBI.i++, pLevel++){
  5212   5413       WhereCost bestPlan;         /* Most efficient plan seen so far */
  5213   5414       Index *pIdx;                /* Index for FROM table at pTabItem */
  5214   5415       int j;                      /* For looping over FROM tables */
  5215   5416       int bestJ = -1;             /* The value of j */
  5216   5417       Bitmask m;                  /* Bitmask value for j or bestJ */
  5217   5418       int isOptimal;              /* Iterator for optimal/non-optimal search */
  5218   5419       int ckOptimal;              /* Do the optimal scan check */
  5219   5420       int nUnconstrained;         /* Number tables without INDEXED BY */
  5220   5421       Bitmask notIndexed;         /* Mask of tables that cannot use an index */
  5221   5422   
  5222   5423       memset(&bestPlan, 0, sizeof(bestPlan));
  5223   5424       bestPlan.rCost = SQLITE_BIG_DBL;
  5224         -    WHERETRACE(("*** Begin search for loop %d ***\n", sWBI.i));
         5425  +    /*WHERETRACE(("*** Begin search for loop %d ***\n", sWBI.i));*/
  5225   5426   
  5226   5427       /* Loop through the remaining entries in the FROM clause to find the
  5227   5428       ** next nested loop. The loop tests all FROM clause entries
  5228   5429       ** either once or twice. 
  5229   5430       **
  5230   5431       ** The first test is always performed if there are two or more entries
  5231   5432       ** remaining and never performed if there is only one FROM clause entry
................................................................................
  5300   5501           if( (m & sWBI.notValid)==0 ){
  5301   5502             assert( j>iFrom );
  5302   5503             continue;
  5303   5504           }
  5304   5505           sWBI.notReady = (isOptimal ? m : sWBI.notValid);
  5305   5506           if( sWBI.pSrc->pIndex==0 ) nUnconstrained++;
  5306   5507     
  5307         -        WHERETRACE(("   === trying table %d (%s) with isOptimal=%d ===\n",
  5308         -                    j, sWBI.pSrc->pTab->zName, isOptimal));
         5508  +        /*WHERETRACE(("   === trying table %d (%s) with isOptimal=%d ===\n",
         5509  +                    j, sWBI.pSrc->pTab->zName, isOptimal));*/
  5309   5510           assert( sWBI.pSrc->pTab );
  5310   5511   #ifndef SQLITE_OMIT_VIRTUALTABLE
  5311   5512           if( IsVirtual(sWBI.pSrc->pTab) ){
  5312   5513             sWBI.ppIdxInfo = &pWInfo->a[j].pIdxInfo;
  5313   5514             bestVirtualIndex(&sWBI);
  5314   5515           }else 
  5315   5516   #endif
................................................................................
  5331   5532             pWInfo->a[j].rOptCost = sWBI.cost.rCost;
  5332   5533           }else if( ckOptimal ){
  5333   5534             /* If two or more tables have nearly the same outer loop cost, but
  5334   5535             ** very different inner loop (optimal) cost, we want to choose
  5335   5536             ** for the outer loop that table which benefits the least from
  5336   5537             ** being in the inner loop.  The following code scales the 
  5337   5538             ** outer loop cost estimate to accomplish that. */
  5338         -          WHERETRACE(("   scaling cost from %.1f to %.1f\n",
         5539  +          /*WHERETRACE(("   scaling cost from %.1f to %.1f\n",
  5339   5540                         sWBI.cost.rCost,
  5340         -                      sWBI.cost.rCost/pWInfo->a[j].rOptCost));
         5541  +                      sWBI.cost.rCost/pWInfo->a[j].rOptCost));*/
  5341   5542             sWBI.cost.rCost /= pWInfo->a[j].rOptCost;
  5342   5543           }
  5343   5544   
  5344   5545           /* Conditions under which this table becomes the best so far:
  5345   5546           **
  5346   5547           **   (1) The table must not depend on other tables that have not
  5347   5548           **       yet run.  (In other words, it must not depend on tables
................................................................................
  5363   5564           **       is defined by the compareCost() function above. 
  5364   5565           */
  5365   5566           if( (sWBI.cost.used&sWBI.notValid)==0                    /* (1) */
  5366   5567               && (nUnconstrained==0 || sWBI.pSrc->pIndex==0        /* (3) */
  5367   5568                   || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
  5368   5569               && (bestJ<0 || compareCost(&sWBI.cost, &bestPlan))   /* (4) */
  5369   5570           ){
  5370         -          WHERETRACE(("   === table %d (%s) is best so far\n"
         5571  +          /*WHERETRACE(("   === table %d (%s) is best so far\n"
  5371   5572                         "       cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=%08x\n",
  5372   5573                         j, sWBI.pSrc->pTab->zName,
  5373   5574                         sWBI.cost.rCost, sWBI.cost.plan.nRow,
  5374         -                      sWBI.cost.plan.nOBSat, sWBI.cost.plan.wsFlags));
         5575  +                      sWBI.cost.plan.nOBSat, sWBI.cost.plan.wsFlags));*/
  5375   5576             bestPlan = sWBI.cost;
  5376   5577             bestJ = j;
  5377   5578           }
  5378   5579   
  5379   5580           /* In a join like "w JOIN x LEFT JOIN y JOIN z"  make sure that
  5380   5581           ** table y (and not table z) is always the next inner loop inside
  5381   5582           ** of table x. */
................................................................................
  5384   5585       }
  5385   5586       assert( bestJ>=0 );
  5386   5587       assert( sWBI.notValid & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
  5387   5588       assert( bestJ==iFrom || (pTabList->a[iFrom].jointype & JT_LEFT)==0 );
  5388   5589       testcase( bestJ>iFrom && (pTabList->a[iFrom].jointype & JT_CROSS)!=0 );
  5389   5590       testcase( bestJ>iFrom && bestJ<nTabList-1
  5390   5591                             && (pTabList->a[bestJ+1].jointype & JT_LEFT)!=0 );
  5391         -    WHERETRACE(("*** Optimizer selects table %d (%s) for loop %d with:\n"
         5592  +    /*WHERETRACE(("*** Optimizer selects table %d (%s) for loop %d with:\n"
  5392   5593                   "    cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=0x%08x\n",
  5393   5594                   bestJ, pTabList->a[bestJ].pTab->zName,
  5394   5595                   pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow,
  5395         -                bestPlan.plan.nOBSat, bestPlan.plan.wsFlags));
         5596  +                bestPlan.plan.nOBSat, bestPlan.plan.wsFlags));*/
  5396   5597       if( (bestPlan.plan.wsFlags & WHERE_DISTINCT)!=0 ){
  5397   5598         assert( pWInfo->eDistinct==0 );
  5398   5599         pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  5399   5600       }
  5400   5601       andFlags &= bestPlan.plan.wsFlags;
  5401   5602       pLevel->plan = bestPlan.plan;
  5402   5603       pLevel->iTabCur = pTabList->a[bestJ].iCursor;