Fossil SCM

Update the built-in SQLite to the latest 3.8.1 beta from upstream.

drh 2013-10-10 15:19 trunk

Commit cb29ef2a1e8b7ccdd4c732357ce7d468b3a7a184

Parent d66cfb164f3987d…

2 files changed +395 -279 +1 -1

M src/sqlite3.c

+395 -279

		--- src/sqlite3.c
		+++ src/sqlite3.c
		@@ -656,11 +656,11 @@
656	656	** [sqlite3_libversion_number()], [sqlite3_sourceid()],
657	657	** [sqlite_version()] and [sqlite_source_id()].
658	658	*/
659	659	#define SQLITE_VERSION "3.8.1"
660	660	#define SQLITE_VERSION_NUMBER 3008001
661		-#define SQLITE_SOURCE_ID "2013-10-07 21:49:16 36d64dc36f18c166b2c93c43579fa3bbb5cd545f"
	661	+#define SQLITE_SOURCE_ID "2013-10-10 15:04:52 af7abebeb1f70466833bc766d294d721eaef746f"
662	662
663	663	/*
664	664	** CAPI3REF: Run-Time Library Version Numbers
665	665	** KEYWORDS: sqlite3_version, sqlite3_sourceid
666	666	**
		@@ -8272,10 +8272,35 @@
8272	8272	typedef u64 tRowcnt; /* 64-bit only if requested at compile-time */
8273	8273	#else
8274	8274	typedef u32 tRowcnt; /* 32-bit is the default */
8275	8275	#endif
8276	8276
	8277	+/*
	8278	+** Estimated quantities used for query planning are stored as 16-bit
	8279	+** logarithms. For quantity X, the value stored is 10*log2(X). This
	8280	+** gives a possible range of values of approximately 1.0e986 to 1e-986.
	8281	+** But the allowed values are "grainy". Not every value is representable.
	8282	+** For example, quantities 16 and 17 are both represented by a LogEst
	8283	+** of 40. However, since LogEst quantatites are suppose to be estimates,
	8284	+** not exact values, this imprecision is not a problem.
	8285	+**
	8286	+** "LogEst" is short for "Logarithimic Estimate".
	8287	+**
	8288	+** Examples:
	8289	+** 1 -> 0 20 -> 43 10000 -> 132
	8290	+** 2 -> 10 25 -> 46 25000 -> 146
	8291	+** 3 -> 16 100 -> 66 1000000 -> 199
	8292	+** 4 -> 20 1000 -> 99 1048576 -> 200
	8293	+** 10 -> 33 1024 -> 100 4294967296 -> 320
	8294	+**
	8295	+** The LogEst can be negative to indicate fractional values.
	8296	+** Examples:
	8297	+**
	8298	+** 0.5 -> -10 0.1 -> -33 0.0625 -> -40
	8299	+*/
	8300	+typedef INT16_TYPE LogEst;
	8301	+
8277	8302	/*
8278	8303	** Macros to determine whether the machine is big or little endian,
8279	8304	** evaluated at runtime.
8280	8305	*/
8281	8306	#ifdef SQLITE_AMALGAMATION
		@@ -10419,11 +10444,12 @@
10419	10444	char zDflt; / Original text of the default value */
10420	10445	char zType; / Data type for this column */
10421	10446	char zColl; / Collating sequence. If NULL, use the default */
10422	10447	u8 notNull; /* An OE_ code for handling a NOT NULL constraint */
10423	10448	char affinity; /* One of the SQLITE_AFF_... values */
10424		- u16 colFlags; /* Boolean properties. See COLFLAG_ defines below */
	10449	+ u8 szEst; /* Estimated size of this column. INT==1 */
	10450	+ u8 colFlags; /* Boolean properties. See COLFLAG_ defines below */
10425	10451	};
10426	10452
10427	10453	/* Allowed values for Column.colFlags:
10428	10454	*/
10429	10455	#define COLFLAG_PRIMKEY 0x0001 /* Column is part of the primary key */
		@@ -10583,10 +10609,11 @@
10583	10609	tRowcnt nRowEst; /* Estimated rows in table - from sqlite_stat1 table */
10584	10610	int tnum; /* Root BTree node for this table (see note above) */
10585	10611	i16 iPKey; /* If not negative, use aCol[iPKey] as the primary key */
10586	10612	i16 nCol; /* Number of columns in this table */
10587	10613	u16 nRef; /* Number of pointers to this Table */
	10614	+ LogEst szTabRow; /* Estimated size of each table row in bytes */
10588	10615	u8 tabFlags; /* Mask of TF_* values */
10589	10616	u8 keyConf; /* What to do in case of uniqueness conflict on iPKey */
10590	10617	#ifndef SQLITE_OMIT_ALTERTABLE
10591	10618	int addColOffset; /* Offset in CREATE TABLE stmt to add a new column */
10592	10619	#endif
		@@ -10694,11 +10721,11 @@
10694	10721	#define OE_Restrict 6 /* OE_Abort for IMMEDIATE, OE_Rollback for DEFERRED */
10695	10722	#define OE_SetNull 7 /* Set the foreign key value to NULL */
10696	10723	#define OE_SetDflt 8 /* Set the foreign key value to its default */
10697	10724	#define OE_Cascade 9 /* Cascade the changes */
10698	10725
10699		-#define OE_Default 99 /* Do whatever the default action is */
	10726	+#define OE_Default 10 /* Do whatever the default action is */
10700	10727
10701	10728
10702	10729	/*
10703	10730	** An instance of the following structure is passed as the first
10704	10731	** argument to sqlite3VdbeKeyCompare and is used to control the
		@@ -10781,10 +10808,11 @@
10781	10808	Schema pSchema; / Schema containing this index */
10782	10809	u8 aSortOrder; / for each column: True==DESC, False==ASC */
10783	10810	char *azColl; / Array of collation sequence names for index */
10784	10811	Expr pPartIdxWhere; / WHERE clause for partial indices */
10785	10812	int tnum; /* DB Page containing root of this index */
	10813	+ LogEst szIdxRow; /* Estimated average row size in bytes */
10786	10814	u16 nColumn; /* Number of columns in table used by this index */
10787	10815	u8 onError; /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */
10788	10816	unsigned autoIndex:2; /* 1==UNIQUE, 2==PRIMARY KEY, 0==CREATE INDEX */
10789	10817	unsigned bUnordered:1; /* Use this index for == or IN queries only */
10790	10818	unsigned uniqNotNull:1; /* True if UNIQUE and NOT NULL for all columns */
		@@ -12187,10 +12215,16 @@
12187	12215	SQLITE_PRIVATE int sqlite3GetInt32(const char , int);
12188	12216	SQLITE_PRIVATE int sqlite3Atoi(const char*);
12189	12217	SQLITE_PRIVATE int sqlite3Utf16ByteLen(const void *pData, int nChar);
12190	12218	SQLITE_PRIVATE int sqlite3Utf8CharLen(const char *pData, int nByte);
12191	12219	SQLITE_PRIVATE u32 sqlite3Utf8Read(const u8**);
	12220	+SQLITE_PRIVATE LogEst sqlite3LogEst(u64);
	12221	+SQLITE_PRIVATE LogEst sqlite3LogEstAdd(LogEst,LogEst);
	12222	+#ifndef SQLITE_OMIT_VIRTUALTABLE
	12223	+SQLITE_PRIVATE LogEst sqlite3LogEstFromDouble(double);
	12224	+#endif
	12225	+SQLITE_PRIVATE u64 sqlite3LogEstToInt(LogEst);
12192	12226
12193	12227	/*
12194	12228	** Routines to read and write variable-length integers. These used to
12195	12229	** be defined locally, but now we use the varint routines in the util.c
12196	12230	** file. Code should use the MACRO forms below, as the Varint32 versions
		@@ -12303,11 +12337,11 @@
12303	12337	SQLITE_PRIVATE int sqlite3ResolveOrderGroupBy(Parse, Select, ExprList, const char);
12304	12338	SQLITE_PRIVATE void sqlite3ColumnDefault(Vdbe , Table , int, int);
12305	12339	SQLITE_PRIVATE void sqlite3AlterFinishAddColumn(Parse , Token );
12306	12340	SQLITE_PRIVATE void sqlite3AlterBeginAddColumn(Parse , SrcList );
12307	12341	SQLITE_PRIVATE CollSeq sqlite3GetCollSeq(Parse, u8, CollSeq , const char);
12308		-SQLITE_PRIVATE char sqlite3AffinityType(const char*);
	12342	+SQLITE_PRIVATE char sqlite3AffinityType(const char, u8);
12309	12343	SQLITE_PRIVATE void sqlite3Analyze(Parse, Token, Token*);
12310	12344	SQLITE_PRIVATE int sqlite3InvokeBusyHandler(BusyHandler*);
12311	12345	SQLITE_PRIVATE int sqlite3FindDb(sqlite3, Token);
12312	12346	SQLITE_PRIVATE int sqlite3FindDbName(sqlite3 , const char );
12313	12347	SQLITE_PRIVATE int sqlite3AnalysisLoad(sqlite3*,int iDB);
		@@ -22388,10 +22422,87 @@
22388	22422	for(i=sz-1; i>0 && z[i]!='/' && z[i]!='.'; i--){}
22389	22423	if( z[i]=='.' && ALWAYS(sz>i+4) ) memmove(&z[i+1], &z[sz-3], 4);
22390	22424	}
22391	22425	}
22392	22426	#endif
	22427	+
	22428	+/*
	22429	+** Find (an approximate) sum of two LogEst values. This computation is
	22430	+** not a simple "+" operator because LogEst is stored as a logarithmic
	22431	+** value.
	22432	+**
	22433	+*/
	22434	+SQLITE_PRIVATE LogEst sqlite3LogEstAdd(LogEst a, LogEst b){
	22435	+ static const unsigned char x[] = {
	22436	+ 10, 10, /* 0,1 */
	22437	+ 9, 9, /* 2,3 */
	22438	+ 8, 8, /* 4,5 */
	22439	+ 7, 7, 7, /* 6,7,8 */
	22440	+ 6, 6, 6, /* 9,10,11 */
	22441	+ 5, 5, 5, /* 12-14 */
	22442	+ 4, 4, 4, 4, /* 15-18 */
	22443	+ 3, 3, 3, 3, 3, 3, /* 19-24 */
	22444	+ 2, 2, 2, 2, 2, 2, 2, /* 25-31 */
	22445	+ };
	22446	+ if( a>=b ){
	22447	+ if( a>b+49 ) return a;
	22448	+ if( a>b+31 ) return a+1;
	22449	+ return a+x[a-b];
	22450	+ }else{
	22451	+ if( b>a+49 ) return b;
	22452	+ if( b>a+31 ) return b+1;
	22453	+ return b+x[b-a];
	22454	+ }
	22455	+}
	22456	+
	22457	+/*
	22458	+** Convert an integer into a LogEst. In other words, compute a
	22459	+** good approximatation for 10*log2(x).
	22460	+*/
	22461	+SQLITE_PRIVATE LogEst sqlite3LogEst(u64 x){
	22462	+ static LogEst a[] = { 0, 2, 3, 5, 6, 7, 8, 9 };
	22463	+ LogEst y = 40;
	22464	+ if( x<8 ){
	22465	+ if( x<2 ) return 0;
	22466	+ while( x<8 ){ y -= 10; x <<= 1; }
	22467	+ }else{
	22468	+ while( x>255 ){ y += 40; x >>= 4; }
	22469	+ while( x>15 ){ y += 10; x >>= 1; }
	22470	+ }
	22471	+ return a[x&7] + y - 10;
	22472	+}
	22473	+
	22474	+#ifndef SQLITE_OMIT_VIRTUALTABLE
	22475	+/*
	22476	+** Convert a double into a LogEst
	22477	+** In other words, compute an approximation for 10*log2(x).
	22478	+*/
	22479	+SQLITE_PRIVATE LogEst sqlite3LogEstFromDouble(double x){
	22480	+ u64 a;
	22481	+ LogEst e;
	22482	+ assert( sizeof(x)==8 && sizeof(a)==8 );
	22483	+ if( x<=1 ) return 0;
	22484	+ if( x<=2000000000 ) return sqlite3LogEst((u64)x);
	22485	+ memcpy(&a, &x, 8);
	22486	+ e = (a>>52) - 1022;
	22487	+ return e*10;
	22488	+}
	22489	+#endif /* SQLITE_OMIT_VIRTUALTABLE */
	22490	+
	22491	+/*
	22492	+** Convert a LogEst into an integer.
	22493	+*/
	22494	+SQLITE_PRIVATE u64 sqlite3LogEstToInt(LogEst x){
	22495	+ u64 n;
	22496	+ if( x<10 ) return 1;
	22497	+ n = x%10;
	22498	+ x /= 10;
	22499	+ if( n>=5 ) n -= 2;
	22500	+ else if( n>=1 ) n -= 1;
	22501	+ if( x>=3 ) return (n+8)<<(x-3);
	22502	+ return (n+8)>>(3-x);
	22503	+}
22393	22504
22394	22505	/************ End of util.c **********************************************/
22395	22506	/************ Begin file hash.c ******************************************/
22396	22507	/*
22397	22508	** 2001 September 22
		@@ -76084,11 +76195,11 @@
76084	76195	return sqlite3ExprAffinity(pExpr->x.pSelect->pEList->a[0].pExpr);
76085	76196	}
76086	76197	#ifndef SQLITE_OMIT_CAST
76087	76198	if( op==TK_CAST ){
76088	76199	assert( !ExprHasProperty(pExpr, EP_IntValue) );
76089		- return sqlite3AffinityType(pExpr->u.zToken);
	76200	+ return sqlite3AffinityType(pExpr->u.zToken, 0);
76090	76201	}
76091	76202	#endif
76092	76203	if( (op==TK_AGG_COLUMN \|\| op==TK_COLUMN \|\| op==TK_REGISTER)
76093	76204	&& pExpr->pTab!=0
76094	76205	){
		@@ -78504,11 +78615,11 @@
78504	78615	case TK_CAST: {
78505	78616	/* Expressions of the form: CAST(pLeft AS token) */
78506	78617	int aff, to_op;
78507	78618	inReg = sqlite3ExprCodeTarget(pParse, pExpr->pLeft, target);
78508	78619	assert( !ExprHasProperty(pExpr, EP_IntValue) );
78509		- aff = sqlite3AffinityType(pExpr->u.zToken);
	78620	+ aff = sqlite3AffinityType(pExpr->u.zToken, 0);
78510	78621	to_op = aff - SQLITE_AFF_TEXT + OP_ToText;
78511	78622	assert( to_op==OP_ToText \|\| aff!=SQLITE_AFF_TEXT );
78512	78623	assert( to_op==OP_ToBlob \|\| aff!=SQLITE_AFF_NONE );
78513	78624	assert( to_op==OP_ToNumeric \|\| aff!=SQLITE_AFF_NUMERIC );
78514	78625	assert( to_op==OP_ToInt \|\| aff!=SQLITE_AFF_INTEGER );
		@@ -79171,11 +79282,11 @@
79171	79282	}
79172	79283	#ifndef SQLITE_OMIT_CAST
79173	79284	case TK_CAST: {
79174	79285	/* Expressions of the form: CAST(pLeft AS token) */
79175	79286	const char *zAff = "unk";
79176		- switch( sqlite3AffinityType(pExpr->u.zToken) ){
	79287	+ switch( sqlite3AffinityType(pExpr->u.zToken, 0) ){
79177	79288	case SQLITE_AFF_TEXT: zAff = "TEXT"; break;
79178	79289	case SQLITE_AFF_NONE: zAff = "NONE"; break;
79179	79290	case SQLITE_AFF_NUMERIC: zAff = "NUMERIC"; break;
79180	79291	case SQLITE_AFF_INTEGER: zAff = "INTEGER"; break;
79181	79292	case SQLITE_AFF_REAL: zAff = "REAL"; break;
		@@ -81886,16 +81997,16 @@
81886	81997	if( zRet==0 ){
81887	81998	sqlite3_result_error_nomem(context);
81888	81999	return;
81889	82000	}
81890	82001
81891		- sqlite3_snprintf(24, zRet, "%lld", p->nRow);
	82002	+ sqlite3_snprintf(24, zRet, "%llu", (u64)p->nRow);
81892	82003	z = zRet + sqlite3Strlen30(zRet);
81893	82004	for(i=0; i<(p->nCol-1); i++){
81894		- i64 nDistinct = p->current.anDLt[i] + 1;
81895		- i64 iVal = (p->nRow + nDistinct - 1) / nDistinct;
81896		- sqlite3_snprintf(24, z, " %lld", iVal);
	82005	+ u64 nDistinct = p->current.anDLt[i] + 1;
	82006	+ u64 iVal = (p->nRow + nDistinct - 1) / nDistinct;
	82007	+ sqlite3_snprintf(24, z, " %llu", iVal);
81897	82008	z += sqlite3Strlen30(z);
81898	82009	assert( p->current.anEq[i] );
81899	82010	}
81900	82011	assert( z[0]=='\0' && z>zRet );
81901	82012
		@@ -81932,11 +82043,11 @@
81932	82043	sqlite3_result_error_nomem(context);
81933	82044	}else{
81934	82045	int i;
81935	82046	char *z = zRet;
81936	82047	for(i=0; i<p->nCol; i++){
81937		- sqlite3_snprintf(24, z, "%lld ", aCnt[i]);
	82048	+ sqlite3_snprintf(24, z, "%llu ", (u64)aCnt[i]);
81938	82049	z += sqlite3Strlen30(z);
81939	82050	}
81940	82051	assert( z[0]=='\0' && z>zRet );
81941	82052	z[-1] = '\0';
81942	82053	sqlite3_result_text(context, zRet, -1, sqlite3_free);
		@@ -82393,22 +82504,20 @@
82393	82504	** The first argument points to a nul-terminated string containing a
82394	82505	** list of space separated integers. Read the first nOut of these into
82395	82506	** the array aOut[].
82396	82507	*/
82397	82508	static void decodeIntArray(
82398		- char *zIntArray,
82399		- int nOut,
82400		- tRowcnt *aOut,
82401		- int *pbUnordered
	82509	+ char zIntArray, / String containing int array to decode */
	82510	+ int nOut, /* Number of slots in aOut[] */
	82511	+ tRowcnt aOut, / Store integers here */
	82512	+ Index pIndex / Handle extra flags for this index, if not NULL */
82402	82513	){
82403	82514	char *z = zIntArray;
82404	82515	int c;
82405	82516	int i;
82406	82517	tRowcnt v;
82407	82518
82408		- assert( pbUnordered==0 \|\| *pbUnordered==0 );
82409		-
82410	82519	#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
82411	82520	if( z==0 ) z = "";
82412	82521	#else
82413	82522	if( NEVER(z==0) ) z = "";
82414	82523	#endif
		@@ -82419,12 +82528,23 @@
82419	82528	z++;
82420	82529	}
82421	82530	aOut[i] = v;
82422	82531	if( *z==' ' ) z++;
82423	82532	}
82424		- if( pbUnordered && strcmp(z, "unordered")==0 ){
82425		- *pbUnordered = 1;
	82533	+#ifndef SQLITE_ENABLE_STAT3_OR_STAT4
	82534	+ assert( pIndex!=0 );
	82535	+#else
	82536	+ if( pIndex )
	82537	+#endif
	82538	+ {
	82539	+ if( strcmp(z, "unordered")==0 ){
	82540	+ pIndex->bUnordered = 1;
	82541	+ }else if( sqlite3_strglob("sz=[0-9]*", z)==0 ){
	82542	+ int v32 = 0;
	82543	+ sqlite3GetInt32(z+3, &v32);
	82544	+ pIndex->szIdxRow = sqlite3LogEst(v32);
	82545	+ }
82426	82546	}
82427	82547	}
82428	82548
82429	82549	/*
82430	82550	** This callback is invoked once for each index when reading the
		@@ -82459,16 +82579,17 @@
82459	82579	pIndex = 0;
82460	82580	}
82461	82581	z = argv[2];
82462	82582
82463	82583	if( pIndex ){
82464		- int bUnordered = 0;
82465		- decodeIntArray((char*)z, pIndex->nColumn+1, pIndex->aiRowEst,&bUnordered);
	82584	+ decodeIntArray((char*)z, pIndex->nColumn+1, pIndex->aiRowEst, pIndex);
82466	82585	if( pIndex->pPartIdxWhere==0 ) pTable->nRowEst = pIndex->aiRowEst[0];
82467		- pIndex->bUnordered = bUnordered;
82468	82586	}else{
82469		- decodeIntArray((char*)z, 1, &pTable->nRowEst, 0);
	82587	+ Index fakeIdx;
	82588	+ fakeIdx.szIdxRow = pTable->szTabRow;
	82589	+ decodeIntArray((char*)z, 1, &pTable->nRowEst, &fakeIdx);
	82590	+ pTable->szTabRow = fakeIdx.szIdxRow;
82470	82591	}
82471	82592
82472	82593	return 0;
82473	82594	}
82474	82595
		@@ -84480,11 +84601,11 @@
84480	84601	}
84481	84602	pTable->zName = zName;
84482	84603	pTable->iPKey = -1;
84483	84604	pTable->pSchema = db->aDb[iDb].pSchema;
84484	84605	pTable->nRef = 1;
84485		- pTable->nRowEst = 1000000;
	84606	+ pTable->nRowEst = 1048576;
84486	84607	assert( pParse->pNewTable==0 );
84487	84608	pParse->pNewTable = pTable;
84488	84609
84489	84610	/* If this is the magic sqlite_sequence table used by autoincrement,
84490	84611	** then record a pointer to this table in the main database structure
		@@ -84627,10 +84748,11 @@
84627	84748	/* If there is no type specified, columns have the default affinity
84628	84749	** 'NONE'. If there is a type specified, then sqlite3AddColumnType() will
84629	84750	** be called next to set pCol->affinity correctly.
84630	84751	*/
84631	84752	pCol->affinity = SQLITE_AFF_NONE;
	84753	+ pCol->szEst = 1;
84632	84754	p->nCol++;
84633	84755	}
84634	84756
84635	84757	/*
84636	84758	** This routine is called by the parser while in the middle of
		@@ -84668,26 +84790,30 @@
84668	84790	** 'DOUB' \| SQLITE_AFF_REAL
84669	84791	**
84670	84792	** If none of the substrings in the above table are found,
84671	84793	** SQLITE_AFF_NUMERIC is returned.
84672	84794	*/
84673		-SQLITE_PRIVATE char sqlite3AffinityType(const char *zIn){
	84795	+SQLITE_PRIVATE char sqlite3AffinityType(const char zIn, u8 pszEst){
84674	84796	u32 h = 0;
84675	84797	char aff = SQLITE_AFF_NUMERIC;
	84798	+ const char *zChar = 0;
84676	84799
84677		- if( zIn ) while( zIn[0] ){
	84800	+ if( zIn==0 ) return aff;
	84801	+ while( zIn[0] ){
84678	84802	h = (h<<8) + sqlite3UpperToLower[(*zIn)&0xff];
84679	84803	zIn++;
84680	84804	if( h==(('c'<<24)+('h'<<16)+('a'<<8)+'r') ){ /* CHAR */
84681		- aff = SQLITE_AFF_TEXT;
	84805	+ aff = SQLITE_AFF_TEXT;
	84806	+ zChar = zIn;
84682	84807	}else if( h==(('c'<<24)+('l'<<16)+('o'<<8)+'b') ){ /* CLOB */
84683	84808	aff = SQLITE_AFF_TEXT;
84684	84809	}else if( h==(('t'<<24)+('e'<<16)+('x'<<8)+'t') ){ /* TEXT */
84685	84810	aff = SQLITE_AFF_TEXT;
84686	84811	}else if( h==(('b'<<24)+('l'<<16)+('o'<<8)+'b') /* BLOB */
84687	84812	&& (aff==SQLITE_AFF_NUMERIC \|\| aff==SQLITE_AFF_REAL) ){
84688	84813	aff = SQLITE_AFF_NONE;
	84814	+ if( zIn[0]=='(' ) zChar = zIn;
84689	84815	#ifndef SQLITE_OMIT_FLOATING_POINT
84690	84816	}else if( h==(('r'<<24)+('e'<<16)+('a'<<8)+'l') /* REAL */
84691	84817	&& aff==SQLITE_AFF_NUMERIC ){
84692	84818	aff = SQLITE_AFF_REAL;
84693	84819	}else if( h==(('f'<<24)+('l'<<16)+('o'<<8)+'a') /* FLOA */
		@@ -84701,10 +84827,32 @@
84701	84827	aff = SQLITE_AFF_INTEGER;
84702	84828	break;
84703	84829	}
84704	84830	}
84705	84831
	84832	+ /* If pszEst is not NULL, store an estimate of the field size. The
	84833	+ ** estimate is scaled so that the size of an integer is 1. */
	84834	+ if( pszEst ){
	84835	+ pszEst = 1; / default size is approx 4 bytes */
	84836	+ if( aff<=SQLITE_AFF_NONE ){
	84837	+ if( zChar ){
	84838	+ while( zChar[0] ){
	84839	+ if( sqlite3Isdigit(zChar[0]) ){
	84840	+ int v;
	84841	+ sqlite3GetInt32(zChar, &v);
	84842	+ v = v/4 + 1;
	84843	+ if( v>255 ) v = 255;
	84844	+ pszEst = v; / BLOB(k), VARCHAR(k), CHAR(k) -> r=(k/4+1) */
	84845	+ break;
	84846	+ }
	84847	+ zChar++;
	84848	+ }
	84849	+ }else{
	84850	+ pszEst = 5; / BLOB, TEXT, CLOB -> r=5 (approx 20 bytes)*/
	84851	+ }
	84852	+ }
	84853	+ }
84706	84854	return aff;
84707	84855	}
84708	84856
84709	84857	/*
84710	84858	** This routine is called by the parser while in the middle of
		@@ -84722,11 +84870,11 @@
84722	84870	p = pParse->pNewTable;
84723	84871	if( p==0 \|\| NEVER(p->nCol<1) ) return;
84724	84872	pCol = &p->aCol[p->nCol-1];
84725	84873	assert( pCol->zType==0 );
84726	84874	pCol->zType = sqlite3NameFromToken(pParse->db, pType);
84727		- pCol->affinity = sqlite3AffinityType(pCol->zType);
	84875	+ pCol->affinity = sqlite3AffinityType(pCol->zType, &pCol->szEst);
84728	84876	}
84729	84877
84730	84878	/*
84731	84879	** The expression is the default value for the most recently added column
84732	84880	** of the table currently under construction.
		@@ -85070,18 +85218,46 @@
85070	85218	testcase( pCol->affinity==SQLITE_AFF_REAL );
85071	85219
85072	85220	zType = azType[pCol->affinity - SQLITE_AFF_TEXT];
85073	85221	len = sqlite3Strlen30(zType);
85074	85222	assert( pCol->affinity==SQLITE_AFF_NONE
85075		- \|\| pCol->affinity==sqlite3AffinityType(zType) );
	85223	+ \|\| pCol->affinity==sqlite3AffinityType(zType, 0) );
85076	85224	memcpy(&zStmt[k], zType, len);
85077	85225	k += len;
85078	85226	assert( k<=n );
85079	85227	}
85080	85228	sqlite3_snprintf(n-k, &zStmt[k], "%s", zEnd);
85081	85229	return zStmt;
85082	85230	}
	85231	+
	85232	+/*
	85233	+** Estimate the total row width for a table.
	85234	+*/
	85235	+static void estimateTableWidth(Table *pTab){
	85236	+ unsigned wTable = 0;
	85237	+ const Column *pTabCol;
	85238	+ int i;
	85239	+ for(i=pTab->nCol, pTabCol=pTab->aCol; i>0; i--, pTabCol++){
	85240	+ wTable += pTabCol->szEst;
	85241	+ }
	85242	+ if( pTab->iPKey<0 ) wTable++;
	85243	+ pTab->szTabRow = sqlite3LogEst(wTable*4);
	85244	+}
	85245	+
	85246	+/*
	85247	+** Estimate the average size of a row for an index.
	85248	+*/
	85249	+static void estimateIndexWidth(Index *pIdx){
	85250	+ unsigned wIndex = 1;
	85251	+ int i;
	85252	+ const Column *aCol = pIdx->pTable->aCol;
	85253	+ for(i=0; i<pIdx->nColumn; i++){
	85254	+ assert( pIdx->aiColumn[i]>=0 && pIdx->aiColumn[i]<pIdx->pTable->nCol );
	85255	+ wIndex += aCol[pIdx->aiColumn[i]].szEst;
	85256	+ }
	85257	+ pIdx->szIdxRow = sqlite3LogEst(wIndex*4);
	85258	+}
85083	85259
85084	85260	/*
85085	85261	** This routine is called to report the final ")" that terminates
85086	85262	** a CREATE TABLE statement.
85087	85263	**
		@@ -85105,13 +85281,14 @@
85105	85281	Parse pParse, / Parse context */
85106	85282	Token pCons, / The ',' token after the last column defn. */
85107	85283	Token pEnd, / The final ')' token in the CREATE TABLE */
85108	85284	Select pSelect / Select from a "CREATE ... AS SELECT" */
85109	85285	){
85110		- Table *p;
85111		- sqlite3 *db = pParse->db;
85112		- int iDb;
	85286	+ Table p; / The new table */
	85287	+ sqlite3 db = pParse->db; / The database connection */
	85288	+ int iDb; /* Database in which the table lives */
	85289	+ Index pIdx; / An implied index of the table */
85113	85290
85114	85291	if( (pEnd==0 && pSelect==0) \|\| db->mallocFailed ){
85115	85292	return;
85116	85293	}
85117	85294	p = pParse->pNewTable;
		@@ -85126,10 +85303,16 @@
85126	85303	*/
85127	85304	if( p->pCheck ){
85128	85305	sqlite3ResolveSelfReference(pParse, p, NC_IsCheck, 0, p->pCheck);
85129	85306	}
85130	85307	#endif /* !defined(SQLITE_OMIT_CHECK) */
	85308	+
	85309	+ /* Estimate the average row size for the table and for all implied indices */
	85310	+ estimateTableWidth(p);
	85311	+ for(pIdx=p->pIndex; pIdx; pIdx=pIdx->pNext){
	85312	+ estimateIndexWidth(pIdx);
	85313	+ }
85131	85314
85132	85315	/* If the db->init.busy is 1 it means we are reading the SQL off the
85133	85316	** "sqlite_master" or "sqlite_temp_master" table on the disk.
85134	85317	** So do not write to the disk again. Extract the root page number
85135	85318	** for the table from the db->init.newTnum field. (The page number
		@@ -86085,13 +86268,14 @@
86085	86268	sqlite3 *db = pParse->db;
86086	86269	Db pDb; / The specific table containing the indexed database */
86087	86270	int iDb; /* Index of the database that is being written */
86088	86271	Token pName = 0; / Unqualified name of the index to create */
86089	86272	struct ExprList_item pListItem; / For looping over pList */
86090		- int nCol;
86091		- int nExtra = 0;
86092		- char *zExtra;
	86273	+ const Column pTabCol; / A column in the table */
	86274	+ int nCol; /* Number of columns */
	86275	+ int nExtra = 0; /* Space allocated for zExtra[] */
	86276	+ char zExtra; / Extra space after the Index object */
86093	86277
86094	86278	assert( pParse->nErr==0 ); /* Never called with prior errors */
86095	86279	if( db->mallocFailed \|\| IN_DECLARE_VTAB ){
86096	86280	goto exit_create_index;
86097	86281	}
		@@ -86314,11 +86498,10 @@
86314	86498	** same column more than once cannot be an error because that would
86315	86499	** break backwards compatibility - it needs to be a warning.
86316	86500	*/
86317	86501	for(i=0, pListItem=pList->a; i<pList->nExpr; i++, pListItem++){
86318	86502	const char *zColName = pListItem->zName;
86319		- Column *pTabCol;
86320	86503	int requestedSortOrder;
86321	86504	char zColl; / Collation sequence name */
86322	86505
86323	86506	for(j=0, pTabCol=pTab->aCol; j<pTab->nCol; j++, pTabCol++){
86324	86507	if( sqlite3StrICmp(zColName, pTabCol->zName)==0 ) break;
		@@ -86351,10 +86534,11 @@
86351	86534	requestedSortOrder = pListItem->sortOrder & sortOrderMask;
86352	86535	pIndex->aSortOrder[i] = (u8)requestedSortOrder;
86353	86536	if( pTab->aCol[j].notNull==0 ) pIndex->uniqNotNull = 0;
86354	86537	}
86355	86538	sqlite3DefaultRowEst(pIndex);
	86539	+ if( pParse->pNewTable==0 ) estimateIndexWidth(pIndex);
86356	86540
86357	86541	if( pTab==pParse->pNewTable ){
86358	86542	/* This routine has been called to create an automatic index as a
86359	86543	** result of a PRIMARY KEY or UNIQUE clause on a column definition, or
86360	86544	** a PRIMARY KEY or UNIQUE clause following the column definitions.
		@@ -96379,30 +96563,34 @@
96379	96563	break;
96380	96564
96381	96565	case PragTyp_INDEX_LIST: if( zRight ){
96382	96566	Index *pIdx;
96383	96567	Table *pTab;
	96568	+ int i;
96384	96569	pTab = sqlite3FindTable(db, zRight, zDb);
96385	96570	if( pTab ){
96386	96571	v = sqlite3GetVdbe(pParse);
96387		- pIdx = pTab->pIndex;
96388		- if( pIdx ){
96389		- int i = 0;
96390		- sqlite3VdbeSetNumCols(v, 3);
96391		- pParse->nMem = 3;
96392		- sqlite3CodeVerifySchema(pParse, iDb);
96393		- sqlite3VdbeSetColName(v, 0, COLNAME_NAME, "seq", SQLITE_STATIC);
96394		- sqlite3VdbeSetColName(v, 1, COLNAME_NAME, "name", SQLITE_STATIC);
96395		- sqlite3VdbeSetColName(v, 2, COLNAME_NAME, "unique", SQLITE_STATIC);
96396		- while(pIdx){
96397		- sqlite3VdbeAddOp2(v, OP_Integer, i, 1);
96398		- sqlite3VdbeAddOp4(v, OP_String8, 0, 2, 0, pIdx->zName, 0);
96399		- sqlite3VdbeAddOp2(v, OP_Integer, pIdx->onError!=OE_None, 3);
96400		- sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 3);
96401		- ++i;
96402		- pIdx = pIdx->pNext;
96403		- }
	96572	+ sqlite3VdbeSetNumCols(v, 4);
	96573	+ pParse->nMem = 4;
	96574	+ sqlite3CodeVerifySchema(pParse, iDb);
	96575	+ sqlite3VdbeSetColName(v, 0, COLNAME_NAME, "seq", SQLITE_STATIC);
	96576	+ sqlite3VdbeSetColName(v, 1, COLNAME_NAME, "name", SQLITE_STATIC);
	96577	+ sqlite3VdbeSetColName(v, 2, COLNAME_NAME, "unique", SQLITE_STATIC);
	96578	+ sqlite3VdbeSetColName(v, 3, COLNAME_NAME, "avgrowsize", SQLITE_STATIC);
	96579	+ sqlite3VdbeAddOp2(v, OP_Integer, 0, 1);
	96580	+ sqlite3VdbeAddOp2(v, OP_Null, 0, 2);
	96581	+ sqlite3VdbeAddOp2(v, OP_Integer, 1, 3);
	96582	+ sqlite3VdbeAddOp2(v, OP_Integer,
	96583	+ (int)sqlite3LogEstToInt(pTab->szTabRow), 4);
	96584	+ sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 4);
	96585	+ for(pIdx=pTab->pIndex, i=1; pIdx; pIdx=pIdx->pNext, i++){
	96586	+ sqlite3VdbeAddOp2(v, OP_Integer, i, 1);
	96587	+ sqlite3VdbeAddOp4(v, OP_String8, 0, 2, 0, pIdx->zName, 0);
	96588	+ sqlite3VdbeAddOp2(v, OP_Integer, pIdx->onError!=OE_None, 3);
	96589	+ sqlite3VdbeAddOp2(v, OP_Integer,
	96590	+ (int)sqlite3LogEstToInt(pIdx->szIdxRow), 4);
	96591	+ sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 4);
96404	96592	}
96405	96593	}
96406	96594	}
96407	96595	break;
96408	96596
		@@ -99086,10 +99274,13 @@
99086	99274	}
99087	99275
99088	99276	/*
99089	99277	** Return a pointer to a string containing the 'declaration type' of the
99090	99278	** expression pExpr. The string may be treated as static by the caller.
	99279	+**
	99280	+** Also try to estimate the size of the returned value and return that
	99281	+** result in *pEstWidth.
99091	99282	**
99092	99283	** The declaration type is the exact datatype definition extracted from the
99093	99284	** original CREATE TABLE statement if the expression is a column. The
99094	99285	** declaration type for a ROWID field is INTEGER. Exactly when an expression
99095	99286	** is considered a column can be complex in the presence of subqueries. The
		@@ -99100,25 +99291,40 @@
99100	99291	** SELECT (SELECT col FROM tbl;
99101	99292	** SELECT (SELECT col FROM tbl);
99102	99293	** SELECT abc FROM (SELECT col AS abc FROM tbl);
99103	99294	**
99104	99295	** The declaration type for any expression other than a column is NULL.
	99296	+**
	99297	+** This routine has either 3 or 6 parameters depending on whether or not
	99298	+** the SQLITE_ENABLE_COLUMN_METADATA compile-time option is used.
99105	99299	*/
99106		-static const char *columnType(
	99300	+#ifdef SQLITE_ENABLE_COLUMN_METADATA
	99301	+# define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,C,D,E,F)
	99302	+static const char *columnTypeImpl(
	99303	+ NameContext *pNC,
	99304	+ Expr *pExpr,
	99305	+ const char **pzOrigDb,
	99306	+ const char **pzOrigTab,
	99307	+ const char **pzOrigCol,
	99308	+ u8 *pEstWidth
	99309	+){
	99310	+ char const *zOrigDb = 0;
	99311	+ char const *zOrigTab = 0;
	99312	+ char const *zOrigCol = 0;
	99313	+#else /* if !defined(SQLITE_ENABLE_COLUMN_METADATA) */
	99314	+# define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,F)
	99315	+static const char *columnTypeImpl(
99107	99316	NameContext *pNC,
99108	99317	Expr *pExpr,
99109		- const char **pzOriginDb,
99110		- const char **pzOriginTab,
99111		- const char **pzOriginCol
	99318	+ u8 *pEstWidth
99112	99319	){
	99320	+#endif /* !defined(SQLITE_ENABLE_COLUMN_METADATA) */
99113	99321	char const *zType = 0;
99114		- char const *zOriginDb = 0;
99115		- char const *zOriginTab = 0;
99116		- char const *zOriginCol = 0;
99117	99322	int j;
	99323	+ u8 estWidth = 1;
	99324	+
99118	99325	if( NEVER(pExpr==0) \|\| pNC->pSrcList==0 ) return 0;
99119		-
99120	99326	switch( pExpr->op ){
99121	99327	case TK_AGG_COLUMN:
99122	99328	case TK_COLUMN: {
99123	99329	/* The expression is a column. Locate the table the column is being
99124	99330	** extracted from in NameContext.pSrcList. This table may be real
		@@ -99175,29 +99381,39 @@
99175	99381	NameContext sNC;
99176	99382	Expr *p = pS->pEList->a[iCol].pExpr;
99177	99383	sNC.pSrcList = pS->pSrc;
99178	99384	sNC.pNext = pNC;
99179	99385	sNC.pParse = pNC->pParse;
99180		- zType = columnType(&sNC, p, &zOriginDb, &zOriginTab, &zOriginCol);
	99386	+ zType = columnType(&sNC, p,&zOrigDb,&zOrigTab,&zOrigCol, &estWidth);
99181	99387	}
99182	99388	}else if( ALWAYS(pTab->pSchema) ){
99183	99389	/* A real table */
99184	99390	assert( !pS );
99185	99391	if( iCol<0 ) iCol = pTab->iPKey;
99186	99392	assert( iCol==-1 \|\| (iCol>=0 && iCol<pTab->nCol) );
	99393	+#ifdef SQLITE_ENABLE_COLUMN_METADATA
99187	99394	if( iCol<0 ){
99188	99395	zType = "INTEGER";
99189		- zOriginCol = "rowid";
	99396	+ zOrigCol = "rowid";
99190	99397	}else{
99191	99398	zType = pTab->aCol[iCol].zType;
99192		- zOriginCol = pTab->aCol[iCol].zName;
	99399	+ zOrigCol = pTab->aCol[iCol].zName;
	99400	+ estWidth = pTab->aCol[iCol].szEst;
99193	99401	}
99194		- zOriginTab = pTab->zName;
	99402	+ zOrigTab = pTab->zName;
99195	99403	if( pNC->pParse ){
99196	99404	int iDb = sqlite3SchemaToIndex(pNC->pParse->db, pTab->pSchema);
99197		- zOriginDb = pNC->pParse->db->aDb[iDb].zName;
	99405	+ zOrigDb = pNC->pParse->db->aDb[iDb].zName;
99198	99406	}
	99407	+#else
	99408	+ if( iCol<0 ){
	99409	+ zType = "INTEGER";
	99410	+ }else{
	99411	+ zType = pTab->aCol[iCol].zType;
	99412	+ estWidth = pTab->aCol[iCol].szEst;
	99413	+ }
	99414	+#endif
99199	99415	}
99200	99416	break;
99201	99417	}
99202	99418	#ifndef SQLITE_OMIT_SUBQUERY
99203	99419	case TK_SELECT: {
		@@ -99210,22 +99426,25 @@
99210	99426	Expr *p = pS->pEList->a[0].pExpr;
99211	99427	assert( ExprHasProperty(pExpr, EP_xIsSelect) );
99212	99428	sNC.pSrcList = pS->pSrc;
99213	99429	sNC.pNext = pNC;
99214	99430	sNC.pParse = pNC->pParse;
99215		- zType = columnType(&sNC, p, &zOriginDb, &zOriginTab, &zOriginCol);
	99431	+ zType = columnType(&sNC, p, &zOrigDb, &zOrigTab, &zOrigCol, &estWidth);
99216	99432	break;
99217	99433	}
99218	99434	#endif
99219	99435	}
99220		-
99221		- if( pzOriginDb ){
99222		- assert( pzOriginTab && pzOriginCol );
99223		- *pzOriginDb = zOriginDb;
99224		- *pzOriginTab = zOriginTab;
99225		- *pzOriginCol = zOriginCol;
	99436	+
	99437	+#ifdef SQLITE_ENABLE_COLUMN_METADATA
	99438	+ if( pzOrigDb ){
	99439	+ assert( pzOrigTab && pzOrigCol );
	99440	+ *pzOrigDb = zOrigDb;
	99441	+ *pzOrigTab = zOrigTab;
	99442	+ *pzOrigCol = zOrigCol;
99226	99443	}
	99444	+#endif
	99445	+ if( pEstWidth ) *pEstWidth = estWidth;
99227	99446	return zType;
99228	99447	}
99229	99448
99230	99449	/*
99231	99450	** Generate code that will tell the VDBE the declaration types of columns
		@@ -99247,25 +99466,25 @@
99247	99466	const char *zType;
99248	99467	#ifdef SQLITE_ENABLE_COLUMN_METADATA
99249	99468	const char *zOrigDb = 0;
99250	99469	const char *zOrigTab = 0;
99251	99470	const char *zOrigCol = 0;
99252		- zType = columnType(&sNC, p, &zOrigDb, &zOrigTab, &zOrigCol);
	99471	+ zType = columnType(&sNC, p, &zOrigDb, &zOrigTab, &zOrigCol, 0);
99253	99472
99254	99473	/* The vdbe must make its own copy of the column-type and other
99255	99474	** column specific strings, in case the schema is reset before this
99256	99475	** virtual machine is deleted.
99257	99476	*/
99258	99477	sqlite3VdbeSetColName(v, i, COLNAME_DATABASE, zOrigDb, SQLITE_TRANSIENT);
99259	99478	sqlite3VdbeSetColName(v, i, COLNAME_TABLE, zOrigTab, SQLITE_TRANSIENT);
99260	99479	sqlite3VdbeSetColName(v, i, COLNAME_COLUMN, zOrigCol, SQLITE_TRANSIENT);
99261	99480	#else
99262		- zType = columnType(&sNC, p, 0, 0, 0);
	99481	+ zType = columnType(&sNC, p, 0, 0, 0, 0);
99263	99482	#endif
99264	99483	sqlite3VdbeSetColName(v, i, COLNAME_DECLTYPE, zType, SQLITE_TRANSIENT);
99265	99484	}
99266		-#endif /* SQLITE_OMIT_DECLTYPE */
	99485	+#endif /* !defined(SQLITE_OMIT_DECLTYPE) */
99267	99486	}
99268	99487
99269	99488	/*
99270	99489	** Generate code that will tell the VDBE the names of columns
99271	99490	** in the result set. This information is used to provide the
		@@ -99450,39 +99669,41 @@
99450	99669	** This routine requires that all identifiers in the SELECT
99451	99670	** statement be resolved.
99452	99671	*/
99453	99672	static void selectAddColumnTypeAndCollation(
99454	99673	Parse pParse, / Parsing contexts */
99455		- int nCol, /* Number of columns */
99456		- Column aCol, / List of columns */
	99674	+ Table pTab, / Add column type information to this table */
99457	99675	Select pSelect / SELECT used to determine types and collations */
99458	99676	){
99459	99677	sqlite3 *db = pParse->db;
99460	99678	NameContext sNC;
99461	99679	Column *pCol;
99462	99680	CollSeq *pColl;
99463	99681	int i;
99464	99682	Expr *p;
99465	99683	struct ExprList_item *a;
	99684	+ u64 szAll = 0;
99466	99685
99467	99686	assert( pSelect!=0 );
99468	99687	assert( (pSelect->selFlags & SF_Resolved)!=0 );
99469		- assert( nCol==pSelect->pEList->nExpr \|\| db->mallocFailed );
	99688	+ assert( pTab->nCol==pSelect->pEList->nExpr \|\| db->mallocFailed );
99470	99689	if( db->mallocFailed ) return;
99471	99690	memset(&sNC, 0, sizeof(sNC));
99472	99691	sNC.pSrcList = pSelect->pSrc;
99473	99692	a = pSelect->pEList->a;
99474		- for(i=0, pCol=aCol; i<nCol; i++, pCol++){
	99693	+ for(i=0, pCol=pTab->aCol; i<pTab->nCol; i++, pCol++){
99475	99694	p = a[i].pExpr;
99476		- pCol->zType = sqlite3DbStrDup(db, columnType(&sNC, p, 0, 0, 0));
	99695	+ pCol->zType = sqlite3DbStrDup(db, columnType(&sNC, p,0,0,0, &pCol->szEst));
	99696	+ szAll += pCol->szEst;
99477	99697	pCol->affinity = sqlite3ExprAffinity(p);
99478	99698	if( pCol->affinity==0 ) pCol->affinity = SQLITE_AFF_NONE;
99479	99699	pColl = sqlite3ExprCollSeq(pParse, p);
99480	99700	if( pColl ){
99481	99701	pCol->zColl = sqlite3DbStrDup(db, pColl->zName);
99482	99702	}
99483	99703	}
	99704	+ pTab->szTabRow = sqlite3LogEst(szAll*4);
99484	99705	}
99485	99706
99486	99707	/*
99487	99708	** Given a SELECT statement, generate a Table structure that describes
99488	99709	** the result set of that SELECT.
		@@ -99506,13 +99727,13 @@
99506	99727	/* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside
99507	99728	** is disabled */
99508	99729	assert( db->lookaside.bEnabled==0 );
99509	99730	pTab->nRef = 1;
99510	99731	pTab->zName = 0;
99511		- pTab->nRowEst = 1000000;
	99732	+ pTab->nRowEst = 1048576;
99512	99733	selectColumnsFromExprList(pParse, pSelect->pEList, &pTab->nCol, &pTab->aCol);
99513		- selectAddColumnTypeAndCollation(pParse, pTab->nCol, pTab->aCol, pSelect);
	99734	+ selectAddColumnTypeAndCollation(pParse, pTab, pSelect);
99514	99735	pTab->iPKey = -1;
99515	99736	if( db->mallocFailed ){
99516	99737	sqlite3DeleteTable(db, pTab);
99517	99738	return 0;
99518	99739	}
		@@ -101420,15 +101641,15 @@
101420	101641	assert( pFrom->pTab==0 );
101421	101642	sqlite3WalkSelect(pWalker, pSel);
101422	101643	pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));
101423	101644	if( pTab==0 ) return WRC_Abort;
101424	101645	pTab->nRef = 1;
101425		- pTab->zName = sqlite3MPrintf(db, "sqlite_subquery_%p_", (void*)pTab);
	101646	+ pTab->zName = sqlite3MPrintf(db, "sqlite_sq_%p", (void*)pTab);
101426	101647	while( pSel->pPrior ){ pSel = pSel->pPrior; }
101427	101648	selectColumnsFromExprList(pParse, pSel->pEList, &pTab->nCol, &pTab->aCol);
101428	101649	pTab->iPKey = -1;
101429		- pTab->nRowEst = 1000000;
	101650	+ pTab->nRowEst = 1048576;
101430	101651	pTab->tabFlags \|= TF_Ephemeral;
101431	101652	#endif
101432	101653	}else{
101433	101654	/* An ordinary table or view name in the FROM clause */
101434	101655	assert( pFrom->pTab==0 );
		@@ -101708,11 +101929,11 @@
101708	101929	if( ALWAYS(pTab!=0) && (pTab->tabFlags & TF_Ephemeral)!=0 ){
101709	101930	/* A sub-query in the FROM clause of a SELECT */
101710	101931	Select *pSel = pFrom->pSelect;
101711	101932	assert( pSel );
101712	101933	while( pSel->pPrior ) pSel = pSel->pPrior;
101713		- selectAddColumnTypeAndCollation(pParse, pTab->nCol, pTab->aCol, pSel);
	101934	+ selectAddColumnTypeAndCollation(pParse, pTab, pSel);
101714	101935	}
101715	101936	}
101716	101937	}
101717	101938	return WRC_Continue;
101718	101939	}
		@@ -102623,17 +102844,11 @@
102623	102844	int iRoot = pTab->tnum; /* Root page of scanned b-tree */
102624	102845
102625	102846	sqlite3CodeVerifySchema(pParse, iDb);
102626	102847	sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
102627	102848
102628		- /* Search for the index that has the least amount of columns. If
102629		- ** there is such an index, and it has less columns than the table
102630		- ** does, then we can assume that it consumes less space on disk and
102631		- ** will therefore be cheaper to scan to determine the query result.
102632		- ** In this case set iRoot to the root page number of the index b-tree
102633		- ** and pKeyInfo to the KeyInfo structure required to navigate the
102634		- ** index.
	102849	+ /* Search for the index that has the lowest scan cost.
102635	102850	**
102636	102851	** (2011-04-15) Do not do a full scan of an unordered index.
102637	102852	**
102638	102853	** (2013-10-03) Do not count the entires in a partial index.
102639	102854	**
		@@ -102640,17 +102855,18 @@
102640	102855	** In practice the KeyInfo structure will not be used. It is only
102641	102856	** passed to keep OP_OpenRead happy.
102642	102857	*/
102643	102858	for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
102644	102859	if( pIdx->bUnordered==0
	102860	+ && pIdx->szIdxRow<pTab->szTabRow
102645	102861	&& pIdx->pPartIdxWhere==0
102646		- && (!pBest \|\| pIdx->nColumn<pBest->nColumn)
	102862	+ && (!pBest \|\| pIdx->szIdxRow<pBest->szIdxRow)
102647	102863	){
102648	102864	pBest = pIdx;
102649	102865	}
102650	102866	}
102651		- if( pBest && pBest->nColumn<pTab->nCol ){
	102867	+ if( pBest ){
102652	102868	iRoot = pBest->tnum;
102653	102869	pKeyInfo = sqlite3IndexKeyinfo(pParse, pBest);
102654	102870	}
102655	102871
102656	102872	/* Open a read-only cursor, execute the OP_Count, close the cursor. */
		@@ -106406,30 +106622,10 @@
106406	106622	typedef struct WhereLoopBuilder WhereLoopBuilder;
106407	106623	typedef struct WhereScan WhereScan;
106408	106624	typedef struct WhereOrCost WhereOrCost;
106409	106625	typedef struct WhereOrSet WhereOrSet;
106410	106626
106411		-/*
106412		-** Cost X is tracked as 10*log2(X) stored in a 16-bit integer. The
106413		-** maximum cost for ordinary tables is 64(2*63) which becomes 6900.
106414		-** (Virtual tables can return a larger cost, but let's assume they do not.)
106415		-** So all costs can be stored in a 16-bit integer without risk
106416		-** of overflow.
106417		-**
106418		-** Costs are estimates, so no effort is made to compute 10*log2(X) exactly.
106419		-** Instead, a close estimate is used. Any value of X=1 is stored as 0.
106420		-** X=2 is 10. X=3 is 16. X=1000 is 99. etc. Negative values are allowed.
106421		-** A WhereCost of -10 means 0.5. WhereCost of -20 means 0.25. And so forth.
106422		-**
106423		-** The tool/wherecosttest.c source file implements a command-line program
106424		-** that will convert WhereCosts to integers, convert integers to WhereCosts
106425		-** and do addition and multiplication on WhereCost values. The wherecosttest
106426		-** command-line program is a useful utility to have around when working with
106427		-** this module.
106428		-*/
106429		-typedef short int WhereCost;
106430		-
106431	106627	/*
106432	106628	** This object contains information needed to implement a single nested
106433	106629	** loop in WHERE clause.
106434	106630	**
106435	106631	** Contrast this object with WhereLoop. This object describes the
		@@ -106490,13 +106686,13 @@
106490	106686	#ifdef SQLITE_DEBUG
106491	106687	char cId; /* Symbolic ID of this loop for debugging use */
106492	106688	#endif
106493	106689	u8 iTab; /* Position in FROM clause of table for this loop */
106494	106690	u8 iSortIdx; /* Sorting index number. 0==None */
106495		- WhereCost rSetup; /* One-time setup cost (ex: create transient index) */
106496		- WhereCost rRun; /* Cost of running each loop */
106497		- WhereCost nOut; /* Estimated number of output rows */
	106691	+ LogEst rSetup; /* One-time setup cost (ex: create transient index) */
	106692	+ LogEst rRun; /* Cost of running each loop */
	106693	+ LogEst nOut; /* Estimated number of output rows */
106498	106694	union {
106499	106695	struct { /* Information for internal btree tables */
106500	106696	int nEq; /* Number of equality constraints */
106501	106697	Index pIndex; / Index used, or NULL */
106502	106698	} btree;
		@@ -106522,12 +106718,12 @@
106522	106718	** subquery on one operand of an OR operator in the WHERE clause.
106523	106719	** See WhereOrSet for additional information
106524	106720	*/
106525	106721	struct WhereOrCost {
106526	106722	Bitmask prereq; /* Prerequisites */
106527		- WhereCost rRun; /* Cost of running this subquery */
106528		- WhereCost nOut; /* Number of outputs for this subquery */
	106723	+ LogEst rRun; /* Cost of running this subquery */
	106724	+ LogEst nOut; /* Number of outputs for this subquery */
106529	106725	};
106530	106726
106531	106727	/* The WhereOrSet object holds a set of possible WhereOrCosts that
106532	106728	** correspond to the subquery(s) of OR-clause processing. Only the
106533	106729	** best N_OR_COST elements are retained.
		@@ -106561,12 +106757,12 @@
106561	106757	** at the end is the choosen query plan.
106562	106758	*/
106563	106759	struct WherePath {
106564	106760	Bitmask maskLoop; /* Bitmask of all WhereLoop objects in this path */
106565	106761	Bitmask revLoop; /* aLoop[]s that should be reversed for ORDER BY */
106566		- WhereCost nRow; /* Estimated number of rows generated by this path */
106567		- WhereCost rCost; /* Total cost of this path */
	106762	+ LogEst nRow; /* Estimated number of rows generated by this path */
	106763	+ LogEst rCost; /* Total cost of this path */
106568	106764	u8 isOrdered; /* True if this path satisfies ORDER BY */
106569	106765	u8 isOrderedValid; /* True if the isOrdered field is valid */
106570	106766	WhereLoop *aLoop; / Array of WhereLoop objects implementing this path */
106571	106767	};
106572	106768
		@@ -106628,11 +106824,11 @@
106628	106824	union {
106629	106825	int leftColumn; /* Column number of X in "X <op> <expr>" */
106630	106826	WhereOrInfo pOrInfo; / Extra information if (eOperator & WO_OR)!=0 */
106631	106827	WhereAndInfo pAndInfo; / Extra information if (eOperator& WO_AND)!=0 */
106632	106828	} u;
106633		- WhereCost truthProb; /* Probability of truth for this expression */
	106829	+ LogEst truthProb; /* Probability of truth for this expression */
106634	106830	u16 eOperator; /* A WO_xx value describing <op> */
106635	106831	u8 wtFlags; /* TERM_xxx bit flags. See below */
106636	106832	u8 nChild; /* Number of children that must disable us */
106637	106833	WhereClause pWC; / The clause this term is part of */
106638	106834	Bitmask prereqRight; /* Bitmask of tables used by pExpr->pRight */
		@@ -106776,11 +106972,11 @@
106776	106972	SrcList pTabList; / List of tables in the join */
106777	106973	ExprList pOrderBy; / The ORDER BY clause or NULL */
106778	106974	ExprList pResultSet; / Result set. DISTINCT operates on these */
106779	106975	WhereLoop pLoops; / List of all WhereLoop objects */
106780	106976	Bitmask revMask; /* Mask of ORDER BY terms that need reversing */
106781		- WhereCost nRowOut; /* Estimated number of output rows */
	106977	+ LogEst nRowOut; /* Estimated number of output rows */
106782	106978	u16 wctrlFlags; /* Flags originally passed to sqlite3WhereBegin() */
106783	106979	u8 bOBSat; /* ORDER BY satisfied by indices */
106784	106980	u8 okOnePass; /* Ok to use one-pass algorithm for UPDATE/DELETE */
106785	106981	u8 untestedTerms; /* Not all WHERE terms resolved by outer loop */
106786	106982	u8 eDistinct; /* One of the WHERE_DISTINCT_* values below */
		@@ -106836,30 +107032,15 @@
106836	107032	#define WHERE_IN_ABLE 0x00000800 /* Able to support an IN operator */
106837	107033	#define WHERE_ONEROW 0x00001000 /* Selects no more than one row */
106838	107034	#define WHERE_MULTI_OR 0x00002000 /* OR using multiple indices */
106839	107035	#define WHERE_AUTO_INDEX 0x00004000 /* Uses an ephemeral index */
106840	107036
106841		-
106842		-/* Convert a WhereCost value (10 times log2(X)) into its integer value X.
106843		-** A rough approximation is used. The value returned is not exact.
106844		-*/
106845		-static u64 whereCostToInt(WhereCost x){
106846		- u64 n;
106847		- if( x<10 ) return 1;
106848		- n = x%10;
106849		- x /= 10;
106850		- if( n>=5 ) n -= 2;
106851		- else if( n>=1 ) n -= 1;
106852		- if( x>=3 ) return (n+8)<<(x-3);
106853		- return (n+8)>>(3-x);
106854		-}
106855		-
106856	107037	/*
106857	107038	** Return the estimated number of output rows from a WHERE clause
106858	107039	*/
106859	107040	SQLITE_PRIVATE u64 sqlite3WhereOutputRowCount(WhereInfo *pWInfo){
106860		- return whereCostToInt(pWInfo->nRowOut);
	107041	+ return sqlite3LogEstToInt(pWInfo->nRowOut);
106861	107042	}
106862	107043
106863	107044	/*
106864	107045	** Return one of the WHERE_DISTINCT_xxxxx values to indicate how this
106865	107046	** WHERE clause returns outputs for DISTINCT processing.
		@@ -106917,12 +107098,12 @@
106917	107098	** so that pSet keeps the N_OR_COST best entries seen so far.
106918	107099	*/
106919	107100	static int whereOrInsert(
106920	107101	WhereOrSet pSet, / The WhereOrSet to be updated */
106921	107102	Bitmask prereq, /* Prerequisites of the new entry */
106922		- WhereCost rRun, /* Run-cost of the new entry */
106923		- WhereCost nOut /* Number of outputs for the new entry */
	107103	+ LogEst rRun, /* Run-cost of the new entry */
	107104	+ LogEst nOut /* Number of outputs for the new entry */
106924	107105	){
106925	107106	u16 i;
106926	107107	WhereOrCost *p;
106927	107108	for(i=pSet->n, p=pSet->a; i>0; i--, p++){
106928	107109	if( rRun<=p->rRun && (prereq & p->prereq)==prereq ){
		@@ -107003,13 +107184,10 @@
107003	107184	if( pWC->a!=pWC->aStatic ){
107004	107185	sqlite3DbFree(db, pWC->a);
107005	107186	}
107006	107187	}
107007	107188
107008		-/* Forward declaration */
107009		-static WhereCost whereCost(tRowcnt x);
107010		-
107011	107189	/*
107012	107190	** Add a single new WhereTerm entry to the WhereClause object pWC.
107013	107191	** The new WhereTerm object is constructed from Expr p and with wtFlags.
107014	107192	** The index in pWC->a[] of the new WhereTerm is returned on success.
107015	107193	** 0 is returned if the new WhereTerm could not be added due to a memory
		@@ -107048,11 +107226,11 @@
107048	107226	}
107049	107227	pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
107050	107228	}
107051	107229	pTerm = &pWC->a[idx = pWC->nTerm++];
107052	107230	if( p && ExprHasProperty(p, EP_Unlikely) ){
107053		- pTerm->truthProb = whereCost(p->iTable) - 99;
	107231	+ pTerm->truthProb = sqlite3LogEst(p->iTable) - 99;
107054	107232	}else{
107055	107233	pTerm->truthProb = -1;
107056	107234	}
107057	107235	pTerm->pExpr = sqlite3ExprSkipCollate(p);
107058	107236	pTerm->wtFlags = wtFlags;
		@@ -108312,79 +108490,16 @@
108312	108490	}
108313	108491
108314	108492	return 0;
108315	108493	}
108316	108494
108317		-/*
108318		-** Find (an approximate) sum of two WhereCosts. This computation is
108319		-** not a simple "+" operator because WhereCost is stored as a logarithmic
108320		-** value.
108321		-**
108322		-*/
108323		-static WhereCost whereCostAdd(WhereCost a, WhereCost b){
108324		- static const unsigned char x[] = {
108325		- 10, 10, /* 0,1 */
108326		- 9, 9, /* 2,3 */
108327		- 8, 8, /* 4,5 */
108328		- 7, 7, 7, /* 6,7,8 */
108329		- 6, 6, 6, /* 9,10,11 */
108330		- 5, 5, 5, /* 12-14 */
108331		- 4, 4, 4, 4, /* 15-18 */
108332		- 3, 3, 3, 3, 3, 3, /* 19-24 */
108333		- 2, 2, 2, 2, 2, 2, 2, /* 25-31 */
108334		- };
108335		- if( a>=b ){
108336		- if( a>b+49 ) return a;
108337		- if( a>b+31 ) return a+1;
108338		- return a+x[a-b];
108339		- }else{
108340		- if( b>a+49 ) return b;
108341		- if( b>a+31 ) return b+1;
108342		- return b+x[b-a];
108343		- }
108344		-}
108345		-
108346		-/*
108347		-** Convert an integer into a WhereCost. In other words, compute a
108348		-** good approximatation for 10*log2(x).
108349		-*/
108350		-static WhereCost whereCost(tRowcnt x){
108351		- static WhereCost a[] = { 0, 2, 3, 5, 6, 7, 8, 9 };
108352		- WhereCost y = 40;
108353		- if( x<8 ){
108354		- if( x<2 ) return 0;
108355		- while( x<8 ){ y -= 10; x <<= 1; }
108356		- }else{
108357		- while( x>255 ){ y += 40; x >>= 4; }
108358		- while( x>15 ){ y += 10; x >>= 1; }
108359		- }
108360		- return a[x&7] + y - 10;
108361		-}
108362		-
108363		-#ifndef SQLITE_OMIT_VIRTUALTABLE
108364		-/*
108365		-** Convert a double (as received from xBestIndex of a virtual table)
108366		-** into a WhereCost. In other words, compute an approximation for
108367		-** 10*log2(x).
108368		-*/
108369		-static WhereCost whereCostFromDouble(double x){
108370		- u64 a;
108371		- WhereCost e;
108372		- assert( sizeof(x)==8 && sizeof(a)==8 );
108373		- if( x<=1 ) return 0;
108374		- if( x<=2000000000 ) return whereCost((tRowcnt)x);
108375		- memcpy(&a, &x, 8);
108376		- e = (a>>52) - 1022;
108377		- return e*10;
108378		-}
108379		-#endif /* SQLITE_OMIT_VIRTUALTABLE */
108380	108495
108381	108496	/*
108382	108497	** Estimate the logarithm of the input value to base 2.
108383	108498	*/
108384		-static WhereCost estLog(WhereCost N){
108385		- WhereCost x = whereCost(N);
	108499	+static LogEst estLog(LogEst N){
	108500	+ LogEst x = sqlite3LogEst(N);
108386	108501	return x>33 ? x - 33 : 0;
108387	108502	}
108388	108503
108389	108504	/*
108390	108505	** Two routines for printing the content of an sqlite3_index_info
		@@ -108893,11 +109008,11 @@
108893	109008	**
108894	109009	** ... FROM t1 WHERE a > ? AND a < ? ...
108895	109010	**
108896	109011	** then nEq is set to 0.
108897	109012	**
108898		-** When this function is called, *pnOut is set to the whereCost() of the
	109013	+** When this function is called, *pnOut is set to the sqlite3LogEst() of the
108899	109014	** number of rows that the index scan is expected to visit without
108900	109015	** considering the range constraints. If nEq is 0, this is the number of
108901	109016	** rows in the index. Assuming no error occurs, *pnOut is adjusted (reduced)
108902	109017	** to account for the range contraints pLower and pUpper.
108903	109018	**
		@@ -108909,19 +109024,19 @@
108909	109024	static int whereRangeScanEst(
108910	109025	Parse pParse, / Parsing & code generating context */
108911	109026	WhereLoopBuilder *pBuilder,
108912	109027	WhereTerm pLower, / Lower bound on the range. ex: "x>123" Might be NULL */
108913	109028	WhereTerm pUpper, / Upper bound on the range. ex: "x<455" Might be NULL */
108914		- WhereCost pnOut / IN/OUT: Number of rows visited */
	109029	+ WhereLoop pLoop / Modify the .nOut and maybe .rRun fields */
108915	109030	){
108916	109031	int rc = SQLITE_OK;
108917		- int nOut = (int)*pnOut;
108918		- WhereCost nNew;
	109032	+ int nOut = pLoop->nOut;
	109033	+ int nEq = pLoop->u.btree.nEq;
	109034	+ LogEst nNew;
108919	109035
108920	109036	#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
108921		- Index *p = pBuilder->pNew->u.btree.pIndex;
108922		- int nEq = pBuilder->pNew->u.btree.nEq;
	109037	+ Index *p = pLoop->u.btree.pIndex;
108923	109038
108924	109039	if( p->nSample>0
108925	109040	&& nEq==pBuilder->nRecValid
108926	109041	&& nEq<p->nSampleCol
108927	109042	&& OptimizationEnabled(pParse->db, SQLITE_Stat3)
		@@ -108998,18 +109113,18 @@
108998	109113	}
108999	109114
109000	109115	pBuilder->pRec = pRec;
109001	109116	if( rc==SQLITE_OK ){
109002	109117	if( iUpper>iLower ){
109003		- nNew = whereCost(iUpper - iLower);
	109118	+ nNew = sqlite3LogEst(iUpper - iLower);
109004	109119	}else{
109005		- nNew = 10; assert( 10==whereCost(2) );
	109120	+ nNew = 10; assert( 10==sqlite3LogEst(2) );
109006	109121	}
109007	109122	if( nNew<nOut ){
109008	109123	nOut = nNew;
109009	109124	}
109010		- *pnOut = (WhereCost)nOut;
	109125	+ pLoop->nOut = (LogEst)nOut;
109011	109126	WHERETRACE(0x100, ("range scan regions: %u..%u est=%d\n",
109012	109127	(u32)iLower, (u32)iUpper, nOut));
109013	109128	return SQLITE_OK;
109014	109129	}
109015	109130	}
		@@ -109020,20 +109135,20 @@
109020	109135	assert( pLower \|\| pUpper );
109021	109136	/* TUNING: Each inequality constraint reduces the search space 4-fold.
109022	109137	** A BETWEEN operator, therefore, reduces the search space 16-fold */
109023	109138	nNew = nOut;
109024	109139	if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ){
109025		- nNew -= 20; assert( 20==whereCost(4) );
	109140	+ nNew -= 20; assert( 20==sqlite3LogEst(4) );
109026	109141	nOut--;
109027	109142	}
109028	109143	if( pUpper ){
109029		- nNew -= 20; assert( 20==whereCost(4) );
	109144	+ nNew -= 20; assert( 20==sqlite3LogEst(4) );
109030	109145	nOut--;
109031	109146	}
109032	109147	if( nNew<10 ) nNew = 10;
109033	109148	if( nNew<nOut ) nOut = nNew;
109034		- *pnOut = (WhereCost)nOut;
	109149	+ pLoop->nOut = (LogEst)nOut;
109035	109150	return rc;
109036	109151	}
109037	109152
109038	109153	#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
109039	109154	/*
		@@ -110673,11 +110788,11 @@
110673	110788	*/
110674	110789	static int whereLoopAddBtreeIndex(
110675	110790	WhereLoopBuilder pBuilder, / The WhereLoop factory */
110676	110791	struct SrcList_item pSrc, / FROM clause term being analyzed */
110677	110792	Index pProbe, / An index on pSrc */
110678		- WhereCost nInMul /* log(Number of iterations due to IN) */
	110793	+ LogEst nInMul /* log(Number of iterations due to IN) */
110679	110794	){
110680	110795	WhereInfo pWInfo = pBuilder->pWInfo; / WHERE analyse context */
110681	110796	Parse pParse = pWInfo->pParse; / Parsing context */
110682	110797	sqlite3 db = pParse->db; / Database connection malloc context */
110683	110798	WhereLoop pNew; / Template WhereLoop under construction */
		@@ -110686,15 +110801,15 @@
110686	110801	WhereScan scan; /* Iterator for WHERE terms */
110687	110802	Bitmask saved_prereq; /* Original value of pNew->prereq */
110688	110803	u16 saved_nLTerm; /* Original value of pNew->nLTerm */
110689	110804	int saved_nEq; /* Original value of pNew->u.btree.nEq */
110690	110805	u32 saved_wsFlags; /* Original value of pNew->wsFlags */
110691		- WhereCost saved_nOut; /* Original value of pNew->nOut */
	110806	+ LogEst saved_nOut; /* Original value of pNew->nOut */
110692	110807	int iCol; /* Index of the column in the table */
110693	110808	int rc = SQLITE_OK; /* Return code */
110694		- WhereCost nRowEst; /* Estimated index selectivity */
110695		- WhereCost rLogSize; /* Logarithm of table size */
	110809	+ LogEst nRowEst; /* Estimated index selectivity */
	110810	+ LogEst rLogSize; /* Logarithm of table size */
110696	110811	WhereTerm pTop = 0, pBtm = 0; /* Top and bottom range constraints */
110697	110812
110698	110813	pNew = pBuilder->pNew;
110699	110814	if( db->mallocFailed ) return SQLITE_NOMEM;
110700	110815
		@@ -110710,11 +110825,11 @@
110710	110825	if( pProbe->bUnordered ) opMask &= ~(WO_GT\|WO_GE\|WO_LT\|WO_LE);
110711	110826
110712	110827	assert( pNew->u.btree.nEq<=pProbe->nColumn );
110713	110828	if( pNew->u.btree.nEq < pProbe->nColumn ){
110714	110829	iCol = pProbe->aiColumn[pNew->u.btree.nEq];
110715		- nRowEst = whereCost(pProbe->aiRowEst[pNew->u.btree.nEq+1]);
	110830	+ nRowEst = sqlite3LogEst(pProbe->aiRowEst[pNew->u.btree.nEq+1]);
110716	110831	if( nRowEst==0 && pProbe->onError==OE_None ) nRowEst = 1;
110717	110832	}else{
110718	110833	iCol = -1;
110719	110834	nRowEst = 0;
110720	110835	}
		@@ -110724,11 +110839,11 @@
110724	110839	saved_nLTerm = pNew->nLTerm;
110725	110840	saved_wsFlags = pNew->wsFlags;
110726	110841	saved_prereq = pNew->prereq;
110727	110842	saved_nOut = pNew->nOut;
110728	110843	pNew->rSetup = 0;
110729		- rLogSize = estLog(whereCost(pProbe->aiRowEst[0]));
	110844	+ rLogSize = estLog(sqlite3LogEst(pProbe->aiRowEst[0]));
110730	110845	for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
110731	110846	int nIn = 0;
110732	110847	#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
110733	110848	int nRecValid = pBuilder->nRecValid;
110734	110849	#endif
		@@ -110751,14 +110866,14 @@
110751	110866	if( pTerm->eOperator & WO_IN ){
110752	110867	Expr *pExpr = pTerm->pExpr;
110753	110868	pNew->wsFlags \|= WHERE_COLUMN_IN;
110754	110869	if( ExprHasProperty(pExpr, EP_xIsSelect) ){
110755	110870	/* "x IN (SELECT ...)": TUNING: the SELECT returns 25 rows */
110756		- nIn = 46; assert( 46==whereCost(25) );
	110871	+ nIn = 46; assert( 46==sqlite3LogEst(25) );
110757	110872	}else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
110758	110873	/* "x IN (value, value, ...)" */
110759		- nIn = whereCost(pExpr->x.pList->nExpr);
	110874	+ nIn = sqlite3LogEst(pExpr->x.pList->nExpr);
110760	110875	}
110761	110876	pNew->rRun += nIn;
110762	110877	pNew->u.btree.nEq++;
110763	110878	pNew->nOut = nRowEst + nInMul + nIn;
110764	110879	}else if( pTerm->eOperator & (WO_EQ) ){
		@@ -110776,11 +110891,11 @@
110776	110891	pNew->nOut = nRowEst + nInMul;
110777	110892	}else if( pTerm->eOperator & (WO_ISNULL) ){
110778	110893	pNew->wsFlags \|= WHERE_COLUMN_NULL;
110779	110894	pNew->u.btree.nEq++;
110780	110895	/* TUNING: IS NULL selects 2 rows */
110781		- nIn = 10; assert( 10==whereCost(2) );
	110896	+ nIn = 10; assert( 10==sqlite3LogEst(2) );
110782	110897	pNew->nOut = nRowEst + nInMul + nIn;
110783	110898	}else if( pTerm->eOperator & (WO_GT\|WO_GE) ){
110784	110899	testcase( pTerm->eOperator & WO_GT );
110785	110900	testcase( pTerm->eOperator & WO_GE );
110786	110901	pNew->wsFlags \|= WHERE_COLUMN_RANGE\|WHERE_BTM_LIMIT;
		@@ -110796,11 +110911,11 @@
110796	110911	pNew->aLTerm[pNew->nLTerm-2] : 0;
110797	110912	}
110798	110913	if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
110799	110914	/* Adjust nOut and rRun for STAT3 range values */
110800	110915	assert( pNew->nOut==saved_nOut );
110801		- whereRangeScanEst(pParse, pBuilder, pBtm, pTop, &pNew->nOut);
	110916	+ whereRangeScanEst(pParse, pBuilder, pBtm, pTop, pNew);
110802	110917	}
110803	110918	#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
110804	110919	if( nInMul==0
110805	110920	&& pProbe->nSample
110806	110921	&& pNew->u.btree.nEq<=pProbe->nSampleCol
		@@ -110816,22 +110931,22 @@
110816	110931	&& !ExprHasProperty(pExpr, EP_xIsSelect) ){
110817	110932	rc = whereInScanEst(pParse, pBuilder, pExpr->x.pList, &nOut);
110818	110933	}
110819	110934	assert( nOut==0 \|\| rc==SQLITE_OK );
110820	110935	if( nOut ){
110821		- nOut = whereCost(nOut);
	110936	+ nOut = sqlite3LogEst(nOut);
110822	110937	pNew->nOut = MIN(nOut, saved_nOut);
110823	110938	}
110824	110939	}
110825	110940	#endif
110826	110941	if( (pNew->wsFlags & (WHERE_IDX_ONLY\|WHERE_IPK))==0 ){
110827	110942	/* Each row involves a step of the index, then a binary search of
110828	110943	** the main table */
110829		- pNew->rRun = whereCostAdd(pNew->rRun, rLogSize>27 ? rLogSize-17 : 10);
	110944	+ pNew->rRun = sqlite3LogEstAdd(pNew->rRun,rLogSize>27 ? rLogSize-17 : 10);
110830	110945	}
110831	110946	/* Step cost for each output row */
110832		- pNew->rRun = whereCostAdd(pNew->rRun, pNew->nOut);
	110947	+ pNew->rRun = sqlite3LogEstAdd(pNew->rRun, pNew->nOut);
110833	110948	whereLoopOutputAdjust(pBuilder->pWC, pNew, pSrc->iCursor);
110834	110949	rc = whereLoopInsert(pBuilder, pNew);
110835	110950	if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
110836	110951	&& pNew->u.btree.nEq<(pProbe->nColumn + (pProbe->zName!=0))
110837	110952	){
		@@ -110927,18 +111042,20 @@
110927	111042	struct SrcList_item pSrc; / The FROM clause btree term to add */
110928	111043	WhereLoop pNew; / Template WhereLoop object */
110929	111044	int rc = SQLITE_OK; /* Return code */
110930	111045	int iSortIdx = 1; /* Index number */
110931	111046	int b; /* A boolean value */
110932		- WhereCost rSize; /* number of rows in the table */
110933		- WhereCost rLogSize; /* Logarithm of the number of rows in the table */
	111047	+ LogEst rSize; /* number of rows in the table */
	111048	+ LogEst rLogSize; /* Logarithm of the number of rows in the table */
110934	111049	WhereClause pWC; / The parsed WHERE clause */
	111050	+ Table pTab; / Table being queried */
110935	111051
110936	111052	pNew = pBuilder->pNew;
110937	111053	pWInfo = pBuilder->pWInfo;
110938	111054	pTabList = pWInfo->pTabList;
110939	111055	pSrc = pTabList->a + pNew->iTab;
	111056	+ pTab = pSrc->pTab;
110940	111057	pWC = pBuilder->pWC;
110941	111058	assert( !IsVirtual(pSrc->pTab) );
110942	111059
110943	111060	if( pSrc->pIndex ){
110944	111061	/* An INDEXED BY clause specifies a particular index to use */
		@@ -110952,22 +111069,22 @@
110952	111069	memset(&sPk, 0, sizeof(Index));
110953	111070	sPk.nColumn = 1;
110954	111071	sPk.aiColumn = &aiColumnPk;
110955	111072	sPk.aiRowEst = aiRowEstPk;
110956	111073	sPk.onError = OE_Replace;
110957		- sPk.pTable = pSrc->pTab;
110958		- aiRowEstPk[0] = pSrc->pTab->nRowEst;
	111074	+ sPk.pTable = pTab;
	111075	+ aiRowEstPk[0] = pTab->nRowEst;
110959	111076	aiRowEstPk[1] = 1;
110960	111077	pFirst = pSrc->pTab->pIndex;
110961	111078	if( pSrc->notIndexed==0 ){
110962	111079	/* The real indices of the table are only considered if the
110963	111080	** NOT INDEXED qualifier is omitted from the FROM clause */
110964	111081	sPk.pNext = pFirst;
110965	111082	}
110966	111083	pProbe = &sPk;
110967	111084	}
110968		- rSize = whereCost(pSrc->pTab->nRowEst);
	111085	+ rSize = sqlite3LogEst(pTab->nRowEst);
110969	111086	rLogSize = estLog(rSize);
110970	111087
110971	111088	#ifndef SQLITE_OMIT_AUTOMATIC_INDEX
110972	111089	/* Automatic indexes */
110973	111090	if( !pBuilder->pOrSet
		@@ -110988,17 +111105,17 @@
110988	111105	pNew->nLTerm = 1;
110989	111106	pNew->aLTerm[0] = pTerm;
110990	111107	/* TUNING: One-time cost for computing the automatic index is
110991	111108	** approximately 7Nlog2(N) where N is the number of rows in
110992	111109	** the table being indexed. */
110993		- pNew->rSetup = rLogSize + rSize + 28; assert( 28==whereCost(7) );
	111110	+ pNew->rSetup = rLogSize + rSize + 28; assert( 28==sqlite3LogEst(7) );
110994	111111	/* TUNING: Each index lookup yields 20 rows in the table. This
110995	111112	** is more than the usual guess of 10 rows, since we have no way
110996	111113	** of knowning how selective the index will ultimately be. It would
110997	111114	** not be unreasonable to make this value much larger. */
110998		- pNew->nOut = 43; assert( 43==whereCost(20) );
110999		- pNew->rRun = whereCostAdd(rLogSize,pNew->nOut);
	111115	+ pNew->nOut = 43; assert( 43==sqlite3LogEst(20) );
	111116	+ pNew->rRun = sqlite3LogEstAdd(rLogSize,pNew->nOut);
111000	111117	pNew->wsFlags = WHERE_AUTO_INDEX;
111001	111118	pNew->prereq = mExtra \| pTerm->prereqRight;
111002	111119	rc = whereLoopInsert(pBuilder, pNew);
111003	111120	}
111004	111121	}
		@@ -111028,14 +111145,12 @@
111028	111145
111029	111146	/* Full table scan */
111030	111147	pNew->iSortIdx = b ? iSortIdx : 0;
111031	111148	/* TUNING: Cost of full table scan is 3*(N + log2(N)).
111032	111149	** + The extra 3 factor is to encourage the use of indexed lookups
111033		- ** over full scans. A smaller constant 2 is used for covering
111034		- ** index scans so that a covering index scan will be favored over
111035		- ** a table scan. */
111036		- pNew->rRun = whereCostAdd(rSize,rLogSize) + 16;
	111150	+ ** over full scans. FIXME */
	111151	+ pNew->rRun = sqlite3LogEstAdd(rSize,rLogSize) + 16;
111037	111152	whereLoopOutputAdjust(pWC, pNew, pSrc->iCursor);
111038	111153	rc = whereLoopInsert(pBuilder, pNew);
111039	111154	pNew->nOut = rSize;
111040	111155	if( rc ) break;
111041	111156	}else{
		@@ -111044,26 +111159,25 @@
111044	111159
111045	111160	/* Full scan via index */
111046	111161	if( b
111047	111162	\|\| ( m==0
111048	111163	&& pProbe->bUnordered==0
	111164	+ && pProbe->szIdxRow<pTab->szTabRow
111049	111165	&& (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
111050	111166	&& sqlite3GlobalConfig.bUseCis
111051	111167	&& OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
111052	111168	)
111053	111169	){
111054	111170	pNew->iSortIdx = b ? iSortIdx : 0;
111055	111171	if( m==0 ){
111056		- /* TUNING: Cost of a covering index scan is 2*(N + log2(N)).
111057		- ** + The extra 2 factor is to encourage the use of indexed lookups
111058		- ** over index scans. A table scan uses a factor of 3 so that
111059		- ** index scans are favored over table scans.
111060		- ** + If this covering index might also help satisfy the ORDER BY
111061		- ** clause, then the cost is fudged down slightly so that this
111062		- ** index is favored above other indices that have no hope of
111063		- ** helping with the ORDER BY. */
111064		- pNew->rRun = 10 + whereCostAdd(rSize,rLogSize) - b;
	111172	+ /* TUNING: Cost of a covering index scan is K*(N + log2(N)).
	111173	+ ** + The extra factor K of between 1.1 and 3.0 that depends
	111174	+ ** on the relative sizes of the table and the index. K
	111175	+ ** is smaller for smaller indices, thus favoring them.
	111176	+ */
	111177	+ pNew->rRun = sqlite3LogEstAdd(rSize,rLogSize) + 1 +
	111178	+ (15*pProbe->szIdxRow)/pTab->szTabRow;
111065	111179	}else{
111066	111180	assert( b!=0 );
111067	111181	/* TUNING: Cost of scanning a non-covering index is (N+1)*log2(N)
111068	111182	** which we will simplify to just Nlog2(N) /
111069	111183	pNew->rRun = rSize + rLogSize;
		@@ -111237,13 +111351,13 @@
111237	111351	pIdxInfo->needToFreeIdxStr = 0;
111238	111352	pNew->u.vtab.idxStr = pIdxInfo->idxStr;
111239	111353	pNew->u.vtab.isOrdered = (u8)((pIdxInfo->nOrderBy!=0)
111240	111354	&& pIdxInfo->orderByConsumed);
111241	111355	pNew->rSetup = 0;
111242		- pNew->rRun = whereCostFromDouble(pIdxInfo->estimatedCost);
	111356	+ pNew->rRun = sqlite3LogEstFromDouble(pIdxInfo->estimatedCost);
111243	111357	/* TUNING: Every virtual table query returns 25 rows */
111244		- pNew->nOut = 46; assert( 46==whereCost(25) );
	111358	+ pNew->nOut = 46; assert( 46==sqlite3LogEst(25) );
111245	111359	whereLoopInsert(pBuilder, pNew);
111246	111360	if( pNew->u.vtab.needFree ){
111247	111361	sqlite3_free(pNew->u.vtab.idxStr);
111248	111362	pNew->u.vtab.needFree = 0;
111249	111363	}
		@@ -111276,10 +111390,12 @@
111276	111390	pWC = pBuilder->pWC;
111277	111391	if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK;
111278	111392	pWCEnd = pWC->a + pWC->nTerm;
111279	111393	pNew = pBuilder->pNew;
111280	111394	memset(&sSum, 0, sizeof(sSum));
	111395	+ pItem = pWInfo->pTabList->a + pNew->iTab;
	111396	+ iCur = pItem->iCursor;
111281	111397
111282	111398	for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){
111283	111399	if( (pTerm->eOperator & WO_OR)!=0
111284	111400	&& (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0
111285	111401	){
		@@ -111287,12 +111403,10 @@
111287	111403	WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
111288	111404	WhereTerm *pOrTerm;
111289	111405	int once = 1;
111290	111406	int i, j;
111291	111407
111292		- pItem = pWInfo->pTabList->a + pNew->iTab;
111293		- iCur = pItem->iCursor;
111294	111408	sSubBuild = *pBuilder;
111295	111409	sSubBuild.pOrderBy = 0;
111296	111410	sSubBuild.pOrSet = &sCur;
111297	111411
111298	111412	for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
		@@ -111329,12 +111443,12 @@
111329	111443	whereOrMove(&sPrev, &sSum);
111330	111444	sSum.n = 0;
111331	111445	for(i=0; i<sPrev.n; i++){
111332	111446	for(j=0; j<sCur.n; j++){
111333	111447	whereOrInsert(&sSum, sPrev.a[i].prereq \| sCur.a[j].prereq,
111334		- whereCostAdd(sPrev.a[i].rRun, sCur.a[j].rRun),
111335		- whereCostAdd(sPrev.a[i].nOut, sCur.a[j].nOut));
	111448	+ sqlite3LogEstAdd(sPrev.a[i].rRun, sCur.a[j].rRun),
	111449	+ sqlite3LogEstAdd(sPrev.a[i].nOut, sCur.a[j].nOut));
111336	111450	}
111337	111451	}
111338	111452	}
111339	111453	}
111340	111454	pNew->nLTerm = 1;
		@@ -111668,23 +111782,23 @@
111668	111782	** costs if nRowEst==0.
111669	111783	**
111670	111784	** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
111671	111785	** error occurs.
111672	111786	*/
111673		-static int wherePathSolver(WhereInfo *pWInfo, WhereCost nRowEst){
	111787	+static int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){
111674	111788	int mxChoice; /* Maximum number of simultaneous paths tracked */
111675	111789	int nLoop; /* Number of terms in the join */
111676	111790	Parse pParse; / Parsing context */
111677	111791	sqlite3 db; / The database connection */
111678	111792	int iLoop; /* Loop counter over the terms of the join */
111679	111793	int ii, jj; /* Loop counters */
111680	111794	int mxI = 0; /* Index of next entry to replace */
111681		- WhereCost rCost; /* Cost of a path */
111682		- WhereCost nOut; /* Number of outputs */
111683		- WhereCost mxCost = 0; /* Maximum cost of a set of paths */
111684		- WhereCost mxOut = 0; /* Maximum nOut value on the set of paths */
111685		- WhereCost rSortCost; /* Cost to do a sort */
	111795	+ LogEst rCost; /* Cost of a path */
	111796	+ LogEst nOut; /* Number of outputs */
	111797	+ LogEst mxCost = 0; /* Maximum cost of a set of paths */
	111798	+ LogEst mxOut = 0; /* Maximum nOut value on the set of paths */
	111799	+ LogEst rSortCost; /* Cost to do a sort */
111686	111800	int nTo, nFrom; /* Number of valid entries in aTo[] and aFrom[] */
111687	111801	WherePath aFrom; / All nFrom paths at the previous level */
111688	111802	WherePath aTo; / The nTo best paths at the current level */
111689	111803	WherePath pFrom; / An element of aFrom[] that we are working on */
111690	111804	WherePath pTo; / An element of aTo[] that we are working on */
		@@ -111717,21 +111831,23 @@
111717	111831	/* Seed the search with a single WherePath containing zero WhereLoops.
111718	111832	**
111719	111833	** TUNING: Do not let the number of iterations go above 25. If the cost
111720	111834	** of computing an automatic index is not paid back within the first 25
111721	111835	** rows, then do not use the automatic index. */
111722		- aFrom[0].nRow = MIN(pParse->nQueryLoop, 46); assert( 46==whereCost(25) );
	111836	+ aFrom[0].nRow = MIN(pParse->nQueryLoop, 46); assert( 46==sqlite3LogEst(25) );
111723	111837	nFrom = 1;
111724	111838
111725	111839	/* Precompute the cost of sorting the final result set, if the caller
111726	111840	** to sqlite3WhereBegin() was concerned about sorting */
111727	111841	rSortCost = 0;
111728	111842	if( pWInfo->pOrderBy==0 \|\| nRowEst==0 ){
111729	111843	aFrom[0].isOrderedValid = 1;
111730	111844	}else{
111731		- /* TUNING: Estimated cost of sorting is N*log2(N) where N is the
111732		- ** number of output rows. */
	111845	+ /* TUNING: Estimated cost of sorting is 48Nlog2(N) where N is the
	111846	+ ** number of output rows. The 48 is the expected size of a row to sort.
	111847	+ ** FIXME: compute a better estimate of the 48 multiplier based on the
	111848	+ ** result set expressions. */
111733	111849	rSortCost = nRowEst + estLog(nRowEst);
111734	111850	WHERETRACE(0x002,("---- sort cost=%-3d\n", rSortCost));
111735	111851	}
111736	111852
111737	111853	/* Compute successively longer WherePaths using the previous generation
		@@ -111747,12 +111863,12 @@
111747	111863	u8 isOrdered = pFrom->isOrdered;
111748	111864	if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
111749	111865	if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
111750	111866	/* At this point, pWLoop is a candidate to be the next loop.
111751	111867	** Compute its cost */
111752		- rCost = whereCostAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow);
111753		- rCost = whereCostAdd(rCost, pFrom->rCost);
	111868	+ rCost = sqlite3LogEstAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow);
	111869	+ rCost = sqlite3LogEstAdd(rCost, pFrom->rCost);
111754	111870	nOut = pFrom->nRow + pWLoop->nOut;
111755	111871	maskNew = pFrom->maskLoop \| pWLoop->maskSelf;
111756	111872	if( !isOrderedValid ){
111757	111873	switch( wherePathSatisfiesOrderBy(pWInfo,
111758	111874	pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
		@@ -111762,11 +111878,11 @@
111762	111878	isOrderedValid = 1;
111763	111879	break;
111764	111880	case 0: /* No. pFrom+pWLoop will require a separate sort */
111765	111881	isOrdered = 0;
111766	111882	isOrderedValid = 1;
111767		- rCost = whereCostAdd(rCost, rSortCost);
	111883	+ rCost = sqlite3LogEstAdd(rCost, rSortCost);
111768	111884	break;
111769	111885	default: /* Cannot tell yet. Try again on the next iteration */
111770	111886	break;
111771	111887	}
111772	111888	}else{
		@@ -111969,11 +112085,11 @@
111969	112085	pLoop->wsFlags = WHERE_COLUMN_EQ\|WHERE_IPK\|WHERE_ONEROW;
111970	112086	pLoop->aLTerm[0] = pTerm;
111971	112087	pLoop->nLTerm = 1;
111972	112088	pLoop->u.btree.nEq = 1;
111973	112089	/* TUNING: Cost of a rowid lookup is 10 */
111974		- pLoop->rRun = 33; /* 33==whereCost(10) */
	112090	+ pLoop->rRun = 33; /* 33==sqlite3LogEst(10) */
111975	112091	}else{
111976	112092	for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
111977	112093	assert( pLoop->aLTermSpace==pLoop->aLTerm );
111978	112094	assert( ArraySize(pLoop->aLTermSpace)==4 );
111979	112095	if( pIdx->onError==OE_None
		@@ -111992,16 +112108,16 @@
111992	112108	}
111993	112109	pLoop->nLTerm = j;
111994	112110	pLoop->u.btree.nEq = j;
111995	112111	pLoop->u.btree.pIndex = pIdx;
111996	112112	/* TUNING: Cost of a unique index lookup is 15 */
111997		- pLoop->rRun = 39; /* 39==whereCost(15) */
	112113	+ pLoop->rRun = 39; /* 39==sqlite3LogEst(15) */
111998	112114	break;
111999	112115	}
112000	112116	}
112001	112117	if( pLoop->wsFlags ){
112002		- pLoop->nOut = (WhereCost)1;
	112118	+ pLoop->nOut = (LogEst)1;
112003	112119	pWInfo->a[0].pWLoop = pLoop;
112004	112120	pLoop->maskSelf = getMask(&pWInfo->sMaskSet, iCur);
112005	112121	pWInfo->a[0].iTabCur = iCur;
112006	112122	pWInfo->nRowOut = 1;
112007	112123	if( pWInfo->pOrderBy ) pWInfo->bOBSat = 1;
112008	112124

	--- src/sqlite3.c
	+++ src/sqlite3.c
	@@ -656,11 +656,11 @@
656	** [sqlite3_libversion_number()], [sqlite3_sourceid()],
657	** [sqlite_version()] and [sqlite_source_id()].
658	*/
659	#define SQLITE_VERSION "3.8.1"
660	#define SQLITE_VERSION_NUMBER 3008001
661	#define SQLITE_SOURCE_ID "2013-10-07 21:49:16 36d64dc36f18c166b2c93c43579fa3bbb5cd545f"
662
663	/*
664	** CAPI3REF: Run-Time Library Version Numbers
665	** KEYWORDS: sqlite3_version, sqlite3_sourceid
666	**
	@@ -8272,10 +8272,35 @@
8272	typedef u64 tRowcnt; /* 64-bit only if requested at compile-time */
8273	#else
8274	typedef u32 tRowcnt; /* 32-bit is the default */
8275	#endif
8276

























8277	/*
8278	** Macros to determine whether the machine is big or little endian,
8279	** evaluated at runtime.
8280	*/
8281	#ifdef SQLITE_AMALGAMATION
	@@ -10419,11 +10444,12 @@
10419	char zDflt; / Original text of the default value */
10420	char zType; / Data type for this column */
10421	char zColl; / Collating sequence. If NULL, use the default */
10422	u8 notNull; /* An OE_ code for handling a NOT NULL constraint */
10423	char affinity; /* One of the SQLITE_AFF_... values */
10424	u16 colFlags; /* Boolean properties. See COLFLAG_ defines below */

10425	};
10426
10427	/* Allowed values for Column.colFlags:
10428	*/
10429	#define COLFLAG_PRIMKEY 0x0001 /* Column is part of the primary key */
	@@ -10583,10 +10609,11 @@
10583	tRowcnt nRowEst; /* Estimated rows in table - from sqlite_stat1 table */
10584	int tnum; /* Root BTree node for this table (see note above) */
10585	i16 iPKey; /* If not negative, use aCol[iPKey] as the primary key */
10586	i16 nCol; /* Number of columns in this table */
10587	u16 nRef; /* Number of pointers to this Table */

10588	u8 tabFlags; /* Mask of TF_* values */
10589	u8 keyConf; /* What to do in case of uniqueness conflict on iPKey */
10590	#ifndef SQLITE_OMIT_ALTERTABLE
10591	int addColOffset; /* Offset in CREATE TABLE stmt to add a new column */
10592	#endif
	@@ -10694,11 +10721,11 @@
10694	#define OE_Restrict 6 /* OE_Abort for IMMEDIATE, OE_Rollback for DEFERRED */
10695	#define OE_SetNull 7 /* Set the foreign key value to NULL */
10696	#define OE_SetDflt 8 /* Set the foreign key value to its default */
10697	#define OE_Cascade 9 /* Cascade the changes */
10698
10699	#define OE_Default 99 /* Do whatever the default action is */
10700
10701
10702	/*
10703	** An instance of the following structure is passed as the first
10704	** argument to sqlite3VdbeKeyCompare and is used to control the
	@@ -10781,10 +10808,11 @@
10781	Schema pSchema; / Schema containing this index */
10782	u8 aSortOrder; / for each column: True==DESC, False==ASC */
10783	char *azColl; / Array of collation sequence names for index */
10784	Expr pPartIdxWhere; / WHERE clause for partial indices */
10785	int tnum; /* DB Page containing root of this index */

10786	u16 nColumn; /* Number of columns in table used by this index */
10787	u8 onError; /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */
10788	unsigned autoIndex:2; /* 1==UNIQUE, 2==PRIMARY KEY, 0==CREATE INDEX */
10789	unsigned bUnordered:1; /* Use this index for == or IN queries only */
10790	unsigned uniqNotNull:1; /* True if UNIQUE and NOT NULL for all columns */
	@@ -12187,10 +12215,16 @@
12187	SQLITE_PRIVATE int sqlite3GetInt32(const char , int);
12188	SQLITE_PRIVATE int sqlite3Atoi(const char*);
12189	SQLITE_PRIVATE int sqlite3Utf16ByteLen(const void *pData, int nChar);
12190	SQLITE_PRIVATE int sqlite3Utf8CharLen(const char *pData, int nByte);
12191	SQLITE_PRIVATE u32 sqlite3Utf8Read(const u8**);






12192
12193	/*
12194	** Routines to read and write variable-length integers. These used to
12195	** be defined locally, but now we use the varint routines in the util.c
12196	** file. Code should use the MACRO forms below, as the Varint32 versions
	@@ -12303,11 +12337,11 @@
12303	SQLITE_PRIVATE int sqlite3ResolveOrderGroupBy(Parse, Select, ExprList, const char);
12304	SQLITE_PRIVATE void sqlite3ColumnDefault(Vdbe , Table , int, int);
12305	SQLITE_PRIVATE void sqlite3AlterFinishAddColumn(Parse , Token );
12306	SQLITE_PRIVATE void sqlite3AlterBeginAddColumn(Parse , SrcList );
12307	SQLITE_PRIVATE CollSeq sqlite3GetCollSeq(Parse, u8, CollSeq , const char);
12308	SQLITE_PRIVATE char sqlite3AffinityType(const char*);
12309	SQLITE_PRIVATE void sqlite3Analyze(Parse, Token, Token*);
12310	SQLITE_PRIVATE int sqlite3InvokeBusyHandler(BusyHandler*);
12311	SQLITE_PRIVATE int sqlite3FindDb(sqlite3, Token);
12312	SQLITE_PRIVATE int sqlite3FindDbName(sqlite3 , const char );
12313	SQLITE_PRIVATE int sqlite3AnalysisLoad(sqlite3*,int iDB);
	@@ -22388,10 +22422,87 @@
22388	for(i=sz-1; i>0 && z[i]!='/' && z[i]!='.'; i--){}
22389	if( z[i]=='.' && ALWAYS(sz>i+4) ) memmove(&z[i+1], &z[sz-3], 4);
22390	}
22391	}
22392	#endif













































































22393
22394	/************ End of util.c **********************************************/
22395	/************ Begin file hash.c ******************************************/
22396	/*
22397	** 2001 September 22
	@@ -76084,11 +76195,11 @@
76084	return sqlite3ExprAffinity(pExpr->x.pSelect->pEList->a[0].pExpr);
76085	}
76086	#ifndef SQLITE_OMIT_CAST
76087	if( op==TK_CAST ){
76088	assert( !ExprHasProperty(pExpr, EP_IntValue) );
76089	return sqlite3AffinityType(pExpr->u.zToken);
76090	}
76091	#endif
76092	if( (op==TK_AGG_COLUMN \|\| op==TK_COLUMN \|\| op==TK_REGISTER)
76093	&& pExpr->pTab!=0
76094	){
	@@ -78504,11 +78615,11 @@
78504	case TK_CAST: {
78505	/* Expressions of the form: CAST(pLeft AS token) */
78506	int aff, to_op;
78507	inReg = sqlite3ExprCodeTarget(pParse, pExpr->pLeft, target);
78508	assert( !ExprHasProperty(pExpr, EP_IntValue) );
78509	aff = sqlite3AffinityType(pExpr->u.zToken);
78510	to_op = aff - SQLITE_AFF_TEXT + OP_ToText;
78511	assert( to_op==OP_ToText \|\| aff!=SQLITE_AFF_TEXT );
78512	assert( to_op==OP_ToBlob \|\| aff!=SQLITE_AFF_NONE );
78513	assert( to_op==OP_ToNumeric \|\| aff!=SQLITE_AFF_NUMERIC );
78514	assert( to_op==OP_ToInt \|\| aff!=SQLITE_AFF_INTEGER );
	@@ -79171,11 +79282,11 @@
79171	}
79172	#ifndef SQLITE_OMIT_CAST
79173	case TK_CAST: {
79174	/* Expressions of the form: CAST(pLeft AS token) */
79175	const char *zAff = "unk";
79176	switch( sqlite3AffinityType(pExpr->u.zToken) ){
79177	case SQLITE_AFF_TEXT: zAff = "TEXT"; break;
79178	case SQLITE_AFF_NONE: zAff = "NONE"; break;
79179	case SQLITE_AFF_NUMERIC: zAff = "NUMERIC"; break;
79180	case SQLITE_AFF_INTEGER: zAff = "INTEGER"; break;
79181	case SQLITE_AFF_REAL: zAff = "REAL"; break;
	@@ -81886,16 +81997,16 @@
81886	if( zRet==0 ){
81887	sqlite3_result_error_nomem(context);
81888	return;
81889	}
81890
81891	sqlite3_snprintf(24, zRet, "%lld", p->nRow);
81892	z = zRet + sqlite3Strlen30(zRet);
81893	for(i=0; i<(p->nCol-1); i++){
81894	i64 nDistinct = p->current.anDLt[i] + 1;
81895	i64 iVal = (p->nRow + nDistinct - 1) / nDistinct;
81896	sqlite3_snprintf(24, z, " %lld", iVal);
81897	z += sqlite3Strlen30(z);
81898	assert( p->current.anEq[i] );
81899	}
81900	assert( z[0]=='\0' && z>zRet );
81901
	@@ -81932,11 +82043,11 @@
81932	sqlite3_result_error_nomem(context);
81933	}else{
81934	int i;
81935	char *z = zRet;
81936	for(i=0; i<p->nCol; i++){
81937	sqlite3_snprintf(24, z, "%lld ", aCnt[i]);
81938	z += sqlite3Strlen30(z);
81939	}
81940	assert( z[0]=='\0' && z>zRet );
81941	z[-1] = '\0';
81942	sqlite3_result_text(context, zRet, -1, sqlite3_free);
	@@ -82393,22 +82504,20 @@
82393	** The first argument points to a nul-terminated string containing a
82394	** list of space separated integers. Read the first nOut of these into
82395	** the array aOut[].
82396	*/
82397	static void decodeIntArray(
82398	char *zIntArray,
82399	int nOut,
82400	tRowcnt *aOut,
82401	int *pbUnordered
82402	){
82403	char *z = zIntArray;
82404	int c;
82405	int i;
82406	tRowcnt v;
82407
82408	assert( pbUnordered==0 \|\| *pbUnordered==0 );
82409
82410	#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
82411	if( z==0 ) z = "";
82412	#else
82413	if( NEVER(z==0) ) z = "";
82414	#endif
	@@ -82419,12 +82528,23 @@
82419	z++;
82420	}
82421	aOut[i] = v;
82422	if( *z==' ' ) z++;
82423	}
82424	if( pbUnordered && strcmp(z, "unordered")==0 ){
82425	*pbUnordered = 1;











82426	}
82427	}
82428
82429	/*
82430	** This callback is invoked once for each index when reading the
	@@ -82459,16 +82579,17 @@
82459	pIndex = 0;
82460	}
82461	z = argv[2];
82462
82463	if( pIndex ){
82464	int bUnordered = 0;
82465	decodeIntArray((char*)z, pIndex->nColumn+1, pIndex->aiRowEst,&bUnordered);
82466	if( pIndex->pPartIdxWhere==0 ) pTable->nRowEst = pIndex->aiRowEst[0];
82467	pIndex->bUnordered = bUnordered;
82468	}else{
82469	decodeIntArray((char*)z, 1, &pTable->nRowEst, 0);



82470	}
82471
82472	return 0;
82473	}
82474
	@@ -84480,11 +84601,11 @@
84480	}
84481	pTable->zName = zName;
84482	pTable->iPKey = -1;
84483	pTable->pSchema = db->aDb[iDb].pSchema;
84484	pTable->nRef = 1;
84485	pTable->nRowEst = 1000000;
84486	assert( pParse->pNewTable==0 );
84487	pParse->pNewTable = pTable;
84488
84489	/* If this is the magic sqlite_sequence table used by autoincrement,
84490	** then record a pointer to this table in the main database structure
	@@ -84627,10 +84748,11 @@
84627	/* If there is no type specified, columns have the default affinity
84628	** 'NONE'. If there is a type specified, then sqlite3AddColumnType() will
84629	** be called next to set pCol->affinity correctly.
84630	*/
84631	pCol->affinity = SQLITE_AFF_NONE;

84632	p->nCol++;
84633	}
84634
84635	/*
84636	** This routine is called by the parser while in the middle of
	@@ -84668,26 +84790,30 @@
84668	** 'DOUB' \| SQLITE_AFF_REAL
84669	**
84670	** If none of the substrings in the above table are found,
84671	** SQLITE_AFF_NUMERIC is returned.
84672	*/
84673	SQLITE_PRIVATE char sqlite3AffinityType(const char *zIn){
84674	u32 h = 0;
84675	char aff = SQLITE_AFF_NUMERIC;

84676
84677	if( zIn ) while( zIn[0] ){

84678	h = (h<<8) + sqlite3UpperToLower[(*zIn)&0xff];
84679	zIn++;
84680	if( h==(('c'<<24)+('h'<<16)+('a'<<8)+'r') ){ /* CHAR */
84681	aff = SQLITE_AFF_TEXT;

84682	}else if( h==(('c'<<24)+('l'<<16)+('o'<<8)+'b') ){ /* CLOB */
84683	aff = SQLITE_AFF_TEXT;
84684	}else if( h==(('t'<<24)+('e'<<16)+('x'<<8)+'t') ){ /* TEXT */
84685	aff = SQLITE_AFF_TEXT;
84686	}else if( h==(('b'<<24)+('l'<<16)+('o'<<8)+'b') /* BLOB */
84687	&& (aff==SQLITE_AFF_NUMERIC \|\| aff==SQLITE_AFF_REAL) ){
84688	aff = SQLITE_AFF_NONE;

84689	#ifndef SQLITE_OMIT_FLOATING_POINT
84690	}else if( h==(('r'<<24)+('e'<<16)+('a'<<8)+'l') /* REAL */
84691	&& aff==SQLITE_AFF_NUMERIC ){
84692	aff = SQLITE_AFF_REAL;
84693	}else if( h==(('f'<<24)+('l'<<16)+('o'<<8)+'a') /* FLOA */
	@@ -84701,10 +84827,32 @@
84701	aff = SQLITE_AFF_INTEGER;
84702	break;
84703	}
84704	}
84705






















84706	return aff;
84707	}
84708
84709	/*
84710	** This routine is called by the parser while in the middle of
	@@ -84722,11 +84870,11 @@
84722	p = pParse->pNewTable;
84723	if( p==0 \|\| NEVER(p->nCol<1) ) return;
84724	pCol = &p->aCol[p->nCol-1];
84725	assert( pCol->zType==0 );
84726	pCol->zType = sqlite3NameFromToken(pParse->db, pType);
84727	pCol->affinity = sqlite3AffinityType(pCol->zType);
84728	}
84729
84730	/*
84731	** The expression is the default value for the most recently added column
84732	** of the table currently under construction.
	@@ -85070,18 +85218,46 @@
85070	testcase( pCol->affinity==SQLITE_AFF_REAL );
85071
85072	zType = azType[pCol->affinity - SQLITE_AFF_TEXT];
85073	len = sqlite3Strlen30(zType);
85074	assert( pCol->affinity==SQLITE_AFF_NONE
85075	\|\| pCol->affinity==sqlite3AffinityType(zType) );
85076	memcpy(&zStmt[k], zType, len);
85077	k += len;
85078	assert( k<=n );
85079	}
85080	sqlite3_snprintf(n-k, &zStmt[k], "%s", zEnd);
85081	return zStmt;
85082	}




























85083
85084	/*
85085	** This routine is called to report the final ")" that terminates
85086	** a CREATE TABLE statement.
85087	**
	@@ -85105,13 +85281,14 @@
85105	Parse pParse, / Parse context */
85106	Token pCons, / The ',' token after the last column defn. */
85107	Token pEnd, / The final ')' token in the CREATE TABLE */
85108	Select pSelect / Select from a "CREATE ... AS SELECT" */
85109	){
85110	Table *p;
85111	sqlite3 *db = pParse->db;
85112	int iDb;

85113
85114	if( (pEnd==0 && pSelect==0) \|\| db->mallocFailed ){
85115	return;
85116	}
85117	p = pParse->pNewTable;
	@@ -85126,10 +85303,16 @@
85126	*/
85127	if( p->pCheck ){
85128	sqlite3ResolveSelfReference(pParse, p, NC_IsCheck, 0, p->pCheck);
85129	}
85130	#endif /* !defined(SQLITE_OMIT_CHECK) */






85131
85132	/* If the db->init.busy is 1 it means we are reading the SQL off the
85133	** "sqlite_master" or "sqlite_temp_master" table on the disk.
85134	** So do not write to the disk again. Extract the root page number
85135	** for the table from the db->init.newTnum field. (The page number
	@@ -86085,13 +86268,14 @@
86085	sqlite3 *db = pParse->db;
86086	Db pDb; / The specific table containing the indexed database */
86087	int iDb; /* Index of the database that is being written */
86088	Token pName = 0; / Unqualified name of the index to create */
86089	struct ExprList_item pListItem; / For looping over pList */
86090	int nCol;
86091	int nExtra = 0;
86092	char *zExtra;

86093
86094	assert( pParse->nErr==0 ); /* Never called with prior errors */
86095	if( db->mallocFailed \|\| IN_DECLARE_VTAB ){
86096	goto exit_create_index;
86097	}
	@@ -86314,11 +86498,10 @@
86314	** same column more than once cannot be an error because that would
86315	** break backwards compatibility - it needs to be a warning.
86316	*/
86317	for(i=0, pListItem=pList->a; i<pList->nExpr; i++, pListItem++){
86318	const char *zColName = pListItem->zName;
86319	Column *pTabCol;
86320	int requestedSortOrder;
86321	char zColl; / Collation sequence name */
86322
86323	for(j=0, pTabCol=pTab->aCol; j<pTab->nCol; j++, pTabCol++){
86324	if( sqlite3StrICmp(zColName, pTabCol->zName)==0 ) break;
	@@ -86351,10 +86534,11 @@
86351	requestedSortOrder = pListItem->sortOrder & sortOrderMask;
86352	pIndex->aSortOrder[i] = (u8)requestedSortOrder;
86353	if( pTab->aCol[j].notNull==0 ) pIndex->uniqNotNull = 0;
86354	}
86355	sqlite3DefaultRowEst(pIndex);

86356
86357	if( pTab==pParse->pNewTable ){
86358	/* This routine has been called to create an automatic index as a
86359	** result of a PRIMARY KEY or UNIQUE clause on a column definition, or
86360	** a PRIMARY KEY or UNIQUE clause following the column definitions.
	@@ -96379,30 +96563,34 @@
96379	break;
96380
96381	case PragTyp_INDEX_LIST: if( zRight ){
96382	Index *pIdx;
96383	Table *pTab;

96384	pTab = sqlite3FindTable(db, zRight, zDb);
96385	if( pTab ){
96386	v = sqlite3GetVdbe(pParse);
96387	pIdx = pTab->pIndex;
96388	if( pIdx ){
96389	int i = 0;
96390	sqlite3VdbeSetNumCols(v, 3);
96391	pParse->nMem = 3;
96392	sqlite3CodeVerifySchema(pParse, iDb);
96393	sqlite3VdbeSetColName(v, 0, COLNAME_NAME, "seq", SQLITE_STATIC);
96394	sqlite3VdbeSetColName(v, 1, COLNAME_NAME, "name", SQLITE_STATIC);
96395	sqlite3VdbeSetColName(v, 2, COLNAME_NAME, "unique", SQLITE_STATIC);
96396	while(pIdx){
96397	sqlite3VdbeAddOp2(v, OP_Integer, i, 1);
96398	sqlite3VdbeAddOp4(v, OP_String8, 0, 2, 0, pIdx->zName, 0);
96399	sqlite3VdbeAddOp2(v, OP_Integer, pIdx->onError!=OE_None, 3);
96400	sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 3);
96401	++i;
96402	pIdx = pIdx->pNext;
96403	}



96404	}
96405	}
96406	}
96407	break;
96408
	@@ -99086,10 +99274,13 @@
99086	}
99087
99088	/*
99089	** Return a pointer to a string containing the 'declaration type' of the
99090	** expression pExpr. The string may be treated as static by the caller.



99091	**
99092	** The declaration type is the exact datatype definition extracted from the
99093	** original CREATE TABLE statement if the expression is a column. The
99094	** declaration type for a ROWID field is INTEGER. Exactly when an expression
99095	** is considered a column can be complex in the presence of subqueries. The
	@@ -99100,25 +99291,40 @@
99100	** SELECT (SELECT col FROM tbl;
99101	** SELECT (SELECT col FROM tbl);
99102	** SELECT abc FROM (SELECT col AS abc FROM tbl);
99103	**
99104	** The declaration type for any expression other than a column is NULL.



99105	*/
99106	static const char *columnType(















99107	NameContext *pNC,
99108	Expr *pExpr,
99109	const char **pzOriginDb,
99110	const char **pzOriginTab,
99111	const char **pzOriginCol
99112	){

99113	char const *zType = 0;
99114	char const *zOriginDb = 0;
99115	char const *zOriginTab = 0;
99116	char const *zOriginCol = 0;
99117	int j;


99118	if( NEVER(pExpr==0) \|\| pNC->pSrcList==0 ) return 0;
99119
99120	switch( pExpr->op ){
99121	case TK_AGG_COLUMN:
99122	case TK_COLUMN: {
99123	/* The expression is a column. Locate the table the column is being
99124	** extracted from in NameContext.pSrcList. This table may be real
	@@ -99175,29 +99381,39 @@
99175	NameContext sNC;
99176	Expr *p = pS->pEList->a[iCol].pExpr;
99177	sNC.pSrcList = pS->pSrc;
99178	sNC.pNext = pNC;
99179	sNC.pParse = pNC->pParse;
99180	zType = columnType(&sNC, p, &zOriginDb, &zOriginTab, &zOriginCol);
99181	}
99182	}else if( ALWAYS(pTab->pSchema) ){
99183	/* A real table */
99184	assert( !pS );
99185	if( iCol<0 ) iCol = pTab->iPKey;
99186	assert( iCol==-1 \|\| (iCol>=0 && iCol<pTab->nCol) );

99187	if( iCol<0 ){
99188	zType = "INTEGER";
99189	zOriginCol = "rowid";
99190	}else{
99191	zType = pTab->aCol[iCol].zType;
99192	zOriginCol = pTab->aCol[iCol].zName;

99193	}
99194	zOriginTab = pTab->zName;
99195	if( pNC->pParse ){
99196	int iDb = sqlite3SchemaToIndex(pNC->pParse->db, pTab->pSchema);
99197	zOriginDb = pNC->pParse->db->aDb[iDb].zName;
99198	}








99199	}
99200	break;
99201	}
99202	#ifndef SQLITE_OMIT_SUBQUERY
99203	case TK_SELECT: {
	@@ -99210,22 +99426,25 @@
99210	Expr *p = pS->pEList->a[0].pExpr;
99211	assert( ExprHasProperty(pExpr, EP_xIsSelect) );
99212	sNC.pSrcList = pS->pSrc;
99213	sNC.pNext = pNC;
99214	sNC.pParse = pNC->pParse;
99215	zType = columnType(&sNC, p, &zOriginDb, &zOriginTab, &zOriginCol);
99216	break;
99217	}
99218	#endif
99219	}
99220
99221	if( pzOriginDb ){
99222	assert( pzOriginTab && pzOriginCol );
99223	*pzOriginDb = zOriginDb;
99224	*pzOriginTab = zOriginTab;
99225	*pzOriginCol = zOriginCol;

99226	}


99227	return zType;
99228	}
99229
99230	/*
99231	** Generate code that will tell the VDBE the declaration types of columns
	@@ -99247,25 +99466,25 @@
99247	const char *zType;
99248	#ifdef SQLITE_ENABLE_COLUMN_METADATA
99249	const char *zOrigDb = 0;
99250	const char *zOrigTab = 0;
99251	const char *zOrigCol = 0;
99252	zType = columnType(&sNC, p, &zOrigDb, &zOrigTab, &zOrigCol);
99253
99254	/* The vdbe must make its own copy of the column-type and other
99255	** column specific strings, in case the schema is reset before this
99256	** virtual machine is deleted.
99257	*/
99258	sqlite3VdbeSetColName(v, i, COLNAME_DATABASE, zOrigDb, SQLITE_TRANSIENT);
99259	sqlite3VdbeSetColName(v, i, COLNAME_TABLE, zOrigTab, SQLITE_TRANSIENT);
99260	sqlite3VdbeSetColName(v, i, COLNAME_COLUMN, zOrigCol, SQLITE_TRANSIENT);
99261	#else
99262	zType = columnType(&sNC, p, 0, 0, 0);
99263	#endif
99264	sqlite3VdbeSetColName(v, i, COLNAME_DECLTYPE, zType, SQLITE_TRANSIENT);
99265	}
99266	#endif /* SQLITE_OMIT_DECLTYPE */
99267	}
99268
99269	/*
99270	** Generate code that will tell the VDBE the names of columns
99271	** in the result set. This information is used to provide the
	@@ -99450,39 +99669,41 @@
99450	** This routine requires that all identifiers in the SELECT
99451	** statement be resolved.
99452	*/
99453	static void selectAddColumnTypeAndCollation(
99454	Parse pParse, / Parsing contexts */
99455	int nCol, /* Number of columns */
99456	Column aCol, / List of columns */
99457	Select pSelect / SELECT used to determine types and collations */
99458	){
99459	sqlite3 *db = pParse->db;
99460	NameContext sNC;
99461	Column *pCol;
99462	CollSeq *pColl;
99463	int i;
99464	Expr *p;
99465	struct ExprList_item *a;

99466
99467	assert( pSelect!=0 );
99468	assert( (pSelect->selFlags & SF_Resolved)!=0 );
99469	assert( nCol==pSelect->pEList->nExpr \|\| db->mallocFailed );
99470	if( db->mallocFailed ) return;
99471	memset(&sNC, 0, sizeof(sNC));
99472	sNC.pSrcList = pSelect->pSrc;
99473	a = pSelect->pEList->a;
99474	for(i=0, pCol=aCol; i<nCol; i++, pCol++){
99475	p = a[i].pExpr;
99476	pCol->zType = sqlite3DbStrDup(db, columnType(&sNC, p, 0, 0, 0));

99477	pCol->affinity = sqlite3ExprAffinity(p);
99478	if( pCol->affinity==0 ) pCol->affinity = SQLITE_AFF_NONE;
99479	pColl = sqlite3ExprCollSeq(pParse, p);
99480	if( pColl ){
99481	pCol->zColl = sqlite3DbStrDup(db, pColl->zName);
99482	}
99483	}

99484	}
99485
99486	/*
99487	** Given a SELECT statement, generate a Table structure that describes
99488	** the result set of that SELECT.
	@@ -99506,13 +99727,13 @@
99506	/* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside
99507	** is disabled */
99508	assert( db->lookaside.bEnabled==0 );
99509	pTab->nRef = 1;
99510	pTab->zName = 0;
99511	pTab->nRowEst = 1000000;
99512	selectColumnsFromExprList(pParse, pSelect->pEList, &pTab->nCol, &pTab->aCol);
99513	selectAddColumnTypeAndCollation(pParse, pTab->nCol, pTab->aCol, pSelect);
99514	pTab->iPKey = -1;
99515	if( db->mallocFailed ){
99516	sqlite3DeleteTable(db, pTab);
99517	return 0;
99518	}
	@@ -101420,15 +101641,15 @@
101420	assert( pFrom->pTab==0 );
101421	sqlite3WalkSelect(pWalker, pSel);
101422	pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));
101423	if( pTab==0 ) return WRC_Abort;
101424	pTab->nRef = 1;
101425	pTab->zName = sqlite3MPrintf(db, "sqlite_subquery_%p_", (void*)pTab);
101426	while( pSel->pPrior ){ pSel = pSel->pPrior; }
101427	selectColumnsFromExprList(pParse, pSel->pEList, &pTab->nCol, &pTab->aCol);
101428	pTab->iPKey = -1;
101429	pTab->nRowEst = 1000000;
101430	pTab->tabFlags \|= TF_Ephemeral;
101431	#endif
101432	}else{
101433	/* An ordinary table or view name in the FROM clause */
101434	assert( pFrom->pTab==0 );
	@@ -101708,11 +101929,11 @@
101708	if( ALWAYS(pTab!=0) && (pTab->tabFlags & TF_Ephemeral)!=0 ){
101709	/* A sub-query in the FROM clause of a SELECT */
101710	Select *pSel = pFrom->pSelect;
101711	assert( pSel );
101712	while( pSel->pPrior ) pSel = pSel->pPrior;
101713	selectAddColumnTypeAndCollation(pParse, pTab->nCol, pTab->aCol, pSel);
101714	}
101715	}
101716	}
101717	return WRC_Continue;
101718	}
	@@ -102623,17 +102844,11 @@
102623	int iRoot = pTab->tnum; /* Root page of scanned b-tree */
102624
102625	sqlite3CodeVerifySchema(pParse, iDb);
102626	sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
102627
102628	/* Search for the index that has the least amount of columns. If
102629	** there is such an index, and it has less columns than the table
102630	** does, then we can assume that it consumes less space on disk and
102631	** will therefore be cheaper to scan to determine the query result.
102632	** In this case set iRoot to the root page number of the index b-tree
102633	** and pKeyInfo to the KeyInfo structure required to navigate the
102634	** index.
102635	**
102636	** (2011-04-15) Do not do a full scan of an unordered index.
102637	**
102638	** (2013-10-03) Do not count the entires in a partial index.
102639	**
	@@ -102640,17 +102855,18 @@
102640	** In practice the KeyInfo structure will not be used. It is only
102641	** passed to keep OP_OpenRead happy.
102642	*/
102643	for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
102644	if( pIdx->bUnordered==0

102645	&& pIdx->pPartIdxWhere==0
102646	&& (!pBest \|\| pIdx->nColumn<pBest->nColumn)
102647	){
102648	pBest = pIdx;
102649	}
102650	}
102651	if( pBest && pBest->nColumn<pTab->nCol ){
102652	iRoot = pBest->tnum;
102653	pKeyInfo = sqlite3IndexKeyinfo(pParse, pBest);
102654	}
102655
102656	/* Open a read-only cursor, execute the OP_Count, close the cursor. */
	@@ -106406,30 +106622,10 @@
106406	typedef struct WhereLoopBuilder WhereLoopBuilder;
106407	typedef struct WhereScan WhereScan;
106408	typedef struct WhereOrCost WhereOrCost;
106409	typedef struct WhereOrSet WhereOrSet;
106410
106411	/*
106412	** Cost X is tracked as 10*log2(X) stored in a 16-bit integer. The
106413	** maximum cost for ordinary tables is 64(2*63) which becomes 6900.
106414	** (Virtual tables can return a larger cost, but let's assume they do not.)
106415	** So all costs can be stored in a 16-bit integer without risk
106416	** of overflow.
106417	**
106418	** Costs are estimates, so no effort is made to compute 10*log2(X) exactly.
106419	** Instead, a close estimate is used. Any value of X=1 is stored as 0.
106420	** X=2 is 10. X=3 is 16. X=1000 is 99. etc. Negative values are allowed.
106421	** A WhereCost of -10 means 0.5. WhereCost of -20 means 0.25. And so forth.
106422	**
106423	** The tool/wherecosttest.c source file implements a command-line program
106424	** that will convert WhereCosts to integers, convert integers to WhereCosts
106425	** and do addition and multiplication on WhereCost values. The wherecosttest
106426	** command-line program is a useful utility to have around when working with
106427	** this module.
106428	*/
106429	typedef short int WhereCost;
106430
106431	/*
106432	** This object contains information needed to implement a single nested
106433	** loop in WHERE clause.
106434	**
106435	** Contrast this object with WhereLoop. This object describes the
	@@ -106490,13 +106686,13 @@
106490	#ifdef SQLITE_DEBUG
106491	char cId; /* Symbolic ID of this loop for debugging use */
106492	#endif
106493	u8 iTab; /* Position in FROM clause of table for this loop */
106494	u8 iSortIdx; /* Sorting index number. 0==None */
106495	WhereCost rSetup; /* One-time setup cost (ex: create transient index) */
106496	WhereCost rRun; /* Cost of running each loop */
106497	WhereCost nOut; /* Estimated number of output rows */
106498	union {
106499	struct { /* Information for internal btree tables */
106500	int nEq; /* Number of equality constraints */
106501	Index pIndex; / Index used, or NULL */
106502	} btree;
	@@ -106522,12 +106718,12 @@
106522	** subquery on one operand of an OR operator in the WHERE clause.
106523	** See WhereOrSet for additional information
106524	*/
106525	struct WhereOrCost {
106526	Bitmask prereq; /* Prerequisites */
106527	WhereCost rRun; /* Cost of running this subquery */
106528	WhereCost nOut; /* Number of outputs for this subquery */
106529	};
106530
106531	/* The WhereOrSet object holds a set of possible WhereOrCosts that
106532	** correspond to the subquery(s) of OR-clause processing. Only the
106533	** best N_OR_COST elements are retained.
	@@ -106561,12 +106757,12 @@
106561	** at the end is the choosen query plan.
106562	*/
106563	struct WherePath {
106564	Bitmask maskLoop; /* Bitmask of all WhereLoop objects in this path */
106565	Bitmask revLoop; /* aLoop[]s that should be reversed for ORDER BY */
106566	WhereCost nRow; /* Estimated number of rows generated by this path */
106567	WhereCost rCost; /* Total cost of this path */
106568	u8 isOrdered; /* True if this path satisfies ORDER BY */
106569	u8 isOrderedValid; /* True if the isOrdered field is valid */
106570	WhereLoop *aLoop; / Array of WhereLoop objects implementing this path */
106571	};
106572
	@@ -106628,11 +106824,11 @@
106628	union {
106629	int leftColumn; /* Column number of X in "X <op> <expr>" */
106630	WhereOrInfo pOrInfo; / Extra information if (eOperator & WO_OR)!=0 */
106631	WhereAndInfo pAndInfo; / Extra information if (eOperator& WO_AND)!=0 */
106632	} u;
106633	WhereCost truthProb; /* Probability of truth for this expression */
106634	u16 eOperator; /* A WO_xx value describing <op> */
106635	u8 wtFlags; /* TERM_xxx bit flags. See below */
106636	u8 nChild; /* Number of children that must disable us */
106637	WhereClause pWC; / The clause this term is part of */
106638	Bitmask prereqRight; /* Bitmask of tables used by pExpr->pRight */
	@@ -106776,11 +106972,11 @@
106776	SrcList pTabList; / List of tables in the join */
106777	ExprList pOrderBy; / The ORDER BY clause or NULL */
106778	ExprList pResultSet; / Result set. DISTINCT operates on these */
106779	WhereLoop pLoops; / List of all WhereLoop objects */
106780	Bitmask revMask; /* Mask of ORDER BY terms that need reversing */
106781	WhereCost nRowOut; /* Estimated number of output rows */
106782	u16 wctrlFlags; /* Flags originally passed to sqlite3WhereBegin() */
106783	u8 bOBSat; /* ORDER BY satisfied by indices */
106784	u8 okOnePass; /* Ok to use one-pass algorithm for UPDATE/DELETE */
106785	u8 untestedTerms; /* Not all WHERE terms resolved by outer loop */
106786	u8 eDistinct; /* One of the WHERE_DISTINCT_* values below */
	@@ -106836,30 +107032,15 @@
106836	#define WHERE_IN_ABLE 0x00000800 /* Able to support an IN operator */
106837	#define WHERE_ONEROW 0x00001000 /* Selects no more than one row */
106838	#define WHERE_MULTI_OR 0x00002000 /* OR using multiple indices */
106839	#define WHERE_AUTO_INDEX 0x00004000 /* Uses an ephemeral index */
106840
106841
106842	/* Convert a WhereCost value (10 times log2(X)) into its integer value X.
106843	** A rough approximation is used. The value returned is not exact.
106844	*/
106845	static u64 whereCostToInt(WhereCost x){
106846	u64 n;
106847	if( x<10 ) return 1;
106848	n = x%10;
106849	x /= 10;
106850	if( n>=5 ) n -= 2;
106851	else if( n>=1 ) n -= 1;
106852	if( x>=3 ) return (n+8)<<(x-3);
106853	return (n+8)>>(3-x);
106854	}
106855
106856	/*
106857	** Return the estimated number of output rows from a WHERE clause
106858	*/
106859	SQLITE_PRIVATE u64 sqlite3WhereOutputRowCount(WhereInfo *pWInfo){
106860	return whereCostToInt(pWInfo->nRowOut);
106861	}
106862
106863	/*
106864	** Return one of the WHERE_DISTINCT_xxxxx values to indicate how this
106865	** WHERE clause returns outputs for DISTINCT processing.
	@@ -106917,12 +107098,12 @@
106917	** so that pSet keeps the N_OR_COST best entries seen so far.
106918	*/
106919	static int whereOrInsert(
106920	WhereOrSet pSet, / The WhereOrSet to be updated */
106921	Bitmask prereq, /* Prerequisites of the new entry */
106922	WhereCost rRun, /* Run-cost of the new entry */
106923	WhereCost nOut /* Number of outputs for the new entry */
106924	){
106925	u16 i;
106926	WhereOrCost *p;
106927	for(i=pSet->n, p=pSet->a; i>0; i--, p++){
106928	if( rRun<=p->rRun && (prereq & p->prereq)==prereq ){
	@@ -107003,13 +107184,10 @@
107003	if( pWC->a!=pWC->aStatic ){
107004	sqlite3DbFree(db, pWC->a);
107005	}
107006	}
107007
107008	/* Forward declaration */
107009	static WhereCost whereCost(tRowcnt x);
107010
107011	/*
107012	** Add a single new WhereTerm entry to the WhereClause object pWC.
107013	** The new WhereTerm object is constructed from Expr p and with wtFlags.
107014	** The index in pWC->a[] of the new WhereTerm is returned on success.
107015	** 0 is returned if the new WhereTerm could not be added due to a memory
	@@ -107048,11 +107226,11 @@
107048	}
107049	pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
107050	}
107051	pTerm = &pWC->a[idx = pWC->nTerm++];
107052	if( p && ExprHasProperty(p, EP_Unlikely) ){
107053	pTerm->truthProb = whereCost(p->iTable) - 99;
107054	}else{
107055	pTerm->truthProb = -1;
107056	}
107057	pTerm->pExpr = sqlite3ExprSkipCollate(p);
107058	pTerm->wtFlags = wtFlags;
	@@ -108312,79 +108490,16 @@
108312	}
108313
108314	return 0;
108315	}
108316
108317	/*
108318	** Find (an approximate) sum of two WhereCosts. This computation is
108319	** not a simple "+" operator because WhereCost is stored as a logarithmic
108320	** value.
108321	**
108322	*/
108323	static WhereCost whereCostAdd(WhereCost a, WhereCost b){
108324	static const unsigned char x[] = {
108325	10, 10, /* 0,1 */
108326	9, 9, /* 2,3 */
108327	8, 8, /* 4,5 */
108328	7, 7, 7, /* 6,7,8 */
108329	6, 6, 6, /* 9,10,11 */
108330	5, 5, 5, /* 12-14 */
108331	4, 4, 4, 4, /* 15-18 */
108332	3, 3, 3, 3, 3, 3, /* 19-24 */
108333	2, 2, 2, 2, 2, 2, 2, /* 25-31 */
108334	};
108335	if( a>=b ){
108336	if( a>b+49 ) return a;
108337	if( a>b+31 ) return a+1;
108338	return a+x[a-b];
108339	}else{
108340	if( b>a+49 ) return b;
108341	if( b>a+31 ) return b+1;
108342	return b+x[b-a];
108343	}
108344	}
108345
108346	/*
108347	** Convert an integer into a WhereCost. In other words, compute a
108348	** good approximatation for 10*log2(x).
108349	*/
108350	static WhereCost whereCost(tRowcnt x){
108351	static WhereCost a[] = { 0, 2, 3, 5, 6, 7, 8, 9 };
108352	WhereCost y = 40;
108353	if( x<8 ){
108354	if( x<2 ) return 0;
108355	while( x<8 ){ y -= 10; x <<= 1; }
108356	}else{
108357	while( x>255 ){ y += 40; x >>= 4; }
108358	while( x>15 ){ y += 10; x >>= 1; }
108359	}
108360	return a[x&7] + y - 10;
108361	}
108362
108363	#ifndef SQLITE_OMIT_VIRTUALTABLE
108364	/*
108365	** Convert a double (as received from xBestIndex of a virtual table)
108366	** into a WhereCost. In other words, compute an approximation for
108367	** 10*log2(x).
108368	*/
108369	static WhereCost whereCostFromDouble(double x){
108370	u64 a;
108371	WhereCost e;
108372	assert( sizeof(x)==8 && sizeof(a)==8 );
108373	if( x<=1 ) return 0;
108374	if( x<=2000000000 ) return whereCost((tRowcnt)x);
108375	memcpy(&a, &x, 8);
108376	e = (a>>52) - 1022;
108377	return e*10;
108378	}
108379	#endif /* SQLITE_OMIT_VIRTUALTABLE */
108380
108381	/*
108382	** Estimate the logarithm of the input value to base 2.
108383	*/
108384	static WhereCost estLog(WhereCost N){
108385	WhereCost x = whereCost(N);
108386	return x>33 ? x - 33 : 0;
108387	}
108388
108389	/*
108390	** Two routines for printing the content of an sqlite3_index_info
	@@ -108893,11 +109008,11 @@
108893	**
108894	** ... FROM t1 WHERE a > ? AND a < ? ...
108895	**
108896	** then nEq is set to 0.
108897	**
108898	** When this function is called, *pnOut is set to the whereCost() of the
108899	** number of rows that the index scan is expected to visit without
108900	** considering the range constraints. If nEq is 0, this is the number of
108901	** rows in the index. Assuming no error occurs, *pnOut is adjusted (reduced)
108902	** to account for the range contraints pLower and pUpper.
108903	**
	@@ -108909,19 +109024,19 @@
108909	static int whereRangeScanEst(
108910	Parse pParse, / Parsing & code generating context */
108911	WhereLoopBuilder *pBuilder,
108912	WhereTerm pLower, / Lower bound on the range. ex: "x>123" Might be NULL */
108913	WhereTerm pUpper, / Upper bound on the range. ex: "x<455" Might be NULL */
108914	WhereCost pnOut / IN/OUT: Number of rows visited */
108915	){
108916	int rc = SQLITE_OK;
108917	int nOut = (int)*pnOut;
108918	WhereCost nNew;

108919
108920	#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
108921	Index *p = pBuilder->pNew->u.btree.pIndex;
108922	int nEq = pBuilder->pNew->u.btree.nEq;
108923
108924	if( p->nSample>0
108925	&& nEq==pBuilder->nRecValid
108926	&& nEq<p->nSampleCol
108927	&& OptimizationEnabled(pParse->db, SQLITE_Stat3)
	@@ -108998,18 +109113,18 @@
108998	}
108999
109000	pBuilder->pRec = pRec;
109001	if( rc==SQLITE_OK ){
109002	if( iUpper>iLower ){
109003	nNew = whereCost(iUpper - iLower);
109004	}else{
109005	nNew = 10; assert( 10==whereCost(2) );
109006	}
109007	if( nNew<nOut ){
109008	nOut = nNew;
109009	}
109010	*pnOut = (WhereCost)nOut;
109011	WHERETRACE(0x100, ("range scan regions: %u..%u est=%d\n",
109012	(u32)iLower, (u32)iUpper, nOut));
109013	return SQLITE_OK;
109014	}
109015	}
	@@ -109020,20 +109135,20 @@
109020	assert( pLower \|\| pUpper );
109021	/* TUNING: Each inequality constraint reduces the search space 4-fold.
109022	** A BETWEEN operator, therefore, reduces the search space 16-fold */
109023	nNew = nOut;
109024	if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ){
109025	nNew -= 20; assert( 20==whereCost(4) );
109026	nOut--;
109027	}
109028	if( pUpper ){
109029	nNew -= 20; assert( 20==whereCost(4) );
109030	nOut--;
109031	}
109032	if( nNew<10 ) nNew = 10;
109033	if( nNew<nOut ) nOut = nNew;
109034	*pnOut = (WhereCost)nOut;
109035	return rc;
109036	}
109037
109038	#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
109039	/*
	@@ -110673,11 +110788,11 @@
110673	*/
110674	static int whereLoopAddBtreeIndex(
110675	WhereLoopBuilder pBuilder, / The WhereLoop factory */
110676	struct SrcList_item pSrc, / FROM clause term being analyzed */
110677	Index pProbe, / An index on pSrc */
110678	WhereCost nInMul /* log(Number of iterations due to IN) */
110679	){
110680	WhereInfo pWInfo = pBuilder->pWInfo; / WHERE analyse context */
110681	Parse pParse = pWInfo->pParse; / Parsing context */
110682	sqlite3 db = pParse->db; / Database connection malloc context */
110683	WhereLoop pNew; / Template WhereLoop under construction */
	@@ -110686,15 +110801,15 @@
110686	WhereScan scan; /* Iterator for WHERE terms */
110687	Bitmask saved_prereq; /* Original value of pNew->prereq */
110688	u16 saved_nLTerm; /* Original value of pNew->nLTerm */
110689	int saved_nEq; /* Original value of pNew->u.btree.nEq */
110690	u32 saved_wsFlags; /* Original value of pNew->wsFlags */
110691	WhereCost saved_nOut; /* Original value of pNew->nOut */
110692	int iCol; /* Index of the column in the table */
110693	int rc = SQLITE_OK; /* Return code */
110694	WhereCost nRowEst; /* Estimated index selectivity */
110695	WhereCost rLogSize; /* Logarithm of table size */
110696	WhereTerm pTop = 0, pBtm = 0; /* Top and bottom range constraints */
110697
110698	pNew = pBuilder->pNew;
110699	if( db->mallocFailed ) return SQLITE_NOMEM;
110700
	@@ -110710,11 +110825,11 @@
110710	if( pProbe->bUnordered ) opMask &= ~(WO_GT\|WO_GE\|WO_LT\|WO_LE);
110711
110712	assert( pNew->u.btree.nEq<=pProbe->nColumn );
110713	if( pNew->u.btree.nEq < pProbe->nColumn ){
110714	iCol = pProbe->aiColumn[pNew->u.btree.nEq];
110715	nRowEst = whereCost(pProbe->aiRowEst[pNew->u.btree.nEq+1]);
110716	if( nRowEst==0 && pProbe->onError==OE_None ) nRowEst = 1;
110717	}else{
110718	iCol = -1;
110719	nRowEst = 0;
110720	}
	@@ -110724,11 +110839,11 @@
110724	saved_nLTerm = pNew->nLTerm;
110725	saved_wsFlags = pNew->wsFlags;
110726	saved_prereq = pNew->prereq;
110727	saved_nOut = pNew->nOut;
110728	pNew->rSetup = 0;
110729	rLogSize = estLog(whereCost(pProbe->aiRowEst[0]));
110730	for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
110731	int nIn = 0;
110732	#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
110733	int nRecValid = pBuilder->nRecValid;
110734	#endif
	@@ -110751,14 +110866,14 @@
110751	if( pTerm->eOperator & WO_IN ){
110752	Expr *pExpr = pTerm->pExpr;
110753	pNew->wsFlags \|= WHERE_COLUMN_IN;
110754	if( ExprHasProperty(pExpr, EP_xIsSelect) ){
110755	/* "x IN (SELECT ...)": TUNING: the SELECT returns 25 rows */
110756	nIn = 46; assert( 46==whereCost(25) );
110757	}else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
110758	/* "x IN (value, value, ...)" */
110759	nIn = whereCost(pExpr->x.pList->nExpr);
110760	}
110761	pNew->rRun += nIn;
110762	pNew->u.btree.nEq++;
110763	pNew->nOut = nRowEst + nInMul + nIn;
110764	}else if( pTerm->eOperator & (WO_EQ) ){
	@@ -110776,11 +110891,11 @@
110776	pNew->nOut = nRowEst + nInMul;
110777	}else if( pTerm->eOperator & (WO_ISNULL) ){
110778	pNew->wsFlags \|= WHERE_COLUMN_NULL;
110779	pNew->u.btree.nEq++;
110780	/* TUNING: IS NULL selects 2 rows */
110781	nIn = 10; assert( 10==whereCost(2) );
110782	pNew->nOut = nRowEst + nInMul + nIn;
110783	}else if( pTerm->eOperator & (WO_GT\|WO_GE) ){
110784	testcase( pTerm->eOperator & WO_GT );
110785	testcase( pTerm->eOperator & WO_GE );
110786	pNew->wsFlags \|= WHERE_COLUMN_RANGE\|WHERE_BTM_LIMIT;
	@@ -110796,11 +110911,11 @@
110796	pNew->aLTerm[pNew->nLTerm-2] : 0;
110797	}
110798	if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
110799	/* Adjust nOut and rRun for STAT3 range values */
110800	assert( pNew->nOut==saved_nOut );
110801	whereRangeScanEst(pParse, pBuilder, pBtm, pTop, &pNew->nOut);
110802	}
110803	#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
110804	if( nInMul==0
110805	&& pProbe->nSample
110806	&& pNew->u.btree.nEq<=pProbe->nSampleCol
	@@ -110816,22 +110931,22 @@
110816	&& !ExprHasProperty(pExpr, EP_xIsSelect) ){
110817	rc = whereInScanEst(pParse, pBuilder, pExpr->x.pList, &nOut);
110818	}
110819	assert( nOut==0 \|\| rc==SQLITE_OK );
110820	if( nOut ){
110821	nOut = whereCost(nOut);
110822	pNew->nOut = MIN(nOut, saved_nOut);
110823	}
110824	}
110825	#endif
110826	if( (pNew->wsFlags & (WHERE_IDX_ONLY\|WHERE_IPK))==0 ){
110827	/* Each row involves a step of the index, then a binary search of
110828	** the main table */
110829	pNew->rRun = whereCostAdd(pNew->rRun, rLogSize>27 ? rLogSize-17 : 10);
110830	}
110831	/* Step cost for each output row */
110832	pNew->rRun = whereCostAdd(pNew->rRun, pNew->nOut);
110833	whereLoopOutputAdjust(pBuilder->pWC, pNew, pSrc->iCursor);
110834	rc = whereLoopInsert(pBuilder, pNew);
110835	if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
110836	&& pNew->u.btree.nEq<(pProbe->nColumn + (pProbe->zName!=0))
110837	){
	@@ -110927,18 +111042,20 @@
110927	struct SrcList_item pSrc; / The FROM clause btree term to add */
110928	WhereLoop pNew; / Template WhereLoop object */
110929	int rc = SQLITE_OK; /* Return code */
110930	int iSortIdx = 1; /* Index number */
110931	int b; /* A boolean value */
110932	WhereCost rSize; /* number of rows in the table */
110933	WhereCost rLogSize; /* Logarithm of the number of rows in the table */
110934	WhereClause pWC; / The parsed WHERE clause */

110935
110936	pNew = pBuilder->pNew;
110937	pWInfo = pBuilder->pWInfo;
110938	pTabList = pWInfo->pTabList;
110939	pSrc = pTabList->a + pNew->iTab;

110940	pWC = pBuilder->pWC;
110941	assert( !IsVirtual(pSrc->pTab) );
110942
110943	if( pSrc->pIndex ){
110944	/* An INDEXED BY clause specifies a particular index to use */
	@@ -110952,22 +111069,22 @@
110952	memset(&sPk, 0, sizeof(Index));
110953	sPk.nColumn = 1;
110954	sPk.aiColumn = &aiColumnPk;
110955	sPk.aiRowEst = aiRowEstPk;
110956	sPk.onError = OE_Replace;
110957	sPk.pTable = pSrc->pTab;
110958	aiRowEstPk[0] = pSrc->pTab->nRowEst;
110959	aiRowEstPk[1] = 1;
110960	pFirst = pSrc->pTab->pIndex;
110961	if( pSrc->notIndexed==0 ){
110962	/* The real indices of the table are only considered if the
110963	** NOT INDEXED qualifier is omitted from the FROM clause */
110964	sPk.pNext = pFirst;
110965	}
110966	pProbe = &sPk;
110967	}
110968	rSize = whereCost(pSrc->pTab->nRowEst);
110969	rLogSize = estLog(rSize);
110970
110971	#ifndef SQLITE_OMIT_AUTOMATIC_INDEX
110972	/* Automatic indexes */
110973	if( !pBuilder->pOrSet
	@@ -110988,17 +111105,17 @@
110988	pNew->nLTerm = 1;
110989	pNew->aLTerm[0] = pTerm;
110990	/* TUNING: One-time cost for computing the automatic index is
110991	** approximately 7Nlog2(N) where N is the number of rows in
110992	** the table being indexed. */
110993	pNew->rSetup = rLogSize + rSize + 28; assert( 28==whereCost(7) );
110994	/* TUNING: Each index lookup yields 20 rows in the table. This
110995	** is more than the usual guess of 10 rows, since we have no way
110996	** of knowning how selective the index will ultimately be. It would
110997	** not be unreasonable to make this value much larger. */
110998	pNew->nOut = 43; assert( 43==whereCost(20) );
110999	pNew->rRun = whereCostAdd(rLogSize,pNew->nOut);
111000	pNew->wsFlags = WHERE_AUTO_INDEX;
111001	pNew->prereq = mExtra \| pTerm->prereqRight;
111002	rc = whereLoopInsert(pBuilder, pNew);
111003	}
111004	}
	@@ -111028,14 +111145,12 @@
111028
111029	/* Full table scan */
111030	pNew->iSortIdx = b ? iSortIdx : 0;
111031	/* TUNING: Cost of full table scan is 3*(N + log2(N)).
111032	** + The extra 3 factor is to encourage the use of indexed lookups
111033	** over full scans. A smaller constant 2 is used for covering
111034	** index scans so that a covering index scan will be favored over
111035	** a table scan. */
111036	pNew->rRun = whereCostAdd(rSize,rLogSize) + 16;
111037	whereLoopOutputAdjust(pWC, pNew, pSrc->iCursor);
111038	rc = whereLoopInsert(pBuilder, pNew);
111039	pNew->nOut = rSize;
111040	if( rc ) break;
111041	}else{
	@@ -111044,26 +111159,25 @@
111044
111045	/* Full scan via index */
111046	if( b
111047	\|\| ( m==0
111048	&& pProbe->bUnordered==0

111049	&& (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
111050	&& sqlite3GlobalConfig.bUseCis
111051	&& OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
111052	)
111053	){
111054	pNew->iSortIdx = b ? iSortIdx : 0;
111055	if( m==0 ){
111056	/* TUNING: Cost of a covering index scan is 2*(N + log2(N)).
111057	** + The extra 2 factor is to encourage the use of indexed lookups
111058	** over index scans. A table scan uses a factor of 3 so that
111059	** index scans are favored over table scans.
111060	** + If this covering index might also help satisfy the ORDER BY
111061	** clause, then the cost is fudged down slightly so that this
111062	** index is favored above other indices that have no hope of
111063	** helping with the ORDER BY. */
111064	pNew->rRun = 10 + whereCostAdd(rSize,rLogSize) - b;
111065	}else{
111066	assert( b!=0 );
111067	/* TUNING: Cost of scanning a non-covering index is (N+1)*log2(N)
111068	** which we will simplify to just Nlog2(N) /
111069	pNew->rRun = rSize + rLogSize;
	@@ -111237,13 +111351,13 @@
111237	pIdxInfo->needToFreeIdxStr = 0;
111238	pNew->u.vtab.idxStr = pIdxInfo->idxStr;
111239	pNew->u.vtab.isOrdered = (u8)((pIdxInfo->nOrderBy!=0)
111240	&& pIdxInfo->orderByConsumed);
111241	pNew->rSetup = 0;
111242	pNew->rRun = whereCostFromDouble(pIdxInfo->estimatedCost);
111243	/* TUNING: Every virtual table query returns 25 rows */
111244	pNew->nOut = 46; assert( 46==whereCost(25) );
111245	whereLoopInsert(pBuilder, pNew);
111246	if( pNew->u.vtab.needFree ){
111247	sqlite3_free(pNew->u.vtab.idxStr);
111248	pNew->u.vtab.needFree = 0;
111249	}
	@@ -111276,10 +111390,12 @@
111276	pWC = pBuilder->pWC;
111277	if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK;
111278	pWCEnd = pWC->a + pWC->nTerm;
111279	pNew = pBuilder->pNew;
111280	memset(&sSum, 0, sizeof(sSum));


111281
111282	for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){
111283	if( (pTerm->eOperator & WO_OR)!=0
111284	&& (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0
111285	){
	@@ -111287,12 +111403,10 @@
111287	WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
111288	WhereTerm *pOrTerm;
111289	int once = 1;
111290	int i, j;
111291
111292	pItem = pWInfo->pTabList->a + pNew->iTab;
111293	iCur = pItem->iCursor;
111294	sSubBuild = *pBuilder;
111295	sSubBuild.pOrderBy = 0;
111296	sSubBuild.pOrSet = &sCur;
111297
111298	for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
	@@ -111329,12 +111443,12 @@
111329	whereOrMove(&sPrev, &sSum);
111330	sSum.n = 0;
111331	for(i=0; i<sPrev.n; i++){
111332	for(j=0; j<sCur.n; j++){
111333	whereOrInsert(&sSum, sPrev.a[i].prereq \| sCur.a[j].prereq,
111334	whereCostAdd(sPrev.a[i].rRun, sCur.a[j].rRun),
111335	whereCostAdd(sPrev.a[i].nOut, sCur.a[j].nOut));
111336	}
111337	}
111338	}
111339	}
111340	pNew->nLTerm = 1;
	@@ -111668,23 +111782,23 @@
111668	** costs if nRowEst==0.
111669	**
111670	** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
111671	** error occurs.
111672	*/
111673	static int wherePathSolver(WhereInfo *pWInfo, WhereCost nRowEst){
111674	int mxChoice; /* Maximum number of simultaneous paths tracked */
111675	int nLoop; /* Number of terms in the join */
111676	Parse pParse; / Parsing context */
111677	sqlite3 db; / The database connection */
111678	int iLoop; /* Loop counter over the terms of the join */
111679	int ii, jj; /* Loop counters */
111680	int mxI = 0; /* Index of next entry to replace */
111681	WhereCost rCost; /* Cost of a path */
111682	WhereCost nOut; /* Number of outputs */
111683	WhereCost mxCost = 0; /* Maximum cost of a set of paths */
111684	WhereCost mxOut = 0; /* Maximum nOut value on the set of paths */
111685	WhereCost rSortCost; /* Cost to do a sort */
111686	int nTo, nFrom; /* Number of valid entries in aTo[] and aFrom[] */
111687	WherePath aFrom; / All nFrom paths at the previous level */
111688	WherePath aTo; / The nTo best paths at the current level */
111689	WherePath pFrom; / An element of aFrom[] that we are working on */
111690	WherePath pTo; / An element of aTo[] that we are working on */
	@@ -111717,21 +111831,23 @@
111717	/* Seed the search with a single WherePath containing zero WhereLoops.
111718	**
111719	** TUNING: Do not let the number of iterations go above 25. If the cost
111720	** of computing an automatic index is not paid back within the first 25
111721	** rows, then do not use the automatic index. */
111722	aFrom[0].nRow = MIN(pParse->nQueryLoop, 46); assert( 46==whereCost(25) );
111723	nFrom = 1;
111724
111725	/* Precompute the cost of sorting the final result set, if the caller
111726	** to sqlite3WhereBegin() was concerned about sorting */
111727	rSortCost = 0;
111728	if( pWInfo->pOrderBy==0 \|\| nRowEst==0 ){
111729	aFrom[0].isOrderedValid = 1;
111730	}else{
111731	/* TUNING: Estimated cost of sorting is N*log2(N) where N is the
111732	** number of output rows. */


111733	rSortCost = nRowEst + estLog(nRowEst);
111734	WHERETRACE(0x002,("---- sort cost=%-3d\n", rSortCost));
111735	}
111736
111737	/* Compute successively longer WherePaths using the previous generation
	@@ -111747,12 +111863,12 @@
111747	u8 isOrdered = pFrom->isOrdered;
111748	if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
111749	if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
111750	/* At this point, pWLoop is a candidate to be the next loop.
111751	** Compute its cost */
111752	rCost = whereCostAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow);
111753	rCost = whereCostAdd(rCost, pFrom->rCost);
111754	nOut = pFrom->nRow + pWLoop->nOut;
111755	maskNew = pFrom->maskLoop \| pWLoop->maskSelf;
111756	if( !isOrderedValid ){
111757	switch( wherePathSatisfiesOrderBy(pWInfo,
111758	pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
	@@ -111762,11 +111878,11 @@
111762	isOrderedValid = 1;
111763	break;
111764	case 0: /* No. pFrom+pWLoop will require a separate sort */
111765	isOrdered = 0;
111766	isOrderedValid = 1;
111767	rCost = whereCostAdd(rCost, rSortCost);
111768	break;
111769	default: /* Cannot tell yet. Try again on the next iteration */
111770	break;
111771	}
111772	}else{
	@@ -111969,11 +112085,11 @@
111969	pLoop->wsFlags = WHERE_COLUMN_EQ\|WHERE_IPK\|WHERE_ONEROW;
111970	pLoop->aLTerm[0] = pTerm;
111971	pLoop->nLTerm = 1;
111972	pLoop->u.btree.nEq = 1;
111973	/* TUNING: Cost of a rowid lookup is 10 */
111974	pLoop->rRun = 33; /* 33==whereCost(10) */
111975	}else{
111976	for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
111977	assert( pLoop->aLTermSpace==pLoop->aLTerm );
111978	assert( ArraySize(pLoop->aLTermSpace)==4 );
111979	if( pIdx->onError==OE_None
	@@ -111992,16 +112108,16 @@
111992	}
111993	pLoop->nLTerm = j;
111994	pLoop->u.btree.nEq = j;
111995	pLoop->u.btree.pIndex = pIdx;
111996	/* TUNING: Cost of a unique index lookup is 15 */
111997	pLoop->rRun = 39; /* 39==whereCost(15) */
111998	break;
111999	}
112000	}
112001	if( pLoop->wsFlags ){
112002	pLoop->nOut = (WhereCost)1;
112003	pWInfo->a[0].pWLoop = pLoop;
112004	pLoop->maskSelf = getMask(&pWInfo->sMaskSet, iCur);
112005	pWInfo->a[0].iTabCur = iCur;
112006	pWInfo->nRowOut = 1;
112007	if( pWInfo->pOrderBy ) pWInfo->bOBSat = 1;
112008

	--- src/sqlite3.c
	+++ src/sqlite3.c
	@@ -656,11 +656,11 @@
656	** [sqlite3_libversion_number()], [sqlite3_sourceid()],
657	** [sqlite_version()] and [sqlite_source_id()].
658	*/
659	#define SQLITE_VERSION "3.8.1"
660	#define SQLITE_VERSION_NUMBER 3008001
661	#define SQLITE_SOURCE_ID "2013-10-10 15:04:52 af7abebeb1f70466833bc766d294d721eaef746f"
662
663	/*
664	** CAPI3REF: Run-Time Library Version Numbers
665	** KEYWORDS: sqlite3_version, sqlite3_sourceid
666	**
	@@ -8272,10 +8272,35 @@
8272	typedef u64 tRowcnt; /* 64-bit only if requested at compile-time */
8273	#else
8274	typedef u32 tRowcnt; /* 32-bit is the default */
8275	#endif
8276
8277	/*
8278	** Estimated quantities used for query planning are stored as 16-bit
8279	** logarithms. For quantity X, the value stored is 10*log2(X). This
8280	** gives a possible range of values of approximately 1.0e986 to 1e-986.
8281	** But the allowed values are "grainy". Not every value is representable.
8282	** For example, quantities 16 and 17 are both represented by a LogEst
8283	** of 40. However, since LogEst quantatites are suppose to be estimates,
8284	** not exact values, this imprecision is not a problem.
8285	**
8286	** "LogEst" is short for "Logarithimic Estimate".
8287	**
8288	** Examples:
8289	** 1 -> 0 20 -> 43 10000 -> 132
8290	** 2 -> 10 25 -> 46 25000 -> 146
8291	** 3 -> 16 100 -> 66 1000000 -> 199
8292	** 4 -> 20 1000 -> 99 1048576 -> 200
8293	** 10 -> 33 1024 -> 100 4294967296 -> 320
8294	**
8295	** The LogEst can be negative to indicate fractional values.
8296	** Examples:
8297	**
8298	** 0.5 -> -10 0.1 -> -33 0.0625 -> -40
8299	*/
8300	typedef INT16_TYPE LogEst;
8301
8302	/*
8303	** Macros to determine whether the machine is big or little endian,
8304	** evaluated at runtime.
8305	*/
8306	#ifdef SQLITE_AMALGAMATION
	@@ -10419,11 +10444,12 @@
10444	char zDflt; / Original text of the default value */
10445	char zType; / Data type for this column */
10446	char zColl; / Collating sequence. If NULL, use the default */
10447	u8 notNull; /* An OE_ code for handling a NOT NULL constraint */
10448	char affinity; /* One of the SQLITE_AFF_... values */
10449	u8 szEst; /* Estimated size of this column. INT==1 */
10450	u8 colFlags; /* Boolean properties. See COLFLAG_ defines below */
10451	};
10452
10453	/* Allowed values for Column.colFlags:
10454	*/
10455	#define COLFLAG_PRIMKEY 0x0001 /* Column is part of the primary key */
	@@ -10583,10 +10609,11 @@
10609	tRowcnt nRowEst; /* Estimated rows in table - from sqlite_stat1 table */
10610	int tnum; /* Root BTree node for this table (see note above) */
10611	i16 iPKey; /* If not negative, use aCol[iPKey] as the primary key */
10612	i16 nCol; /* Number of columns in this table */
10613	u16 nRef; /* Number of pointers to this Table */
10614	LogEst szTabRow; /* Estimated size of each table row in bytes */
10615	u8 tabFlags; /* Mask of TF_* values */
10616	u8 keyConf; /* What to do in case of uniqueness conflict on iPKey */
10617	#ifndef SQLITE_OMIT_ALTERTABLE
10618	int addColOffset; /* Offset in CREATE TABLE stmt to add a new column */
10619	#endif
	@@ -10694,11 +10721,11 @@
10721	#define OE_Restrict 6 /* OE_Abort for IMMEDIATE, OE_Rollback for DEFERRED */
10722	#define OE_SetNull 7 /* Set the foreign key value to NULL */
10723	#define OE_SetDflt 8 /* Set the foreign key value to its default */
10724	#define OE_Cascade 9 /* Cascade the changes */
10725
10726	#define OE_Default 10 /* Do whatever the default action is */
10727
10728
10729	/*
10730	** An instance of the following structure is passed as the first
10731	** argument to sqlite3VdbeKeyCompare and is used to control the
	@@ -10781,10 +10808,11 @@
10808	Schema pSchema; / Schema containing this index */
10809	u8 aSortOrder; / for each column: True==DESC, False==ASC */
10810	char *azColl; / Array of collation sequence names for index */
10811	Expr pPartIdxWhere; / WHERE clause for partial indices */
10812	int tnum; /* DB Page containing root of this index */
10813	LogEst szIdxRow; /* Estimated average row size in bytes */
10814	u16 nColumn; /* Number of columns in table used by this index */
10815	u8 onError; /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */
10816	unsigned autoIndex:2; /* 1==UNIQUE, 2==PRIMARY KEY, 0==CREATE INDEX */
10817	unsigned bUnordered:1; /* Use this index for == or IN queries only */
10818	unsigned uniqNotNull:1; /* True if UNIQUE and NOT NULL for all columns */
	@@ -12187,10 +12215,16 @@
12215	SQLITE_PRIVATE int sqlite3GetInt32(const char , int);
12216	SQLITE_PRIVATE int sqlite3Atoi(const char*);
12217	SQLITE_PRIVATE int sqlite3Utf16ByteLen(const void *pData, int nChar);
12218	SQLITE_PRIVATE int sqlite3Utf8CharLen(const char *pData, int nByte);
12219	SQLITE_PRIVATE u32 sqlite3Utf8Read(const u8**);
12220	SQLITE_PRIVATE LogEst sqlite3LogEst(u64);
12221	SQLITE_PRIVATE LogEst sqlite3LogEstAdd(LogEst,LogEst);
12222	#ifndef SQLITE_OMIT_VIRTUALTABLE
12223	SQLITE_PRIVATE LogEst sqlite3LogEstFromDouble(double);
12224	#endif
12225	SQLITE_PRIVATE u64 sqlite3LogEstToInt(LogEst);
12226
12227	/*
12228	** Routines to read and write variable-length integers. These used to
12229	** be defined locally, but now we use the varint routines in the util.c
12230	** file. Code should use the MACRO forms below, as the Varint32 versions
	@@ -12303,11 +12337,11 @@
12337	SQLITE_PRIVATE int sqlite3ResolveOrderGroupBy(Parse, Select, ExprList, const char);
12338	SQLITE_PRIVATE void sqlite3ColumnDefault(Vdbe , Table , int, int);
12339	SQLITE_PRIVATE void sqlite3AlterFinishAddColumn(Parse , Token );
12340	SQLITE_PRIVATE void sqlite3AlterBeginAddColumn(Parse , SrcList );
12341	SQLITE_PRIVATE CollSeq sqlite3GetCollSeq(Parse, u8, CollSeq , const char);
12342	SQLITE_PRIVATE char sqlite3AffinityType(const char, u8);
12343	SQLITE_PRIVATE void sqlite3Analyze(Parse, Token, Token*);
12344	SQLITE_PRIVATE int sqlite3InvokeBusyHandler(BusyHandler*);
12345	SQLITE_PRIVATE int sqlite3FindDb(sqlite3, Token);
12346	SQLITE_PRIVATE int sqlite3FindDbName(sqlite3 , const char );
12347	SQLITE_PRIVATE int sqlite3AnalysisLoad(sqlite3*,int iDB);
	@@ -22388,10 +22422,87 @@
22422	for(i=sz-1; i>0 && z[i]!='/' && z[i]!='.'; i--){}
22423	if( z[i]=='.' && ALWAYS(sz>i+4) ) memmove(&z[i+1], &z[sz-3], 4);
22424	}
22425	}
22426	#endif
22427
22428	/*
22429	** Find (an approximate) sum of two LogEst values. This computation is
22430	** not a simple "+" operator because LogEst is stored as a logarithmic
22431	** value.
22432	**
22433	*/
22434	SQLITE_PRIVATE LogEst sqlite3LogEstAdd(LogEst a, LogEst b){
22435	static const unsigned char x[] = {
22436	10, 10, /* 0,1 */
22437	9, 9, /* 2,3 */
22438	8, 8, /* 4,5 */
22439	7, 7, 7, /* 6,7,8 */
22440	6, 6, 6, /* 9,10,11 */
22441	5, 5, 5, /* 12-14 */
22442	4, 4, 4, 4, /* 15-18 */
22443	3, 3, 3, 3, 3, 3, /* 19-24 */
22444	2, 2, 2, 2, 2, 2, 2, /* 25-31 */
22445	};
22446	if( a>=b ){
22447	if( a>b+49 ) return a;
22448	if( a>b+31 ) return a+1;
22449	return a+x[a-b];
22450	}else{
22451	if( b>a+49 ) return b;
22452	if( b>a+31 ) return b+1;
22453	return b+x[b-a];
22454	}
22455	}
22456
22457	/*
22458	** Convert an integer into a LogEst. In other words, compute a
22459	** good approximatation for 10*log2(x).
22460	*/
22461	SQLITE_PRIVATE LogEst sqlite3LogEst(u64 x){
22462	static LogEst a[] = { 0, 2, 3, 5, 6, 7, 8, 9 };
22463	LogEst y = 40;
22464	if( x<8 ){
22465	if( x<2 ) return 0;
22466	while( x<8 ){ y -= 10; x <<= 1; }
22467	}else{
22468	while( x>255 ){ y += 40; x >>= 4; }
22469	while( x>15 ){ y += 10; x >>= 1; }
22470	}
22471	return a[x&7] + y - 10;
22472	}
22473
22474	#ifndef SQLITE_OMIT_VIRTUALTABLE
22475	/*
22476	** Convert a double into a LogEst
22477	** In other words, compute an approximation for 10*log2(x).
22478	*/
22479	SQLITE_PRIVATE LogEst sqlite3LogEstFromDouble(double x){
22480	u64 a;
22481	LogEst e;
22482	assert( sizeof(x)==8 && sizeof(a)==8 );
22483	if( x<=1 ) return 0;
22484	if( x<=2000000000 ) return sqlite3LogEst((u64)x);
22485	memcpy(&a, &x, 8);
22486	e = (a>>52) - 1022;
22487	return e*10;
22488	}
22489	#endif /* SQLITE_OMIT_VIRTUALTABLE */
22490
22491	/*
22492	** Convert a LogEst into an integer.
22493	*/
22494	SQLITE_PRIVATE u64 sqlite3LogEstToInt(LogEst x){
22495	u64 n;
22496	if( x<10 ) return 1;
22497	n = x%10;
22498	x /= 10;
22499	if( n>=5 ) n -= 2;
22500	else if( n>=1 ) n -= 1;
22501	if( x>=3 ) return (n+8)<<(x-3);
22502	return (n+8)>>(3-x);
22503	}
22504
22505	/************ End of util.c **********************************************/
22506	/************ Begin file hash.c ******************************************/
22507	/*
22508	** 2001 September 22
	@@ -76084,11 +76195,11 @@
76195	return sqlite3ExprAffinity(pExpr->x.pSelect->pEList->a[0].pExpr);
76196	}
76197	#ifndef SQLITE_OMIT_CAST
76198	if( op==TK_CAST ){
76199	assert( !ExprHasProperty(pExpr, EP_IntValue) );
76200	return sqlite3AffinityType(pExpr->u.zToken, 0);
76201	}
76202	#endif
76203	if( (op==TK_AGG_COLUMN \|\| op==TK_COLUMN \|\| op==TK_REGISTER)
76204	&& pExpr->pTab!=0
76205	){
	@@ -78504,11 +78615,11 @@
78615	case TK_CAST: {
78616	/* Expressions of the form: CAST(pLeft AS token) */
78617	int aff, to_op;
78618	inReg = sqlite3ExprCodeTarget(pParse, pExpr->pLeft, target);
78619	assert( !ExprHasProperty(pExpr, EP_IntValue) );
78620	aff = sqlite3AffinityType(pExpr->u.zToken, 0);
78621	to_op = aff - SQLITE_AFF_TEXT + OP_ToText;
78622	assert( to_op==OP_ToText \|\| aff!=SQLITE_AFF_TEXT );
78623	assert( to_op==OP_ToBlob \|\| aff!=SQLITE_AFF_NONE );
78624	assert( to_op==OP_ToNumeric \|\| aff!=SQLITE_AFF_NUMERIC );
78625	assert( to_op==OP_ToInt \|\| aff!=SQLITE_AFF_INTEGER );
	@@ -79171,11 +79282,11 @@
79282	}
79283	#ifndef SQLITE_OMIT_CAST
79284	case TK_CAST: {
79285	/* Expressions of the form: CAST(pLeft AS token) */
79286	const char *zAff = "unk";
79287	switch( sqlite3AffinityType(pExpr->u.zToken, 0) ){
79288	case SQLITE_AFF_TEXT: zAff = "TEXT"; break;
79289	case SQLITE_AFF_NONE: zAff = "NONE"; break;
79290	case SQLITE_AFF_NUMERIC: zAff = "NUMERIC"; break;
79291	case SQLITE_AFF_INTEGER: zAff = "INTEGER"; break;
79292	case SQLITE_AFF_REAL: zAff = "REAL"; break;
	@@ -81886,16 +81997,16 @@
81997	if( zRet==0 ){
81998	sqlite3_result_error_nomem(context);
81999	return;
82000	}
82001
82002	sqlite3_snprintf(24, zRet, "%llu", (u64)p->nRow);
82003	z = zRet + sqlite3Strlen30(zRet);
82004	for(i=0; i<(p->nCol-1); i++){
82005	u64 nDistinct = p->current.anDLt[i] + 1;
82006	u64 iVal = (p->nRow + nDistinct - 1) / nDistinct;
82007	sqlite3_snprintf(24, z, " %llu", iVal);
82008	z += sqlite3Strlen30(z);
82009	assert( p->current.anEq[i] );
82010	}
82011	assert( z[0]=='\0' && z>zRet );
82012
	@@ -81932,11 +82043,11 @@
82043	sqlite3_result_error_nomem(context);
82044	}else{
82045	int i;
82046	char *z = zRet;
82047	for(i=0; i<p->nCol; i++){
82048	sqlite3_snprintf(24, z, "%llu ", (u64)aCnt[i]);
82049	z += sqlite3Strlen30(z);
82050	}
82051	assert( z[0]=='\0' && z>zRet );
82052	z[-1] = '\0';
82053	sqlite3_result_text(context, zRet, -1, sqlite3_free);
	@@ -82393,22 +82504,20 @@
82504	** The first argument points to a nul-terminated string containing a
82505	** list of space separated integers. Read the first nOut of these into
82506	** the array aOut[].
82507	*/
82508	static void decodeIntArray(
82509	char zIntArray, / String containing int array to decode */
82510	int nOut, /* Number of slots in aOut[] */
82511	tRowcnt aOut, / Store integers here */
82512	Index pIndex / Handle extra flags for this index, if not NULL */
82513	){
82514	char *z = zIntArray;
82515	int c;
82516	int i;
82517	tRowcnt v;
82518


82519	#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
82520	if( z==0 ) z = "";
82521	#else
82522	if( NEVER(z==0) ) z = "";
82523	#endif
	@@ -82419,12 +82528,23 @@
82528	z++;
82529	}
82530	aOut[i] = v;
82531	if( *z==' ' ) z++;
82532	}
82533	#ifndef SQLITE_ENABLE_STAT3_OR_STAT4
82534	assert( pIndex!=0 );
82535	#else
82536	if( pIndex )
82537	#endif
82538	{
82539	if( strcmp(z, "unordered")==0 ){
82540	pIndex->bUnordered = 1;
82541	}else if( sqlite3_strglob("sz=[0-9]*", z)==0 ){
82542	int v32 = 0;
82543	sqlite3GetInt32(z+3, &v32);
82544	pIndex->szIdxRow = sqlite3LogEst(v32);
82545	}
82546	}
82547	}
82548
82549	/*
82550	** This callback is invoked once for each index when reading the
	@@ -82459,16 +82579,17 @@
82579	pIndex = 0;
82580	}
82581	z = argv[2];
82582
82583	if( pIndex ){
82584	decodeIntArray((char*)z, pIndex->nColumn+1, pIndex->aiRowEst, pIndex);

82585	if( pIndex->pPartIdxWhere==0 ) pTable->nRowEst = pIndex->aiRowEst[0];

82586	}else{
82587	Index fakeIdx;
82588	fakeIdx.szIdxRow = pTable->szTabRow;
82589	decodeIntArray((char*)z, 1, &pTable->nRowEst, &fakeIdx);
82590	pTable->szTabRow = fakeIdx.szIdxRow;
82591	}
82592
82593	return 0;
82594	}
82595
	@@ -84480,11 +84601,11 @@
84601	}
84602	pTable->zName = zName;
84603	pTable->iPKey = -1;
84604	pTable->pSchema = db->aDb[iDb].pSchema;
84605	pTable->nRef = 1;
84606	pTable->nRowEst = 1048576;
84607	assert( pParse->pNewTable==0 );
84608	pParse->pNewTable = pTable;
84609
84610	/* If this is the magic sqlite_sequence table used by autoincrement,
84611	** then record a pointer to this table in the main database structure
	@@ -84627,10 +84748,11 @@
84748	/* If there is no type specified, columns have the default affinity
84749	** 'NONE'. If there is a type specified, then sqlite3AddColumnType() will
84750	** be called next to set pCol->affinity correctly.
84751	*/
84752	pCol->affinity = SQLITE_AFF_NONE;
84753	pCol->szEst = 1;
84754	p->nCol++;
84755	}
84756
84757	/*
84758	** This routine is called by the parser while in the middle of
	@@ -84668,26 +84790,30 @@
84790	** 'DOUB' \| SQLITE_AFF_REAL
84791	**
84792	** If none of the substrings in the above table are found,
84793	** SQLITE_AFF_NUMERIC is returned.
84794	*/
84795	SQLITE_PRIVATE char sqlite3AffinityType(const char zIn, u8 pszEst){
84796	u32 h = 0;
84797	char aff = SQLITE_AFF_NUMERIC;
84798	const char *zChar = 0;
84799
84800	if( zIn==0 ) return aff;
84801	while( zIn[0] ){
84802	h = (h<<8) + sqlite3UpperToLower[(*zIn)&0xff];
84803	zIn++;
84804	if( h==(('c'<<24)+('h'<<16)+('a'<<8)+'r') ){ /* CHAR */
84805	aff = SQLITE_AFF_TEXT;
84806	zChar = zIn;
84807	}else if( h==(('c'<<24)+('l'<<16)+('o'<<8)+'b') ){ /* CLOB */
84808	aff = SQLITE_AFF_TEXT;
84809	}else if( h==(('t'<<24)+('e'<<16)+('x'<<8)+'t') ){ /* TEXT */
84810	aff = SQLITE_AFF_TEXT;
84811	}else if( h==(('b'<<24)+('l'<<16)+('o'<<8)+'b') /* BLOB */
84812	&& (aff==SQLITE_AFF_NUMERIC \|\| aff==SQLITE_AFF_REAL) ){
84813	aff = SQLITE_AFF_NONE;
84814	if( zIn[0]=='(' ) zChar = zIn;
84815	#ifndef SQLITE_OMIT_FLOATING_POINT
84816	}else if( h==(('r'<<24)+('e'<<16)+('a'<<8)+'l') /* REAL */
84817	&& aff==SQLITE_AFF_NUMERIC ){
84818	aff = SQLITE_AFF_REAL;
84819	}else if( h==(('f'<<24)+('l'<<16)+('o'<<8)+'a') /* FLOA */
	@@ -84701,10 +84827,32 @@
84827	aff = SQLITE_AFF_INTEGER;
84828	break;
84829	}
84830	}
84831
84832	/* If pszEst is not NULL, store an estimate of the field size. The
84833	** estimate is scaled so that the size of an integer is 1. */
84834	if( pszEst ){
84835	pszEst = 1; / default size is approx 4 bytes */
84836	if( aff<=SQLITE_AFF_NONE ){
84837	if( zChar ){
84838	while( zChar[0] ){
84839	if( sqlite3Isdigit(zChar[0]) ){
84840	int v;
84841	sqlite3GetInt32(zChar, &v);
84842	v = v/4 + 1;
84843	if( v>255 ) v = 255;
84844	pszEst = v; / BLOB(k), VARCHAR(k), CHAR(k) -> r=(k/4+1) */
84845	break;
84846	}
84847	zChar++;
84848	}
84849	}else{
84850	pszEst = 5; / BLOB, TEXT, CLOB -> r=5 (approx 20 bytes)*/
84851	}
84852	}
84853	}
84854	return aff;
84855	}
84856
84857	/*
84858	** This routine is called by the parser while in the middle of
	@@ -84722,11 +84870,11 @@
84870	p = pParse->pNewTable;
84871	if( p==0 \|\| NEVER(p->nCol<1) ) return;
84872	pCol = &p->aCol[p->nCol-1];
84873	assert( pCol->zType==0 );
84874	pCol->zType = sqlite3NameFromToken(pParse->db, pType);
84875	pCol->affinity = sqlite3AffinityType(pCol->zType, &pCol->szEst);
84876	}
84877
84878	/*
84879	** The expression is the default value for the most recently added column
84880	** of the table currently under construction.
	@@ -85070,18 +85218,46 @@
85218	testcase( pCol->affinity==SQLITE_AFF_REAL );
85219
85220	zType = azType[pCol->affinity - SQLITE_AFF_TEXT];
85221	len = sqlite3Strlen30(zType);
85222	assert( pCol->affinity==SQLITE_AFF_NONE
85223	\|\| pCol->affinity==sqlite3AffinityType(zType, 0) );
85224	memcpy(&zStmt[k], zType, len);
85225	k += len;
85226	assert( k<=n );
85227	}
85228	sqlite3_snprintf(n-k, &zStmt[k], "%s", zEnd);
85229	return zStmt;
85230	}
85231
85232	/*
85233	** Estimate the total row width for a table.
85234	*/
85235	static void estimateTableWidth(Table *pTab){
85236	unsigned wTable = 0;
85237	const Column *pTabCol;
85238	int i;
85239	for(i=pTab->nCol, pTabCol=pTab->aCol; i>0; i--, pTabCol++){
85240	wTable += pTabCol->szEst;
85241	}
85242	if( pTab->iPKey<0 ) wTable++;
85243	pTab->szTabRow = sqlite3LogEst(wTable*4);
85244	}
85245
85246	/*
85247	** Estimate the average size of a row for an index.
85248	*/
85249	static void estimateIndexWidth(Index *pIdx){
85250	unsigned wIndex = 1;
85251	int i;
85252	const Column *aCol = pIdx->pTable->aCol;
85253	for(i=0; i<pIdx->nColumn; i++){
85254	assert( pIdx->aiColumn[i]>=0 && pIdx->aiColumn[i]<pIdx->pTable->nCol );
85255	wIndex += aCol[pIdx->aiColumn[i]].szEst;
85256	}
85257	pIdx->szIdxRow = sqlite3LogEst(wIndex*4);
85258	}
85259
85260	/*
85261	** This routine is called to report the final ")" that terminates
85262	** a CREATE TABLE statement.
85263	**
	@@ -85105,13 +85281,14 @@
85281	Parse pParse, / Parse context */
85282	Token pCons, / The ',' token after the last column defn. */
85283	Token pEnd, / The final ')' token in the CREATE TABLE */
85284	Select pSelect / Select from a "CREATE ... AS SELECT" */
85285	){
85286	Table p; / The new table */
85287	sqlite3 db = pParse->db; / The database connection */
85288	int iDb; /* Database in which the table lives */
85289	Index pIdx; / An implied index of the table */
85290
85291	if( (pEnd==0 && pSelect==0) \|\| db->mallocFailed ){
85292	return;
85293	}
85294	p = pParse->pNewTable;
	@@ -85126,10 +85303,16 @@
85303	*/
85304	if( p->pCheck ){
85305	sqlite3ResolveSelfReference(pParse, p, NC_IsCheck, 0, p->pCheck);
85306	}
85307	#endif /* !defined(SQLITE_OMIT_CHECK) */
85308
85309	/* Estimate the average row size for the table and for all implied indices */
85310	estimateTableWidth(p);
85311	for(pIdx=p->pIndex; pIdx; pIdx=pIdx->pNext){
85312	estimateIndexWidth(pIdx);
85313	}
85314
85315	/* If the db->init.busy is 1 it means we are reading the SQL off the
85316	** "sqlite_master" or "sqlite_temp_master" table on the disk.
85317	** So do not write to the disk again. Extract the root page number
85318	** for the table from the db->init.newTnum field. (The page number
	@@ -86085,13 +86268,14 @@
86268	sqlite3 *db = pParse->db;
86269	Db pDb; / The specific table containing the indexed database */
86270	int iDb; /* Index of the database that is being written */
86271	Token pName = 0; / Unqualified name of the index to create */
86272	struct ExprList_item pListItem; / For looping over pList */
86273	const Column pTabCol; / A column in the table */
86274	int nCol; /* Number of columns */
86275	int nExtra = 0; /* Space allocated for zExtra[] */
86276	char zExtra; / Extra space after the Index object */
86277
86278	assert( pParse->nErr==0 ); /* Never called with prior errors */
86279	if( db->mallocFailed \|\| IN_DECLARE_VTAB ){
86280	goto exit_create_index;
86281	}
	@@ -86314,11 +86498,10 @@
86498	** same column more than once cannot be an error because that would
86499	** break backwards compatibility - it needs to be a warning.
86500	*/
86501	for(i=0, pListItem=pList->a; i<pList->nExpr; i++, pListItem++){
86502	const char *zColName = pListItem->zName;

86503	int requestedSortOrder;
86504	char zColl; / Collation sequence name */
86505
86506	for(j=0, pTabCol=pTab->aCol; j<pTab->nCol; j++, pTabCol++){
86507	if( sqlite3StrICmp(zColName, pTabCol->zName)==0 ) break;
	@@ -86351,10 +86534,11 @@
86534	requestedSortOrder = pListItem->sortOrder & sortOrderMask;
86535	pIndex->aSortOrder[i] = (u8)requestedSortOrder;
86536	if( pTab->aCol[j].notNull==0 ) pIndex->uniqNotNull = 0;
86537	}
86538	sqlite3DefaultRowEst(pIndex);
86539	if( pParse->pNewTable==0 ) estimateIndexWidth(pIndex);
86540
86541	if( pTab==pParse->pNewTable ){
86542	/* This routine has been called to create an automatic index as a
86543	** result of a PRIMARY KEY or UNIQUE clause on a column definition, or
86544	** a PRIMARY KEY or UNIQUE clause following the column definitions.
	@@ -96379,30 +96563,34 @@
96563	break;
96564
96565	case PragTyp_INDEX_LIST: if( zRight ){
96566	Index *pIdx;
96567	Table *pTab;
96568	int i;
96569	pTab = sqlite3FindTable(db, zRight, zDb);
96570	if( pTab ){
96571	v = sqlite3GetVdbe(pParse);
96572	sqlite3VdbeSetNumCols(v, 4);
96573	pParse->nMem = 4;
96574	sqlite3CodeVerifySchema(pParse, iDb);
96575	sqlite3VdbeSetColName(v, 0, COLNAME_NAME, "seq", SQLITE_STATIC);
96576	sqlite3VdbeSetColName(v, 1, COLNAME_NAME, "name", SQLITE_STATIC);
96577	sqlite3VdbeSetColName(v, 2, COLNAME_NAME, "unique", SQLITE_STATIC);
96578	sqlite3VdbeSetColName(v, 3, COLNAME_NAME, "avgrowsize", SQLITE_STATIC);
96579	sqlite3VdbeAddOp2(v, OP_Integer, 0, 1);
96580	sqlite3VdbeAddOp2(v, OP_Null, 0, 2);
96581	sqlite3VdbeAddOp2(v, OP_Integer, 1, 3);
96582	sqlite3VdbeAddOp2(v, OP_Integer,
96583	(int)sqlite3LogEstToInt(pTab->szTabRow), 4);
96584	sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 4);
96585	for(pIdx=pTab->pIndex, i=1; pIdx; pIdx=pIdx->pNext, i++){
96586	sqlite3VdbeAddOp2(v, OP_Integer, i, 1);
96587	sqlite3VdbeAddOp4(v, OP_String8, 0, 2, 0, pIdx->zName, 0);
96588	sqlite3VdbeAddOp2(v, OP_Integer, pIdx->onError!=OE_None, 3);
96589	sqlite3VdbeAddOp2(v, OP_Integer,
96590	(int)sqlite3LogEstToInt(pIdx->szIdxRow), 4);
96591	sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 4);
96592	}
96593	}
96594	}
96595	break;
96596
	@@ -99086,10 +99274,13 @@
99274	}
99275
99276	/*
99277	** Return a pointer to a string containing the 'declaration type' of the
99278	** expression pExpr. The string may be treated as static by the caller.
99279	**
99280	** Also try to estimate the size of the returned value and return that
99281	** result in *pEstWidth.
99282	**
99283	** The declaration type is the exact datatype definition extracted from the
99284	** original CREATE TABLE statement if the expression is a column. The
99285	** declaration type for a ROWID field is INTEGER. Exactly when an expression
99286	** is considered a column can be complex in the presence of subqueries. The
	@@ -99100,25 +99291,40 @@
99291	** SELECT (SELECT col FROM tbl;
99292	** SELECT (SELECT col FROM tbl);
99293	** SELECT abc FROM (SELECT col AS abc FROM tbl);
99294	**
99295	** The declaration type for any expression other than a column is NULL.
99296	**
99297	** This routine has either 3 or 6 parameters depending on whether or not
99298	** the SQLITE_ENABLE_COLUMN_METADATA compile-time option is used.
99299	*/
99300	#ifdef SQLITE_ENABLE_COLUMN_METADATA
99301	# define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,C,D,E,F)
99302	static const char *columnTypeImpl(
99303	NameContext *pNC,
99304	Expr *pExpr,
99305	const char **pzOrigDb,
99306	const char **pzOrigTab,
99307	const char **pzOrigCol,
99308	u8 *pEstWidth
99309	){
99310	char const *zOrigDb = 0;
99311	char const *zOrigTab = 0;
99312	char const *zOrigCol = 0;
99313	#else /* if !defined(SQLITE_ENABLE_COLUMN_METADATA) */
99314	# define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,F)
99315	static const char *columnTypeImpl(
99316	NameContext *pNC,
99317	Expr *pExpr,
99318	u8 *pEstWidth


99319	){
99320	#endif /* !defined(SQLITE_ENABLE_COLUMN_METADATA) */
99321	char const *zType = 0;



99322	int j;
99323	u8 estWidth = 1;
99324
99325	if( NEVER(pExpr==0) \|\| pNC->pSrcList==0 ) return 0;

99326	switch( pExpr->op ){
99327	case TK_AGG_COLUMN:
99328	case TK_COLUMN: {
99329	/* The expression is a column. Locate the table the column is being
99330	** extracted from in NameContext.pSrcList. This table may be real
	@@ -99175,29 +99381,39 @@
99381	NameContext sNC;
99382	Expr *p = pS->pEList->a[iCol].pExpr;
99383	sNC.pSrcList = pS->pSrc;
99384	sNC.pNext = pNC;
99385	sNC.pParse = pNC->pParse;
99386	zType = columnType(&sNC, p,&zOrigDb,&zOrigTab,&zOrigCol, &estWidth);
99387	}
99388	}else if( ALWAYS(pTab->pSchema) ){
99389	/* A real table */
99390	assert( !pS );
99391	if( iCol<0 ) iCol = pTab->iPKey;
99392	assert( iCol==-1 \|\| (iCol>=0 && iCol<pTab->nCol) );
99393	#ifdef SQLITE_ENABLE_COLUMN_METADATA
99394	if( iCol<0 ){
99395	zType = "INTEGER";
99396	zOrigCol = "rowid";
99397	}else{
99398	zType = pTab->aCol[iCol].zType;
99399	zOrigCol = pTab->aCol[iCol].zName;
99400	estWidth = pTab->aCol[iCol].szEst;
99401	}
99402	zOrigTab = pTab->zName;
99403	if( pNC->pParse ){
99404	int iDb = sqlite3SchemaToIndex(pNC->pParse->db, pTab->pSchema);
99405	zOrigDb = pNC->pParse->db->aDb[iDb].zName;
99406	}
99407	#else
99408	if( iCol<0 ){
99409	zType = "INTEGER";
99410	}else{
99411	zType = pTab->aCol[iCol].zType;
99412	estWidth = pTab->aCol[iCol].szEst;
99413	}
99414	#endif
99415	}
99416	break;
99417	}
99418	#ifndef SQLITE_OMIT_SUBQUERY
99419	case TK_SELECT: {
	@@ -99210,22 +99426,25 @@
99426	Expr *p = pS->pEList->a[0].pExpr;
99427	assert( ExprHasProperty(pExpr, EP_xIsSelect) );
99428	sNC.pSrcList = pS->pSrc;
99429	sNC.pNext = pNC;
99430	sNC.pParse = pNC->pParse;
99431	zType = columnType(&sNC, p, &zOrigDb, &zOrigTab, &zOrigCol, &estWidth);
99432	break;
99433	}
99434	#endif
99435	}
99436
99437	#ifdef SQLITE_ENABLE_COLUMN_METADATA
99438	if( pzOrigDb ){
99439	assert( pzOrigTab && pzOrigCol );
99440	*pzOrigDb = zOrigDb;
99441	*pzOrigTab = zOrigTab;
99442	*pzOrigCol = zOrigCol;
99443	}
99444	#endif
99445	if( pEstWidth ) *pEstWidth = estWidth;
99446	return zType;
99447	}
99448
99449	/*
99450	** Generate code that will tell the VDBE the declaration types of columns
	@@ -99247,25 +99466,25 @@
99466	const char *zType;
99467	#ifdef SQLITE_ENABLE_COLUMN_METADATA
99468	const char *zOrigDb = 0;
99469	const char *zOrigTab = 0;
99470	const char *zOrigCol = 0;
99471	zType = columnType(&sNC, p, &zOrigDb, &zOrigTab, &zOrigCol, 0);
99472
99473	/* The vdbe must make its own copy of the column-type and other
99474	** column specific strings, in case the schema is reset before this
99475	** virtual machine is deleted.
99476	*/
99477	sqlite3VdbeSetColName(v, i, COLNAME_DATABASE, zOrigDb, SQLITE_TRANSIENT);
99478	sqlite3VdbeSetColName(v, i, COLNAME_TABLE, zOrigTab, SQLITE_TRANSIENT);
99479	sqlite3VdbeSetColName(v, i, COLNAME_COLUMN, zOrigCol, SQLITE_TRANSIENT);
99480	#else
99481	zType = columnType(&sNC, p, 0, 0, 0, 0);
99482	#endif
99483	sqlite3VdbeSetColName(v, i, COLNAME_DECLTYPE, zType, SQLITE_TRANSIENT);
99484	}
99485	#endif /* !defined(SQLITE_OMIT_DECLTYPE) */
99486	}
99487
99488	/*
99489	** Generate code that will tell the VDBE the names of columns
99490	** in the result set. This information is used to provide the
	@@ -99450,39 +99669,41 @@
99669	** This routine requires that all identifiers in the SELECT
99670	** statement be resolved.
99671	*/
99672	static void selectAddColumnTypeAndCollation(
99673	Parse pParse, / Parsing contexts */
99674	Table pTab, / Add column type information to this table */

99675	Select pSelect / SELECT used to determine types and collations */
99676	){
99677	sqlite3 *db = pParse->db;
99678	NameContext sNC;
99679	Column *pCol;
99680	CollSeq *pColl;
99681	int i;
99682	Expr *p;
99683	struct ExprList_item *a;
99684	u64 szAll = 0;
99685
99686	assert( pSelect!=0 );
99687	assert( (pSelect->selFlags & SF_Resolved)!=0 );
99688	assert( pTab->nCol==pSelect->pEList->nExpr \|\| db->mallocFailed );
99689	if( db->mallocFailed ) return;
99690	memset(&sNC, 0, sizeof(sNC));
99691	sNC.pSrcList = pSelect->pSrc;
99692	a = pSelect->pEList->a;
99693	for(i=0, pCol=pTab->aCol; i<pTab->nCol; i++, pCol++){
99694	p = a[i].pExpr;
99695	pCol->zType = sqlite3DbStrDup(db, columnType(&sNC, p,0,0,0, &pCol->szEst));
99696	szAll += pCol->szEst;
99697	pCol->affinity = sqlite3ExprAffinity(p);
99698	if( pCol->affinity==0 ) pCol->affinity = SQLITE_AFF_NONE;
99699	pColl = sqlite3ExprCollSeq(pParse, p);
99700	if( pColl ){
99701	pCol->zColl = sqlite3DbStrDup(db, pColl->zName);
99702	}
99703	}
99704	pTab->szTabRow = sqlite3LogEst(szAll*4);
99705	}
99706
99707	/*
99708	** Given a SELECT statement, generate a Table structure that describes
99709	** the result set of that SELECT.
	@@ -99506,13 +99727,13 @@
99727	/* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside
99728	** is disabled */
99729	assert( db->lookaside.bEnabled==0 );
99730	pTab->nRef = 1;
99731	pTab->zName = 0;
99732	pTab->nRowEst = 1048576;
99733	selectColumnsFromExprList(pParse, pSelect->pEList, &pTab->nCol, &pTab->aCol);
99734	selectAddColumnTypeAndCollation(pParse, pTab, pSelect);
99735	pTab->iPKey = -1;
99736	if( db->mallocFailed ){
99737	sqlite3DeleteTable(db, pTab);
99738	return 0;
99739	}
	@@ -101420,15 +101641,15 @@
101641	assert( pFrom->pTab==0 );
101642	sqlite3WalkSelect(pWalker, pSel);
101643	pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));
101644	if( pTab==0 ) return WRC_Abort;
101645	pTab->nRef = 1;
101646	pTab->zName = sqlite3MPrintf(db, "sqlite_sq_%p", (void*)pTab);
101647	while( pSel->pPrior ){ pSel = pSel->pPrior; }
101648	selectColumnsFromExprList(pParse, pSel->pEList, &pTab->nCol, &pTab->aCol);
101649	pTab->iPKey = -1;
101650	pTab->nRowEst = 1048576;
101651	pTab->tabFlags \|= TF_Ephemeral;
101652	#endif
101653	}else{
101654	/* An ordinary table or view name in the FROM clause */
101655	assert( pFrom->pTab==0 );
	@@ -101708,11 +101929,11 @@
101929	if( ALWAYS(pTab!=0) && (pTab->tabFlags & TF_Ephemeral)!=0 ){
101930	/* A sub-query in the FROM clause of a SELECT */
101931	Select *pSel = pFrom->pSelect;
101932	assert( pSel );
101933	while( pSel->pPrior ) pSel = pSel->pPrior;
101934	selectAddColumnTypeAndCollation(pParse, pTab, pSel);
101935	}
101936	}
101937	}
101938	return WRC_Continue;
101939	}
	@@ -102623,17 +102844,11 @@
102844	int iRoot = pTab->tnum; /* Root page of scanned b-tree */
102845
102846	sqlite3CodeVerifySchema(pParse, iDb);
102847	sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
102848
102849	/* Search for the index that has the lowest scan cost.






102850	**
102851	** (2011-04-15) Do not do a full scan of an unordered index.
102852	**
102853	** (2013-10-03) Do not count the entires in a partial index.
102854	**
	@@ -102640,17 +102855,18 @@
102855	** In practice the KeyInfo structure will not be used. It is only
102856	** passed to keep OP_OpenRead happy.
102857	*/
102858	for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
102859	if( pIdx->bUnordered==0
102860	&& pIdx->szIdxRow<pTab->szTabRow
102861	&& pIdx->pPartIdxWhere==0
102862	&& (!pBest \|\| pIdx->szIdxRow<pBest->szIdxRow)
102863	){
102864	pBest = pIdx;
102865	}
102866	}
102867	if( pBest ){
102868	iRoot = pBest->tnum;
102869	pKeyInfo = sqlite3IndexKeyinfo(pParse, pBest);
102870	}
102871
102872	/* Open a read-only cursor, execute the OP_Count, close the cursor. */
	@@ -106406,30 +106622,10 @@
106622	typedef struct WhereLoopBuilder WhereLoopBuilder;
106623	typedef struct WhereScan WhereScan;
106624	typedef struct WhereOrCost WhereOrCost;
106625	typedef struct WhereOrSet WhereOrSet;
106626




















106627	/*
106628	** This object contains information needed to implement a single nested
106629	** loop in WHERE clause.
106630	**
106631	** Contrast this object with WhereLoop. This object describes the
	@@ -106490,13 +106686,13 @@
106686	#ifdef SQLITE_DEBUG
106687	char cId; /* Symbolic ID of this loop for debugging use */
106688	#endif
106689	u8 iTab; /* Position in FROM clause of table for this loop */
106690	u8 iSortIdx; /* Sorting index number. 0==None */
106691	LogEst rSetup; /* One-time setup cost (ex: create transient index) */
106692	LogEst rRun; /* Cost of running each loop */
106693	LogEst nOut; /* Estimated number of output rows */
106694	union {
106695	struct { /* Information for internal btree tables */
106696	int nEq; /* Number of equality constraints */
106697	Index pIndex; / Index used, or NULL */
106698	} btree;
	@@ -106522,12 +106718,12 @@
106718	** subquery on one operand of an OR operator in the WHERE clause.
106719	** See WhereOrSet for additional information
106720	*/
106721	struct WhereOrCost {
106722	Bitmask prereq; /* Prerequisites */
106723	LogEst rRun; /* Cost of running this subquery */
106724	LogEst nOut; /* Number of outputs for this subquery */
106725	};
106726
106727	/* The WhereOrSet object holds a set of possible WhereOrCosts that
106728	** correspond to the subquery(s) of OR-clause processing. Only the
106729	** best N_OR_COST elements are retained.
	@@ -106561,12 +106757,12 @@
106757	** at the end is the choosen query plan.
106758	*/
106759	struct WherePath {
106760	Bitmask maskLoop; /* Bitmask of all WhereLoop objects in this path */
106761	Bitmask revLoop; /* aLoop[]s that should be reversed for ORDER BY */
106762	LogEst nRow; /* Estimated number of rows generated by this path */
106763	LogEst rCost; /* Total cost of this path */
106764	u8 isOrdered; /* True if this path satisfies ORDER BY */
106765	u8 isOrderedValid; /* True if the isOrdered field is valid */
106766	WhereLoop *aLoop; / Array of WhereLoop objects implementing this path */
106767	};
106768
	@@ -106628,11 +106824,11 @@
106824	union {
106825	int leftColumn; /* Column number of X in "X <op> <expr>" */
106826	WhereOrInfo pOrInfo; / Extra information if (eOperator & WO_OR)!=0 */
106827	WhereAndInfo pAndInfo; / Extra information if (eOperator& WO_AND)!=0 */
106828	} u;
106829	LogEst truthProb; /* Probability of truth for this expression */
106830	u16 eOperator; /* A WO_xx value describing <op> */
106831	u8 wtFlags; /* TERM_xxx bit flags. See below */
106832	u8 nChild; /* Number of children that must disable us */
106833	WhereClause pWC; / The clause this term is part of */
106834	Bitmask prereqRight; /* Bitmask of tables used by pExpr->pRight */
	@@ -106776,11 +106972,11 @@
106972	SrcList pTabList; / List of tables in the join */
106973	ExprList pOrderBy; / The ORDER BY clause or NULL */
106974	ExprList pResultSet; / Result set. DISTINCT operates on these */
106975	WhereLoop pLoops; / List of all WhereLoop objects */
106976	Bitmask revMask; /* Mask of ORDER BY terms that need reversing */
106977	LogEst nRowOut; /* Estimated number of output rows */
106978	u16 wctrlFlags; /* Flags originally passed to sqlite3WhereBegin() */
106979	u8 bOBSat; /* ORDER BY satisfied by indices */
106980	u8 okOnePass; /* Ok to use one-pass algorithm for UPDATE/DELETE */
106981	u8 untestedTerms; /* Not all WHERE terms resolved by outer loop */
106982	u8 eDistinct; /* One of the WHERE_DISTINCT_* values below */
	@@ -106836,30 +107032,15 @@
107032	#define WHERE_IN_ABLE 0x00000800 /* Able to support an IN operator */
107033	#define WHERE_ONEROW 0x00001000 /* Selects no more than one row */
107034	#define WHERE_MULTI_OR 0x00002000 /* OR using multiple indices */
107035	#define WHERE_AUTO_INDEX 0x00004000 /* Uses an ephemeral index */
107036















107037	/*
107038	** Return the estimated number of output rows from a WHERE clause
107039	*/
107040	SQLITE_PRIVATE u64 sqlite3WhereOutputRowCount(WhereInfo *pWInfo){
107041	return sqlite3LogEstToInt(pWInfo->nRowOut);
107042	}
107043
107044	/*
107045	** Return one of the WHERE_DISTINCT_xxxxx values to indicate how this
107046	** WHERE clause returns outputs for DISTINCT processing.
	@@ -106917,12 +107098,12 @@
107098	** so that pSet keeps the N_OR_COST best entries seen so far.
107099	*/
107100	static int whereOrInsert(
107101	WhereOrSet pSet, / The WhereOrSet to be updated */
107102	Bitmask prereq, /* Prerequisites of the new entry */
107103	LogEst rRun, /* Run-cost of the new entry */
107104	LogEst nOut /* Number of outputs for the new entry */
107105	){
107106	u16 i;
107107	WhereOrCost *p;
107108	for(i=pSet->n, p=pSet->a; i>0; i--, p++){
107109	if( rRun<=p->rRun && (prereq & p->prereq)==prereq ){
	@@ -107003,13 +107184,10 @@
107184	if( pWC->a!=pWC->aStatic ){
107185	sqlite3DbFree(db, pWC->a);
107186	}
107187	}
107188



107189	/*
107190	** Add a single new WhereTerm entry to the WhereClause object pWC.
107191	** The new WhereTerm object is constructed from Expr p and with wtFlags.
107192	** The index in pWC->a[] of the new WhereTerm is returned on success.
107193	** 0 is returned if the new WhereTerm could not be added due to a memory
	@@ -107048,11 +107226,11 @@
107226	}
107227	pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
107228	}
107229	pTerm = &pWC->a[idx = pWC->nTerm++];
107230	if( p && ExprHasProperty(p, EP_Unlikely) ){
107231	pTerm->truthProb = sqlite3LogEst(p->iTable) - 99;
107232	}else{
107233	pTerm->truthProb = -1;
107234	}
107235	pTerm->pExpr = sqlite3ExprSkipCollate(p);
107236	pTerm->wtFlags = wtFlags;
	@@ -108312,79 +108490,16 @@
108490	}
108491
108492	return 0;
108493	}
108494































































108495
108496	/*
108497	** Estimate the logarithm of the input value to base 2.
108498	*/
108499	static LogEst estLog(LogEst N){
108500	LogEst x = sqlite3LogEst(N);
108501	return x>33 ? x - 33 : 0;
108502	}
108503
108504	/*
108505	** Two routines for printing the content of an sqlite3_index_info
	@@ -108893,11 +109008,11 @@
109008	**
109009	** ... FROM t1 WHERE a > ? AND a < ? ...
109010	**
109011	** then nEq is set to 0.
109012	**
109013	** When this function is called, *pnOut is set to the sqlite3LogEst() of the
109014	** number of rows that the index scan is expected to visit without
109015	** considering the range constraints. If nEq is 0, this is the number of
109016	** rows in the index. Assuming no error occurs, *pnOut is adjusted (reduced)
109017	** to account for the range contraints pLower and pUpper.
109018	**
	@@ -108909,19 +109024,19 @@
109024	static int whereRangeScanEst(
109025	Parse pParse, / Parsing & code generating context */
109026	WhereLoopBuilder *pBuilder,
109027	WhereTerm pLower, / Lower bound on the range. ex: "x>123" Might be NULL */
109028	WhereTerm pUpper, / Upper bound on the range. ex: "x<455" Might be NULL */
109029	WhereLoop pLoop / Modify the .nOut and maybe .rRun fields */
109030	){
109031	int rc = SQLITE_OK;
109032	int nOut = pLoop->nOut;
109033	int nEq = pLoop->u.btree.nEq;
109034	LogEst nNew;
109035
109036	#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
109037	Index *p = pLoop->u.btree.pIndex;

109038
109039	if( p->nSample>0
109040	&& nEq==pBuilder->nRecValid
109041	&& nEq<p->nSampleCol
109042	&& OptimizationEnabled(pParse->db, SQLITE_Stat3)
	@@ -108998,18 +109113,18 @@
109113	}
109114
109115	pBuilder->pRec = pRec;
109116	if( rc==SQLITE_OK ){
109117	if( iUpper>iLower ){
109118	nNew = sqlite3LogEst(iUpper - iLower);
109119	}else{
109120	nNew = 10; assert( 10==sqlite3LogEst(2) );
109121	}
109122	if( nNew<nOut ){
109123	nOut = nNew;
109124	}
109125	pLoop->nOut = (LogEst)nOut;
109126	WHERETRACE(0x100, ("range scan regions: %u..%u est=%d\n",
109127	(u32)iLower, (u32)iUpper, nOut));
109128	return SQLITE_OK;
109129	}
109130	}
	@@ -109020,20 +109135,20 @@
109135	assert( pLower \|\| pUpper );
109136	/* TUNING: Each inequality constraint reduces the search space 4-fold.
109137	** A BETWEEN operator, therefore, reduces the search space 16-fold */
109138	nNew = nOut;
109139	if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ){
109140	nNew -= 20; assert( 20==sqlite3LogEst(4) );
109141	nOut--;
109142	}
109143	if( pUpper ){
109144	nNew -= 20; assert( 20==sqlite3LogEst(4) );
109145	nOut--;
109146	}
109147	if( nNew<10 ) nNew = 10;
109148	if( nNew<nOut ) nOut = nNew;
109149	pLoop->nOut = (LogEst)nOut;
109150	return rc;
109151	}
109152
109153	#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
109154	/*
	@@ -110673,11 +110788,11 @@
110788	*/
110789	static int whereLoopAddBtreeIndex(
110790	WhereLoopBuilder pBuilder, / The WhereLoop factory */
110791	struct SrcList_item pSrc, / FROM clause term being analyzed */
110792	Index pProbe, / An index on pSrc */
110793	LogEst nInMul /* log(Number of iterations due to IN) */
110794	){
110795	WhereInfo pWInfo = pBuilder->pWInfo; / WHERE analyse context */
110796	Parse pParse = pWInfo->pParse; / Parsing context */
110797	sqlite3 db = pParse->db; / Database connection malloc context */
110798	WhereLoop pNew; / Template WhereLoop under construction */
	@@ -110686,15 +110801,15 @@
110801	WhereScan scan; /* Iterator for WHERE terms */
110802	Bitmask saved_prereq; /* Original value of pNew->prereq */
110803	u16 saved_nLTerm; /* Original value of pNew->nLTerm */
110804	int saved_nEq; /* Original value of pNew->u.btree.nEq */
110805	u32 saved_wsFlags; /* Original value of pNew->wsFlags */
110806	LogEst saved_nOut; /* Original value of pNew->nOut */
110807	int iCol; /* Index of the column in the table */
110808	int rc = SQLITE_OK; /* Return code */
110809	LogEst nRowEst; /* Estimated index selectivity */
110810	LogEst rLogSize; /* Logarithm of table size */
110811	WhereTerm pTop = 0, pBtm = 0; /* Top and bottom range constraints */
110812
110813	pNew = pBuilder->pNew;
110814	if( db->mallocFailed ) return SQLITE_NOMEM;
110815
	@@ -110710,11 +110825,11 @@
110825	if( pProbe->bUnordered ) opMask &= ~(WO_GT\|WO_GE\|WO_LT\|WO_LE);
110826
110827	assert( pNew->u.btree.nEq<=pProbe->nColumn );
110828	if( pNew->u.btree.nEq < pProbe->nColumn ){
110829	iCol = pProbe->aiColumn[pNew->u.btree.nEq];
110830	nRowEst = sqlite3LogEst(pProbe->aiRowEst[pNew->u.btree.nEq+1]);
110831	if( nRowEst==0 && pProbe->onError==OE_None ) nRowEst = 1;
110832	}else{
110833	iCol = -1;
110834	nRowEst = 0;
110835	}
	@@ -110724,11 +110839,11 @@
110839	saved_nLTerm = pNew->nLTerm;
110840	saved_wsFlags = pNew->wsFlags;
110841	saved_prereq = pNew->prereq;
110842	saved_nOut = pNew->nOut;
110843	pNew->rSetup = 0;
110844	rLogSize = estLog(sqlite3LogEst(pProbe->aiRowEst[0]));
110845	for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
110846	int nIn = 0;
110847	#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
110848	int nRecValid = pBuilder->nRecValid;
110849	#endif
	@@ -110751,14 +110866,14 @@
110866	if( pTerm->eOperator & WO_IN ){
110867	Expr *pExpr = pTerm->pExpr;
110868	pNew->wsFlags \|= WHERE_COLUMN_IN;
110869	if( ExprHasProperty(pExpr, EP_xIsSelect) ){
110870	/* "x IN (SELECT ...)": TUNING: the SELECT returns 25 rows */
110871	nIn = 46; assert( 46==sqlite3LogEst(25) );
110872	}else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
110873	/* "x IN (value, value, ...)" */
110874	nIn = sqlite3LogEst(pExpr->x.pList->nExpr);
110875	}
110876	pNew->rRun += nIn;
110877	pNew->u.btree.nEq++;
110878	pNew->nOut = nRowEst + nInMul + nIn;
110879	}else if( pTerm->eOperator & (WO_EQ) ){
	@@ -110776,11 +110891,11 @@
110891	pNew->nOut = nRowEst + nInMul;
110892	}else if( pTerm->eOperator & (WO_ISNULL) ){
110893	pNew->wsFlags \|= WHERE_COLUMN_NULL;
110894	pNew->u.btree.nEq++;
110895	/* TUNING: IS NULL selects 2 rows */
110896	nIn = 10; assert( 10==sqlite3LogEst(2) );
110897	pNew->nOut = nRowEst + nInMul + nIn;
110898	}else if( pTerm->eOperator & (WO_GT\|WO_GE) ){
110899	testcase( pTerm->eOperator & WO_GT );
110900	testcase( pTerm->eOperator & WO_GE );
110901	pNew->wsFlags \|= WHERE_COLUMN_RANGE\|WHERE_BTM_LIMIT;
	@@ -110796,11 +110911,11 @@
110911	pNew->aLTerm[pNew->nLTerm-2] : 0;
110912	}
110913	if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
110914	/* Adjust nOut and rRun for STAT3 range values */
110915	assert( pNew->nOut==saved_nOut );
110916	whereRangeScanEst(pParse, pBuilder, pBtm, pTop, pNew);
110917	}
110918	#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
110919	if( nInMul==0
110920	&& pProbe->nSample
110921	&& pNew->u.btree.nEq<=pProbe->nSampleCol
	@@ -110816,22 +110931,22 @@
110931	&& !ExprHasProperty(pExpr, EP_xIsSelect) ){
110932	rc = whereInScanEst(pParse, pBuilder, pExpr->x.pList, &nOut);
110933	}
110934	assert( nOut==0 \|\| rc==SQLITE_OK );
110935	if( nOut ){
110936	nOut = sqlite3LogEst(nOut);
110937	pNew->nOut = MIN(nOut, saved_nOut);
110938	}
110939	}
110940	#endif
110941	if( (pNew->wsFlags & (WHERE_IDX_ONLY\|WHERE_IPK))==0 ){
110942	/* Each row involves a step of the index, then a binary search of
110943	** the main table */
110944	pNew->rRun = sqlite3LogEstAdd(pNew->rRun,rLogSize>27 ? rLogSize-17 : 10);
110945	}
110946	/* Step cost for each output row */
110947	pNew->rRun = sqlite3LogEstAdd(pNew->rRun, pNew->nOut);
110948	whereLoopOutputAdjust(pBuilder->pWC, pNew, pSrc->iCursor);
110949	rc = whereLoopInsert(pBuilder, pNew);
110950	if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
110951	&& pNew->u.btree.nEq<(pProbe->nColumn + (pProbe->zName!=0))
110952	){
	@@ -110927,18 +111042,20 @@
111042	struct SrcList_item pSrc; / The FROM clause btree term to add */
111043	WhereLoop pNew; / Template WhereLoop object */
111044	int rc = SQLITE_OK; /* Return code */
111045	int iSortIdx = 1; /* Index number */
111046	int b; /* A boolean value */
111047	LogEst rSize; /* number of rows in the table */
111048	LogEst rLogSize; /* Logarithm of the number of rows in the table */
111049	WhereClause pWC; / The parsed WHERE clause */
111050	Table pTab; / Table being queried */
111051
111052	pNew = pBuilder->pNew;
111053	pWInfo = pBuilder->pWInfo;
111054	pTabList = pWInfo->pTabList;
111055	pSrc = pTabList->a + pNew->iTab;
111056	pTab = pSrc->pTab;
111057	pWC = pBuilder->pWC;
111058	assert( !IsVirtual(pSrc->pTab) );
111059
111060	if( pSrc->pIndex ){
111061	/* An INDEXED BY clause specifies a particular index to use */
	@@ -110952,22 +111069,22 @@
111069	memset(&sPk, 0, sizeof(Index));
111070	sPk.nColumn = 1;
111071	sPk.aiColumn = &aiColumnPk;
111072	sPk.aiRowEst = aiRowEstPk;
111073	sPk.onError = OE_Replace;
111074	sPk.pTable = pTab;
111075	aiRowEstPk[0] = pTab->nRowEst;
111076	aiRowEstPk[1] = 1;
111077	pFirst = pSrc->pTab->pIndex;
111078	if( pSrc->notIndexed==0 ){
111079	/* The real indices of the table are only considered if the
111080	** NOT INDEXED qualifier is omitted from the FROM clause */
111081	sPk.pNext = pFirst;
111082	}
111083	pProbe = &sPk;
111084	}
111085	rSize = sqlite3LogEst(pTab->nRowEst);
111086	rLogSize = estLog(rSize);
111087
111088	#ifndef SQLITE_OMIT_AUTOMATIC_INDEX
111089	/* Automatic indexes */
111090	if( !pBuilder->pOrSet
	@@ -110988,17 +111105,17 @@
111105	pNew->nLTerm = 1;
111106	pNew->aLTerm[0] = pTerm;
111107	/* TUNING: One-time cost for computing the automatic index is
111108	** approximately 7Nlog2(N) where N is the number of rows in
111109	** the table being indexed. */
111110	pNew->rSetup = rLogSize + rSize + 28; assert( 28==sqlite3LogEst(7) );
111111	/* TUNING: Each index lookup yields 20 rows in the table. This
111112	** is more than the usual guess of 10 rows, since we have no way
111113	** of knowning how selective the index will ultimately be. It would
111114	** not be unreasonable to make this value much larger. */
111115	pNew->nOut = 43; assert( 43==sqlite3LogEst(20) );
111116	pNew->rRun = sqlite3LogEstAdd(rLogSize,pNew->nOut);
111117	pNew->wsFlags = WHERE_AUTO_INDEX;
111118	pNew->prereq = mExtra \| pTerm->prereqRight;
111119	rc = whereLoopInsert(pBuilder, pNew);
111120	}
111121	}
	@@ -111028,14 +111145,12 @@
111145
111146	/* Full table scan */
111147	pNew->iSortIdx = b ? iSortIdx : 0;
111148	/* TUNING: Cost of full table scan is 3*(N + log2(N)).
111149	** + The extra 3 factor is to encourage the use of indexed lookups
111150	** over full scans. FIXME */
111151	pNew->rRun = sqlite3LogEstAdd(rSize,rLogSize) + 16;


111152	whereLoopOutputAdjust(pWC, pNew, pSrc->iCursor);
111153	rc = whereLoopInsert(pBuilder, pNew);
111154	pNew->nOut = rSize;
111155	if( rc ) break;
111156	}else{
	@@ -111044,26 +111159,25 @@
111159
111160	/* Full scan via index */
111161	if( b
111162	\|\| ( m==0
111163	&& pProbe->bUnordered==0
111164	&& pProbe->szIdxRow<pTab->szTabRow
111165	&& (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
111166	&& sqlite3GlobalConfig.bUseCis
111167	&& OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
111168	)
111169	){
111170	pNew->iSortIdx = b ? iSortIdx : 0;
111171	if( m==0 ){
111172	/* TUNING: Cost of a covering index scan is K*(N + log2(N)).
111173	** + The extra factor K of between 1.1 and 3.0 that depends
111174	** on the relative sizes of the table and the index. K
111175	** is smaller for smaller indices, thus favoring them.
111176	*/
111177	pNew->rRun = sqlite3LogEstAdd(rSize,rLogSize) + 1 +
111178	(15*pProbe->szIdxRow)/pTab->szTabRow;


111179	}else{
111180	assert( b!=0 );
111181	/* TUNING: Cost of scanning a non-covering index is (N+1)*log2(N)
111182	** which we will simplify to just Nlog2(N) /
111183	pNew->rRun = rSize + rLogSize;
	@@ -111237,13 +111351,13 @@
111351	pIdxInfo->needToFreeIdxStr = 0;
111352	pNew->u.vtab.idxStr = pIdxInfo->idxStr;
111353	pNew->u.vtab.isOrdered = (u8)((pIdxInfo->nOrderBy!=0)
111354	&& pIdxInfo->orderByConsumed);
111355	pNew->rSetup = 0;
111356	pNew->rRun = sqlite3LogEstFromDouble(pIdxInfo->estimatedCost);
111357	/* TUNING: Every virtual table query returns 25 rows */
111358	pNew->nOut = 46; assert( 46==sqlite3LogEst(25) );
111359	whereLoopInsert(pBuilder, pNew);
111360	if( pNew->u.vtab.needFree ){
111361	sqlite3_free(pNew->u.vtab.idxStr);
111362	pNew->u.vtab.needFree = 0;
111363	}
	@@ -111276,10 +111390,12 @@
111390	pWC = pBuilder->pWC;
111391	if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK;
111392	pWCEnd = pWC->a + pWC->nTerm;
111393	pNew = pBuilder->pNew;
111394	memset(&sSum, 0, sizeof(sSum));
111395	pItem = pWInfo->pTabList->a + pNew->iTab;
111396	iCur = pItem->iCursor;
111397
111398	for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){
111399	if( (pTerm->eOperator & WO_OR)!=0
111400	&& (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0
111401	){
	@@ -111287,12 +111403,10 @@
111403	WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
111404	WhereTerm *pOrTerm;
111405	int once = 1;
111406	int i, j;
111407


111408	sSubBuild = *pBuilder;
111409	sSubBuild.pOrderBy = 0;
111410	sSubBuild.pOrSet = &sCur;
111411
111412	for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
	@@ -111329,12 +111443,12 @@
111443	whereOrMove(&sPrev, &sSum);
111444	sSum.n = 0;
111445	for(i=0; i<sPrev.n; i++){
111446	for(j=0; j<sCur.n; j++){
111447	whereOrInsert(&sSum, sPrev.a[i].prereq \| sCur.a[j].prereq,
111448	sqlite3LogEstAdd(sPrev.a[i].rRun, sCur.a[j].rRun),
111449	sqlite3LogEstAdd(sPrev.a[i].nOut, sCur.a[j].nOut));
111450	}
111451	}
111452	}
111453	}
111454	pNew->nLTerm = 1;
	@@ -111668,23 +111782,23 @@
111782	** costs if nRowEst==0.
111783	**
111784	** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
111785	** error occurs.
111786	*/
111787	static int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){
111788	int mxChoice; /* Maximum number of simultaneous paths tracked */
111789	int nLoop; /* Number of terms in the join */
111790	Parse pParse; / Parsing context */
111791	sqlite3 db; / The database connection */
111792	int iLoop; /* Loop counter over the terms of the join */
111793	int ii, jj; /* Loop counters */
111794	int mxI = 0; /* Index of next entry to replace */
111795	LogEst rCost; /* Cost of a path */
111796	LogEst nOut; /* Number of outputs */
111797	LogEst mxCost = 0; /* Maximum cost of a set of paths */
111798	LogEst mxOut = 0; /* Maximum nOut value on the set of paths */
111799	LogEst rSortCost; /* Cost to do a sort */
111800	int nTo, nFrom; /* Number of valid entries in aTo[] and aFrom[] */
111801	WherePath aFrom; / All nFrom paths at the previous level */
111802	WherePath aTo; / The nTo best paths at the current level */
111803	WherePath pFrom; / An element of aFrom[] that we are working on */
111804	WherePath pTo; / An element of aTo[] that we are working on */
	@@ -111717,21 +111831,23 @@
111831	/* Seed the search with a single WherePath containing zero WhereLoops.
111832	**
111833	** TUNING: Do not let the number of iterations go above 25. If the cost
111834	** of computing an automatic index is not paid back within the first 25
111835	** rows, then do not use the automatic index. */
111836	aFrom[0].nRow = MIN(pParse->nQueryLoop, 46); assert( 46==sqlite3LogEst(25) );
111837	nFrom = 1;
111838
111839	/* Precompute the cost of sorting the final result set, if the caller
111840	** to sqlite3WhereBegin() was concerned about sorting */
111841	rSortCost = 0;
111842	if( pWInfo->pOrderBy==0 \|\| nRowEst==0 ){
111843	aFrom[0].isOrderedValid = 1;
111844	}else{
111845	/* TUNING: Estimated cost of sorting is 48Nlog2(N) where N is the
111846	** number of output rows. The 48 is the expected size of a row to sort.
111847	** FIXME: compute a better estimate of the 48 multiplier based on the
111848	** result set expressions. */
111849	rSortCost = nRowEst + estLog(nRowEst);
111850	WHERETRACE(0x002,("---- sort cost=%-3d\n", rSortCost));
111851	}
111852
111853	/* Compute successively longer WherePaths using the previous generation
	@@ -111747,12 +111863,12 @@
111863	u8 isOrdered = pFrom->isOrdered;
111864	if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
111865	if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
111866	/* At this point, pWLoop is a candidate to be the next loop.
111867	** Compute its cost */
111868	rCost = sqlite3LogEstAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow);
111869	rCost = sqlite3LogEstAdd(rCost, pFrom->rCost);
111870	nOut = pFrom->nRow + pWLoop->nOut;
111871	maskNew = pFrom->maskLoop \| pWLoop->maskSelf;
111872	if( !isOrderedValid ){
111873	switch( wherePathSatisfiesOrderBy(pWInfo,
111874	pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
	@@ -111762,11 +111878,11 @@
111878	isOrderedValid = 1;
111879	break;
111880	case 0: /* No. pFrom+pWLoop will require a separate sort */
111881	isOrdered = 0;
111882	isOrderedValid = 1;
111883	rCost = sqlite3LogEstAdd(rCost, rSortCost);
111884	break;
111885	default: /* Cannot tell yet. Try again on the next iteration */
111886	break;
111887	}
111888	}else{
	@@ -111969,11 +112085,11 @@
112085	pLoop->wsFlags = WHERE_COLUMN_EQ\|WHERE_IPK\|WHERE_ONEROW;
112086	pLoop->aLTerm[0] = pTerm;
112087	pLoop->nLTerm = 1;
112088	pLoop->u.btree.nEq = 1;
112089	/* TUNING: Cost of a rowid lookup is 10 */
112090	pLoop->rRun = 33; /* 33==sqlite3LogEst(10) */
112091	}else{
112092	for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
112093	assert( pLoop->aLTermSpace==pLoop->aLTerm );
112094	assert( ArraySize(pLoop->aLTermSpace)==4 );
112095	if( pIdx->onError==OE_None
	@@ -111992,16 +112108,16 @@
112108	}
112109	pLoop->nLTerm = j;
112110	pLoop->u.btree.nEq = j;
112111	pLoop->u.btree.pIndex = pIdx;
112112	/* TUNING: Cost of a unique index lookup is 15 */
112113	pLoop->rRun = 39; /* 39==sqlite3LogEst(15) */
112114	break;
112115	}
112116	}
112117	if( pLoop->wsFlags ){
112118	pLoop->nOut = (LogEst)1;
112119	pWInfo->a[0].pWLoop = pLoop;
112120	pLoop->maskSelf = getMask(&pWInfo->sMaskSet, iCur);
112121	pWInfo->a[0].iTabCur = iCur;
112122	pWInfo->nRowOut = 1;
112123	if( pWInfo->pOrderBy ) pWInfo->bOBSat = 1;
112124

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.8.1"
111	111	#define SQLITE_VERSION_NUMBER 3008001
112		-#define SQLITE_SOURCE_ID "2013-10-07 21:49:16 36d64dc36f18c166b2c93c43579fa3bbb5cd545f"
	112	+#define SQLITE_SOURCE_ID "2013-10-10 15:04:52 af7abebeb1f70466833bc766d294d721eaef746f"
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.8.1"
111	#define SQLITE_VERSION_NUMBER 3008001
112	#define SQLITE_SOURCE_ID "2013-10-07 21:49:16 36d64dc36f18c166b2c93c43579fa3bbb5cd545f"
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.8.1"
111	#define SQLITE_VERSION_NUMBER 3008001
112	#define SQLITE_SOURCE_ID "2013-10-10 15:04:52 af7abebeb1f70466833bc766d294d721eaef746f"
113
114	/*
115	** CAPI3REF: Run-Time Library Version Numbers
116	** KEYWORDS: sqlite3_version, sqlite3_sourceid
117	**
118

Fossil SCM

Keyboard Shortcuts