Symaptic: os/persistentdata/persistentstorage/sql/SQLite364/where.c@260cb5ec6c19 (annotated)

sl@0	1	/*
sl@0	2	** 2001 September 15
sl@0	3	**
sl@0	4	** The author disclaims copyright to this source code. In place of
sl@0	5	** a legal notice, here is a blessing:
sl@0	6	**
sl@0	7	** May you do good and not evil.
sl@0	8	** May you find forgiveness for yourself and forgive others.
sl@0	9	** May you share freely, never taking more than you give.
sl@0	10	**
sl@0	11	*************************************************************************
sl@0	12	** This module contains C code that generates VDBE code used to process
sl@0	13	** the WHERE clause of SQL statements. This module is responsible for
sl@0	14	** generating the code that loops through a table looking for applicable
sl@0	15	** rows. Indices are selected and used to speed the search when doing
sl@0	16	** so is applicable. Because this module is responsible for selecting
sl@0	17	** indices, you might also think of this module as the "query optimizer".
sl@0	18	**
sl@0	19	** $Id: where.c,v 1.326 2008/10/11 16:47:36 drh Exp $
sl@0	20	*/
sl@0	21	#include "sqliteInt.h"
sl@0	22
sl@0	23	/*
sl@0	24	** The number of bits in a Bitmask. "BMS" means "BitMask Size".
sl@0	25	*/
sl@0	26	#define BMS (sizeof(Bitmask)*8)
sl@0	27
sl@0	28	/*
sl@0	29	** Trace output macros
sl@0	30	*/
sl@0	31	#if defined(SQLITE_TEST) \|\| defined(SQLITE_DEBUG)
sl@0	32	int sqlite3WhereTrace = 0;
sl@0	33	#endif
sl@0	34	#if 0
sl@0	35	# define WHERETRACE(X) if(sqlite3WhereTrace) sqlite3DebugPrintf X
sl@0	36	#else
sl@0	37	# define WHERETRACE(X)
sl@0	38	#endif
sl@0	39
sl@0	40	/* Forward reference
sl@0	41	*/
sl@0	42	typedef struct WhereClause WhereClause;
sl@0	43	typedef struct ExprMaskSet ExprMaskSet;
sl@0	44
sl@0	45	/*
sl@0	46	** The query generator uses an array of instances of this structure to
sl@0	47	** help it analyze the subexpressions of the WHERE clause. Each WHERE
sl@0	48	** clause subexpression is separated from the others by an AND operator.
sl@0	49	**
sl@0	50	** All WhereTerms are collected into a single WhereClause structure.
sl@0	51	** The following identity holds:
sl@0	52	**
sl@0	53	** WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm
sl@0	54	**
sl@0	55	** When a term is of the form:
sl@0	56	**
sl@0	57	** X <op> <expr>
sl@0	58	**
sl@0	59	** where X is a column name and <op> is one of certain operators,
sl@0	60	** then WhereTerm.leftCursor and WhereTerm.leftColumn record the
sl@0	61	** cursor number and column number for X. WhereTerm.operator records
sl@0	62	** the <op> using a bitmask encoding defined by WO_xxx below. The
sl@0	63	** use of a bitmask encoding for the operator allows us to search
sl@0	64	** quickly for terms that match any of several different operators.
sl@0	65	**
sl@0	66	** prereqRight and prereqAll record sets of cursor numbers,
sl@0	67	** but they do so indirectly. A single ExprMaskSet structure translates
sl@0	68	** cursor number into bits and the translated bit is stored in the prereq
sl@0	69	** fields. The translation is used in order to maximize the number of
sl@0	70	** bits that will fit in a Bitmask. The VDBE cursor numbers might be
sl@0	71	** spread out over the non-negative integers. For example, the cursor
sl@0	72	** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45. The ExprMaskSet
sl@0	73	** translates these sparse cursor numbers into consecutive integers
sl@0	74	** beginning with 0 in order to make the best possible use of the available
sl@0	75	** bits in the Bitmask. So, in the example above, the cursor numbers
sl@0	76	** would be mapped into integers 0 through 7.
sl@0	77	*/
sl@0	78	typedef struct WhereTerm WhereTerm;
sl@0	79	struct WhereTerm {
sl@0	80	Expr pExpr; / Pointer to the subexpression */
sl@0	81	i16 iParent; /* Disable pWC->a[iParent] when this term disabled */
sl@0	82	i16 leftCursor; /* Cursor number of X in "X <op> <expr>" */
sl@0	83	i16 leftColumn; /* Column number of X in "X <op> <expr>" */
sl@0	84	u16 eOperator; /* A WO_xx value describing <op> */
sl@0	85	u8 flags; /* Bit flags. See below */
sl@0	86	u8 nChild; /* Number of children that must disable us */
sl@0	87	WhereClause pWC; / The clause this term is part of */
sl@0	88	Bitmask prereqRight; /* Bitmask of tables used by pRight */
sl@0	89	Bitmask prereqAll; /* Bitmask of tables referenced by p */
sl@0	90	};
sl@0	91
sl@0	92	/*
sl@0	93	** Allowed values of WhereTerm.flags
sl@0	94	*/
sl@0	95	#define TERM_DYNAMIC 0x01 /* Need to call sqlite3ExprDelete(db, pExpr) */
sl@0	96	#define TERM_VIRTUAL 0x02 /* Added by the optimizer. Do not code */
sl@0	97	#define TERM_CODED 0x04 /* This term is already coded */
sl@0	98	#define TERM_COPIED 0x08 /* Has a child */
sl@0	99	#define TERM_OR_OK 0x10 /* Used during OR-clause processing */
sl@0	100
sl@0	101	/*
sl@0	102	** An instance of the following structure holds all information about a
sl@0	103	** WHERE clause. Mostly this is a container for one or more WhereTerms.
sl@0	104	*/
sl@0	105	struct WhereClause {
sl@0	106	Parse pParse; / The parser context */
sl@0	107	ExprMaskSet pMaskSet; / Mapping of table indices to bitmasks */
sl@0	108	int nTerm; /* Number of terms */
sl@0	109	int nSlot; /* Number of entries in a[] */
sl@0	110	WhereTerm a; / Each a[] describes a term of the WHERE cluase */
sl@0	111	WhereTerm aStatic[10]; /* Initial static space for a[] */
sl@0	112	};
sl@0	113
sl@0	114	/*
sl@0	115	** An instance of the following structure keeps track of a mapping
sl@0	116	** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.
sl@0	117	**
sl@0	118	** The VDBE cursor numbers are small integers contained in
sl@0	119	** SrcList_item.iCursor and Expr.iTable fields. For any given WHERE
sl@0	120	** clause, the cursor numbers might not begin with 0 and they might
sl@0	121	** contain gaps in the numbering sequence. But we want to make maximum
sl@0	122	** use of the bits in our bitmasks. This structure provides a mapping
sl@0	123	** from the sparse cursor numbers into consecutive integers beginning
sl@0	124	** with 0.
sl@0	125	**
sl@0	126	** If ExprMaskSet.ix[A]==B it means that The A-th bit of a Bitmask
sl@0	127	** corresponds VDBE cursor number B. The A-th bit of a bitmask is 1<<A.
sl@0	128	**
sl@0	129	** For example, if the WHERE clause expression used these VDBE
sl@0	130	** cursors: 4, 5, 8, 29, 57, 73. Then the ExprMaskSet structure
sl@0	131	** would map those cursor numbers into bits 0 through 5.
sl@0	132	**
sl@0	133	** Note that the mapping is not necessarily ordered. In the example
sl@0	134	** above, the mapping might go like this: 4->3, 5->1, 8->2, 29->0,
sl@0	135	** 57->5, 73->4. Or one of 719 other combinations might be used. It
sl@0	136	** does not really matter. What is important is that sparse cursor
sl@0	137	** numbers all get mapped into bit numbers that begin with 0 and contain
sl@0	138	** no gaps.
sl@0	139	*/
sl@0	140	struct ExprMaskSet {
sl@0	141	int n; /* Number of assigned cursor values */
sl@0	142	int ix[sizeof(Bitmask)8]; / Cursor assigned to each bit */
sl@0	143	};
sl@0	144
sl@0	145
sl@0	146	/*
sl@0	147	** Bitmasks for the operators that indices are able to exploit. An
sl@0	148	** OR-ed combination of these values can be used when searching for
sl@0	149	** terms in the where clause.
sl@0	150	*/
sl@0	151	#define WO_IN 1
sl@0	152	#define WO_EQ 2
sl@0	153	#define WO_LT (WO_EQ<<(TK_LT-TK_EQ))
sl@0	154	#define WO_LE (WO_EQ<<(TK_LE-TK_EQ))
sl@0	155	#define WO_GT (WO_EQ<<(TK_GT-TK_EQ))
sl@0	156	#define WO_GE (WO_EQ<<(TK_GE-TK_EQ))
sl@0	157	#define WO_MATCH 64
sl@0	158	#define WO_ISNULL 128
sl@0	159
sl@0	160	/*
sl@0	161	** Value for flags returned by bestIndex().
sl@0	162	**
sl@0	163	** The least significant byte is reserved as a mask for WO_ values above.
sl@0	164	** The WhereLevel.flags field is usually set to WO_IN\|WO_EQ\|WO_ISNULL.
sl@0	165	** But if the table is the right table of a left join, WhereLevel.flags
sl@0	166	** is set to WO_IN\|WO_EQ. The WhereLevel.flags field can then be used as
sl@0	167	** the "op" parameter to findTerm when we are resolving equality constraints.
sl@0	168	** ISNULL constraints will then not be used on the right table of a left
sl@0	169	** join. Tickets #2177 and #2189.
sl@0	170	*/
sl@0	171	#define WHERE_ROWID_EQ 0x000100 /* rowid=EXPR or rowid IN (...) */
sl@0	172	#define WHERE_ROWID_RANGE 0x000200 /* rowid<EXPR and/or rowid>EXPR */
sl@0	173	#define WHERE_COLUMN_EQ 0x001000 /* x=EXPR or x IN (...) */
sl@0	174	#define WHERE_COLUMN_RANGE 0x002000 /* x<EXPR and/or x>EXPR */
sl@0	175	#define WHERE_COLUMN_IN 0x004000 /* x IN (...) */
sl@0	176	#define WHERE_TOP_LIMIT 0x010000 /* x<EXPR or x<=EXPR constraint */
sl@0	177	#define WHERE_BTM_LIMIT 0x020000 /* x>EXPR or x>=EXPR constraint */
sl@0	178	#define WHERE_IDX_ONLY 0x080000 /* Use index only - omit table */
sl@0	179	#define WHERE_ORDERBY 0x100000 /* Output will appear in correct order */
sl@0	180	#define WHERE_REVERSE 0x200000 /* Scan in reverse order */
sl@0	181	#define WHERE_UNIQUE 0x400000 /* Selects no more than one row */
sl@0	182	#define WHERE_VIRTUALTABLE 0x800000 /* Use virtual-table processing */
sl@0	183
sl@0	184	/*
sl@0	185	** Initialize a preallocated WhereClause structure.
sl@0	186	*/
sl@0	187	static void whereClauseInit(
sl@0	188	WhereClause pWC, / The WhereClause to be initialized */
sl@0	189	Parse pParse, / The parsing context */
sl@0	190	ExprMaskSet pMaskSet / Mapping from table indices to bitmasks */
sl@0	191	){
sl@0	192	pWC->pParse = pParse;
sl@0	193	pWC->pMaskSet = pMaskSet;
sl@0	194	pWC->nTerm = 0;
sl@0	195	pWC->nSlot = ArraySize(pWC->aStatic);
sl@0	196	pWC->a = pWC->aStatic;
sl@0	197	}
sl@0	198
sl@0	199	/*
sl@0	200	** Deallocate a WhereClause structure. The WhereClause structure
sl@0	201	** itself is not freed. This routine is the inverse of whereClauseInit().
sl@0	202	*/
sl@0	203	static void whereClauseClear(WhereClause *pWC){
sl@0	204	int i;
sl@0	205	WhereTerm *a;
sl@0	206	sqlite3 *db = pWC->pParse->db;
sl@0	207	for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){
sl@0	208	if( a->flags & TERM_DYNAMIC ){
sl@0	209	sqlite3ExprDelete(db, a->pExpr);
sl@0	210	}
sl@0	211	}
sl@0	212	if( pWC->a!=pWC->aStatic ){
sl@0	213	sqlite3DbFree(db, pWC->a);
sl@0	214	}
sl@0	215	}
sl@0	216
sl@0	217	/*
sl@0	218	** Add a new entries to the WhereClause structure. Increase the allocated
sl@0	219	** space as necessary.
sl@0	220	**
sl@0	221	** If the flags argument includes TERM_DYNAMIC, then responsibility
sl@0	222	** for freeing the expression p is assumed by the WhereClause object.
sl@0	223	**
sl@0	224	** WARNING: This routine might reallocate the space used to store
sl@0	225	** WhereTerms. All pointers to WhereTerms should be invalidated after
sl@0	226	** calling this routine. Such pointers may be reinitialized by referencing
sl@0	227	** the pWC->a[] array.
sl@0	228	*/
sl@0	229	static int whereClauseInsert(WhereClause pWC, Expr p, int flags){
sl@0	230	WhereTerm *pTerm;
sl@0	231	int idx;
sl@0	232	if( pWC->nTerm>=pWC->nSlot ){
sl@0	233	WhereTerm *pOld = pWC->a;
sl@0	234	sqlite3 *db = pWC->pParse->db;
sl@0	235	pWC->a = sqlite3DbMallocRaw(db, sizeof(pWC->a[0])pWC->nSlot2 );
sl@0	236	if( pWC->a==0 ){
sl@0	237	if( flags & TERM_DYNAMIC ){
sl@0	238	sqlite3ExprDelete(db, p);
sl@0	239	}
sl@0	240	pWC->a = pOld;
sl@0	241	return 0;
sl@0	242	}
sl@0	243	memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
sl@0	244	if( pOld!=pWC->aStatic ){
sl@0	245	sqlite3DbFree(db, pOld);
sl@0	246	}
sl@0	247	pWC->nSlot *= 2;
sl@0	248	}
sl@0	249	pTerm = &pWC->a[idx = pWC->nTerm];
sl@0	250	pWC->nTerm++;
sl@0	251	pTerm->pExpr = p;
sl@0	252	pTerm->flags = flags;
sl@0	253	pTerm->pWC = pWC;
sl@0	254	pTerm->iParent = -1;
sl@0	255	return idx;
sl@0	256	}
sl@0	257
sl@0	258	/*
sl@0	259	** This routine identifies subexpressions in the WHERE clause where
sl@0	260	** each subexpression is separated by the AND operator or some other
sl@0	261	** operator specified in the op parameter. The WhereClause structure
sl@0	262	** is filled with pointers to subexpressions. For example:
sl@0	263	**
sl@0	264	** WHERE a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
sl@0	265	** \________/ \_______________/ \________________/
sl@0	266	** slot[0] slot[1] slot[2]
sl@0	267	**
sl@0	268	** The original WHERE clause in pExpr is unaltered. All this routine
sl@0	269	** does is make slot[] entries point to substructure within pExpr.
sl@0	270	**
sl@0	271	** In the previous sentence and in the diagram, "slot[]" refers to
sl@0	272	** the WhereClause.a[] array. This array grows as needed to contain
sl@0	273	** all terms of the WHERE clause.
sl@0	274	*/
sl@0	275	static void whereSplit(WhereClause pWC, Expr pExpr, int op){
sl@0	276	if( pExpr==0 ) return;
sl@0	277	if( pExpr->op!=op ){
sl@0	278	whereClauseInsert(pWC, pExpr, 0);
sl@0	279	}else{
sl@0	280	whereSplit(pWC, pExpr->pLeft, op);
sl@0	281	whereSplit(pWC, pExpr->pRight, op);
sl@0	282	}
sl@0	283	}
sl@0	284
sl@0	285	/*
sl@0	286	** Initialize an expression mask set
sl@0	287	*/
sl@0	288	#define initMaskSet(P) memset(P, 0, sizeof(*P))
sl@0	289
sl@0	290	/*
sl@0	291	** Return the bitmask for the given cursor number. Return 0 if
sl@0	292	** iCursor is not in the set.
sl@0	293	*/
sl@0	294	static Bitmask getMask(ExprMaskSet *pMaskSet, int iCursor){
sl@0	295	int i;
sl@0	296	for(i=0; i<pMaskSet->n; i++){
sl@0	297	if( pMaskSet->ix[i]==iCursor ){
sl@0	298	return ((Bitmask)1)<<i;
sl@0	299	}
sl@0	300	}
sl@0	301	return 0;
sl@0	302	}
sl@0	303
sl@0	304	/*
sl@0	305	** Create a new mask for cursor iCursor.
sl@0	306	**
sl@0	307	** There is one cursor per table in the FROM clause. The number of
sl@0	308	** tables in the FROM clause is limited by a test early in the
sl@0	309	** sqlite3WhereBegin() routine. So we know that the pMaskSet->ix[]
sl@0	310	** array will never overflow.
sl@0	311	*/
sl@0	312	static void createMask(ExprMaskSet *pMaskSet, int iCursor){
sl@0	313	assert( pMaskSet->n < ArraySize(pMaskSet->ix) );
sl@0	314	pMaskSet->ix[pMaskSet->n++] = iCursor;
sl@0	315	}
sl@0	316
sl@0	317	/*
sl@0	318	** This routine walks (recursively) an expression tree and generates
sl@0	319	** a bitmask indicating which tables are used in that expression
sl@0	320	** tree.
sl@0	321	**
sl@0	322	** In order for this routine to work, the calling function must have
sl@0	323	** previously invoked sqlite3ResolveExprNames() on the expression. See
sl@0	324	** the header comment on that routine for additional information.
sl@0	325	** The sqlite3ResolveExprNames() routines looks for column names and
sl@0	326	** sets their opcodes to TK_COLUMN and their Expr.iTable fields to
sl@0	327	** the VDBE cursor number of the table. This routine just has to
sl@0	328	** translate the cursor numbers into bitmask values and OR all
sl@0	329	** the bitmasks together.
sl@0	330	*/
sl@0	331	static Bitmask exprListTableUsage(ExprMaskSet, ExprList);
sl@0	332	static Bitmask exprSelectTableUsage(ExprMaskSet, Select);
sl@0	333	static Bitmask exprTableUsage(ExprMaskSet pMaskSet, Expr p){
sl@0	334	Bitmask mask = 0;
sl@0	335	if( p==0 ) return 0;
sl@0	336	if( p->op==TK_COLUMN ){
sl@0	337	mask = getMask(pMaskSet, p->iTable);
sl@0	338	return mask;
sl@0	339	}
sl@0	340	mask = exprTableUsage(pMaskSet, p->pRight);
sl@0	341	mask \|= exprTableUsage(pMaskSet, p->pLeft);
sl@0	342	mask \|= exprListTableUsage(pMaskSet, p->pList);
sl@0	343	mask \|= exprSelectTableUsage(pMaskSet, p->pSelect);
sl@0	344	return mask;
sl@0	345	}
sl@0	346	static Bitmask exprListTableUsage(ExprMaskSet pMaskSet, ExprList pList){
sl@0	347	int i;
sl@0	348	Bitmask mask = 0;
sl@0	349	if( pList ){
sl@0	350	for(i=0; i<pList->nExpr; i++){
sl@0	351	mask \|= exprTableUsage(pMaskSet, pList->a[i].pExpr);
sl@0	352	}
sl@0	353	}
sl@0	354	return mask;
sl@0	355	}
sl@0	356	static Bitmask exprSelectTableUsage(ExprMaskSet pMaskSet, Select pS){
sl@0	357	Bitmask mask = 0;
sl@0	358	while( pS ){
sl@0	359	mask \|= exprListTableUsage(pMaskSet, pS->pEList);
sl@0	360	mask \|= exprListTableUsage(pMaskSet, pS->pGroupBy);
sl@0	361	mask \|= exprListTableUsage(pMaskSet, pS->pOrderBy);
sl@0	362	mask \|= exprTableUsage(pMaskSet, pS->pWhere);
sl@0	363	mask \|= exprTableUsage(pMaskSet, pS->pHaving);
sl@0	364	pS = pS->pPrior;
sl@0	365	}
sl@0	366	return mask;
sl@0	367	}
sl@0	368
sl@0	369	/*
sl@0	370	** Return TRUE if the given operator is one of the operators that is
sl@0	371	** allowed for an indexable WHERE clause term. The allowed operators are
sl@0	372	** "=", "<", ">", "<=", ">=", and "IN".
sl@0	373	*/
sl@0	374	static int allowedOp(int op){
sl@0	375	assert( TK_GT>TK_EQ && TK_GT<TK_GE );
sl@0	376	assert( TK_LT>TK_EQ && TK_LT<TK_GE );
sl@0	377	assert( TK_LE>TK_EQ && TK_LE<TK_GE );
sl@0	378	assert( TK_GE==TK_EQ+4 );
sl@0	379	return op==TK_IN \|\| (op>=TK_EQ && op<=TK_GE) \|\| op==TK_ISNULL;
sl@0	380	}
sl@0	381
sl@0	382	/*
sl@0	383	** Swap two objects of type T.
sl@0	384	*/
sl@0	385	#define SWAP(TYPE,A,B) {TYPE t=A; A=B; B=t;}
sl@0	386
sl@0	387	/*
sl@0	388	** Commute a comparison operator. Expressions of the form "X op Y"
sl@0	389	** are converted into "Y op X".
sl@0	390	**
sl@0	391	** If a collation sequence is associated with either the left or right
sl@0	392	** side of the comparison, it remains associated with the same side after
sl@0	393	** the commutation. So "Y collate NOCASE op X" becomes
sl@0	394	** "X collate NOCASE op Y". This is because any collation sequence on
sl@0	395	** the left hand side of a comparison overrides any collation sequence
sl@0	396	** attached to the right. For the same reason the EP_ExpCollate flag
sl@0	397	** is not commuted.
sl@0	398	*/
sl@0	399	static void exprCommute(Parse pParse, Expr pExpr){
sl@0	400	u16 expRight = (pExpr->pRight->flags & EP_ExpCollate);
sl@0	401	u16 expLeft = (pExpr->pLeft->flags & EP_ExpCollate);
sl@0	402	assert( allowedOp(pExpr->op) && pExpr->op!=TK_IN );
sl@0	403	pExpr->pRight->pColl = sqlite3ExprCollSeq(pParse, pExpr->pRight);
sl@0	404	pExpr->pLeft->pColl = sqlite3ExprCollSeq(pParse, pExpr->pLeft);
sl@0	405	SWAP(CollSeq*,pExpr->pRight->pColl,pExpr->pLeft->pColl);
sl@0	406	pExpr->pRight->flags = (pExpr->pRight->flags & ~EP_ExpCollate) \| expLeft;
sl@0	407	pExpr->pLeft->flags = (pExpr->pLeft->flags & ~EP_ExpCollate) \| expRight;
sl@0	408	SWAP(Expr*,pExpr->pRight,pExpr->pLeft);
sl@0	409	if( pExpr->op>=TK_GT ){
sl@0	410	assert( TK_LT==TK_GT+2 );
sl@0	411	assert( TK_GE==TK_LE+2 );
sl@0	412	assert( TK_GT>TK_EQ );
sl@0	413	assert( TK_GT<TK_LE );
sl@0	414	assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );
sl@0	415	pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;
sl@0	416	}
sl@0	417	}
sl@0	418
sl@0	419	/*
sl@0	420	** Translate from TK_xx operator to WO_xx bitmask.
sl@0	421	*/
sl@0	422	static int operatorMask(int op){
sl@0	423	int c;
sl@0	424	assert( allowedOp(op) );
sl@0	425	if( op==TK_IN ){
sl@0	426	c = WO_IN;
sl@0	427	}else if( op==TK_ISNULL ){
sl@0	428	c = WO_ISNULL;
sl@0	429	}else{
sl@0	430	c = WO_EQ<<(op-TK_EQ);
sl@0	431	}
sl@0	432	assert( op!=TK_ISNULL \|\| c==WO_ISNULL );
sl@0	433	assert( op!=TK_IN \|\| c==WO_IN );
sl@0	434	assert( op!=TK_EQ \|\| c==WO_EQ );
sl@0	435	assert( op!=TK_LT \|\| c==WO_LT );
sl@0	436	assert( op!=TK_LE \|\| c==WO_LE );
sl@0	437	assert( op!=TK_GT \|\| c==WO_GT );
sl@0	438	assert( op!=TK_GE \|\| c==WO_GE );
sl@0	439	return c;
sl@0	440	}
sl@0	441
sl@0	442	/*
sl@0	443	** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
sl@0	444	** where X is a reference to the iColumn of table iCur and <op> is one of
sl@0	445	** the WO_xx operator codes specified by the op parameter.
sl@0	446	** Return a pointer to the term. Return 0 if not found.
sl@0	447	*/
sl@0	448	static WhereTerm *findTerm(
sl@0	449	WhereClause pWC, / The WHERE clause to be searched */
sl@0	450	int iCur, /* Cursor number of LHS */
sl@0	451	int iColumn, /* Column number of LHS */
sl@0	452	Bitmask notReady, /* RHS must not overlap with this mask */
sl@0	453	u16 op, /* Mask of WO_xx values describing operator */
sl@0	454	Index pIdx / Must be compatible with this index, if not NULL */
sl@0	455	){
sl@0	456	WhereTerm *pTerm;
sl@0	457	int k;
sl@0	458	assert( iCur>=0 );
sl@0	459	for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
sl@0	460	if( pTerm->leftCursor==iCur
sl@0	461	&& (pTerm->prereqRight & notReady)==0
sl@0	462	&& pTerm->leftColumn==iColumn
sl@0	463	&& (pTerm->eOperator & op)!=0
sl@0	464	){
sl@0	465	if( pIdx && pTerm->eOperator!=WO_ISNULL ){
sl@0	466	Expr *pX = pTerm->pExpr;
sl@0	467	CollSeq *pColl;
sl@0	468	char idxaff;
sl@0	469	int j;
sl@0	470	Parse *pParse = pWC->pParse;
sl@0	471
sl@0	472	idxaff = pIdx->pTable->aCol[iColumn].affinity;
sl@0	473	if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
sl@0	474
sl@0	475	/* Figure out the collation sequence required from an index for
sl@0	476	** it to be useful for optimising expression pX. Store this
sl@0	477	** value in variable pColl.
sl@0	478	*/
sl@0	479	assert(pX->pLeft);
sl@0	480	pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
sl@0	481	if( !pColl ){
sl@0	482	pColl = pParse->db->pDfltColl;
sl@0	483	}
sl@0	484
sl@0	485	for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
sl@0	486	if( NEVER(j>=pIdx->nColumn) ) return 0;
sl@0	487	}
sl@0	488	if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
sl@0	489	}
sl@0	490	return pTerm;
sl@0	491	}
sl@0	492	}
sl@0	493	return 0;
sl@0	494	}
sl@0	495
sl@0	496	/* Forward reference */
sl@0	497	static void exprAnalyze(SrcList, WhereClause, int);
sl@0	498
sl@0	499	/*
sl@0	500	** Call exprAnalyze on all terms in a WHERE clause.
sl@0	501	**
sl@0	502	**
sl@0	503	*/
sl@0	504	static void exprAnalyzeAll(
sl@0	505	SrcList pTabList, / the FROM clause */
sl@0	506	WhereClause pWC / the WHERE clause to be analyzed */
sl@0	507	){
sl@0	508	int i;
sl@0	509	for(i=pWC->nTerm-1; i>=0; i--){
sl@0	510	exprAnalyze(pTabList, pWC, i);
sl@0	511	}
sl@0	512	}
sl@0	513
sl@0	514	#ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
sl@0	515	/*
sl@0	516	** Check to see if the given expression is a LIKE or GLOB operator that
sl@0	517	** can be optimized using inequality constraints. Return TRUE if it is
sl@0	518	** so and false if not.
sl@0	519	**
sl@0	520	** In order for the operator to be optimizible, the RHS must be a string
sl@0	521	** literal that does not begin with a wildcard.
sl@0	522	*/
sl@0	523	static int isLikeOrGlob(
sl@0	524	Parse pParse, / Parsing and code generating context */
sl@0	525	Expr pExpr, / Test this expression */
sl@0	526	int pnPattern, / Number of non-wildcard prefix characters */
sl@0	527	int pisComplete, / True if the only wildcard is % in the last character */
sl@0	528	int pnoCase / True if uppercase is equivalent to lowercase */
sl@0	529	){
sl@0	530	const char *z;
sl@0	531	Expr pRight, pLeft;
sl@0	532	ExprList *pList;
sl@0	533	int c, cnt;
sl@0	534	char wc[3];
sl@0	535	CollSeq *pColl;
sl@0	536	sqlite3 *db = pParse->db;
sl@0	537
sl@0	538	if( !sqlite3IsLikeFunction(db, pExpr, pnoCase, wc) ){
sl@0	539	return 0;
sl@0	540	}
sl@0	541	#ifdef SQLITE_EBCDIC
sl@0	542	if( *pnoCase ) return 0;
sl@0	543	#endif
sl@0	544	pList = pExpr->pList;
sl@0	545	pRight = pList->a[0].pExpr;
sl@0	546	if( pRight->op!=TK_STRING
sl@0	547	&& (pRight->op!=TK_REGISTER \|\| pRight->iColumn!=TK_STRING) ){
sl@0	548	return 0;
sl@0	549	}
sl@0	550	pLeft = pList->a[1].pExpr;
sl@0	551	if( pLeft->op!=TK_COLUMN ){
sl@0	552	return 0;
sl@0	553	}
sl@0	554	pColl = sqlite3ExprCollSeq(pParse, pLeft);
sl@0	555	assert( pColl!=0 \|\| pLeft->iColumn==-1 );
sl@0	556	if( pColl==0 ){
sl@0	557	/* No collation is defined for the ROWID. Use the default. */
sl@0	558	pColl = db->pDfltColl;
sl@0	559	}
sl@0	560	if( (pColl->type!=SQLITE_COLL_BINARY \|\| *pnoCase) &&
sl@0	561	(pColl->type!=SQLITE_COLL_NOCASE \|\| !*pnoCase) ){
sl@0	562	return 0;
sl@0	563	}
sl@0	564	sqlite3DequoteExpr(db, pRight);
sl@0	565	z = (char *)pRight->token.z;
sl@0	566	cnt = 0;
sl@0	567	if( z ){
sl@0	568	while( (c=z[cnt])!=0 && c!=wc[0] && c!=wc[1] && c!=wc[2] ){ cnt++; }
sl@0	569	}
sl@0	570	if( cnt==0 \|\| 255==(u8)z[cnt] ){
sl@0	571	return 0;
sl@0	572	}
sl@0	573	*pisComplete = z[cnt]==wc[0] && z[cnt+1]==0;
sl@0	574	*pnPattern = cnt;
sl@0	575	return 1;
sl@0	576	}
sl@0	577	#endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
sl@0	578
sl@0	579
sl@0	580	#ifndef SQLITE_OMIT_VIRTUALTABLE
sl@0	581	/*
sl@0	582	** Check to see if the given expression is of the form
sl@0	583	**
sl@0	584	** column MATCH expr
sl@0	585	**
sl@0	586	** If it is then return TRUE. If not, return FALSE.
sl@0	587	*/
sl@0	588	static int isMatchOfColumn(
sl@0	589	Expr pExpr / Test this expression */
sl@0	590	){
sl@0	591	ExprList *pList;
sl@0	592
sl@0	593	if( pExpr->op!=TK_FUNCTION ){
sl@0	594	return 0;
sl@0	595	}
sl@0	596	if( pExpr->token.n!=5 \|\|
sl@0	597	sqlite3StrNICmp((const char*)pExpr->token.z,"match",5)!=0 ){
sl@0	598	return 0;
sl@0	599	}
sl@0	600	pList = pExpr->pList;
sl@0	601	if( pList->nExpr!=2 ){
sl@0	602	return 0;
sl@0	603	}
sl@0	604	if( pList->a[1].pExpr->op != TK_COLUMN ){
sl@0	605	return 0;
sl@0	606	}
sl@0	607	return 1;
sl@0	608	}
sl@0	609	#endif /* SQLITE_OMIT_VIRTUALTABLE */
sl@0	610
sl@0	611	/*
sl@0	612	** If the pBase expression originated in the ON or USING clause of
sl@0	613	** a join, then transfer the appropriate markings over to derived.
sl@0	614	*/
sl@0	615	static void transferJoinMarkings(Expr pDerived, Expr pBase){
sl@0	616	pDerived->flags \|= pBase->flags & EP_FromJoin;
sl@0	617	pDerived->iRightJoinTable = pBase->iRightJoinTable;
sl@0	618	}
sl@0	619
sl@0	620	#if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
sl@0	621	/*
sl@0	622	** Return TRUE if the given term of an OR clause can be converted
sl@0	623	** into an IN clause. The iCursor and iColumn define the left-hand
sl@0	624	** side of the IN clause.
sl@0	625	**
sl@0	626	** The context is that we have multiple OR-connected equality terms
sl@0	627	** like this:
sl@0	628	**
sl@0	629	** a=<expr1> OR a=<expr2> OR b=<expr3> OR ...
sl@0	630	**
sl@0	631	** The pOrTerm input to this routine corresponds to a single term of
sl@0	632	** this OR clause. In order for the term to be a candidate for
sl@0	633	** conversion to an IN operator, the following must be true:
sl@0	634	**
sl@0	635	** * The left-hand side of the term must be the column which
sl@0	636	** is identified by iCursor and iColumn.
sl@0	637	**
sl@0	638	** * If the right-hand side is also a column, then the affinities
sl@0	639	** of both right and left sides must be such that no type
sl@0	640	** conversions are required on the right. (Ticket #2249)
sl@0	641	**
sl@0	642	** If both of these conditions are true, then return true. Otherwise
sl@0	643	** return false.
sl@0	644	*/
sl@0	645	static int orTermIsOptCandidate(WhereTerm *pOrTerm, int iCursor, int iColumn){
sl@0	646	int affLeft, affRight;
sl@0	647	assert( pOrTerm->eOperator==WO_EQ );
sl@0	648	if( pOrTerm->leftCursor!=iCursor ){
sl@0	649	return 0;
sl@0	650	}
sl@0	651	if( pOrTerm->leftColumn!=iColumn ){
sl@0	652	return 0;
sl@0	653	}
sl@0	654	affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);
sl@0	655	if( affRight==0 ){
sl@0	656	return 1;
sl@0	657	}
sl@0	658	affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);
sl@0	659	if( affRight!=affLeft ){
sl@0	660	return 0;
sl@0	661	}
sl@0	662	return 1;
sl@0	663	}
sl@0	664
sl@0	665	/*
sl@0	666	** Return true if the given term of an OR clause can be ignored during
sl@0	667	** a check to make sure all OR terms are candidates for optimization.
sl@0	668	** In other words, return true if a call to the orTermIsOptCandidate()
sl@0	669	** above returned false but it is not necessary to disqualify the
sl@0	670	** optimization.
sl@0	671	**
sl@0	672	** Suppose the original OR phrase was this:
sl@0	673	**
sl@0	674	** a=4 OR a=11 OR a=b
sl@0	675	**
sl@0	676	** During analysis, the third term gets flipped around and duplicate
sl@0	677	** so that we are left with this:
sl@0	678	**
sl@0	679	** a=4 OR a=11 OR a=b OR b=a
sl@0	680	**
sl@0	681	** Since the last two terms are duplicates, only one of them
sl@0	682	** has to qualify in order for the whole phrase to qualify. When
sl@0	683	** this routine is called, we know that pOrTerm did not qualify.
sl@0	684	** This routine merely checks to see if pOrTerm has a duplicate that
sl@0	685	** might qualify. If there is a duplicate that has not yet been
sl@0	686	** disqualified, then return true. If there are no duplicates, or
sl@0	687	** the duplicate has also been disqualified, return false.
sl@0	688	*/
sl@0	689	static int orTermHasOkDuplicate(WhereClause pOr, WhereTerm pOrTerm){
sl@0	690	if( pOrTerm->flags & TERM_COPIED ){
sl@0	691	/* This is the original term. The duplicate is to the left had
sl@0	692	** has not yet been analyzed and thus has not yet been disqualified. */
sl@0	693	return 1;
sl@0	694	}
sl@0	695	if( (pOrTerm->flags & TERM_VIRTUAL)!=0
sl@0	696	&& (pOr->a[pOrTerm->iParent].flags & TERM_OR_OK)!=0 ){
sl@0	697	/* This is a duplicate term. The original qualified so this one
sl@0	698	** does not have to. */
sl@0	699	return 1;
sl@0	700	}
sl@0	701	/* This is either a singleton term or else it is a duplicate for
sl@0	702	** which the original did not qualify. Either way we are done for. */
sl@0	703	return 0;
sl@0	704	}
sl@0	705	#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
sl@0	706
sl@0	707	/*
sl@0	708	** The input to this routine is an WhereTerm structure with only the
sl@0	709	** "pExpr" field filled in. The job of this routine is to analyze the
sl@0	710	** subexpression and populate all the other fields of the WhereTerm
sl@0	711	** structure.
sl@0	712	**
sl@0	713	** If the expression is of the form "<expr> <op> X" it gets commuted
sl@0	714	** to the standard form of "X <op> <expr>". If the expression is of
sl@0	715	** the form "X <op> Y" where both X and Y are columns, then the original
sl@0	716	** expression is unchanged and a new virtual expression of the form
sl@0	717	** "Y <op> X" is added to the WHERE clause and analyzed separately.
sl@0	718	*/
sl@0	719	static void exprAnalyze(
sl@0	720	SrcList pSrc, / the FROM clause */
sl@0	721	WhereClause pWC, / the WHERE clause */
sl@0	722	int idxTerm /* Index of the term to be analyzed */
sl@0	723	){
sl@0	724	WhereTerm *pTerm;
sl@0	725	ExprMaskSet *pMaskSet;
sl@0	726	Expr *pExpr;
sl@0	727	Bitmask prereqLeft;
sl@0	728	Bitmask prereqAll;
sl@0	729	Bitmask extraRight = 0;
sl@0	730	int nPattern;
sl@0	731	int isComplete;
sl@0	732	int noCase;
sl@0	733	int op;
sl@0	734	Parse *pParse = pWC->pParse;
sl@0	735	sqlite3 *db = pParse->db;
sl@0	736
sl@0	737	if( db->mallocFailed ){
sl@0	738	return;
sl@0	739	}
sl@0	740	pTerm = &pWC->a[idxTerm];
sl@0	741	pMaskSet = pWC->pMaskSet;
sl@0	742	pExpr = pTerm->pExpr;
sl@0	743	prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);
sl@0	744	op = pExpr->op;
sl@0	745	if( op==TK_IN ){
sl@0	746	assert( pExpr->pRight==0 );
sl@0	747	pTerm->prereqRight = exprListTableUsage(pMaskSet, pExpr->pList)
sl@0	748	\| exprSelectTableUsage(pMaskSet, pExpr->pSelect);
sl@0	749	}else if( op==TK_ISNULL ){
sl@0	750	pTerm->prereqRight = 0;
sl@0	751	}else{
sl@0	752	pTerm->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);
sl@0	753	}
sl@0	754	prereqAll = exprTableUsage(pMaskSet, pExpr);
sl@0	755	if( ExprHasProperty(pExpr, EP_FromJoin) ){
sl@0	756	Bitmask x = getMask(pMaskSet, pExpr->iRightJoinTable);
sl@0	757	prereqAll \|= x;
sl@0	758	extraRight = x-1; /* ON clause terms may not be used with an index
sl@0	759	** on left table of a LEFT JOIN. Ticket #3015 */
sl@0	760	}
sl@0	761	pTerm->prereqAll = prereqAll;
sl@0	762	pTerm->leftCursor = -1;
sl@0	763	pTerm->iParent = -1;
sl@0	764	pTerm->eOperator = 0;
sl@0	765	if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
sl@0	766	Expr *pLeft = pExpr->pLeft;
sl@0	767	Expr *pRight = pExpr->pRight;
sl@0	768	if( pLeft->op==TK_COLUMN ){
sl@0	769	pTerm->leftCursor = pLeft->iTable;
sl@0	770	pTerm->leftColumn = pLeft->iColumn;
sl@0	771	pTerm->eOperator = operatorMask(op);
sl@0	772	}
sl@0	773	if( pRight && pRight->op==TK_COLUMN ){
sl@0	774	WhereTerm *pNew;
sl@0	775	Expr *pDup;
sl@0	776	if( pTerm->leftCursor>=0 ){
sl@0	777	int idxNew;
sl@0	778	pDup = sqlite3ExprDup(db, pExpr);
sl@0	779	if( db->mallocFailed ){
sl@0	780	sqlite3ExprDelete(db, pDup);
sl@0	781	return;
sl@0	782	}
sl@0	783	idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL\|TERM_DYNAMIC);
sl@0	784	if( idxNew==0 ) return;
sl@0	785	pNew = &pWC->a[idxNew];
sl@0	786	pNew->iParent = idxTerm;
sl@0	787	pTerm = &pWC->a[idxTerm];
sl@0	788	pTerm->nChild = 1;
sl@0	789	pTerm->flags \|= TERM_COPIED;
sl@0	790	}else{
sl@0	791	pDup = pExpr;
sl@0	792	pNew = pTerm;
sl@0	793	}
sl@0	794	exprCommute(pParse, pDup);
sl@0	795	pLeft = pDup->pLeft;
sl@0	796	pNew->leftCursor = pLeft->iTable;
sl@0	797	pNew->leftColumn = pLeft->iColumn;
sl@0	798	pNew->prereqRight = prereqLeft;
sl@0	799	pNew->prereqAll = prereqAll;
sl@0	800	pNew->eOperator = operatorMask(pDup->op);
sl@0	801	}
sl@0	802	}
sl@0	803
sl@0	804	#ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
sl@0	805	/* If a term is the BETWEEN operator, create two new virtual terms
sl@0	806	** that define the range that the BETWEEN implements.
sl@0	807	*/
sl@0	808	else if( pExpr->op==TK_BETWEEN ){
sl@0	809	ExprList *pList = pExpr->pList;
sl@0	810	int i;
sl@0	811	static const u8 ops[] = {TK_GE, TK_LE};
sl@0	812	assert( pList!=0 );
sl@0	813	assert( pList->nExpr==2 );
sl@0	814	for(i=0; i<2; i++){
sl@0	815	Expr *pNewExpr;
sl@0	816	int idxNew;
sl@0	817	pNewExpr = sqlite3Expr(db, ops[i], sqlite3ExprDup(db, pExpr->pLeft),
sl@0	818	sqlite3ExprDup(db, pList->a[i].pExpr), 0);
sl@0	819	idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL\|TERM_DYNAMIC);
sl@0	820	exprAnalyze(pSrc, pWC, idxNew);
sl@0	821	pTerm = &pWC->a[idxTerm];
sl@0	822	pWC->a[idxNew].iParent = idxTerm;
sl@0	823	}
sl@0	824	pTerm->nChild = 2;
sl@0	825	}
sl@0	826	#endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */
sl@0	827
sl@0	828	#if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
sl@0	829	/* Attempt to convert OR-connected terms into an IN operator so that
sl@0	830	** they can make use of indices. Example:
sl@0	831	**
sl@0	832	** x = expr1 OR expr2 = x OR x = expr3
sl@0	833	**
sl@0	834	** is converted into
sl@0	835	**
sl@0	836	** x IN (expr1,expr2,expr3)
sl@0	837	**
sl@0	838	** This optimization must be omitted if OMIT_SUBQUERY is defined because
sl@0	839	** the compiler for the the IN operator is part of sub-queries.
sl@0	840	*/
sl@0	841	else if( pExpr->op==TK_OR ){
sl@0	842	int ok;
sl@0	843	int i, j;
sl@0	844	int iColumn, iCursor;
sl@0	845	WhereClause sOr;
sl@0	846	WhereTerm *pOrTerm;
sl@0	847
sl@0	848	assert( (pTerm->flags & TERM_DYNAMIC)==0 );
sl@0	849	whereClauseInit(&sOr, pWC->pParse, pMaskSet);
sl@0	850	whereSplit(&sOr, pExpr, TK_OR);
sl@0	851	exprAnalyzeAll(pSrc, &sOr);
sl@0	852	assert( sOr.nTerm>=2 );
sl@0	853	j = 0;
sl@0	854	if( db->mallocFailed ) goto or_not_possible;
sl@0	855	do{
sl@0	856	assert( j<sOr.nTerm );
sl@0	857	iColumn = sOr.a[j].leftColumn;
sl@0	858	iCursor = sOr.a[j].leftCursor;
sl@0	859	ok = iCursor>=0;
sl@0	860	for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){
sl@0	861	if( pOrTerm->eOperator!=WO_EQ ){
sl@0	862	goto or_not_possible;
sl@0	863	}
sl@0	864	if( orTermIsOptCandidate(pOrTerm, iCursor, iColumn) ){
sl@0	865	pOrTerm->flags \|= TERM_OR_OK;
sl@0	866	}else if( orTermHasOkDuplicate(&sOr, pOrTerm) ){
sl@0	867	pOrTerm->flags &= ~TERM_OR_OK;
sl@0	868	}else{
sl@0	869	ok = 0;
sl@0	870	}
sl@0	871	}
sl@0	872	}while( !ok && (sOr.a[j++].flags & TERM_COPIED)!=0 && j<2 );
sl@0	873	if( ok ){
sl@0	874	ExprList *pList = 0;
sl@0	875	Expr pNew, pDup;
sl@0	876	Expr *pLeft = 0;
sl@0	877	for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0; i--, pOrTerm++){
sl@0	878	if( (pOrTerm->flags & TERM_OR_OK)==0 ) continue;
sl@0	879	pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight);
sl@0	880	pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup, 0);
sl@0	881	pLeft = pOrTerm->pExpr->pLeft;
sl@0	882	}
sl@0	883	assert( pLeft!=0 );
sl@0	884	pDup = sqlite3ExprDup(db, pLeft);
sl@0	885	pNew = sqlite3Expr(db, TK_IN, pDup, 0, 0);
sl@0	886	if( pNew ){
sl@0	887	int idxNew;
sl@0	888	transferJoinMarkings(pNew, pExpr);
sl@0	889	pNew->pList = pList;
sl@0	890	idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL\|TERM_DYNAMIC);
sl@0	891	exprAnalyze(pSrc, pWC, idxNew);
sl@0	892	pTerm = &pWC->a[idxTerm];
sl@0	893	pWC->a[idxNew].iParent = idxTerm;
sl@0	894	pTerm->nChild = 1;
sl@0	895	}else{
sl@0	896	sqlite3ExprListDelete(db, pList);
sl@0	897	}
sl@0	898	}
sl@0	899	or_not_possible:
sl@0	900	whereClauseClear(&sOr);
sl@0	901	}
sl@0	902	#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
sl@0	903
sl@0	904	#ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
sl@0	905	/* Add constraints to reduce the search space on a LIKE or GLOB
sl@0	906	** operator.
sl@0	907	**
sl@0	908	** A like pattern of the form "x LIKE 'abc%'" is changed into constraints
sl@0	909	**
sl@0	910	** x>='abc' AND x<'abd' AND x LIKE 'abc%'
sl@0	911	**
sl@0	912	** The last character of the prefix "abc" is incremented to form the
sl@0	913	** termination condition "abd".
sl@0	914	*/
sl@0	915	if( isLikeOrGlob(pParse, pExpr, &nPattern, &isComplete, &noCase) ){
sl@0	916	Expr pLeft, pRight;
sl@0	917	Expr pStr1, pStr2;
sl@0	918	Expr pNewExpr1, pNewExpr2;
sl@0	919	int idxNew1, idxNew2;
sl@0	920
sl@0	921	pLeft = pExpr->pList->a[1].pExpr;
sl@0	922	pRight = pExpr->pList->a[0].pExpr;
sl@0	923	pStr1 = sqlite3PExpr(pParse, TK_STRING, 0, 0, 0);
sl@0	924	if( pStr1 ){
sl@0	925	sqlite3TokenCopy(db, &pStr1->token, &pRight->token);
sl@0	926	pStr1->token.n = nPattern;
sl@0	927	pStr1->flags = EP_Dequoted;
sl@0	928	}
sl@0	929	pStr2 = sqlite3ExprDup(db, pStr1);
sl@0	930	if( !db->mallocFailed ){
sl@0	931	u8 c, *pC;
sl@0	932	assert( pStr2->token.dyn );
sl@0	933	pC = (u8*)&pStr2->token.z[nPattern-1];
sl@0	934	c = *pC;
sl@0	935	if( noCase ){
sl@0	936	if( c=='@' ) isComplete = 0;
sl@0	937	c = sqlite3UpperToLower[c];
sl@0	938	}
sl@0	939	*pC = c + 1;
sl@0	940	}
sl@0	941	pNewExpr1 = sqlite3PExpr(pParse, TK_GE, sqlite3ExprDup(db,pLeft), pStr1, 0);
sl@0	942	idxNew1 = whereClauseInsert(pWC, pNewExpr1, TERM_VIRTUAL\|TERM_DYNAMIC);
sl@0	943	exprAnalyze(pSrc, pWC, idxNew1);
sl@0	944	pNewExpr2 = sqlite3PExpr(pParse, TK_LT, sqlite3ExprDup(db,pLeft), pStr2, 0);
sl@0	945	idxNew2 = whereClauseInsert(pWC, pNewExpr2, TERM_VIRTUAL\|TERM_DYNAMIC);
sl@0	946	exprAnalyze(pSrc, pWC, idxNew2);
sl@0	947	pTerm = &pWC->a[idxTerm];
sl@0	948	if( isComplete ){
sl@0	949	pWC->a[idxNew1].iParent = idxTerm;
sl@0	950	pWC->a[idxNew2].iParent = idxTerm;
sl@0	951	pTerm->nChild = 2;
sl@0	952	}
sl@0	953	}
sl@0	954	#endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
sl@0	955
sl@0	956	#ifndef SQLITE_OMIT_VIRTUALTABLE
sl@0	957	/* Add a WO_MATCH auxiliary term to the constraint set if the
sl@0	958	** current expression is of the form: column MATCH expr.
sl@0	959	** This information is used by the xBestIndex methods of
sl@0	960	** virtual tables. The native query optimizer does not attempt
sl@0	961	** to do anything with MATCH functions.
sl@0	962	*/
sl@0	963	if( isMatchOfColumn(pExpr) ){
sl@0	964	int idxNew;
sl@0	965	Expr pRight, pLeft;
sl@0	966	WhereTerm *pNewTerm;
sl@0	967	Bitmask prereqColumn, prereqExpr;
sl@0	968
sl@0	969	pRight = pExpr->pList->a[0].pExpr;
sl@0	970	pLeft = pExpr->pList->a[1].pExpr;
sl@0	971	prereqExpr = exprTableUsage(pMaskSet, pRight);
sl@0	972	prereqColumn = exprTableUsage(pMaskSet, pLeft);
sl@0	973	if( (prereqExpr & prereqColumn)==0 ){
sl@0	974	Expr *pNewExpr;
sl@0	975	pNewExpr = sqlite3Expr(db, TK_MATCH, 0, sqlite3ExprDup(db, pRight), 0);
sl@0	976	idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL\|TERM_DYNAMIC);
sl@0	977	pNewTerm = &pWC->a[idxNew];
sl@0	978	pNewTerm->prereqRight = prereqExpr;
sl@0	979	pNewTerm->leftCursor = pLeft->iTable;
sl@0	980	pNewTerm->leftColumn = pLeft->iColumn;
sl@0	981	pNewTerm->eOperator = WO_MATCH;
sl@0	982	pNewTerm->iParent = idxTerm;
sl@0	983	pTerm = &pWC->a[idxTerm];
sl@0	984	pTerm->nChild = 1;
sl@0	985	pTerm->flags \|= TERM_COPIED;
sl@0	986	pNewTerm->prereqAll = pTerm->prereqAll;
sl@0	987	}
sl@0	988	}
sl@0	989	#endif /* SQLITE_OMIT_VIRTUALTABLE */
sl@0	990
sl@0	991	/* Prevent ON clause terms of a LEFT JOIN from being used to drive
sl@0	992	** an index for tables to the left of the join.
sl@0	993	*/
sl@0	994	pTerm->prereqRight \|= extraRight;
sl@0	995	}
sl@0	996
sl@0	997	/*
sl@0	998	** Return TRUE if any of the expressions in pList->a[iFirst...] contain
sl@0	999	** a reference to any table other than the iBase table.
sl@0	1000	*/
sl@0	1001	static int referencesOtherTables(
sl@0	1002	ExprList pList, / Search expressions in ths list */
sl@0	1003	ExprMaskSet pMaskSet, / Mapping from tables to bitmaps */
sl@0	1004	int iFirst, /* Be searching with the iFirst-th expression */
sl@0	1005	int iBase /* Ignore references to this table */
sl@0	1006	){
sl@0	1007	Bitmask allowed = ~getMask(pMaskSet, iBase);
sl@0	1008	while( iFirst<pList->nExpr ){
sl@0	1009	if( (exprTableUsage(pMaskSet, pList->a[iFirst++].pExpr)&allowed)!=0 ){
sl@0	1010	return 1;
sl@0	1011	}
sl@0	1012	}
sl@0	1013	return 0;
sl@0	1014	}
sl@0	1015
sl@0	1016
sl@0	1017	/*
sl@0	1018	** This routine decides if pIdx can be used to satisfy the ORDER BY
sl@0	1019	** clause. If it can, it returns 1. If pIdx cannot satisfy the
sl@0	1020	** ORDER BY clause, this routine returns 0.
sl@0	1021	**
sl@0	1022	** pOrderBy is an ORDER BY clause from a SELECT statement. pTab is the
sl@0	1023	** left-most table in the FROM clause of that same SELECT statement and
sl@0	1024	** the table has a cursor number of "base". pIdx is an index on pTab.
sl@0	1025	**
sl@0	1026	** nEqCol is the number of columns of pIdx that are used as equality
sl@0	1027	** constraints. Any of these columns may be missing from the ORDER BY
sl@0	1028	** clause and the match can still be a success.
sl@0	1029	**
sl@0	1030	** All terms of the ORDER BY that match against the index must be either
sl@0	1031	** ASC or DESC. (Terms of the ORDER BY clause past the end of a UNIQUE
sl@0	1032	** index do not need to satisfy this constraint.) The *pbRev value is
sl@0	1033	** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
sl@0	1034	** the ORDER BY clause is all ASC.
sl@0	1035	*/
sl@0	1036	static int isSortingIndex(
sl@0	1037	Parse pParse, / Parsing context */
sl@0	1038	ExprMaskSet pMaskSet, / Mapping from table indices to bitmaps */
sl@0	1039	Index pIdx, / The index we are testing */
sl@0	1040	int base, /* Cursor number for the table to be sorted */
sl@0	1041	ExprList pOrderBy, / The ORDER BY clause */
sl@0	1042	int nEqCol, /* Number of index columns with == constraints */
sl@0	1043	int pbRev / Set to 1 if ORDER BY is DESC */
sl@0	1044	){
sl@0	1045	int i, j; /* Loop counters */
sl@0	1046	int sortOrder = 0; /* XOR of index and ORDER BY sort direction */
sl@0	1047	int nTerm; /* Number of ORDER BY terms */
sl@0	1048	struct ExprList_item pTerm; / A term of the ORDER BY clause */
sl@0	1049	sqlite3 *db = pParse->db;
sl@0	1050
sl@0	1051	assert( pOrderBy!=0 );
sl@0	1052	nTerm = pOrderBy->nExpr;
sl@0	1053	assert( nTerm>0 );
sl@0	1054
sl@0	1055	/* Match terms of the ORDER BY clause against columns of
sl@0	1056	** the index.
sl@0	1057	**
sl@0	1058	** Note that indices have pIdx->nColumn regular columns plus
sl@0	1059	** one additional column containing the rowid. The rowid column
sl@0	1060	** of the index is also allowed to match against the ORDER BY
sl@0	1061	** clause.
sl@0	1062	*/
sl@0	1063	for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<=pIdx->nColumn; i++){
sl@0	1064	Expr pExpr; / The expression of the ORDER BY pTerm */
sl@0	1065	CollSeq pColl; / The collating sequence of pExpr */
sl@0	1066	int termSortOrder; /* Sort order for this term */
sl@0	1067	int iColumn; /* The i-th column of the index. -1 for rowid */
sl@0	1068	int iSortOrder; /* 1 for DESC, 0 for ASC on the i-th index term */
sl@0	1069	const char zColl; / Name of the collating sequence for i-th index term */
sl@0	1070
sl@0	1071	pExpr = pTerm->pExpr;
sl@0	1072	if( pExpr->op!=TK_COLUMN \|\| pExpr->iTable!=base ){
sl@0	1073	/* Can not use an index sort on anything that is not a column in the
sl@0	1074	** left-most table of the FROM clause */
sl@0	1075	break;
sl@0	1076	}
sl@0	1077	pColl = sqlite3ExprCollSeq(pParse, pExpr);
sl@0	1078	if( !pColl ){
sl@0	1079	pColl = db->pDfltColl;
sl@0	1080	}
sl@0	1081	if( i<pIdx->nColumn ){
sl@0	1082	iColumn = pIdx->aiColumn[i];
sl@0	1083	if( iColumn==pIdx->pTable->iPKey ){
sl@0	1084	iColumn = -1;
sl@0	1085	}
sl@0	1086	iSortOrder = pIdx->aSortOrder[i];
sl@0	1087	zColl = pIdx->azColl[i];
sl@0	1088	}else{
sl@0	1089	iColumn = -1;
sl@0	1090	iSortOrder = 0;
sl@0	1091	zColl = pColl->zName;
sl@0	1092	}
sl@0	1093	if( pExpr->iColumn!=iColumn \|\| sqlite3StrICmp(pColl->zName, zColl) ){
sl@0	1094	/* Term j of the ORDER BY clause does not match column i of the index */
sl@0	1095	if( i<nEqCol ){
sl@0	1096	/* If an index column that is constrained by == fails to match an
sl@0	1097	** ORDER BY term, that is OK. Just ignore that column of the index
sl@0	1098	*/
sl@0	1099	continue;
sl@0	1100	}else if( i==pIdx->nColumn ){
sl@0	1101	/* Index column i is the rowid. All other terms match. */
sl@0	1102	break;
sl@0	1103	}else{
sl@0	1104	/* If an index column fails to match and is not constrained by ==
sl@0	1105	** then the index cannot satisfy the ORDER BY constraint.
sl@0	1106	*/
sl@0	1107	return 0;
sl@0	1108	}
sl@0	1109	}
sl@0	1110	assert( pIdx->aSortOrder!=0 );
sl@0	1111	assert( pTerm->sortOrder==0 \|\| pTerm->sortOrder==1 );
sl@0	1112	assert( iSortOrder==0 \|\| iSortOrder==1 );
sl@0	1113	termSortOrder = iSortOrder ^ pTerm->sortOrder;
sl@0	1114	if( i>nEqCol ){
sl@0	1115	if( termSortOrder!=sortOrder ){
sl@0	1116	/* Indices can only be used if all ORDER BY terms past the
sl@0	1117	** equality constraints are all either DESC or ASC. */
sl@0	1118	return 0;
sl@0	1119	}
sl@0	1120	}else{
sl@0	1121	sortOrder = termSortOrder;
sl@0	1122	}
sl@0	1123	j++;
sl@0	1124	pTerm++;
sl@0	1125	if( iColumn<0 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
sl@0	1126	/* If the indexed column is the primary key and everything matches
sl@0	1127	** so far and none of the ORDER BY terms to the right reference other
sl@0	1128	** tables in the join, then we are assured that the index can be used
sl@0	1129	** to sort because the primary key is unique and so none of the other
sl@0	1130	** columns will make any difference
sl@0	1131	*/
sl@0	1132	j = nTerm;
sl@0	1133	}
sl@0	1134	}
sl@0	1135
sl@0	1136	*pbRev = sortOrder!=0;
sl@0	1137	if( j>=nTerm ){
sl@0	1138	/* All terms of the ORDER BY clause are covered by this index so
sl@0	1139	** this index can be used for sorting. */
sl@0	1140	return 1;
sl@0	1141	}
sl@0	1142	if( pIdx->onError!=OE_None && i==pIdx->nColumn
sl@0	1143	&& !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
sl@0	1144	/* All terms of this index match some prefix of the ORDER BY clause
sl@0	1145	** and the index is UNIQUE and no terms on the tail of the ORDER BY
sl@0	1146	** clause reference other tables in a join. If this is all true then
sl@0	1147	** the order by clause is superfluous. */
sl@0	1148	return 1;
sl@0	1149	}
sl@0	1150	return 0;
sl@0	1151	}
sl@0	1152
sl@0	1153	/*
sl@0	1154	** Check table to see if the ORDER BY clause in pOrderBy can be satisfied
sl@0	1155	** by sorting in order of ROWID. Return true if so and set *pbRev to be
sl@0	1156	** true for reverse ROWID and false for forward ROWID order.
sl@0	1157	*/
sl@0	1158	static int sortableByRowid(
sl@0	1159	int base, /* Cursor number for table to be sorted */
sl@0	1160	ExprList pOrderBy, / The ORDER BY clause */
sl@0	1161	ExprMaskSet pMaskSet, / Mapping from tables to bitmaps */
sl@0	1162	int pbRev / Set to 1 if ORDER BY is DESC */
sl@0	1163	){
sl@0	1164	Expr *p;
sl@0	1165
sl@0	1166	assert( pOrderBy!=0 );
sl@0	1167	assert( pOrderBy->nExpr>0 );
sl@0	1168	p = pOrderBy->a[0].pExpr;
sl@0	1169	if( p->op==TK_COLUMN && p->iTable==base && p->iColumn==-1
sl@0	1170	&& !referencesOtherTables(pOrderBy, pMaskSet, 1, base) ){
sl@0	1171	*pbRev = pOrderBy->a[0].sortOrder;
sl@0	1172	return 1;
sl@0	1173	}
sl@0	1174	return 0;
sl@0	1175	}
sl@0	1176
sl@0	1177	/*
sl@0	1178	** Prepare a crude estimate of the logarithm of the input value.
sl@0	1179	** The results need not be exact. This is only used for estimating
sl@0	1180	** the total cost of performing operations with O(logN) or O(NlogN)
sl@0	1181	** complexity. Because N is just a guess, it is no great tragedy if
sl@0	1182	** logN is a little off.
sl@0	1183	*/
sl@0	1184	static double estLog(double N){
sl@0	1185	double logN = 1;
sl@0	1186	double x = 10;
sl@0	1187	while( N>x ){
sl@0	1188	logN += 1;
sl@0	1189	x *= 10;
sl@0	1190	}
sl@0	1191	return logN;
sl@0	1192	}
sl@0	1193
sl@0	1194	/*
sl@0	1195	** Two routines for printing the content of an sqlite3_index_info
sl@0	1196	** structure. Used for testing and debugging only. If neither
sl@0	1197	** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
sl@0	1198	** are no-ops.
sl@0	1199	*/
sl@0	1200	#if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(SQLITE_DEBUG)
sl@0	1201	static void TRACE_IDX_INPUTS(sqlite3_index_info *p){
sl@0	1202	int i;
sl@0	1203	if( !sqlite3WhereTrace ) return;
sl@0	1204	for(i=0; i<p->nConstraint; i++){
sl@0	1205	sqlite3DebugPrintf(" constraint[%d]: col=%d termid=%d op=%d usabled=%d\n",
sl@0	1206	i,
sl@0	1207	p->aConstraint[i].iColumn,
sl@0	1208	p->aConstraint[i].iTermOffset,
sl@0	1209	p->aConstraint[i].op,
sl@0	1210	p->aConstraint[i].usable);
sl@0	1211	}
sl@0	1212	for(i=0; i<p->nOrderBy; i++){
sl@0	1213	sqlite3DebugPrintf(" orderby[%d]: col=%d desc=%d\n",
sl@0	1214	i,
sl@0	1215	p->aOrderBy[i].iColumn,
sl@0	1216	p->aOrderBy[i].desc);
sl@0	1217	}
sl@0	1218	}
sl@0	1219	static void TRACE_IDX_OUTPUTS(sqlite3_index_info *p){
sl@0	1220	int i;
sl@0	1221	if( !sqlite3WhereTrace ) return;
sl@0	1222	for(i=0; i<p->nConstraint; i++){
sl@0	1223	sqlite3DebugPrintf(" usage[%d]: argvIdx=%d omit=%d\n",
sl@0	1224	i,
sl@0	1225	p->aConstraintUsage[i].argvIndex,
sl@0	1226	p->aConstraintUsage[i].omit);
sl@0	1227	}
sl@0	1228	sqlite3DebugPrintf(" idxNum=%d\n", p->idxNum);
sl@0	1229	sqlite3DebugPrintf(" idxStr=%s\n", p->idxStr);
sl@0	1230	sqlite3DebugPrintf(" orderByConsumed=%d\n", p->orderByConsumed);
sl@0	1231	sqlite3DebugPrintf(" estimatedCost=%g\n", p->estimatedCost);
sl@0	1232	}
sl@0	1233	#else
sl@0	1234	#define TRACE_IDX_INPUTS(A)
sl@0	1235	#define TRACE_IDX_OUTPUTS(A)
sl@0	1236	#endif
sl@0	1237
sl@0	1238	#ifndef SQLITE_OMIT_VIRTUALTABLE
sl@0	1239	/*
sl@0	1240	** Compute the best index for a virtual table.
sl@0	1241	**
sl@0	1242	** The best index is computed by the xBestIndex method of the virtual
sl@0	1243	** table module. This routine is really just a wrapper that sets up
sl@0	1244	** the sqlite3_index_info structure that is used to communicate with
sl@0	1245	** xBestIndex.
sl@0	1246	**
sl@0	1247	** In a join, this routine might be called multiple times for the
sl@0	1248	** same virtual table. The sqlite3_index_info structure is created
sl@0	1249	** and initialized on the first invocation and reused on all subsequent
sl@0	1250	** invocations. The sqlite3_index_info structure is also used when
sl@0	1251	** code is generated to access the virtual table. The whereInfoDelete()
sl@0	1252	** routine takes care of freeing the sqlite3_index_info structure after
sl@0	1253	** everybody has finished with it.
sl@0	1254	*/
sl@0	1255	static double bestVirtualIndex(
sl@0	1256	Parse pParse, / The parsing context */
sl@0	1257	WhereClause pWC, / The WHERE clause */
sl@0	1258	struct SrcList_item pSrc, / The FROM clause term to search */
sl@0	1259	Bitmask notReady, /* Mask of cursors that are not available */
sl@0	1260	ExprList pOrderBy, / The order by clause */
sl@0	1261	int orderByUsable, /* True if we can potential sort */
sl@0	1262	sqlite3_index_info *ppIdxInfo / Index information passed to xBestIndex */
sl@0	1263	){
sl@0	1264	Table *pTab = pSrc->pTab;
sl@0	1265	sqlite3_vtab *pVtab = pTab->pVtab;
sl@0	1266	sqlite3_index_info *pIdxInfo;
sl@0	1267	struct sqlite3_index_constraint *pIdxCons;
sl@0	1268	struct sqlite3_index_orderby *pIdxOrderBy;
sl@0	1269	struct sqlite3_index_constraint_usage *pUsage;
sl@0	1270	WhereTerm *pTerm;
sl@0	1271	int i, j;
sl@0	1272	int nOrderBy;
sl@0	1273	int rc;
sl@0	1274
sl@0	1275	/* If the sqlite3_index_info structure has not been previously
sl@0	1276	** allocated and initialized for this virtual table, then allocate
sl@0	1277	** and initialize it now
sl@0	1278	*/
sl@0	1279	pIdxInfo = *ppIdxInfo;
sl@0	1280	if( pIdxInfo==0 ){
sl@0	1281	WhereTerm *pTerm;
sl@0	1282	int nTerm;
sl@0	1283	WHERETRACE(("Recomputing index info for %s...\n", pTab->zName));
sl@0	1284
sl@0	1285	/* Count the number of possible WHERE clause constraints referring
sl@0	1286	** to this virtual table */
sl@0	1287	for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
sl@0	1288	if( pTerm->leftCursor != pSrc->iCursor ) continue;
sl@0	1289	assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
sl@0	1290	testcase( pTerm->eOperator==WO_IN );
sl@0	1291	testcase( pTerm->eOperator==WO_ISNULL );
sl@0	1292	if( pTerm->eOperator & (WO_IN\|WO_ISNULL) ) continue;
sl@0	1293	nTerm++;
sl@0	1294	}
sl@0	1295
sl@0	1296	/* If the ORDER BY clause contains only columns in the current
sl@0	1297	** virtual table then allocate space for the aOrderBy part of
sl@0	1298	** the sqlite3_index_info structure.
sl@0	1299	*/
sl@0	1300	nOrderBy = 0;
sl@0	1301	if( pOrderBy ){
sl@0	1302	for(i=0; i<pOrderBy->nExpr; i++){
sl@0	1303	Expr *pExpr = pOrderBy->a[i].pExpr;
sl@0	1304	if( pExpr->op!=TK_COLUMN \|\| pExpr->iTable!=pSrc->iCursor ) break;
sl@0	1305	}
sl@0	1306	if( i==pOrderBy->nExpr ){
sl@0	1307	nOrderBy = pOrderBy->nExpr;
sl@0	1308	}
sl@0	1309	}
sl@0	1310
sl@0	1311	/* Allocate the sqlite3_index_info structure
sl@0	1312	*/
sl@0	1313	pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo)
sl@0	1314	+ (sizeof(pIdxCons) + sizeof(pUsage))*nTerm
sl@0	1315	+ sizeof(pIdxOrderBy)nOrderBy );
sl@0	1316	if( pIdxInfo==0 ){
sl@0	1317	sqlite3ErrorMsg(pParse, "out of memory");
sl@0	1318	return 0.0;
sl@0	1319	}
sl@0	1320	*ppIdxInfo = pIdxInfo;
sl@0	1321
sl@0	1322	/* Initialize the structure. The sqlite3_index_info structure contains
sl@0	1323	** many fields that are declared "const" to prevent xBestIndex from
sl@0	1324	** changing them. We have to do some funky casting in order to
sl@0	1325	** initialize those fields.
sl@0	1326	*/
sl@0	1327	pIdxCons = (struct sqlite3_index_constraint*)&pIdxInfo[1];
sl@0	1328	pIdxOrderBy = (struct sqlite3_index_orderby*)&pIdxCons[nTerm];
sl@0	1329	pUsage = (struct sqlite3_index_constraint_usage*)&pIdxOrderBy[nOrderBy];
sl@0	1330	(int)&pIdxInfo->nConstraint = nTerm;
sl@0	1331	(int)&pIdxInfo->nOrderBy = nOrderBy;
sl@0	1332	(struct sqlite3_index_constraint*)&pIdxInfo->aConstraint = pIdxCons;
sl@0	1333	(struct sqlite3_index_orderby*)&pIdxInfo->aOrderBy = pIdxOrderBy;
sl@0	1334	(struct sqlite3_index_constraint_usage*)&pIdxInfo->aConstraintUsage =
sl@0	1335	pUsage;
sl@0	1336
sl@0	1337	for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
sl@0	1338	if( pTerm->leftCursor != pSrc->iCursor ) continue;
sl@0	1339	assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
sl@0	1340	testcase( pTerm->eOperator==WO_IN );
sl@0	1341	testcase( pTerm->eOperator==WO_ISNULL );
sl@0	1342	if( pTerm->eOperator & (WO_IN\|WO_ISNULL) ) continue;
sl@0	1343	pIdxCons[j].iColumn = pTerm->leftColumn;
sl@0	1344	pIdxCons[j].iTermOffset = i;
sl@0	1345	pIdxCons[j].op = pTerm->eOperator;
sl@0	1346	/* The direct assignment in the previous line is possible only because
sl@0	1347	** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The
sl@0	1348	** following asserts verify this fact. */
sl@0	1349	assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
sl@0	1350	assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
sl@0	1351	assert( WO_LE==SQLITE_INDEX_CONSTRAINT_LE );
sl@0	1352	assert( WO_GT==SQLITE_INDEX_CONSTRAINT_GT );
sl@0	1353	assert( WO_GE==SQLITE_INDEX_CONSTRAINT_GE );
sl@0	1354	assert( WO_MATCH==SQLITE_INDEX_CONSTRAINT_MATCH );
sl@0	1355	assert( pTerm->eOperator & (WO_EQ\|WO_LT\|WO_LE\|WO_GT\|WO_GE\|WO_MATCH) );
sl@0	1356	j++;
sl@0	1357	}
sl@0	1358	for(i=0; i<nOrderBy; i++){
sl@0	1359	Expr *pExpr = pOrderBy->a[i].pExpr;
sl@0	1360	pIdxOrderBy[i].iColumn = pExpr->iColumn;
sl@0	1361	pIdxOrderBy[i].desc = pOrderBy->a[i].sortOrder;
sl@0	1362	}
sl@0	1363	}
sl@0	1364
sl@0	1365	/* At this point, the sqlite3_index_info structure that pIdxInfo points
sl@0	1366	** to will have been initialized, either during the current invocation or
sl@0	1367	** during some prior invocation. Now we just have to customize the
sl@0	1368	** details of pIdxInfo for the current invocation and pass it to
sl@0	1369	** xBestIndex.
sl@0	1370	*/
sl@0	1371
sl@0	1372	/* The module name must be defined. Also, by this point there must
sl@0	1373	** be a pointer to an sqlite3_vtab structure. Otherwise
sl@0	1374	** sqlite3ViewGetColumnNames() would have picked up the error.
sl@0	1375	*/
sl@0	1376	assert( pTab->azModuleArg && pTab->azModuleArg[0] );
sl@0	1377	assert( pVtab );
sl@0	1378	#if 0
sl@0	1379	if( pTab->pVtab==0 ){
sl@0	1380	sqlite3ErrorMsg(pParse, "undefined module %s for table %s",
sl@0	1381	pTab->azModuleArg[0], pTab->zName);
sl@0	1382	return 0.0;
sl@0	1383	}
sl@0	1384	#endif
sl@0	1385
sl@0	1386	/* Set the aConstraint[].usable fields and initialize all
sl@0	1387	** output variables to zero.
sl@0	1388	**
sl@0	1389	** aConstraint[].usable is true for constraints where the right-hand
sl@0	1390	** side contains only references to tables to the left of the current
sl@0	1391	** table. In other words, if the constraint is of the form:
sl@0	1392	**
sl@0	1393	** column = expr
sl@0	1394	**
sl@0	1395	** and we are evaluating a join, then the constraint on column is
sl@0	1396	** only valid if all tables referenced in expr occur to the left
sl@0	1397	** of the table containing column.
sl@0	1398	**
sl@0	1399	** The aConstraints[] array contains entries for all constraints
sl@0	1400	** on the current table. That way we only have to compute it once
sl@0	1401	** even though we might try to pick the best index multiple times.
sl@0	1402	** For each attempt at picking an index, the order of tables in the
sl@0	1403	** join might be different so we have to recompute the usable flag
sl@0	1404	** each time.
sl@0	1405	*/
sl@0	1406	pIdxCons = (struct sqlite3_index_constraint*)&pIdxInfo->aConstraint;
sl@0	1407	pUsage = pIdxInfo->aConstraintUsage;
sl@0	1408	for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
sl@0	1409	j = pIdxCons->iTermOffset;
sl@0	1410	pTerm = &pWC->a[j];
sl@0	1411	pIdxCons->usable = (pTerm->prereqRight & notReady)==0;
sl@0	1412	}
sl@0	1413	memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
sl@0	1414	if( pIdxInfo->needToFreeIdxStr ){
sl@0	1415	sqlite3_free(pIdxInfo->idxStr);
sl@0	1416	}
sl@0	1417	pIdxInfo->idxStr = 0;
sl@0	1418	pIdxInfo->idxNum = 0;
sl@0	1419	pIdxInfo->needToFreeIdxStr = 0;
sl@0	1420	pIdxInfo->orderByConsumed = 0;
sl@0	1421	pIdxInfo->estimatedCost = SQLITE_BIG_DBL / 2.0;
sl@0	1422	nOrderBy = pIdxInfo->nOrderBy;
sl@0	1423	if( pIdxInfo->nOrderBy && !orderByUsable ){
sl@0	1424	(int)&pIdxInfo->nOrderBy = 0;
sl@0	1425	}
sl@0	1426
sl@0	1427	(void)sqlite3SafetyOff(pParse->db);
sl@0	1428	WHERETRACE(("xBestIndex for %s\n", pTab->zName));
sl@0	1429	TRACE_IDX_INPUTS(pIdxInfo);
sl@0	1430	rc = pVtab->pModule->xBestIndex(pVtab, pIdxInfo);
sl@0	1431	TRACE_IDX_OUTPUTS(pIdxInfo);
sl@0	1432	(void)sqlite3SafetyOn(pParse->db);
sl@0	1433
sl@0	1434	if( rc!=SQLITE_OK ){
sl@0	1435	if( rc==SQLITE_NOMEM ){
sl@0	1436	pParse->db->mallocFailed = 1;
sl@0	1437	}else if( !pVtab->zErrMsg ){
sl@0	1438	sqlite3ErrorMsg(pParse, "%s", sqlite3ErrStr(rc));
sl@0	1439	}else{
sl@0	1440	sqlite3ErrorMsg(pParse, "%s", pVtab->zErrMsg);
sl@0	1441	}
sl@0	1442	}
sl@0	1443	sqlite3DbFree(pParse->db, pVtab->zErrMsg);
sl@0	1444	pVtab->zErrMsg = 0;
sl@0	1445
sl@0	1446	for(i=0; i<pIdxInfo->nConstraint; i++){
sl@0	1447	if( !pIdxInfo->aConstraint[i].usable && pUsage[i].argvIndex>0 ){
sl@0	1448	sqlite3ErrorMsg(pParse,
sl@0	1449	"table %s: xBestIndex returned an invalid plan", pTab->zName);
sl@0	1450	return 0.0;
sl@0	1451	}
sl@0	1452	}
sl@0	1453
sl@0	1454	(int)&pIdxInfo->nOrderBy = nOrderBy;
sl@0	1455	return pIdxInfo->estimatedCost;
sl@0	1456	}
sl@0	1457	#endif /* SQLITE_OMIT_VIRTUALTABLE */
sl@0	1458
sl@0	1459	/*
sl@0	1460	** Find the best index for accessing a particular table. Return a pointer
sl@0	1461	** to the index, flags that describe how the index should be used, the
sl@0	1462	** number of equality constraints, and the "cost" for this index.
sl@0	1463	**
sl@0	1464	** The lowest cost index wins. The cost is an estimate of the amount of
sl@0	1465	** CPU and disk I/O need to process the request using the selected index.
sl@0	1466	** Factors that influence cost include:
sl@0	1467	**
sl@0	1468	** * The estimated number of rows that will be retrieved. (The
sl@0	1469	** fewer the better.)
sl@0	1470	**
sl@0	1471	** * Whether or not sorting must occur.
sl@0	1472	**
sl@0	1473	** * Whether or not there must be separate lookups in the
sl@0	1474	** index and in the main table.
sl@0	1475	**
sl@0	1476	** If there was an INDEXED BY clause attached to the table in the SELECT
sl@0	1477	** statement, then this function only considers strategies using the
sl@0	1478	** named index. If one cannot be found, then the returned cost is
sl@0	1479	** SQLITE_BIG_DBL. If a strategy can be found that uses the named index,
sl@0	1480	** then the cost is calculated in the usual way.
sl@0	1481	**
sl@0	1482	** If a NOT INDEXED clause was attached to the table in the SELECT
sl@0	1483	** statement, then no indexes are considered. However, the selected
sl@0	1484	** stategy may still take advantage of the tables built-in rowid
sl@0	1485	** index.
sl@0	1486	*/
sl@0	1487	static double bestIndex(
sl@0	1488	Parse pParse, / The parsing context */
sl@0	1489	WhereClause pWC, / The WHERE clause */
sl@0	1490	struct SrcList_item pSrc, / The FROM clause term to search */
sl@0	1491	Bitmask notReady, /* Mask of cursors that are not available */
sl@0	1492	ExprList pOrderBy, / The order by clause */
sl@0	1493	Index *ppIndex, / Make ppIndex point to the best index /
sl@0	1494	int pFlags, / Put flags describing this choice in pFlags /
sl@0	1495	int pnEq / Put the number of == or IN constraints here */
sl@0	1496	){
sl@0	1497	WhereTerm *pTerm;
sl@0	1498	Index bestIdx = 0; / Index that gives the lowest cost */
sl@0	1499	double lowestCost; /* The cost of using bestIdx */
sl@0	1500	int bestFlags = 0; /* Flags associated with bestIdx */
sl@0	1501	int bestNEq = 0; /* Best value for nEq */
sl@0	1502	int iCur = pSrc->iCursor; /* The cursor of the table to be accessed */
sl@0	1503	Index pProbe; / An index we are evaluating */
sl@0	1504	int rev; /* True to scan in reverse order */
sl@0	1505	int flags; /* Flags associated with pProbe */
sl@0	1506	int nEq; /* Number of == or IN constraints */
sl@0	1507	int eqTermMask; /* Mask of valid equality operators */
sl@0	1508	double cost; /* Cost of using pProbe */
sl@0	1509
sl@0	1510	WHERETRACE(("bestIndex: tbl=%s notReady=%llx\n", pSrc->pTab->zName, notReady));
sl@0	1511	lowestCost = SQLITE_BIG_DBL;
sl@0	1512	pProbe = pSrc->pTab->pIndex;
sl@0	1513	if( pSrc->notIndexed ){
sl@0	1514	pProbe = 0;
sl@0	1515	}
sl@0	1516
sl@0	1517	/* If the table has no indices and there are no terms in the where
sl@0	1518	** clause that refer to the ROWID, then we will never be able to do
sl@0	1519	** anything other than a full table scan on this table. We might as
sl@0	1520	** well put it first in the join order. That way, perhaps it can be
sl@0	1521	** referenced by other tables in the join.
sl@0	1522	*/
sl@0	1523	if( pProbe==0 &&
sl@0	1524	findTerm(pWC, iCur, -1, 0, WO_EQ\|WO_IN\|WO_LT\|WO_LE\|WO_GT\|WO_GE,0)==0 &&
sl@0	1525	(pOrderBy==0 \|\| !sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev)) ){
sl@0	1526	*pFlags = 0;
sl@0	1527	*ppIndex = 0;
sl@0	1528	*pnEq = 0;
sl@0	1529	return 0.0;
sl@0	1530	}
sl@0	1531
sl@0	1532	/* Check for a rowid=EXPR or rowid IN (...) constraints. If there was
sl@0	1533	** an INDEXED BY clause attached to this table, skip this step.
sl@0	1534	*/
sl@0	1535	if( !pSrc->pIndex ){
sl@0	1536	pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ\|WO_IN, 0);
sl@0	1537	if( pTerm ){
sl@0	1538	Expr *pExpr;
sl@0	1539	*ppIndex = 0;
sl@0	1540	bestFlags = WHERE_ROWID_EQ;
sl@0	1541	if( pTerm->eOperator & WO_EQ ){
sl@0	1542	/* Rowid== is always the best pick. Look no further. Because only
sl@0	1543	** a single row is generated, output is always in sorted order */
sl@0	1544	*pFlags = WHERE_ROWID_EQ \| WHERE_UNIQUE;
sl@0	1545	*pnEq = 1;
sl@0	1546	WHERETRACE(("... best is rowid\n"));
sl@0	1547	return 0.0;
sl@0	1548	}else if( (pExpr = pTerm->pExpr)->pList!=0 ){
sl@0	1549	/* Rowid IN (LIST): cost is NlogN where N is the number of list
sl@0	1550	** elements. */
sl@0	1551	lowestCost = pExpr->pList->nExpr;
sl@0	1552	lowestCost *= estLog(lowestCost);
sl@0	1553	}else{
sl@0	1554	/* Rowid IN (SELECT): cost is NlogN where N is the number of rows
sl@0	1555	** in the result of the inner select. We have no way to estimate
sl@0	1556	** that value so make a wild guess. */
sl@0	1557	lowestCost = 200;
sl@0	1558	}
sl@0	1559	WHERETRACE(("... rowid IN cost: %.9g\n", lowestCost));
sl@0	1560	}
sl@0	1561
sl@0	1562	/* Estimate the cost of a table scan. If we do not know how many
sl@0	1563	** entries are in the table, use 1 million as a guess.
sl@0	1564	*/
sl@0	1565	cost = pProbe ? pProbe->aiRowEst[0] : 1000000;
sl@0	1566	WHERETRACE(("... table scan base cost: %.9g\n", cost));
sl@0	1567	flags = WHERE_ROWID_RANGE;
sl@0	1568
sl@0	1569	/* Check for constraints on a range of rowids in a table scan.
sl@0	1570	*/
sl@0	1571	pTerm = findTerm(pWC, iCur, -1, notReady, WO_LT\|WO_LE\|WO_GT\|WO_GE, 0);
sl@0	1572	if( pTerm ){
sl@0	1573	if( findTerm(pWC, iCur, -1, notReady, WO_LT\|WO_LE, 0) ){
sl@0	1574	flags \|= WHERE_TOP_LIMIT;
sl@0	1575	cost /= 3; /* Guess that rowid<EXPR eliminates two-thirds or rows */
sl@0	1576	}
sl@0	1577	if( findTerm(pWC, iCur, -1, notReady, WO_GT\|WO_GE, 0) ){
sl@0	1578	flags \|= WHERE_BTM_LIMIT;
sl@0	1579	cost /= 3; /* Guess that rowid>EXPR eliminates two-thirds of rows */
sl@0	1580	}
sl@0	1581	WHERETRACE(("... rowid range reduces cost to %.9g\n", cost));
sl@0	1582	}else{
sl@0	1583	flags = 0;
sl@0	1584	}
sl@0	1585
sl@0	1586	/* If the table scan does not satisfy the ORDER BY clause, increase
sl@0	1587	** the cost by NlogN to cover the expense of sorting. */
sl@0	1588	if( pOrderBy ){
sl@0	1589	if( sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev) ){
sl@0	1590	flags \|= WHERE_ORDERBY\|WHERE_ROWID_RANGE;
sl@0	1591	if( rev ){
sl@0	1592	flags \|= WHERE_REVERSE;
sl@0	1593	}
sl@0	1594	}else{
sl@0	1595	cost += cost*estLog(cost);
sl@0	1596	WHERETRACE(("... sorting increases cost to %.9g\n", cost));
sl@0	1597	}
sl@0	1598	}
sl@0	1599	if( cost<lowestCost ){
sl@0	1600	lowestCost = cost;
sl@0	1601	bestFlags = flags;
sl@0	1602	}
sl@0	1603	}
sl@0	1604
sl@0	1605	/* If the pSrc table is the right table of a LEFT JOIN then we may not
sl@0	1606	** use an index to satisfy IS NULL constraints on that table. This is
sl@0	1607	** because columns might end up being NULL if the table does not match -
sl@0	1608	** a circumstance which the index cannot help us discover. Ticket #2177.
sl@0	1609	*/
sl@0	1610	if( (pSrc->jointype & JT_LEFT)!=0 ){
sl@0	1611	eqTermMask = WO_EQ\|WO_IN;
sl@0	1612	}else{
sl@0	1613	eqTermMask = WO_EQ\|WO_IN\|WO_ISNULL;
sl@0	1614	}
sl@0	1615
sl@0	1616	/* Look at each index.
sl@0	1617	*/
sl@0	1618	if( pSrc->pIndex ){
sl@0	1619	pProbe = pSrc->pIndex;
sl@0	1620	}
sl@0	1621	for(; pProbe; pProbe=(pSrc->pIndex ? 0 : pProbe->pNext)){
sl@0	1622	int i; /* Loop counter */
sl@0	1623	double inMultiplier = 1;
sl@0	1624
sl@0	1625	WHERETRACE(("... index %s:\n", pProbe->zName));
sl@0	1626
sl@0	1627	/* Count the number of columns in the index that are satisfied
sl@0	1628	** by x=EXPR constraints or x IN (...) constraints.
sl@0	1629	*/
sl@0	1630	flags = 0;
sl@0	1631	for(i=0; i<pProbe->nColumn; i++){
sl@0	1632	int j = pProbe->aiColumn[i];
sl@0	1633	pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pProbe);
sl@0	1634	if( pTerm==0 ) break;
sl@0	1635	flags \|= WHERE_COLUMN_EQ;
sl@0	1636	if( pTerm->eOperator & WO_IN ){
sl@0	1637	Expr *pExpr = pTerm->pExpr;
sl@0	1638	flags \|= WHERE_COLUMN_IN;
sl@0	1639	if( pExpr->pSelect!=0 ){
sl@0	1640	inMultiplier *= 25;
sl@0	1641	}else if( ALWAYS(pExpr->pList) ){
sl@0	1642	inMultiplier *= pExpr->pList->nExpr + 1;
sl@0	1643	}
sl@0	1644	}
sl@0	1645	}
sl@0	1646	cost = pProbe->aiRowEst[i] * inMultiplier * estLog(inMultiplier);
sl@0	1647	nEq = i;
sl@0	1648	if( pProbe->onError!=OE_None && (flags & WHERE_COLUMN_IN)==0
sl@0	1649	&& nEq==pProbe->nColumn ){
sl@0	1650	flags \|= WHERE_UNIQUE;
sl@0	1651	}
sl@0	1652	WHERETRACE(("...... nEq=%d inMult=%.9g cost=%.9g\n",nEq,inMultiplier,cost));
sl@0	1653
sl@0	1654	/* Look for range constraints
sl@0	1655	*/
sl@0	1656	if( nEq<pProbe->nColumn ){
sl@0	1657	int j = pProbe->aiColumn[nEq];
sl@0	1658	pTerm = findTerm(pWC, iCur, j, notReady, WO_LT\|WO_LE\|WO_GT\|WO_GE, pProbe);
sl@0	1659	if( pTerm ){
sl@0	1660	flags \|= WHERE_COLUMN_RANGE;
sl@0	1661	if( findTerm(pWC, iCur, j, notReady, WO_LT\|WO_LE, pProbe) ){
sl@0	1662	flags \|= WHERE_TOP_LIMIT;
sl@0	1663	cost /= 3;
sl@0	1664	}
sl@0	1665	if( findTerm(pWC, iCur, j, notReady, WO_GT\|WO_GE, pProbe) ){
sl@0	1666	flags \|= WHERE_BTM_LIMIT;
sl@0	1667	cost /= 3;
sl@0	1668	}
sl@0	1669	WHERETRACE(("...... range reduces cost to %.9g\n", cost));
sl@0	1670	}
sl@0	1671	}
sl@0	1672
sl@0	1673	/* Add the additional cost of sorting if that is a factor.
sl@0	1674	*/
sl@0	1675	if( pOrderBy ){
sl@0	1676	if( (flags & WHERE_COLUMN_IN)==0 &&
sl@0	1677	isSortingIndex(pParse,pWC->pMaskSet,pProbe,iCur,pOrderBy,nEq,&rev) ){
sl@0	1678	if( flags==0 ){
sl@0	1679	flags = WHERE_COLUMN_RANGE;
sl@0	1680	}
sl@0	1681	flags \|= WHERE_ORDERBY;
sl@0	1682	if( rev ){
sl@0	1683	flags \|= WHERE_REVERSE;
sl@0	1684	}
sl@0	1685	}else{
sl@0	1686	cost += cost*estLog(cost);
sl@0	1687	WHERETRACE(("...... orderby increases cost to %.9g\n", cost));
sl@0	1688	}
sl@0	1689	}
sl@0	1690
sl@0	1691	/* Check to see if we can get away with using just the index without
sl@0	1692	** ever reading the table. If that is the case, then halve the
sl@0	1693	** cost of this index.
sl@0	1694	*/
sl@0	1695	if( flags && pSrc->colUsed < (((Bitmask)1)<<(BMS-1)) ){
sl@0	1696	Bitmask m = pSrc->colUsed;
sl@0	1697	int j;
sl@0	1698	for(j=0; j<pProbe->nColumn; j++){
sl@0	1699	int x = pProbe->aiColumn[j];
sl@0	1700	if( x<BMS-1 ){
sl@0	1701	m &= ~(((Bitmask)1)<<x);
sl@0	1702	}
sl@0	1703	}
sl@0	1704	if( m==0 ){
sl@0	1705	flags \|= WHERE_IDX_ONLY;
sl@0	1706	cost /= 2;
sl@0	1707	WHERETRACE(("...... idx-only reduces cost to %.9g\n", cost));
sl@0	1708	}
sl@0	1709	}
sl@0	1710
sl@0	1711	/* If this index has achieved the lowest cost so far, then use it.
sl@0	1712	*/
sl@0	1713	if( flags && cost < lowestCost ){
sl@0	1714	bestIdx = pProbe;
sl@0	1715	lowestCost = cost;
sl@0	1716	bestFlags = flags;
sl@0	1717	bestNEq = nEq;
sl@0	1718	}
sl@0	1719	}
sl@0	1720
sl@0	1721	/* Report the best result
sl@0	1722	*/
sl@0	1723	*ppIndex = bestIdx;
sl@0	1724	WHERETRACE(("best index is %s, cost=%.9g, flags=%x, nEq=%d\n",
sl@0	1725	bestIdx ? bestIdx->zName : "(none)", lowestCost, bestFlags, bestNEq));
sl@0	1726	*pFlags = bestFlags \| eqTermMask;
sl@0	1727	*pnEq = bestNEq;
sl@0	1728	return lowestCost;
sl@0	1729	}
sl@0	1730
sl@0	1731
sl@0	1732	/*
sl@0	1733	** Disable a term in the WHERE clause. Except, do not disable the term
sl@0	1734	** if it controls a LEFT OUTER JOIN and it did not originate in the ON
sl@0	1735	** or USING clause of that join.
sl@0	1736	**
sl@0	1737	** Consider the term t2.z='ok' in the following queries:
sl@0	1738	**
sl@0	1739	** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
sl@0	1740	** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
sl@0	1741	** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
sl@0	1742	**
sl@0	1743	** The t2.z='ok' is disabled in the in (2) because it originates
sl@0	1744	** in the ON clause. The term is disabled in (3) because it is not part
sl@0	1745	** of a LEFT OUTER JOIN. In (1), the term is not disabled.
sl@0	1746	**
sl@0	1747	** Disabling a term causes that term to not be tested in the inner loop
sl@0	1748	** of the join. Disabling is an optimization. When terms are satisfied
sl@0	1749	** by indices, we disable them to prevent redundant tests in the inner
sl@0	1750	** loop. We would get the correct results if nothing were ever disabled,
sl@0	1751	** but joins might run a little slower. The trick is to disable as much
sl@0	1752	** as we can without disabling too much. If we disabled in (1), we'd get
sl@0	1753	** the wrong answer. See ticket #813.
sl@0	1754	*/
sl@0	1755	static void disableTerm(WhereLevel pLevel, WhereTerm pTerm){
sl@0	1756	if( pTerm
sl@0	1757	&& ALWAYS((pTerm->flags & TERM_CODED)==0)
sl@0	1758	&& (pLevel->iLeftJoin==0 \|\| ExprHasProperty(pTerm->pExpr, EP_FromJoin))
sl@0	1759	){
sl@0	1760	pTerm->flags \|= TERM_CODED;
sl@0	1761	if( pTerm->iParent>=0 ){
sl@0	1762	WhereTerm *pOther = &pTerm->pWC->a[pTerm->iParent];
sl@0	1763	if( (--pOther->nChild)==0 ){
sl@0	1764	disableTerm(pLevel, pOther);
sl@0	1765	}
sl@0	1766	}
sl@0	1767	}
sl@0	1768	}
sl@0	1769
sl@0	1770	/*
sl@0	1771	** Apply the affinities associated with the first n columns of index
sl@0	1772	** pIdx to the values in the n registers starting at base.
sl@0	1773	*/
sl@0	1774	static void codeApplyAffinity(Parse pParse, int base, int n, Index pIdx){
sl@0	1775	if( n>0 ){
sl@0	1776	Vdbe *v = pParse->pVdbe;
sl@0	1777	assert( v!=0 );
sl@0	1778	sqlite3VdbeAddOp2(v, OP_Affinity, base, n);
sl@0	1779	sqlite3IndexAffinityStr(v, pIdx);
sl@0	1780	sqlite3ExprCacheAffinityChange(pParse, base, n);
sl@0	1781	}
sl@0	1782	}
sl@0	1783
sl@0	1784
sl@0	1785	/*
sl@0	1786	** Generate code for a single equality term of the WHERE clause. An equality
sl@0	1787	** term can be either X=expr or X IN (...). pTerm is the term to be
sl@0	1788	** coded.
sl@0	1789	**
sl@0	1790	** The current value for the constraint is left in register iReg.
sl@0	1791	**
sl@0	1792	** For a constraint of the form X=expr, the expression is evaluated and its
sl@0	1793	** result is left on the stack. For constraints of the form X IN (...)
sl@0	1794	** this routine sets up a loop that will iterate over all values of X.
sl@0	1795	*/
sl@0	1796	static int codeEqualityTerm(
sl@0	1797	Parse pParse, / The parsing context */
sl@0	1798	WhereTerm pTerm, / The term of the WHERE clause to be coded */
sl@0	1799	WhereLevel pLevel, / When level of the FROM clause we are working on */
sl@0	1800	int iTarget /* Attempt to leave results in this register */
sl@0	1801	){
sl@0	1802	Expr *pX = pTerm->pExpr;
sl@0	1803	Vdbe *v = pParse->pVdbe;
sl@0	1804	int iReg; /* Register holding results */
sl@0	1805
sl@0	1806	assert( iTarget>0 );
sl@0	1807	if( pX->op==TK_EQ ){
sl@0	1808	iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget);
sl@0	1809	}else if( pX->op==TK_ISNULL ){
sl@0	1810	iReg = iTarget;
sl@0	1811	sqlite3VdbeAddOp2(v, OP_Null, 0, iReg);
sl@0	1812	#ifndef SQLITE_OMIT_SUBQUERY
sl@0	1813	}else{
sl@0	1814	int eType;
sl@0	1815	int iTab;
sl@0	1816	struct InLoop *pIn;
sl@0	1817
sl@0	1818	assert( pX->op==TK_IN );
sl@0	1819	iReg = iTarget;
sl@0	1820	eType = sqlite3FindInIndex(pParse, pX, 0);
sl@0	1821	iTab = pX->iTable;
sl@0	1822	sqlite3VdbeAddOp2(v, OP_Rewind, iTab, 0);
sl@0	1823	VdbeComment((v, "%.*s", pX->span.n, pX->span.z));
sl@0	1824	if( pLevel->nIn==0 ){
sl@0	1825	pLevel->nxt = sqlite3VdbeMakeLabel(v);
sl@0	1826	}
sl@0	1827	pLevel->nIn++;
sl@0	1828	pLevel->aInLoop = sqlite3DbReallocOrFree(pParse->db, pLevel->aInLoop,
sl@0	1829	sizeof(pLevel->aInLoop[0])*pLevel->nIn);
sl@0	1830	pIn = pLevel->aInLoop;
sl@0	1831	if( pIn ){
sl@0	1832	pIn += pLevel->nIn - 1;
sl@0	1833	pIn->iCur = iTab;
sl@0	1834	if( eType==IN_INDEX_ROWID ){
sl@0	1835	pIn->topAddr = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iReg);
sl@0	1836	}else{
sl@0	1837	pIn->topAddr = sqlite3VdbeAddOp3(v, OP_Column, iTab, 0, iReg);
sl@0	1838	}
sl@0	1839	sqlite3VdbeAddOp1(v, OP_IsNull, iReg);
sl@0	1840	}else{
sl@0	1841	pLevel->nIn = 0;
sl@0	1842	}
sl@0	1843	#endif
sl@0	1844	}
sl@0	1845	disableTerm(pLevel, pTerm);
sl@0	1846	return iReg;
sl@0	1847	}
sl@0	1848
sl@0	1849	/*
sl@0	1850	** Generate code that will evaluate all == and IN constraints for an
sl@0	1851	** index. The values for all constraints are left on the stack.
sl@0	1852	**
sl@0	1853	** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
sl@0	1854	** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10
sl@0	1855	** The index has as many as three equality constraints, but in this
sl@0	1856	** example, the third "c" value is an inequality. So only two
sl@0	1857	** constraints are coded. This routine will generate code to evaluate
sl@0	1858	** a==5 and b IN (1,2,3). The current values for a and b will be left
sl@0	1859	** on the stack - a is the deepest and b the shallowest.
sl@0	1860	**
sl@0	1861	** In the example above nEq==2. But this subroutine works for any value
sl@0	1862	** of nEq including 0. If nEq==0, this routine is nearly a no-op.
sl@0	1863	** The only thing it does is allocate the pLevel->iMem memory cell.
sl@0	1864	**
sl@0	1865	** This routine always allocates at least one memory cell and puts
sl@0	1866	** the address of that memory cell in pLevel->iMem. The code that
sl@0	1867	** calls this routine will use pLevel->iMem to store the termination
sl@0	1868	** key value of the loop. If one or more IN operators appear, then
sl@0	1869	** this routine allocates an additional nEq memory cells for internal
sl@0	1870	** use.
sl@0	1871	*/
sl@0	1872	static int codeAllEqualityTerms(
sl@0	1873	Parse pParse, / Parsing context */
sl@0	1874	WhereLevel pLevel, / Which nested loop of the FROM we are coding */
sl@0	1875	WhereClause pWC, / The WHERE clause */
sl@0	1876	Bitmask notReady, /* Which parts of FROM have not yet been coded */
sl@0	1877	int nExtraReg /* Number of extra registers to allocate */
sl@0	1878	){
sl@0	1879	int nEq = pLevel->nEq; /* The number of == or IN constraints to code */
sl@0	1880	Vdbe v = pParse->pVdbe; / The virtual machine under construction */
sl@0	1881	Index pIdx = pLevel->pIdx; / The index being used for this loop */
sl@0	1882	int iCur = pLevel->iTabCur; /* The cursor of the table */
sl@0	1883	WhereTerm pTerm; / A single constraint term */
sl@0	1884	int j; /* Loop counter */
sl@0	1885	int regBase; /* Base register */
sl@0	1886
sl@0	1887	/* Figure out how many memory cells we will need then allocate them.
sl@0	1888	** We always need at least one used to store the loop terminator
sl@0	1889	** value. If there are IN operators we'll need one for each == or
sl@0	1890	** IN constraint.
sl@0	1891	*/
sl@0	1892	pLevel->iMem = pParse->nMem + 1;
sl@0	1893	regBase = pParse->nMem + 2;
sl@0	1894	pParse->nMem += pLevel->nEq + 2 + nExtraReg;
sl@0	1895
sl@0	1896	/* Evaluate the equality constraints
sl@0	1897	*/
sl@0	1898	assert( pIdx->nColumn>=nEq );
sl@0	1899	for(j=0; j<nEq; j++){
sl@0	1900	int r1;
sl@0	1901	int k = pIdx->aiColumn[j];
sl@0	1902	pTerm = findTerm(pWC, iCur, k, notReady, pLevel->flags, pIdx);
sl@0	1903	if( NEVER(pTerm==0) ) break;
sl@0	1904	assert( (pTerm->flags & TERM_CODED)==0 );
sl@0	1905	r1 = codeEqualityTerm(pParse, pTerm, pLevel, regBase+j);
sl@0	1906	if( r1!=regBase+j ){
sl@0	1907	sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
sl@0	1908	}
sl@0	1909	testcase( pTerm->eOperator & WO_ISNULL );
sl@0	1910	testcase( pTerm->eOperator & WO_IN );
sl@0	1911	if( (pTerm->eOperator & (WO_ISNULL\|WO_IN))==0 ){
sl@0	1912	sqlite3VdbeAddOp2(v, OP_IsNull, regBase+j, pLevel->brk);
sl@0	1913	}
sl@0	1914	}
sl@0	1915	return regBase;
sl@0	1916	}
sl@0	1917
sl@0	1918	#if defined(SQLITE_TEST)
sl@0	1919	/*
sl@0	1920	** The following variable holds a text description of query plan generated
sl@0	1921	** by the most recent call to sqlite3WhereBegin(). Each call to WhereBegin
sl@0	1922	** overwrites the previous. This information is used for testing and
sl@0	1923	** analysis only.
sl@0	1924	*/
sl@0	1925	char sqlite3_query_plan[BMS240]; /* Text of the join */
sl@0	1926	static int nQPlan = 0; /* Next free slow in _query_plan[] */
sl@0	1927
sl@0	1928	#endif /* SQLITE_TEST */
sl@0	1929
sl@0	1930
sl@0	1931	/*
sl@0	1932	** Free a WhereInfo structure
sl@0	1933	*/
sl@0	1934	static void whereInfoFree(sqlite3 db, WhereInfo pWInfo){
sl@0	1935	if( pWInfo ){
sl@0	1936	int i;
sl@0	1937	for(i=0; i<pWInfo->nLevel; i++){
sl@0	1938	sqlite3_index_info *pInfo = pWInfo->a[i].pIdxInfo;
sl@0	1939	if( pInfo ){
sl@0	1940	assert( pInfo->needToFreeIdxStr==0 );
sl@0	1941	sqlite3DbFree(db, pInfo);
sl@0	1942	}
sl@0	1943	}
sl@0	1944	sqlite3DbFree(db, pWInfo);
sl@0	1945	}
sl@0	1946	}
sl@0	1947
sl@0	1948
sl@0	1949	/*
sl@0	1950	** Generate the beginning of the loop used for WHERE clause processing.
sl@0	1951	** The return value is a pointer to an opaque structure that contains
sl@0	1952	** information needed to terminate the loop. Later, the calling routine
sl@0	1953	** should invoke sqlite3WhereEnd() with the return value of this function
sl@0	1954	** in order to complete the WHERE clause processing.
sl@0	1955	**
sl@0	1956	** If an error occurs, this routine returns NULL.
sl@0	1957	**
sl@0	1958	** The basic idea is to do a nested loop, one loop for each table in
sl@0	1959	** the FROM clause of a select. (INSERT and UPDATE statements are the
sl@0	1960	** same as a SELECT with only a single table in the FROM clause.) For
sl@0	1961	** example, if the SQL is this:
sl@0	1962	**
sl@0	1963	** SELECT * FROM t1, t2, t3 WHERE ...;
sl@0	1964	**
sl@0	1965	** Then the code generated is conceptually like the following:
sl@0	1966	**
sl@0	1967	** foreach row1 in t1 do \ Code generated
sl@0	1968	** foreach row2 in t2 do \|-- by sqlite3WhereBegin()
sl@0	1969	** foreach row3 in t3 do /
sl@0	1970	** ...
sl@0	1971	** end \ Code generated
sl@0	1972	** end \|-- by sqlite3WhereEnd()
sl@0	1973	** end /
sl@0	1974	**
sl@0	1975	** Note that the loops might not be nested in the order in which they
sl@0	1976	** appear in the FROM clause if a different order is better able to make
sl@0	1977	** use of indices. Note also that when the IN operator appears in
sl@0	1978	** the WHERE clause, it might result in additional nested loops for
sl@0	1979	** scanning through all values on the right-hand side of the IN.
sl@0	1980	**
sl@0	1981	** There are Btree cursors associated with each table. t1 uses cursor
sl@0	1982	** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor.
sl@0	1983	** And so forth. This routine generates code to open those VDBE cursors
sl@0	1984	** and sqlite3WhereEnd() generates the code to close them.
sl@0	1985	**
sl@0	1986	** The code that sqlite3WhereBegin() generates leaves the cursors named
sl@0	1987	** in pTabList pointing at their appropriate entries. The [...] code
sl@0	1988	** can use OP_Column and OP_Rowid opcodes on these cursors to extract
sl@0	1989	** data from the various tables of the loop.
sl@0	1990	**
sl@0	1991	** If the WHERE clause is empty, the foreach loops must each scan their
sl@0	1992	** entire tables. Thus a three-way join is an O(N^3) operation. But if
sl@0	1993	** the tables have indices and there are terms in the WHERE clause that
sl@0	1994	** refer to those indices, a complete table scan can be avoided and the
sl@0	1995	** code will run much faster. Most of the work of this routine is checking
sl@0	1996	** to see if there are indices that can be used to speed up the loop.
sl@0	1997	**
sl@0	1998	** Terms of the WHERE clause are also used to limit which rows actually
sl@0	1999	** make it to the "..." in the middle of the loop. After each "foreach",
sl@0	2000	** terms of the WHERE clause that use only terms in that loop and outer
sl@0	2001	** loops are evaluated and if false a jump is made around all subsequent
sl@0	2002	** inner loops (or around the "..." if the test occurs within the inner-
sl@0	2003	** most loop)
sl@0	2004	**
sl@0	2005	** OUTER JOINS
sl@0	2006	**
sl@0	2007	** An outer join of tables t1 and t2 is conceptally coded as follows:
sl@0	2008	**
sl@0	2009	** foreach row1 in t1 do
sl@0	2010	** flag = 0
sl@0	2011	** foreach row2 in t2 do
sl@0	2012	** start:
sl@0	2013	** ...
sl@0	2014	** flag = 1
sl@0	2015	** end
sl@0	2016	** if flag==0 then
sl@0	2017	** move the row2 cursor to a null row
sl@0	2018	** goto start
sl@0	2019	** fi
sl@0	2020	** end
sl@0	2021	**
sl@0	2022	** ORDER BY CLAUSE PROCESSING
sl@0	2023	**
sl@0	2024	** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
sl@0	2025	** if there is one. If there is no ORDER BY clause or if this routine
sl@0	2026	** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.
sl@0	2027	**
sl@0	2028	** If an index can be used so that the natural output order of the table
sl@0	2029	** scan is correct for the ORDER BY clause, then that index is used and
sl@0	2030	** *ppOrderBy is set to NULL. This is an optimization that prevents an
sl@0	2031	** unnecessary sort of the result set if an index appropriate for the
sl@0	2032	** ORDER BY clause already exists.
sl@0	2033	**
sl@0	2034	** If the where clause loops cannot be arranged to provide the correct
sl@0	2035	** output order, then the *ppOrderBy is unchanged.
sl@0	2036	*/
sl@0	2037	WhereInfo *sqlite3WhereBegin(
sl@0	2038	Parse pParse, / The parser context */
sl@0	2039	SrcList pTabList, / A list of all tables to be scanned */
sl@0	2040	Expr pWhere, / The WHERE clause */
sl@0	2041	ExprList *ppOrderBy, / An ORDER BY clause, or NULL */
sl@0	2042	u8 wflags /* One of the WHERE_* flags defined in sqliteInt.h */
sl@0	2043	){
sl@0	2044	int i; /* Loop counter */
sl@0	2045	WhereInfo pWInfo; / Will become the return value of this function */
sl@0	2046	Vdbe v = pParse->pVdbe; / The virtual database engine */
sl@0	2047	int brk, cont = 0; /* Addresses used during code generation */
sl@0	2048	Bitmask notReady; /* Cursors that are not yet positioned */
sl@0	2049	WhereTerm pTerm; / A single term in the WHERE clause */
sl@0	2050	ExprMaskSet maskSet; /* The expression mask set */
sl@0	2051	WhereClause wc; /* The WHERE clause is divided into these terms */
sl@0	2052	struct SrcList_item pTabItem; / A single entry from pTabList */
sl@0	2053	WhereLevel pLevel; / A single level in the pWInfo list */
sl@0	2054	int iFrom; /* First unused FROM clause element */
sl@0	2055	int andFlags; /* AND-ed combination of all wc.a[].flags */
sl@0	2056	sqlite3 db; / Database connection */
sl@0	2057	ExprList *pOrderBy = 0;
sl@0	2058
sl@0	2059	/* The number of tables in the FROM clause is limited by the number of
sl@0	2060	** bits in a Bitmask
sl@0	2061	*/
sl@0	2062	if( pTabList->nSrc>BMS ){
sl@0	2063	sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);
sl@0	2064	return 0;
sl@0	2065	}
sl@0	2066
sl@0	2067	if( ppOrderBy ){
sl@0	2068	pOrderBy = *ppOrderBy;
sl@0	2069	}
sl@0	2070
sl@0	2071	/* Split the WHERE clause into separate subexpressions where each
sl@0	2072	** subexpression is separated by an AND operator.
sl@0	2073	*/
sl@0	2074	initMaskSet(&maskSet);
sl@0	2075	whereClauseInit(&wc, pParse, &maskSet);
sl@0	2076	sqlite3ExprCodeConstants(pParse, pWhere);
sl@0	2077	whereSplit(&wc, pWhere, TK_AND);
sl@0	2078
sl@0	2079	/* Allocate and initialize the WhereInfo structure that will become the
sl@0	2080	** return value.
sl@0	2081	*/
sl@0	2082	db = pParse->db;
sl@0	2083	pWInfo = sqlite3DbMallocZero(db,
sl@0	2084	sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel));
sl@0	2085	if( db->mallocFailed ){
sl@0	2086	goto whereBeginError;
sl@0	2087	}
sl@0	2088	pWInfo->nLevel = pTabList->nSrc;
sl@0	2089	pWInfo->pParse = pParse;
sl@0	2090	pWInfo->pTabList = pTabList;
sl@0	2091	pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
sl@0	2092
sl@0	2093	/* Special case: a WHERE clause that is constant. Evaluate the
sl@0	2094	** expression and either jump over all of the code or fall thru.
sl@0	2095	*/
sl@0	2096	if( pWhere && (pTabList->nSrc==0 \|\| sqlite3ExprIsConstantNotJoin(pWhere)) ){
sl@0	2097	sqlite3ExprIfFalse(pParse, pWhere, pWInfo->iBreak, SQLITE_JUMPIFNULL);
sl@0	2098	pWhere = 0;
sl@0	2099	}
sl@0	2100
sl@0	2101	/* Assign a bit from the bitmask to every term in the FROM clause.
sl@0	2102	**
sl@0	2103	** When assigning bitmask values to FROM clause cursors, it must be
sl@0	2104	** the case that if X is the bitmask for the N-th FROM clause term then
sl@0	2105	** the bitmask for all FROM clause terms to the left of the N-th term
sl@0	2106	** is (X-1). An expression from the ON clause of a LEFT JOIN can use
sl@0	2107	** its Expr.iRightJoinTable value to find the bitmask of the right table
sl@0	2108	** of the join. Subtracting one from the right table bitmask gives a
sl@0	2109	** bitmask for all tables to the left of the join. Knowing the bitmask
sl@0	2110	** for all tables to the left of a left join is important. Ticket #3015.
sl@0	2111	*/
sl@0	2112	for(i=0; i<pTabList->nSrc; i++){
sl@0	2113	createMask(&maskSet, pTabList->a[i].iCursor);
sl@0	2114	}
sl@0	2115	#ifndef NDEBUG
sl@0	2116	{
sl@0	2117	Bitmask toTheLeft = 0;
sl@0	2118	for(i=0; i<pTabList->nSrc; i++){
sl@0	2119	Bitmask m = getMask(&maskSet, pTabList->a[i].iCursor);
sl@0	2120	assert( (m-1)==toTheLeft );
sl@0	2121	toTheLeft \|= m;
sl@0	2122	}
sl@0	2123	}
sl@0	2124	#endif
sl@0	2125
sl@0	2126	/* Analyze all of the subexpressions. Note that exprAnalyze() might
sl@0	2127	** add new virtual terms onto the end of the WHERE clause. We do not
sl@0	2128	** want to analyze these virtual terms, so start analyzing at the end
sl@0	2129	** and work forward so that the added virtual terms are never processed.
sl@0	2130	*/
sl@0	2131	exprAnalyzeAll(pTabList, &wc);
sl@0	2132	if( db->mallocFailed ){
sl@0	2133	goto whereBeginError;
sl@0	2134	}
sl@0	2135
sl@0	2136	/* Chose the best index to use for each table in the FROM clause.
sl@0	2137	**
sl@0	2138	** This loop fills in the following fields:
sl@0	2139	**
sl@0	2140	** pWInfo->a[].pIdx The index to use for this level of the loop.
sl@0	2141	** pWInfo->a[].flags WHERE_xxx flags associated with pIdx
sl@0	2142	** pWInfo->a[].nEq The number of == and IN constraints
sl@0	2143	** pWInfo->a[].iFrom Which term of the FROM clause is being coded
sl@0	2144	** pWInfo->a[].iTabCur The VDBE cursor for the database table
sl@0	2145	** pWInfo->a[].iIdxCur The VDBE cursor for the index
sl@0	2146	**
sl@0	2147	** This loop also figures out the nesting order of tables in the FROM
sl@0	2148	** clause.
sl@0	2149	*/
sl@0	2150	notReady = ~(Bitmask)0;
sl@0	2151	pTabItem = pTabList->a;
sl@0	2152	pLevel = pWInfo->a;
sl@0	2153	andFlags = ~0;
sl@0	2154	WHERETRACE(("* Optimizer Start *\n"));
sl@0	2155	for(i=iFrom=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
sl@0	2156	Index pIdx; / Index for FROM table at pTabItem */
sl@0	2157	int flags; /* Flags asssociated with pIdx */
sl@0	2158	int nEq; /* Number of == or IN constraints */
sl@0	2159	double cost; /* The cost for pIdx */
sl@0	2160	int j; /* For looping over FROM tables */
sl@0	2161	Index pBest = 0; / The best index seen so far */
sl@0	2162	int bestFlags = 0; /* Flags associated with pBest */
sl@0	2163	int bestNEq = 0; /* nEq associated with pBest */
sl@0	2164	double lowestCost; /* Cost of the pBest */
sl@0	2165	int bestJ = 0; /* The value of j */
sl@0	2166	Bitmask m; /* Bitmask value for j or bestJ */
sl@0	2167	int once = 0; /* True when first table is seen */
sl@0	2168	sqlite3_index_info pIndex; / Current virtual index */
sl@0	2169
sl@0	2170	lowestCost = SQLITE_BIG_DBL;
sl@0	2171	for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
sl@0	2172	int doNotReorder; /* True if this table should not be reordered */
sl@0	2173
sl@0	2174	doNotReorder = (pTabItem->jointype & (JT_LEFT\|JT_CROSS))!=0;
sl@0	2175	if( once && doNotReorder ) break;
sl@0	2176	m = getMask(&maskSet, pTabItem->iCursor);
sl@0	2177	if( (m & notReady)==0 ){
sl@0	2178	if( j==iFrom ) iFrom++;
sl@0	2179	continue;
sl@0	2180	}
sl@0	2181	assert( pTabItem->pTab );
sl@0	2182	#ifndef SQLITE_OMIT_VIRTUALTABLE
sl@0	2183	if( IsVirtual(pTabItem->pTab) ){
sl@0	2184	sqlite3_index_info **ppIdxInfo = &pWInfo->a[j].pIdxInfo;
sl@0	2185	cost = bestVirtualIndex(pParse, &wc, pTabItem, notReady,
sl@0	2186	ppOrderBy ? *ppOrderBy : 0, i==0,
sl@0	2187	ppIdxInfo);
sl@0	2188	flags = WHERE_VIRTUALTABLE;
sl@0	2189	pIndex = *ppIdxInfo;
sl@0	2190	if( pIndex && pIndex->orderByConsumed ){
sl@0	2191	flags = WHERE_VIRTUALTABLE \| WHERE_ORDERBY;
sl@0	2192	}
sl@0	2193	pIdx = 0;
sl@0	2194	nEq = 0;
sl@0	2195	if( (SQLITE_BIG_DBL/2.0)<cost ){
sl@0	2196	/* The cost is not allowed to be larger than SQLITE_BIG_DBL (the
sl@0	2197	** inital value of lowestCost in this loop. If it is, then
sl@0	2198	** the (cost<lowestCost) test below will never be true and
sl@0	2199	** pLevel->pBestIdx never set.
sl@0	2200	*/
sl@0	2201	cost = (SQLITE_BIG_DBL/2.0);
sl@0	2202	}
sl@0	2203	}else
sl@0	2204	#endif
sl@0	2205	{
sl@0	2206	cost = bestIndex(pParse, &wc, pTabItem, notReady,
sl@0	2207	(i==0 && ppOrderBy) ? *ppOrderBy : 0,
sl@0	2208	&pIdx, &flags, &nEq);
sl@0	2209	pIndex = 0;
sl@0	2210	}
sl@0	2211	if( cost<lowestCost ){
sl@0	2212	once = 1;
sl@0	2213	lowestCost = cost;
sl@0	2214	pBest = pIdx;
sl@0	2215	bestFlags = flags;
sl@0	2216	bestNEq = nEq;
sl@0	2217	bestJ = j;
sl@0	2218	pLevel->pBestIdx = pIndex;
sl@0	2219	}
sl@0	2220	if( doNotReorder ) break;
sl@0	2221	}
sl@0	2222	WHERETRACE(("*** Optimizer selects table %d for loop %d\n", bestJ,
sl@0	2223	pLevel-pWInfo->a));
sl@0	2224	if( (bestFlags & WHERE_ORDERBY)!=0 ){
sl@0	2225	*ppOrderBy = 0;
sl@0	2226	}
sl@0	2227	andFlags &= bestFlags;
sl@0	2228	pLevel->flags = bestFlags;
sl@0	2229	pLevel->pIdx = pBest;
sl@0	2230	pLevel->nEq = bestNEq;
sl@0	2231	pLevel->aInLoop = 0;
sl@0	2232	pLevel->nIn = 0;
sl@0	2233	if( pBest ){
sl@0	2234	pLevel->iIdxCur = pParse->nTab++;
sl@0	2235	}else{
sl@0	2236	pLevel->iIdxCur = -1;
sl@0	2237	}
sl@0	2238	notReady &= ~getMask(&maskSet, pTabList->a[bestJ].iCursor);
sl@0	2239	pLevel->iFrom = bestJ;
sl@0	2240
sl@0	2241	/* Check that if the table scanned by this loop iteration had an
sl@0	2242	** INDEXED BY clause attached to it, that the named index is being
sl@0	2243	** used for the scan. If not, then query compilation has failed.
sl@0	2244	** Return an error.
sl@0	2245	*/
sl@0	2246	pIdx = pTabList->a[bestJ].pIndex;
sl@0	2247	assert( !pIdx \|\| !pBest \|\| pIdx==pBest );
sl@0	2248	if( pIdx && pBest!=pIdx ){
sl@0	2249	sqlite3ErrorMsg(pParse, "cannot use index: %s", pIdx->zName);
sl@0	2250	goto whereBeginError;
sl@0	2251	}
sl@0	2252	}
sl@0	2253	WHERETRACE(("* Optimizer Finished *\n"));
sl@0	2254
sl@0	2255	/* If the total query only selects a single row, then the ORDER BY
sl@0	2256	** clause is irrelevant.
sl@0	2257	*/
sl@0	2258	if( (andFlags & WHERE_UNIQUE)!=0 && ppOrderBy ){
sl@0	2259	*ppOrderBy = 0;
sl@0	2260	}
sl@0	2261
sl@0	2262	/* If the caller is an UPDATE or DELETE statement that is requesting
sl@0	2263	** to use a one-pass algorithm, determine if this is appropriate.
sl@0	2264	** The one-pass algorithm only works if the WHERE clause constraints
sl@0	2265	** the statement to update a single row.
sl@0	2266	*/
sl@0	2267	assert( (wflags & WHERE_ONEPASS_DESIRED)==0 \|\| pWInfo->nLevel==1 );
sl@0	2268	if( (wflags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){
sl@0	2269	pWInfo->okOnePass = 1;
sl@0	2270	pWInfo->a[0].flags &= ~WHERE_IDX_ONLY;
sl@0	2271	}
sl@0	2272
sl@0	2273	/* Open all tables in the pTabList and any indices selected for
sl@0	2274	** searching those tables.
sl@0	2275	*/
sl@0	2276	sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
sl@0	2277	for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
sl@0	2278	Table pTab; / Table to open */
sl@0	2279	Index pIx; / Index used to access pTab (if any) */
sl@0	2280	int iDb; /* Index of database containing table/index */
sl@0	2281	int iIdxCur = pLevel->iIdxCur;
sl@0	2282
sl@0	2283	#ifndef SQLITE_OMIT_EXPLAIN
sl@0	2284	if( pParse->explain==2 ){
sl@0	2285	char *zMsg;
sl@0	2286	struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom];
sl@0	2287	zMsg = sqlite3MPrintf(db, "TABLE %s", pItem->zName);
sl@0	2288	if( pItem->zAlias ){
sl@0	2289	zMsg = sqlite3MAppendf(db, zMsg, "%s AS %s", zMsg, pItem->zAlias);
sl@0	2290	}
sl@0	2291	if( (pIx = pLevel->pIdx)!=0 ){
sl@0	2292	zMsg = sqlite3MAppendf(db, zMsg, "%s WITH INDEX %s", zMsg, pIx->zName);
sl@0	2293	}else if( pLevel->flags & (WHERE_ROWID_EQ\|WHERE_ROWID_RANGE) ){
sl@0	2294	zMsg = sqlite3MAppendf(db, zMsg, "%s USING PRIMARY KEY", zMsg);
sl@0	2295	}
sl@0	2296	#ifndef SQLITE_OMIT_VIRTUALTABLE
sl@0	2297	else if( pLevel->pBestIdx ){
sl@0	2298	sqlite3_index_info *pBestIdx = pLevel->pBestIdx;
sl@0	2299	zMsg = sqlite3MAppendf(db, zMsg, "%s VIRTUAL TABLE INDEX %d:%s", zMsg,
sl@0	2300	pBestIdx->idxNum, pBestIdx->idxStr);
sl@0	2301	}
sl@0	2302	#endif
sl@0	2303	if( pLevel->flags & WHERE_ORDERBY ){
sl@0	2304	zMsg = sqlite3MAppendf(db, zMsg, "%s ORDER BY", zMsg);
sl@0	2305	}
sl@0	2306	sqlite3VdbeAddOp4(v, OP_Explain, i, pLevel->iFrom, 0, zMsg, P4_DYNAMIC);
sl@0	2307	}
sl@0	2308	#endif /* SQLITE_OMIT_EXPLAIN */
sl@0	2309	pTabItem = &pTabList->a[pLevel->iFrom];
sl@0	2310	pTab = pTabItem->pTab;
sl@0	2311	iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
sl@0	2312	if( (pTab->tabFlags & TF_Ephemeral)!=0 \|\| pTab->pSelect ) continue;
sl@0	2313	#ifndef SQLITE_OMIT_VIRTUALTABLE
sl@0	2314	if( pLevel->pBestIdx ){
sl@0	2315	int iCur = pTabItem->iCursor;
sl@0	2316	sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0,
sl@0	2317	(const char*)pTab->pVtab, P4_VTAB);
sl@0	2318	}else
sl@0	2319	#endif
sl@0	2320	if( (pLevel->flags & WHERE_IDX_ONLY)==0 ){
sl@0	2321	int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead;
sl@0	2322	sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);
sl@0	2323	if( !pWInfo->okOnePass && pTab->nCol<(sizeof(Bitmask)*8) ){
sl@0	2324	Bitmask b = pTabItem->colUsed;
sl@0	2325	int n = 0;
sl@0	2326	for(; b; b=b>>1, n++){}
sl@0	2327	sqlite3VdbeChangeP2(v, sqlite3VdbeCurrentAddr(v)-2, n);
sl@0	2328	assert( n<=pTab->nCol );
sl@0	2329	}
sl@0	2330	}else{
sl@0	2331	sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
sl@0	2332	}
sl@0	2333	pLevel->iTabCur = pTabItem->iCursor;
sl@0	2334	if( (pIx = pLevel->pIdx)!=0 ){
sl@0	2335	KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIx);
sl@0	2336	assert( pIx->pSchema==pTab->pSchema );
sl@0	2337	sqlite3VdbeAddOp2(v, OP_SetNumColumns, 0, pIx->nColumn+1);
sl@0	2338	sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIx->tnum, iDb,
sl@0	2339	(char*)pKey, P4_KEYINFO_HANDOFF);
sl@0	2340	VdbeComment((v, "%s", pIx->zName));
sl@0	2341	}
sl@0	2342	sqlite3CodeVerifySchema(pParse, iDb);
sl@0	2343	}
sl@0	2344	pWInfo->iTop = sqlite3VdbeCurrentAddr(v);
sl@0	2345
sl@0	2346	/* Generate the code to do the search. Each iteration of the for
sl@0	2347	** loop below generates code for a single nested loop of the VM
sl@0	2348	** program.
sl@0	2349	*/
sl@0	2350	notReady = ~(Bitmask)0;
sl@0	2351	for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
sl@0	2352	int j, k;
sl@0	2353	int iCur = pTabItem->iCursor; /* The VDBE cursor for the table */
sl@0	2354	Index pIdx; / The index we will be using */
sl@0	2355	int nxt; /* Where to jump to continue with the next IN case */
sl@0	2356	int iIdxCur; /* The VDBE cursor for the index */
sl@0	2357	int omitTable; /* True if we use the index only */
sl@0	2358	int bRev; /* True if we need to scan in reverse order */
sl@0	2359
sl@0	2360	pTabItem = &pTabList->a[pLevel->iFrom];
sl@0	2361	iCur = pTabItem->iCursor;
sl@0	2362	pIdx = pLevel->pIdx;
sl@0	2363	iIdxCur = pLevel->iIdxCur;
sl@0	2364	bRev = (pLevel->flags & WHERE_REVERSE)!=0;
sl@0	2365	omitTable = (pLevel->flags & WHERE_IDX_ONLY)!=0;
sl@0	2366
sl@0	2367	/* Create labels for the "break" and "continue" instructions
sl@0	2368	** for the current loop. Jump to brk to break out of a loop.
sl@0	2369	** Jump to cont to go immediately to the next iteration of the
sl@0	2370	** loop.
sl@0	2371	**
sl@0	2372	** When there is an IN operator, we also have a "nxt" label that
sl@0	2373	** means to continue with the next IN value combination. When
sl@0	2374	** there are no IN operators in the constraints, the "nxt" label
sl@0	2375	** is the same as "brk".
sl@0	2376	*/
sl@0	2377	brk = pLevel->brk = pLevel->nxt = sqlite3VdbeMakeLabel(v);
sl@0	2378	cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
sl@0	2379
sl@0	2380	/* If this is the right table of a LEFT OUTER JOIN, allocate and
sl@0	2381	** initialize a memory cell that records if this table matches any
sl@0	2382	** row of the left table of the join.
sl@0	2383	*/
sl@0	2384	if( pLevel->iFrom>0 && (pTabItem[0].jointype & JT_LEFT)!=0 ){
sl@0	2385	pLevel->iLeftJoin = ++pParse->nMem;
sl@0	2386	sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin);
sl@0	2387	VdbeComment((v, "init LEFT JOIN no-match flag"));
sl@0	2388	}
sl@0	2389
sl@0	2390	#ifndef SQLITE_OMIT_VIRTUALTABLE
sl@0	2391	if( pLevel->pBestIdx ){
sl@0	2392	/* Case 0: The table is a virtual-table. Use the VFilter and VNext
sl@0	2393	** to access the data.
sl@0	2394	*/
sl@0	2395	int j;
sl@0	2396	int iReg; /* P3 Value for OP_VFilter */
sl@0	2397	sqlite3_index_info *pBestIdx = pLevel->pBestIdx;
sl@0	2398	int nConstraint = pBestIdx->nConstraint;
sl@0	2399	struct sqlite3_index_constraint_usage *aUsage =
sl@0	2400	pBestIdx->aConstraintUsage;
sl@0	2401	const struct sqlite3_index_constraint *aConstraint =
sl@0	2402	pBestIdx->aConstraint;
sl@0	2403
sl@0	2404	iReg = sqlite3GetTempRange(pParse, nConstraint+2);
sl@0	2405	pParse->disableColCache++;
sl@0	2406	for(j=1; j<=nConstraint; j++){
sl@0	2407	int k;
sl@0	2408	for(k=0; k<nConstraint; k++){
sl@0	2409	if( aUsage[k].argvIndex==j ){
sl@0	2410	int iTerm = aConstraint[k].iTermOffset;
sl@0	2411	assert( pParse->disableColCache );
sl@0	2412	sqlite3ExprCode(pParse, wc.a[iTerm].pExpr->pRight, iReg+j+1);
sl@0	2413	break;
sl@0	2414	}
sl@0	2415	}
sl@0	2416	if( k==nConstraint ) break;
sl@0	2417	}
sl@0	2418	assert( pParse->disableColCache );
sl@0	2419	pParse->disableColCache--;
sl@0	2420	sqlite3VdbeAddOp2(v, OP_Integer, pBestIdx->idxNum, iReg);
sl@0	2421	sqlite3VdbeAddOp2(v, OP_Integer, j-1, iReg+1);
sl@0	2422	sqlite3VdbeAddOp4(v, OP_VFilter, iCur, brk, iReg, pBestIdx->idxStr,
sl@0	2423	pBestIdx->needToFreeIdxStr ? P4_MPRINTF : P4_STATIC);
sl@0	2424	sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
sl@0	2425	pBestIdx->needToFreeIdxStr = 0;
sl@0	2426	for(j=0; j<nConstraint; j++){
sl@0	2427	if( aUsage[j].omit ){
sl@0	2428	int iTerm = aConstraint[j].iTermOffset;
sl@0	2429	disableTerm(pLevel, &wc.a[iTerm]);
sl@0	2430	}
sl@0	2431	}
sl@0	2432	pLevel->op = OP_VNext;
sl@0	2433	pLevel->p1 = iCur;
sl@0	2434	pLevel->p2 = sqlite3VdbeCurrentAddr(v);
sl@0	2435	}else
sl@0	2436	#endif /* SQLITE_OMIT_VIRTUALTABLE */
sl@0	2437
sl@0	2438	if( pLevel->flags & WHERE_ROWID_EQ ){
sl@0	2439	/* Case 1: We can directly reference a single row using an
sl@0	2440	** equality comparison against the ROWID field. Or
sl@0	2441	** we reference multiple rows using a "rowid IN (...)"
sl@0	2442	** construct.
sl@0	2443	*/
sl@0	2444	int r1;
sl@0	2445	int rtmp = sqlite3GetTempReg(pParse);
sl@0	2446	pTerm = findTerm(&wc, iCur, -1, notReady, WO_EQ\|WO_IN, 0);
sl@0	2447	assert( pTerm!=0 );
sl@0	2448	assert( pTerm->pExpr!=0 );
sl@0	2449	assert( pTerm->leftCursor==iCur );
sl@0	2450	assert( omitTable==0 );
sl@0	2451	r1 = codeEqualityTerm(pParse, pTerm, pLevel, rtmp);
sl@0	2452	nxt = pLevel->nxt;
sl@0	2453	sqlite3VdbeAddOp2(v, OP_MustBeInt, r1, nxt);
sl@0	2454	sqlite3VdbeAddOp3(v, OP_NotExists, iCur, nxt, r1);
sl@0	2455	sqlite3ReleaseTempReg(pParse, rtmp);
sl@0	2456	VdbeComment((v, "pk"));
sl@0	2457	pLevel->op = OP_Noop;
sl@0	2458	}else if( pLevel->flags & WHERE_ROWID_RANGE ){
sl@0	2459	/* Case 2: We have an inequality comparison against the ROWID field.
sl@0	2460	*/
sl@0	2461	int testOp = OP_Noop;
sl@0	2462	int start;
sl@0	2463	WhereTerm pStart, pEnd;
sl@0	2464
sl@0	2465	assert( omitTable==0 );
sl@0	2466	pStart = findTerm(&wc, iCur, -1, notReady, WO_GT\|WO_GE, 0);
sl@0	2467	pEnd = findTerm(&wc, iCur, -1, notReady, WO_LT\|WO_LE, 0);
sl@0	2468	if( bRev ){
sl@0	2469	pTerm = pStart;
sl@0	2470	pStart = pEnd;
sl@0	2471	pEnd = pTerm;
sl@0	2472	}
sl@0	2473	if( pStart ){
sl@0	2474	Expr *pX;
sl@0	2475	int r1;
sl@0	2476	pX = pStart->pExpr;
sl@0	2477	assert( pX!=0 );
sl@0	2478	assert( pStart->leftCursor==iCur );
sl@0	2479
sl@0	2480	/* The ForceInt instruction may modify the register that it operates
sl@0	2481	** on. For example it may replace a real value with an integer one,
sl@0	2482	** or if p3 is true it may increment the register value. For this
sl@0	2483	** reason we need to make sure that register r1 is really a newly
sl@0	2484	** allocated temporary register, and not part of the column-cache.
sl@0	2485	** For this reason we cannot use sqlite3ExprCodeTemp() here.
sl@0	2486	*/
sl@0	2487	r1 = sqlite3GetTempReg(pParse);
sl@0	2488	sqlite3ExprCode(pParse, pX->pRight, r1);
sl@0	2489
sl@0	2490	sqlite3VdbeAddOp3(v, OP_ForceInt, r1, brk,
sl@0	2491	pX->op==TK_LE \|\| pX->op==TK_GT);
sl@0	2492	sqlite3VdbeAddOp3(v, bRev ? OP_MoveLt : OP_MoveGe, iCur, brk, r1);
sl@0	2493	VdbeComment((v, "pk"));
sl@0	2494	sqlite3ReleaseTempReg(pParse, r1);
sl@0	2495	disableTerm(pLevel, pStart);
sl@0	2496	}else{
sl@0	2497	sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, brk);
sl@0	2498	}
sl@0	2499	if( pEnd ){
sl@0	2500	Expr *pX;
sl@0	2501	pX = pEnd->pExpr;
sl@0	2502	assert( pX!=0 );
sl@0	2503	assert( pEnd->leftCursor==iCur );
sl@0	2504	pLevel->iMem = ++pParse->nMem;
sl@0	2505	sqlite3ExprCode(pParse, pX->pRight, pLevel->iMem);
sl@0	2506	if( pX->op==TK_LT \|\| pX->op==TK_GT ){
sl@0	2507	testOp = bRev ? OP_Le : OP_Ge;
sl@0	2508	}else{
sl@0	2509	testOp = bRev ? OP_Lt : OP_Gt;
sl@0	2510	}
sl@0	2511	disableTerm(pLevel, pEnd);
sl@0	2512	}
sl@0	2513	start = sqlite3VdbeCurrentAddr(v);
sl@0	2514	pLevel->op = bRev ? OP_Prev : OP_Next;
sl@0	2515	pLevel->p1 = iCur;
sl@0	2516	pLevel->p2 = start;
sl@0	2517	if( testOp!=OP_Noop ){
sl@0	2518	int r1 = sqlite3GetTempReg(pParse);
sl@0	2519	sqlite3VdbeAddOp2(v, OP_Rowid, iCur, r1);
sl@0	2520	/* sqlite3VdbeAddOp2(v, OP_SCopy, pLevel->iMem, 0); */
sl@0	2521	sqlite3VdbeAddOp3(v, testOp, pLevel->iMem, brk, r1);
sl@0	2522	sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC \| SQLITE_JUMPIFNULL);
sl@0	2523	sqlite3ReleaseTempReg(pParse, r1);
sl@0	2524	}
sl@0	2525	}else if( pLevel->flags & (WHERE_COLUMN_RANGE\|WHERE_COLUMN_EQ) ){
sl@0	2526	/* Case 3: A scan using an index.
sl@0	2527	**
sl@0	2528	** The WHERE clause may contain zero or more equality
sl@0	2529	** terms ("==" or "IN" operators) that refer to the N
sl@0	2530	** left-most columns of the index. It may also contain
sl@0	2531	** inequality constraints (>, <, >= or <=) on the indexed
sl@0	2532	** column that immediately follows the N equalities. Only
sl@0	2533	** the right-most column can be an inequality - the rest must
sl@0	2534	** use the "==" and "IN" operators. For example, if the
sl@0	2535	** index is on (x,y,z), then the following clauses are all
sl@0	2536	** optimized:
sl@0	2537	**
sl@0	2538	** x=5
sl@0	2539	** x=5 AND y=10
sl@0	2540	** x=5 AND y<10
sl@0	2541	** x=5 AND y>5 AND y<10
sl@0	2542	** x=5 AND y=5 AND z<=10
sl@0	2543	**
sl@0	2544	** The z<10 term of the following cannot be used, only
sl@0	2545	** the x=5 term:
sl@0	2546	**
sl@0	2547	** x=5 AND z<10
sl@0	2548	**
sl@0	2549	** N may be zero if there are inequality constraints.
sl@0	2550	** If there are no inequality constraints, then N is at
sl@0	2551	** least one.
sl@0	2552	**
sl@0	2553	** This case is also used when there are no WHERE clause
sl@0	2554	** constraints but an index is selected anyway, in order
sl@0	2555	** to force the output order to conform to an ORDER BY.
sl@0	2556	*/
sl@0	2557	int aStartOp[] = {
sl@0	2558	0,
sl@0	2559	0,
sl@0	2560	OP_Rewind, /* 2: (!start_constraints && startEq && !bRev) */
sl@0	2561	OP_Last, /* 3: (!start_constraints && startEq && bRev) */
sl@0	2562	OP_MoveGt, /* 4: (start_constraints && !startEq && !bRev) */
sl@0	2563	OP_MoveLt, /* 5: (start_constraints && !startEq && bRev) */
sl@0	2564	OP_MoveGe, /* 6: (start_constraints && startEq && !bRev) */
sl@0	2565	OP_MoveLe /* 7: (start_constraints && startEq && bRev) */
sl@0	2566	};
sl@0	2567	int aEndOp[] = {
sl@0	2568	OP_Noop, /* 0: (!end_constraints) */
sl@0	2569	OP_IdxGE, /* 1: (end_constraints && !bRev) */
sl@0	2570	OP_IdxLT /* 2: (end_constraints && bRev) */
sl@0	2571	};
sl@0	2572	int nEq = pLevel->nEq;
sl@0	2573	int isMinQuery = 0; /* If this is an optimized SELECT min(x).. */
sl@0	2574	int regBase; /* Base register holding constraint values */
sl@0	2575	int r1; /* Temp register */
sl@0	2576	WhereTerm pRangeStart = 0; / Inequality constraint at range start */
sl@0	2577	WhereTerm pRangeEnd = 0; / Inequality constraint at range end */
sl@0	2578	int startEq; /* True if range start uses ==, >= or <= */
sl@0	2579	int endEq; /* True if range end uses ==, >= or <= */
sl@0	2580	int start_constraints; /* Start of range is constrained */
sl@0	2581	int k = pIdx->aiColumn[nEq]; /* Column for inequality constraints */
sl@0	2582	int nConstraint; /* Number of constraint terms */
sl@0	2583	int op;
sl@0	2584
sl@0	2585	/* Generate code to evaluate all constraint terms using == or IN
sl@0	2586	** and store the values of those terms in an array of registers
sl@0	2587	** starting at regBase.
sl@0	2588	*/
sl@0	2589	regBase = codeAllEqualityTerms(pParse, pLevel, &wc, notReady, 2);
sl@0	2590	nxt = pLevel->nxt;
sl@0	2591
sl@0	2592	/* If this loop satisfies a sort order (pOrderBy) request that
sl@0	2593	** was passed to this function to implement a "SELECT min(x) ..."
sl@0	2594	** query, then the caller will only allow the loop to run for
sl@0	2595	** a single iteration. This means that the first row returned
sl@0	2596	** should not have a NULL value stored in 'x'. If column 'x' is
sl@0	2597	** the first one after the nEq equality constraints in the index,
sl@0	2598	** this requires some special handling.
sl@0	2599	*/
sl@0	2600	if( (wflags&WHERE_ORDERBY_MIN)!=0
sl@0	2601	&& (pLevel->flags&WHERE_ORDERBY)
sl@0	2602	&& (pIdx->nColumn>nEq)
sl@0	2603	){
sl@0	2604	assert( pOrderBy->nExpr==1 );
sl@0	2605	assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] );
sl@0	2606	isMinQuery = 1;
sl@0	2607	}
sl@0	2608
sl@0	2609	/* Find any inequality constraint terms for the start and end
sl@0	2610	** of the range.
sl@0	2611	*/
sl@0	2612	if( pLevel->flags & WHERE_TOP_LIMIT ){
sl@0	2613	pRangeEnd = findTerm(&wc, iCur, k, notReady, (WO_LT\|WO_LE), pIdx);
sl@0	2614	}
sl@0	2615	if( pLevel->flags & WHERE_BTM_LIMIT ){
sl@0	2616	pRangeStart = findTerm(&wc, iCur, k, notReady, (WO_GT\|WO_GE), pIdx);
sl@0	2617	}
sl@0	2618
sl@0	2619	/* If we are doing a reverse order scan on an ascending index, or
sl@0	2620	** a forward order scan on a descending index, interchange the
sl@0	2621	** start and end terms (pRangeStart and pRangeEnd).
sl@0	2622	*/
sl@0	2623	if( bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC) ){
sl@0	2624	SWAP(WhereTerm *, pRangeEnd, pRangeStart);
sl@0	2625	}
sl@0	2626
sl@0	2627	testcase( pRangeStart && pRangeStart->eOperator & WO_LE );
sl@0	2628	testcase( pRangeStart && pRangeStart->eOperator & WO_GE );
sl@0	2629	testcase( pRangeEnd && pRangeEnd->eOperator & WO_LE );
sl@0	2630	testcase( pRangeEnd && pRangeEnd->eOperator & WO_GE );
sl@0	2631	startEq = !pRangeStart \|\| pRangeStart->eOperator & (WO_LE\|WO_GE);
sl@0	2632	endEq = !pRangeEnd \|\| pRangeEnd->eOperator & (WO_LE\|WO_GE);
sl@0	2633	start_constraints = pRangeStart \|\| nEq>0;
sl@0	2634
sl@0	2635	/* Seek the index cursor to the start of the range. */
sl@0	2636	nConstraint = nEq;
sl@0	2637	if( pRangeStart ){
sl@0	2638	int dcc = pParse->disableColCache;
sl@0	2639	if( pRangeEnd ){
sl@0	2640	pParse->disableColCache++;
sl@0	2641	}
sl@0	2642	sqlite3ExprCode(pParse, pRangeStart->pExpr->pRight, regBase+nEq);
sl@0	2643	pParse->disableColCache = dcc;
sl@0	2644	sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, nxt);
sl@0	2645	nConstraint++;
sl@0	2646	}else if( isMinQuery ){
sl@0	2647	sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
sl@0	2648	nConstraint++;
sl@0	2649	startEq = 0;
sl@0	2650	start_constraints = 1;
sl@0	2651	}
sl@0	2652	codeApplyAffinity(pParse, regBase, nConstraint, pIdx);
sl@0	2653	op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
sl@0	2654	assert( op!=0 );
sl@0	2655	testcase( op==OP_Rewind );
sl@0	2656	testcase( op==OP_Last );
sl@0	2657	testcase( op==OP_MoveGt );
sl@0	2658	testcase( op==OP_MoveGe );
sl@0	2659	testcase( op==OP_MoveLe );
sl@0	2660	testcase( op==OP_MoveLt );
sl@0	2661	sqlite3VdbeAddOp4(v, op, iIdxCur, nxt, regBase,
sl@0	2662	SQLITE_INT_TO_PTR(nConstraint), P4_INT32);
sl@0	2663
sl@0	2664	/* Load the value for the inequality constraint at the end of the
sl@0	2665	** range (if any).
sl@0	2666	*/
sl@0	2667	nConstraint = nEq;
sl@0	2668	if( pRangeEnd ){
sl@0	2669	sqlite3ExprCode(pParse, pRangeEnd->pExpr->pRight, regBase+nEq);
sl@0	2670	sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, nxt);
sl@0	2671	codeApplyAffinity(pParse, regBase, nEq+1, pIdx);
sl@0	2672	nConstraint++;
sl@0	2673	}
sl@0	2674
sl@0	2675	/* Top of the loop body */
sl@0	2676	pLevel->p2 = sqlite3VdbeCurrentAddr(v);
sl@0	2677
sl@0	2678	/* Check if the index cursor is past the end of the range. */
sl@0	2679	op = aEndOp[(pRangeEnd \|\| nEq) * (1 + bRev)];
sl@0	2680	testcase( op==OP_Noop );
sl@0	2681	testcase( op==OP_IdxGE );
sl@0	2682	testcase( op==OP_IdxLT );
sl@0	2683	sqlite3VdbeAddOp4(v, op, iIdxCur, nxt, regBase,
sl@0	2684	SQLITE_INT_TO_PTR(nConstraint), P4_INT32);
sl@0	2685	sqlite3VdbeChangeP5(v, endEq!=bRev);
sl@0	2686
sl@0	2687	/* If there are inequality constraints, check that the value
sl@0	2688	** of the table column that the inequality contrains is not NULL.
sl@0	2689	** If it is, jump to the next iteration of the loop.
sl@0	2690	*/
sl@0	2691	r1 = sqlite3GetTempReg(pParse);
sl@0	2692	testcase( pLevel->flags & WHERE_BTM_LIMIT );
sl@0	2693	testcase( pLevel->flags & WHERE_TOP_LIMIT );
sl@0	2694	if( pLevel->flags & (WHERE_BTM_LIMIT\|WHERE_TOP_LIMIT) ){
sl@0	2695	sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
sl@0	2696	sqlite3VdbeAddOp2(v, OP_IsNull, r1, cont);
sl@0	2697	}
sl@0	2698
sl@0	2699	/* Seek the table cursor, if required */
sl@0	2700	if( !omitTable ){
sl@0	2701	sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, r1);
sl@0	2702	sqlite3VdbeAddOp3(v, OP_MoveGe, iCur, 0, r1); /* Deferred seek */
sl@0	2703	}
sl@0	2704	sqlite3ReleaseTempReg(pParse, r1);
sl@0	2705
sl@0	2706	/* Record the instruction used to terminate the loop. Disable
sl@0	2707	** WHERE clause terms made redundant by the index range scan.
sl@0	2708	*/
sl@0	2709	pLevel->op = bRev ? OP_Prev : OP_Next;
sl@0	2710	pLevel->p1 = iIdxCur;
sl@0	2711	disableTerm(pLevel, pRangeStart);
sl@0	2712	disableTerm(pLevel, pRangeEnd);
sl@0	2713	}else{
sl@0	2714	/* Case 4: There is no usable index. We must do a complete
sl@0	2715	** scan of the entire table.
sl@0	2716	*/
sl@0	2717	assert( omitTable==0 );
sl@0	2718	assert( bRev==0 );
sl@0	2719	pLevel->op = OP_Next;
sl@0	2720	pLevel->p1 = iCur;
sl@0	2721	pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, OP_Rewind, iCur, brk);
sl@0	2722	pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
sl@0	2723	}
sl@0	2724	notReady &= ~getMask(&maskSet, iCur);
sl@0	2725
sl@0	2726	/* Insert code to test every subexpression that can be completely
sl@0	2727	** computed using the current set of tables.
sl@0	2728	*/
sl@0	2729	k = 0;
sl@0	2730	for(pTerm=wc.a, j=wc.nTerm; j>0; j--, pTerm++){
sl@0	2731	Expr *pE;
sl@0	2732	testcase( pTerm->flags & TERM_VIRTUAL );
sl@0	2733	testcase( pTerm->flags & TERM_CODED );
sl@0	2734	if( pTerm->flags & (TERM_VIRTUAL\|TERM_CODED) ) continue;
sl@0	2735	if( (pTerm->prereqAll & notReady)!=0 ) continue;
sl@0	2736	pE = pTerm->pExpr;
sl@0	2737	assert( pE!=0 );
sl@0	2738	if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
sl@0	2739	continue;
sl@0	2740	}
sl@0	2741	pParse->disableColCache += k;
sl@0	2742	sqlite3ExprIfFalse(pParse, pE, cont, SQLITE_JUMPIFNULL);
sl@0	2743	pParse->disableColCache -= k;
sl@0	2744	k = 1;
sl@0	2745	pTerm->flags \|= TERM_CODED;
sl@0	2746	}
sl@0	2747
sl@0	2748	/* For a LEFT OUTER JOIN, generate code that will record the fact that
sl@0	2749	** at least one row of the right table has matched the left table.
sl@0	2750	*/
sl@0	2751	if( pLevel->iLeftJoin ){
sl@0	2752	pLevel->top = sqlite3VdbeCurrentAddr(v);
sl@0	2753	sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin);
sl@0	2754	VdbeComment((v, "record LEFT JOIN hit"));
sl@0	2755	sqlite3ExprClearColumnCache(pParse, pLevel->iTabCur);
sl@0	2756	sqlite3ExprClearColumnCache(pParse, pLevel->iIdxCur);
sl@0	2757	for(pTerm=wc.a, j=0; j<wc.nTerm; j++, pTerm++){
sl@0	2758	testcase( pTerm->flags & TERM_VIRTUAL );
sl@0	2759	testcase( pTerm->flags & TERM_CODED );
sl@0	2760	if( pTerm->flags & (TERM_VIRTUAL\|TERM_CODED) ) continue;
sl@0	2761	if( (pTerm->prereqAll & notReady)!=0 ) continue;
sl@0	2762	assert( pTerm->pExpr );
sl@0	2763	sqlite3ExprIfFalse(pParse, pTerm->pExpr, cont, SQLITE_JUMPIFNULL);
sl@0	2764	pTerm->flags \|= TERM_CODED;
sl@0	2765	}
sl@0	2766	}
sl@0	2767	}
sl@0	2768
sl@0	2769	#ifdef SQLITE_TEST /* For testing and debugging use only */
sl@0	2770	/* Record in the query plan information about the current table
sl@0	2771	** and the index used to access it (if any). If the table itself
sl@0	2772	** is not used, its name is just '{}'. If no index is used
sl@0	2773	** the index is listed as "{}". If the primary key is used the
sl@0	2774	** index name is '*'.
sl@0	2775	*/
sl@0	2776	for(i=0; i<pTabList->nSrc; i++){
sl@0	2777	char *z;
sl@0	2778	int n;
sl@0	2779	pLevel = &pWInfo->a[i];
sl@0	2780	pTabItem = &pTabList->a[pLevel->iFrom];
sl@0	2781	z = pTabItem->zAlias;
sl@0	2782	if( z==0 ) z = pTabItem->pTab->zName;
sl@0	2783	n = strlen(z);
sl@0	2784	if( n+nQPlan < sizeof(sqlite3_query_plan)-10 ){
sl@0	2785	if( pLevel->flags & WHERE_IDX_ONLY ){
sl@0	2786	memcpy(&sqlite3_query_plan[nQPlan], "{}", 2);
sl@0	2787	nQPlan += 2;
sl@0	2788	}else{
sl@0	2789	memcpy(&sqlite3_query_plan[nQPlan], z, n);
sl@0	2790	nQPlan += n;
sl@0	2791	}
sl@0	2792	sqlite3_query_plan[nQPlan++] = ' ';
sl@0	2793	}
sl@0	2794	testcase( pLevel->flags & WHERE_ROWID_EQ );
sl@0	2795	testcase( pLevel->flags & WHERE_ROWID_RANGE );
sl@0	2796	if( pLevel->flags & (WHERE_ROWID_EQ\|WHERE_ROWID_RANGE) ){
sl@0	2797	memcpy(&sqlite3_query_plan[nQPlan], "* ", 2);
sl@0	2798	nQPlan += 2;
sl@0	2799	}else if( pLevel->pIdx==0 ){
sl@0	2800	memcpy(&sqlite3_query_plan[nQPlan], "{} ", 3);
sl@0	2801	nQPlan += 3;
sl@0	2802	}else{
sl@0	2803	n = strlen(pLevel->pIdx->zName);
sl@0	2804	if( n+nQPlan < sizeof(sqlite3_query_plan)-2 ){
sl@0	2805	memcpy(&sqlite3_query_plan[nQPlan], pLevel->pIdx->zName, n);
sl@0	2806	nQPlan += n;
sl@0	2807	sqlite3_query_plan[nQPlan++] = ' ';
sl@0	2808	}
sl@0	2809	}
sl@0	2810	}
sl@0	2811	while( nQPlan>0 && sqlite3_query_plan[nQPlan-1]==' ' ){
sl@0	2812	sqlite3_query_plan[--nQPlan] = 0;
sl@0	2813	}
sl@0	2814	sqlite3_query_plan[nQPlan] = 0;
sl@0	2815	nQPlan = 0;
sl@0	2816	#endif /* SQLITE_TEST // Testing and debugging use only */
sl@0	2817
sl@0	2818	/* Record the continuation address in the WhereInfo structure. Then
sl@0	2819	** clean up and return.
sl@0	2820	*/
sl@0	2821	pWInfo->iContinue = cont;
sl@0	2822	whereClauseClear(&wc);
sl@0	2823	return pWInfo;
sl@0	2824
sl@0	2825	/* Jump here if malloc fails */
sl@0	2826	whereBeginError:
sl@0	2827	whereClauseClear(&wc);
sl@0	2828	whereInfoFree(db, pWInfo);
sl@0	2829	return 0;
sl@0	2830	}
sl@0	2831
sl@0	2832	/*
sl@0	2833	** Generate the end of the WHERE loop. See comments on
sl@0	2834	** sqlite3WhereBegin() for additional information.
sl@0	2835	*/
sl@0	2836	void sqlite3WhereEnd(WhereInfo *pWInfo){
sl@0	2837	Parse *pParse = pWInfo->pParse;
sl@0	2838	Vdbe *v = pParse->pVdbe;
sl@0	2839	int i;
sl@0	2840	WhereLevel *pLevel;
sl@0	2841	SrcList *pTabList = pWInfo->pTabList;
sl@0	2842	sqlite3 *db = pParse->db;
sl@0	2843
sl@0	2844	/* Generate loop termination code.
sl@0	2845	*/
sl@0	2846	sqlite3ExprClearColumnCache(pParse, -1);
sl@0	2847	for(i=pTabList->nSrc-1; i>=0; i--){
sl@0	2848	pLevel = &pWInfo->a[i];
sl@0	2849	sqlite3VdbeResolveLabel(v, pLevel->cont);
sl@0	2850	if( pLevel->op!=OP_Noop ){
sl@0	2851	sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2);
sl@0	2852	sqlite3VdbeChangeP5(v, pLevel->p5);
sl@0	2853	}
sl@0	2854	if( pLevel->nIn ){
sl@0	2855	struct InLoop *pIn;
sl@0	2856	int j;
sl@0	2857	sqlite3VdbeResolveLabel(v, pLevel->nxt);
sl@0	2858	for(j=pLevel->nIn, pIn=&pLevel->aInLoop[j-1]; j>0; j--, pIn--){
sl@0	2859	sqlite3VdbeJumpHere(v, pIn->topAddr+1);
sl@0	2860	sqlite3VdbeAddOp2(v, OP_Next, pIn->iCur, pIn->topAddr);
sl@0	2861	sqlite3VdbeJumpHere(v, pIn->topAddr-1);
sl@0	2862	}
sl@0	2863	sqlite3DbFree(db, pLevel->aInLoop);
sl@0	2864	}
sl@0	2865	sqlite3VdbeResolveLabel(v, pLevel->brk);
sl@0	2866	if( pLevel->iLeftJoin ){
sl@0	2867	int addr;
sl@0	2868	addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin);
sl@0	2869	sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);
sl@0	2870	if( pLevel->iIdxCur>=0 ){
sl@0	2871	sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iIdxCur);
sl@0	2872	}
sl@0	2873	sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->top);
sl@0	2874	sqlite3VdbeJumpHere(v, addr);
sl@0	2875	}
sl@0	2876	}
sl@0	2877
sl@0	2878	/* The "break" point is here, just past the end of the outer loop.
sl@0	2879	** Set it.
sl@0	2880	*/
sl@0	2881	sqlite3VdbeResolveLabel(v, pWInfo->iBreak);
sl@0	2882
sl@0	2883	/* Close all of the cursors that were opened by sqlite3WhereBegin.
sl@0	2884	*/
sl@0	2885	for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
sl@0	2886	struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
sl@0	2887	Table *pTab = pTabItem->pTab;
sl@0	2888	assert( pTab!=0 );
sl@0	2889	if( (pTab->tabFlags & TF_Ephemeral)!=0 \|\| pTab->pSelect ) continue;
sl@0	2890	if( !pWInfo->okOnePass && (pLevel->flags & WHERE_IDX_ONLY)==0 ){
sl@0	2891	sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
sl@0	2892	}
sl@0	2893	if( pLevel->pIdx!=0 ){
sl@0	2894	sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
sl@0	2895	}
sl@0	2896
sl@0	2897	/* If this scan uses an index, make code substitutions to read data
sl@0	2898	** from the index in preference to the table. Sometimes, this means
sl@0	2899	** the table need never be read from. This is a performance boost,
sl@0	2900	** as the vdbe level waits until the table is read before actually
sl@0	2901	** seeking the table cursor to the record corresponding to the current
sl@0	2902	** position in the index.
sl@0	2903	**
sl@0	2904	** Calls to the code generator in between sqlite3WhereBegin and
sl@0	2905	** sqlite3WhereEnd will have created code that references the table
sl@0	2906	** directly. This loop scans all that code looking for opcodes
sl@0	2907	** that reference the table and converts them into opcodes that
sl@0	2908	** reference the index.
sl@0	2909	*/
sl@0	2910	if( pLevel->pIdx ){
sl@0	2911	int k, j, last;
sl@0	2912	VdbeOp *pOp;
sl@0	2913	Index *pIdx = pLevel->pIdx;
sl@0	2914	int useIndexOnly = pLevel->flags & WHERE_IDX_ONLY;
sl@0	2915
sl@0	2916	assert( pIdx!=0 );
sl@0	2917	pOp = sqlite3VdbeGetOp(v, pWInfo->iTop);
sl@0	2918	last = sqlite3VdbeCurrentAddr(v);
sl@0	2919	for(k=pWInfo->iTop; k<last; k++, pOp++){
sl@0	2920	if( pOp->p1!=pLevel->iTabCur ) continue;
sl@0	2921	if( pOp->opcode==OP_Column ){
sl@0	2922	for(j=0; j<pIdx->nColumn; j++){
sl@0	2923	if( pOp->p2==pIdx->aiColumn[j] ){
sl@0	2924	pOp->p2 = j;
sl@0	2925	pOp->p1 = pLevel->iIdxCur;
sl@0	2926	break;
sl@0	2927	}
sl@0	2928	}
sl@0	2929	assert(!useIndexOnly \|\| j<pIdx->nColumn);
sl@0	2930	}else if( pOp->opcode==OP_Rowid ){
sl@0	2931	pOp->p1 = pLevel->iIdxCur;
sl@0	2932	pOp->opcode = OP_IdxRowid;
sl@0	2933	}else if( pOp->opcode==OP_NullRow && useIndexOnly ){
sl@0	2934	pOp->opcode = OP_Noop;
sl@0	2935	}
sl@0	2936	}
sl@0	2937	}
sl@0	2938	}
sl@0	2939
sl@0	2940	/* Final cleanup
sl@0	2941	*/
sl@0	2942	whereInfoFree(db, pWInfo);
sl@0	2943	return;
sl@0	2944	}

author	sl
	Tue, 10 Jun 2014 14:32:02 +0200
changeset 1	260cb5ec6c19
permissions	-rw-r--r--