Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Prevent infinite recursion of in the query planner for some pathological test cases by disabling OR-clause processing upon first recursion. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | or-opt |
| Files: | files | file ages | folders |
| SHA1: |
9fca05eac503d712886a05d03794f76c |
| User & Date: | drh 2011-10-07 14:40:59 |
Context
|
2011-10-07
| ||
| 16:08 | More test cases for the OR optimization. (check-in: 4997d8b8 user: drh tags: or-opt) | |
| 14:40 | Prevent infinite recursion of in the query planner for some pathological test cases by disabling OR-clause processing upon first recursion. (check-in: 9fca05ea user: drh tags: or-opt) | |
| 13:33 | Begin an effort to enhance the query planner to do a better job with OR terms in the WHERE clause. This change allows ANDs outside of the OR to be factored into the OR terms if that is helpful in finding better indices. (check-in: 876bd21a user: drh tags: or-opt) | |
Changes
Changes to src/sqliteInt.h.
1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 |
** and the WhereInfo.wctrlFlags member. */ #define WHERE_ORDERBY_NORMAL 0x0000 /* No-op */ #define WHERE_ORDERBY_MIN 0x0001 /* ORDER BY processing for min() func */ #define WHERE_ORDERBY_MAX 0x0002 /* ORDER BY processing for max() func */ #define WHERE_ONEPASS_DESIRED 0x0004 /* Want to do one-pass UPDATE/DELETE */ #define WHERE_DUPLICATES_OK 0x0008 /* Ok to return a row more than once */ #define WHERE_OMIT_OPEN 0x0010 /* Table cursors are already open */ #define WHERE_OMIT_CLOSE 0x0020 /* Omit close of table & index cursors */ #define WHERE_FORCE_TABLE 0x0040 /* Do not use an index-only search */ #define WHERE_ONETABLE_ONLY 0x0080 /* Only code the 1st table in pTabList */ /* ** The WHERE clause processing routine has two halves. The ** first part does the start of the WHERE loop and the second ** half does the tail of the WHERE loop. An instance of ** this structure is returned by the first half and passed ** into the second half to give some continuity. |
| < | | > |
1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 |
** and the WhereInfo.wctrlFlags member. */ #define WHERE_ORDERBY_NORMAL 0x0000 /* No-op */ #define WHERE_ORDERBY_MIN 0x0001 /* ORDER BY processing for min() func */ #define WHERE_ORDERBY_MAX 0x0002 /* ORDER BY processing for max() func */ #define WHERE_ONEPASS_DESIRED 0x0004 /* Want to do one-pass UPDATE/DELETE */ #define WHERE_DUPLICATES_OK 0x0008 /* Ok to return a row more than once */ #define WHERE_OMIT_OPEN_CLOSE 0x0010 /* Table cursors are already open */ #define WHERE_FORCE_TABLE 0x0020 /* Do not use an index-only search */ #define WHERE_ONETABLE_ONLY 0x0040 /* Only code the 1st table in pTabList */ #define WHERE_AND_ONLY 0x0080 /* Don't use indices for OR terms */ /* ** The WHERE clause processing routine has two halves. The ** first part does the start of the WHERE loop and the second ** half does the tail of the WHERE loop. An instance of ** this structure is returned by the first half and passed ** into the second half to give some continuity. |
Changes to src/where.c.
138 139 140 141 142 143 144 145 146 147 148 149 150 151 ... 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 ... 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 ... 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 .... 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 .... 4334 4335 4336 4337 4338 4339 4340 4341 4342 4343 4344 4345 4346 4347 4348 .... 4644 4645 4646 4647 4648 4649 4650 4651 4652 4653 4654 4655 4656 4657 4658 .... 4972 4973 4974 4975 4976 4977 4978 4979 4980 4981 4982 4983 4984 4985 4986 .... 5152 5153 5154 5155 5156 5157 5158 5159 5160 5161 5162 5163 5164 5165 5166 |
*/
struct WhereClause {
Parse *pParse; /* The parser context */
WhereMaskSet *pMaskSet; /* Mapping of table cursor numbers to bitmasks */
Bitmask vmask; /* Bitmask identifying virtual table cursors */
WhereClause *pOuter; /* Outer conjunction */
u8 op; /* Split operator. TK_AND or TK_OR */
int nTerm; /* Number of terms */
int nSlot; /* Number of entries in a[] */
WhereTerm *a; /* Each a[] describes a term of the WHERE cluase */
#if defined(SQLITE_SMALL_STACK)
WhereTerm aStatic[1]; /* Initial static space for a[] */
#else
WhereTerm aStatic[8]; /* Initial static space for a[] */
................................................................................
/*
** Initialize a preallocated WhereClause structure.
*/
static void whereClauseInit(
WhereClause *pWC, /* The WhereClause to be initialized */
Parse *pParse, /* The parsing context */
WhereMaskSet *pMaskSet /* Mapping from table cursor numbers to bitmasks */
){
pWC->pParse = pParse;
pWC->pMaskSet = pMaskSet;
pWC->pOuter = 0;
pWC->nTerm = 0;
pWC->nSlot = ArraySize(pWC->aStatic);
pWC->a = pWC->aStatic;
pWC->vmask = 0;
}
/* Forward reference */
static void whereClauseClear(WhereClause*);
/*
** Deallocate all memory associated with a WhereOrInfo object.
................................................................................
*/
assert( (pTerm->wtFlags & (TERM_DYNAMIC|TERM_ORINFO|TERM_ANDINFO))==0 );
assert( pExpr->op==TK_OR );
pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocZero(db, sizeof(*pOrInfo));
if( pOrInfo==0 ) return;
pTerm->wtFlags |= TERM_ORINFO;
pOrWc = &pOrInfo->wc;
whereClauseInit(pOrWc, pWC->pParse, pMaskSet);
whereSplit(pOrWc, pExpr, TK_OR);
exprAnalyzeAll(pSrc, pOrWc);
if( db->mallocFailed ) return;
assert( pOrWc->nTerm>=2 );
/*
** Compute the set of tables that might satisfy cases 1 or 2.
................................................................................
WhereTerm *pAndTerm;
int j;
Bitmask b = 0;
pOrTerm->u.pAndInfo = pAndInfo;
pOrTerm->wtFlags |= TERM_ANDINFO;
pOrTerm->eOperator = WO_AND;
pAndWC = &pAndInfo->wc;
whereClauseInit(pAndWC, pWC->pParse, pMaskSet);
whereSplit(pAndWC, pOrTerm->pExpr, TK_AND);
exprAnalyzeAll(pSrc, pAndWC);
pAndWC->pOuter = pWC;
testcase( db->mallocFailed );
if( !db->mallocFailed ){
for(j=0, pAndTerm=pAndWC->a; j<pAndWC->nTerm; j++, pAndTerm++){
assert( pAndTerm->pExpr );
................................................................................
){
#ifndef SQLITE_OMIT_OR_OPTIMIZATION
const int iCur = pSrc->iCursor; /* The cursor of the table to be accessed */
const Bitmask maskSrc = getMask(pWC->pMaskSet, iCur); /* Bitmask for pSrc */
WhereTerm * const pWCEnd = &pWC->a[pWC->nTerm]; /* End of pWC->a[] */
WhereTerm *pTerm; /* A single term of the WHERE clause */
/* No OR-clause optimization allowed if the INDEXED BY or NOT INDEXED clauses
** are used */
if( pSrc->notIndexed || pSrc->pIndex!=0 ){
return;
}
/* Search the WHERE clause terms for a usable WO_OR term. */
for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
if( pTerm->eOperator==WO_OR
&& ((pTerm->prereqAll & ~maskSrc) & notReady)==0
&& (pTerm->u.pOrInfo->indexable & maskSrc)!=0
................................................................................
Expr *pOrExpr = pOrTerm->pExpr;
if( pAndExpr ){
pAndExpr->pLeft = pOrExpr;
pOrExpr = pAndExpr;
}
/* Loop through table entries that match term pOrTerm. */
pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0,
WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE |
WHERE_FORCE_TABLE | WHERE_ONETABLE_ONLY);
if( pSubWInfo ){
explainOneScan(
pParse, pOrTab, &pSubWInfo->a[0], iLevel, pLevel->iFrom, 0
);
if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
................................................................................
** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
if( db->flags & SQLITE_DistinctOpt ) pDistinct = 0;
/* Split the WHERE clause into separate subexpressions where each
** subexpression is separated by an AND operator.
*/
initMaskSet(pMaskSet);
whereClauseInit(pWC, pParse, pMaskSet);
sqlite3ExprCodeConstants(pParse, pWhere);
whereSplit(pWC, pWhere, TK_AND); /* IMP: R-15842-53296 */
/* Special case: a WHERE clause that is constant. Evaluate the
** expression and either jump over all of the code or fall thru.
*/
if( pWhere && (nTabList==0 || sqlite3ExprIsConstantNotJoin(pWhere)) ){
................................................................................
if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
const char *pVTab = (const char *)sqlite3GetVTable(db, pTab);
int iCur = pTabItem->iCursor;
sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB);
}else
#endif
if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
&& (wctrlFlags & WHERE_OMIT_OPEN)==0 ){
int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead;
sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);
testcase( pTab->nCol==BMS-1 );
testcase( pTab->nCol==BMS );
if( !pWInfo->okOnePass && pTab->nCol<BMS ){
Bitmask b = pTabItem->colUsed;
int n = 0;
................................................................................
assert( pWInfo->nLevel==1 || pWInfo->nLevel==pTabList->nSrc );
for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){
struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
Table *pTab = pTabItem->pTab;
assert( pTab!=0 );
if( (pTab->tabFlags & TF_Ephemeral)==0
&& pTab->pSelect==0
&& (pWInfo->wctrlFlags & WHERE_OMIT_CLOSE)==0
){
int ws = pLevel->plan.wsFlags;
if( !pWInfo->okOnePass && (ws & WHERE_IDX_ONLY)==0 ){
sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
}
if( (ws & WHERE_INDEXED)!=0 && (ws & WHERE_TEMP_INDEX)==0 ){
sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
|
> | > > | | | | > > > | | | | |
138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 ... 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 ... 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 ... 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 .... 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 .... 4340 4341 4342 4343 4344 4345 4346 4347 4348 4349 4350 4351 4352 4353 4354 .... 4650 4651 4652 4653 4654 4655 4656 4657 4658 4659 4660 4661 4662 4663 4664 .... 4978 4979 4980 4981 4982 4983 4984 4985 4986 4987 4988 4989 4990 4991 4992 .... 5158 5159 5160 5161 5162 5163 5164 5165 5166 5167 5168 5169 5170 5171 5172 |
*/
struct WhereClause {
Parse *pParse; /* The parser context */
WhereMaskSet *pMaskSet; /* Mapping of table cursor numbers to bitmasks */
Bitmask vmask; /* Bitmask identifying virtual table cursors */
WhereClause *pOuter; /* Outer conjunction */
u8 op; /* Split operator. TK_AND or TK_OR */
u16 wctrlFlags; /* Might include WHERE_AND_ONLY */
int nTerm; /* Number of terms */
int nSlot; /* Number of entries in a[] */
WhereTerm *a; /* Each a[] describes a term of the WHERE cluase */
#if defined(SQLITE_SMALL_STACK)
WhereTerm aStatic[1]; /* Initial static space for a[] */
#else
WhereTerm aStatic[8]; /* Initial static space for a[] */
................................................................................
/*
** Initialize a preallocated WhereClause structure.
*/
static void whereClauseInit(
WhereClause *pWC, /* The WhereClause to be initialized */
Parse *pParse, /* The parsing context */
WhereMaskSet *pMaskSet, /* Mapping from table cursor numbers to bitmasks */
u16 wctrlFlags /* Might include WHERE_AND_ONLY */
){
pWC->pParse = pParse;
pWC->pMaskSet = pMaskSet;
pWC->pOuter = 0;
pWC->nTerm = 0;
pWC->nSlot = ArraySize(pWC->aStatic);
pWC->a = pWC->aStatic;
pWC->vmask = 0;
pWC->wctrlFlags = wctrlFlags;
}
/* Forward reference */
static void whereClauseClear(WhereClause*);
/*
** Deallocate all memory associated with a WhereOrInfo object.
................................................................................
*/
assert( (pTerm->wtFlags & (TERM_DYNAMIC|TERM_ORINFO|TERM_ANDINFO))==0 );
assert( pExpr->op==TK_OR );
pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocZero(db, sizeof(*pOrInfo));
if( pOrInfo==0 ) return;
pTerm->wtFlags |= TERM_ORINFO;
pOrWc = &pOrInfo->wc;
whereClauseInit(pOrWc, pWC->pParse, pMaskSet, pWC->wctrlFlags);
whereSplit(pOrWc, pExpr, TK_OR);
exprAnalyzeAll(pSrc, pOrWc);
if( db->mallocFailed ) return;
assert( pOrWc->nTerm>=2 );
/*
** Compute the set of tables that might satisfy cases 1 or 2.
................................................................................
WhereTerm *pAndTerm;
int j;
Bitmask b = 0;
pOrTerm->u.pAndInfo = pAndInfo;
pOrTerm->wtFlags |= TERM_ANDINFO;
pOrTerm->eOperator = WO_AND;
pAndWC = &pAndInfo->wc;
whereClauseInit(pAndWC, pWC->pParse, pMaskSet, pWC->wctrlFlags);
whereSplit(pAndWC, pOrTerm->pExpr, TK_AND);
exprAnalyzeAll(pSrc, pAndWC);
pAndWC->pOuter = pWC;
testcase( db->mallocFailed );
if( !db->mallocFailed ){
for(j=0, pAndTerm=pAndWC->a; j<pAndWC->nTerm; j++, pAndTerm++){
assert( pAndTerm->pExpr );
................................................................................
){
#ifndef SQLITE_OMIT_OR_OPTIMIZATION
const int iCur = pSrc->iCursor; /* The cursor of the table to be accessed */
const Bitmask maskSrc = getMask(pWC->pMaskSet, iCur); /* Bitmask for pSrc */
WhereTerm * const pWCEnd = &pWC->a[pWC->nTerm]; /* End of pWC->a[] */
WhereTerm *pTerm; /* A single term of the WHERE clause */
/* The OR-clause optimization is disallowed if the INDEXED BY or
** NOT INDEXED clauses are used or if the WHERE_AND_ONLY bit is set. */
if( pSrc->notIndexed || pSrc->pIndex!=0 ){
return;
}
if( pWC->wctrlFlags & WHERE_AND_ONLY ){
return;
}
/* Search the WHERE clause terms for a usable WO_OR term. */
for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
if( pTerm->eOperator==WO_OR
&& ((pTerm->prereqAll & ~maskSrc) & notReady)==0
&& (pTerm->u.pOrInfo->indexable & maskSrc)!=0
................................................................................
Expr *pOrExpr = pOrTerm->pExpr;
if( pAndExpr ){
pAndExpr->pLeft = pOrExpr;
pOrExpr = pAndExpr;
}
/* Loop through table entries that match term pOrTerm. */
pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0,
WHERE_OMIT_OPEN_CLOSE | WHERE_AND_ONLY |
WHERE_FORCE_TABLE | WHERE_ONETABLE_ONLY);
if( pSubWInfo ){
explainOneScan(
pParse, pOrTab, &pSubWInfo->a[0], iLevel, pLevel->iFrom, 0
);
if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
................................................................................
** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
if( db->flags & SQLITE_DistinctOpt ) pDistinct = 0;
/* Split the WHERE clause into separate subexpressions where each
** subexpression is separated by an AND operator.
*/
initMaskSet(pMaskSet);
whereClauseInit(pWC, pParse, pMaskSet, wctrlFlags);
sqlite3ExprCodeConstants(pParse, pWhere);
whereSplit(pWC, pWhere, TK_AND); /* IMP: R-15842-53296 */
/* Special case: a WHERE clause that is constant. Evaluate the
** expression and either jump over all of the code or fall thru.
*/
if( pWhere && (nTabList==0 || sqlite3ExprIsConstantNotJoin(pWhere)) ){
................................................................................
if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
const char *pVTab = (const char *)sqlite3GetVTable(db, pTab);
int iCur = pTabItem->iCursor;
sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB);
}else
#endif
if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
&& (wctrlFlags & WHERE_OMIT_OPEN_CLOSE)==0 ){
int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead;
sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);
testcase( pTab->nCol==BMS-1 );
testcase( pTab->nCol==BMS );
if( !pWInfo->okOnePass && pTab->nCol<BMS ){
Bitmask b = pTabItem->colUsed;
int n = 0;
................................................................................
assert( pWInfo->nLevel==1 || pWInfo->nLevel==pTabList->nSrc );
for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){
struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
Table *pTab = pTabItem->pTab;
assert( pTab!=0 );
if( (pTab->tabFlags & TF_Ephemeral)==0
&& pTab->pSelect==0
&& (pWInfo->wctrlFlags & WHERE_OMIT_OPEN_CLOSE)==0
){
int ws = pLevel->plan.wsFlags;
if( !pWInfo->okOnePass && (ws & WHERE_IDX_ONLY)==0 ){
sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
}
if( (ws & WHERE_INDEXED)!=0 && (ws & WHERE_TEMP_INDEX)==0 ){
sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
|