Improved patch against latest CVS with more comments and new test
case attached. No regressions with make test.
> This updated patch greatly improves query times against compound
> SELECT statements (i.e., UNIONs) when the parent SELECT has a WHERE
> clause.
____________________________________________________________________________________
Expecting? Get great news right away with email Auto-Check.
Try the Yahoo! Mail Beta.
http://advision.webevents.yahoo.com/mailbeta/newmail_tools.html
Index: src/expr.c
===================================================================
RCS file: /sqlite/sqlite/src/expr.c,v
retrieving revision 1.294
diff -u -3 -p -r1.294 expr.c
--- src/expr.c 15 May 2007 07:00:34 -0000 1.294
+++ src/expr.c 19 May 2007 15:19:50 -0000
@@ -604,6 +604,7 @@ Select *sqlite3SelectDup(Select *p){
pNew->isAgg = p->isAgg;
pNew->usesEphm = 0;
pNew->disallowOrderBy = 0;
+ pNew->fOptPass = 0;
pNew->pRightmost = 0;
pNew->addrOpenEphm[0] = -1;
pNew->addrOpenEphm[1] = -1;
Index: src/select.c
===================================================================
RCS file: /sqlite/sqlite/src/select.c,v
retrieving revision 1.348
diff -u -3 -p -r1.348 select.c
--- src/select.c 14 May 2007 16:50:49 -0000 1.348
+++ src/select.c 19 May 2007 15:19:50 -0000
@@ -73,6 +73,7 @@ Select *sqlite3SelectNew(
pNew->pOffset = pOffset;
pNew->iLimit = -1;
pNew->iOffset = -1;
+ pNew->fOptPass = 0;
pNew->addrOpenEphm[0] = -1;
pNew->addrOpenEphm[1] = -1;
pNew->addrOpenEphm[2] = -1;
@@ -1397,7 +1398,7 @@ static int matchOrderbyToColumn(
Parse *pParse, /* A place to leave error messages */
Select *pSelect, /* Match to result columns of this SELECT */
ExprList *pOrderBy, /* The ORDER BY values to match against columns */
- int iTable, /* Insert this value in iTable */
+ int *iTable, /* Insert this value in iTable */
int mustComplete /* If TRUE all ORDER BYs must match */
){
int nErr = 0;
@@ -1423,6 +1424,10 @@ static int matchOrderbyToColumn(
int iCol = -1;
char *zLabel;
+ if( pE->op==TK_COLUMN ) {
+ *iTable = pE->iTable;
+ continue;
+ }
if( pOrderBy->a[i].done ) continue;
if( sqlite3ExprIsInteger(pE, &iCol) ){
if( iCol<=0 || iCol>pEList->nExpr ){
@@ -1456,7 +1461,7 @@ static int matchOrderbyToColumn(
if( iCol>=0 ){
pE->op = TK_COLUMN;
pE->iColumn = iCol;
- pE->iTable = iTable;
+ pE->iTable = *iTable;
pE->iAgg = -1;
pOrderBy->a[i].done = 1;
}else if( mustComplete ){
@@ -1731,7 +1736,7 @@ static int multiSelect(
** intermediate results.
*/
unionTab = pParse->nTab++;
- if( pOrderBy && matchOrderbyToColumn(pParse, p, pOrderBy, unionTab,1)
){
+ if( pOrderBy && matchOrderbyToColumn(pParse,p,pOrderBy,&unionTab,1) ){
rc = 1;
goto multi_select_end;
}
@@ -1825,7 +1830,7 @@ static int multiSelect(
*/
tab1 = pParse->nTab++;
tab2 = pParse->nTab++;
- if( pOrderBy && matchOrderbyToColumn(pParse,p,pOrderBy,tab1,1) ){
+ if( pOrderBy && matchOrderbyToColumn(pParse,p,pOrderBy,&tab1,1) ){
rc = 1;
goto multi_select_end;
}
@@ -2643,11 +2648,11 @@ int sqlite3SelectResolve(
sqlite3ExprResolveNames(&sNC, p->pHaving) ){
return SQLITE_ERROR;
}
- if( p->pPrior==0 ){
- if( processOrderGroupBy(&sNC, p->pOrderBy, "ORDER") ||
- processOrderGroupBy(&sNC, pGroupBy, "GROUP") ){
- return SQLITE_ERROR;
- }
+ if( p->pPrior==0 && processOrderGroupBy(&sNC, p->pOrderBy, "ORDER") ){
+ return SQLITE_ERROR;
+ }
+ if( processOrderGroupBy(&sNC, pGroupBy, "GROUP") ){
+ return SQLITE_ERROR;
}
/* Make sure the GROUP BY clause does not contain aggregate functions.
@@ -2774,6 +2779,167 @@ static void updateAccumulator(Parse *pPa
pAggInfo->directMode = 0;
}
+#ifdef SQLITE_OMIT_COMPOUND_SELECT
+#define SQLITE_OMIT_UNION_WHERE_OPTIMIZATION
+#endif
+
+#ifndef SQLITE_OMIT_UNION_WHERE_OPTIMIZATION
+
+static int optSelect(Parse*, Select*);
+static int optExprList(Parse*, ExprList*);
+
+static int optExpr(Parse* pParse, Expr* p) {
+ if (p) {
+ if( optExpr(pParse, p->pLeft)
+ || optExpr(pParse, p->pRight)
+ || optExprList(pParse, p->pList)
+ || optSelect(pParse, p->pSelect) ){
+ return SQLITE_ERROR;
+ }
+ }
+ return SQLITE_OK;
+}
+
+static int optSrcList(Parse* pParse, SrcList* p) {
+ if (p) {
+ int i;
+ for (i = 0; i < p->nSrc; ++i) {
+ if( optSelect(pParse, p->a[i].pSelect) ){
+ return SQLITE_ERROR;
+ }
+ }
+ }
+ return SQLITE_OK;
+}
+
+static int optExprList(Parse* pParse, ExprList* p) {
+ if (p) {
+ int i;
+ for (i = 0; i < p->nExpr; ++i) {
+ if( optExpr(pParse, p->a[i].pExpr) ){
+ return SQLITE_ERROR;
+ }
+ }
+ }
+ return SQLITE_OK;
+}
+
+/* This function will optimize the WHERE clauses of a single compound SELECT
+** statement by merging it with its parent WHERE clause, often resulting
+** in a much faster query due to better index selection, consuming less
+** temp store in the process.
+** This is most commonly seen in the form of a SELECT on a VIEW
+** which contains one or more UNIONs.
+**
+** For example:
+**
+** SELECT * FROM (
+** SELECT a, b FROM t1 WHERE b!=7
+** UNION ALL
+** SELECT x, sum(y) FROM t2
+** WHERE x<9 GROUP BY x HAVING sum(y)>7
+** ) WHERE a>b;
+**
+** will be transformed into:
+**
+** SELECT * FROM (
+** SELECT a, b FROM t1 WHERE b!=7 AND a>b
+** UNION ALL
+** SELECT x, sum(y) FROM t2
+** WHERE x<9 GROUP BY x HAVING sum(y)>7 AND x>sum(y)
+** );
+**
+** This function expects a completely resolved parse tree.
+*/
+static void optimizeSelectOnUnion(Select* p) {
+ if( p && p->pWhere /* Parent has a WHERE clause. */
+ && p->pEList && p->pEList->nExpr > 0 /* At least 1 column in result list. */
+ && p->pSrc && p->pSrc->nSrc == 1 /* Parent FROM clause has 1 entry. */
+ && p->pSrc->a[0].pSelect /* FROM clause entry is a SELECT. */
+ && p->pSrc->a[0].pSelect->pPrior /* FROM entry is a compound SELECT. */
+ ){
+ int numColumnsInLeftmostSelect, deleteParentWhereClause = 1;
+ Select *leftmostSelect;
+ Select *pSub = p->pSrc->a[0].pSelect;
+ assert( pSub );
+ leftmostSelect = pSub;
+ while( leftmostSelect->pPrior ){
+ leftmostSelect = leftmostSelect->pPrior;
+ }
+ numColumnsInLeftmostSelect = leftmostSelect->pEList->nExpr;
+ for( ; pSub; pSub = pSub->pPrior ){
+ if( pSub->pEList->nExpr != numColumnsInLeftmostSelect ){
+ /* Mismatched number of result columns in a compound subselect.
+ ** This error will be caught later in the code generation phase. */
+ return;
+ }
+ /* Do not add the parent WHERE clause to this compound subselect if:
+ ** (1) the subselect is an aggregate SELECT without a GROUP BY clause
+ ** OR (2) the subselect has a LIMIT clause (may be overly restrictive)
+ */
+ if( (pSub->isAgg && !pSub->pGroupBy) /* Restriction (1) */
+ || (pSub->pLimit) /* Restriction (2) */
+ ){
+ deleteParentWhereClause = 0;
+ continue;
+ } else {
+ Expr *parentWhereCopy = sqlite3ExprDup(p->pWhere);
+ substExpr(parentWhereCopy, p->pSrc->a[0].iCursor, pSub->pEList);
+ if( pSub->pGroupBy ){
+ pSub->pHaving = sqlite3ExprAnd(pSub->pHaving, parentWhereCopy);
+ } else {
+ pSub->pWhere = sqlite3ExprAnd(pSub->pWhere, parentWhereCopy);
+ }
+ }
+ }
+ if( deleteParentWhereClause ){
+ sqlite3ExprDelete(p->pWhere);
+ p->pWhere = 0;
+ }
+ }
+}
+
+#define SQLITE_SELECT_OPT_UNION_WHERE 1
+
+static int optSelect(Parse* pParse, Select* p) {
+ int rc = SQLITE_OK;
+ if (pParse && p && (p->fOptPass & SQLITE_SELECT_OPT_UNION_WHERE)==0) {
+ p->fOptPass |= SQLITE_SELECT_OPT_UNION_WHERE;
+ if( p->pPrior ){
+ if( p->pRightmost==0 ){
+ Select *pLoop;
+ for(pLoop=p; pLoop; pLoop=pLoop->pPrior){
+ pLoop->pRightmost = p;
+ }
+ }
+ if (p->pOrderBy) {
+ /* adjust cursors for ORDER BY expressions */
+ int unionTab = pParse->nTab++;
+ if (matchOrderbyToColumn(pParse, p, p->pOrderBy, &unionTab, 1)) {
+ return SQLITE_ERROR;
+ }
+ }
+ }
+ if (sqlite3SelectResolve(pParse, p, 0)) {
+ return SQLITE_ERROR;
+ }
+ if (optSrcList(pParse, p->pSrc)
+ || optExprList(pParse, p->pEList)
+ || optExpr(pParse, p->pWhere)
+ || optExprList(pParse, p->pGroupBy)
+ || optExpr(pParse, p->pHaving)
+ || optExprList(pParse, p->pOrderBy)
+ || optSelect(pParse, p->pPrior)
+ || optExpr(pParse, p->pLimit)
+ || optExpr(pParse, p->pOffset) ){
+ return SQLITE_ERROR;
+ }
+ optimizeSelectOnUnion(p);
+ }
+ return rc;
+}
+
+#endif /* SQLITE_OMIT_UNION_WHERE_OPTIMIZATION */
/*
** Generate code for the given SELECT statement.
@@ -2861,6 +3027,13 @@ int sqlite3Select(
memset(&sAggInfo, 0, sizeof(sAggInfo));
#ifndef SQLITE_OMIT_COMPOUND_SELECT
+
+#ifndef SQLITE_OMIT_UNION_WHERE_OPTIMIZATION
+ if( optSelect(pParse, p) ){
+ return 1;
+ }
+#endif
+
/* If there is are a sequence of queries, do the earlier ones first.
*/
if( p->pPrior ){
Index: src/sqliteInt.h
===================================================================
RCS file: /sqlite/sqlite/src/sqliteInt.h,v
retrieving revision 1.569
diff -u -3 -p -r1.569 sqliteInt.h
--- src/sqliteInt.h 16 May 2007 17:28:43 -0000 1.569
+++ src/sqliteInt.h 19 May 2007 15:19:51 -0000
@@ -1263,6 +1263,7 @@ struct Select {
u8 isAgg; /* True if this is an aggregate query */
u8 usesEphm; /* True if uses an OpenEphemeral opcode */
u8 disallowOrderBy; /* Do not allow an ORDER BY to be attached if TRUE */
+ u8 fOptPass; /* Set bits for each optimization pass performed */
char affinity; /* MakeRecord with this affinity for SRT_Set */
SrcList *pSrc; /* The FROM clause */
Expr *pWhere; /* The WHERE clause */
Index: test/misc5.test
===================================================================
RCS file: /sqlite/sqlite/test/misc5.test,v
retrieving revision 1.16
diff -u -3 -p -r1.16 misc5.test
--- test/misc5.test 3 Jan 2007 23:37:29 -0000 1.16
+++ test/misc5.test 19 May 2007 15:19:51 -0000
@@ -553,7 +553,7 @@ ifcapable subquery&&compound {
SELECT * FROM logs
LIMIT (SELECT lmt FROM logs_base) ;
}
- } {1 {no such column: logs.id}}
+ } {1 {no such table: logs_base}}
}
# Overflow the lemon parser stack by providing an overly complex
Index: test/select7.test
===================================================================
RCS file: /sqlite/sqlite/test/select7.test,v
retrieving revision 1.9
diff -u -3 -p -r1.9 select7.test
--- test/select7.test 9 May 2007 22:56:39 -0000 1.9
+++ test/select7.test 19 May 2007 15:19:51 -0000
@@ -135,4 +135,87 @@ ifcapable {subquery && compound} {
{only a single result allowed for a SELECT that is part of an expression}]
}
+# Test cases for WHERE clause optimization on compound SELECT statements
+ifcapable {subquery && compound} {
+ do_test select7-6.1 {
+ execsql {
+ CREATE TABLE T5(a,b);
+ INSERT INTO T5 VALUES(1,2);
+ INSERT INTO T5 VALUES(1,3);
+ INSERT INTO T5 VALUES(1,4);
+ INSERT INTO T5 VALUES(2,4);
+ INSERT INTO T5 VALUES(2,7);
+ INSERT INTO T5 VALUES(3,1);
+
+ CREATE TABLE T4(x,y);
+ INSERT INTO T4 VALUES(2,3);
+ INSERT INTO T4 VALUES(7,9);
+ INSERT INTO T4 VALUES(8,8);
+ INSERT INTO T4 VALUES(1,3);
+
+ CREATE VIEW UV1 AS
+ SELECT x,y FROM T4 UNION ALL SELECT * FROM T5;
+
+ SELECT * FROM UV1 WHERE x>1 and y<>3;
+ }
+ } {7 9 8 8 2 4 2 7 3 1}
+ do_test select7-6.2 {
+ execsql {
+ CREATE VIEW UV2 AS
+ SELECT x,y FROM T4 WHERE x*y>4 UNION SELECT * FROM T5 WHERE a*2=b;
+ SELECT x, sum(y) FROM UV2 GROUP BY x;
+ }
+ } {1 2 2 7 7 9 8 8}
+ do_test select7-6.3 {
+ execsql {
+ SELECT * FROM (
+ SELECT x,y from UV1 UNION SELECT y,x FROM UV2 WHERE x+y>6
+ ) WHERE y>2*x OR x=y ORDER BY y-x;
+ }
+ } {8 8 1 3 1 4 2 7}
+ do_test select7-6.4 {
+ execsql {
+ SELECT x, sum(y) FROM (
+ SELECT x,y from UV1 UNION SELECT y,x FROM UV2 WHERE x+y>6
+ ) GROUP BY 1 ORDER BY 2,1;
+ }
+ } {3 1 9 7 8 8 1 9 7 9 2 14}
+ do_test select7-6.5 {
+ execsql {
+ SELECT j, k FROM (
+ SELECT a+2 AS j, sum(b) AS k FROM T5 GROUP BY 1 HAVING k>=9
+ UNION ALL SELECT x,y FROM T4 WHERE y-x<>2
+ UNION ALL SELECT 7,3
+ ) WHERE j>3 ORDER BY 2,1;
+ }
+ } {7 3 8 8 4 11}
+ do_test select7-6.6 {
+ execsql {
+ CREATE TABLE n1(a integer primary key);
+ INSERT INTO n1 VALUES(1);
+ INSERT INTO n1 VALUES(2);
+ INSERT INTO n1 VALUES(3);
+ INSERT INTO n1 VALUES(4);
+ INSERT INTO n1 VALUES(5);
+ INSERT INTO n1 VALUES(6);
+ INSERT INTO n1 VALUES(7);
+ INSERT INTO n1 VALUES(8);
+ INSERT INTO n1 VALUES(9);
+ CREATE VIEW vu as select v3.a a, v5.a-v2.a*v7.a b
+ from n1 v1,n1 v2,n1 v3,n1 v4,n1 v5,n1 v6,n1 v7;
+ CREATE VIEW v2 as select * from vu union all select 7, 8;
+ select count(*), avg(b) from v2 where a<3;
+ }
+ } {1062882 -20.0}
+ do_test select7-6.7 {
+ execsql {
+ SELECT * FROM (
+ SELECT 7 a, max(a) b FROM n1
+ UNION ALL
+ SELECT a, a*a FROM n1 WHERE a<4
+ ) WHERE b>8;
+ }
+ } {7 9 3 9}
+}
+
finish_test
-----------------------------------------------------------------------------
To unsubscribe, send email to [EMAIL PROTECTED]
-----------------------------------------------------------------------------
