From 85574e31cba504782df8d335efc74a174bfeb9ac Mon Sep 17 00:00:00 2001 From: danielk1977 Date: Mon, 6 Oct 2008 05:32:18 +0000 Subject: [PATCH] Allow INDEXED BY and NOT INDEXED clauses in SELECT statements. (CVS 5766) FossilOrigin-Name: 98ca5580f5acd2e7b3ce512520ec0527f221505e --- manifest | 29 ++++---- manifest.uuid | 2 +- src/build.c | 12 ++- src/delete.c | 4 +- src/expr.c | 5 +- src/parse.y | 23 +++++- src/select.c | 17 ++++- src/sqliteInt.h | 7 +- src/where.c | 169 +++++++++++++++++++++++++------------------ test/indexedby.test | 151 ++++++++++++++++++++++++++++++++++++++ test/malloc.test | 13 +++- tool/mkkeywordhash.c | 3 +- 12 files changed, 337 insertions(+), 98 deletions(-) create mode 100644 test/indexedby.test diff --git a/manifest b/manifest index 38ec0fe52f..315bfc07e2 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Modifications\sto\sbind.test\sto\saccount\sfor\sdifferent\svalues\sof\sSQLITE_MAX_VARIABLE_NUMBER.\sTicket\s#3409.\s(CVS\s5765) -D 2008-10-03T09:10:46 +C Allow\sINDEXED\sBY\sand\sNOT\sINDEXED\sclauses\sin\sSELECT\sstatements.\s(CVS\s5766) +D 2008-10-06T05:32:19 F Makefile.arm-wince-mingw32ce-gcc fcd5e9cd67fe88836360bb4f9ef4cb7f8e2fb5a0 F Makefile.in e4ab842f9a64ef61d57093539a8aab76b12810db F Makefile.linux-gcc d53183f4aa6a9192d249731c90dbdffbd2c68654 @@ -102,12 +102,12 @@ F src/btmutex.c 709cad2cdca0afd013f0f612363810e53f59ec53 F src/btree.c 64a38df6f0a9997563418ed194984b81e4ab3694 F src/btree.h 6371c5e599fab391a150c96afbc10062b276d107 F src/btreeInt.h e38e9b2b285f40f5bc0a6664f630d4a141622f16 -F src/build.c 160c71acca8f643f436ed6c1ee2f684c88df4dfe +F src/build.c 5097bb7978bfdae4ae052abc16aa00c1054b7956 F src/callback.c 7a40fd44da3eb89e7f6eff30aa6f940c45d73a97 F src/complete.c cb14e06dbe79dee031031f0d9e686ff306afe07c F src/date.c 5c092296c03d658e84884121a694150964d6861d -F src/delete.c bae6684aa02e1f7cf6328023157c91d9cf94200b -F src/expr.c efa82724366877b546a12174fa1278bd47a450a9 +F src/delete.c 52c3614b1dc815f54d64a98dc65a393737f68b91 +F src/expr.c 30973b017bf95ca767f5eec64918c8afc425488d F src/fault.c dc88c821842157460750d2d61a8a8b4197d047ff F src/func.c 8431b40a7843d1024145684d303c55b4ee087bbe F src/global.c 20a3fe46c8287a01ba3a7442558f0eb70c66b19a @@ -139,7 +139,7 @@ F src/os_unix.c f33b69d8a85372b270fe37ee664a4c2140a5217d F src/os_win.c 04033a86a39f49cb8e348f515eb0116aa9d36678 F src/pager.c 44eba010e81dcc9b772401b90d6a1c61ec24345b F src/pager.h 9c1917be28fff58118e1fe0ddbc7adfb8dd4f44d -F src/parse.y d0f76d2cb8d6883d5600dc20beb961a6022b94b8 +F src/parse.y c69312dff9285f6638b209189d4166dd3a985c81 F src/pcache.c f8d7beceba164a34441ac37e88abb3a404f968a7 F src/pcache.h 28d9ce2d66909db1f01652586450b62b64793093 F src/pragma.c 0b1c2d2a241dd79a7361bbeb8ff575a9e9d7cd71 @@ -147,11 +147,11 @@ F src/prepare.c c7e00ed1b0bdcf699b1aad651247d4dc3d281b0b F src/printf.c 785f87120589c1db672e37c6eb1087c456e6f84d F src/random.c 11bbdf7def3746a762fbdb56c9d04648135ad6d8 F src/resolve.c a6abf83125bce0c80ba04acc27c3565155ad305c -F src/select.c f118f8db2ce91a4cf972e6ae88c8e7cc8543f513 +F src/select.c 75d4ffe971e25831125ea165c0c580df00f4c403 F src/shell.c d83b578a8ccdd3e0e7fef4388a0887ce9f810967 F src/sqlite.h.in ea235b37a691b32e7941baa70fb0afaf6377dbb4 F src/sqlite3ext.h 1e3887c9bd3ae66cb599e922824b04cd0d0f2c3e -F src/sqliteInt.h 437b408a7473293a903eb63f3c1d6ca814a13cdb +F src/sqliteInt.h 1806947aac72ba3ea6de3b9de5c66e3d257e8fe7 F src/sqliteLimit.h f435e728c6b620ef7312814d660a81f9356eb5c8 F src/status.c 237b193efae0cf6ac3f0817a208de6c6c6ef6d76 F src/table.c 22744786199c9195720c15a7a42cb97b2e2728d8 @@ -199,7 +199,7 @@ F src/vdbefifo.c 20fda2a7c4c0bcee1b90eb7e545fefcdbf2e1de7 F src/vdbemem.c ead88713b852576e2a924bc4ae696964bfbaec0a F src/vtab.c 527c180e9c5fca417c9167d02af4b5039f892b4b F src/walker.c 488c2660e13224ff70c0c82761118efb547f8f0d -F src/where.c 75b7f45bc02832445c244e2c6df4f7f5653148be +F src/where.c da2a0e132d642acc6afc4df2fe31ecd6f963c035 F tclinstaller.tcl 4356d9d94d2b5ed5e68f9f0c80c4df3048dd7617 F test/aggerror.test a867e273ef9e3d7919f03ef4f0e8c0d2767944f2 F test/alias.test c321c114a8a31a33e3cbda910fa39949f5d9dcb2 @@ -372,6 +372,7 @@ F test/incrvacuum_ioerr.test 57d2f5777ab13fa03b87b262a4ea1bad5cfc0291 F test/index.test cbf301cdb2da43e4eac636c3400c2439af1834ad F test/index2.test ee83c6b5e3173a3d7137140d945d9a5d4fdfb9d6 F test/index3.test 727d55dceb9a4ec36675057bb5becfc265e28ca6 +F test/indexedby.test b3fde1aed0790ad5e6366e0cf48f9cc34a3c7745 F test/insert.test aef273dd1cee84cc92407469e6bd1b3cdcb76908 F test/insert2.test 4f3a04d168c728ed5ec2c88842e772606c7ce435 F test/insert3.test 9a4ef3526fd3cca8b05278020ec3100448b4c677 @@ -406,7 +407,7 @@ F test/lock4.test 09d97d52cae18fadfe631552af9880dac6b3ae90 F test/lock5.test 904c20aec51d5dbff0a3aec6a4d35c5ae0257449 F test/lookaside.test 28f730199350f3912c122c23bab2f01910530c84 F test/main.test 187a9a1b5248ed74a83838c581c15ec6023b555b -F test/malloc.test 6ff6063f750d30741bc6d8c01b6ae5f94f5cf6f6 +F test/malloc.test 2fa351108503f0da80e9183a8157fbd943c5d533 F test/malloc3.test 094f8195fe8e409bd4da0f1d769f7745faec62c8 F test/malloc4.test 957337613002b7058a85116493a262f679f3a261 F test/malloc5.test c8d0f7673337e8a29afa558735ae937a0d629751 @@ -621,7 +622,7 @@ F tool/lempar.c 770dc64b74429daf9611676f43bfbd7c1bed0152 F tool/memleak.awk 4e7690a51bf3ed757e611273d43fe3f65b510133 F tool/memleak2.awk 9cc20c8e8f3c675efac71ea0721ee6874a1566e8 F tool/memleak3.tcl 7707006ee908cffff210c98158788d85bb3fcdbf -F tool/mkkeywordhash.c ef93810fc41fb3d3dbacf9a33a29be88ea99ffa9 +F tool/mkkeywordhash.c c219ee2b8b5b8e7011cccfa1caec62d9812e82e7 F tool/mkopts.tcl 66ac10d240cc6e86abd37dc908d50382f84ff46e x F tool/mksqlite3c.tcl 50f3ca0333694ef51ae4016c310af020c09006f4 F tool/mksqlite3internalh.tcl 7b43894e21bcb1bb39e11547ce7e38a063357e87 @@ -638,7 +639,7 @@ F tool/speedtest16.c c8a9c793df96db7e4933f0852abb7a03d48f2e81 F tool/speedtest2.tcl ee2149167303ba8e95af97873c575c3e0fab58ff F tool/speedtest8.c 1dbced29de5f59ba2ebf877edcadf171540374d1 F tool/speedtest8inst1.c 293327bc76823f473684d589a8160bde1f52c14e -P 83b7dd737a16555b9eb4ad9faacac3d705b0a90e -R e1b31f97badd065f62c08777c72ef7ab +P 1a91f3fd58608e258b60305d1d18c3d07d2e9c46 +R 8c1c7a684aaa38c556e33506eaf2c8a3 U danielk1977 -Z 1e0e51d60145cedc85e2ef54e96b33e8 +Z 40b4cbdd0428ffc473ce2e8ffc9b642c diff --git a/manifest.uuid b/manifest.uuid index 3b40eef29b..d54542d380 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -1a91f3fd58608e258b60305d1d18c3d07d2e9c46 \ No newline at end of file +98ca5580f5acd2e7b3ce512520ec0527f221505e \ No newline at end of file diff --git a/src/build.c b/src/build.c index 91c8323c70..2ed5d8692b 100644 --- a/src/build.c +++ b/src/build.c @@ -22,7 +22,7 @@ ** COMMIT ** ROLLBACK ** -** $Id: build.c,v 1.496 2008/08/20 16:35:10 drh Exp $ +** $Id: build.c,v 1.497 2008/10/06 05:32:19 danielk1977 Exp $ */ #include "sqliteInt.h" #include @@ -3052,7 +3052,6 @@ SrcList *sqlite3SrcListAppend( pItem->zName = sqlite3NameFromToken(db, pTable); pItem->zDatabase = sqlite3NameFromToken(db, pDatabase); pItem->iCursor = -1; - pItem->isPopulated = 0; pList->nSrc++; return pList; } @@ -3086,6 +3085,7 @@ void sqlite3SrcListDelete(sqlite3 *db, SrcList *pList){ sqlite3DbFree(db, pItem->zDatabase); sqlite3DbFree(db, pItem->zName); sqlite3DbFree(db, pItem->zAlias); + sqlite3DbFree(db, pItem->zIndex); sqlite3DeleteTable(pItem->pTab); sqlite3SelectDelete(db, pItem->pSelect); sqlite3ExprDelete(db, pItem->pOn); @@ -3116,6 +3116,7 @@ SrcList *sqlite3SrcListAppendFromTerm( Token *pTable, /* Name of the table to add to the FROM clause */ Token *pDatabase, /* Name of the database containing pTable */ Token *pAlias, /* The right-hand side of the AS subexpression */ + Token *pIndexedBy, /* Token from INDEXED BY clause, if any */ Select *pSubquery, /* A subquery used in place of a table name */ Expr *pOn, /* The ON clause of a join */ IdList *pUsing /* The USING clause of a join */ @@ -3133,6 +3134,13 @@ SrcList *sqlite3SrcListAppendFromTerm( if( pAlias && pAlias->n ){ pItem->zAlias = sqlite3NameFromToken(db, pAlias); } + if( pIndexedBy && pIndexedBy->n==1 && !pIndexedBy->z ){ + /* A "NOT INDEXED" clause was supplied. See parse.y + ** construct "indexed_opt" for details. */ + pItem->notIndexed = 1; + }else{ + pItem->zIndex = sqlite3NameFromToken(db, pIndexedBy); + } pItem->pSelect = pSubquery; pItem->pOn = pOn; pItem->pUsing = pUsing; diff --git a/src/delete.c b/src/delete.c index cc25c1b726..a9a887ec0e 100644 --- a/src/delete.c +++ b/src/delete.c @@ -12,7 +12,7 @@ ** This file contains C code routines that are called by the parser ** in order to generate code for DELETE FROM statements. ** -** $Id: delete.c,v 1.175 2008/09/01 21:59:43 shane Exp $ +** $Id: delete.c,v 1.176 2008/10/06 05:32:19 danielk1977 Exp $ */ #include "sqliteInt.h" @@ -106,7 +106,7 @@ void sqlite3MaterializeView( pWhere = sqlite3ExprDup(db, pWhere); viewName.z = (u8*)pView->zName; viewName.n = (unsigned int)strlen((const char*)viewName.z); - pFrom = sqlite3SrcListAppendFromTerm(pParse, 0, 0, 0, &viewName, pDup, 0,0); + pFrom = sqlite3SrcListAppendFromTerm(pParse, 0, 0, 0, &viewName,0,pDup,0,0); pDup = sqlite3SelectNew(pParse, 0, pFrom, pWhere, 0, 0, 0, 0, 0, 0); } sqlite3SelectDestInit(&dest, SRT_EphemTab, iCur); diff --git a/src/expr.c b/src/expr.c index b13bb99e0e..b5fc4f9d11 100644 --- a/src/expr.c +++ b/src/expr.c @@ -12,7 +12,7 @@ ** This file contains routines used for analyzing expressions and ** for generating VDBE code that evaluates expressions in SQLite. ** -** $Id: expr.c,v 1.396 2008/10/02 16:42:07 danielk1977 Exp $ +** $Id: expr.c,v 1.397 2008/10/06 05:32:19 danielk1977 Exp $ */ #include "sqliteInt.h" #include @@ -733,6 +733,9 @@ SrcList *sqlite3SrcListDup(sqlite3 *db, SrcList *p){ pNewItem->jointype = pOldItem->jointype; pNewItem->iCursor = pOldItem->iCursor; pNewItem->isPopulated = pOldItem->isPopulated; + pNewItem->zIndex = sqlite3DbStrDup(db, pOldItem->zIndex); + pNewItem->notIndexed = pOldItem->notIndexed; + pNewItem->pIndex = pOldItem->pIndex; pTab = pNewItem->pTab = pOldItem->pTab; if( pTab ){ pTab->nRef++; diff --git a/src/parse.y b/src/parse.y index 7ec6343177..4af16d422e 100644 --- a/src/parse.y +++ b/src/parse.y @@ -14,7 +14,7 @@ ** the parser. Lemon will also generate a header file containing ** numeric codes for all of the tokens. ** -** @(#) $Id: parse.y,v 1.252 2008/08/20 16:35:10 drh Exp $ +** @(#) $Id: parse.y,v 1.253 2008/10/06 05:32:19 danielk1977 Exp $ */ // All token codes are small integers with #defines that begin with "TK_" @@ -456,13 +456,13 @@ stl_prefix(A) ::= seltablist(X) joinop(Y). { if( A && A->nSrc>0 ) A->a[A->nSrc-1].jointype = Y; } stl_prefix(A) ::= . {A = 0;} -seltablist(A) ::= stl_prefix(X) nm(Y) dbnm(D) as(Z) on_opt(N) using_opt(U). { - A = sqlite3SrcListAppendFromTerm(pParse,X,&Y,&D,&Z,0,N,U); +seltablist(A) ::= stl_prefix(X) nm(Y) dbnm(D) as(Z) indexed_opt(I) on_opt(N) using_opt(U). { + A = sqlite3SrcListAppendFromTerm(pParse,X,&Y,&D,&Z,&I,0,N,U); } %ifndef SQLITE_OMIT_SUBQUERY seltablist(A) ::= stl_prefix(X) LP seltablist_paren(S) RP as(Z) on_opt(N) using_opt(U). { - A = sqlite3SrcListAppendFromTerm(pParse,X,0,0,&Z,S,N,U); + A = sqlite3SrcListAppendFromTerm(pParse,X,0,0,&Z,0,S,N,U); } // A seltablist_paren nonterminal represents anything in a FROM that @@ -499,6 +499,21 @@ joinop(X) ::= JOIN_KW(A) nm(B) nm(C) JOIN. on_opt(N) ::= ON expr(E). {N = E;} on_opt(N) ::= . {N = 0;} +// Note that this block abuses the Token type just a little. If there is +// no "INDEXED BY" clause, the returned token is empty (z==0 && n==0). If +// there is an INDEXED BY clause, then the token is populated as per normal, +// with z pointing to the token data and n containing the number of bytes +// in the token. +// +// If there is a "NOT INDEXED" clause, then (z==0 && n==1), which is +// normally illegal. The sqlite3SrcListAppendFromTerm() function +// recognizes and interprets this as a special case. +// +%type indexed_opt {Token} +indexed_opt(A) ::= . {A.z=0; A.n=0;} +indexed_opt(A) ::= INDEXED BY nm(X). {A = X;} +indexed_opt(A) ::= NOT INDEXED. {A.z=0; A.n=1;} + %type using_opt {IdList*} %destructor using_opt {sqlite3IdListDelete(pParse->db, $$);} using_opt(U) ::= USING LP inscollist(L) RP. {U = L;} diff --git a/src/select.c b/src/select.c index adbf9e432f..eebeb4cf41 100644 --- a/src/select.c +++ b/src/select.c @@ -12,7 +12,7 @@ ** This file contains C code routines that are called by the parser ** to handle SELECT statements in SQLite. ** -** $Id: select.c,v 1.476 2008/09/23 09:36:10 drh Exp $ +** $Id: select.c,v 1.477 2008/10/06 05:32:19 danielk1977 Exp $ */ #include "sqliteInt.h" @@ -2982,6 +2982,21 @@ static int selectExpander(Walker *pWalker, Select *p){ } #endif } + + /* Locate the index named by the INDEXED BY clause, if any. */ + if( pFrom->zIndex ){ + char *zIndex = pFrom->zIndex; + Index *pIdx; + for(pIdx=pTab->pIndex; + pIdx && sqlite3StrICmp(pIdx->zName, zIndex); + pIdx=pIdx->pNext + ); + if( !pIdx ){ + sqlite3ErrorMsg(pParse, "no such index: %s", zIndex, 0); + return WRC_Abort; + } + pFrom->pIndex = pIdx; + } } /* Process NATURAL keywords, and ON and USING clauses of joins. diff --git a/src/sqliteInt.h b/src/sqliteInt.h index daa85a7224..134886f4d4 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -11,7 +11,7 @@ ************************************************************************* ** Internal interface definitions for SQLite. ** -** @(#) $Id: sqliteInt.h,v 1.773 2008/10/02 13:50:56 danielk1977 Exp $ +** @(#) $Id: sqliteInt.h,v 1.774 2008/10/06 05:32:19 danielk1977 Exp $ */ #ifndef _SQLITEINT_H_ #define _SQLITEINT_H_ @@ -1448,6 +1448,9 @@ struct SrcList { Expr *pOn; /* The ON clause of a join */ IdList *pUsing; /* The USING clause of a join */ Bitmask colUsed; /* Bit N (1<" clause */ + Index *pIndex; /* Index structure corresponding to zIndex, if any */ } a[1]; /* One entry for each identifier on the list */ }; @@ -2139,7 +2142,7 @@ IdList *sqlite3IdListAppend(sqlite3*, IdList*, Token*); int sqlite3IdListIndex(IdList*,const char*); SrcList *sqlite3SrcListAppend(sqlite3*, SrcList*, Token*, Token*); SrcList *sqlite3SrcListAppendFromTerm(Parse*, SrcList*, Token*, Token*, Token*, - Select*, Expr*, IdList*); + Token*, Select*, Expr*, IdList*); void sqlite3SrcListShiftJoinType(SrcList*); void sqlite3SrcListAssignCursors(Parse*, SrcList*); void sqlite3IdListDelete(sqlite3*, IdList*); diff --git a/src/where.c b/src/where.c index 08dc448aa0..afb61b4ce3 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.323 2008/10/01 08:43:03 danielk1977 Exp $ +** $Id: where.c,v 1.324 2008/10/06 05:32:19 danielk1977 Exp $ */ #include "sqliteInt.h" @@ -1473,6 +1473,16 @@ static double bestVirtualIndex( ** * Whether or not there must be separate lookups in the ** index and in the main table. ** +** If there was an INDEXED BY clause attached to the table in the SELECT +** statement, then this function only considers strategies using the +** named index. If one cannot be found, then the returned cost is +** SQLITE_BIG_DBL. If a strategy can be found that uses the named index, +** then the cost is calculated in the usual way. +** +** If a NOT INDEXED clause was attached to the table in the SELECT +** statement, then no indexes are considered. However, the selected +** stategy may still take advantage of the tables built-in rowid +** index. */ static double bestIndex( Parse *pParse, /* The parsing context */ @@ -1500,6 +1510,9 @@ static double bestIndex( WHERETRACE(("bestIndex: tbl=%s notReady=%llx\n", pSrc->pTab->zName, notReady)); lowestCost = SQLITE_BIG_DBL; pProbe = pSrc->pTab->pIndex; + if( pSrc->notIndexed ){ + pProbe = 0; + } /* If the table has no indices and there are no terms in the where ** clause that refer to the ROWID, then we will never be able to do @@ -1516,74 +1529,77 @@ static double bestIndex( return 0.0; } - /* Check for a rowid=EXPR or rowid IN (...) constraints - */ - pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0); - if( pTerm ){ - Expr *pExpr; - *ppIndex = 0; - bestFlags = WHERE_ROWID_EQ; - if( pTerm->eOperator & WO_EQ ){ - /* Rowid== is always the best pick. Look no further. Because only - ** a single row is generated, output is always in sorted order */ - *pFlags = WHERE_ROWID_EQ | WHERE_UNIQUE; - *pnEq = 1; - WHERETRACE(("... best is rowid\n")); - return 0.0; - }else if( (pExpr = pTerm->pExpr)->pList!=0 ){ - /* Rowid IN (LIST): cost is NlogN where N is the number of list - ** elements. */ - lowestCost = pExpr->pList->nExpr; - lowestCost *= estLog(lowestCost); - }else{ - /* Rowid IN (SELECT): cost is NlogN where N is the number of rows - ** in the result of the inner select. We have no way to estimate - ** that value so make a wild guess. */ - lowestCost = 200; - } - WHERETRACE(("... rowid IN cost: %.9g\n", lowestCost)); - } - - /* Estimate the cost of a table scan. If we do not know how many - ** entries are in the table, use 1 million as a guess. + /* Check for a rowid=EXPR or rowid IN (...) constraints. If there was + ** an INDEXED BY clause attached to this table, skip this step. */ - cost = pProbe ? pProbe->aiRowEst[0] : 1000000; - WHERETRACE(("... table scan base cost: %.9g\n", cost)); - flags = WHERE_ROWID_RANGE; - - /* Check for constraints on a range of rowids in a table scan. - */ - pTerm = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE|WO_GT|WO_GE, 0); - if( pTerm ){ - if( findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0) ){ - flags |= WHERE_TOP_LIMIT; - cost /= 3; /* Guess that rowidEXPR eliminates two-thirds of rows */ + if( !pSrc->pIndex ){ + pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0); + if( pTerm ){ + Expr *pExpr; + *ppIndex = 0; + bestFlags = WHERE_ROWID_EQ; + if( pTerm->eOperator & WO_EQ ){ + /* Rowid== is always the best pick. Look no further. Because only + ** a single row is generated, output is always in sorted order */ + *pFlags = WHERE_ROWID_EQ | WHERE_UNIQUE; + *pnEq = 1; + WHERETRACE(("... best is rowid\n")); + return 0.0; + }else if( (pExpr = pTerm->pExpr)->pList!=0 ){ + /* Rowid IN (LIST): cost is NlogN where N is the number of list + ** elements. */ + lowestCost = pExpr->pList->nExpr; + lowestCost *= estLog(lowestCost); + }else{ + /* Rowid IN (SELECT): cost is NlogN where N is the number of rows + ** in the result of the inner select. We have no way to estimate + ** that value so make a wild guess. */ + lowestCost = 200; + } + WHERETRACE(("... rowid IN cost: %.9g\n", lowestCost)); } - WHERETRACE(("... rowid range reduces cost to %.9g\n", cost)); - }else{ - flags = 0; - } - - /* 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, pWC->pMaskSet, &rev) ){ - flags |= WHERE_ORDERBY|WHERE_ROWID_RANGE; - if( rev ){ - flags |= WHERE_REVERSE; + + /* Estimate the cost of a table scan. If we do not know how many + ** entries are in the table, use 1 million as a guess. + */ + cost = pProbe ? pProbe->aiRowEst[0] : 1000000; + WHERETRACE(("... table scan base cost: %.9g\n", cost)); + flags = WHERE_ROWID_RANGE; + + /* Check for constraints on a range of rowids in a table scan. + */ + pTerm = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE|WO_GT|WO_GE, 0); + if( pTerm ){ + if( findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0) ){ + flags |= WHERE_TOP_LIMIT; + cost /= 3; /* Guess that rowidEXPR eliminates two-thirds of rows */ } + WHERETRACE(("... rowid range reduces cost to %.9g\n", cost)); }else{ - cost += cost*estLog(cost); - WHERETRACE(("... sorting increases cost to %.9g\n", cost)); + flags = 0; + } + + /* 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, pWC->pMaskSet, &rev) ){ + flags |= WHERE_ORDERBY|WHERE_ROWID_RANGE; + if( rev ){ + flags |= WHERE_REVERSE; + } + }else{ + cost += cost*estLog(cost); + WHERETRACE(("... sorting increases cost to %.9g\n", cost)); + } + } + if( costpNext){ + if( pSrc->pIndex ){ + pProbe = pSrc->pIndex; + } + for(; pProbe; pProbe=(pSrc->pIndex ? 0 : pProbe->pNext)){ int i; /* Loop counter */ double inMultiplier = 1; @@ -2065,7 +2084,7 @@ WhereInfo *sqlite3WhereBegin( pWInfo = sqlite3DbMallocZero(db, sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel)); if( db->mallocFailed ){ - goto whereBeginNoMem; + goto whereBeginError; } pWInfo->nLevel = pTabList->nSrc; pWInfo->pParse = pParse; @@ -2112,7 +2131,7 @@ WhereInfo *sqlite3WhereBegin( */ exprAnalyzeAll(pTabList, &wc); if( db->mallocFailed ){ - goto whereBeginNoMem; + goto whereBeginError; } /* Chose the best index to use for each table in the FROM clause. @@ -2122,7 +2141,7 @@ WhereInfo *sqlite3WhereBegin( ** pWInfo->a[].pIdx The index to use for this level of the loop. ** pWInfo->a[].flags WHERE_xxx flags associated with pIdx ** pWInfo->a[].nEq The number of == and IN constraints - ** pWInfo->a[].iFrom When term of the FROM clause is being coded + ** pWInfo->a[].iFrom Which term of the FROM clause is being coded ** pWInfo->a[].iTabCur The VDBE cursor for the database table ** pWInfo->a[].iIdxCur The VDBE cursor for the index ** @@ -2219,6 +2238,18 @@ WhereInfo *sqlite3WhereBegin( } notReady &= ~getMask(&maskSet, pTabList->a[bestJ].iCursor); pLevel->iFrom = bestJ; + + /* Check that if the table scanned by this loop iteration had an + ** INDEXED BY clause attached to it, that the named index is being + ** used for the scan. If not, then query compilation has failed. + ** Return an error. + */ + pIdx = pTabList->a[bestJ].pIndex; + assert( !pIdx || !pBest || pIdx==pBest ); + if( pIdx && pBest!=pIdx ){ + sqlite3ErrorMsg(pParse, "cannot use index: %s", pIdx->zName); + goto whereBeginError; + } } WHERETRACE(("*** Optimizer Finished ***\n")); @@ -2778,7 +2809,7 @@ WhereInfo *sqlite3WhereBegin( return pWInfo; /* Jump here if malloc fails */ -whereBeginNoMem: +whereBeginError: whereClauseClear(&wc); whereInfoFree(pWInfo); return 0; diff --git a/test/indexedby.test b/test/indexedby.test new file mode 100644 index 0000000000..bb9a9bc0bf --- /dev/null +++ b/test/indexedby.test @@ -0,0 +1,151 @@ +# 2008 October 4 +# +# 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. +# +#*********************************************************************** +# +# $Id: indexedby.test,v 1.1 2008/10/06 05:32:19 danielk1977 Exp $ + +set testdir [file dirname $argv0] +source $testdir/tester.tcl + +# Create a schema with some indexes. +# +do_test indexedby-1.1 { + execsql { + CREATE TABLE t1(a, b); + CREATE INDEX i1 ON t1(a); + CREATE INDEX i2 ON t1(b); + + CREATE TABLE t2(c, d); + CREATE INDEX i3 ON t2(c); + CREATE INDEX i4 ON t2(d); + + CREATE VIEW v1 AS SELECT * FROM t1; + } +} {} + +# Explain Query Plan +# +proc EQP {sql} { + uplevel "execsql {EXPLAIN QUERY PLAN $sql}" +} + +# These tests are to check that "EXPLAIN QUERY PLAN" is working as expected. +# +do_test indexedby-1.2 { + EQP { select * from t1 WHERE a = 10; } +} {0 0 {TABLE t1 WITH INDEX i1}} +do_test indexedby-1.3 { + EQP { select * from t1 ; } +} {0 0 {TABLE t1}} +do_test indexedby-1.4 { + EQP { select * from t1, t2 WHERE c = 10; } +} {0 1 {TABLE t2 WITH INDEX i3} 1 0 {TABLE t1}} + +# Parser tests. Test that an INDEXED BY or NOT INDEX clause can be +# attached to a table in the FROM clause, but not to a sub-select or +# SQL view. Also test that specifying an index that does not exist or +# is attached to a different table is detected as an error. +# +do_test indexedby-2.1 { + execsql { SELECT * FROM t1 NOT INDEXED WHERE a = 'one' AND b = 'two'} +} {} +do_test indexedby-2.2 { + execsql { SELECT * FROM t1 INDEXED BY i1 WHERE a = 'one' AND b = 'two'} +} {} +do_test indexedby-2.3 { + execsql { SELECT * FROM t1 INDEXED BY i2 WHERE a = 'one' AND b = 'two'} +} {} + +do_test indexedby-2.4 { + catchsql { SELECT * FROM t1 INDEXED BY i3 WHERE a = 'one' AND b = 'two'} +} {1 {no such index: i3}} +do_test indexedby-2.5 { + catchsql { SELECT * FROM t1 INDEXED BY i5 WHERE a = 'one' AND b = 'two'} +} {1 {no such index: i5}} +do_test indexedby-2.6 { + catchsql { SELECT * FROM t1 INDEXED BY WHERE a = 'one' AND b = 'two'} +} {1 {near "WHERE": syntax error}} +do_test indexedby-2.7 { + catchsql { SELECT * FROM v1 INDEXED BY i1 WHERE a = 'one' } +} {1 {no such index: i1}} + +# Tests for single table cases. +# +do_test indexedby-3.1 { + EQP { SELECT * FROM t1 NOT INDEXED WHERE a = 'one' AND b = 'two'} +} {0 0 {TABLE t1}} +do_test indexedby-3.2 { + EQP { SELECT * FROM t1 INDEXED BY i1 WHERE a = 'one' AND b = 'two'} +} {0 0 {TABLE t1 WITH INDEX i1}} +do_test indexedby-3.3 { + EQP { SELECT * FROM t1 INDEXED BY i2 WHERE a = 'one' AND b = 'two'} +} {0 0 {TABLE t1 WITH INDEX i2}} +do_test indexedby-3.4 { + catchsql { SELECT * FROM t1 INDEXED BY i2 WHERE a = 'one' } +} {1 {cannot use index: i2}} +do_test indexedby-3.5 { + catchsql { SELECT * FROM t1 INDEXED BY i2 ORDER BY a } +} {1 {cannot use index: i2}} +do_test indexedby-3.6 { + catchsql { SELECT * FROM t1 INDEXED BY i1 WHERE a = 'one' } +} {0 {}} +do_test indexedby-3.7 { + catchsql { SELECT * FROM t1 INDEXED BY i1 ORDER BY a } +} {0 {}} + +# Tests for multiple table cases. +# +do_test indexedby-4.1 { + EQP { SELECT * FROM t1, t2 WHERE a = c } +} {0 0 {TABLE t1} 1 1 {TABLE t2 WITH INDEX i3}} +do_test indexedby-4.2 { + EQP { SELECT * FROM t1 INDEXED BY i1, t2 WHERE a = c } +} {0 1 {TABLE t2} 1 0 {TABLE t1 WITH INDEX i1}} + +# Test embedding an INDEXED BY in a CREATE VIEW statement. This block +# also tests that nothing bad happens if an index refered to by +# a CREATE VIEW statement is dropped and recreated. +# +do_test indexedby-5.1 { + execsql { + CREATE VIEW v2 AS SELECT * FROM t1 INDEXED BY i1 WHERE a > 5; + } + EQP { SELECT * FROM v2 } +} {0 0 {TABLE t1 WITH INDEX i1}} +do_test indexedby-5.2 { + EQP { SELECT * FROM v2 WHERE b = 10 } +} {0 0 {TABLE t1 WITH INDEX i1}} +do_test indexedby-5.3 { + execsql { DROP INDEX i1 } + catchsql { SELECT * FROM v2 } +} {1 {no such index: i1}} +do_test indexedby-5.4 { + # Recreate index i1 in such a way as it cannot be used by the view query. + execsql { CREATE INDEX i1 ON t1(b) } + catchsql { SELECT * FROM v2 } +} {1 {cannot use index: i1}} +do_test indexedby-5.5 { + # Drop and recreate index i1 again. This time, create it so that it can + # be used by the query. + execsql { DROP INDEX i1 ; CREATE INDEX i1 ON t1(a) } + catchsql { SELECT * FROM v2 } +} {0 {}} + +# Test that "NOT INDEXED" may use the rowid index, but not others. +# +do_test indexedby-6.1 { + EQP { SELECT * FROM t1 WHERE b = 10 ORDER BY rowid } +} {0 0 {TABLE t1 WITH INDEX i2 ORDER BY}} +do_test indexedby-6.2 { + EQP { SELECT * FROM t1 NOT INDEXED WHERE b = 10 ORDER BY rowid } +} {0 0 {TABLE t1 USING PRIMARY KEY ORDER BY}} + +finish_test + diff --git a/test/malloc.test b/test/malloc.test index dd3969f3d1..0b5677030a 100644 --- a/test/malloc.test +++ b/test/malloc.test @@ -16,7 +16,7 @@ # to see what happens in the library if a malloc were to really fail # due to an out-of-memory situation. # -# $Id: malloc.test,v 1.67 2008/09/23 16:41:30 danielk1977 Exp $ +# $Id: malloc.test,v 1.68 2008/10/06 05:32:19 danielk1977 Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl @@ -660,6 +660,17 @@ do_malloc_test 27 -tclprep { } } +# Test that malloc failures that occur while processing INDEXED BY +# clauses are handled correctly. +do_malloc_test 28 -sqlprep { + CREATE TABLE t1(a, b); + CREATE INDEX i1 ON t1(a); + CREATE VIEW v1 AS SELECT * FROM t1 INDEXED BY i1 WHERE a = 10; +} -sqlbody { + SELECT * FROM t1 INDEXED BY i1 ORDER BY a; + SELECT * FROM v1; +} + # Ensure that no file descriptors were leaked. do_test malloc-99.X { catch {db close} diff --git a/tool/mkkeywordhash.c b/tool/mkkeywordhash.c index 5515f1d8d9..c8f6eebe37 100644 --- a/tool/mkkeywordhash.c +++ b/tool/mkkeywordhash.c @@ -15,7 +15,7 @@ static const char zHdr[] = "**\n" "** The code in this file has been automatically generated by\n" "**\n" - "** $Header: /home/drh/sqlite/trans/cvs/sqlite/sqlite/tool/mkkeywordhash.c,v 1.31 2007/07/30 18:26:20 rse Exp $\n" + "** $Header: /home/drh/sqlite/trans/cvs/sqlite/sqlite/tool/mkkeywordhash.c,v 1.32 2008/10/06 05:32:19 danielk1977 Exp $\n" "**\n" "** The code in this file implements a function that determines whether\n" "** or not a given identifier is really an SQL keyword. The same thing\n" @@ -200,6 +200,7 @@ static Keyword aKeywordTable[] = { { "IMMEDIATE", "TK_IMMEDIATE", ALWAYS }, { "IN", "TK_IN", ALWAYS }, { "INDEX", "TK_INDEX", ALWAYS }, + { "INDEXED", "TK_INDEXED", ALWAYS }, { "INITIALLY", "TK_INITIALLY", FKEY }, { "INNER", "TK_JOIN_KW", ALWAYS }, { "INSERT", "TK_INSERT", ALWAYS }, -- 2.47.2