From 7b4fc6a8cb8e7fb63ddf5012fa89adcc21487de7 Mon Sep 17 00:00:00 2001 From: drh Date: Tue, 6 Feb 2007 13:26:32 +0000 Subject: [PATCH] When optimizing out an ORDER BY clause due to uniqueness constraints, make sure unused terms to the right in the ORDER BY clause to not reference other tables in a join. Ticket #2211. Additional test cases needed before closing this ticket. (CVS 3629) FossilOrigin-Name: 912faf18d86416b1a36660851f8a4554e6746875 --- manifest | 14 ++++----- manifest.uuid | 2 +- src/where.c | 83 +++++++++++++++++++++++++++++++++---------------- test/where.test | 73 ++++++++++++++++++++++++++++++++++++++++++- 4 files changed, 137 insertions(+), 35 deletions(-) diff --git a/manifest b/manifest index 41eff4fa22..1a96a90055 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Check\sthe\sreturn\svalue\sof\slseek()\sin\sos_unix.c\sto\smake\ssure\sit\sreally\sworked.\s(CVS\s3628) -D 2007-02-06T11:11:08 +C When\soptimizing\sout\san\sORDER\sBY\sclause\sdue\sto\suniqueness\sconstraints,\smake\nsure\sunused\sterms\sto\sthe\sright\sin\sthe\sORDER\sBY\sclause\sto\snot\sreference\sother\ntables\sin\sa\sjoin.\s\sTicket\s#2211.\s\sAdditional\stest\scases\sneeded\sbefore\nclosing\sthis\sticket.\s(CVS\s3629) +D 2007-02-06T13:26:33 F Makefile.in 7fa74bf4359aa899da5586e394d17735f221315f F Makefile.linux-gcc 2d8574d1ba75f129aba2019f0b959db380a90935 F README 9c4e2d6706bdcc3efdd773ce752a8cdab4f90028 @@ -129,7 +129,7 @@ F src/vdbeaux.c c5324d62f51529bccc5be3b04bac2e4eeae1569a F src/vdbefifo.c 9efb94c8c3f4c979ebd0028219483f88e57584f5 F src/vdbemem.c ff2424bee9eaf7c61d1f28bc0e711bebddebd653 F src/vtab.c 7fbda947e28cbe7adb3ba752a76ca9ef29936750 -F src/where.c 23dc1c7535c96770d214762ed0bc3c655de5061c +F src/where.c 2a919a3fbaff2e55604119f7c60133db459b404c F tclinstaller.tcl 046e3624671962dc50f0481d7c25b38ef803eb42 F test/aggerror.test a867e273ef9e3d7919f03ef4f0e8c0d2767944f2 F test/all.test b62fcd122052efaff1b0979aefa2dd65cfc8ee52 @@ -353,7 +353,7 @@ F test/vtab6.test ec0036f29f8a803da9935206f2d9d1b6a8026392 F test/vtab7.test 5f9ef9fb84733e928d5d0267c821072561b198d5 F test/vtab9.test 87afba55339b0c255e9697fbfb5bfb6120505d9d F test/vtab_err.test 224cc80ad700797c48b9cd2c1e0bd7a8517d8609 -F test/where.test 8dcc1b1a6f17b6bad2dc6a9917eafe62d4ea57eb +F test/where.test 1c28457a059119022a13c025e739c2e85a7eda0d F test/where2.test 61d5b20d9bedc8788a773bbdc5b2ef887725928e F test/where3.test 0a30fe9808b0fa01c46d0fcf4fac0bf6cf75bb30 F test/where4.test 3fcf53c5ea7af1db3980b3293c2a45b56605f26a @@ -429,7 +429,7 @@ F www/tclsqlite.tcl bb0d1357328a42b1993d78573e587c6dcbc964b9 F www/vdbe.tcl 87a31ace769f20d3627a64fa1fade7fed47b90d0 F www/version3.tcl 890248cf7b70e60c383b0e84d77d5132b3ead42b F www/whentouse.tcl 97e2b5cd296f7d8057e11f44427dea8a4c2db513 -P fc969ad991e5114c3612f4796e342a6db2d79cd5 -R 6df56c6ecba71e85197c64417671afce +P e4408dd1fd32e6c5057cce0fdfa70eb2d9bd2531 +R f29bac49ff178303d3caa7ff66242000 U drh -Z 5bd5ca139750741850fce483a9880960 +Z 7d81b673ebf7bf1811ff2651a7450761 diff --git a/manifest.uuid b/manifest.uuid index c5a71e63ec..9e127593b1 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -e4408dd1fd32e6c5057cce0fdfa70eb2d9bd2531 \ No newline at end of file +912faf18d86416b1a36660851f8a4554e6746875 \ No newline at end of file diff --git a/src/where.c b/src/where.c index d8fe6da85f..a364ce0e10 100644 --- a/src/where.c +++ b/src/where.c @@ -16,7 +16,7 @@ ** so is applicable. Because this module is responsible for selecting ** indices, you might also think of this module as the "query optimizer". ** -** $Id: where.c,v 1.236 2007/01/25 16:56:07 drh Exp $ +** $Id: where.c,v 1.237 2007/02/06 13:26:33 drh Exp $ */ #include "sqliteInt.h" @@ -43,6 +43,7 @@ int sqlite3_where_trace = 0; /* Forward reference */ typedef struct WhereClause WhereClause; +typedef struct ExprMaskSet ExprMaskSet; /* ** The query generator uses an array of instances of this structure to @@ -106,6 +107,7 @@ struct WhereTerm { */ struct WhereClause { Parse *pParse; /* The parser context */ + ExprMaskSet *pMaskSet; /* Mapping of table indices to bitmasks */ int nTerm; /* Number of terms */ int nSlot; /* Number of entries in a[] */ WhereTerm *a; /* Each a[] describes a term of the WHERE cluase */ @@ -138,7 +140,6 @@ struct WhereClause { ** numbers all get mapped into bit numbers that begin with 0 and contain ** no gaps. */ -typedef struct ExprMaskSet ExprMaskSet; struct ExprMaskSet { int n; /* Number of assigned cursor values */ int ix[sizeof(Bitmask)*8]; /* Cursor assigned to each bit */ @@ -186,8 +187,13 @@ struct ExprMaskSet { /* ** Initialize a preallocated WhereClause structure. */ -static void whereClauseInit(WhereClause *pWC, Parse *pParse){ +static void whereClauseInit( + WhereClause *pWC, /* The WhereClause to be initialized */ + Parse *pParse, /* The parsing context */ + ExprMaskSet *pMaskSet /* Mapping from table indices to bitmasks */ +){ pWC->pParse = pParse; + pWC->pMaskSet = pMaskSet; pWC->nTerm = 0; pWC->nSlot = ARRAYSIZE(pWC->aStatic); pWC->a = pWC->aStatic; @@ -463,7 +469,7 @@ static WhereTerm *findTerm( } /* Forward reference */ -static void exprAnalyze(SrcList*, ExprMaskSet*, WhereClause*, int); +static void exprAnalyze(SrcList*, WhereClause*, int); /* ** Call exprAnalyze on all terms in a WHERE clause. @@ -472,12 +478,11 @@ static void exprAnalyze(SrcList*, ExprMaskSet*, WhereClause*, int); */ static void exprAnalyzeAll( SrcList *pTabList, /* the FROM clause */ - ExprMaskSet *pMaskSet, /* table masks */ WhereClause *pWC /* the WHERE clause to be analyzed */ ){ int i; for(i=pWC->nTerm-1; i>=0; i--){ - exprAnalyze(pTabList, pMaskSet, pWC, i); + exprAnalyze(pTabList, pWC, i); } } @@ -592,11 +597,11 @@ static void transferJoinMarkings(Expr *pDerived, Expr *pBase){ */ static void exprAnalyze( SrcList *pSrc, /* the FROM clause */ - ExprMaskSet *pMaskSet, /* table masks */ WhereClause *pWC, /* the WHERE clause */ int idxTerm /* Index of the term to be analyzed */ ){ WhereTerm *pTerm = &pWC->a[idxTerm]; + ExprMaskSet *pMaskSet = pWC->pMaskSet; Expr *pExpr = pTerm->pExpr; Bitmask prereqLeft; Bitmask prereqAll; @@ -679,7 +684,7 @@ static void exprAnalyze( pNewExpr = sqlite3Expr(ops[i], sqlite3ExprDup(pExpr->pLeft), sqlite3ExprDup(pList->a[i].pExpr), 0); idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC); - exprAnalyze(pSrc, pMaskSet, pWC, idxNew); + exprAnalyze(pSrc, pWC, idxNew); pTerm = &pWC->a[idxTerm]; pWC->a[idxNew].iParent = idxTerm; } @@ -708,9 +713,9 @@ static void exprAnalyze( WhereTerm *pOrTerm; assert( (pTerm->flags & TERM_DYNAMIC)==0 ); - whereClauseInit(&sOr, pWC->pParse); + whereClauseInit(&sOr, pWC->pParse, pMaskSet); whereSplit(&sOr, pExpr, TK_OR); - exprAnalyzeAll(pSrc, pMaskSet, &sOr); + exprAnalyzeAll(pSrc, &sOr); assert( sOr.nTerm>0 ); j = 0; do{ @@ -750,7 +755,7 @@ static void exprAnalyze( transferJoinMarkings(pNew, pExpr); pNew->pList = pList; idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC); - exprAnalyze(pSrc, pMaskSet, pWC, idxNew); + exprAnalyze(pSrc, pWC, idxNew); pTerm = &pWC->a[idxTerm]; pWC->a[idxNew].iParent = idxTerm; pTerm->nChild = 1; @@ -787,10 +792,10 @@ or_not_possible: } pNewExpr1 = sqlite3Expr(TK_GE, sqlite3ExprDup(pLeft), pStr1, 0); idxNew1 = whereClauseInsert(pWC, pNewExpr1, TERM_VIRTUAL|TERM_DYNAMIC); - exprAnalyze(pSrc, pMaskSet, pWC, idxNew1); + exprAnalyze(pSrc, pWC, idxNew1); pNewExpr2 = sqlite3Expr(TK_LT, sqlite3ExprDup(pLeft), pStr2, 0); idxNew2 = whereClauseInsert(pWC, pNewExpr2, TERM_VIRTUAL|TERM_DYNAMIC); - exprAnalyze(pSrc, pMaskSet, pWC, idxNew2); + exprAnalyze(pSrc, pWC, idxNew2); pTerm = &pWC->a[idxTerm]; if( isComplete ){ pWC->a[idxNew1].iParent = idxTerm; @@ -836,6 +841,25 @@ or_not_possible: #endif /* SQLITE_OMIT_VIRTUALTABLE */ } +/* +** Return TRUE if any of the expressions in pList->a[iFirst...] contain +** a reference to any table other than the iBase table. +*/ +static int referencesOtherTables( + ExprList *pList, /* Search expressions in ths list */ + ExprMaskSet *pMaskSet, /* Mapping from tables to bitmaps */ + int iFirst, /* Be searching with the iFirst-th expression */ + int iBase /* Ignore references to this table */ +){ + Bitmask allowed = ~getMask(pMaskSet, iBase); + while( iFirstnExpr ){ + if( (exprTableUsage(pMaskSet, pList->a[iFirst++].pExpr)&allowed)!=0 ){ + return 1; + } + } + return 0; +} + /* ** This routine decides if pIdx can be used to satisfy the ORDER BY @@ -858,6 +882,7 @@ or_not_possible: */ static int isSortingIndex( Parse *pParse, /* Parsing context */ + ExprMaskSet *pMaskSet, /* Mapping from table indices to bitmaps */ Index *pIdx, /* The index we are testing */ int base, /* Cursor number for the table to be sorted */ ExprList *pOrderBy, /* The ORDER BY clause */ @@ -894,7 +919,7 @@ static int isSortingIndex( if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){ /* Can not use an index sort on anything that is not a column in the ** left-most table of the FROM clause */ - return 0; + break; } pColl = sqlite3ExprCollSeq(pParse, pExpr); if( !pColl ){ @@ -941,11 +966,12 @@ static int isSortingIndex( } j++; pTerm++; - if( iColumn<0 ){ + if( iColumn<0 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){ /* If the indexed column is the primary key and everything matches - ** so far, then we are assured that the index can be used to sort - ** because the primary key is unique and so none of the other columns - ** will make any difference + ** so far and none of the ORDER BY terms to the right reference other + ** tables in the join, then we are assured that the index can be used + ** to sort because the primary key is unique and so none of the other + ** columns will make any difference */ j = nTerm; } @@ -957,9 +983,12 @@ static int isSortingIndex( ** this index can be used for sorting. */ return 1; } - if( j==pIdx->nColumn && pIdx->onError!=OE_None ){ + if( pIdx->onError!=OE_None && i==pIdx->nColumn + && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){ /* All terms of this index match some prefix of the ORDER BY clause - ** and this index is UNIQUE, so this index can be used for sorting. */ + ** and the index is UNIQUE and no terms on the tail of the ORDER BY + ** clause reference other tables in a join. If this is all true then + ** the order by clause is superfluous. */ return 1; } return 0; @@ -973,6 +1002,7 @@ static int isSortingIndex( static int sortableByRowid( int base, /* Cursor number for table to be sorted */ ExprList *pOrderBy, /* The ORDER BY clause */ + ExprMaskSet *pMaskSet, /* Mapping from tables to bitmaps */ int *pbRev /* Set to 1 if ORDER BY is DESC */ ){ Expr *p; @@ -980,7 +1010,8 @@ static int sortableByRowid( assert( pOrderBy!=0 ); assert( pOrderBy->nExpr>0 ); p = pOrderBy->a[0].pExpr; - if( p->op==TK_COLUMN && p->iTable==base && p->iColumn==-1 ){ + if( p->op==TK_COLUMN && p->iTable==base && p->iColumn==-1 + && !referencesOtherTables(pOrderBy, pMaskSet, 1, base) ){ *pbRev = pOrderBy->a[0].sortOrder; return 1; } @@ -1298,7 +1329,7 @@ static double bestIndex( */ if( pProbe==0 && findTerm(pWC, iCur, -1, 0, WO_EQ|WO_IN|WO_LT|WO_LE|WO_GT|WO_GE,0)==0 && - (pOrderBy==0 || !sortableByRowid(iCur, pOrderBy, &rev)) ){ + (pOrderBy==0 || !sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev)) ){ *pFlags = 0; *ppIndex = 0; *pnEq = 0; @@ -1360,7 +1391,7 @@ static double bestIndex( /* If the table scan does not satisfy the ORDER BY clause, increase ** the cost by NlogN to cover the expense of sorting. */ if( pOrderBy ){ - if( sortableByRowid(iCur, pOrderBy, &rev) ){ + if( sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev) ){ flags |= WHERE_ORDERBY|WHERE_ROWID_RANGE; if( rev ){ flags |= WHERE_REVERSE; @@ -1444,7 +1475,7 @@ static double bestIndex( */ if( pOrderBy ){ if( (flags & WHERE_COLUMN_IN)==0 && - isSortingIndex(pParse,pProbe,iCur,pOrderBy,nEq,&rev) ){ + isSortingIndex(pParse,pWC->pMaskSet,pProbe,iCur,pOrderBy,nEq,&rev) ){ if( flags==0 ){ flags = WHERE_COLUMN_RANGE; } @@ -1832,7 +1863,7 @@ WhereInfo *sqlite3WhereBegin( ** subexpression is separated by an AND operator. */ initMaskSet(&maskSet); - whereClauseInit(&wc, pParse); + whereClauseInit(&wc, pParse, &maskSet); whereSplit(&wc, pWhere, TK_AND); /* Allocate and initialize the WhereInfo structure that will become the @@ -1863,7 +1894,7 @@ WhereInfo *sqlite3WhereBegin( for(i=0; inSrc; i++){ createMask(&maskSet, pTabList->a[i].iCursor); } - exprAnalyzeAll(pTabList, &maskSet, &wc); + exprAnalyzeAll(pTabList, &wc); if( sqlite3MallocFailed() ){ goto whereBeginNoMem; } diff --git a/test/where.test b/test/where.test index 8eeb3f81e6..1770d31986 100644 --- a/test/where.test +++ b/test/where.test @@ -11,7 +11,7 @@ # This file implements regression tests for SQLite library. The # focus of this file is testing the use of indices in WHERE clases. # -# $Id: where.test,v 1.39 2006/12/20 03:24:19 drh Exp $ +# $Id: where.test,v 1.40 2007/02/06 13:26:34 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl @@ -1037,6 +1037,77 @@ do_test where-13.12 { } } {1 one 4 four nosort} +# Ticket #2211. +# +# When optimizing out ORDER BY clauses, make sure that trailing terms +# of the ORDER BY clause do not reference other tables in a join. +# +do_test where-14.1 { + execsql { + CREATE TABLE t8(a INTEGER PRIMARY KEY, b TEXT UNIQUE); + INSERT INTO t8 VALUES(1,'one'); + INSERT INTO t8 VALUES(4,'four'); + } + cksort { + SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.a, y.b + } +} {1/4 1/1 4/4 4/1 sort} +do_test where-14.2 { + cksort { + SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.a, y.b DESC + } +} {1/1 1/4 4/1 4/4 sort} +do_test where-14.3 { + cksort { + SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.a, x.b + } +} {1/1 1/4 4/1 4/4 nosort} +do_test where-14.4 { + cksort { + SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.a, x.b DESC + } +} {1/1 1/4 4/1 4/4 nosort} +btree_breakpoint +do_test where-14.5 { + cksort { + SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b + } +} {4/1 4/4 1/1 1/4 nosort} +do_test where-14.6 { + cksort { + SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b DESC + } +} {4/1 4/4 1/1 1/4 nosort} +do_test where-14.7 { + cksort { + SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, y.a||y.b + } +} {4/1 4/4 1/1 1/4 sort} +do_test where-14.8 { + cksort { + SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, y.a||y.b DESC + } +} {4/4 4/1 1/4 1/1 sort} +do_test where-14.9 { + cksort { + SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||y.b + } +} {4/4 4/1 1/4 1/1 sort} +do_test where-14.10 { + cksort { + SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||y.b DESC + } +} {4/1 4/4 1/1 1/4 sort} +do_test where-14.11 { + cksort { + SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, y.a||x.b + } +} {4/1 4/4 1/1 1/4 sort} +do_test where-14.12 { + cksort { + SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, y.a||x.b DESC + } +} {4/4 4/1 1/4 1/1 sort} integrity_check {where-99.0} -- 2.47.2