aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/build.c12
-rw-r--r--src/delete.c4
-rw-r--r--src/expr.c5
-rw-r--r--src/parse.y23
-rw-r--r--src/select.c17
-rw-r--r--src/sqliteInt.h7
-rw-r--r--src/where.c169
7 files changed, 156 insertions, 81 deletions
diff --git a/src/build.c b/src/build.c
index 91c8323c7..2ed5d8692 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 <ctype.h>
@@ -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 cc25c1b72..a9a887ec0 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 b13bb99e0..b5fc4f9d1 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 <ctype.h>
@@ -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 7ec634317..4af16d422 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 adbf9e432..eebeb4cf4 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 daa85a722..134886f4d 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<<N) set if column N or pTab is used */
+ u8 notIndexed; /* True if there is a NOT INDEXED clause */
+ char *zIndex; /* Identifier from "INDEXED BY <zIndex>" 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 08dc448aa..afb61b4ce 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 rowid<EXPR eliminates two-thirds or rows */
- }
- if( findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0) ){
- flags |= WHERE_BTM_LIMIT;
- cost /= 3; /* Guess that rowid>EXPR 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 rowid<EXPR eliminates two-thirds or rows */
+ }
+ if( findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0) ){
+ flags |= WHERE_BTM_LIMIT;
+ cost /= 3; /* Guess that rowid>EXPR 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( cost<lowestCost ){
+ lowestCost = cost;
+ bestFlags = flags;
}
- }
- if( cost<lowestCost ){
- lowestCost = cost;
- bestFlags = flags;
}
/* If the pSrc table is the right table of a LEFT JOIN then we may not
@@ -1599,7 +1615,10 @@ static double bestIndex(
/* Look at each index.
*/
- for(; pProbe; pProbe=pProbe->pNext){
+ 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;
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-21 14:17:21 +0000