sourcemod-central: extensions/sqlite/sqlite-source/where.c@bee90c8ef6c3 (annotated)

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

author	Asher Baker <asherkin@gmail.com>
	Thu Apr 26 16:58:18 2012 +0100 (2012-04-26)
changeset 3488	bee90c8ef6c3
parent 1952	b7aa2b626807
permissions	-rw-r--r--