1898
1933
#endif /* SQLITE_OMIT_VIRTUALTABLE */
1936
** Argument pIdx is a pointer to an index structure that has an array of
1937
** SQLITE_INDEX_SAMPLES evenly spaced samples of the first indexed column
1938
** stored in Index.aSample. The domain of values stored in said column
1939
** may be thought of as divided into (SQLITE_INDEX_SAMPLES+1) regions.
1940
** Region 0 contains all values smaller than the first sample value. Region
1941
** 1 contains values larger than or equal to the value of the first sample,
1942
** but smaller than the value of the second. And so on.
1944
** If successful, this function determines which of the regions value
1945
** pVal lies in, sets *piRegion to the region index (a value between 0
1946
** and SQLITE_INDEX_SAMPLES+1, inclusive) and returns SQLITE_OK.
1947
** Or, if an OOM occurs while converting text values between encodings,
1948
** SQLITE_NOMEM is returned and *piRegion is undefined.
1950
#ifdef SQLITE_ENABLE_STAT2
1951
static int whereRangeRegion(
1952
Parse *pParse, /* Database connection */
1953
Index *pIdx, /* Index to consider domain of */
1954
sqlite3_value *pVal, /* Value to consider */
1955
int *piRegion /* OUT: Region of domain in which value lies */
1958
IndexSample *aSample = pIdx->aSample;
1960
int eType = sqlite3_value_type(pVal);
1962
if( eType==SQLITE_INTEGER || eType==SQLITE_FLOAT ){
1963
double r = sqlite3_value_double(pVal);
1964
for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
1965
if( aSample[i].eType==SQLITE_NULL ) continue;
1966
if( aSample[i].eType>=SQLITE_TEXT || aSample[i].u.r>r ) break;
1969
sqlite3 *db = pParse->db;
1974
/* pVal comes from sqlite3ValueFromExpr() so the type cannot be NULL */
1975
assert( eType==SQLITE_TEXT || eType==SQLITE_BLOB );
1977
if( eType==SQLITE_BLOB ){
1978
z = (const u8 *)sqlite3_value_blob(pVal);
1979
pColl = db->pDfltColl;
1980
assert( pColl->enc==SQLITE_UTF8 );
1982
pColl = sqlite3GetCollSeq(db, SQLITE_UTF8, 0, *pIdx->azColl);
1984
sqlite3ErrorMsg(pParse, "no such collation sequence: %s",
1986
return SQLITE_ERROR;
1988
z = (const u8 *)sqlite3ValueText(pVal, pColl->enc);
1990
return SQLITE_NOMEM;
1992
assert( z && pColl && pColl->xCmp );
1994
n = sqlite3ValueBytes(pVal, pColl->enc);
1996
for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
1998
int eSampletype = aSample[i].eType;
1999
if( eSampletype==SQLITE_NULL || eSampletype<eType ) continue;
2000
if( (eSampletype!=eType) ) break;
2001
#ifndef SQLITE_OMIT_UTF16
2002
if( pColl->enc!=SQLITE_UTF8 ){
2004
char *zSample = sqlite3Utf8to16(
2005
db, pColl->enc, aSample[i].u.z, aSample[i].nByte, &nSample
2008
assert( db->mallocFailed );
2009
return SQLITE_NOMEM;
2011
r = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);
2012
sqlite3DbFree(db, zSample);
2016
r = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
2022
assert( i>=0 && i<=SQLITE_INDEX_SAMPLES );
2027
#endif /* #ifdef SQLITE_ENABLE_STAT2 */
2030
** If expression pExpr represents a literal value, set *pp to point to
2031
** an sqlite3_value structure containing the same value, with affinity
2032
** aff applied to it, before returning. It is the responsibility of the
2033
** caller to eventually release this structure by passing it to
2034
** sqlite3ValueFree().
2036
** If the current parse is a recompile (sqlite3Reprepare()) and pExpr
2037
** is an SQL variable that currently has a non-NULL value bound to it,
2038
** create an sqlite3_value structure containing this value, again with
2039
** affinity aff applied to it, instead.
2041
** If neither of the above apply, set *pp to NULL.
2043
** If an error occurs, return an error code. Otherwise, SQLITE_OK.
2045
#ifdef SQLITE_ENABLE_STAT2
2046
static int valueFromExpr(
2052
/* The evalConstExpr() function will have already converted any TK_VARIABLE
2053
** expression involved in an comparison into a TK_REGISTER. */
2054
assert( pExpr->op!=TK_VARIABLE );
2055
if( pExpr->op==TK_REGISTER && pExpr->op2==TK_VARIABLE ){
2056
int iVar = pExpr->iColumn;
2057
sqlite3VdbeSetVarmask(pParse->pVdbe, iVar);
2058
*pp = sqlite3VdbeGetValue(pParse->pReprepare, iVar, aff);
2061
return sqlite3ValueFromExpr(pParse->db, pExpr, SQLITE_UTF8, aff, pp);
2066
** This function is used to estimate the number of rows that will be visited
2067
** by scanning an index for a range of values. The range may have an upper
2068
** bound, a lower bound, or both. The WHERE clause terms that set the upper
2069
** and lower bounds are represented by pLower and pUpper respectively. For
2070
** example, assuming that index p is on t1(a):
2072
** ... FROM t1 WHERE a > ? AND a < ? ...
2077
** If either of the upper or lower bound is not present, then NULL is passed in
2078
** place of the corresponding WhereTerm.
2080
** The nEq parameter is passed the index of the index column subject to the
2081
** range constraint. Or, equivalently, the number of equality constraints
2082
** optimized by the proposed index scan. For example, assuming index p is
2083
** on t1(a, b), and the SQL query is:
2085
** ... FROM t1 WHERE a = ? AND b > ? AND b < ? ...
2087
** then nEq should be passed the value 1 (as the range restricted column,
2088
** b, is the second left-most column of the index). Or, if the query is:
2090
** ... FROM t1 WHERE a > ? AND a < ? ...
2092
** then nEq should be passed 0.
2094
** The returned value is an integer between 1 and 100, inclusive. A return
2095
** value of 1 indicates that the proposed range scan is expected to visit
2096
** approximately 1/100th (1%) of the rows selected by the nEq equality
2097
** constraints (if any). A return value of 100 indicates that it is expected
2098
** that the range scan will visit every row (100%) selected by the equality
2101
** In the absence of sqlite_stat2 ANALYZE data, each range inequality
2102
** reduces the search space by 2/3rds. Hence a single constraint (x>?)
2103
** results in a return of 33 and a range constraint (x>? AND x<?) results
2104
** in a return of 11.
2106
static int whereRangeScanEst(
2107
Parse *pParse, /* Parsing & code generating context */
2108
Index *p, /* The index containing the range-compared column; "x" */
2109
int nEq, /* index into p->aCol[] of the range-compared column */
2110
WhereTerm *pLower, /* Lower bound on the range. ex: "x>123" Might be NULL */
2111
WhereTerm *pUpper, /* Upper bound on the range. ex: "x<455" Might be NULL */
2112
int *piEst /* OUT: Return value */
2116
#ifdef SQLITE_ENABLE_STAT2
2118
if( nEq==0 && p->aSample ){
2119
sqlite3_value *pLowerVal = 0;
2120
sqlite3_value *pUpperVal = 0;
2123
int iUpper = SQLITE_INDEX_SAMPLES;
2124
u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;
2127
Expr *pExpr = pLower->pExpr->pRight;
2128
rc = valueFromExpr(pParse, pExpr, aff, &pLowerVal);
2130
if( rc==SQLITE_OK && pUpper ){
2131
Expr *pExpr = pUpper->pExpr->pRight;
2132
rc = valueFromExpr(pParse, pExpr, aff, &pUpperVal);
2135
if( rc!=SQLITE_OK || (pLowerVal==0 && pUpperVal==0) ){
2136
sqlite3ValueFree(pLowerVal);
2137
sqlite3ValueFree(pUpperVal);
2138
goto range_est_fallback;
2139
}else if( pLowerVal==0 ){
2140
rc = whereRangeRegion(pParse, p, pUpperVal, &iUpper);
2141
if( pLower ) iLower = iUpper/2;
2142
}else if( pUpperVal==0 ){
2143
rc = whereRangeRegion(pParse, p, pLowerVal, &iLower);
2144
if( pUpper ) iUpper = (iLower + SQLITE_INDEX_SAMPLES + 1)/2;
2146
rc = whereRangeRegion(pParse, p, pUpperVal, &iUpper);
2147
if( rc==SQLITE_OK ){
2148
rc = whereRangeRegion(pParse, p, pLowerVal, &iLower);
2152
iEst = iUpper - iLower;
2153
testcase( iEst==SQLITE_INDEX_SAMPLES );
2154
assert( iEst<=SQLITE_INDEX_SAMPLES );
2159
sqlite3ValueFree(pLowerVal);
2160
sqlite3ValueFree(pUpperVal);
2161
*piEst = (iEst * 100)/SQLITE_INDEX_SAMPLES;
2166
UNUSED_PARAMETER(pParse);
2167
UNUSED_PARAMETER(p);
2168
UNUSED_PARAMETER(nEq);
2170
assert( pLower || pUpper );
2171
if( pLower && pUpper ){
1901
2181
** Find the query plan for accessing a particular table. Write the
1902
2182
** best query plan and its cost into the WhereCost object supplied as the
1903
2183
** last parameter.
1933
2213
ExprList *pOrderBy, /* The ORDER BY clause */
1934
2214
WhereCost *pCost /* Lowest cost query plan */
1936
WhereTerm *pTerm; /* A single term of the WHERE clause */
1937
2216
int iCur = pSrc->iCursor; /* The cursor of the table to be accessed */
1938
2217
Index *pProbe; /* An index we are evaluating */
1939
int rev; /* True to scan in reverse order */
1940
int wsFlags; /* Flags associated with pProbe */
1941
int nEq; /* Number of == or IN constraints */
1942
int eqTermMask; /* Mask of valid equality operators */
1943
double cost; /* Cost of using pProbe */
1944
double nRow; /* Estimated number of rows in result set */
1945
int i; /* Loop counter */
1947
WHERETRACE(("bestIndex: tbl=%s notReady=%llx\n", pSrc->pTab->zName,notReady));
1948
pProbe = pSrc->pTab->pIndex;
1949
if( pSrc->notIndexed ){
1953
/* If the table has no indices and there are no terms in the where
1954
** clause that refer to the ROWID, then we will never be able to do
1955
** anything other than a full table scan on this table. We might as
1956
** well put it first in the join order. That way, perhaps it can be
1957
** referenced by other tables in the join.
2218
Index *pIdx; /* Copy of pProbe, or zero for IPK index */
2219
int eqTermMask; /* Current mask of valid equality operators */
2220
int idxEqTermMask; /* Index mask of valid equality operators */
2221
Index sPk; /* A fake index object for the primary key */
2222
unsigned int aiRowEstPk[2]; /* The aiRowEst[] value for the sPk index */
2223
int aiColumnPk = -1; /* The aColumn[] value for the sPk index */
2224
int wsFlagMask; /* Allowed flags in pCost->plan.wsFlag */
2226
/* Initialize the cost to a worst-case value */
1959
2227
memset(pCost, 0, sizeof(*pCost));
1961
findTerm(pWC, iCur, -1, 0, WO_EQ|WO_IN|WO_LT|WO_LE|WO_GT|WO_GE,0)==0 &&
1962
(pOrderBy==0 || !sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev)) ){
1963
if( pParse->db->flags & SQLITE_ReverseOrder ){
1964
/* For application testing, randomly reverse the output order for
1965
** SELECT statements that omit the ORDER BY clause. This will help
1966
** to find cases where
1968
pCost->plan.wsFlags |= WHERE_REVERSE;
1972
2228
pCost->rCost = SQLITE_BIG_DBL;
1974
/* Check for a rowid=EXPR or rowid IN (...) constraints. If there was
1975
** an INDEXED BY clause attached to this table, skip this step.
1977
if( !pSrc->pIndex ){
1978
pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
1981
pCost->plan.wsFlags = WHERE_ROWID_EQ;
1982
if( pTerm->eOperator & WO_EQ ){
1983
/* Rowid== is always the best pick. Look no further. Because only
1984
** a single row is generated, output is always in sorted order */
1985
pCost->plan.wsFlags = WHERE_ROWID_EQ | WHERE_UNIQUE;
1986
pCost->plan.nEq = 1;
1987
WHERETRACE(("... best is rowid\n"));
1991
}else if( !ExprHasProperty((pExpr = pTerm->pExpr), EP_xIsSelect)
1994
/* Rowid IN (LIST): cost is NlogN where N is the number of list
1996
pCost->rCost = pCost->nRow = pExpr->x.pList->nExpr;
1997
pCost->rCost *= estLog(pCost->rCost);
1999
/* Rowid IN (SELECT): cost is NlogN where N is the number of rows
2000
** in the result of the inner select. We have no way to estimate
2001
** that value so make a wild guess. */
2005
WHERETRACE(("... rowid IN cost: %.9g\n", pCost->rCost));
2008
/* Estimate the cost of a table scan. If we do not know how many
2009
** entries are in the table, use 1 million as a guess.
2011
cost = pProbe ? pProbe->aiRowEst[0] : 1000000;
2012
WHERETRACE(("... table scan base cost: %.9g\n", cost));
2013
wsFlags = WHERE_ROWID_RANGE;
2015
/* Check for constraints on a range of rowids in a table scan.
2017
pTerm = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE|WO_GT|WO_GE, 0);
2019
if( findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0) ){
2020
wsFlags |= WHERE_TOP_LIMIT;
2021
cost /= 3; /* Guess that rowid<EXPR eliminates two-thirds of rows */
2023
if( findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0) ){
2024
wsFlags |= WHERE_BTM_LIMIT;
2025
cost /= 3; /* Guess that rowid>EXPR eliminates two-thirds of rows */
2027
WHERETRACE(("... rowid range reduces cost to %.9g\n", cost));
2033
/* If the table scan does not satisfy the ORDER BY clause, increase
2034
** the cost by NlogN to cover the expense of sorting. */
2036
if( sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev) ){
2037
wsFlags |= WHERE_ORDERBY|WHERE_ROWID_RANGE;
2039
wsFlags |= WHERE_REVERSE;
2042
cost += cost*estLog(cost);
2043
WHERETRACE(("... sorting increases cost to %.9g\n", cost));
2045
}else if( pParse->db->flags & SQLITE_ReverseOrder ){
2046
/* For application testing, randomly reverse the output order for
2047
** SELECT statements that omit the ORDER BY clause. This will help
2048
** to find cases where
2050
wsFlags |= WHERE_REVERSE;
2053
/* Remember this case if it is the best so far */
2054
if( cost<pCost->rCost ){
2055
pCost->rCost = cost;
2057
pCost->plan.wsFlags = wsFlags;
2061
bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
2063
2230
/* If the pSrc table is the right table of a LEFT JOIN then we may not
2064
2231
** use an index to satisfy IS NULL constraints on that table. This is
2065
2232
** because columns might end up being NULL if the table does not match -
2066
2233
** a circumstance which the index cannot help us discover. Ticket #2177.
2068
if( (pSrc->jointype & JT_LEFT)!=0 ){
2235
if( pSrc->jointype & JT_LEFT ){
2236
idxEqTermMask = WO_EQ|WO_IN;
2238
idxEqTermMask = WO_EQ|WO_IN|WO_ISNULL;
2242
/* An INDEXED BY clause specifies a particular index to use */
2243
pIdx = pProbe = pSrc->pIndex;
2244
wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE);
2245
eqTermMask = idxEqTermMask;
2247
/* There is no INDEXED BY clause. Create a fake Index object to
2248
** represent the primary key */
2249
Index *pFirst; /* Any other index on the table */
2250
memset(&sPk, 0, sizeof(Index));
2252
sPk.aiColumn = &aiColumnPk;
2253
sPk.aiRowEst = aiRowEstPk;
2255
sPk.onError = OE_Replace;
2256
sPk.pTable = pSrc->pTab;
2257
pFirst = pSrc->pTab->pIndex;
2258
if( pSrc->notIndexed==0 ){
2261
/* The aiRowEstPk[0] is an estimate of the total number of rows in the
2262
** table. Get this information from the ANALYZE information if it is
2263
** available. If not available, assume the table 1 million rows in size.
2266
assert( pFirst->aiRowEst!=0 ); /* Allocated together with pFirst */
2267
aiRowEstPk[0] = pFirst->aiRowEst[0];
2269
aiRowEstPk[0] = 1000000;
2273
WHERE_COLUMN_IN|WHERE_COLUMN_EQ|WHERE_COLUMN_NULL|WHERE_COLUMN_RANGE
2069
2275
eqTermMask = WO_EQ|WO_IN;
2071
eqTermMask = WO_EQ|WO_IN|WO_ISNULL;
2074
/* Look at each index.
2279
/* Loop over all indices looking for the best one to use
2077
pProbe = pSrc->pIndex;
2079
for(; pProbe; pProbe=(pSrc->pIndex ? 0 : pProbe->pNext)){
2080
double inMultiplier = 1; /* Number of equality look-ups needed */
2081
int inMultIsEst = 0; /* True if inMultiplier is an estimate */
2083
WHERETRACE(("... index %s:\n", pProbe->zName));
2085
/* Count the number of columns in the index that are satisfied
2086
** by x=EXPR or x IS NULL constraints or x IN (...) constraints.
2087
** For a term of the form x=EXPR or x IS NULL we only have to do
2088
** a single binary search. But for x IN (...) we have to do a
2089
** number of binary searched
2090
** equal to the number of entries on the RHS of the IN operator.
2091
** The inMultipler variable with try to estimate the number of
2092
** binary searches needed.
2281
for(; pProbe; pIdx=pProbe=pProbe->pNext){
2282
const unsigned int * const aiRowEst = pProbe->aiRowEst;
2283
double cost; /* Cost of using pProbe */
2284
double nRow; /* Estimated number of rows in result set */
2285
int rev; /* True to scan in reverse order */
2289
/* The following variables are populated based on the properties of
2290
** scan being evaluated. They are then used to determine the expected
2291
** cost and number of rows returned.
2294
** Number of equality terms that can be implemented using the index.
2297
** The "in-multiplier". This is an estimate of how many seek operations
2298
** SQLite must perform on the index in question. For example, if the
2301
** WHERE a IN (1, 2, 3) AND b IN (4, 5, 6)
2303
** SQLite must perform 9 lookups on an index on (a, b), so nInMul is
2304
** set to 9. Given the same schema and either of the following WHERE
2310
** nInMul is set to 1.
2312
** If there exists a WHERE term of the form "x IN (SELECT ...)", then
2313
** the sub-select is assumed to return 25 rows for the purposes of
2314
** determining nInMul.
2317
** Set to true if there was at least one "x IN (SELECT ...)" term used
2318
** in determining the value of nInMul.
2321
** An estimate on the amount of the table that must be searched. A
2322
** value of 100 means the entire table is searched. Range constraints
2323
** might reduce this to a value less than 100 to indicate that only
2324
** a fraction of the table needs searching. In the absence of
2325
** sqlite_stat2 ANALYZE data, a single inequality reduces the search
2326
** space to 1/3rd its original size. So an x>? constraint reduces
2327
** nBound to 33. Two constraints (x>? AND x<?) reduce nBound to 11.
2330
** Boolean. True if there is an ORDER BY clause that will require an
2331
** external sort (i.e. scanning the index being evaluated will not
2332
** correctly order records).
2335
** Boolean. True if for each index entry visited a lookup on the
2336
** corresponding table b-tree is required. This is always false
2337
** for the rowid index. For other indexes, it is true unless all the
2338
** columns of the table used by the SELECT statement are present in
2339
** the index (such an index is sometimes described as a covering index).
2340
** For example, given the index on (a, b), the second of the following
2341
** two queries requires table b-tree lookups, but the first does not.
2343
** SELECT a, b FROM tbl WHERE a = 1;
2344
** SELECT a, b, c FROM tbl WHERE a = 1;
2095
for(i=0; i<pProbe->nColumn; i++){
2096
int j = pProbe->aiColumn[i];
2097
pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pProbe);
2353
/* Determine the values of nEq and nInMul */
2354
for(nEq=0; nEq<pProbe->nColumn; nEq++){
2355
WhereTerm *pTerm; /* A single term of the WHERE clause */
2356
int j = pProbe->aiColumn[nEq];
2357
pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pIdx);
2098
2358
if( pTerm==0 ) break;
2099
wsFlags |= WHERE_COLUMN_EQ;
2359
wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
2100
2360
if( pTerm->eOperator & WO_IN ){
2101
2361
Expr *pExpr = pTerm->pExpr;
2102
2362
wsFlags |= WHERE_COLUMN_IN;
2103
2363
if( ExprHasProperty(pExpr, EP_xIsSelect) ){
2106
2366
}else if( pExpr->x.pList ){
2107
inMultiplier *= pExpr->x.pList->nExpr + 1;
2367
nInMul *= pExpr->x.pList->nExpr + 1;
2109
2369
}else if( pTerm->eOperator & WO_ISNULL ){
2110
2370
wsFlags |= WHERE_COLUMN_NULL;
2113
nRow = pProbe->aiRowEst[i] * inMultiplier;
2114
/* If inMultiplier is an estimate and that estimate results in an
2115
** nRow it that is more than half number of rows in the table,
2116
** then reduce inMultipler */
2117
if( inMultIsEst && nRow*2 > pProbe->aiRowEst[0] ){
2118
nRow = pProbe->aiRowEst[0]/2;
2119
inMultiplier = nRow/pProbe->aiRowEst[i];
2121
cost = nRow + inMultiplier*estLog(pProbe->aiRowEst[0]);
2123
if( pProbe->onError!=OE_None && nEq==pProbe->nColumn ){
2372
used |= pTerm->prereqRight;
2375
/* Determine the value of nBound. */
2376
if( nEq<pProbe->nColumn ){
2377
int j = pProbe->aiColumn[nEq];
2378
if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
2379
WhereTerm *pTop = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pIdx);
2380
WhereTerm *pBtm = findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pIdx);
2381
whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &nBound);
2383
wsFlags |= WHERE_TOP_LIMIT;
2384
used |= pTop->prereqRight;
2387
wsFlags |= WHERE_BTM_LIMIT;
2388
used |= pBtm->prereqRight;
2390
wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE);
2392
}else if( pProbe->onError!=OE_None ){
2124
2393
testcase( wsFlags & WHERE_COLUMN_IN );
2125
2394
testcase( wsFlags & WHERE_COLUMN_NULL );
2126
2395
if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
2127
2396
wsFlags |= WHERE_UNIQUE;
2130
WHERETRACE(("...... nEq=%d inMult=%.9g nRow=%.9g cost=%.9g\n",
2131
nEq, inMultiplier, nRow, cost));
2133
/* Look for range constraints. Assume that each range constraint
2134
** makes the search space 1/3rd smaller.
2136
if( nEq<pProbe->nColumn ){
2137
int j = pProbe->aiColumn[nEq];
2138
pTerm = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe);
2140
wsFlags |= WHERE_COLUMN_RANGE;
2141
if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pProbe) ){
2142
wsFlags |= WHERE_TOP_LIMIT;
2146
if( findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pProbe) ){
2147
wsFlags |= WHERE_BTM_LIMIT;
2151
WHERETRACE(("...... range reduces nRow to %.9g and cost to %.9g\n",
2156
/* Add the additional cost of sorting if that is a factor.
2400
/* If there is an ORDER BY clause and the index being considered will
2401
** naturally scan rows in the required order, set the appropriate flags
2402
** in wsFlags. Otherwise, if there is an ORDER BY clause but the index
2403
** will scan rows in a different order, set the bSort variable. */
2158
2404
if( pOrderBy ){
2159
2405
if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0
2160
&& isSortingIndex(pParse,pWC->pMaskSet,pProbe,iCur,pOrderBy,nEq,&rev)
2406
&& isSortingIndex(pParse,pWC->pMaskSet,pProbe,iCur,pOrderBy,nEq,&rev)
2163
wsFlags = WHERE_COLUMN_RANGE;
2165
wsFlags |= WHERE_ORDERBY;
2167
wsFlags |= WHERE_REVERSE;
2408
wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_ORDERBY;
2409
wsFlags |= (rev ? WHERE_REVERSE : 0);
2170
cost += cost*estLog(cost);
2171
WHERETRACE(("...... orderby increases cost to %.9g\n", cost));
2173
}else if( wsFlags!=0 && (pParse->db->flags & SQLITE_ReverseOrder)!=0 ){
2174
/* For application testing, randomly reverse the output order for
2175
** SELECT statements that omit the ORDER BY clause. This will help
2176
** to find cases where
2178
wsFlags |= WHERE_REVERSE;
2181
/* Check to see if we can get away with using just the index without
2182
** ever reading the table. If that is the case, then halve the
2183
** cost of this index.
2185
if( wsFlags && pSrc->colUsed < (((Bitmask)1)<<(BMS-1)) ){
2415
/* If currently calculating the cost of using an index (not the IPK
2416
** index), determine if all required column data may be obtained without
2417
** seeking to entries in the main table (i.e. if the index is a covering
2418
** index for this query). If it is, set the WHERE_IDX_ONLY flag in
2419
** wsFlags. Otherwise, set the bLookup variable to true. */
2420
if( pIdx && wsFlags ){
2186
2421
Bitmask m = pSrc->colUsed;
2188
for(j=0; j<pProbe->nColumn; j++){
2189
int x = pProbe->aiColumn[j];
2423
for(j=0; j<pIdx->nColumn; j++){
2424
int x = pIdx->aiColumn[j];
2191
2426
m &= ~(((Bitmask)1)<<x);
2195
2430
wsFlags |= WHERE_IDX_ONLY;
2197
WHERETRACE(("...... idx-only reduces cost to %.9g\n", cost));
2201
/* If this index has achieved the lowest cost so far, then use it.
2203
if( wsFlags!=0 && cost < pCost->rCost ){
2436
/**** Begin adding up the cost of using this index (Needs improvements)
2438
** Estimate the number of rows of output. For an IN operator,
2439
** do not let the estimate exceed half the rows in the table.
2441
nRow = (double)(aiRowEst[nEq] * nInMul);
2442
if( bInEst && nRow*2>aiRowEst[0] ){
2443
nRow = aiRowEst[0]/2;
2444
nInMul = (int)(nRow / aiRowEst[nEq]);
2447
/* Assume constant cost to access a row and logarithmic cost to
2448
** do a binary search. Hence, the initial cost is the number of output
2449
** rows plus log2(table-size) times the number of binary searches.
2451
cost = nRow + nInMul*estLog(aiRowEst[0]);
2453
/* Adjust the number of rows and the cost downward to reflect rows
2454
** that are excluded by range constraints.
2456
nRow = (nRow * (double)nBound) / (double)100;
2457
cost = (cost * (double)nBound) / (double)100;
2459
/* Add in the estimated cost of sorting the result
2462
cost += cost*estLog(cost);
2465
/* If all information can be taken directly from the index, we avoid
2466
** doing table lookups. This reduces the cost by half. (Not really -
2467
** this needs to be fixed.)
2469
if( pIdx && bLookup==0 ){
2472
/**** Cost of using this index has now been computed ****/
2475
"tbl=%s idx=%s nEq=%d nInMul=%d nBound=%d bSort=%d bLookup=%d"
2476
" wsFlags=%d (nRow=%.2f cost=%.2f)\n",
2477
pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"),
2478
nEq, nInMul, nBound, bSort, bLookup, wsFlags, nRow, cost
2481
/* If this index is the best we have seen so far, then record this
2482
** index and its cost in the pCost structure.
2484
if( (!pIdx || wsFlags) && cost<pCost->rCost ){
2204
2485
pCost->rCost = cost;
2205
2486
pCost->nRow = nRow;
2206
pCost->plan.wsFlags = wsFlags;
2488
pCost->plan.wsFlags = (wsFlags&wsFlagMask);
2207
2489
pCost->plan.nEq = nEq;
2208
assert( pCost->plan.wsFlags & WHERE_INDEXED );
2209
pCost->plan.u.pIdx = pProbe;
2490
pCost->plan.u.pIdx = pIdx;
2213
/* Report the best result
2493
/* If there was an INDEXED BY clause, then only that one index is
2495
if( pSrc->pIndex ) break;
2497
/* Reset masks for the next index in the loop */
2498
wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE);
2499
eqTermMask = idxEqTermMask;
2502
/* If there is no ORDER BY clause and the SQLITE_ReverseOrder flag
2503
** is set, then reverse the order that the index will be scanned
2504
** in. This is used for application testing, to help find cases
2505
** where application behaviour depends on the (undefined) order that
2506
** SQLite outputs rows in in the absence of an ORDER BY clause. */
2507
if( !pOrderBy && pParse->db->flags & SQLITE_ReverseOrder ){
2508
pCost->plan.wsFlags |= WHERE_REVERSE;
2511
assert( pOrderBy || (pCost->plan.wsFlags&WHERE_ORDERBY)==0 );
2512
assert( pCost->plan.u.pIdx==0 || (pCost->plan.wsFlags&WHERE_ROWID_EQ)==0 );
2513
assert( pSrc->pIndex==0
2514
|| pCost->plan.u.pIdx==0
2515
|| pCost->plan.u.pIdx==pSrc->pIndex
2518
WHERETRACE(("best index is: %s\n",
2519
(pCost->plan.u.pIdx ? pCost->plan.u.pIdx->zName : "ipk")
2522
bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
2215
2523
pCost->plan.wsFlags |= eqTermMask;
2216
WHERETRACE(("best index is %s, cost=%.9g, nrow=%.9g, wsFlags=%x, nEq=%d\n",
2217
(pCost->plan.wsFlags & WHERE_INDEXED)!=0 ?
2218
pCost->plan.u.pIdx->zName : "(none)", pCost->nRow,
2219
pCost->rCost, pCost->plan.wsFlags, pCost->plan.nEq));
3270
3658
WhereCost bestPlan; /* Most efficient plan seen so far */
3271
3659
Index *pIdx; /* Index for FROM table at pTabItem */
3272
3660
int j; /* For looping over FROM tables */
3273
int bestJ = 0; /* The value of j */
3661
int bestJ = -1; /* The value of j */
3274
3662
Bitmask m; /* Bitmask value for j or bestJ */
3275
int once = 0; /* True when first table is seen */
3663
int isOptimal; /* Iterator for optimal/non-optimal search */
3277
3665
memset(&bestPlan, 0, sizeof(bestPlan));
3278
3666
bestPlan.rCost = SQLITE_BIG_DBL;
3279
for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
3280
int doNotReorder; /* True if this table should not be reordered */
3281
WhereCost sCost; /* Cost information from best[Virtual]Index() */
3282
ExprList *pOrderBy; /* ORDER BY clause for index to optimize */
3284
doNotReorder = (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
3285
if( once && doNotReorder ) break;
3286
m = getMask(pMaskSet, pTabItem->iCursor);
3287
if( (m & notReady)==0 ){
3288
if( j==iFrom ) iFrom++;
3291
pOrderBy = ((i==0 && ppOrderBy )?*ppOrderBy:0);
3293
assert( pTabItem->pTab );
3668
/* Loop through the remaining entries in the FROM clause to find the
3669
** next nested loop. The FROM clause entries may be iterated through
3670
** either once or twice.
3672
** The first iteration, which is always performed, searches for the
3673
** FROM clause entry that permits the lowest-cost, "optimal" scan. In
3674
** this context an optimal scan is one that uses the same strategy
3675
** for the given FROM clause entry as would be selected if the entry
3676
** were used as the innermost nested loop. In other words, a table
3677
** is chosen such that the cost of running that table cannot be reduced
3678
** by waiting for other tables to run first.
3680
** The second iteration is only performed if no optimal scan strategies
3681
** were found by the first. This iteration is used to search for the
3682
** lowest cost scan overall.
3684
** Previous versions of SQLite performed only the second iteration -
3685
** the next outermost loop was always that with the lowest overall
3686
** cost. However, this meant that SQLite could select the wrong plan
3687
** for scripts such as the following:
3689
** CREATE TABLE t1(a, b);
3690
** CREATE TABLE t2(c, d);
3691
** SELECT * FROM t2, t1 WHERE t2.rowid = t1.a;
3693
** The best strategy is to iterate through table t1 first. However it
3694
** is not possible to determine this with a simple greedy algorithm.
3695
** However, since the cost of a linear scan through table t2 is the same
3696
** as the cost of a linear scan through table t1, a simple greedy
3697
** algorithm may choose to use t2 for the outer loop, which is a much
3698
** costlier approach.
3700
for(isOptimal=1; isOptimal>=0 && bestJ<0; isOptimal--){
3701
Bitmask mask = (isOptimal ? 0 : notReady);
3702
assert( (pTabList->nSrc-iFrom)>1 || isOptimal );
3703
for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
3704
int doNotReorder; /* True if this table should not be reordered */
3705
WhereCost sCost; /* Cost information from best[Virtual]Index() */
3706
ExprList *pOrderBy; /* ORDER BY clause for index to optimize */
3708
doNotReorder = (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
3709
if( j!=iFrom && doNotReorder ) break;
3710
m = getMask(pMaskSet, pTabItem->iCursor);
3711
if( (m & notReady)==0 ){
3712
if( j==iFrom ) iFrom++;
3715
pOrderBy = ((i==0 && ppOrderBy )?*ppOrderBy:0);
3717
assert( pTabItem->pTab );
3294
3718
#ifndef SQLITE_OMIT_VIRTUALTABLE
3295
if( IsVirtual(pTabItem->pTab) ){
3296
sqlite3_index_info **pp = &pWInfo->a[j].pIdxInfo;
3297
bestVirtualIndex(pParse, pWC, pTabItem, notReady, pOrderBy, &sCost, pp);
3719
if( IsVirtual(pTabItem->pTab) ){
3720
sqlite3_index_info **pp = &pWInfo->a[j].pIdxInfo;
3721
bestVirtualIndex(pParse, pWC, pTabItem, mask, pOrderBy, &sCost, pp);
3301
bestBtreeIndex(pParse, pWC, pTabItem, notReady, pOrderBy, &sCost);
3303
if( once==0 || sCost.rCost<bestPlan.rCost ){
3308
if( doNotReorder ) break;
3725
bestBtreeIndex(pParse, pWC, pTabItem, mask, pOrderBy, &sCost);
3727
assert( isOptimal || (sCost.used¬Ready)==0 );
3729
if( (sCost.used¬Ready)==0
3730
&& (j==iFrom || sCost.rCost<bestPlan.rCost)
3735
if( doNotReorder ) break;
3311
3739
assert( notReady & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
3312
3740
WHERETRACE(("*** Optimizer selects table %d for loop %d\n", bestJ,
3313
3741
pLevel-pWInfo->a));
added
removed
src/where.c
