--- [EMAIL PROTECTED] wrote:
> Joe Wilson <[EMAIL PROTECTED]> wrote:
> >
> > I would think it would not be too difficult to extend SQLite
> > to perform this type of transformation on a view.
> >
> > i.e., transform:
> >
> > SELECT columns0 from (
> > SELECT columns1 WHERE condition1
> > UNION (ALL)
> > SELECT columns2 WHERE condition2
> > )
> > WHERE condition3
> >
> > to
> >
> > SELECT columns0 from (
> > SELECT columns1 WHERE (condition1) AND (condition3)
> > UNION (ALL)
> > SELECT columns2 WHERE (condition2) AND (condition3)
> > }
> >
> > or am I neglecting something?
> >
>
> We await your patch.
> --
> D. Richard Hipp <[EMAIL PROTECTED]>
As goaded^H^H^H^H^H^Hrequested, here's a patch that optimizes
SELECTs on a compound subquery, or VIEWs containing UNIONS.
pragma temp_store=memory;
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);
INSERT INTO "n1" VALUES(10);
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;
The above query takes 58 seconds in sqlite 3.3.7, using 136M of temp_store.
With the patch, it takes just 12 seconds and uses 26M of temp_store.
The patch also performs 32 bit integer constant folding:
sqlite> explain select 1*2+3-4%5/2|128;
0|Goto|0|4|
1|Integer|131|0|
2|Callback|1|0|
3|Halt|0|0|
4|Goto|0|1|
5|Noop|0|0|
These optimizations take place on a resolved tree before any VDBE
instructions are generated. This way you have more flexibility
to do complete tree transforms. ORs in WHERE clauses are another good
candidate for optimization, if someone wants to take that on.
The SELECT tree dump utility could be helpful:
http://marc.theaimsgroup.com/?l=sqlite-users&m=115371405520994&w=2
"make test" ran with no regressions, but this patch should be considered
experimental. Many more test cases are needed to test these optimizations.
I disclaim copyright to this source code.
Joe Wilson
__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
Index: src/parse.y
===================================================================
RCS file: /sqlite/sqlite/src/parse.y,v
retrieving revision 1.207
diff -u -3 -p -r1.207 parse.y
--- src/parse.y 14 Aug 2006 14:23:42 -0000 1.207
+++ src/parse.y 17 Aug 2006 04:07:31 -0000
@@ -366,6 +366,7 @@ cmd ::= DROP VIEW ifexists(E) fullname(X
//////////////////////// The SELECT statement /////////////////////////////////
//
cmd ::= select(X). {
+ sqlite3SelectOptimize(pParse, X);
sqlite3Select(pParse, X, SRT_Callback, 0, 0, 0, 0, 0);
sqlite3SelectDelete(X);
}
@@ -598,8 +599,10 @@ setlist(A) ::= nm(X) EQ expr(Y). {A =
cmd ::= insert_cmd(R) INTO fullname(X) inscollist_opt(F)
VALUES LP itemlist(Y) RP.
{sqlite3Insert(pParse, X, Y, 0, F, R);}
-cmd ::= insert_cmd(R) INTO fullname(X) inscollist_opt(F) select(S).
- {sqlite3Insert(pParse, X, 0, S, F, R);}
+cmd ::= insert_cmd(R) INTO fullname(X) inscollist_opt(F) select(S). {
+ sqlite3SelectOptimize(pParse, S);
+ sqlite3Insert(pParse, X, 0, S, F, R);
+}
%type insert_cmd {int}
insert_cmd(A) ::= INSERT orconf(R). {A = R;}
Index: src/select.c
===================================================================
RCS file: /sqlite/sqlite/src/select.c,v
retrieving revision 1.320
diff -u -3 -p -r1.320 select.c
--- src/select.c 11 Aug 2006 19:08:27 -0000 1.320
+++ src/select.c 17 Aug 2006 04:07:32 -0000
@@ -1382,7 +1382,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;
@@ -1405,6 +1405,12 @@ static int matchOrderbyToColumn(
for(i=0; i<pOrderBy->nExpr; i++){
Expr *pE = pOrderBy->a[i].pExpr;
int iCol = -1;
+ if( pE->op==TK_COLUMN ) {
+ /* If type is TK_COLUMN, all column nodes in expression
+ are guaranteed to contain the same iTable value. */
+ *iTable = pE->iTable;
+ continue;
+ }
if( pOrderBy->a[i].done ) continue;
if( sqlite3ExprIsInteger(pE, &iCol) ){
if( iCol<=0 || iCol>pEList->nExpr ){
@@ -1435,7 +1441,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;
}
@@ -1710,7 +1716,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;
}
@@ -1804,7 +1810,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;
}
@@ -2122,6 +2128,7 @@ static void substSelect(Select *p, int i
** the subquery before this routine runs.
*/
static int flattenSubquery(
+ Parse* pParse,
Select *p, /* The parent or outer SELECT statement */
int iFrom, /* Index in p->pSrc->a[] of the inner subquery */
int isAgg, /* True if outer SELECT uses aggregate functions */
@@ -2306,6 +2313,7 @@ static int flattenSubquery(
** success.
*/
sqlite3SelectDelete(pSub);
+ sqlite3SelectOptimize(pParse, p);
return 1;
}
#endif /* SQLITE_OMIT_VIEW */
@@ -2903,10 +2911,11 @@ int sqlite3Select(
*/
#ifndef SQLITE_OMIT_VIEW
if( pParent && pParentAgg &&
- flattenSubquery(pParent, parentTab, *pParentAgg, isAgg) ){
+ flattenSubquery(pParse, pParent, parentTab, *pParentAgg, isAgg) ){
if( isAgg ) *pParentAgg = 1;
goto select_end;
}
+ pWhere = p->pWhere; /* may have been optimized away by flattenSubquery */
#endif
/* If there is an ORDER BY clause, resolve any collation sequences
@@ -3295,3 +3304,237 @@ select_end:
sqliteFree(sAggInfo.aFunc);
return rc;
}
+
+#ifndef SQLITE_OMIT_SELECT_OPTIMIZE
+
+static void optSelect(Parse*, Select*);
+static void optExprList(Parse*, ExprList*);
+
+/* Fold constant 32 bit integer expressions into single TK_INTEGER values
+** to improve SELECT performance for certain classes of queries
+** (often involving SELECTs on VIEWs).
+** For example, the SQL expression 5*3+2 is transformed into the
+** TK_INTEGER value 17 prior to VDBE code generation.
+*/
+static void foldConstantIntegerExpr(Expr* pE) {
+ int op;
+ int left;
+ int right;
+ int v;
+ char zBuf[40];
+
+ if (pE == 0) return;
+ op = pE->op;
+ if (op == TK_INTEGER) return;
+
+ foldConstantIntegerExpr(pE->pLeft);
+
+ if (op == TK_UMINUS || op == TK_NOT || op == TK_BITNOT) {
+ if (sqlite3ExprIsInteger(pE->pLeft, &left)) {
+ switch (op) {
+ case TK_UMINUS: left = -left; break;
+ case TK_NOT: left = !left; break;
+ case TK_BITNOT: left = ~left; break;
+ default:
+ return;
+ }
+ sqlite3_snprintf(sizeof(zBuf), zBuf, "%d", left);
+ pE->op = TK_INTEGER;
+ pE->token.dyn = 1;
+ pE->token.z = sqlite3StrDup(zBuf);
+ pE->token.n = strlen(zBuf);
+ sqlite3ExprDelete(pE->pLeft);
+ pE->pLeft = 0;
+ }
+ return;
+ }
+
+ foldConstantIntegerExpr(pE->pRight);
+
+ if (pE->pLeft && pE->pRight) {
+ if (sqlite3ExprIsInteger(pE->pLeft, &left)
+ && sqlite3ExprIsInteger(pE->pRight, &right)){
+ switch (op) {
+ case TK_LT: { v = left < right; break; }
+ case TK_LE: { v = left <= right; break; }
+ case TK_GT: { v = left > right; break; }
+ case TK_GE: { v = left >= right; break; }
+ case TK_NE: { v = left != right; break; }
+ case TK_EQ: { v = left == right; break; }
+ case TK_AND: { v = left && right; break; }
+ case TK_OR: { v = left || right; break; }
+ case TK_PLUS: { v = left + right; break; }
+ case TK_STAR: { v = left * right; break; }
+ case TK_MINUS: { v = left - right; break; }
+ case TK_REM: { v = left % right; break; }
+ case TK_BITAND: { v = left & right; break; }
+ case TK_BITOR: { v = left | right; break; }
+ case TK_RSHIFT: { v = left >> right; break; }
+ case TK_SLASH: {
+ if (right) {
+ v = left / right;
+ } else {
+ return;
+ }
+ break;
+ }
+ default: return;
+ }
+
+ pE->op = TK_INTEGER;
+ sqlite3_snprintf(sizeof(zBuf), zBuf, "%d", v);
+ pE->token.dyn = 1;
+ pE->token.z = sqliteStrDup(zBuf);
+ pE->token.n = strlen(zBuf);
+
+ sqlite3ExprDelete(pE->pLeft);
+ sqlite3ExprDelete(pE->pRight);
+ pE->pLeft = 0;
+ pE->pRight = 0;
+ return;
+ }
+ }
+}
+
+static void optExpr(Parse* pParse, Expr* p) {
+ if (p) {
+ if (pParse) foldConstantIntegerExpr(p);
+ optExpr(pParse, p->pLeft);
+ optExpr(pParse, p->pRight);
+ optExprList(pParse, p->pList);
+ optSelect(pParse, p->pSelect);
+ }
+}
+
+static void optSrcList_item(Parse* pParse, struct SrcList_item* p) {
+ if (p) {
+ optSelect(pParse, p->pSelect);
+ optExpr(pParse, p->pOn);
+ }
+}
+
+static void optSrcList(Parse* pParse, SrcList* p) {
+ if (p) {
+ int i;
+ for (i = 0; i < p->nSrc; ++i) {
+ optSrcList_item(pParse, &p->a[i]);
+ }
+ }
+}
+
+static void optExprList_item(Parse* pParse, struct ExprList_item* p) {
+ if (p) {
+ optExpr(pParse, p->pExpr);
+ }
+}
+
+static void optExprList(Parse* pParse, ExprList* p) {
+ if (p) {
+ int i;
+ for (i = 0; i < p->nExpr; ++i) {
+ optExprList_item(pParse, &p->a[i]);
+ }
+ }
+}
+
+/* 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 UNION ALL SELECT x,y FROM t2) WHERE a>b;
+**
+** will be transformed into:
+**
+** SELECT * FROM (
+** SELECT a, b FROM t1 WHERE a>b
+** UNION ALL
+** SELECT x, y FROM t2 WHERE x>y
+** );
+*/
+static void optimizeSelectOnUnion(Select* p) {
+ if (p && p->pWhere && p->pSrc && p->pSrc->nSrc == 1 && p->pEList
+ && p->pEList->nExpr > 0 && p->pSrc->a[0].pSelect
+ && p->pSrc->a[0].pSelect->pPrior) {
+ Select* subSel = p->pSrc->a[0].pSelect;
+ assert( subSel );
+ if (subSel->pRightmost && subSel->pRightmost->pLimit) {
+ /* the child compound SELECT must not have a LIMIT clause */
+ return;
+ }
+ Select* firstSubSelect = subSel;
+ while (firstSubSelect->pPrior) {
+ firstSubSelect = firstSubSelect->pPrior;
+ }
+ int numCols = firstSubSelect->pEList->nExpr;
+ while (subSel) {
+ Expr* e = 0;
+ if (subSel->pEList->nExpr != numCols) {
+ return; /* error will be caught in code gen pass */
+ }
+ Expr* parentWhereCopy = sqlite3ExprDup(p->pWhere);
+ substExpr(parentWhereCopy, p->pSrc->a[0].iCursor, subSel->pEList);
+ if (subSel->pGroupBy) {
+ /* XXX this requires testing */
+ e = subSel->pHaving = sqlite3ExprAnd(subSel->pHaving, parentWhereCopy);
+ } else {
+ e = subSel->pWhere = sqlite3ExprAnd(subSel->pWhere, parentWhereCopy);
+ }
+ foldConstantIntegerExpr(e);
+ subSel = subSel->pPrior;
+ }
+ /* the parent where clause is no longer required */
+ sqlite3ExprDelete(p->pWhere);
+ p->pWhere = 0;
+ }
+}
+
+#ifndef SQLITE_OMIT_COMPOUND_SELECT
+static int matchOrderbyToColumn(Parse*,Select*,ExprList*,int*,int);
+#endif
+
+static void optSelect(Parse* pParse, Select* p) {
+ if (pParse && p) {
+ if( p->pPrior ){
+ if( p->pRightmost==0 ){
+ Select *pLoop;
+ for(pLoop=p; pLoop; pLoop=pLoop->pPrior){
+ pLoop->pRightmost = p;
+ }
+ }
+ if (p->pOrderBy) {
+ /* if() below required by some obscure SELECT ORDER BY clauses */
+ int unionTab = pParse->nTab++;
+ if (matchOrderbyToColumn(pParse, p, p->pOrderBy, &unionTab, 1)) {
+ return;
+ }
+ }
+ }
+ if (sqlite3SelectResolve(pParse, p, 0)) {
+ return;
+ }
+ 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);
+ optimizeSelectOnUnion(p);
+ }
+}
+
+#endif
+
+int sqlite3SelectOptimize(Parse *pParse, Select *p) {
+#ifndef SQLITE_OMIT_SELECT_OPTIMIZE
+ optSelect(pParse, p);
+#endif
+ return 0;
+}
Index: src/sqliteInt.h
===================================================================
RCS file: /sqlite/sqlite/src/sqliteInt.h,v
retrieving revision 1.523
diff -u -3 -p -r1.523 sqliteInt.h
--- src/sqliteInt.h 26 Jul 2006 13:43:31 -0000 1.523
+++ src/sqliteInt.h 17 Aug 2006 04:07:32 -0000
@@ -1625,6 +1625,7 @@ void sqlite3DropIndex(Parse*, SrcList*,
void sqlite3AddKeyType(Vdbe*, ExprList*);
void sqlite3AddIdxKeyType(Vdbe*, Index*);
int sqlite3Select(Parse*, Select*, int, int, Select*, int, int*, char *aff);
+int sqlite3SelectOptimize(Parse*, Select*);
Select *sqlite3SelectNew(ExprList*,SrcList*,Expr*,ExprList*,Expr*,ExprList*,
int,Expr*,Expr*);
void sqlite3SelectDelete(Select*);
-----------------------------------------------------------------------------
To unsubscribe, send email to [EMAIL PROTECTED]
-----------------------------------------------------------------------------
