Fossil SCM

Merge in the latest SQLite from upstream, in order to test SQLite.

drh 2013-01-17 18:13 trunk

Commit d7019134a500927cbd22f773387f1c7105fed984

Parent 39fa6911fc10523…

2 files changed +199 -93 +1 -1

M src/sqlite3.c

+199 -93

		--- src/sqlite3.c
		+++ src/sqlite3.c
		@@ -673,11 +673,11 @@
673	673	** [sqlite3_libversion_number()], [sqlite3_sourceid()],
674	674	** [sqlite_version()] and [sqlite_source_id()].
675	675	*/
676	676	#define SQLITE_VERSION "3.7.16"
677	677	#define SQLITE_VERSION_NUMBER 3007016
678		-#define SQLITE_SOURCE_ID "2013-01-09 11:31:17 5774f2175ce621dfc4b6b93f7ee13fd66f3ec2b9"
	678	+#define SQLITE_SOURCE_ID "2013-01-17 17:20:49 38852f158ab20bb4d7b264af987ec1538052bec3"
679	679
680	680	/*
681	681	** CAPI3REF: Run-Time Library Version Numbers
682	682	** KEYWORDS: sqlite3_version, sqlite3_sourceid
683	683	**
		@@ -8238,10 +8238,15 @@
8238	8238	** A convenience macro that returns the number of elements in
8239	8239	** an array.
8240	8240	*/
8241	8241	#define ArraySize(X) ((int)(sizeof(X)/sizeof(X[0])))
8242	8242
	8243	+/*
	8244	+** Determine if the argument is a power of two
	8245	+*/
	8246	+#define IsPowerOfTwo(X) (((X)&((X)-1))==0)
	8247	+
8243	8248	/*
8244	8249	** The following value as a destructor means to use sqlite3DbFree().
8245	8250	** The sqlite3DbFree() routine requires two parameters instead of the
8246	8251	** one parameter that destructors normally want. So we have to introduce
8247	8252	** this magic value that the code knows to handle differently. Any
		@@ -10042,10 +10047,11 @@
10042	10047	#define SQLITE_IdxRealAsInt 0x0010 /* Store REAL as INT in indices */
10043	10048	#define SQLITE_DistinctOpt 0x0020 /* DISTINCT using indexes */
10044	10049	#define SQLITE_CoverIdxScan 0x0040 /* Covering index scans */
10045	10050	#define SQLITE_OrderByIdxJoin 0x0080 /* ORDER BY of joins via index */
10046	10051	#define SQLITE_SubqCoroutine 0x0100 /* Evaluate subqueries as coroutines */
	10052	+#define SQLITE_Transitive 0x0200 /* Transitive constraints */
10047	10053	#define SQLITE_AllOpts 0xffff /* All optimizations */
10048	10054
10049	10055	/*
10050	10056	** Macros for testing whether or not optimizations are enabled or disabled.
10051	10057	*/
		@@ -93581,11 +93587,11 @@
93581	93587	sqlite3_rekey(db, zKey, i/2);
93582	93588	}
93583	93589	}else
93584	93590	#endif
93585	93591	#if defined(SQLITE_HAS_CODEC) \|\| defined(SQLITE_ENABLE_CEROD)
93586		- if( sqlite3StrICmp(zLeft, "activate_extensions")==0 ){
	93592	+ if( sqlite3StrICmp(zLeft, "activate_extensions")==0 && zRight ){
93587	93593	#ifdef SQLITE_HAS_CODEC
93588	93594	if( sqlite3StrNICmp(zRight, "see-", 4)==0 ){
93589	93595	sqlite3_activate_see(&zRight[4]);
93590	93596	}
93591	93597	#endif
		@@ -102802,12 +102808,12 @@
102802	102808	Expr pExpr; / Pointer to the subexpression that is this term */
102803	102809	int iParent; /* Disable pWC->a[iParent] when this term disabled */
102804	102810	int leftCursor; /* Cursor number of X in "X <op> <expr>" */
102805	102811	union {
102806	102812	int leftColumn; /* Column number of X in "X <op> <expr>" */
102807		- WhereOrInfo pOrInfo; / Extra information if eOperator==WO_OR */
102808		- WhereAndInfo pAndInfo; / Extra information if eOperator==WO_AND */
	102813	+ WhereOrInfo pOrInfo; / Extra information if (eOperator & WO_OR)!=0 */
	102814	+ WhereAndInfo pAndInfo; / Extra information if (eOperator& WO_AND)!=0 */
102809	102815	} u;
102810	102816	u16 eOperator; /* A WO_xx value describing <op> */
102811	102817	u8 wtFlags; /* TERM_xxx bit flags. See below */
102812	102818	u8 nChild; /* Number of children that must disable us */
102813	102819	WhereClause pWC; / The clause this term is part of */
		@@ -102931,10 +102937,11 @@
102931	102937	#define WO_GE (WO_EQ<<(TK_GE-TK_EQ))
102932	102938	#define WO_MATCH 0x040
102933	102939	#define WO_ISNULL 0x080
102934	102940	#define WO_OR 0x100 /* Two or more OR-connected terms */
102935	102941	#define WO_AND 0x200 /* Two or more AND-connected terms */
	102942	+#define WO_EQUIV 0x400 /* Of the form A==B, both columns */
102936	102943	#define WO_NOOP 0x800 /* This term does not restrict search space */
102937	102944
102938	102945	#define WO_ALL 0xfff /* Mask of all possible WO_* values */
102939	102946	#define WO_SINGLE 0x0ff /* Mask of all non-compound WO_* values */
102940	102947
		@@ -103333,58 +103340,112 @@
103333	103340	/*
103334	103341	** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
103335	103342	** where X is a reference to the iColumn of table iCur and <op> is one of
103336	103343	** the WO_xx operator codes specified by the op parameter.
103337	103344	** Return a pointer to the term. Return 0 if not found.
	103345	+**
	103346	+** The term returned might by Y=<expr> if there is another constraint in
	103347	+** the WHERE clause that specifies that X=Y. Any such constraints will be
	103348	+** identified by the WO_EQUIV bit in the pTerm->eOperator field. The
	103349	+** aEquiv[] array holds X and all its equivalents, with each SQL variable
	103350	+** taking up two slots in aEquiv[]. The first slot is for the cursor number
	103351	+** and the second is for the column number. There are 22 slots in aEquiv[]
	103352	+** so that means we can look for X plus up to 10 other equivalent values.
	103353	+** Hence a search for X will return <expr> if X=A1 and A1=A2 and A2=A3
	103354	+** and ... and A9=A10 and A10=<expr>.
	103355	+**
	103356	+** If there are multiple terms in the WHERE clause of the form "X <op> <expr>"
	103357	+** then try for the one with no dependencies on <expr> - in other words where
	103358	+** <expr> is a constant expression of some kind. Only return entries of
	103359	+** the form "X <op> Y" where Y is a column in another table if no terms of
	103360	+** the form "X <op> <const-expr>" exist. Other than this priority, if there
	103361	+** are two or more terms that match, then the choice of which term to return
	103362	+** is arbitrary.
103338	103363	*/
103339	103364	static WhereTerm *findTerm(
103340	103365	WhereClause pWC, / The WHERE clause to be searched */
103341	103366	int iCur, /* Cursor number of LHS */
103342	103367	int iColumn, /* Column number of LHS */
103343	103368	Bitmask notReady, /* RHS must not overlap with this mask */
103344	103369	u32 op, /* Mask of WO_xx values describing operator */
103345	103370	Index pIdx / Must be compatible with this index, if not NULL */
103346	103371	){
103347		- WhereTerm *pTerm;
103348		- int k;
	103372	+ WhereTerm pTerm; / Term being examined as possible result */
	103373	+ WhereTerm pResult = 0; / The answer to return */
	103374	+ WhereClause pWCOrig = pWC; / Original pWC value */
	103375	+ int j, k; /* Loop counters */
	103376	+ Expr pX; / Pointer to an expression */
	103377	+ Parse pParse; / Parsing context */
	103378	+ int iOrigCol = iColumn; /* Original value of iColumn */
	103379	+ int nEquiv = 2; /* Number of entires in aEquiv[] */
	103380	+ int iEquiv = 2; /* Number of entries of aEquiv[] processed so far */
	103381	+ int aEquiv[22]; /* iCur,iColumn and up to 10 other equivalents */
	103382	+
103349	103383	assert( iCur>=0 );
103350		- op &= WO_ALL;
103351		- for(; pWC; pWC=pWC->pOuter){
103352		- for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
103353		- if( pTerm->leftCursor==iCur
103354		- && (pTerm->prereqRight & notReady)==0
103355		- && pTerm->u.leftColumn==iColumn
103356		- && (pTerm->eOperator & op)!=0
103357		- ){
103358		- if( iColumn>=0 && pIdx && pTerm->eOperator!=WO_ISNULL ){
103359		- Expr *pX = pTerm->pExpr;
103360		- CollSeq *pColl;
103361		- char idxaff;
103362		- int j;
103363		- Parse *pParse = pWC->pParse;
103364		-
103365		- idxaff = pIdx->pTable->aCol[iColumn].affinity;
103366		- if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
103367		-
103368		- /* Figure out the collation sequence required from an index for
103369		- ** it to be useful for optimising expression pX. Store this
103370		- ** value in variable pColl.
103371		- */
103372		- assert(pX->pLeft);
103373		- pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
103374		- if( pColl==0 ) pColl = pParse->db->pDfltColl;
103375		-
103376		- for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
103377		- if( NEVER(j>=pIdx->nColumn) ) return 0;
103378		- }
103379		- if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
103380		- }
103381		- return pTerm;
103382		- }
103383		- }
103384		- }
103385		- return 0;
	103384	+ aEquiv[0] = iCur;
	103385	+ aEquiv[1] = iColumn;
	103386	+ for(;;){
	103387	+ for(pWC=pWCOrig; pWC; pWC=pWC->pOuter){
	103388	+ for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
	103389	+ if( pTerm->leftCursor==iCur
	103390	+ && pTerm->u.leftColumn==iColumn
	103391	+ ){
	103392	+ if( (pTerm->prereqRight & notReady)==0
	103393	+ && (pTerm->eOperator & op & WO_ALL)!=0
	103394	+ ){
	103395	+ if( iOrigCol>=0 && pIdx && (pTerm->eOperator & WO_ISNULL)==0 ){
	103396	+ CollSeq *pColl;
	103397	+ char idxaff;
	103398	+
	103399	+ pX = pTerm->pExpr;
	103400	+ pParse = pWC->pParse;
	103401	+ idxaff = pIdx->pTable->aCol[iOrigCol].affinity;
	103402	+ if( !sqlite3IndexAffinityOk(pX, idxaff) ){
	103403	+ continue;
	103404	+ }
	103405	+
	103406	+ /* Figure out the collation sequence required from an index for
	103407	+ ** it to be useful for optimising expression pX. Store this
	103408	+ ** value in variable pColl.
	103409	+ */
	103410	+ assert(pX->pLeft);
	103411	+ pColl = sqlite3BinaryCompareCollSeq(pParse,pX->pLeft,pX->pRight);
	103412	+ if( pColl==0 ) pColl = pParse->db->pDfltColl;
	103413	+
	103414	+ for(j=0; pIdx->aiColumn[j]!=iOrigCol; j++){
	103415	+ if( NEVER(j>=pIdx->nColumn) ) return 0;
	103416	+ }
	103417	+ if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ){
	103418	+ continue;
	103419	+ }
	103420	+ }
	103421	+ pResult = pTerm;
	103422	+ if( pTerm->prereqRight==0 ) goto findTerm_success;
	103423	+ }
	103424	+ if( (pTerm->eOperator & WO_EQUIV)!=0
	103425	+ && nEquiv<ArraySize(aEquiv)
	103426	+ ){
	103427	+ pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight);
	103428	+ assert( pX->op==TK_COLUMN );
	103429	+ for(j=0; j<nEquiv; j+=2){
	103430	+ if( aEquiv[j]==pX->iTable && aEquiv[j+1]==pX->iColumn ) break;
	103431	+ }
	103432	+ if( j==nEquiv ){
	103433	+ aEquiv[j] = pX->iTable;
	103434	+ aEquiv[j+1] = pX->iColumn;
	103435	+ nEquiv += 2;
	103436	+ }
	103437	+ }
	103438	+ }
	103439	+ }
	103440	+ }
	103441	+ if( iEquiv>=nEquiv ) break;
	103442	+ iCur = aEquiv[iEquiv++];
	103443	+ iColumn = aEquiv[iEquiv++];
	103444	+ }
	103445	+findTerm_success:
	103446	+ return pResult;
103386	103447	}
103387	103448
103388	103449	/* Forward reference */
103389	103450	static void exprAnalyze(SrcList, WhereClause, int);
103390	103451
		@@ -103658,11 +103719,10 @@
103658	103719	indexable = ~(Bitmask)0;
103659	103720	chngToIN = ~(pWC->vmask);
103660	103721	for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){
103661	103722	if( (pOrTerm->eOperator & WO_SINGLE)==0 ){
103662	103723	WhereAndInfo *pAndInfo;
103663		- assert( pOrTerm->eOperator==0 );
103664	103724	assert( (pOrTerm->wtFlags & (TERM_ANDINFO\|TERM_ORINFO))==0 );
103665	103725	chngToIN = 0;
103666	103726	pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo));
103667	103727	if( pAndInfo ){
103668	103728	WhereClause *pAndWC;
		@@ -103697,11 +103757,11 @@
103697	103757	if( pOrTerm->wtFlags & TERM_VIRTUAL ){
103698	103758	WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent];
103699	103759	b \|= getMask(pMaskSet, pOther->leftCursor);
103700	103760	}
103701	103761	indexable &= b;
103702		- if( pOrTerm->eOperator!=WO_EQ ){
	103762	+ if( (pOrTerm->eOperator & WO_EQ)==0 ){
103703	103763	chngToIN = 0;
103704	103764	}else{
103705	103765	chngToIN &= b;
103706	103766	}
103707	103767	}
		@@ -103748,11 +103808,11 @@
103748	103808	** and column is found but leave okToChngToIN false if not found.
103749	103809	*/
103750	103810	for(j=0; j<2 && !okToChngToIN; j++){
103751	103811	pOrTerm = pOrWc->a;
103752	103812	for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){
103753		- assert( pOrTerm->eOperator==WO_EQ );
	103813	+ assert( pOrTerm->eOperator & WO_EQ );
103754	103814	pOrTerm->wtFlags &= ~TERM_OR_OK;
103755	103815	if( pOrTerm->leftCursor==iCursor ){
103756	103816	/* This is the 2-bit case and we are on the second iteration and
103757	103817	** current term is from the first iteration. So skip this term. */
103758	103818	assert( j==1 );
		@@ -103774,21 +103834,21 @@
103774	103834	}
103775	103835	if( i<0 ){
103776	103836	/* No candidate table+column was found. This can only occur
103777	103837	** on the second iteration */
103778	103838	assert( j==1 );
103779		- assert( (chngToIN&(chngToIN-1))==0 );
	103839	+ assert( IsPowerOfTwo(chngToIN) );
103780	103840	assert( chngToIN==getMask(pMaskSet, iCursor) );
103781	103841	break;
103782	103842	}
103783	103843	testcase( j==1 );
103784	103844
103785	103845	/* We have found a candidate table and column. Check to see if that
103786	103846	** table and column is common to every term in the OR clause */
103787	103847	okToChngToIN = 1;
103788	103848	for(; i>=0 && okToChngToIN; i--, pOrTerm++){
103789		- assert( pOrTerm->eOperator==WO_EQ );
	103849	+ assert( pOrTerm->eOperator & WO_EQ );
103790	103850	if( pOrTerm->leftCursor!=iCursor ){
103791	103851	pOrTerm->wtFlags &= ~TERM_OR_OK;
103792	103852	}else if( pOrTerm->u.leftColumn!=iColumn ){
103793	103853	okToChngToIN = 0;
103794	103854	}else{
		@@ -103820,11 +103880,11 @@
103820	103880	Expr pLeft = 0; / The LHS of the IN operator */
103821	103881	Expr pNew; / The complete IN operator */
103822	103882
103823	103883	for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){
103824	103884	if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue;
103825		- assert( pOrTerm->eOperator==WO_EQ );
	103885	+ assert( pOrTerm->eOperator & WO_EQ );
103826	103886	assert( pOrTerm->leftCursor==iCursor );
103827	103887	assert( pOrTerm->u.leftColumn==iColumn );
103828	103888	pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0);
103829	103889	pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup);
103830	103890	pLeft = pOrTerm->pExpr->pLeft;
		@@ -103849,11 +103909,10 @@
103849	103909	pTerm->eOperator = WO_NOOP; /* case 1 trumps case 2 */
103850	103910	}
103851	103911	}
103852	103912	}
103853	103913	#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
103854		-
103855	103914
103856	103915	/*
103857	103916	** The input to this routine is an WhereTerm structure with only the
103858	103917	** "pExpr" field filled in. The job of this routine is to analyze the
103859	103918	** subexpression and populate all the other fields of the WhereTerm
		@@ -103919,21 +103978,23 @@
103919	103978	}
103920	103979	pTerm->prereqAll = prereqAll;
103921	103980	pTerm->leftCursor = -1;
103922	103981	pTerm->iParent = -1;
103923	103982	pTerm->eOperator = 0;
103924		- if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
	103983	+ if( allowedOp(op) ){
103925	103984	Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft);
103926	103985	Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight);
	103986	+ u16 opMask = (pTerm->prereqRight & prereqLeft)==0 ? WO_ALL : WO_EQUIV;
103927	103987	if( pLeft->op==TK_COLUMN ){
103928	103988	pTerm->leftCursor = pLeft->iTable;
103929	103989	pTerm->u.leftColumn = pLeft->iColumn;
103930		- pTerm->eOperator = operatorMask(op);
	103990	+ pTerm->eOperator = operatorMask(op) & opMask;
103931	103991	}
103932	103992	if( pRight && pRight->op==TK_COLUMN ){
103933	103993	WhereTerm *pNew;
103934	103994	Expr *pDup;
	103995	+ u16 eExtraOp = 0; /* Extra bits for pNew->eOperator */
103935	103996	if( pTerm->leftCursor>=0 ){
103936	103997	int idxNew;
103937	103998	pDup = sqlite3ExprDup(db, pExpr, 0);
103938	103999	if( db->mallocFailed ){
103939	104000	sqlite3ExprDelete(db, pDup);
		@@ -103944,10 +104005,17 @@
103944	104005	pNew = &pWC->a[idxNew];
103945	104006	pNew->iParent = idxTerm;
103946	104007	pTerm = &pWC->a[idxTerm];
103947	104008	pTerm->nChild = 1;
103948	104009	pTerm->wtFlags \|= TERM_COPIED;
	104010	+ if( pExpr->op==TK_EQ
	104011	+ && !ExprHasProperty(pExpr, EP_FromJoin)
	104012	+ && OptimizationEnabled(db, SQLITE_Transitive)
	104013	+ ){
	104014	+ pTerm->eOperator \|= WO_EQUIV;
	104015	+ eExtraOp = WO_EQUIV;
	104016	+ }
103949	104017	}else{
103950	104018	pDup = pExpr;
103951	104019	pNew = pTerm;
103952	104020	}
103953	104021	exprCommute(pParse, pDup);
		@@ -103955,11 +104023,11 @@
103955	104023	pNew->leftCursor = pLeft->iTable;
103956	104024	pNew->u.leftColumn = pLeft->iColumn;
103957	104025	testcase( (prereqLeft \| extraRight) != prereqLeft );
103958	104026	pNew->prereqRight = prereqLeft \| extraRight;
103959	104027	pNew->prereqAll = prereqAll;
103960		- pNew->eOperator = operatorMask(pDup->op);
	104028	+ pNew->eOperator = (operatorMask(pDup->op) + eExtraOp) & opMask;
103961	104029	}
103962	104030	}
103963	104031
103964	104032	#ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
103965	104033	/* If a term is the BETWEEN operator, create two new virtual terms
		@@ -104414,11 +104482,11 @@
104414	104482	return;
104415	104483	}
104416	104484
104417	104485	/* Search the WHERE clause terms for a usable WO_OR term. */
104418	104486	for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
104419		- if( pTerm->eOperator==WO_OR
	104487	+ if( (pTerm->eOperator & WO_OR)!=0
104420	104488	&& ((pTerm->prereqAll & ~maskSrc) & p->notReady)==0
104421	104489	&& (pTerm->u.pOrInfo->indexable & maskSrc)!=0
104422	104490	){
104423	104491	WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
104424	104492	WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
		@@ -104435,11 +104503,11 @@
104435	104503	sBOI.ppIdxInfo = 0;
104436	104504	for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
104437	104505	WHERETRACE(("... Multi-index OR testing for term %d of %d....\n",
104438	104506	(pOrTerm - pOrWC->a), (pTerm - pWC->a)
104439	104507	));
104440		- if( pOrTerm->eOperator==WO_AND ){
	104508	+ if( (pOrTerm->eOperator& WO_AND)!=0 ){
104441	104509	sBOI.pWC = &pOrTerm->u.pAndInfo->wc;
104442	104510	bestIndex(&sBOI);
104443	104511	}else if( pOrTerm->leftCursor==iCur ){
104444	104512	WhereClause tempWC;
104445	104513	tempWC.pParse = pWC->pParse;
		@@ -104496,11 +104564,11 @@
104496	104564	struct SrcList_item pSrc, / Table we are trying to access */
104497	104565	Bitmask notReady /* Tables in outer loops of the join */
104498	104566	){
104499	104567	char aff;
104500	104568	if( pTerm->leftCursor!=pSrc->iCursor ) return 0;
104501		- if( pTerm->eOperator!=WO_EQ ) return 0;
	104569	+ if( (pTerm->eOperator & WO_EQ)==0 ) return 0;
104502	104570	if( (pTerm->prereqRight & notReady)!=0 ) return 0;
104503	104571	aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;
104504	104572	if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0;
104505	104573	return 1;
104506	104574	}
		@@ -104758,13 +104826,13 @@
104758	104826
104759	104827	/* Count the number of possible WHERE clause constraints referring
104760	104828	** to this virtual table */
104761	104829	for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
104762	104830	if( pTerm->leftCursor != pSrc->iCursor ) continue;
104763		- assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
104764		- testcase( pTerm->eOperator==WO_IN );
104765		- testcase( pTerm->eOperator==WO_ISNULL );
	104831	+ assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
	104832	+ testcase( pTerm->eOperator & WO_IN );
	104833	+ testcase( pTerm->eOperator & WO_ISNULL );
104766	104834	if( pTerm->eOperator & (WO_ISNULL) ) continue;
104767	104835	if( pTerm->wtFlags & TERM_VNULL ) continue;
104768	104836	nTerm++;
104769	104837	}
104770	104838
		@@ -104811,18 +104879,18 @@
104811	104879	pUsage;
104812	104880
104813	104881	for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
104814	104882	u8 op;
104815	104883	if( pTerm->leftCursor != pSrc->iCursor ) continue;
104816		- assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
104817		- testcase( pTerm->eOperator==WO_IN );
104818		- testcase( pTerm->eOperator==WO_ISNULL );
	104884	+ assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
	104885	+ testcase( pTerm->eOperator & WO_IN );
	104886	+ testcase( pTerm->eOperator & WO_ISNULL );
104819	104887	if( pTerm->eOperator & (WO_ISNULL) ) continue;
104820	104888	if( pTerm->wtFlags & TERM_VNULL ) continue;
104821	104889	pIdxCons[j].iColumn = pTerm->u.leftColumn;
104822	104890	pIdxCons[j].iTermOffset = i;
104823		- op = (u8)pTerm->eOperator;
	104891	+ op = (u8)pTerm->eOperator & WO_ALL;
104824	104892	if( op==WO_IN ) op = WO_EQ;
104825	104893	pIdxCons[j].op = op;
104826	104894	/* The direct assignment in the previous line is possible only because
104827	104895	** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The
104828	104896	** following asserts verify this fact. */
		@@ -104988,11 +105056,11 @@
104988	105056	pUsage = pIdxInfo->aConstraintUsage;
104989	105057	for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
104990	105058	j = pIdxCons->iTermOffset;
104991	105059	pTerm = &pWC->a[j];
104992	105060	if( (pTerm->prereqRight&p->notReady)==0
104993		- && (bAllowIN \|\| pTerm->eOperator!=WO_IN)
	105061	+ && (bAllowIN \|\| (pTerm->eOperator & WO_IN)==0)
104994	105062	){
104995	105063	pIdxCons->usable = 1;
104996	105064	}else{
104997	105065	pIdxCons->usable = 0;
104998	105066	}
		@@ -105020,11 +105088,11 @@
105020	105088	for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
105021	105089	if( pUsage[i].argvIndex>0 ){
105022	105090	j = pIdxCons->iTermOffset;
105023	105091	pTerm = &pWC->a[j];
105024	105092	p->cost.used \|= pTerm->prereqRight;
105025		- if( pTerm->eOperator==WO_IN && pUsage[i].omit==0 ){
	105093	+ if( (pTerm->eOperator & WO_IN)!=0 && pUsage[i].omit==0 ){
105026	105094	/* Do not attempt to use an IN constraint if the virtual table
105027	105095	** says that the equivalent EQ constraint cannot be safely omitted.
105028	105096	** If we do attempt to use such a constraint, some rows might be
105029	105097	** repeated in the output. */
105030	105098	break;
		@@ -105326,28 +105394,28 @@
105326	105394	u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;
105327	105395
105328	105396	if( pLower ){
105329	105397	Expr *pExpr = pLower->pExpr->pRight;
105330	105398	rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
105331		- assert( pLower->eOperator==WO_GT \|\| pLower->eOperator==WO_GE );
	105399	+ assert( (pLower->eOperator & (WO_GT\|WO_GE))!=0 );
105332	105400	if( rc==SQLITE_OK
105333	105401	&& whereKeyStats(pParse, p, pRangeVal, 0, a)==SQLITE_OK
105334	105402	){
105335	105403	iLower = a[0];
105336		- if( pLower->eOperator==WO_GT ) iLower += a[1];
	105404	+ if( (pLower->eOperator & WO_GT)!=0 ) iLower += a[1];
105337	105405	}
105338	105406	sqlite3ValueFree(pRangeVal);
105339	105407	}
105340	105408	if( rc==SQLITE_OK && pUpper ){
105341	105409	Expr *pExpr = pUpper->pExpr->pRight;
105342	105410	rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
105343		- assert( pUpper->eOperator==WO_LT \|\| pUpper->eOperator==WO_LE );
	105411	+ assert( (pUpper->eOperator & (WO_LT\|WO_LE))!=0 );
105344	105412	if( rc==SQLITE_OK
105345	105413	&& whereKeyStats(pParse, p, pRangeVal, 1, a)==SQLITE_OK
105346	105414	){
105347	105415	iUpper = a[0];
105348		- if( pUpper->eOperator==WO_LE ) iUpper += a[1];
	105416	+ if( (pUpper->eOperator & WO_LE)!=0 ) iUpper += a[1];
105349	105417	}
105350	105418	sqlite3ValueFree(pRangeVal);
105351	105419	}
105352	105420	if( rc==SQLITE_OK ){
105353	105421	if( iUpper<=iLower ){
		@@ -105651,16 +105719,16 @@
105651	105719	** if there are any X= or X IS NULL constraints in the WHERE clause. */
105652	105720	pConstraint = findTerm(p->pWC, base, iColumn, p->notReady,
105653	105721	WO_EQ\|WO_ISNULL\|WO_IN, pIdx);
105654	105722	if( pConstraint==0 ){
105655	105723	isEq = 0;
105656		- }else if( pConstraint->eOperator==WO_IN ){
	105724	+ }else if( (pConstraint->eOperator & WO_IN)!=0 ){
105657	105725	/* Constraints of the form: "X IN ..." cannot be used with an ORDER BY
105658	105726	** because we do not know in what order the values on the RHS of the IN
105659	105727	** operator will occur. */
105660	105728	break;
105661		- }else if( pConstraint->eOperator==WO_ISNULL ){
	105729	+ }else if( (pConstraint->eOperator & WO_ISNULL)!=0 ){
105662	105730	uniqueNotNull = 0;
105663	105731	isEq = 1; /* "X IS NULL" means X has only a single value */
105664	105732	}else if( pConstraint->prereqRight==0 ){
105665	105733	isEq = 1; /* Constraint "X=constant" means X has only a single value */
105666	105734	}else{
		@@ -106069,16 +106137,17 @@
106069	106137	*/
106070	106138	if( pc.plan.nRow>(double)1 && pc.plan.nEq==1
106071	106139	&& pFirstTerm!=0 && aiRowEst[1]>1 ){
106072	106140	assert( (pFirstTerm->eOperator & (WO_EQ\|WO_ISNULL\|WO_IN))!=0 );
106073	106141	if( pFirstTerm->eOperator & (WO_EQ\|WO_ISNULL) ){
106074		- testcase( pFirstTerm->eOperator==WO_EQ );
106075		- testcase( pFirstTerm->eOperator==WO_ISNULL );
	106142	+ testcase( pFirstTerm->eOperator & WO_EQ );
	106143	+ testcase( pFirstTerm->eOperator & WO_EQUIV );
	106144	+ testcase( pFirstTerm->eOperator & WO_ISNULL );
106076	106145	whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight,
106077	106146	&pc.plan.nRow);
106078	106147	}else if( bInEst==0 ){
106079		- assert( pFirstTerm->eOperator==WO_IN );
	106148	+ assert( pFirstTerm->eOperator & WO_IN );
106080	106149	whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList,
106081	106150	&pc.plan.nRow);
106082	106151	}
106083	106152	}
106084	106153	#endif /* SQLITE_ENABLE_STAT3 */
		@@ -106221,11 +106290,11 @@
106221	106290	** more selective intentionally because of the subjective
106222	106291	** observation that indexed range constraints really are more
106223	106292	** selective in practice, on average. */
106224	106293	pc.plan.nRow /= 3;
106225	106294	}
106226		- }else if( pTerm->eOperator!=WO_NOOP ){
	106295	+ }else if( (pTerm->eOperator & WO_NOOP)==0 ){
106227	106296	/* Any other expression lowers the output row count by half */
106228	106297	pc.plan.nRow /= 2;
106229	106298	}
106230	106299	}
106231	106300	if( pc.plan.nRow<2 ) pc.plan.nRow = 2;
		@@ -106273,12 +106342,13 @@
106273	106342	assert( pSrc->pIndex==0
106274	106343	\|\| p->cost.plan.u.pIdx==0
106275	106344	\|\| p->cost.plan.u.pIdx==pSrc->pIndex
106276	106345	);
106277	106346
106278		- WHERETRACE((" best index is: %s\n",
106279		- p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk"));
	106347	+ WHERETRACE((" best index is %s cost=%.1f\n",
	106348	+ p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk",
	106349	+ p->cost.rCost));
106280	106350
106281	106351	bestOrClauseIndex(p);
106282	106352	bestAutomaticIndex(p);
106283	106353	p->cost.plan.wsFlags \|= eqTermMask;
106284	106354	}
		@@ -106856,11 +106926,10 @@
106856	106926	*/
106857	106927	iReleaseReg = sqlite3GetTempReg(pParse);
106858	106928	pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ\|WO_IN, 0);
106859	106929	assert( pTerm!=0 );
106860	106930	assert( pTerm->pExpr!=0 );
106861		- assert( pTerm->leftCursor==iCur );
106862	106931	assert( omitTable==0 );
106863	106932	testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
106864	106933	iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg);
106865	106934	addrNxt = pLevel->addrNxt;
106866	106935	sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
		@@ -107247,11 +107316,11 @@
107247	107316	int ii; /* Loop counter */
107248	107317	Expr pAndExpr = 0; / An ".. AND (...)" expression */
107249	107318
107250	107319	pTerm = pLevel->plan.u.pTerm;
107251	107320	assert( pTerm!=0 );
107252		- assert( pTerm->eOperator==WO_OR );
	107321	+ assert( pTerm->eOperator & WO_OR );
107253	107322	assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
107254	107323	pOrWc = &pTerm->u.pOrInfo->wc;
107255	107324	pLevel->op = OP_Return;
107256	107325	pLevel->p1 = regReturn;
107257	107326
		@@ -107320,11 +107389,11 @@
107320	107389	}
107321	107390	}
107322	107391
107323	107392	for(ii=0; ii<pOrWc->nTerm; ii++){
107324	107393	WhereTerm *pOrTerm = &pOrWc->a[ii];
107325		- if( pOrTerm->leftCursor==iCur \|\| pOrTerm->eOperator==WO_AND ){
	107394	+ if( pOrTerm->leftCursor==iCur \|\| (pOrTerm->eOperator & WO_AND)!=0 ){
107326	107395	WhereInfo pSubWInfo; / Info for single OR-term scan */
107327	107396	Expr *pOrExpr = pOrTerm->pExpr;
107328	107397	if( pAndExpr ){
107329	107398	pAndExpr->pLeft = pOrExpr;
107330	107399	pOrExpr = pAndExpr;
		@@ -107775,10 +107844,11 @@
107775	107844	Index pIdx; / Index for FROM table at pTabItem */
107776	107845	int j; /* For looping over FROM tables */
107777	107846	int bestJ = -1; /* The value of j */
107778	107847	Bitmask m; /* Bitmask value for j or bestJ */
107779	107848	int isOptimal; /* Iterator for optimal/non-optimal search */
	107849	+ int ckOptimal; /* Do the optimal scan check */
107780	107850	int nUnconstrained; /* Number tables without INDEXED BY */
107781	107851	Bitmask notIndexed; /* Mask of tables that cannot use an index */
107782	107852
107783	107853	memset(&bestPlan, 0, sizeof(bestPlan));
107784	107854	bestPlan.rCost = SQLITE_BIG_DBL;
		@@ -107809,14 +107879,12 @@
107809	107879	**
107810	107880	** The second loop iteration is only performed if no optimal scan
107811	107881	** strategies were found by the first iteration. This second iteration
107812	107882	** is used to search for the lowest cost scan overall.
107813	107883	**
107814		- ** Previous versions of SQLite performed only the second iteration -
107815		- ** the next outermost loop was always that with the lowest overall
107816		- ** cost. However, this meant that SQLite could select the wrong plan
107817		- ** for scripts such as the following:
	107884	+ ** Without the optimal scan step (the first iteration) a suboptimal
	107885	+ ** plan might be chosen for queries like this:
107818	107886	**
107819	107887	** CREATE TABLE t1(a, b);
107820	107888	** CREATE TABLE t2(c, d);
107821	107889	** SELECT * FROM t2, t1 WHERE t2.rowid = t1.a;
107822	107890	**
		@@ -107827,20 +107895,44 @@
107827	107895	** algorithm may choose to use t2 for the outer loop, which is a much
107828	107896	** costlier approach.
107829	107897	*/
107830	107898	nUnconstrained = 0;
107831	107899	notIndexed = 0;
107832		- for(isOptimal=(iFrom<nTabList-1); isOptimal>=0 && bestJ<0; isOptimal--){
	107900	+
	107901	+ /* The optimal scan check only occurs if there are two or more tables
	107902	+ ** available to be reordered */
	107903	+ if( iFrom==nTabList-1 ){
	107904	+ ckOptimal = 0; /* Common case of just one table in the FROM clause */
	107905	+ }else{
	107906	+ ckOptimal = -1;
107833	107907	for(j=iFrom, sWBI.pSrc=&pTabList->a[j]; j<nTabList; j++, sWBI.pSrc++){
107834		- int doNotReorder; /* True if this table should not be reordered */
107835		-
107836		- doNotReorder = (sWBI.pSrc->jointype & (JT_LEFT\|JT_CROSS))!=0;
107837		- if( j!=iFrom && doNotReorder ) break;
107838	107908	m = getMask(pMaskSet, sWBI.pSrc->iCursor);
107839	107909	if( (m & sWBI.notValid)==0 ){
107840	107910	if( j==iFrom ) iFrom++;
107841	107911	continue;
	107912	+ }
	107913	+ if( j>iFrom && (sWBI.pSrc->jointype & (JT_LEFT\|JT_CROSS))!=0 ) break;
	107914	+ if( ++ckOptimal ) break;
	107915	+ if( (sWBI.pSrc->jointype & JT_LEFT)!=0 ) break;
	107916	+ }
	107917	+ }
	107918	+ assert( ckOptimal==0 \|\| ckOptimal==1 );
	107919	+
	107920	+ for(isOptimal=ckOptimal; isOptimal>=0 && bestJ<0; isOptimal--){
	107921	+ for(j=iFrom, sWBI.pSrc=&pTabList->a[j]; j<nTabList; j++, sWBI.pSrc++){
	107922	+ if( j>iFrom && (sWBI.pSrc->jointype & (JT_LEFT\|JT_CROSS))!=0 ){
	107923	+ /* This break and one like it in the ckOptimal computation loop
	107924	+ ** above prevent table reordering across LEFT and CROSS JOINs.
	107925	+ ** The LEFT JOIN case is necessary for correctness. The prohibition
	107926	+ ** against reordering across a CROSS JOIN is an SQLite feature that
	107927	+ ** allows the developer to control table reordering */
	107928	+ break;
	107929	+ }
	107930	+ m = getMask(pMaskSet, sWBI.pSrc->iCursor);
	107931	+ if( (m & sWBI.notValid)==0 ){
	107932	+ assert( j>iFrom );
	107933	+ continue;
107842	107934	}
107843	107935	sWBI.notReady = (isOptimal ? m : sWBI.notValid);
107844	107936	if( sWBI.pSrc->pIndex==0 ) nUnconstrained++;
107845	107937
107846	107938	WHERETRACE((" === trying table %d (%s) with isOptimal=%d ===\n",
		@@ -107866,12 +107958,12 @@
107866	107958	if( isOptimal && (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){
107867	107959	notIndexed \|= m;
107868	107960	}
107869	107961	if( isOptimal ){
107870	107962	pWInfo->a[j].rOptCost = sWBI.cost.rCost;
107871		- }else if( iFrom<nTabList-1 ){
107872		- /* If two or more tables have nearly the same outer loop cost,
	107963	+ }else if( ckOptimal ){
	107964	+ /* If two or more tables have nearly the same outer loop cost, but
107873	107965	** very different inner loop (optimal) cost, we want to choose
107874	107966	** for the outer loop that table which benefits the least from
107875	107967	** being in the inner loop. The following code scales the
107876	107968	** outer loop cost estimate to accomplish that. */
107877	107969	WHERETRACE((" scaling cost from %.1f to %.1f\n",
		@@ -107912,15 +108004,23 @@
107912	108004	sWBI.cost.rCost, sWBI.cost.plan.nRow,
107913	108005	sWBI.cost.plan.nOBSat, sWBI.cost.plan.wsFlags));
107914	108006	bestPlan = sWBI.cost;
107915	108007	bestJ = j;
107916	108008	}
107917		- if( doNotReorder ) break;
	108009	+
	108010	+ /* In a join like "w JOIN x LEFT JOIN y JOIN z" make sure that
	108011	+ ** table y (and not table z) is always the next inner loop inside
	108012	+ ** of table x. */
	108013	+ if( (sWBI.pSrc->jointype & JT_LEFT)!=0 ) break;
107918	108014	}
107919	108015	}
107920	108016	assert( bestJ>=0 );
107921	108017	assert( sWBI.notValid & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
	108018	+ assert( bestJ==iFrom \|\| (pTabList->a[iFrom].jointype & JT_LEFT)==0 );
	108019	+ testcase( bestJ>iFrom && (pTabList->a[iFrom].jointype & JT_CROSS)!=0 );
	108020	+ testcase( bestJ>iFrom && bestJ<nTabList-1
	108021	+ && (pTabList->a[bestJ+1].jointype & JT_LEFT)!=0 );
107922	108022	WHERETRACE(("*** Optimizer selects table %d (%s) for loop %d with:\n"
107923	108023	" cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=0x%08x\n",
107924	108024	bestJ, pTabList->a[bestJ].pTab->zName,
107925	108025	pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow,
107926	108026	bestPlan.plan.nOBSat, bestPlan.plan.wsFlags));
		@@ -136646,11 +136746,12 @@
136646	136746	** would fit in a single node, use a smaller node-size.
136647	136747	*/
136648	136748	static int getNodeSize(
136649	136749	sqlite3 db, / Database handle */
136650	136750	Rtree pRtree, / Rtree handle */
136651		- int isCreate /* True for xCreate, false for xConnect */
	136751	+ int isCreate, /* True for xCreate, false for xConnect */
	136752	+ char *pzErr / OUT: Error message, if any */
136652	136753	){
136653	136754	int rc;
136654	136755	char *zSql;
136655	136756	if( isCreate ){
136656	136757	int iPageSize = 0;
		@@ -136659,17 +136760,22 @@
136659	136760	if( rc==SQLITE_OK ){
136660	136761	pRtree->iNodeSize = iPageSize-64;
136661	136762	if( (4+pRtree->nBytesPerCell*RTREE_MAXCELLS)<pRtree->iNodeSize ){
136662	136763	pRtree->iNodeSize = 4+pRtree->nBytesPerCell*RTREE_MAXCELLS;
136663	136764	}
	136765	+ }else{
	136766	+ *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
136664	136767	}
136665	136768	}else{
136666	136769	zSql = sqlite3_mprintf(
136667	136770	"SELECT length(data) FROM '%q'.'%q_node' WHERE nodeno = 1",
136668	136771	pRtree->zDb, pRtree->zName
136669	136772	);
136670	136773	rc = getIntFromStmt(db, zSql, &pRtree->iNodeSize);
	136774	+ if( rc!=SQLITE_OK ){
	136775	+ *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
	136776	+ }
136671	136777	}
136672	136778
136673	136779	sqlite3_free(zSql);
136674	136780	return rc;
136675	136781	}
		@@ -136729,11 +136835,11 @@
136729	136835	pRtree->eCoordType = eCoordType;
136730	136836	memcpy(pRtree->zDb, argv[1], nDb);
136731	136837	memcpy(pRtree->zName, argv[2], nName);
136732	136838
136733	136839	/* Figure out the node size to use. */
136734		- rc = getNodeSize(db, pRtree, isCreate);
	136840	+ rc = getNodeSize(db, pRtree, isCreate, pzErr);
136735	136841
136736	136842	/* Create/Connect to the underlying relational database schema. If
136737	136843	** that is successful, call sqlite3_declare_vtab() to configure
136738	136844	** the r-tree table schema.
136739	136845	*/
136740	136846

	--- src/sqlite3.c
	+++ src/sqlite3.c
	@@ -673,11 +673,11 @@
673	** [sqlite3_libversion_number()], [sqlite3_sourceid()],
674	** [sqlite_version()] and [sqlite_source_id()].
675	*/
676	#define SQLITE_VERSION "3.7.16"
677	#define SQLITE_VERSION_NUMBER 3007016
678	#define SQLITE_SOURCE_ID "2013-01-09 11:31:17 5774f2175ce621dfc4b6b93f7ee13fd66f3ec2b9"
679
680	/*
681	** CAPI3REF: Run-Time Library Version Numbers
682	** KEYWORDS: sqlite3_version, sqlite3_sourceid
683	**
	@@ -8238,10 +8238,15 @@
8238	** A convenience macro that returns the number of elements in
8239	** an array.
8240	*/
8241	#define ArraySize(X) ((int)(sizeof(X)/sizeof(X[0])))
8242





8243	/*
8244	** The following value as a destructor means to use sqlite3DbFree().
8245	** The sqlite3DbFree() routine requires two parameters instead of the
8246	** one parameter that destructors normally want. So we have to introduce
8247	** this magic value that the code knows to handle differently. Any
	@@ -10042,10 +10047,11 @@
10042	#define SQLITE_IdxRealAsInt 0x0010 /* Store REAL as INT in indices */
10043	#define SQLITE_DistinctOpt 0x0020 /* DISTINCT using indexes */
10044	#define SQLITE_CoverIdxScan 0x0040 /* Covering index scans */
10045	#define SQLITE_OrderByIdxJoin 0x0080 /* ORDER BY of joins via index */
10046	#define SQLITE_SubqCoroutine 0x0100 /* Evaluate subqueries as coroutines */

10047	#define SQLITE_AllOpts 0xffff /* All optimizations */
10048
10049	/*
10050	** Macros for testing whether or not optimizations are enabled or disabled.
10051	*/
	@@ -93581,11 +93587,11 @@
93581	sqlite3_rekey(db, zKey, i/2);
93582	}
93583	}else
93584	#endif
93585	#if defined(SQLITE_HAS_CODEC) \|\| defined(SQLITE_ENABLE_CEROD)
93586	if( sqlite3StrICmp(zLeft, "activate_extensions")==0 ){
93587	#ifdef SQLITE_HAS_CODEC
93588	if( sqlite3StrNICmp(zRight, "see-", 4)==0 ){
93589	sqlite3_activate_see(&zRight[4]);
93590	}
93591	#endif
	@@ -102802,12 +102808,12 @@
102802	Expr pExpr; / Pointer to the subexpression that is this term */
102803	int iParent; /* Disable pWC->a[iParent] when this term disabled */
102804	int leftCursor; /* Cursor number of X in "X <op> <expr>" */
102805	union {
102806	int leftColumn; /* Column number of X in "X <op> <expr>" */
102807	WhereOrInfo pOrInfo; / Extra information if eOperator==WO_OR */
102808	WhereAndInfo pAndInfo; / Extra information if eOperator==WO_AND */
102809	} u;
102810	u16 eOperator; /* A WO_xx value describing <op> */
102811	u8 wtFlags; /* TERM_xxx bit flags. See below */
102812	u8 nChild; /* Number of children that must disable us */
102813	WhereClause pWC; / The clause this term is part of */
	@@ -102931,10 +102937,11 @@
102931	#define WO_GE (WO_EQ<<(TK_GE-TK_EQ))
102932	#define WO_MATCH 0x040
102933	#define WO_ISNULL 0x080
102934	#define WO_OR 0x100 /* Two or more OR-connected terms */
102935	#define WO_AND 0x200 /* Two or more AND-connected terms */

102936	#define WO_NOOP 0x800 /* This term does not restrict search space */
102937
102938	#define WO_ALL 0xfff /* Mask of all possible WO_* values */
102939	#define WO_SINGLE 0x0ff /* Mask of all non-compound WO_* values */
102940
	@@ -103333,58 +103340,112 @@
103333	/*
103334	** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
103335	** where X is a reference to the iColumn of table iCur and <op> is one of
103336	** the WO_xx operator codes specified by the op parameter.
103337	** Return a pointer to the term. Return 0 if not found.


















103338	*/
103339	static WhereTerm *findTerm(
103340	WhereClause pWC, / The WHERE clause to be searched */
103341	int iCur, /* Cursor number of LHS */
103342	int iColumn, /* Column number of LHS */
103343	Bitmask notReady, /* RHS must not overlap with this mask */
103344	u32 op, /* Mask of WO_xx values describing operator */
103345	Index pIdx / Must be compatible with this index, if not NULL */
103346	){
103347	WhereTerm *pTerm;
103348	int k;









103349	assert( iCur>=0 );
103350	op &= WO_ALL;
103351	for(; pWC; pWC=pWC->pOuter){
103352	for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
103353	if( pTerm->leftCursor==iCur
103354	&& (pTerm->prereqRight & notReady)==0
103355	&& pTerm->u.leftColumn==iColumn
103356	&& (pTerm->eOperator & op)!=0
103357	){
103358	if( iColumn>=0 && pIdx && pTerm->eOperator!=WO_ISNULL ){
103359	Expr *pX = pTerm->pExpr;
103360	CollSeq *pColl;
103361	char idxaff;
103362	int j;
103363	Parse *pParse = pWC->pParse;
103364
103365	idxaff = pIdx->pTable->aCol[iColumn].affinity;
103366	if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
103367
103368	/* Figure out the collation sequence required from an index for
103369	** it to be useful for optimising expression pX. Store this
103370	** value in variable pColl.
103371	*/
103372	assert(pX->pLeft);
103373	pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
103374	if( pColl==0 ) pColl = pParse->db->pDfltColl;
103375
103376	for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
103377	if( NEVER(j>=pIdx->nColumn) ) return 0;
103378	}
103379	if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
103380	}
103381	return pTerm;
103382	}
103383	}
103384	}
103385	return 0;



























103386	}
103387
103388	/* Forward reference */
103389	static void exprAnalyze(SrcList, WhereClause, int);
103390
	@@ -103658,11 +103719,10 @@
103658	indexable = ~(Bitmask)0;
103659	chngToIN = ~(pWC->vmask);
103660	for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){
103661	if( (pOrTerm->eOperator & WO_SINGLE)==0 ){
103662	WhereAndInfo *pAndInfo;
103663	assert( pOrTerm->eOperator==0 );
103664	assert( (pOrTerm->wtFlags & (TERM_ANDINFO\|TERM_ORINFO))==0 );
103665	chngToIN = 0;
103666	pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo));
103667	if( pAndInfo ){
103668	WhereClause *pAndWC;
	@@ -103697,11 +103757,11 @@
103697	if( pOrTerm->wtFlags & TERM_VIRTUAL ){
103698	WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent];
103699	b \|= getMask(pMaskSet, pOther->leftCursor);
103700	}
103701	indexable &= b;
103702	if( pOrTerm->eOperator!=WO_EQ ){
103703	chngToIN = 0;
103704	}else{
103705	chngToIN &= b;
103706	}
103707	}
	@@ -103748,11 +103808,11 @@
103748	** and column is found but leave okToChngToIN false if not found.
103749	*/
103750	for(j=0; j<2 && !okToChngToIN; j++){
103751	pOrTerm = pOrWc->a;
103752	for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){
103753	assert( pOrTerm->eOperator==WO_EQ );
103754	pOrTerm->wtFlags &= ~TERM_OR_OK;
103755	if( pOrTerm->leftCursor==iCursor ){
103756	/* This is the 2-bit case and we are on the second iteration and
103757	** current term is from the first iteration. So skip this term. */
103758	assert( j==1 );
	@@ -103774,21 +103834,21 @@
103774	}
103775	if( i<0 ){
103776	/* No candidate table+column was found. This can only occur
103777	** on the second iteration */
103778	assert( j==1 );
103779	assert( (chngToIN&(chngToIN-1))==0 );
103780	assert( chngToIN==getMask(pMaskSet, iCursor) );
103781	break;
103782	}
103783	testcase( j==1 );
103784
103785	/* We have found a candidate table and column. Check to see if that
103786	** table and column is common to every term in the OR clause */
103787	okToChngToIN = 1;
103788	for(; i>=0 && okToChngToIN; i--, pOrTerm++){
103789	assert( pOrTerm->eOperator==WO_EQ );
103790	if( pOrTerm->leftCursor!=iCursor ){
103791	pOrTerm->wtFlags &= ~TERM_OR_OK;
103792	}else if( pOrTerm->u.leftColumn!=iColumn ){
103793	okToChngToIN = 0;
103794	}else{
	@@ -103820,11 +103880,11 @@
103820	Expr pLeft = 0; / The LHS of the IN operator */
103821	Expr pNew; / The complete IN operator */
103822
103823	for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){
103824	if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue;
103825	assert( pOrTerm->eOperator==WO_EQ );
103826	assert( pOrTerm->leftCursor==iCursor );
103827	assert( pOrTerm->u.leftColumn==iColumn );
103828	pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0);
103829	pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup);
103830	pLeft = pOrTerm->pExpr->pLeft;
	@@ -103849,11 +103909,10 @@
103849	pTerm->eOperator = WO_NOOP; /* case 1 trumps case 2 */
103850	}
103851	}
103852	}
103853	#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
103854
103855
103856	/*
103857	** The input to this routine is an WhereTerm structure with only the
103858	** "pExpr" field filled in. The job of this routine is to analyze the
103859	** subexpression and populate all the other fields of the WhereTerm
	@@ -103919,21 +103978,23 @@
103919	}
103920	pTerm->prereqAll = prereqAll;
103921	pTerm->leftCursor = -1;
103922	pTerm->iParent = -1;
103923	pTerm->eOperator = 0;
103924	if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
103925	Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft);
103926	Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight);

103927	if( pLeft->op==TK_COLUMN ){
103928	pTerm->leftCursor = pLeft->iTable;
103929	pTerm->u.leftColumn = pLeft->iColumn;
103930	pTerm->eOperator = operatorMask(op);
103931	}
103932	if( pRight && pRight->op==TK_COLUMN ){
103933	WhereTerm *pNew;
103934	Expr *pDup;

103935	if( pTerm->leftCursor>=0 ){
103936	int idxNew;
103937	pDup = sqlite3ExprDup(db, pExpr, 0);
103938	if( db->mallocFailed ){
103939	sqlite3ExprDelete(db, pDup);
	@@ -103944,10 +104005,17 @@
103944	pNew = &pWC->a[idxNew];
103945	pNew->iParent = idxTerm;
103946	pTerm = &pWC->a[idxTerm];
103947	pTerm->nChild = 1;
103948	pTerm->wtFlags \|= TERM_COPIED;







103949	}else{
103950	pDup = pExpr;
103951	pNew = pTerm;
103952	}
103953	exprCommute(pParse, pDup);
	@@ -103955,11 +104023,11 @@
103955	pNew->leftCursor = pLeft->iTable;
103956	pNew->u.leftColumn = pLeft->iColumn;
103957	testcase( (prereqLeft \| extraRight) != prereqLeft );
103958	pNew->prereqRight = prereqLeft \| extraRight;
103959	pNew->prereqAll = prereqAll;
103960	pNew->eOperator = operatorMask(pDup->op);
103961	}
103962	}
103963
103964	#ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
103965	/* If a term is the BETWEEN operator, create two new virtual terms
	@@ -104414,11 +104482,11 @@
104414	return;
104415	}
104416
104417	/* Search the WHERE clause terms for a usable WO_OR term. */
104418	for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
104419	if( pTerm->eOperator==WO_OR
104420	&& ((pTerm->prereqAll & ~maskSrc) & p->notReady)==0
104421	&& (pTerm->u.pOrInfo->indexable & maskSrc)!=0
104422	){
104423	WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
104424	WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
	@@ -104435,11 +104503,11 @@
104435	sBOI.ppIdxInfo = 0;
104436	for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
104437	WHERETRACE(("... Multi-index OR testing for term %d of %d....\n",
104438	(pOrTerm - pOrWC->a), (pTerm - pWC->a)
104439	));
104440	if( pOrTerm->eOperator==WO_AND ){
104441	sBOI.pWC = &pOrTerm->u.pAndInfo->wc;
104442	bestIndex(&sBOI);
104443	}else if( pOrTerm->leftCursor==iCur ){
104444	WhereClause tempWC;
104445	tempWC.pParse = pWC->pParse;
	@@ -104496,11 +104564,11 @@
104496	struct SrcList_item pSrc, / Table we are trying to access */
104497	Bitmask notReady /* Tables in outer loops of the join */
104498	){
104499	char aff;
104500	if( pTerm->leftCursor!=pSrc->iCursor ) return 0;
104501	if( pTerm->eOperator!=WO_EQ ) return 0;
104502	if( (pTerm->prereqRight & notReady)!=0 ) return 0;
104503	aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;
104504	if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0;
104505	return 1;
104506	}
	@@ -104758,13 +104826,13 @@
104758
104759	/* Count the number of possible WHERE clause constraints referring
104760	** to this virtual table */
104761	for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
104762	if( pTerm->leftCursor != pSrc->iCursor ) continue;
104763	assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
104764	testcase( pTerm->eOperator==WO_IN );
104765	testcase( pTerm->eOperator==WO_ISNULL );
104766	if( pTerm->eOperator & (WO_ISNULL) ) continue;
104767	if( pTerm->wtFlags & TERM_VNULL ) continue;
104768	nTerm++;
104769	}
104770
	@@ -104811,18 +104879,18 @@
104811	pUsage;
104812
104813	for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
104814	u8 op;
104815	if( pTerm->leftCursor != pSrc->iCursor ) continue;
104816	assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
104817	testcase( pTerm->eOperator==WO_IN );
104818	testcase( pTerm->eOperator==WO_ISNULL );
104819	if( pTerm->eOperator & (WO_ISNULL) ) continue;
104820	if( pTerm->wtFlags & TERM_VNULL ) continue;
104821	pIdxCons[j].iColumn = pTerm->u.leftColumn;
104822	pIdxCons[j].iTermOffset = i;
104823	op = (u8)pTerm->eOperator;
104824	if( op==WO_IN ) op = WO_EQ;
104825	pIdxCons[j].op = op;
104826	/* The direct assignment in the previous line is possible only because
104827	** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The
104828	** following asserts verify this fact. */
	@@ -104988,11 +105056,11 @@
104988	pUsage = pIdxInfo->aConstraintUsage;
104989	for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
104990	j = pIdxCons->iTermOffset;
104991	pTerm = &pWC->a[j];
104992	if( (pTerm->prereqRight&p->notReady)==0
104993	&& (bAllowIN \|\| pTerm->eOperator!=WO_IN)
104994	){
104995	pIdxCons->usable = 1;
104996	}else{
104997	pIdxCons->usable = 0;
104998	}
	@@ -105020,11 +105088,11 @@
105020	for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
105021	if( pUsage[i].argvIndex>0 ){
105022	j = pIdxCons->iTermOffset;
105023	pTerm = &pWC->a[j];
105024	p->cost.used \|= pTerm->prereqRight;
105025	if( pTerm->eOperator==WO_IN && pUsage[i].omit==0 ){
105026	/* Do not attempt to use an IN constraint if the virtual table
105027	** says that the equivalent EQ constraint cannot be safely omitted.
105028	** If we do attempt to use such a constraint, some rows might be
105029	** repeated in the output. */
105030	break;
	@@ -105326,28 +105394,28 @@
105326	u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;
105327
105328	if( pLower ){
105329	Expr *pExpr = pLower->pExpr->pRight;
105330	rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
105331	assert( pLower->eOperator==WO_GT \|\| pLower->eOperator==WO_GE );
105332	if( rc==SQLITE_OK
105333	&& whereKeyStats(pParse, p, pRangeVal, 0, a)==SQLITE_OK
105334	){
105335	iLower = a[0];
105336	if( pLower->eOperator==WO_GT ) iLower += a[1];
105337	}
105338	sqlite3ValueFree(pRangeVal);
105339	}
105340	if( rc==SQLITE_OK && pUpper ){
105341	Expr *pExpr = pUpper->pExpr->pRight;
105342	rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
105343	assert( pUpper->eOperator==WO_LT \|\| pUpper->eOperator==WO_LE );
105344	if( rc==SQLITE_OK
105345	&& whereKeyStats(pParse, p, pRangeVal, 1, a)==SQLITE_OK
105346	){
105347	iUpper = a[0];
105348	if( pUpper->eOperator==WO_LE ) iUpper += a[1];
105349	}
105350	sqlite3ValueFree(pRangeVal);
105351	}
105352	if( rc==SQLITE_OK ){
105353	if( iUpper<=iLower ){
	@@ -105651,16 +105719,16 @@
105651	** if there are any X= or X IS NULL constraints in the WHERE clause. */
105652	pConstraint = findTerm(p->pWC, base, iColumn, p->notReady,
105653	WO_EQ\|WO_ISNULL\|WO_IN, pIdx);
105654	if( pConstraint==0 ){
105655	isEq = 0;
105656	}else if( pConstraint->eOperator==WO_IN ){
105657	/* Constraints of the form: "X IN ..." cannot be used with an ORDER BY
105658	** because we do not know in what order the values on the RHS of the IN
105659	** operator will occur. */
105660	break;
105661	}else if( pConstraint->eOperator==WO_ISNULL ){
105662	uniqueNotNull = 0;
105663	isEq = 1; /* "X IS NULL" means X has only a single value */
105664	}else if( pConstraint->prereqRight==0 ){
105665	isEq = 1; /* Constraint "X=constant" means X has only a single value */
105666	}else{
	@@ -106069,16 +106137,17 @@
106069	*/
106070	if( pc.plan.nRow>(double)1 && pc.plan.nEq==1
106071	&& pFirstTerm!=0 && aiRowEst[1]>1 ){
106072	assert( (pFirstTerm->eOperator & (WO_EQ\|WO_ISNULL\|WO_IN))!=0 );
106073	if( pFirstTerm->eOperator & (WO_EQ\|WO_ISNULL) ){
106074	testcase( pFirstTerm->eOperator==WO_EQ );
106075	testcase( pFirstTerm->eOperator==WO_ISNULL );

106076	whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight,
106077	&pc.plan.nRow);
106078	}else if( bInEst==0 ){
106079	assert( pFirstTerm->eOperator==WO_IN );
106080	whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList,
106081	&pc.plan.nRow);
106082	}
106083	}
106084	#endif /* SQLITE_ENABLE_STAT3 */
	@@ -106221,11 +106290,11 @@
106221	** more selective intentionally because of the subjective
106222	** observation that indexed range constraints really are more
106223	** selective in practice, on average. */
106224	pc.plan.nRow /= 3;
106225	}
106226	}else if( pTerm->eOperator!=WO_NOOP ){
106227	/* Any other expression lowers the output row count by half */
106228	pc.plan.nRow /= 2;
106229	}
106230	}
106231	if( pc.plan.nRow<2 ) pc.plan.nRow = 2;
	@@ -106273,12 +106342,13 @@
106273	assert( pSrc->pIndex==0
106274	\|\| p->cost.plan.u.pIdx==0
106275	\|\| p->cost.plan.u.pIdx==pSrc->pIndex
106276	);
106277
106278	WHERETRACE((" best index is: %s\n",
106279	p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk"));

106280
106281	bestOrClauseIndex(p);
106282	bestAutomaticIndex(p);
106283	p->cost.plan.wsFlags \|= eqTermMask;
106284	}
	@@ -106856,11 +106926,10 @@
106856	*/
106857	iReleaseReg = sqlite3GetTempReg(pParse);
106858	pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ\|WO_IN, 0);
106859	assert( pTerm!=0 );
106860	assert( pTerm->pExpr!=0 );
106861	assert( pTerm->leftCursor==iCur );
106862	assert( omitTable==0 );
106863	testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
106864	iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg);
106865	addrNxt = pLevel->addrNxt;
106866	sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
	@@ -107247,11 +107316,11 @@
107247	int ii; /* Loop counter */
107248	Expr pAndExpr = 0; / An ".. AND (...)" expression */
107249
107250	pTerm = pLevel->plan.u.pTerm;
107251	assert( pTerm!=0 );
107252	assert( pTerm->eOperator==WO_OR );
107253	assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
107254	pOrWc = &pTerm->u.pOrInfo->wc;
107255	pLevel->op = OP_Return;
107256	pLevel->p1 = regReturn;
107257
	@@ -107320,11 +107389,11 @@
107320	}
107321	}
107322
107323	for(ii=0; ii<pOrWc->nTerm; ii++){
107324	WhereTerm *pOrTerm = &pOrWc->a[ii];
107325	if( pOrTerm->leftCursor==iCur \|\| pOrTerm->eOperator==WO_AND ){
107326	WhereInfo pSubWInfo; / Info for single OR-term scan */
107327	Expr *pOrExpr = pOrTerm->pExpr;
107328	if( pAndExpr ){
107329	pAndExpr->pLeft = pOrExpr;
107330	pOrExpr = pAndExpr;
	@@ -107775,10 +107844,11 @@
107775	Index pIdx; / Index for FROM table at pTabItem */
107776	int j; /* For looping over FROM tables */
107777	int bestJ = -1; /* The value of j */
107778	Bitmask m; /* Bitmask value for j or bestJ */
107779	int isOptimal; /* Iterator for optimal/non-optimal search */

107780	int nUnconstrained; /* Number tables without INDEXED BY */
107781	Bitmask notIndexed; /* Mask of tables that cannot use an index */
107782
107783	memset(&bestPlan, 0, sizeof(bestPlan));
107784	bestPlan.rCost = SQLITE_BIG_DBL;
	@@ -107809,14 +107879,12 @@
107809	**
107810	** The second loop iteration is only performed if no optimal scan
107811	** strategies were found by the first iteration. This second iteration
107812	** is used to search for the lowest cost scan overall.
107813	**
107814	** Previous versions of SQLite performed only the second iteration -
107815	** the next outermost loop was always that with the lowest overall
107816	** cost. However, this meant that SQLite could select the wrong plan
107817	** for scripts such as the following:
107818	**
107819	** CREATE TABLE t1(a, b);
107820	** CREATE TABLE t2(c, d);
107821	** SELECT * FROM t2, t1 WHERE t2.rowid = t1.a;
107822	**
	@@ -107827,20 +107895,44 @@
107827	** algorithm may choose to use t2 for the outer loop, which is a much
107828	** costlier approach.
107829	*/
107830	nUnconstrained = 0;
107831	notIndexed = 0;
107832	for(isOptimal=(iFrom<nTabList-1); isOptimal>=0 && bestJ<0; isOptimal--){






107833	for(j=iFrom, sWBI.pSrc=&pTabList->a[j]; j<nTabList; j++, sWBI.pSrc++){
107834	int doNotReorder; /* True if this table should not be reordered */
107835
107836	doNotReorder = (sWBI.pSrc->jointype & (JT_LEFT\|JT_CROSS))!=0;
107837	if( j!=iFrom && doNotReorder ) break;
107838	m = getMask(pMaskSet, sWBI.pSrc->iCursor);
107839	if( (m & sWBI.notValid)==0 ){
107840	if( j==iFrom ) iFrom++;
107841	continue;






















107842	}
107843	sWBI.notReady = (isOptimal ? m : sWBI.notValid);
107844	if( sWBI.pSrc->pIndex==0 ) nUnconstrained++;
107845
107846	WHERETRACE((" === trying table %d (%s) with isOptimal=%d ===\n",
	@@ -107866,12 +107958,12 @@
107866	if( isOptimal && (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){
107867	notIndexed \|= m;
107868	}
107869	if( isOptimal ){
107870	pWInfo->a[j].rOptCost = sWBI.cost.rCost;
107871	}else if( iFrom<nTabList-1 ){
107872	/* If two or more tables have nearly the same outer loop cost,
107873	** very different inner loop (optimal) cost, we want to choose
107874	** for the outer loop that table which benefits the least from
107875	** being in the inner loop. The following code scales the
107876	** outer loop cost estimate to accomplish that. */
107877	WHERETRACE((" scaling cost from %.1f to %.1f\n",
	@@ -107912,15 +108004,23 @@
107912	sWBI.cost.rCost, sWBI.cost.plan.nRow,
107913	sWBI.cost.plan.nOBSat, sWBI.cost.plan.wsFlags));
107914	bestPlan = sWBI.cost;
107915	bestJ = j;
107916	}
107917	if( doNotReorder ) break;




107918	}
107919	}
107920	assert( bestJ>=0 );
107921	assert( sWBI.notValid & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );




107922	WHERETRACE(("*** Optimizer selects table %d (%s) for loop %d with:\n"
107923	" cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=0x%08x\n",
107924	bestJ, pTabList->a[bestJ].pTab->zName,
107925	pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow,
107926	bestPlan.plan.nOBSat, bestPlan.plan.wsFlags));
	@@ -136646,11 +136746,12 @@
136646	** would fit in a single node, use a smaller node-size.
136647	*/
136648	static int getNodeSize(
136649	sqlite3 db, / Database handle */
136650	Rtree pRtree, / Rtree handle */
136651	int isCreate /* True for xCreate, false for xConnect */

136652	){
136653	int rc;
136654	char *zSql;
136655	if( isCreate ){
136656	int iPageSize = 0;
	@@ -136659,17 +136760,22 @@
136659	if( rc==SQLITE_OK ){
136660	pRtree->iNodeSize = iPageSize-64;
136661	if( (4+pRtree->nBytesPerCell*RTREE_MAXCELLS)<pRtree->iNodeSize ){
136662	pRtree->iNodeSize = 4+pRtree->nBytesPerCell*RTREE_MAXCELLS;
136663	}


136664	}
136665	}else{
136666	zSql = sqlite3_mprintf(
136667	"SELECT length(data) FROM '%q'.'%q_node' WHERE nodeno = 1",
136668	pRtree->zDb, pRtree->zName
136669	);
136670	rc = getIntFromStmt(db, zSql, &pRtree->iNodeSize);



136671	}
136672
136673	sqlite3_free(zSql);
136674	return rc;
136675	}
	@@ -136729,11 +136835,11 @@
136729	pRtree->eCoordType = eCoordType;
136730	memcpy(pRtree->zDb, argv[1], nDb);
136731	memcpy(pRtree->zName, argv[2], nName);
136732
136733	/* Figure out the node size to use. */
136734	rc = getNodeSize(db, pRtree, isCreate);
136735
136736	/* Create/Connect to the underlying relational database schema. If
136737	** that is successful, call sqlite3_declare_vtab() to configure
136738	** the r-tree table schema.
136739	*/
136740

	--- src/sqlite3.c
	+++ src/sqlite3.c
	@@ -673,11 +673,11 @@
673	** [sqlite3_libversion_number()], [sqlite3_sourceid()],
674	** [sqlite_version()] and [sqlite_source_id()].
675	*/
676	#define SQLITE_VERSION "3.7.16"
677	#define SQLITE_VERSION_NUMBER 3007016
678	#define SQLITE_SOURCE_ID "2013-01-17 17:20:49 38852f158ab20bb4d7b264af987ec1538052bec3"
679
680	/*
681	** CAPI3REF: Run-Time Library Version Numbers
682	** KEYWORDS: sqlite3_version, sqlite3_sourceid
683	**
	@@ -8238,10 +8238,15 @@
8238	** A convenience macro that returns the number of elements in
8239	** an array.
8240	*/
8241	#define ArraySize(X) ((int)(sizeof(X)/sizeof(X[0])))
8242
8243	/*
8244	** Determine if the argument is a power of two
8245	*/
8246	#define IsPowerOfTwo(X) (((X)&((X)-1))==0)
8247
8248	/*
8249	** The following value as a destructor means to use sqlite3DbFree().
8250	** The sqlite3DbFree() routine requires two parameters instead of the
8251	** one parameter that destructors normally want. So we have to introduce
8252	** this magic value that the code knows to handle differently. Any
	@@ -10042,10 +10047,11 @@
10047	#define SQLITE_IdxRealAsInt 0x0010 /* Store REAL as INT in indices */
10048	#define SQLITE_DistinctOpt 0x0020 /* DISTINCT using indexes */
10049	#define SQLITE_CoverIdxScan 0x0040 /* Covering index scans */
10050	#define SQLITE_OrderByIdxJoin 0x0080 /* ORDER BY of joins via index */
10051	#define SQLITE_SubqCoroutine 0x0100 /* Evaluate subqueries as coroutines */
10052	#define SQLITE_Transitive 0x0200 /* Transitive constraints */
10053	#define SQLITE_AllOpts 0xffff /* All optimizations */
10054
10055	/*
10056	** Macros for testing whether or not optimizations are enabled or disabled.
10057	*/
	@@ -93581,11 +93587,11 @@
93587	sqlite3_rekey(db, zKey, i/2);
93588	}
93589	}else
93590	#endif
93591	#if defined(SQLITE_HAS_CODEC) \|\| defined(SQLITE_ENABLE_CEROD)
93592	if( sqlite3StrICmp(zLeft, "activate_extensions")==0 && zRight ){
93593	#ifdef SQLITE_HAS_CODEC
93594	if( sqlite3StrNICmp(zRight, "see-", 4)==0 ){
93595	sqlite3_activate_see(&zRight[4]);
93596	}
93597	#endif
	@@ -102802,12 +102808,12 @@
102808	Expr pExpr; / Pointer to the subexpression that is this term */
102809	int iParent; /* Disable pWC->a[iParent] when this term disabled */
102810	int leftCursor; /* Cursor number of X in "X <op> <expr>" */
102811	union {
102812	int leftColumn; /* Column number of X in "X <op> <expr>" */
102813	WhereOrInfo pOrInfo; / Extra information if (eOperator & WO_OR)!=0 */
102814	WhereAndInfo pAndInfo; / Extra information if (eOperator& WO_AND)!=0 */
102815	} u;
102816	u16 eOperator; /* A WO_xx value describing <op> */
102817	u8 wtFlags; /* TERM_xxx bit flags. See below */
102818	u8 nChild; /* Number of children that must disable us */
102819	WhereClause pWC; / The clause this term is part of */
	@@ -102931,10 +102937,11 @@
102937	#define WO_GE (WO_EQ<<(TK_GE-TK_EQ))
102938	#define WO_MATCH 0x040
102939	#define WO_ISNULL 0x080
102940	#define WO_OR 0x100 /* Two or more OR-connected terms */
102941	#define WO_AND 0x200 /* Two or more AND-connected terms */
102942	#define WO_EQUIV 0x400 /* Of the form A==B, both columns */
102943	#define WO_NOOP 0x800 /* This term does not restrict search space */
102944
102945	#define WO_ALL 0xfff /* Mask of all possible WO_* values */
102946	#define WO_SINGLE 0x0ff /* Mask of all non-compound WO_* values */
102947
	@@ -103333,58 +103340,112 @@
103340	/*
103341	** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
103342	** where X is a reference to the iColumn of table iCur and <op> is one of
103343	** the WO_xx operator codes specified by the op parameter.
103344	** Return a pointer to the term. Return 0 if not found.
103345	**
103346	** The term returned might by Y=<expr> if there is another constraint in
103347	** the WHERE clause that specifies that X=Y. Any such constraints will be
103348	** identified by the WO_EQUIV bit in the pTerm->eOperator field. The
103349	** aEquiv[] array holds X and all its equivalents, with each SQL variable
103350	** taking up two slots in aEquiv[]. The first slot is for the cursor number
103351	** and the second is for the column number. There are 22 slots in aEquiv[]
103352	** so that means we can look for X plus up to 10 other equivalent values.
103353	** Hence a search for X will return <expr> if X=A1 and A1=A2 and A2=A3
103354	** and ... and A9=A10 and A10=<expr>.
103355	**
103356	** If there are multiple terms in the WHERE clause of the form "X <op> <expr>"
103357	** then try for the one with no dependencies on <expr> - in other words where
103358	** <expr> is a constant expression of some kind. Only return entries of
103359	** the form "X <op> Y" where Y is a column in another table if no terms of
103360	** the form "X <op> <const-expr>" exist. Other than this priority, if there
103361	** are two or more terms that match, then the choice of which term to return
103362	** is arbitrary.
103363	*/
103364	static WhereTerm *findTerm(
103365	WhereClause pWC, / The WHERE clause to be searched */
103366	int iCur, /* Cursor number of LHS */
103367	int iColumn, /* Column number of LHS */
103368	Bitmask notReady, /* RHS must not overlap with this mask */
103369	u32 op, /* Mask of WO_xx values describing operator */
103370	Index pIdx / Must be compatible with this index, if not NULL */
103371	){
103372	WhereTerm pTerm; / Term being examined as possible result */
103373	WhereTerm pResult = 0; / The answer to return */
103374	WhereClause pWCOrig = pWC; / Original pWC value */
103375	int j, k; /* Loop counters */
103376	Expr pX; / Pointer to an expression */
103377	Parse pParse; / Parsing context */
103378	int iOrigCol = iColumn; /* Original value of iColumn */
103379	int nEquiv = 2; /* Number of entires in aEquiv[] */
103380	int iEquiv = 2; /* Number of entries of aEquiv[] processed so far */
103381	int aEquiv[22]; /* iCur,iColumn and up to 10 other equivalents */
103382
103383	assert( iCur>=0 );
103384	aEquiv[0] = iCur;
103385	aEquiv[1] = iColumn;
103386	for(;;){
103387	for(pWC=pWCOrig; pWC; pWC=pWC->pOuter){
103388	for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
103389	if( pTerm->leftCursor==iCur
103390	&& pTerm->u.leftColumn==iColumn
103391	){
103392	if( (pTerm->prereqRight & notReady)==0
103393	&& (pTerm->eOperator & op & WO_ALL)!=0
103394	){
103395	if( iOrigCol>=0 && pIdx && (pTerm->eOperator & WO_ISNULL)==0 ){
103396	CollSeq *pColl;
103397	char idxaff;
103398
103399	pX = pTerm->pExpr;
103400	pParse = pWC->pParse;
103401	idxaff = pIdx->pTable->aCol[iOrigCol].affinity;
103402	if( !sqlite3IndexAffinityOk(pX, idxaff) ){
103403	continue;
103404	}
103405
103406	/* Figure out the collation sequence required from an index for
103407	** it to be useful for optimising expression pX. Store this
103408	** value in variable pColl.
103409	*/
103410	assert(pX->pLeft);
103411	pColl = sqlite3BinaryCompareCollSeq(pParse,pX->pLeft,pX->pRight);
103412	if( pColl==0 ) pColl = pParse->db->pDfltColl;
103413
103414	for(j=0; pIdx->aiColumn[j]!=iOrigCol; j++){
103415	if( NEVER(j>=pIdx->nColumn) ) return 0;
103416	}
103417	if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ){
103418	continue;
103419	}
103420	}
103421	pResult = pTerm;
103422	if( pTerm->prereqRight==0 ) goto findTerm_success;
103423	}
103424	if( (pTerm->eOperator & WO_EQUIV)!=0
103425	&& nEquiv<ArraySize(aEquiv)
103426	){
103427	pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight);
103428	assert( pX->op==TK_COLUMN );
103429	for(j=0; j<nEquiv; j+=2){
103430	if( aEquiv[j]==pX->iTable && aEquiv[j+1]==pX->iColumn ) break;
103431	}
103432	if( j==nEquiv ){
103433	aEquiv[j] = pX->iTable;
103434	aEquiv[j+1] = pX->iColumn;
103435	nEquiv += 2;
103436	}
103437	}
103438	}
103439	}
103440	}
103441	if( iEquiv>=nEquiv ) break;
103442	iCur = aEquiv[iEquiv++];
103443	iColumn = aEquiv[iEquiv++];
103444	}
103445	findTerm_success:
103446	return pResult;
103447	}
103448
103449	/* Forward reference */
103450	static void exprAnalyze(SrcList, WhereClause, int);
103451
	@@ -103658,11 +103719,10 @@
103719	indexable = ~(Bitmask)0;
103720	chngToIN = ~(pWC->vmask);
103721	for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){
103722	if( (pOrTerm->eOperator & WO_SINGLE)==0 ){
103723	WhereAndInfo *pAndInfo;

103724	assert( (pOrTerm->wtFlags & (TERM_ANDINFO\|TERM_ORINFO))==0 );
103725	chngToIN = 0;
103726	pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo));
103727	if( pAndInfo ){
103728	WhereClause *pAndWC;
	@@ -103697,11 +103757,11 @@
103757	if( pOrTerm->wtFlags & TERM_VIRTUAL ){
103758	WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent];
103759	b \|= getMask(pMaskSet, pOther->leftCursor);
103760	}
103761	indexable &= b;
103762	if( (pOrTerm->eOperator & WO_EQ)==0 ){
103763	chngToIN = 0;
103764	}else{
103765	chngToIN &= b;
103766	}
103767	}
	@@ -103748,11 +103808,11 @@
103808	** and column is found but leave okToChngToIN false if not found.
103809	*/
103810	for(j=0; j<2 && !okToChngToIN; j++){
103811	pOrTerm = pOrWc->a;
103812	for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){
103813	assert( pOrTerm->eOperator & WO_EQ );
103814	pOrTerm->wtFlags &= ~TERM_OR_OK;
103815	if( pOrTerm->leftCursor==iCursor ){
103816	/* This is the 2-bit case and we are on the second iteration and
103817	** current term is from the first iteration. So skip this term. */
103818	assert( j==1 );
	@@ -103774,21 +103834,21 @@
103834	}
103835	if( i<0 ){
103836	/* No candidate table+column was found. This can only occur
103837	** on the second iteration */
103838	assert( j==1 );
103839	assert( IsPowerOfTwo(chngToIN) );
103840	assert( chngToIN==getMask(pMaskSet, iCursor) );
103841	break;
103842	}
103843	testcase( j==1 );
103844
103845	/* We have found a candidate table and column. Check to see if that
103846	** table and column is common to every term in the OR clause */
103847	okToChngToIN = 1;
103848	for(; i>=0 && okToChngToIN; i--, pOrTerm++){
103849	assert( pOrTerm->eOperator & WO_EQ );
103850	if( pOrTerm->leftCursor!=iCursor ){
103851	pOrTerm->wtFlags &= ~TERM_OR_OK;
103852	}else if( pOrTerm->u.leftColumn!=iColumn ){
103853	okToChngToIN = 0;
103854	}else{
	@@ -103820,11 +103880,11 @@
103880	Expr pLeft = 0; / The LHS of the IN operator */
103881	Expr pNew; / The complete IN operator */
103882
103883	for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){
103884	if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue;
103885	assert( pOrTerm->eOperator & WO_EQ );
103886	assert( pOrTerm->leftCursor==iCursor );
103887	assert( pOrTerm->u.leftColumn==iColumn );
103888	pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0);
103889	pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup);
103890	pLeft = pOrTerm->pExpr->pLeft;
	@@ -103849,11 +103909,10 @@
103909	pTerm->eOperator = WO_NOOP; /* case 1 trumps case 2 */
103910	}
103911	}
103912	}
103913	#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */

103914
103915	/*
103916	** The input to this routine is an WhereTerm structure with only the
103917	** "pExpr" field filled in. The job of this routine is to analyze the
103918	** subexpression and populate all the other fields of the WhereTerm
	@@ -103919,21 +103978,23 @@
103978	}
103979	pTerm->prereqAll = prereqAll;
103980	pTerm->leftCursor = -1;
103981	pTerm->iParent = -1;
103982	pTerm->eOperator = 0;
103983	if( allowedOp(op) ){
103984	Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft);
103985	Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight);
103986	u16 opMask = (pTerm->prereqRight & prereqLeft)==0 ? WO_ALL : WO_EQUIV;
103987	if( pLeft->op==TK_COLUMN ){
103988	pTerm->leftCursor = pLeft->iTable;
103989	pTerm->u.leftColumn = pLeft->iColumn;
103990	pTerm->eOperator = operatorMask(op) & opMask;
103991	}
103992	if( pRight && pRight->op==TK_COLUMN ){
103993	WhereTerm *pNew;
103994	Expr *pDup;
103995	u16 eExtraOp = 0; /* Extra bits for pNew->eOperator */
103996	if( pTerm->leftCursor>=0 ){
103997	int idxNew;
103998	pDup = sqlite3ExprDup(db, pExpr, 0);
103999	if( db->mallocFailed ){
104000	sqlite3ExprDelete(db, pDup);
	@@ -103944,10 +104005,17 @@
104005	pNew = &pWC->a[idxNew];
104006	pNew->iParent = idxTerm;
104007	pTerm = &pWC->a[idxTerm];
104008	pTerm->nChild = 1;
104009	pTerm->wtFlags \|= TERM_COPIED;
104010	if( pExpr->op==TK_EQ
104011	&& !ExprHasProperty(pExpr, EP_FromJoin)
104012	&& OptimizationEnabled(db, SQLITE_Transitive)
104013	){
104014	pTerm->eOperator \|= WO_EQUIV;
104015	eExtraOp = WO_EQUIV;
104016	}
104017	}else{
104018	pDup = pExpr;
104019	pNew = pTerm;
104020	}
104021	exprCommute(pParse, pDup);
	@@ -103955,11 +104023,11 @@
104023	pNew->leftCursor = pLeft->iTable;
104024	pNew->u.leftColumn = pLeft->iColumn;
104025	testcase( (prereqLeft \| extraRight) != prereqLeft );
104026	pNew->prereqRight = prereqLeft \| extraRight;
104027	pNew->prereqAll = prereqAll;
104028	pNew->eOperator = (operatorMask(pDup->op) + eExtraOp) & opMask;
104029	}
104030	}
104031
104032	#ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
104033	/* If a term is the BETWEEN operator, create two new virtual terms
	@@ -104414,11 +104482,11 @@
104482	return;
104483	}
104484
104485	/* Search the WHERE clause terms for a usable WO_OR term. */
104486	for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
104487	if( (pTerm->eOperator & WO_OR)!=0
104488	&& ((pTerm->prereqAll & ~maskSrc) & p->notReady)==0
104489	&& (pTerm->u.pOrInfo->indexable & maskSrc)!=0
104490	){
104491	WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
104492	WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
	@@ -104435,11 +104503,11 @@
104503	sBOI.ppIdxInfo = 0;
104504	for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
104505	WHERETRACE(("... Multi-index OR testing for term %d of %d....\n",
104506	(pOrTerm - pOrWC->a), (pTerm - pWC->a)
104507	));
104508	if( (pOrTerm->eOperator& WO_AND)!=0 ){
104509	sBOI.pWC = &pOrTerm->u.pAndInfo->wc;
104510	bestIndex(&sBOI);
104511	}else if( pOrTerm->leftCursor==iCur ){
104512	WhereClause tempWC;
104513	tempWC.pParse = pWC->pParse;
	@@ -104496,11 +104564,11 @@
104564	struct SrcList_item pSrc, / Table we are trying to access */
104565	Bitmask notReady /* Tables in outer loops of the join */
104566	){
104567	char aff;
104568	if( pTerm->leftCursor!=pSrc->iCursor ) return 0;
104569	if( (pTerm->eOperator & WO_EQ)==0 ) return 0;
104570	if( (pTerm->prereqRight & notReady)!=0 ) return 0;
104571	aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;
104572	if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0;
104573	return 1;
104574	}
	@@ -104758,13 +104826,13 @@
104826
104827	/* Count the number of possible WHERE clause constraints referring
104828	** to this virtual table */
104829	for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
104830	if( pTerm->leftCursor != pSrc->iCursor ) continue;
104831	assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
104832	testcase( pTerm->eOperator & WO_IN );
104833	testcase( pTerm->eOperator & WO_ISNULL );
104834	if( pTerm->eOperator & (WO_ISNULL) ) continue;
104835	if( pTerm->wtFlags & TERM_VNULL ) continue;
104836	nTerm++;
104837	}
104838
	@@ -104811,18 +104879,18 @@
104879	pUsage;
104880
104881	for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
104882	u8 op;
104883	if( pTerm->leftCursor != pSrc->iCursor ) continue;
104884	assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
104885	testcase( pTerm->eOperator & WO_IN );
104886	testcase( pTerm->eOperator & WO_ISNULL );
104887	if( pTerm->eOperator & (WO_ISNULL) ) continue;
104888	if( pTerm->wtFlags & TERM_VNULL ) continue;
104889	pIdxCons[j].iColumn = pTerm->u.leftColumn;
104890	pIdxCons[j].iTermOffset = i;
104891	op = (u8)pTerm->eOperator & WO_ALL;
104892	if( op==WO_IN ) op = WO_EQ;
104893	pIdxCons[j].op = op;
104894	/* The direct assignment in the previous line is possible only because
104895	** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The
104896	** following asserts verify this fact. */
	@@ -104988,11 +105056,11 @@
105056	pUsage = pIdxInfo->aConstraintUsage;
105057	for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
105058	j = pIdxCons->iTermOffset;
105059	pTerm = &pWC->a[j];
105060	if( (pTerm->prereqRight&p->notReady)==0
105061	&& (bAllowIN \|\| (pTerm->eOperator & WO_IN)==0)
105062	){
105063	pIdxCons->usable = 1;
105064	}else{
105065	pIdxCons->usable = 0;
105066	}
	@@ -105020,11 +105088,11 @@
105088	for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
105089	if( pUsage[i].argvIndex>0 ){
105090	j = pIdxCons->iTermOffset;
105091	pTerm = &pWC->a[j];
105092	p->cost.used \|= pTerm->prereqRight;
105093	if( (pTerm->eOperator & WO_IN)!=0 && pUsage[i].omit==0 ){
105094	/* Do not attempt to use an IN constraint if the virtual table
105095	** says that the equivalent EQ constraint cannot be safely omitted.
105096	** If we do attempt to use such a constraint, some rows might be
105097	** repeated in the output. */
105098	break;
	@@ -105326,28 +105394,28 @@
105394	u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;
105395
105396	if( pLower ){
105397	Expr *pExpr = pLower->pExpr->pRight;
105398	rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
105399	assert( (pLower->eOperator & (WO_GT\|WO_GE))!=0 );
105400	if( rc==SQLITE_OK
105401	&& whereKeyStats(pParse, p, pRangeVal, 0, a)==SQLITE_OK
105402	){
105403	iLower = a[0];
105404	if( (pLower->eOperator & WO_GT)!=0 ) iLower += a[1];
105405	}
105406	sqlite3ValueFree(pRangeVal);
105407	}
105408	if( rc==SQLITE_OK && pUpper ){
105409	Expr *pExpr = pUpper->pExpr->pRight;
105410	rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
105411	assert( (pUpper->eOperator & (WO_LT\|WO_LE))!=0 );
105412	if( rc==SQLITE_OK
105413	&& whereKeyStats(pParse, p, pRangeVal, 1, a)==SQLITE_OK
105414	){
105415	iUpper = a[0];
105416	if( (pUpper->eOperator & WO_LE)!=0 ) iUpper += a[1];
105417	}
105418	sqlite3ValueFree(pRangeVal);
105419	}
105420	if( rc==SQLITE_OK ){
105421	if( iUpper<=iLower ){
	@@ -105651,16 +105719,16 @@
105719	** if there are any X= or X IS NULL constraints in the WHERE clause. */
105720	pConstraint = findTerm(p->pWC, base, iColumn, p->notReady,
105721	WO_EQ\|WO_ISNULL\|WO_IN, pIdx);
105722	if( pConstraint==0 ){
105723	isEq = 0;
105724	}else if( (pConstraint->eOperator & WO_IN)!=0 ){
105725	/* Constraints of the form: "X IN ..." cannot be used with an ORDER BY
105726	** because we do not know in what order the values on the RHS of the IN
105727	** operator will occur. */
105728	break;
105729	}else if( (pConstraint->eOperator & WO_ISNULL)!=0 ){
105730	uniqueNotNull = 0;
105731	isEq = 1; /* "X IS NULL" means X has only a single value */
105732	}else if( pConstraint->prereqRight==0 ){
105733	isEq = 1; /* Constraint "X=constant" means X has only a single value */
105734	}else{
	@@ -106069,16 +106137,17 @@
106137	*/
106138	if( pc.plan.nRow>(double)1 && pc.plan.nEq==1
106139	&& pFirstTerm!=0 && aiRowEst[1]>1 ){
106140	assert( (pFirstTerm->eOperator & (WO_EQ\|WO_ISNULL\|WO_IN))!=0 );
106141	if( pFirstTerm->eOperator & (WO_EQ\|WO_ISNULL) ){
106142	testcase( pFirstTerm->eOperator & WO_EQ );
106143	testcase( pFirstTerm->eOperator & WO_EQUIV );
106144	testcase( pFirstTerm->eOperator & WO_ISNULL );
106145	whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight,
106146	&pc.plan.nRow);
106147	}else if( bInEst==0 ){
106148	assert( pFirstTerm->eOperator & WO_IN );
106149	whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList,
106150	&pc.plan.nRow);
106151	}
106152	}
106153	#endif /* SQLITE_ENABLE_STAT3 */
	@@ -106221,11 +106290,11 @@
106290	** more selective intentionally because of the subjective
106291	** observation that indexed range constraints really are more
106292	** selective in practice, on average. */
106293	pc.plan.nRow /= 3;
106294	}
106295	}else if( (pTerm->eOperator & WO_NOOP)==0 ){
106296	/* Any other expression lowers the output row count by half */
106297	pc.plan.nRow /= 2;
106298	}
106299	}
106300	if( pc.plan.nRow<2 ) pc.plan.nRow = 2;
	@@ -106273,12 +106342,13 @@
106342	assert( pSrc->pIndex==0
106343	\|\| p->cost.plan.u.pIdx==0
106344	\|\| p->cost.plan.u.pIdx==pSrc->pIndex
106345	);
106346
106347	WHERETRACE((" best index is %s cost=%.1f\n",
106348	p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk",
106349	p->cost.rCost));
106350
106351	bestOrClauseIndex(p);
106352	bestAutomaticIndex(p);
106353	p->cost.plan.wsFlags \|= eqTermMask;
106354	}
	@@ -106856,11 +106926,10 @@
106926	*/
106927	iReleaseReg = sqlite3GetTempReg(pParse);
106928	pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ\|WO_IN, 0);
106929	assert( pTerm!=0 );
106930	assert( pTerm->pExpr!=0 );

106931	assert( omitTable==0 );
106932	testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
106933	iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg);
106934	addrNxt = pLevel->addrNxt;
106935	sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
	@@ -107247,11 +107316,11 @@
107316	int ii; /* Loop counter */
107317	Expr pAndExpr = 0; / An ".. AND (...)" expression */
107318
107319	pTerm = pLevel->plan.u.pTerm;
107320	assert( pTerm!=0 );
107321	assert( pTerm->eOperator & WO_OR );
107322	assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
107323	pOrWc = &pTerm->u.pOrInfo->wc;
107324	pLevel->op = OP_Return;
107325	pLevel->p1 = regReturn;
107326
	@@ -107320,11 +107389,11 @@
107389	}
107390	}
107391
107392	for(ii=0; ii<pOrWc->nTerm; ii++){
107393	WhereTerm *pOrTerm = &pOrWc->a[ii];
107394	if( pOrTerm->leftCursor==iCur \|\| (pOrTerm->eOperator & WO_AND)!=0 ){
107395	WhereInfo pSubWInfo; / Info for single OR-term scan */
107396	Expr *pOrExpr = pOrTerm->pExpr;
107397	if( pAndExpr ){
107398	pAndExpr->pLeft = pOrExpr;
107399	pOrExpr = pAndExpr;
	@@ -107775,10 +107844,11 @@
107844	Index pIdx; / Index for FROM table at pTabItem */
107845	int j; /* For looping over FROM tables */
107846	int bestJ = -1; /* The value of j */
107847	Bitmask m; /* Bitmask value for j or bestJ */
107848	int isOptimal; /* Iterator for optimal/non-optimal search */
107849	int ckOptimal; /* Do the optimal scan check */
107850	int nUnconstrained; /* Number tables without INDEXED BY */
107851	Bitmask notIndexed; /* Mask of tables that cannot use an index */
107852
107853	memset(&bestPlan, 0, sizeof(bestPlan));
107854	bestPlan.rCost = SQLITE_BIG_DBL;
	@@ -107809,14 +107879,12 @@
107879	**
107880	** The second loop iteration is only performed if no optimal scan
107881	** strategies were found by the first iteration. This second iteration
107882	** is used to search for the lowest cost scan overall.
107883	**
107884	** Without the optimal scan step (the first iteration) a suboptimal
107885	** plan might be chosen for queries like this:


107886	**
107887	** CREATE TABLE t1(a, b);
107888	** CREATE TABLE t2(c, d);
107889	** SELECT * FROM t2, t1 WHERE t2.rowid = t1.a;
107890	**
	@@ -107827,20 +107895,44 @@
107895	** algorithm may choose to use t2 for the outer loop, which is a much
107896	** costlier approach.
107897	*/
107898	nUnconstrained = 0;
107899	notIndexed = 0;
107900
107901	/* The optimal scan check only occurs if there are two or more tables
107902	** available to be reordered */
107903	if( iFrom==nTabList-1 ){
107904	ckOptimal = 0; /* Common case of just one table in the FROM clause */
107905	}else{
107906	ckOptimal = -1;
107907	for(j=iFrom, sWBI.pSrc=&pTabList->a[j]; j<nTabList; j++, sWBI.pSrc++){




107908	m = getMask(pMaskSet, sWBI.pSrc->iCursor);
107909	if( (m & sWBI.notValid)==0 ){
107910	if( j==iFrom ) iFrom++;
107911	continue;
107912	}
107913	if( j>iFrom && (sWBI.pSrc->jointype & (JT_LEFT\|JT_CROSS))!=0 ) break;
107914	if( ++ckOptimal ) break;
107915	if( (sWBI.pSrc->jointype & JT_LEFT)!=0 ) break;
107916	}
107917	}
107918	assert( ckOptimal==0 \|\| ckOptimal==1 );
107919
107920	for(isOptimal=ckOptimal; isOptimal>=0 && bestJ<0; isOptimal--){
107921	for(j=iFrom, sWBI.pSrc=&pTabList->a[j]; j<nTabList; j++, sWBI.pSrc++){
107922	if( j>iFrom && (sWBI.pSrc->jointype & (JT_LEFT\|JT_CROSS))!=0 ){
107923	/* This break and one like it in the ckOptimal computation loop
107924	** above prevent table reordering across LEFT and CROSS JOINs.
107925	** The LEFT JOIN case is necessary for correctness. The prohibition
107926	** against reordering across a CROSS JOIN is an SQLite feature that
107927	** allows the developer to control table reordering */
107928	break;
107929	}
107930	m = getMask(pMaskSet, sWBI.pSrc->iCursor);
107931	if( (m & sWBI.notValid)==0 ){
107932	assert( j>iFrom );
107933	continue;
107934	}
107935	sWBI.notReady = (isOptimal ? m : sWBI.notValid);
107936	if( sWBI.pSrc->pIndex==0 ) nUnconstrained++;
107937
107938	WHERETRACE((" === trying table %d (%s) with isOptimal=%d ===\n",
	@@ -107866,12 +107958,12 @@
107958	if( isOptimal && (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){
107959	notIndexed \|= m;
107960	}
107961	if( isOptimal ){
107962	pWInfo->a[j].rOptCost = sWBI.cost.rCost;
107963	}else if( ckOptimal ){
107964	/* If two or more tables have nearly the same outer loop cost, but
107965	** very different inner loop (optimal) cost, we want to choose
107966	** for the outer loop that table which benefits the least from
107967	** being in the inner loop. The following code scales the
107968	** outer loop cost estimate to accomplish that. */
107969	WHERETRACE((" scaling cost from %.1f to %.1f\n",
	@@ -107912,15 +108004,23 @@
108004	sWBI.cost.rCost, sWBI.cost.plan.nRow,
108005	sWBI.cost.plan.nOBSat, sWBI.cost.plan.wsFlags));
108006	bestPlan = sWBI.cost;
108007	bestJ = j;
108008	}
108009
108010	/* In a join like "w JOIN x LEFT JOIN y JOIN z" make sure that
108011	** table y (and not table z) is always the next inner loop inside
108012	** of table x. */
108013	if( (sWBI.pSrc->jointype & JT_LEFT)!=0 ) break;
108014	}
108015	}
108016	assert( bestJ>=0 );
108017	assert( sWBI.notValid & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
108018	assert( bestJ==iFrom \|\| (pTabList->a[iFrom].jointype & JT_LEFT)==0 );
108019	testcase( bestJ>iFrom && (pTabList->a[iFrom].jointype & JT_CROSS)!=0 );
108020	testcase( bestJ>iFrom && bestJ<nTabList-1
108021	&& (pTabList->a[bestJ+1].jointype & JT_LEFT)!=0 );
108022	WHERETRACE(("*** Optimizer selects table %d (%s) for loop %d with:\n"
108023	" cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=0x%08x\n",
108024	bestJ, pTabList->a[bestJ].pTab->zName,
108025	pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow,
108026	bestPlan.plan.nOBSat, bestPlan.plan.wsFlags));
	@@ -136646,11 +136746,12 @@
136746	** would fit in a single node, use a smaller node-size.
136747	*/
136748	static int getNodeSize(
136749	sqlite3 db, / Database handle */
136750	Rtree pRtree, / Rtree handle */
136751	int isCreate, /* True for xCreate, false for xConnect */
136752	char *pzErr / OUT: Error message, if any */
136753	){
136754	int rc;
136755	char *zSql;
136756	if( isCreate ){
136757	int iPageSize = 0;
	@@ -136659,17 +136760,22 @@
136760	if( rc==SQLITE_OK ){
136761	pRtree->iNodeSize = iPageSize-64;
136762	if( (4+pRtree->nBytesPerCell*RTREE_MAXCELLS)<pRtree->iNodeSize ){
136763	pRtree->iNodeSize = 4+pRtree->nBytesPerCell*RTREE_MAXCELLS;
136764	}
136765	}else{
136766	*pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
136767	}
136768	}else{
136769	zSql = sqlite3_mprintf(
136770	"SELECT length(data) FROM '%q'.'%q_node' WHERE nodeno = 1",
136771	pRtree->zDb, pRtree->zName
136772	);
136773	rc = getIntFromStmt(db, zSql, &pRtree->iNodeSize);
136774	if( rc!=SQLITE_OK ){
136775	*pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
136776	}
136777	}
136778
136779	sqlite3_free(zSql);
136780	return rc;
136781	}
	@@ -136729,11 +136835,11 @@
136835	pRtree->eCoordType = eCoordType;
136836	memcpy(pRtree->zDb, argv[1], nDb);
136837	memcpy(pRtree->zName, argv[2], nName);
136838
136839	/* Figure out the node size to use. */
136840	rc = getNodeSize(db, pRtree, isCreate, pzErr);
136841
136842	/* Create/Connect to the underlying relational database schema. If
136843	** that is successful, call sqlite3_declare_vtab() to configure
136844	** the r-tree table schema.
136845	*/
136846

M src/sqlite3.h

+1 -1

		--- src/sqlite3.h
		+++ src/sqlite3.h
		@@ -107,11 +107,11 @@
107	107	** [sqlite3_libversion_number()], [sqlite3_sourceid()],
108	108	** [sqlite_version()] and [sqlite_source_id()].
109	109	*/
110	110	#define SQLITE_VERSION "3.7.16"
111	111	#define SQLITE_VERSION_NUMBER 3007016
112		-#define SQLITE_SOURCE_ID "2013-01-09 11:31:17 5774f2175ce621dfc4b6b93f7ee13fd66f3ec2b9"
	112	+#define SQLITE_SOURCE_ID "2013-01-17 17:20:49 38852f158ab20bb4d7b264af987ec1538052bec3"
113	113
114	114	/*
115	115	** CAPI3REF: Run-Time Library Version Numbers
116	116	** KEYWORDS: sqlite3_version, sqlite3_sourceid
117	117	**
118	118

	--- src/sqlite3.h
	+++ src/sqlite3.h
	@@ -107,11 +107,11 @@
107	** [sqlite3_libversion_number()], [sqlite3_sourceid()],
108	** [sqlite_version()] and [sqlite_source_id()].
109	*/
110	#define SQLITE_VERSION "3.7.16"
111	#define SQLITE_VERSION_NUMBER 3007016
112	#define SQLITE_SOURCE_ID "2013-01-09 11:31:17 5774f2175ce621dfc4b6b93f7ee13fd66f3ec2b9"
113
114	/*
115	** CAPI3REF: Run-Time Library Version Numbers
116	** KEYWORDS: sqlite3_version, sqlite3_sourceid
117	**
118

	--- src/sqlite3.h
	+++ src/sqlite3.h
	@@ -107,11 +107,11 @@
107	** [sqlite3_libversion_number()], [sqlite3_sourceid()],
108	** [sqlite_version()] and [sqlite_source_id()].
109	*/
110	#define SQLITE_VERSION "3.7.16"
111	#define SQLITE_VERSION_NUMBER 3007016
112	#define SQLITE_SOURCE_ID "2013-01-17 17:20:49 38852f158ab20bb4d7b264af987ec1538052bec3"
113
114	/*
115	** CAPI3REF: Run-Time Library Version Numbers
116	** KEYWORDS: sqlite3_version, sqlite3_sourceid
117	**
118

Fossil SCM

Keyboard Shortcuts