Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -767,10 +767,83 @@ static void markTermAsChild(WhereClause *pWC, int iChild, int iParent){ pWC->a[iChild].iParent = iParent; pWC->a[iChild].truthProb = pWC->a[iParent].truthProb; pWC->a[iParent].nChild++; } + +/* +** Return the N-th AND-connected subterm of pTerm. Or if pTerm is not +** a conjunction, then return just pTerm when N==0. If N is exceeds +** the number of available subterms, return NULL. +*/ +static WhereTerm *whereNthSubterm(WhereTerm *pTerm, int N){ + if( pTerm->eOperator!=WO_AND ){ + return N==0 ? pTerm : 0; + } + if( Nu.pAndInfo->wc.nTerm ){ + return &pTerm->u.pAndInfo->wc.a[N]; + } + return 0; +} + +/* +** Subterms pOne and pTwo are contained within WHERE clause pWC. The +** two subterms are in disjunction - they are OR-ed together. +** +** If these two terms are both of the form: "A op B" with the same +** A and B values but different operators and if the operators are +** compatible (if one is = and the other is <, for example) then +** add a new virtual AND term to pWC that is the combination of the +** two. +** +** Some examples: +** +** x x<=y +** x=y OR x=y --> x=y +** x<=y OR x x<=y +** +** The following is NOT generated: +** +** xy --> x!=y +*/ +static void whereCombineDisjuncts( + SrcList *pSrc, /* the FROM clause */ + WhereClause *pWC, /* The complete WHERE clause */ + WhereTerm *pOne, /* First disjunct */ + WhereTerm *pTwo /* Second disjunct */ +){ + u16 eOp = pOne->eOperator | pTwo->eOperator; + sqlite3 *db; /* Database connection (for malloc) */ + Expr *pNew; /* New virtual expression */ + int op; /* Operator for the combined expression */ + int idxNew; /* Index in pWC of the next virtual term */ + + if( (pOne->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE))==0 ) return; + if( (pTwo->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE))==0 ) return; + if( (eOp & (WO_EQ|WO_LT|WO_LE))!=eOp + && (eOp & (WO_EQ|WO_GT|WO_GE))!=eOp ) return; + assert( pOne->pExpr->pLeft!=0 && pOne->pExpr->pRight!=0 ); + assert( pTwo->pExpr->pLeft!=0 && pTwo->pExpr->pRight!=0 ); + if( sqlite3ExprCompare(pOne->pExpr->pLeft, pTwo->pExpr->pLeft, -1) ) return; + if( sqlite3ExprCompare(pOne->pExpr->pRight, pTwo->pExpr->pRight, -1) )return; + /* If we reach this point, it means the two subterms can be combined */ + if( (eOp & (eOp-1))!=0 ){ + if( eOp & (WO_LT|WO_LE) ){ + eOp = WO_LE; + }else{ + assert( eOp & (WO_GT|WO_GE) ); + eOp = WO_GE; + } + } + db = pWC->pWInfo->pParse->db; + pNew = sqlite3ExprDup(db, pOne->pExpr, 0); + if( pNew==0 ) return; + for(op=TK_EQ; eOp!=(WO_EQ<<(op-TK_EQ)); op++){ assert( opop = op; + idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC); + exprAnalyze(pSrc, pWC, idxNew); +} #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY) /* ** Analyze a term that consists of two or more OR-connected ** subterms. So in: @@ -792,10 +865,11 @@ ** (A) t1.x=t2.y OR t1.x=t2.z OR t1.y=15 OR t1.z=t3.a+5 ** (B) x=expr1 OR expr2=x OR x=expr3 ** (C) t1.x=t2.y OR (t1.x=t2.z AND t1.y=15) ** (D) x=expr1 OR (y>11 AND y<22 AND z LIKE '*hello*') ** (E) (p.a=1 AND q.b=2 AND r.c=3) OR (p.x=4 AND q.y=5 AND r.z=6) +** (F) x>A OR (x=A AND y>=B) ** ** CASE 1: ** ** If all subterms are of the form T.C=expr for some single column of C and ** a single table T (as shown in example B above) then create a new virtual @@ -807,10 +881,20 @@ ** then create a new virtual term like this: ** ** x IN (expr1,expr2,expr3) ** ** CASE 2: +** +** If there are exactly two disjuncts one side has x>A and the other side +** has x=A (for the same x and A) then add a new virtual conjunct term to the +** WHERE clause of the form "x>=A". Example: +** +** x>A OR (x=A AND y>B) adds: x>=A +** +** The added conjunct can sometimes be helpful in query planning. +** +** CASE 3: ** ** If all subterms are indexable by a single table T, then set ** ** WhereTerm.eOperator = WO_OR ** WhereTerm.u.pOrInfo->indexable |= the cursor number for table T @@ -934,15 +1018,29 @@ } } } /* - ** Record the set of tables that satisfy case 2. The set might be + ** Record the set of tables that satisfy case 3. The set might be ** empty. */ pOrInfo->indexable = indexable; pTerm->eOperator = indexable==0 ? 0 : WO_OR; + + /* For a two-way OR, attempt to implementation case 2. + */ + if( indexable && pOrWc->nTerm==2 ){ + int iOne = 0; + WhereTerm *pOne; + while( (pOne = whereNthSubterm(&pOrWc->a[0],iOne++))!=0 ){ + int iTwo = 0; + WhereTerm *pTwo; + while( (pTwo = whereNthSubterm(&pOrWc->a[1],iTwo++))!=0 ){ + whereCombineDisjuncts(pSrc, pWC, pOne, pTwo); + } + } + } /* ** chngToIN holds a set of tables that *might* satisfy case 1. But ** we have to do some additional checking to see if case 1 really ** is satisfied. @@ -1069,11 +1167,11 @@ pTerm = &pWC->a[idxTerm]; markTermAsChild(pWC, idxNew, idxTerm); }else{ sqlite3ExprListDelete(db, pList); } - pTerm->eOperator = WO_NOOP; /* case 1 trumps case 2 */ + pTerm->eOperator = WO_NOOP; /* case 1 trumps case 3 */ } } } #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */ ADDED test/whereK.test Index: test/whereK.test ================================================================== --- /dev/null +++ test/whereK.test @@ -0,0 +1,72 @@ +# 2015-03-16 +# +# The author disclaims copyright to this source code. In place of +# a legal notice, here is a blessing: +# +# May you do good and not evil. +# May you find forgiveness for yourself and forgive others. +# May you share freely, never taking more than you give. +# +#*********************************************************************** +# This file implements regression tests for SQLite library. The +# focus of this file is testing OR expressions where terms can be +# factored from either side of the OR and combined into a single new +# AND term that is beneficial to the search. Examples: +# +# (x>A OR x=A) --> ... AND (x>=A) +# (x>A OR (x=A AND y>=B) --> ... AND (x>=A) +# + + + +set testdir [file dirname $argv0] +source $testdir/tester.tcl +set ::testprefix whereD + +do_execsql_test 1.1 { + CREATE TABLE t1(a,b,c); + WITH RECURSIVE c(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM c WHERE x<99) + INSERT INTO t1(a,b,c) SELECT x, x/10, x%10 FROM c; + CREATE INDEX t1bc ON t1(b,c); + SELECT a FROM t1 WHERE b>9 OR b=9 ORDER BY +a; +} {90 91 92 93 94 95 96 97 98 99} +do_execsql_test 1.1eqp { + EXPLAIN QUERY PLAN + SELECT a FROM t1 WHERE b>9 OR b=9 ORDER BY +a; +} {/SEARCH TABLE t1 USING INDEX t1bc/} + +do_execsql_test 1.2 { + SELECT a FROM t1 WHERE b>8 OR (b=8 AND c>7) ORDER BY +a; +} {88 89 90 91 92 93 94 95 96 97 98 99} +do_execsql_test 1.2eqp { + EXPLAIN QUERY PLAN + SELECT a FROM t1 WHERE b>8 OR (b=8 AND c>7) ORDER BY +a; +} {/SEARCH TABLE t1 USING INDEX t1bc/} + +do_execsql_test 1.3 { + SELECT a FROM t1 WHERE (b=8 AND c>7) OR b>8 ORDER BY +a; +} {88 89 90 91 92 93 94 95 96 97 98 99} +do_execsql_test 1.3eqp { + EXPLAIN QUERY PLAN + SELECT a FROM t1 WHERE (b=8 AND c>7) OR b>8 ORDER BY +a; +} {/SEARCH TABLE t1 USING INDEX t1bc/} + +do_execsql_test 1.4 { + SELECT a FROM t1 WHERE (b=8 AND c>7) OR 87) OR 87) OR (b>8 AND c NOT IN (4,5,6)) + ORDER BY +a; +} {88 89 90 91 92 93 97 98 99} +do_execsql_test 1.5eqp { + EXPLAIN QUERY PLAN + SELECT a FROM t1 WHERE (b=8 AND c>7) OR (b>8 AND c NOT IN (4,5,6)) + ORDER BY +a; +} {/SEARCH TABLE t1 USING INDEX t1bc/} + +finish_test