wasCSharpSQLite – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 using System;
2 using System.Diagnostics;
3 using System.Text;
4  
5 using Bitmask = System.UInt64;
6  
7 using i16 = System.Int16;
8 using u8 = System.Byte;
9 using u16 = System.UInt16;
10 using u32 = System.UInt32;
11  
12 using sqlite3_int64 = System.Int64;
13  
14 namespace Community.CsharpSqlite
15 {
16 using sqlite3_value = Sqlite3.Mem;
17 public partial class Sqlite3
18 {
19 /*
20 ** 2001 September 15
21 **
22 ** The author disclaims copyright to this source code. In place of
23 ** a legal notice, here is a blessing:
24 **
25 ** May you do good and not evil.
26 ** May you find forgiveness for yourself and forgive others.
27 ** May you share freely, never taking more than you give.
28 **
29 *************************************************************************
30 ** This module contains C code that generates VDBE code used to process
31 ** the WHERE clause of SQL statements. This module is responsible for
32 ** generating the code that loops through a table looking for applicable
33 ** rows. Indices are selected and used to speed the search when doing
34 ** so is applicable. Because this module is responsible for selecting
35 ** indices, you might also think of this module as the "query optimizer".
36 *************************************************************************
37 ** Included in SQLite3 port to C#-SQLite; 2008 Noah B Hart
38 ** C#-SQLite is an independent reimplementation of the SQLite software library
39 **
40 ** SQLITE_SOURCE_ID: 2011-05-19 13:26:54 ed1da510a239ea767a01dc332b667119fa3c908ecd7
41 **
42 *************************************************************************
43 */
44 //#include "sqliteInt.h"
45  
46  
47 /*
48 ** Trace output macros
49 */
50 #if (SQLITE_TEST) || (SQLITE_DEBUG)
51 static bool sqlite3WhereTrace = false;
52 #endif
53 #if (SQLITE_TEST) && (SQLITE_DEBUG) && TRACE
54 //# define WHERETRACE(X) if(sqlite3WhereTrace) sqlite3DebugPrintf X
55 static void WHERETRACE( string X, params object[] ap ) { if ( sqlite3WhereTrace ) sqlite3DebugPrintf( X, ap ); }
56 #else
57 //# define WHERETRACE(X)
58 static void WHERETRACE( string X, params object[] ap )
59 {
60 }
61 #endif
62  
63 /* Forward reference
64 */
65 //typedef struct WhereClause WhereClause;
66 //typedef struct WhereMaskSet WhereMaskSet;
67 //typedef struct WhereOrInfo WhereOrInfo;
68 //typedef struct WhereAndInfo WhereAndInfo;
69 //typedef struct WhereCost WhereCost;
70  
71 /*
72 ** The query generator uses an array of instances of this structure to
73 ** help it analyze the subexpressions of the WHERE clause. Each WHERE
74 ** clause subexpression is separated from the others by AND operators,
75 ** usually, or sometimes subexpressions separated by OR.
76 **
77 ** All WhereTerms are collected into a single WhereClause structure.
78 ** The following identity holds:
79 **
80 ** WhereTerm.pWC.a[WhereTerm.idx] == WhereTerm
81 **
82 ** When a term is of the form:
83 **
84 ** X <op> <expr>
85 **
86 ** where X is a column name and <op> is one of certain operators,
87 ** then WhereTerm.leftCursor and WhereTerm.u.leftColumn record the
88 ** cursor number and column number for X. WhereTerm.eOperator records
89 ** the <op> using a bitmask encoding defined by WO_xxx below. The
90 ** use of a bitmask encoding for the operator allows us to search
91 ** quickly for terms that match any of several different operators.
92 **
93 ** A WhereTerm might also be two or more subterms connected by OR:
94 **
95 ** (t1.X <op> <expr>) OR (t1.Y <op> <expr>) OR ....
96 **
97 ** In this second case, wtFlag as the TERM_ORINFO set and eOperator==WO_OR
98 ** and the WhereTerm.u.pOrInfo field points to auxiliary information that
99 ** is collected about the
100 **
101 ** If a term in the WHERE clause does not match either of the two previous
102 ** categories, then eOperator==0. The WhereTerm.pExpr field is still set
103 ** to the original subexpression content and wtFlags is set up appropriately
104 ** but no other fields in the WhereTerm object are meaningful.
105 **
106 ** When eOperator!=0, prereqRight and prereqAll record sets of cursor numbers,
107 ** but they do so indirectly. A single WhereMaskSet structure translates
108 ** cursor number into bits and the translated bit is stored in the prereq
109 ** fields. The translation is used in order to maximize the number of
110 ** bits that will fit in a Bitmask. The VDBE cursor numbers might be
111 ** spread out over the non-negative integers. For example, the cursor
112 ** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45. The WhereMaskSet
113 ** translates these sparse cursor numbers into consecutive integers
114 ** beginning with 0 in order to make the best possible use of the available
115 ** bits in the Bitmask. So, in the example above, the cursor numbers
116 ** would be mapped into integers 0 through 7.
117 **
118 ** The number of terms in a join is limited by the number of bits
119 ** in prereqRight and prereqAll. The default is 64 bits, hence SQLite
120 ** is only able to process joins with 64 or fewer tables.
121 */
122 //typedef struct WhereTerm WhereTerm;
123 public class WhereTerm
124 {
125 public Expr pExpr; /* Pointer to the subexpression that is this term */
126 public int iParent; /* Disable pWC.a[iParent] when this term disabled */
127 public int leftCursor; /* Cursor number of X in "X <op> <expr>" */
128 public class _u
129 {
130 public int leftColumn; /* Column number of X in "X <op> <expr>" */
131 public WhereOrInfo pOrInfo; /* Extra information if eOperator==WO_OR */
132 public WhereAndInfo pAndInfo; /* Extra information if eOperator==WO_AND */
133 }
134 public _u u = new _u();
135 public u16 eOperator; /* A WO_xx value describing <op> */
136 public u8 wtFlags; /* TERM_xxx bit flags. See below */
137 public u8 nChild; /* Number of children that must disable us */
138 public WhereClause pWC; /* The clause this term is part of */
139 public Bitmask prereqRight; /* Bitmask of tables used by pExpr.pRight */
140 public Bitmask prereqAll; /* Bitmask of tables referenced by pExpr */
141 };
142  
143 /*
144 ** Allowed values of WhereTerm.wtFlags
145 */
146 //#define TERM_DYNAMIC 0x01 /* Need to call sqlite3ExprDelete(db, ref pExpr) */
147 //#define TERM_VIRTUAL 0x02 /* Added by the optimizer. Do not code */
148 //#define TERM_CODED 0x04 /* This term is already coded */
149 //#define TERM_COPIED 0x08 /* Has a child */
150 //#define TERM_ORINFO 0x10 /* Need to free the WhereTerm.u.pOrInfo object */
151 //#define TERM_ANDINFO 0x20 /* Need to free the WhereTerm.u.pAndInfo obj */
152 //#define TERM_OR_OK 0x40 /* Used during OR-clause processing */
153 #if SQLITE_ENABLE_STAT2
154 //# define TERM_VNULL 0x80 /* Manufactured x>NULL or x<=NULL term */
155 #else
156 //# define TERM_VNULL 0x00 /* Disabled if not using stat2 */
157 #endif
158 const int TERM_DYNAMIC = 0x01; /* Need to call sqlite3ExprDelete(db, ref pExpr) */
159 const int TERM_VIRTUAL = 0x02; /* Added by the optimizer. Do not code */
160 const int TERM_CODED = 0x04; /* This term is already coded */
161 const int TERM_COPIED = 0x08; /* Has a child */
162 const int TERM_ORINFO = 0x10; /* Need to free the WhereTerm.u.pOrInfo object */
163 const int TERM_ANDINFO = 0x20; /* Need to free the WhereTerm.u.pAndInfo obj */
164 const int TERM_OR_OK = 0x40; /* Used during OR-clause processing */
165 #if SQLITE_ENABLE_STAT2
166 const int TERM_VNULL = 0x80; /* Manufactured x>NULL or x<=NULL term */
167 #else
168 const int TERM_VNULL = 0x00; /* Disabled if not using stat2 */
169 #endif
170  
171 /*
172 ** An instance of the following structure holds all information about a
173 ** WHERE clause. Mostly this is a container for one or more WhereTerms.
174 */
175 public class WhereClause
176 {
177 public Parse pParse; /* The parser context */
178 public WhereMaskSet pMaskSet; /* Mapping of table cursor numbers to bitmasks */
179 public Bitmask vmask; /* Bitmask identifying virtual table cursors */
180 public u8 op; /* Split operator. TK_AND or TK_OR */
181 public int nTerm; /* Number of terms */
182 public int nSlot; /* Number of entries in a[] */
183 public WhereTerm[] a; /* Each a[] describes a term of the WHERE cluase */
184 #if (SQLITE_SMALL_STACK)
185 public WhereTerm[] aStatic = new WhereTerm[1]; /* Initial static space for a[] */
186 #else
187 public WhereTerm[] aStatic = new WhereTerm[8]; /* Initial static space for a[] */
188 #endif
189  
190 public void CopyTo( WhereClause wc )
191 {
192 wc.pParse = this.pParse;
193 wc.pMaskSet = new WhereMaskSet();
194 this.pMaskSet.CopyTo( wc.pMaskSet );
195 wc.op = this.op;
196 wc.nTerm = this.nTerm;
197 wc.nSlot = this.nSlot;
198 wc.a = (WhereTerm[])this.a.Clone();
199 wc.aStatic = (WhereTerm[])this.aStatic.Clone();
200 }
201 };
202  
203 /*
204 ** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to
205 ** a dynamically allocated instance of the following structure.
206 */
207 public class WhereOrInfo
208 {
209 public WhereClause wc = new WhereClause();/* Decomposition into subterms */
210 public Bitmask indexable; /* Bitmask of all indexable tables in the clause */
211 };
212  
213 /*
214 ** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to
215 ** a dynamically allocated instance of the following structure.
216 */
217 public class WhereAndInfo
218 {
219 public WhereClause wc = new WhereClause(); /* The subexpression broken out */
220 };
221  
222 /*
223 ** An instance of the following structure keeps track of a mapping
224 ** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.
225 **
226 ** The VDBE cursor numbers are small integers contained in
227 ** SrcList_item.iCursor and Expr.iTable fields. For any given WHERE
228 ** clause, the cursor numbers might not begin with 0 and they might
229 ** contain gaps in the numbering sequence. But we want to make maximum
230 ** use of the bits in our bitmasks. This structure provides a mapping
231 ** from the sparse cursor numbers into consecutive integers beginning
232 ** with 0.
233 **
234 ** If WhereMaskSet.ix[A]==B it means that The A-th bit of a Bitmask
235 ** corresponds VDBE cursor number B. The A-th bit of a bitmask is 1<<A.
236 **
237 ** For example, if the WHERE clause expression used these VDBE
238 ** cursors: 4, 5, 8, 29, 57, 73. Then the WhereMaskSet structure
239 ** would map those cursor numbers into bits 0 through 5.
240 **
241 ** Note that the mapping is not necessarily ordered. In the example
242 ** above, the mapping might go like this: 4.3, 5.1, 8.2, 29.0,
243 ** 57.5, 73.4. Or one of 719 other combinations might be used. It
244 ** does not really matter. What is important is that sparse cursor
245 ** numbers all get mapped into bit numbers that begin with 0 and contain
246 ** no gaps.
247 */
248 public class WhereMaskSet
249 {
250 public int n; /* Number of Debug.Assigned cursor values */
251 public int[] ix = new int[BMS]; /* Cursor Debug.Assigned to each bit */
252  
253 public void CopyTo( WhereMaskSet wms )
254 {
255 wms.n = this.n;
256 wms.ix = (int[])this.ix.Clone();
257 }
258 }
259  
260 /*
261 ** A WhereCost object records a lookup strategy and the estimated
262 ** cost of pursuing that strategy.
263 */
264 public class WhereCost
265 {
266 public WherePlan plan = new WherePlan();/* The lookup strategy */
267 public double rCost; /* Overall cost of pursuing this search strategy */
268 public Bitmask used; /* Bitmask of cursors used by this plan */
269  
270 public void Clear()
271 {
272 plan.Clear();
273 rCost = 0;
274 used = 0;
275 }
276 };
277  
278 /*
279 ** Bitmasks for the operators that indices are able to exploit. An
280 ** OR-ed combination of these values can be used when searching for
281 ** terms in the where clause.
282 */
283 //#define WO_IN 0x001
284 //#define WO_EQ 0x002
285 //#define WO_LT (WO_EQ<<(TK_LT-TK_EQ))
286 //#define WO_LE (WO_EQ<<(TK_LE-TK_EQ))
287 //#define WO_GT (WO_EQ<<(TK_GT-TK_EQ))
288 //#define WO_GE (WO_EQ<<(TK_GE-TK_EQ))
289 //#define WO_MATCH 0x040
290 //#define WO_ISNULL 0x080
291 //#define WO_OR 0x100 /* Two or more OR-connected terms */
292 //#define WO_AND 0x200 /* Two or more AND-connected terms */
293 //#define WO_NOOP 0x800 /* This term does not restrict search space */
294  
295 //#define WO_ALL 0xfff /* Mask of all possible WO_* values */
296 //#define WO_SINGLE 0x0ff /* Mask of all non-compound WO_* values */
297 const int WO_IN = 0x001;
298 const int WO_EQ = 0x002;
299 const int WO_LT = ( WO_EQ << ( TK_LT - TK_EQ ) );
300 const int WO_LE = ( WO_EQ << ( TK_LE - TK_EQ ) );
301 const int WO_GT = ( WO_EQ << ( TK_GT - TK_EQ ) );
302 const int WO_GE = ( WO_EQ << ( TK_GE - TK_EQ ) );
303 const int WO_MATCH = 0x040;
304 const int WO_ISNULL = 0x080;
305 const int WO_OR = 0x100; /* Two or more OR-connected terms */
306 const int WO_AND = 0x200; /* Two or more AND-connected terms */
307 const int WO_NOOP = 0x800; /* This term does not restrict search space */
308  
309 const int WO_ALL = 0xfff; /* Mask of all possible WO_* values */
310 const int WO_SINGLE = 0x0ff; /* Mask of all non-compound WO_* values */
311 /*
312 ** Value for wsFlags returned by bestIndex() and stored in
313 ** WhereLevel.wsFlags. These flags determine which search
314 ** strategies are appropriate.
315 **
316 ** The least significant 12 bits is reserved as a mask for WO_ values above.
317 ** The WhereLevel.wsFlags field is usually set to WO_IN|WO_EQ|WO_ISNULL.
318 ** But if the table is the right table of a left join, WhereLevel.wsFlags
319 ** is set to WO_IN|WO_EQ. The WhereLevel.wsFlags field can then be used as
320 ** the "op" parameter to findTerm when we are resolving equality constraints.
321 ** ISNULL constraints will then not be used on the right table of a left
322 ** join. Tickets #2177 and #2189.
323 */
324 //#define WHERE_ROWID_EQ 0x00001000 /* rowid=EXPR or rowid IN (...) */
325 //#define WHERE_ROWID_RANGE 0x00002000 /* rowid<EXPR and/or rowid>EXPR */
326 //#define WHERE_COLUMN_EQ 0x00010000 /* x=EXPR or x IN (...) or x IS NULL */
327 //#define WHERE_COLUMN_RANGE 0x00020000 /* x<EXPR and/or x>EXPR */
328 //#define WHERE_COLUMN_IN 0x00040000 /* x IN (...) */
329 //#define WHERE_COLUMN_NULL 0x00080000 /* x IS NULL */
330 //#define WHERE_INDEXED 0x000f0000 /* Anything that uses an index */
331 //#define WHERE_IN_ABLE 0x000f1000 /* Able to support an IN operator */
332 //#define WHERE_NOT_FULLSCAN 0x100f3000 /* Does not do a full table scan */
333 //#define WHERE_TOP_LIMIT 0x00100000 /* x<EXPR or x<=EXPR constraint */
334 //#define WHERE_BTM_LIMIT 0x00200000 /* x>EXPR or x>=EXPR constraint */
335 //#define WHERE_BOTH_LIMIT 0x00300000 /* Both x>EXPR and x<EXPR */
336 //#define WHERE_IDX_ONLY 0x00800000 /* Use index only - omit table */
337 //#define WHERE_ORDERBY 0x01000000 /* Output will appear in correct order */
338 //#define WHERE_REVERSE 0x02000000 /* Scan in reverse order */
339 //#define WHERE_UNIQUE 0x04000000 /* Selects no more than one row */
340 //#define WHERE_VIRTUALTABLE 0x08000000 /* Use virtual-table processing */
341 //#define WHERE_MULTI_OR 0x10000000 /* OR using multiple indices */
342 //#define WHERE_TEMP_INDEX 0x20000000 /* Uses an ephemeral index */
343 const int WHERE_ROWID_EQ = 0x00001000;
344 const int WHERE_ROWID_RANGE = 0x00002000;
345 const int WHERE_COLUMN_EQ = 0x00010000;
346 const int WHERE_COLUMN_RANGE = 0x00020000;
347 const int WHERE_COLUMN_IN = 0x00040000;
348 const int WHERE_COLUMN_NULL = 0x00080000;
349 const int WHERE_INDEXED = 0x000f0000;
350 const int WHERE_IN_ABLE = 0x000f1000;
351 const int WHERE_NOT_FULLSCAN = 0x100f3000;
352 const int WHERE_TOP_LIMIT = 0x00100000;
353 const int WHERE_BTM_LIMIT = 0x00200000;
354 const int WHERE_BOTH_LIMIT = 0x00300000;
355 const int WHERE_IDX_ONLY = 0x00800000;
356 const int WHERE_ORDERBY = 0x01000000;
357 const int WHERE_REVERSE = 0x02000000;
358 const int WHERE_UNIQUE = 0x04000000;
359 const int WHERE_VIRTUALTABLE = 0x08000000;
360 const int WHERE_MULTI_OR = 0x10000000;
361 const int WHERE_TEMP_INDEX = 0x20000000;
362  
363 /*
364 ** Initialize a preallocated WhereClause structure.
365 */
366 static void whereClauseInit(
367 WhereClause pWC, /* The WhereClause to be initialized */
368 Parse pParse, /* The parsing context */
369 WhereMaskSet pMaskSet /* Mapping from table cursor numbers to bitmasks */
370 )
371 {
372 pWC.pParse = pParse;
373 pWC.pMaskSet = pMaskSet;
374 pWC.nTerm = 0;
375 pWC.nSlot = ArraySize( pWC.aStatic ) - 1;
376 pWC.a = pWC.aStatic;
377 pWC.vmask = 0;
378 }
379  
380 /* Forward reference */
381 //static void whereClauseClear(WhereClause);
382  
383 /*
384 ** Deallocate all memory Debug.Associated with a WhereOrInfo object.
385 */
386 static void whereOrInfoDelete( sqlite3 db, WhereOrInfo p )
387 {
388 whereClauseClear( p.wc );
389 sqlite3DbFree( db, ref p );
390 }
391  
392 /*
393 ** Deallocate all memory Debug.Associated with a WhereAndInfo object.
394 */
395 static void whereAndInfoDelete( sqlite3 db, WhereAndInfo p )
396 {
397 whereClauseClear( p.wc );
398 sqlite3DbFree( db, ref p );
399 }
400  
401 /*
402 ** Deallocate a WhereClause structure. The WhereClause structure
403 ** itself is not freed. This routine is the inverse of whereClauseInit().
404 */
405 static void whereClauseClear( WhereClause pWC )
406 {
407 int i;
408 WhereTerm a;
409 sqlite3 db = pWC.pParse.db;
410 for ( i = pWC.nTerm - 1; i >= 0; i-- )//, a++)
411 {
412 a = pWC.a[i];
413 if ( ( a.wtFlags & TERM_DYNAMIC ) != 0 )
414 {
415 sqlite3ExprDelete( db, ref a.pExpr );
416 }
417 if ( ( a.wtFlags & TERM_ORINFO ) != 0 )
418 {
419 whereOrInfoDelete( db, a.u.pOrInfo );
420 }
421 else if ( ( a.wtFlags & TERM_ANDINFO ) != 0 )
422 {
423 whereAndInfoDelete( db, a.u.pAndInfo );
424 }
425 }
426 if ( pWC.a != pWC.aStatic )
427 {
428 sqlite3DbFree( db, ref pWC.a );
429 }
430 }
431  
432 /*
433 ** Add a single new WhereTerm entry to the WhereClause object pWC.
434 ** The new WhereTerm object is constructed from Expr p and with wtFlags.
435 ** The index in pWC.a[] of the new WhereTerm is returned on success.
436 ** 0 is returned if the new WhereTerm could not be added due to a memory
437 ** allocation error. The memory allocation failure will be recorded in
438 ** the db.mallocFailed flag so that higher-level functions can detect it.
439 **
440 ** This routine will increase the size of the pWC.a[] array as necessary.
441 **
442 ** If the wtFlags argument includes TERM_DYNAMIC, then responsibility
443 ** for freeing the expression p is Debug.Assumed by the WhereClause object pWC.
444 ** This is true even if this routine fails to allocate a new WhereTerm.
445 **
446 ** WARNING: This routine might reallocate the space used to store
447 ** WhereTerms. All pointers to WhereTerms should be invalidated after
448 ** calling this routine. Such pointers may be reinitialized by referencing
449 ** the pWC.a[] array.
450 */
451 static int whereClauseInsert( WhereClause pWC, Expr p, u8 wtFlags )
452 {
453 WhereTerm pTerm;
454 int idx;
455 testcase( wtFlags & TERM_VIRTUAL ); /* EV: R-00211-15100 */
456 if ( pWC.nTerm >= pWC.nSlot )
457 {
458 //WhereTerm pOld = pWC.a;
459 //sqlite3 db = pWC.pParse.db;
460 Array.Resize( ref pWC.a, pWC.nSlot * 2 );
461 //pWC.a = sqlite3DbMallocRaw(db, sizeof(pWC.a[0])*pWC.nSlot*2 );
462 //if( pWC.a==null ){
463 // if( wtFlags & TERM_DYNAMIC ){
464 // sqlite3ExprDelete(db, ref p);
465 // }
466 // pWC.a = pOld;
467 // return 0;
468 //}
469 //memcpy(pWC.a, pOld, sizeof(pWC.a[0])*pWC.nTerm);
470 //if( pOld!=pWC.aStatic ){
471 // sqlite3DbFree(db, ref pOld);
472 //}
473 //pWC.nSlot = sqlite3DbMallocSize(db, pWC.a)/sizeof(pWC.a[0]);
474 pWC.nSlot = pWC.a.Length - 1;
475 }
476 pWC.a[idx = pWC.nTerm++] = new WhereTerm();
477 pTerm = pWC.a[idx];
478 pTerm.pExpr = p;
479 pTerm.wtFlags = wtFlags;
480 pTerm.pWC = pWC;
481 pTerm.iParent = -1;
482 return idx;
483 }
484  
485 /*
486 ** This routine identifies subexpressions in the WHERE clause where
487 ** each subexpression is separated by the AND operator or some other
488 ** operator specified in the op parameter. The WhereClause structure
489 ** is filled with pointers to subexpressions. For example:
490 **
491 ** WHERE a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
492 ** \________/ \_______________/ \________________/
493 ** slot[0] slot[1] slot[2]
494 **
495 ** The original WHERE clause in pExpr is unaltered. All this routine
496 ** does is make slot[] entries point to substructure within pExpr.
497 **
498 ** In the previous sentence and in the diagram, "slot[]" refers to
499 ** the WhereClause.a[] array. The slot[] array grows as needed to contain
500 ** all terms of the WHERE clause.
501 */
502 static void whereSplit( WhereClause pWC, Expr pExpr, int op )
503 {
504 pWC.op = (u8)op;
505 if ( pExpr == null )
506 return;
507 if ( pExpr.op != op )
508 {
509 whereClauseInsert( pWC, pExpr, 0 );
510 }
511 else
512 {
513 whereSplit( pWC, pExpr.pLeft, op );
514 whereSplit( pWC, pExpr.pRight, op );
515 }
516 }
517  
518 /*
519 ** Initialize an expression mask set (a WhereMaskSet object)
520 */
521 //#define initMaskSet(P) memset(P, 0, sizeof(*P))
522  
523 /*
524 ** Return the bitmask for the given cursor number. Return 0 if
525 ** iCursor is not in the set.
526 */
527 static Bitmask getMask( WhereMaskSet pMaskSet, int iCursor )
528 {
529 int i;
530 Debug.Assert( pMaskSet.n <= (int)sizeof( Bitmask ) * 8 );
531 for ( i = 0; i < pMaskSet.n; i++ )
532 {
533 if ( pMaskSet.ix[i] == iCursor )
534 {
535 return ( (Bitmask)1 ) << i;
536 }
537 }
538 return 0;
539 }
540  
541 /*
542 ** Create a new mask for cursor iCursor.
543 **
544 ** There is one cursor per table in the FROM clause. The number of
545 ** tables in the FROM clause is limited by a test early in the
546 ** sqlite3WhereBegin() routine. So we know that the pMaskSet.ix[]
547 ** array will never overflow.
548 */
549 static void createMask( WhereMaskSet pMaskSet, int iCursor )
550 {
551 Debug.Assert( pMaskSet.n < ArraySize( pMaskSet.ix ) );
552 pMaskSet.ix[pMaskSet.n++] = iCursor;
553 }
554  
555 /*
556 ** This routine walks (recursively) an expression tree and generates
557 ** a bitmask indicating which tables are used in that expression
558 ** tree.
559 **
560 ** In order for this routine to work, the calling function must have
561 ** previously invoked sqlite3ResolveExprNames() on the expression. See
562 ** the header comment on that routine for additional information.
563 ** The sqlite3ResolveExprNames() routines looks for column names and
564 ** sets their opcodes to TK_COLUMN and their Expr.iTable fields to
565 ** the VDBE cursor number of the table. This routine just has to
566 ** translate the cursor numbers into bitmask values and OR all
567 ** the bitmasks together.
568 */
569 //static Bitmask exprListTableUsage(WhereMaskSet*, ExprList);
570 //static Bitmask exprSelectTableUsage(WhereMaskSet*, Select);
571 static Bitmask exprTableUsage( WhereMaskSet pMaskSet, Expr p )
572 {
573 Bitmask mask = 0;
574 if ( p == null )
575 return 0;
576 if ( p.op == TK_COLUMN )
577 {
578 mask = getMask( pMaskSet, p.iTable );
579 return mask;
580 }
581 mask = exprTableUsage( pMaskSet, p.pRight );
582 mask |= exprTableUsage( pMaskSet, p.pLeft );
583 if ( ExprHasProperty( p, EP_xIsSelect ) )
584 {
585 mask |= exprSelectTableUsage( pMaskSet, p.x.pSelect );
586 }
587 else
588 {
589 mask |= exprListTableUsage( pMaskSet, p.x.pList );
590 }
591 return mask;
592 }
593 static Bitmask exprListTableUsage( WhereMaskSet pMaskSet, ExprList pList )
594 {
595 int i;
596 Bitmask mask = 0;
597 if ( pList != null )
598 {
599 for ( i = 0; i < pList.nExpr; i++ )
600 {
601 mask |= exprTableUsage( pMaskSet, pList.a[i].pExpr );
602 }
603 }
604 return mask;
605 }
606 static Bitmask exprSelectTableUsage( WhereMaskSet pMaskSet, Select pS )
607 {
608 Bitmask mask = 0;
609 while ( pS != null )
610 {
611 mask |= exprListTableUsage( pMaskSet, pS.pEList );
612 mask |= exprListTableUsage( pMaskSet, pS.pGroupBy );
613 mask |= exprListTableUsage( pMaskSet, pS.pOrderBy );
614 mask |= exprTableUsage( pMaskSet, pS.pWhere );
615 mask |= exprTableUsage( pMaskSet, pS.pHaving );
616 pS = pS.pPrior;
617 }
618 return mask;
619 }
620  
621 /*
622 ** Return TRUE if the given operator is one of the operators that is
623 ** allowed for an indexable WHERE clause term. The allowed operators are
624 ** "=", "<", ">", "<=", ">=", and "IN".
625 **
626 ** IMPLEMENTATION-OF: R-59926-26393 To be usable by an index a term must be
627 ** of one of the following forms: column = expression column > expression
628 ** column >= expression column < expression column <= expression
629 ** expression = column expression > column expression >= column
630 ** expression < column expression <= column column IN
631 ** (expression-list) column IN (subquery) column IS NULL
632 */
633 static bool allowedOp( int op )
634 {
635 Debug.Assert( TK_GT > TK_EQ && TK_GT < TK_GE );
636 Debug.Assert( TK_LT > TK_EQ && TK_LT < TK_GE );
637 Debug.Assert( TK_LE > TK_EQ && TK_LE < TK_GE );
638 Debug.Assert( TK_GE == TK_EQ + 4 );
639 return op == TK_IN || ( op >= TK_EQ && op <= TK_GE ) || op == TK_ISNULL;
640 }
641  
642 /*
643 ** Swap two objects of type TYPE.
644 */
645 //#define SWAP(TYPE,A,B) {TYPE t=A; A=B; B=t;}
646  
647 /*
648 ** Commute a comparison operator. Expressions of the form "X op Y"
649 ** are converted into "Y op X".
650 **
651 ** If a collation sequence is Debug.Associated with either the left or right
652 ** side of the comparison, it remains Debug.Associated with the same side after
653 ** the commutation. So "Y collate NOCASE op X" becomes
654 ** "X collate NOCASE op Y". This is because any collation sequence on
655 ** the left hand side of a comparison overrides any collation sequence
656 ** attached to the right. For the same reason the EP_ExpCollate flag
657 ** is not commuted.
658 */
659 static void exprCommute( Parse pParse, Expr pExpr )
660 {
661 u16 expRight = (u16)( pExpr.pRight.flags & EP_ExpCollate );
662 u16 expLeft = (u16)( pExpr.pLeft.flags & EP_ExpCollate );
663 Debug.Assert( allowedOp( pExpr.op ) && pExpr.op != TK_IN );
664 pExpr.pRight.pColl = sqlite3ExprCollSeq( pParse, pExpr.pRight );
665 pExpr.pLeft.pColl = sqlite3ExprCollSeq( pParse, pExpr.pLeft );
666 SWAP( ref pExpr.pRight.pColl, ref pExpr.pLeft.pColl );
667 pExpr.pRight.flags = (u16)( ( pExpr.pRight.flags & ~EP_ExpCollate ) | expLeft );
668 pExpr.pLeft.flags = (u16)( ( pExpr.pLeft.flags & ~EP_ExpCollate ) | expRight );
669 SWAP( ref pExpr.pRight, ref pExpr.pLeft );
670 if ( pExpr.op >= TK_GT )
671 {
672 Debug.Assert( TK_LT == TK_GT + 2 );
673 Debug.Assert( TK_GE == TK_LE + 2 );
674 Debug.Assert( TK_GT > TK_EQ );
675 Debug.Assert( TK_GT < TK_LE );
676 Debug.Assert( pExpr.op >= TK_GT && pExpr.op <= TK_GE );
677 pExpr.op = (u8)( ( ( pExpr.op - TK_GT ) ^ 2 ) + TK_GT );
678 }
679 }
680  
681 /*
682 ** Translate from TK_xx operator to WO_xx bitmask.
683 */
684 static u16 operatorMask( int op )
685 {
686 u16 c;
687 Debug.Assert( allowedOp( op ) );
688 if ( op == TK_IN )
689 {
690 c = WO_IN;
691 }
692 else if ( op == TK_ISNULL )
693 {
694 c = WO_ISNULL;
695 }
696 else
697 {
698 Debug.Assert( ( WO_EQ << ( op - TK_EQ ) ) < 0x7fff );
699 c = (u16)( WO_EQ << ( op - TK_EQ ) );
700 }
701 Debug.Assert( op != TK_ISNULL || c == WO_ISNULL );
702 Debug.Assert( op != TK_IN || c == WO_IN );
703 Debug.Assert( op != TK_EQ || c == WO_EQ );
704 Debug.Assert( op != TK_LT || c == WO_LT );
705 Debug.Assert( op != TK_LE || c == WO_LE );
706 Debug.Assert( op != TK_GT || c == WO_GT );
707 Debug.Assert( op != TK_GE || c == WO_GE );
708 return c;
709 }
710  
711 /*
712 ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
713 ** where X is a reference to the iColumn of table iCur and <op> is one of
714 ** the WO_xx operator codes specified by the op parameter.
715 ** Return a pointer to the term. Return 0 if not found.
716 */
717 static WhereTerm findTerm(
718 WhereClause pWC, /* The WHERE clause to be searched */
719 int iCur, /* Cursor number of LHS */
720 int iColumn, /* Column number of LHS */
721 Bitmask notReady, /* RHS must not overlap with this mask */
722 u32 op, /* Mask of WO_xx values describing operator */
723 Index pIdx /* Must be compatible with this index, if not NULL */
724 )
725 {
726 WhereTerm pTerm;
727 int k;
728 Debug.Assert( iCur >= 0 );
729 op &= WO_ALL;
730 for ( k = pWC.nTerm; k != 0; k-- )//, pTerm++)
731 {
732 pTerm = pWC.a[pWC.nTerm - k];
733 if ( pTerm.leftCursor == iCur
734 && ( pTerm.prereqRight & notReady ) == 0
735 && pTerm.u.leftColumn == iColumn
736 && ( pTerm.eOperator & op ) != 0
737 )
738 {
739 if ( pIdx != null && pTerm.eOperator != WO_ISNULL )
740 {
741 Expr pX = pTerm.pExpr;
742 CollSeq pColl;
743 char idxaff;
744 int j;
745 Parse pParse = pWC.pParse;
746  
747 idxaff = pIdx.pTable.aCol[iColumn].affinity;
748 if ( !sqlite3IndexAffinityOk( pX, idxaff ) )
749 continue;
750  
751 /* Figure out the collation sequence required from an index for
752 ** it to be useful for optimising expression pX. Store this
753 ** value in variable pColl.
754 */
755 Debug.Assert( pX.pLeft != null );
756 pColl = sqlite3BinaryCompareCollSeq( pParse, pX.pLeft, pX.pRight );
757 Debug.Assert( pColl != null || pParse.nErr != 0 );
758  
759 for ( j = 0; pIdx.aiColumn[j] != iColumn; j++ )
760 {
761 if ( NEVER( j >= pIdx.nColumn ) )
762 return null;
763 }
764 if ( pColl != null && !pColl.zName.Equals( pIdx.azColl[j], StringComparison.OrdinalIgnoreCase ) )
765 continue;
766 }
767 return pTerm;
768 }
769 }
770 return null;
771 }
772  
773 /* Forward reference */
774 //static void exprAnalyze(SrcList*, WhereClause*, int);
775  
776 /*
777 ** Call exprAnalyze on all terms in a WHERE clause.
778 **
779 **
780 */
781 static void exprAnalyzeAll(
782 SrcList pTabList, /* the FROM clause */
783 WhereClause pWC /* the WHERE clause to be analyzed */
784 )
785 {
786 int i;
787 for ( i = pWC.nTerm - 1; i >= 0; i-- )
788 {
789 exprAnalyze( pTabList, pWC, i );
790 }
791 }
792  
793 #if !SQLITE_OMIT_LIKE_OPTIMIZATION
794 /*
795 ** Check to see if the given expression is a LIKE or GLOB operator that
796 ** can be optimized using inequality constraints. Return TRUE if it is
797 ** so and false if not.
798 **
799 ** In order for the operator to be optimizible, the RHS must be a string
800 ** literal that does not begin with a wildcard.
801 */
802 static int isLikeOrGlob(
803 Parse pParse, /* Parsing and code generating context */
804 Expr pExpr, /* Test this expression */
805 ref Expr ppPrefix, /* Pointer to TK_STRING expression with pattern prefix */
806 ref bool pisComplete, /* True if the only wildcard is % in the last character */
807 ref bool pnoCase /* True if uppercase is equivalent to lowercase */
808 )
809 {
810 string z = null; /* String on RHS of LIKE operator */
811 Expr pRight, pLeft; /* Right and left size of LIKE operator */
812 ExprList pList; /* List of operands to the LIKE operator */
813 int c = 0; /* One character in z[] */
814 int cnt; /* Number of non-wildcard prefix characters */
815 char[] wc = new char[3]; /* Wildcard characters */
816 sqlite3 db = pParse.db; /* Data_base connection */
817 sqlite3_value pVal = null;
818 int op; /* Opcode of pRight */
819  
820 if ( !sqlite3IsLikeFunction( db, pExpr, ref pnoCase, wc ) )
821 {
822 return 0;
823 }
824 //#if SQLITE_EBCDIC
825 //if( pnoCase ) return 0;
826 //#endif
827 pList = pExpr.x.pList;
828 pLeft = pList.a[1].pExpr;
829 if ( pLeft.op != TK_COLUMN || sqlite3ExprAffinity( pLeft ) != SQLITE_AFF_TEXT )
830 {
831 /* IMP: R-02065-49465 The left-hand side of the LIKE or GLOB operator must
832 ** be the name of an indexed column with TEXT affinity. */
833 return 0;
834 }
835 Debug.Assert( pLeft.iColumn != ( -1 ) ); /* Because IPK never has AFF_TEXT */
836  
837 pRight = pList.a[0].pExpr;
838 op = pRight.op;
839 if ( op == TK_REGISTER )
840 {
841 op = pRight.op2;
842 }
843 if ( op == TK_VARIABLE )
844 {
845 Vdbe pReprepare = pParse.pReprepare;
846 int iCol = pRight.iColumn;
847 pVal = sqlite3VdbeGetValue( pReprepare, iCol, (byte)SQLITE_AFF_NONE );
848 if ( pVal != null && sqlite3_value_type( pVal ) == SQLITE_TEXT )
849 {
850 z = sqlite3_value_text( pVal );
851 }
852 sqlite3VdbeSetVarmask( pParse.pVdbe, iCol ); /* IMP: R-23257-02778 */
853 Debug.Assert( pRight.op == TK_VARIABLE || pRight.op == TK_REGISTER );
854 }
855 else if ( op == TK_STRING )
856 {
857 z = pRight.u.zToken;
858 }
859 if ( !string.IsNullOrEmpty( z ) )
860 {
861 cnt = 0;
862 while ( cnt < z.Length && ( c = z[cnt] ) != 0 && c != wc[0] && c != wc[1] && c != wc[2] )
863 {
864 cnt++;
865 }
866 if ( cnt != 0 && 255 != (u8)z[cnt - 1] )
867 {
868 Expr pPrefix;
869 pisComplete = c == wc[0] && cnt == z.Length - 1;
870 pPrefix = sqlite3Expr( db, TK_STRING, z );
871 if ( pPrefix != null )
872 pPrefix.u.zToken = pPrefix.u.zToken.Substring( 0, cnt );
873 ppPrefix = pPrefix;
874 if ( op == TK_VARIABLE )
875 {
876 Vdbe v = pParse.pVdbe;
877 sqlite3VdbeSetVarmask( v, pRight.iColumn ); /* IMP: R-23257-02778 */
878 if ( pisComplete && pRight.u.zToken.Length > 1 )
879 {
880 /* If the rhs of the LIKE expression is a variable, and the current
881 ** value of the variable means there is no need to invoke the LIKE
882 ** function, then no OP_Variable will be added to the program.
883 ** This causes problems for the sqlite3_bind_parameter_name()
884 ** API. To workaround them, add a dummy OP_Variable here.
885 */
886 int r1 = sqlite3GetTempReg( pParse );
887 sqlite3ExprCodeTarget( pParse, pRight, r1 );
888 sqlite3VdbeChangeP3( v, sqlite3VdbeCurrentAddr( v ) - 1, 0 );
889 sqlite3ReleaseTempReg( pParse, r1 );
890 }
891 }
892 }
893 else
894 {
895 z = null;
896 }
897 }
898  
899 sqlite3ValueFree( ref pVal );
900 return ( z != null ) ? 1 : 0;
901 }
902 #endif //* SQLITE_OMIT_LIKE_OPTIMIZATION */
903  
904  
905 #if !SQLITE_OMIT_VIRTUALTABLE
906 /*
907 ** Check to see if the given expression is of the form
908 **
909 ** column MATCH expr
910 **
911 ** If it is then return TRUE. If not, return FALSE.
912 */
913 static int isMatchOfColumn(
914 Expr pExpr /* Test this expression */
915 ){
916 ExprList pList;
917  
918 if( pExpr.op!=TK_FUNCTION ){
919 return 0;
920 }
921 if( !pExpr.u.zToken.Equals("match", StringComparison.OrdinalIgnoreCase ) ){
922 return 0;
923 }
924 pList = pExpr.x.pList;
925 if( pList.nExpr!=2 ){
926 return 0;
927 }
928 if( pList.a[1].pExpr.op != TK_COLUMN ){
929 return 0;
930 }
931 return 1;
932 }
933 #endif //* SQLITE_OMIT_VIRTUALTABLE */
934  
935 /*
936 ** If the pBase expression originated in the ON or USING clause of
937 ** a join, then transfer the appropriate markings over to derived.
938 */
939 static void transferJoinMarkings( Expr pDerived, Expr pBase )
940 {
941 pDerived.flags = (u16)( pDerived.flags | pBase.flags & EP_FromJoin );
942 pDerived.iRightJoinTable = pBase.iRightJoinTable;
943 }
944  
945 #if !(SQLITE_OMIT_OR_OPTIMIZATION) && !(SQLITE_OMIT_SUBQUERY)
946 /*
947 ** Analyze a term that consists of two or more OR-connected
948 ** subterms. So in:
949 **
950 ** ... WHERE (a=5) AND (b=7 OR c=9 OR d=13) AND (d=13)
951 ** ^^^^^^^^^^^^^^^^^^^^
952 **
953 ** This routine analyzes terms such as the middle term in the above example.
954 ** A WhereOrTerm object is computed and attached to the term under
955 ** analysis, regardless of the outcome of the analysis. Hence:
956 **
957 ** WhereTerm.wtFlags |= TERM_ORINFO
958 ** WhereTerm.u.pOrInfo = a dynamically allocated WhereOrTerm object
959 **
960 ** The term being analyzed must have two or more of OR-connected subterms.
961 ** A single subterm might be a set of AND-connected sub-subterms.
962 ** Examples of terms under analysis:
963 **
964 ** (A) t1.x=t2.y OR t1.x=t2.z OR t1.y=15 OR t1.z=t3.a+5
965 ** (B) x=expr1 OR expr2=x OR x=expr3
966 ** (C) t1.x=t2.y OR (t1.x=t2.z AND t1.y=15)
967 ** (D) x=expr1 OR (y>11 AND y<22 AND z LIKE '*hello*')
968 ** (E) (p.a=1 AND q.b=2 AND r.c=3) OR (p.x=4 AND q.y=5 AND r.z=6)
969 **
970 ** CASE 1:
971 **
972 ** If all subterms are of the form T.C=expr for some single column of C
973 ** a single table T (as shown in example B above) then create a new virtual
974 ** term that is an equivalent IN expression. In other words, if the term
975 ** being analyzed is:
976 **
977 ** x = expr1 OR expr2 = x OR x = expr3
978 **
979 ** then create a new virtual term like this:
980 **
981 ** x IN (expr1,expr2,expr3)
982 **
983 ** CASE 2:
984 **
985 ** If all subterms are indexable by a single table T, then set
986 **
987 ** WhereTerm.eOperator = WO_OR
988 ** WhereTerm.u.pOrInfo.indexable |= the cursor number for table T
989 **
990 ** A subterm is "indexable" if it is of the form
991 ** "T.C <op> <expr>" where C is any column of table T and
992 ** <op> is one of "=", "<", "<=", ">", ">=", "IS NULL", or "IN".
993 ** A subterm is also indexable if it is an AND of two or more
994 ** subsubterms at least one of which is indexable. Indexable AND
995 ** subterms have their eOperator set to WO_AND and they have
996 ** u.pAndInfo set to a dynamically allocated WhereAndTerm object.
997 **
998 ** From another point of view, "indexable" means that the subterm could
999 ** potentially be used with an index if an appropriate index exists.
1000 ** This analysis does not consider whether or not the index exists; that
1001 ** is something the bestIndex() routine will determine. This analysis
1002 ** only looks at whether subterms appropriate for indexing exist.
1003 **
1004 ** All examples A through E above all satisfy case 2. But if a term
1005 ** also statisfies case 1 (such as B) we know that the optimizer will
1006 ** always prefer case 1, so in that case we pretend that case 2 is not
1007 ** satisfied.
1008 **
1009 ** It might be the case that multiple tables are indexable. For example,
1010 ** (E) above is indexable on tables P, Q, and R.
1011 **
1012 ** Terms that satisfy case 2 are candidates for lookup by using
1013 ** separate indices to find rowids for each subterm and composing
1014 ** the union of all rowids using a RowSet object. This is similar
1015 ** to "bitmap indices" in other data_base engines.
1016 **
1017 ** OTHERWISE:
1018 **
1019 ** If neither case 1 nor case 2 apply, then leave the eOperator set to
1020 ** zero. This term is not useful for search.
1021 */
1022 static void exprAnalyzeOrTerm(
1023 SrcList pSrc, /* the FROM clause */
1024 WhereClause pWC, /* the complete WHERE clause */
1025 int idxTerm /* Index of the OR-term to be analyzed */
1026 )
1027 {
1028 Parse pParse = pWC.pParse; /* Parser context */
1029 sqlite3 db = pParse.db; /* Data_base connection */
1030 WhereTerm pTerm = pWC.a[idxTerm]; /* The term to be analyzed */
1031 Expr pExpr = pTerm.pExpr; /* The expression of the term */
1032 WhereMaskSet pMaskSet = pWC.pMaskSet; /* Table use masks */
1033 int i; /* Loop counters */
1034 WhereClause pOrWc; /* Breakup of pTerm into subterms */
1035 WhereTerm pOrTerm; /* A Sub-term within the pOrWc */
1036 WhereOrInfo pOrInfo; /* Additional information Debug.Associated with pTerm */
1037 Bitmask chngToIN; /* Tables that might satisfy case 1 */
1038 Bitmask indexable; /* Tables that are indexable, satisfying case 2 */
1039  
1040 /*
1041 ** Break the OR clause into its separate subterms. The subterms are
1042 ** stored in a WhereClause structure containing within the WhereOrInfo
1043 ** object that is attached to the original OR clause term.
1044 */
1045 Debug.Assert( ( pTerm.wtFlags & ( TERM_DYNAMIC | TERM_ORINFO | TERM_ANDINFO ) ) == 0 );
1046 Debug.Assert( pExpr.op == TK_OR );
1047 pTerm.u.pOrInfo = pOrInfo = new WhereOrInfo();//sqlite3DbMallocZero(db, sizeof(*pOrInfo));
1048 if ( pOrInfo == null )
1049 return;
1050 pTerm.wtFlags |= TERM_ORINFO;
1051 pOrWc = pOrInfo.wc;
1052 whereClauseInit( pOrWc, pWC.pParse, pMaskSet );
1053 whereSplit( pOrWc, pExpr, TK_OR );
1054 exprAnalyzeAll( pSrc, pOrWc );
1055 // if ( db.mallocFailed != 0 ) return;
1056 Debug.Assert( pOrWc.nTerm >= 2 );
1057  
1058 /*
1059 ** Compute the set of tables that might satisfy cases 1 or 2.
1060 */
1061 indexable = ~(Bitmask)0;
1062 chngToIN = ~( pWC.vmask );
1063 for ( i = pOrWc.nTerm - 1; i >= 0 && indexable != 0; i-- )//, pOrTerm++ )
1064 {
1065 pOrTerm = pOrWc.a[i];
1066 if ( ( pOrTerm.eOperator & WO_SINGLE ) == 0 )
1067 {
1068 WhereAndInfo pAndInfo;
1069 Debug.Assert( pOrTerm.eOperator == 0 );
1070 Debug.Assert( ( pOrTerm.wtFlags & ( TERM_ANDINFO | TERM_ORINFO ) ) == 0 );
1071 chngToIN = 0;
1072 pAndInfo = new WhereAndInfo();//sqlite3DbMallocRaw(db, sizeof(*pAndInfo));
1073 if ( pAndInfo != null )
1074 {
1075 WhereClause pAndWC;
1076 WhereTerm pAndTerm;
1077 int j;
1078 Bitmask b = 0;
1079 pOrTerm.u.pAndInfo = pAndInfo;
1080 pOrTerm.wtFlags |= TERM_ANDINFO;
1081 pOrTerm.eOperator = WO_AND;
1082 pAndWC = pAndInfo.wc;
1083 whereClauseInit( pAndWC, pWC.pParse, pMaskSet );
1084 whereSplit( pAndWC, pOrTerm.pExpr, TK_AND );
1085 exprAnalyzeAll( pSrc, pAndWC );
1086 //testcase( db.mallocFailed );
1087 ////if ( 0 == db.mallocFailed )
1088 {
1089 for ( j = 0; j < pAndWC.nTerm; j++ )//, pAndTerm++ )
1090 {
1091 pAndTerm = pAndWC.a[j];
1092 Debug.Assert( pAndTerm.pExpr != null );
1093 if ( allowedOp( pAndTerm.pExpr.op ) )
1094 {
1095 b |= getMask( pMaskSet, pAndTerm.leftCursor );
1096 }
1097 }
1098 }
1099 indexable &= b;
1100 }
1101 }
1102 else if ( ( pOrTerm.wtFlags & TERM_COPIED ) != 0 )
1103 {
1104 /* Skip this term for now. We revisit it when we process the
1105 ** corresponding TERM_VIRTUAL term */
1106 }
1107 else
1108 {
1109 Bitmask b;
1110 b = getMask( pMaskSet, pOrTerm.leftCursor );
1111 if ( ( pOrTerm.wtFlags & TERM_VIRTUAL ) != 0 )
1112 {
1113 WhereTerm pOther = pOrWc.a[pOrTerm.iParent];
1114 b |= getMask( pMaskSet, pOther.leftCursor );
1115 }
1116 indexable &= b;
1117 if ( pOrTerm.eOperator != WO_EQ )
1118 {
1119 chngToIN = 0;
1120 }
1121 else
1122 {
1123 chngToIN &= b;
1124 }
1125 }
1126 }
1127  
1128 /*
1129 ** Record the set of tables that satisfy case 2. The set might be
1130 ** empty.
1131 */
1132 pOrInfo.indexable = indexable;
1133 pTerm.eOperator = (u16)( indexable == 0 ? 0 : WO_OR );
1134  
1135 /*
1136 ** chngToIN holds a set of tables that *might* satisfy case 1. But
1137 ** we have to do some additional checking to see if case 1 really
1138 ** is satisfied.
1139 **
1140 ** chngToIN will hold either 0, 1, or 2 bits. The 0-bit case means
1141 ** that there is no possibility of transforming the OR clause into an
1142 ** IN operator because one or more terms in the OR clause contain
1143 ** something other than == on a column in the single table. The 1-bit
1144 ** case means that every term of the OR clause is of the form
1145 ** "table.column=expr" for some single table. The one bit that is set
1146 ** will correspond to the common table. We still need to check to make
1147 ** sure the same column is used on all terms. The 2-bit case is when
1148 ** the all terms are of the form "table1.column=table2.column". It
1149 ** might be possible to form an IN operator with either table1.column
1150 ** or table2.column as the LHS if either is common to every term of
1151 ** the OR clause.
1152 **
1153 ** Note that terms of the form "table.column1=table.column2" (the
1154 ** same table on both sizes of the ==) cannot be optimized.
1155 */
1156 if ( chngToIN != 0 )
1157 {
1158 int okToChngToIN = 0; /* True if the conversion to IN is valid */
1159 int iColumn = -1; /* Column index on lhs of IN operator */
1160 int iCursor = -1; /* Table cursor common to all terms */
1161 int j = 0; /* Loop counter */
1162  
1163 /* Search for a table and column that appears on one side or the
1164 ** other of the == operator in every subterm. That table and column
1165 ** will be recorded in iCursor and iColumn. There might not be any
1166 ** such table and column. Set okToChngToIN if an appropriate table
1167 ** and column is found but leave okToChngToIN false if not found.
1168 */
1169 for ( j = 0; j < 2 && 0 == okToChngToIN; j++ )
1170 {
1171 //pOrTerm = pOrWc.a;
1172 for ( i = pOrWc.nTerm - 1; i >= 0; i-- )//, pOrTerm++)
1173 {
1174 pOrTerm = pOrWc.a[pOrWc.nTerm - 1 - i];
1175 Debug.Assert( pOrTerm.eOperator == WO_EQ );
1176 pOrTerm.wtFlags = (u8)( pOrTerm.wtFlags & ~TERM_OR_OK );
1177 if ( pOrTerm.leftCursor == iCursor )
1178 {
1179 /* This is the 2-bit case and we are on the second iteration and
1180 ** current term is from the first iteration. So skip this term. */
1181 Debug.Assert( j == 1 );
1182 continue;
1183 }
1184 if ( ( chngToIN & getMask( pMaskSet, pOrTerm.leftCursor ) ) == 0 )
1185 {
1186 /* This term must be of the form t1.a==t2.b where t2 is in the
1187 ** chngToIN set but t1 is not. This term will be either preceeded
1188 ** or follwed by an inverted copy (t2.b==t1.a). Skip this term
1189 ** and use its inversion. */
1190 testcase( pOrTerm.wtFlags & TERM_COPIED );
1191 testcase( pOrTerm.wtFlags & TERM_VIRTUAL );
1192 Debug.Assert( ( pOrTerm.wtFlags & ( TERM_COPIED | TERM_VIRTUAL ) ) != 0 );
1193 continue;
1194 }
1195 iColumn = pOrTerm.u.leftColumn;
1196 iCursor = pOrTerm.leftCursor;
1197 break;
1198 }
1199 if ( i < 0 )
1200 {
1201 /* No candidate table+column was found. This can only occur
1202 ** on the second iteration */
1203 Debug.Assert( j == 1 );
1204 Debug.Assert( ( chngToIN & ( chngToIN - 1 ) ) == 0 );
1205 Debug.Assert( chngToIN == getMask( pMaskSet, iCursor ) );
1206 break;
1207 }
1208 testcase( j == 1 );
1209  
1210 /* We have found a candidate table and column. Check to see if that
1211 ** table and column is common to every term in the OR clause */
1212 okToChngToIN = 1;
1213 for ( ; i >= 0 && okToChngToIN != 0; i-- )//, pOrTerm++)
1214 {
1215 pOrTerm = pOrWc.a[pOrWc.nTerm - 1 - i];
1216 Debug.Assert( pOrTerm.eOperator == WO_EQ );
1217 if ( pOrTerm.leftCursor != iCursor )
1218 {
1219 pOrTerm.wtFlags = (u8)( pOrTerm.wtFlags & ~TERM_OR_OK );
1220 }
1221 else if ( pOrTerm.u.leftColumn != iColumn )
1222 {
1223 okToChngToIN = 0;
1224 }
1225 else
1226 {
1227 int affLeft, affRight;
1228 /* If the right-hand side is also a column, then the affinities
1229 ** of both right and left sides must be such that no type
1230 ** conversions are required on the right. (Ticket #2249)
1231 */
1232 affRight = sqlite3ExprAffinity( pOrTerm.pExpr.pRight );
1233 affLeft = sqlite3ExprAffinity( pOrTerm.pExpr.pLeft );
1234 if ( affRight != 0 && affRight != affLeft )
1235 {
1236 okToChngToIN = 0;
1237 }
1238 else
1239 {
1240 pOrTerm.wtFlags |= TERM_OR_OK;
1241 }
1242 }
1243 }
1244 }
1245  
1246 /* At this point, okToChngToIN is true if original pTerm satisfies
1247 ** case 1. In that case, construct a new virtual term that is
1248 ** pTerm converted into an IN operator.
1249 **
1250 ** EV: R-00211-15100
1251 */
1252 if ( okToChngToIN != 0 )
1253 {
1254 Expr pDup; /* A transient duplicate expression */
1255 ExprList pList = null; /* The RHS of the IN operator */
1256 Expr pLeft = null; /* The LHS of the IN operator */
1257 Expr pNew; /* The complete IN operator */
1258  
1259 for ( i = pOrWc.nTerm - 1; i >= 0; i-- )//, pOrTerm++)
1260 {
1261 pOrTerm = pOrWc.a[pOrWc.nTerm - 1 - i];
1262 if ( ( pOrTerm.wtFlags & TERM_OR_OK ) == 0 )
1263 continue;
1264 Debug.Assert( pOrTerm.eOperator == WO_EQ );
1265 Debug.Assert( pOrTerm.leftCursor == iCursor );
1266 Debug.Assert( pOrTerm.u.leftColumn == iColumn );
1267 pDup = sqlite3ExprDup( db, pOrTerm.pExpr.pRight, 0 );
1268 pList = sqlite3ExprListAppend( pWC.pParse, pList, pDup );
1269 pLeft = pOrTerm.pExpr.pLeft;
1270 }
1271 Debug.Assert( pLeft != null );
1272 pDup = sqlite3ExprDup( db, pLeft, 0 );
1273 pNew = sqlite3PExpr( pParse, TK_IN, pDup, null, null );
1274 if ( pNew != null )
1275 {
1276 int idxNew;
1277 transferJoinMarkings( pNew, pExpr );
1278 Debug.Assert( !ExprHasProperty( pNew, EP_xIsSelect ) );
1279 pNew.x.pList = pList;
1280 idxNew = whereClauseInsert( pWC, pNew, TERM_VIRTUAL | TERM_DYNAMIC );
1281 testcase( idxNew == 0 );
1282 exprAnalyze( pSrc, pWC, idxNew );
1283 pTerm = pWC.a[idxTerm];
1284 pWC.a[idxNew].iParent = idxTerm;
1285 pTerm.nChild = 1;
1286 }
1287 else
1288 {
1289 sqlite3ExprListDelete( db, ref pList );
1290 }
1291 pTerm.eOperator = WO_NOOP; /* case 1 trumps case 2 */
1292 }
1293 }
1294 }
1295 #endif //* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
1296  
1297  
1298 /*
1299 ** The input to this routine is an WhereTerm structure with only the
1300 ** "pExpr" field filled in. The job of this routine is to analyze the
1301 ** subexpression and populate all the other fields of the WhereTerm
1302 ** structure.
1303 **
1304 ** If the expression is of the form "<expr> <op> X" it gets commuted
1305 ** to the standard form of "X <op> <expr>".
1306 **
1307 ** If the expression is of the form "X <op> Y" where both X and Y are
1308 ** columns, then the original expression is unchanged and a new virtual
1309 ** term of the form "Y <op> X" is added to the WHERE clause and
1310 ** analyzed separately. The original term is marked with TERM_COPIED
1311 ** and the new term is marked with TERM_DYNAMIC (because it's pExpr
1312 ** needs to be freed with the WhereClause) and TERM_VIRTUAL (because it
1313 ** is a commuted copy of a prior term.) The original term has nChild=1
1314 ** and the copy has idxParent set to the index of the original term.
1315 */
1316 static void exprAnalyze(
1317 SrcList pSrc, /* the FROM clause */
1318 WhereClause pWC, /* the WHERE clause */
1319 int idxTerm /* Index of the term to be analyzed */
1320 )
1321 {
1322 WhereTerm pTerm; /* The term to be analyzed */
1323 WhereMaskSet pMaskSet; /* Set of table index masks */
1324 Expr pExpr; /* The expression to be analyzed */
1325 Bitmask prereqLeft; /* Prerequesites of the pExpr.pLeft */
1326 Bitmask prereqAll; /* Prerequesites of pExpr */
1327 Bitmask extraRight = 0; /* Extra dependencies on LEFT JOIN */
1328 Expr pStr1 = null; /* RHS of LIKE/GLOB operator */
1329 bool isComplete = false; /* RHS of LIKE/GLOB ends with wildcard */
1330 bool noCase = false; /* LIKE/GLOB distinguishes case */
1331 int op; /* Top-level operator. pExpr.op */
1332 Parse pParse = pWC.pParse; /* Parsing context */
1333 sqlite3 db = pParse.db; /* Data_base connection */
1334  
1335 //if ( db.mallocFailed != 0 )
1336 //{
1337 // return;
1338 //}
1339 pTerm = pWC.a[idxTerm];
1340 pMaskSet = pWC.pMaskSet;
1341 pExpr = pTerm.pExpr;
1342 prereqLeft = exprTableUsage( pMaskSet, pExpr.pLeft );
1343 op = pExpr.op;
1344 if ( op == TK_IN )
1345 {
1346 Debug.Assert( pExpr.pRight == null );
1347 if ( ExprHasProperty( pExpr, EP_xIsSelect ) )
1348 {
1349 pTerm.prereqRight = exprSelectTableUsage( pMaskSet, pExpr.x.pSelect );
1350 }
1351 else
1352 {
1353 pTerm.prereqRight = exprListTableUsage( pMaskSet, pExpr.x.pList );
1354 }
1355 }
1356 else if ( op == TK_ISNULL )
1357 {
1358 pTerm.prereqRight = 0;
1359 }
1360 else
1361 {
1362 pTerm.prereqRight = exprTableUsage( pMaskSet, pExpr.pRight );
1363 }
1364 prereqAll = exprTableUsage( pMaskSet, pExpr );
1365 if ( ExprHasProperty( pExpr, EP_FromJoin ) )
1366 {
1367 Bitmask x = getMask( pMaskSet, pExpr.iRightJoinTable );
1368 prereqAll |= x;
1369 extraRight = x - 1; /* ON clause terms may not be used with an index
1370 ** on left table of a LEFT JOIN. Ticket #3015 */
1371 }
1372 pTerm.prereqAll = prereqAll;
1373 pTerm.leftCursor = -1;
1374 pTerm.iParent = -1;
1375 pTerm.eOperator = 0;
1376 if ( allowedOp( op ) && ( pTerm.prereqRight & prereqLeft ) == 0 )
1377 {
1378 Expr pLeft = pExpr.pLeft;
1379 Expr pRight = pExpr.pRight;
1380 if ( pLeft.op == TK_COLUMN )
1381 {
1382 pTerm.leftCursor = pLeft.iTable;
1383 pTerm.u.leftColumn = pLeft.iColumn;
1384 pTerm.eOperator = operatorMask( op );
1385 }
1386 if ( pRight != null && pRight.op == TK_COLUMN )
1387 {
1388 WhereTerm pNew;
1389 Expr pDup;
1390 if ( pTerm.leftCursor >= 0 )
1391 {
1392 int idxNew;
1393 pDup = sqlite3ExprDup( db, pExpr, 0 );
1394 //if ( db.mallocFailed != 0 )
1395 //{
1396 // sqlite3ExprDelete( db, ref pDup );
1397 // return;
1398 //}
1399 idxNew = whereClauseInsert( pWC, pDup, TERM_VIRTUAL | TERM_DYNAMIC );
1400 if ( idxNew == 0 )
1401 return;
1402 pNew = pWC.a[idxNew];
1403 pNew.iParent = idxTerm;
1404 pTerm = pWC.a[idxTerm];
1405 pTerm.nChild = 1;
1406 pTerm.wtFlags |= TERM_COPIED;
1407 }
1408 else
1409 {
1410 pDup = pExpr;
1411 pNew = pTerm;
1412 }
1413 exprCommute( pParse, pDup );
1414 pLeft = pDup.pLeft;
1415 pNew.leftCursor = pLeft.iTable;
1416 pNew.u.leftColumn = pLeft.iColumn;
1417 testcase( ( prereqLeft | extraRight ) != prereqLeft );
1418 pNew.prereqRight = prereqLeft | extraRight;
1419 pNew.prereqAll = prereqAll;
1420 pNew.eOperator = operatorMask( pDup.op );
1421 }
1422 }
1423  
1424 #if !SQLITE_OMIT_BETWEEN_OPTIMIZATION
1425 /* If a term is the BETWEEN operator, create two new virtual terms
1426 ** that define the range that the BETWEEN implements. For example:
1427 **
1428 ** a BETWEEN b AND c
1429 **
1430 ** is converted into:
1431 **
1432 ** (a BETWEEN b AND c) AND (a>=b) AND (a<=c)
1433 **
1434 ** The two new terms are added onto the end of the WhereClause object.
1435 ** The new terms are "dynamic" and are children of the original BETWEEN
1436 ** term. That means that if the BETWEEN term is coded, the children are
1437 ** skipped. Or, if the children are satisfied by an index, the original
1438 ** BETWEEN term is skipped.
1439 */
1440 else if ( pExpr.op == TK_BETWEEN && pWC.op == TK_AND )
1441 {
1442 ExprList pList = pExpr.x.pList;
1443 int i;
1444 u8[] ops = new u8[] { TK_GE, TK_LE };
1445 Debug.Assert( pList != null );
1446 Debug.Assert( pList.nExpr == 2 );
1447 for ( i = 0; i < 2; i++ )
1448 {
1449 Expr pNewExpr;
1450 int idxNew;
1451 pNewExpr = sqlite3PExpr( pParse, ops[i],
1452 sqlite3ExprDup( db, pExpr.pLeft, 0 ),
1453 sqlite3ExprDup( db, pList.a[i].pExpr, 0 ), null );
1454 idxNew = whereClauseInsert( pWC, pNewExpr, TERM_VIRTUAL | TERM_DYNAMIC );
1455 testcase( idxNew == 0 );
1456 exprAnalyze( pSrc, pWC, idxNew );
1457 pTerm = pWC.a[idxTerm];
1458 pWC.a[idxNew].iParent = idxTerm;
1459 }
1460 pTerm.nChild = 2;
1461 }
1462 #endif //* SQLITE_OMIT_BETWEEN_OPTIMIZATION */
1463  
1464 #if !(SQLITE_OMIT_OR_OPTIMIZATION) && !(SQLITE_OMIT_SUBQUERY)
1465 /* Analyze a term that is composed of two or more subterms connected by
1466 ** an OR operator.
1467 */
1468 else if ( pExpr.op == TK_OR )
1469 {
1470 Debug.Assert( pWC.op == TK_AND );
1471 exprAnalyzeOrTerm( pSrc, pWC, idxTerm );
1472 pTerm = pWC.a[idxTerm];
1473 }
1474 #endif //* SQLITE_OMIT_OR_OPTIMIZATION */
1475  
1476 #if !SQLITE_OMIT_LIKE_OPTIMIZATION
1477 /* Add constraints to reduce the search space on a LIKE or GLOB
1478 ** operator.
1479 **
1480 ** A like pattern of the form "x LIKE 'abc%'" is changed into constraints
1481 **
1482 ** x>='abc' AND x<'abd' AND x LIKE 'abc%'
1483 **
1484 ** The last character of the prefix "abc" is incremented to form the
1485 ** termination condition "abd".
1486 */
1487 if ( pWC.op == TK_AND
1488 && isLikeOrGlob( pParse, pExpr, ref pStr1, ref isComplete, ref noCase ) != 0
1489 )
1490 {
1491 Expr pLeft; /* LHS of LIKE/GLOB operator */
1492 Expr pStr2; /* Copy of pStr1 - RHS of LIKE/GLOB operator */
1493 Expr pNewExpr1;
1494 Expr pNewExpr2;
1495 int idxNew1;
1496 int idxNew2;
1497 CollSeq pColl; /* Collating sequence to use */
1498  
1499 pLeft = pExpr.x.pList.a[1].pExpr;
1500 pStr2 = sqlite3ExprDup( db, pStr1, 0 );
1501 ////if ( 0 == db.mallocFailed )
1502 {
1503 int c, pC; /* Last character before the first wildcard */
1504 pC = pStr2.u.zToken[sqlite3Strlen30( pStr2.u.zToken ) - 1];
1505 c = pC;
1506 if ( noCase )
1507 {
1508 /* The point is to increment the last character before the first
1509 ** wildcard. But if we increment '@', that will push it into the
1510 ** alphabetic range where case conversions will mess up the
1511 ** inequality. To avoid this, make sure to also run the full
1512 ** LIKE on all candidate expressions by clearing the isComplete flag
1513 */
1514 if ( c == 'A' - 1 )
1515 isComplete = false; /* EV: R-64339-08207 */
1516 c = sqlite3UpperToLower[c];
1517 }
1518 pStr2.u.zToken = pStr2.u.zToken.Substring( 0, sqlite3Strlen30( pStr2.u.zToken ) - 1 ) + (char)( c + 1 );// pC = c + 1;
1519 }
1520 pColl = sqlite3FindCollSeq( db, SQLITE_UTF8, noCase ? "NOCASE" : "BINARY", 0 );
1521 pNewExpr1 = sqlite3PExpr( pParse, TK_GE,
1522 sqlite3ExprSetColl( sqlite3ExprDup( db, pLeft, 0 ), pColl ),
1523 pStr1, 0 );
1524 idxNew1 = whereClauseInsert( pWC, pNewExpr1, TERM_VIRTUAL | TERM_DYNAMIC );
1525 testcase( idxNew1 == 0 );
1526 exprAnalyze( pSrc, pWC, idxNew1 );
1527 pNewExpr2 = sqlite3PExpr( pParse, TK_LT,
1528 sqlite3ExprSetColl( sqlite3ExprDup( db, pLeft, 0 ), pColl ),
1529 pStr2, null );
1530 idxNew2 = whereClauseInsert( pWC, pNewExpr2, TERM_VIRTUAL | TERM_DYNAMIC );
1531 testcase( idxNew2 == 0 );
1532 exprAnalyze( pSrc, pWC, idxNew2 );
1533 pTerm = pWC.a[idxTerm];
1534 if ( isComplete )
1535 {
1536 pWC.a[idxNew1].iParent = idxTerm;
1537 pWC.a[idxNew2].iParent = idxTerm;
1538 pTerm.nChild = 2;
1539 }
1540 }
1541 #endif //* SQLITE_OMIT_LIKE_OPTIMIZATION */
1542  
1543 #if !SQLITE_OMIT_VIRTUALTABLE
1544 /* Add a WO_MATCH auxiliary term to the constraint set if the
1545 ** current expression is of the form: column MATCH expr.
1546 ** This information is used by the xBestIndex methods of
1547 ** virtual tables. The native query optimizer does not attempt
1548 ** to do anything with MATCH functions.
1549 */
1550 if ( isMatchOfColumn( pExpr ) != 0 )
1551 {
1552 int idxNew;
1553 Expr pRight, pLeft;
1554 WhereTerm pNewTerm;
1555 Bitmask prereqColumn, prereqExpr;
1556  
1557 pRight = pExpr.x.pList.a[0].pExpr;
1558 pLeft = pExpr.x.pList.a[1].pExpr;
1559 prereqExpr = exprTableUsage( pMaskSet, pRight );
1560 prereqColumn = exprTableUsage( pMaskSet, pLeft );
1561 if ( ( prereqExpr & prereqColumn ) == 0 )
1562 {
1563 Expr pNewExpr;
1564 pNewExpr = sqlite3PExpr( pParse, TK_MATCH,
1565 null, sqlite3ExprDup( db, pRight, 0 ), null );
1566 idxNew = whereClauseInsert( pWC, pNewExpr, TERM_VIRTUAL | TERM_DYNAMIC );
1567 testcase( idxNew == 0 );
1568 pNewTerm = pWC.a[idxNew];
1569 pNewTerm.prereqRight = prereqExpr;
1570 pNewTerm.leftCursor = pLeft.iTable;
1571 pNewTerm.u.leftColumn = pLeft.iColumn;
1572 pNewTerm.eOperator = WO_MATCH;
1573 pNewTerm.iParent = idxTerm;
1574 pTerm = pWC.a[idxTerm];
1575 pTerm.nChild = 1;
1576 pTerm.wtFlags |= TERM_COPIED;
1577 pNewTerm.prereqAll = pTerm.prereqAll;
1578 }
1579 }
1580 #endif //* SQLITE_OMIT_VIRTUALTABLE */
1581  
1582 #if SQLITE_ENABLE_STAT2
1583 /* When sqlite_stat2 histogram data is available an operator of the
1584 ** form "x IS NOT NULL" can sometimes be evaluated more efficiently
1585 ** as "x>NULL" if x is not an INTEGER PRIMARY KEY. So construct a
1586 ** virtual term of that form.
1587 **
1588 ** Note that the virtual term must be tagged with TERM_VNULL. This
1589 ** TERM_VNULL tag will suppress the not-null check at the beginning
1590 ** of the loop. Without the TERM_VNULL flag, the not-null check at
1591 ** the start of the loop will prevent any results from being returned.
1592 */
1593 if ( pExpr.op == TK_NOTNULL
1594 && pExpr.pLeft.op == TK_COLUMN
1595 && pExpr.pLeft.iColumn >= 0
1596 )
1597 {
1598 Expr pNewExpr;
1599 Expr pLeft = pExpr.pLeft;
1600 int idxNew;
1601 WhereTerm pNewTerm;
1602  
1603 pNewExpr = sqlite3PExpr( pParse, TK_GT,
1604 sqlite3ExprDup( db, pLeft, 0 ),
1605 sqlite3PExpr( pParse, TK_NULL, 0, 0, 0 ), 0 );
1606  
1607 idxNew = whereClauseInsert( pWC, pNewExpr,
1608 TERM_VIRTUAL | TERM_DYNAMIC | TERM_VNULL );
1609 if ( idxNew != 0 )
1610 {
1611 pNewTerm = pWC.a[idxNew];
1612 pNewTerm.prereqRight = 0;
1613 pNewTerm.leftCursor = pLeft.iTable;
1614 pNewTerm.u.leftColumn = pLeft.iColumn;
1615 pNewTerm.eOperator = WO_GT;
1616 pNewTerm.iParent = idxTerm;
1617 pTerm = pWC.a[idxTerm];
1618 pTerm.nChild = 1;
1619 pTerm.wtFlags |= TERM_COPIED;
1620 pNewTerm.prereqAll = pTerm.prereqAll;
1621 }
1622 }
1623 #endif //* SQLITE_ENABLE_STAT2 */
1624  
1625 /* Prevent ON clause terms of a LEFT JOIN from being used to drive
1626 ** an index for tables to the left of the join.
1627 */
1628 pTerm.prereqRight |= extraRight;
1629 }
1630  
1631 /*
1632 ** Return TRUE if any of the expressions in pList.a[iFirst...] contain
1633 ** a reference to any table other than the iBase table.
1634 */
1635 static bool referencesOtherTables(
1636 ExprList pList, /* Search expressions in ths list */
1637 WhereMaskSet pMaskSet, /* Mapping from tables to bitmaps */
1638 int iFirst, /* Be searching with the iFirst-th expression */
1639 int iBase /* Ignore references to this table */
1640 )
1641 {
1642 Bitmask allowed = ~getMask( pMaskSet, iBase );
1643 while ( iFirst < pList.nExpr )
1644 {
1645 if ( ( exprTableUsage( pMaskSet, pList.a[iFirst++].pExpr ) & allowed ) != 0 )
1646 {
1647 return true;
1648 }
1649 }
1650 return false;
1651 }
1652  
1653  
1654 /*
1655 ** This routine decides if pIdx can be used to satisfy the ORDER BY
1656 ** clause. If it can, it returns 1. If pIdx cannot satisfy the
1657 ** ORDER BY clause, this routine returns 0.
1658 **
1659 ** pOrderBy is an ORDER BY clause from a SELECT statement. pTab is the
1660 ** left-most table in the FROM clause of that same SELECT statement and
1661 ** the table has a cursor number of "_base". pIdx is an index on pTab.
1662 **
1663 ** nEqCol is the number of columns of pIdx that are used as equality
1664 ** constraints. Any of these columns may be missing from the ORDER BY
1665 ** clause and the match can still be a success.
1666 **
1667 ** All terms of the ORDER BY that match against the index must be either
1668 ** ASC or DESC. (Terms of the ORDER BY clause past the end of a UNIQUE
1669 ** index do not need to satisfy this constraint.) The pbRev value is
1670 ** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
1671 ** the ORDER BY clause is all ASC.
1672 */
1673 static bool isSortingIndex(
1674 Parse pParse, /* Parsing context */
1675 WhereMaskSet pMaskSet, /* Mapping from table cursor numbers to bitmaps */
1676 Index pIdx, /* The index we are testing */
1677 int _base, /* Cursor number for the table to be sorted */
1678 ExprList pOrderBy, /* The ORDER BY clause */
1679 int nEqCol, /* Number of index columns with == constraints */
1680 int wsFlags, /* Index usages flags */
1681 ref int pbRev /* Set to 1 if ORDER BY is DESC */
1682 )
1683 {
1684 int i, j; /* Loop counters */
1685 int sortOrder = 0; /* XOR of index and ORDER BY sort direction */
1686 int nTerm; /* Number of ORDER BY terms */
1687 ExprList_item pTerm; /* A term of the ORDER BY clause */
1688 sqlite3 db = pParse.db;
1689  
1690 Debug.Assert( pOrderBy != null );
1691 nTerm = pOrderBy.nExpr;
1692 Debug.Assert( nTerm > 0 );
1693  
1694 /* Argument pIdx must either point to a 'real' named index structure,
1695 ** or an index structure allocated on the stack by bestBtreeIndex() to
1696 ** represent the rowid index that is part of every table. */
1697 Debug.Assert( !string.IsNullOrEmpty( pIdx.zName ) || ( pIdx.nColumn == 1 && pIdx.aiColumn[0] == -1 ) );
1698  
1699 /* Match terms of the ORDER BY clause against columns of
1700 ** the index.
1701 **
1702 ** Note that indices have pIdx.nColumn regular columns plus
1703 ** one additional column containing the rowid. The rowid column
1704 ** of the index is also allowed to match against the ORDER BY
1705 ** clause.
1706 */
1707 for ( i = j = 0; j < nTerm && i <= pIdx.nColumn; i++ )
1708 {
1709 pTerm = pOrderBy.a[j];
1710 Expr pExpr; /* The expression of the ORDER BY pTerm */
1711 CollSeq pColl; /* The collating sequence of pExpr */
1712 int termSortOrder; /* Sort order for this term */
1713 int iColumn; /* The i-th column of the index. -1 for rowid */
1714 int iSortOrder; /* 1 for DESC, 0 for ASC on the i-th index term */
1715 string zColl; /* Name of the collating sequence for i-th index term */
1716  
1717 pExpr = pTerm.pExpr;
1718 if ( pExpr.op != TK_COLUMN || pExpr.iTable != _base )
1719 {
1720 /* Can not use an index sort on anything that is not a column in the
1721 ** left-most table of the FROM clause */
1722 break;
1723 }
1724 pColl = sqlite3ExprCollSeq( pParse, pExpr );
1725 if ( null == pColl )
1726 {
1727 pColl = db.pDfltColl;
1728 }
1729 if ( !string.IsNullOrEmpty( pIdx.zName ) && i < pIdx.nColumn )
1730 {
1731 iColumn = pIdx.aiColumn[i];
1732 if ( iColumn == pIdx.pTable.iPKey )
1733 {
1734 iColumn = -1;
1735 }
1736 iSortOrder = pIdx.aSortOrder[i];
1737 zColl = pIdx.azColl[i];
1738 }
1739 else
1740 {
1741 iColumn = -1;
1742 iSortOrder = 0;
1743 zColl = pColl.zName;
1744 }
1745 if ( pExpr.iColumn != iColumn || !pColl.zName.Equals( zColl, StringComparison.OrdinalIgnoreCase ) )
1746 {
1747 /* Term j of the ORDER BY clause does not match column i of the index */
1748 if ( i < nEqCol )
1749 {
1750 /* If an index column that is constrained by == fails to match an
1751 ** ORDER BY term, that is OK. Just ignore that column of the index
1752 */
1753 continue;
1754 }
1755 else if ( i == pIdx.nColumn )
1756 {
1757 /* Index column i is the rowid. All other terms match. */
1758 break;
1759 }
1760 else
1761 {
1762 /* If an index column fails to match and is not constrained by ==
1763 ** then the index cannot satisfy the ORDER BY constraint.
1764 */
1765 return false;
1766 }
1767 }
1768 Debug.Assert( pIdx.aSortOrder != null || iColumn == -1 );
1769 Debug.Assert( pTerm.sortOrder == 0 || pTerm.sortOrder == 1 );
1770 Debug.Assert( iSortOrder == 0 || iSortOrder == 1 );
1771 termSortOrder = iSortOrder ^ pTerm.sortOrder;
1772 if ( i > nEqCol )
1773 {
1774 if ( termSortOrder != sortOrder )
1775 {
1776 /* Indices can only be used if all ORDER BY terms past the
1777 ** equality constraints are all either DESC or ASC. */
1778 return false;
1779 }
1780 }
1781 else
1782 {
1783 sortOrder = termSortOrder;
1784 }
1785 j++;
1786 //pTerm++;
1787 if ( iColumn < 0 && !referencesOtherTables( pOrderBy, pMaskSet, j, _base ) )
1788 {
1789 /* If the indexed column is the primary key and everything matches
1790 ** so far and none of the ORDER BY terms to the right reference other
1791 ** tables in the join, then we are Debug.Assured that the index can be used
1792 ** to sort because the primary key is unique and so none of the other
1793 ** columns will make any difference
1794 */
1795 j = nTerm;
1796 }
1797 }
1798  
1799 pbRev = sortOrder != 0 ? 1 : 0;
1800 if ( j >= nTerm )
1801 {
1802 /* All terms of the ORDER BY clause are covered by this index so
1803 ** this index can be used for sorting. */
1804 return true;
1805 }
1806 if ( pIdx.onError != OE_None && i == pIdx.nColumn
1807 && ( wsFlags & WHERE_COLUMN_NULL ) == 0
1808 && !referencesOtherTables( pOrderBy, pMaskSet, j, _base ) )
1809 {
1810 /* All terms of this index match some prefix of the ORDER BY clause
1811 ** and the index is UNIQUE and no terms on the tail of the ORDER BY
1812 ** clause reference other tables in a join. If this is all true then
1813 ** the order by clause is superfluous. Not that if the matching
1814 ** condition is IS NULL then the result is not necessarily unique
1815 ** even on a UNIQUE index, so disallow those cases. */
1816 return true;
1817 }
1818 return false;
1819 }
1820  
1821 /*
1822 ** Prepare a crude estimate of the logarithm of the input value.
1823 ** The results need not be exact. This is only used for estimating
1824 ** the total cost of performing operations with O(logN) or O(NlogN)
1825 ** complexity. Because N is just a guess, it is no great tragedy if
1826 ** logN is a little off.
1827 */
1828 static double estLog( double N )
1829 {
1830 double logN = 1;
1831 double x = 10;
1832 while ( N > x )
1833 {
1834 logN += 1;
1835 x *= 10;
1836 }
1837 return logN;
1838 }
1839  
1840 /*
1841 ** Two routines for printing the content of an sqlite3_index_info
1842 ** structure. Used for testing and debugging only. If neither
1843 ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
1844 ** are no-ops.
1845 */
1846 #if !(SQLITE_OMIT_VIRTUALTABLE) && (SQLITE_DEBUG)
1847 static void TRACE_IDX_INPUTS( sqlite3_index_info p )
1848 {
1849 int i;
1850 if ( !sqlite3WhereTrace ) return;
1851 for ( i = 0 ; i < p.nConstraint ; i++ )
1852 {
1853 sqlite3DebugPrintf( " constraint[%d]: col=%d termid=%d op=%d usabled=%d\n",
1854 i,
1855 p.aConstraint[i].iColumn,
1856 p.aConstraint[i].iTermOffset,
1857 p.aConstraint[i].op,
1858 p.aConstraint[i].usable );
1859 }
1860 for ( i = 0 ; i < p.nOrderBy ; i++ )
1861 {
1862 sqlite3DebugPrintf( " orderby[%d]: col=%d desc=%d\n",
1863 i,
1864 p.aOrderBy[i].iColumn,
1865 p.aOrderBy[i].desc );
1866 }
1867 }
1868 static void TRACE_IDX_OUTPUTS( sqlite3_index_info p )
1869 {
1870 int i;
1871 if ( !sqlite3WhereTrace ) return;
1872 for ( i = 0 ; i < p.nConstraint ; i++ )
1873 {
1874 sqlite3DebugPrintf( " usage[%d]: argvIdx=%d omit=%d\n",
1875 i,
1876 p.aConstraintUsage[i].argvIndex,
1877 p.aConstraintUsage[i].omit );
1878 }
1879 sqlite3DebugPrintf( " idxNum=%d\n", p.idxNum );
1880 sqlite3DebugPrintf( " idxStr=%s\n", p.idxStr );
1881 sqlite3DebugPrintf( " orderByConsumed=%d\n", p.orderByConsumed );
1882 sqlite3DebugPrintf( " estimatedCost=%g\n", p.estimatedCost );
1883 }
1884 #else
1885 //#define TRACE_IDX_INPUTS(A)
1886 static void TRACE_IDX_INPUTS( sqlite3_index_info p ) { }
1887 //#define TRACE_IDX_OUTPUTS(A)
1888 static void TRACE_IDX_OUTPUTS( sqlite3_index_info p ) { }
1889 #endif
1890  
1891 /*
1892 ** Required because bestIndex() is called by bestOrClauseIndex()
1893 */
1894 //static void bestIndex(
1895 //Parse*, WhereClause*, struct SrcList_item*,
1896 //Bitmask, ExprList*, WhereCost);
1897  
1898 /*
1899 ** This routine attempts to find an scanning strategy that can be used
1900 ** to optimize an 'OR' expression that is part of a WHERE clause.
1901 **
1902 ** The table associated with FROM clause term pSrc may be either a
1903 ** regular B-Tree table or a virtual table.
1904 */
1905 static void bestOrClauseIndex(
1906 Parse pParse, /* The parsing context */
1907 WhereClause pWC, /* The WHERE clause */
1908 SrcList_item pSrc, /* The FROM clause term to search */
1909 Bitmask notReady, /* Mask of cursors not available for indexing */
1910 Bitmask notValid, /* Cursors not available for any purpose */
1911 ExprList pOrderBy, /* The ORDER BY clause */
1912 WhereCost pCost /* Lowest cost query plan */
1913 )
1914 {
1915 #if !SQLITE_OMIT_OR_OPTIMIZATION
1916 int iCur = pSrc.iCursor; /* The cursor of the table to be accessed */
1917 Bitmask maskSrc = getMask( pWC.pMaskSet, iCur ); /* Bitmask for pSrc */
1918 ////WhereTerm pWCEnd = pWC.a[pWC.nTerm]; /* End of pWC.a[] */
1919 WhereTerm pTerm; /* A single term of the WHERE clause */
1920  
1921 /* No OR-clause optimization allowed if the INDEXED BY or NOT INDEXED clauses
1922 ** are used */
1923 if ( pSrc.notIndexed != 0 || pSrc.pIndex != null )
1924 {
1925 return;
1926 }
1927  
1928 /* Search the WHERE clause terms for a usable WO_OR term. */
1929 for ( int _pt = 0; _pt < pWC.nTerm; _pt++ )//<pWCEnd; pTerm++)
1930 {
1931 pTerm = pWC.a[_pt];
1932 if ( pTerm.eOperator == WO_OR
1933 && ( ( pTerm.prereqAll & ~maskSrc ) & notReady ) == 0
1934 && ( pTerm.u.pOrInfo.indexable & maskSrc ) != 0
1935 )
1936 {
1937 WhereClause pOrWC = pTerm.u.pOrInfo.wc;
1938 ////WhereTerm pOrWCEnd = pOrWC.a[pOrWC.nTerm];
1939 WhereTerm pOrTerm;
1940 int flags = WHERE_MULTI_OR;
1941 double rTotal = 0;
1942 double nRow = 0;
1943 Bitmask used = 0;
1944  
1945 for ( int _pOrWC = 0; _pOrWC < pOrWC.nTerm; _pOrWC++ )//pOrTerm = pOrWC.a ; pOrTerm < pOrWCEnd ; pOrTerm++ )
1946 {
1947 pOrTerm = pOrWC.a[_pOrWC];
1948 WhereCost sTermCost = null;
1949 #if (SQLITE_TEST) && (SQLITE_DEBUG)
1950 WHERETRACE( "... Multi-index OR testing for term %d of %d....\n",
1951 _pOrWC, pOrWC.nTerm - _pOrWC//( pOrTerm - pOrWC.a ), ( pTerm - pWC.a )
1952 );
1953 #endif
1954 if ( pOrTerm.eOperator == WO_AND )
1955 {
1956 WhereClause pAndWC = pOrTerm.u.pAndInfo.wc;
1957 bestIndex( pParse, pAndWC, pSrc, notReady, notValid, null, ref sTermCost );
1958 }
1959 else if ( pOrTerm.leftCursor == iCur )
1960 {
1961 WhereClause tempWC = new WhereClause();
1962 tempWC.pParse = pWC.pParse;
1963 tempWC.pMaskSet = pWC.pMaskSet;
1964 tempWC.op = TK_AND;
1965 tempWC.a = new WhereTerm[2];
1966 tempWC.a[0] = pOrTerm;
1967 tempWC.nTerm = 1;
1968 bestIndex( pParse, tempWC, pSrc, notReady, notValid, null, ref sTermCost );
1969 }
1970 else
1971 {
1972 continue;
1973 }
1974 rTotal += sTermCost.rCost;
1975 nRow += sTermCost.plan.nRow;
1976 used |= sTermCost.used;
1977 if ( rTotal >= pCost.rCost )
1978 break;
1979 }
1980  
1981 /* If there is an ORDER BY clause, increase the scan cost to account
1982 ** for the cost of the sort. */
1983 if ( pOrderBy != null )
1984 {
1985 #if (SQLITE_TEST) && (SQLITE_DEBUG)
1986 WHERETRACE( "... sorting increases OR cost %.9g to %.9g\n",
1987 rTotal, rTotal + nRow * estLog( nRow ) );
1988 #endif
1989 rTotal += nRow * estLog( nRow );
1990 }
1991  
1992 /* If the cost of scanning using this OR term for optimization is
1993 ** less than the current cost stored in pCost, replace the contents
1994 ** of pCost. */
1995 #if (SQLITE_TEST) && (SQLITE_DEBUG)
1996 WHERETRACE( "... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow );
1997 #endif
1998 if ( rTotal < pCost.rCost )
1999 {
2000 pCost.rCost = rTotal;
2001 pCost.used = used;
2002 pCost.plan.nRow = nRow;
2003 pCost.plan.wsFlags = (uint)flags;
2004 pCost.plan.u.pTerm = pTerm;
2005 }
2006 }
2007 }
2008 #endif //* SQLITE_OMIT_OR_OPTIMIZATION */
2009 }
2010  
2011 #if !SQLITE_OMIT_AUTOMATIC_INDEX
2012 /*
2013 ** Return TRUE if the WHERE clause term pTerm is of a form where it
2014 ** could be used with an index to access pSrc, assuming an appropriate
2015 ** index existed.
2016 */
2017 static int termCanDriveIndex(
2018 WhereTerm pTerm, /* WHERE clause term to check */
2019 SrcList_item pSrc, /* Table we are trying to access */
2020 Bitmask notReady /* Tables in outer loops of the join */
2021 )
2022 {
2023 char aff;
2024 if ( pTerm.leftCursor != pSrc.iCursor )
2025 return 0;
2026 if ( pTerm.eOperator != WO_EQ )
2027 return 0;
2028 if ( ( pTerm.prereqRight & notReady ) != 0 )
2029 return 0;
2030 aff = pSrc.pTab.aCol[pTerm.u.leftColumn].affinity;
2031 if ( !sqlite3IndexAffinityOk( pTerm.pExpr, aff ) )
2032 return 0;
2033 return 1;
2034 }
2035 #endif
2036  
2037 #if !SQLITE_OMIT_AUTOMATIC_INDEX
2038 /*
2039 ** If the query plan for pSrc specified in pCost is a full table scan
2040 ** and indexing is allows (if there is no NOT INDEXED clause) and it
2041 ** possible to construct a transient index that would perform better
2042 ** than a full table scan even when the cost of constructing the index
2043 ** is taken into account, then alter the query plan to use the
2044 ** transient index.
2045 */
2046 static void bestAutomaticIndex(
2047 Parse pParse, /* The parsing context */
2048 WhereClause pWC, /* The WHERE clause */
2049 SrcList_item pSrc, /* The FROM clause term to search */
2050 Bitmask notReady, /* Mask of cursors that are not available */
2051 WhereCost pCost /* Lowest cost query plan */
2052 )
2053 {
2054 double nTableRow; /* Rows in the input table */
2055 double logN; /* log(nTableRow) */
2056 double costTempIdx; /* per-query cost of the transient index */
2057 WhereTerm pTerm; /* A single term of the WHERE clause */
2058 WhereTerm pWCEnd; /* End of pWC.a[] */
2059 Table pTable; /* Table that might be indexed */
2060  
2061 if ( pParse.nQueryLoop <= (double)1 )
2062 {
2063 /* There is no point in building an automatic index for a single scan */
2064 return;
2065 }
2066 if ( ( pParse.db.flags & SQLITE_AutoIndex ) == 0 )
2067 {
2068 /* Automatic indices are disabled at run-time */
2069 return;
2070 }
2071 if ( ( pCost.plan.wsFlags & WHERE_NOT_FULLSCAN ) != 0 )
2072 {
2073 /* We already have some kind of index in use for this query. */
2074 return;
2075 }
2076 if ( pSrc.notIndexed != 0 )
2077 {
2078 /* The NOT INDEXED clause appears in the SQL. */
2079 return;
2080 }
2081  
2082 Debug.Assert( pParse.nQueryLoop >= (double)1 );
2083 pTable = pSrc.pTab;
2084 nTableRow = pTable.nRowEst;
2085 logN = estLog( nTableRow );
2086 costTempIdx = 2 * logN * ( nTableRow / pParse.nQueryLoop + 1 );
2087 if ( costTempIdx >= pCost.rCost )
2088 {
2089 /* The cost of creating the transient table would be greater than
2090 ** doing the full table scan */
2091 return;
2092 }
2093  
2094 /* Search for any equality comparison term */
2095 //pWCEnd = pWC.a[pWC.nTerm];
2096 for ( int ipTerm = 0; ipTerm < pWC.nTerm; ipTerm++ )//; pTerm<pWCEnd; pTerm++)
2097 {
2098 pTerm = pWC.a[ipTerm];
2099 if ( termCanDriveIndex( pTerm, pSrc, notReady ) != 0 )
2100 {
2101 #if (SQLITE_TEST) && (SQLITE_DEBUG)
2102 WHERETRACE( "auto-index reduces cost from %.2f to %.2f\n",
2103 pCost.rCost, costTempIdx );
2104 #endif
2105 pCost.rCost = costTempIdx;
2106 pCost.plan.nRow = logN + 1;
2107 pCost.plan.wsFlags = WHERE_TEMP_INDEX;
2108 pCost.used = pTerm.prereqRight;
2109 break;
2110 }
2111 }
2112 }
2113 #else
2114 //# define bestAutomaticIndex(A,B,C,D,E) /* no-op */
2115 static void bestAutomaticIndex(
2116 Parse pParse, /* The parsing context */
2117 WhereClause pWC, /* The WHERE clause */
2118 SrcList_item pSrc, /* The FROM clause term to search */
2119 Bitmask notReady, /* Mask of cursors that are not available */
2120 WhereCost pCost /* Lowest cost query plan */
2121 ){}
2122 #endif //* SQLITE_OMIT_AUTOMATIC_INDEX */
2123  
2124  
2125 #if !SQLITE_OMIT_AUTOMATIC_INDEX
2126 /*
2127 ** Generate code to construct the Index object for an automatic index
2128 ** and to set up the WhereLevel object pLevel so that the code generator
2129 ** makes use of the automatic index.
2130 */
2131 static void constructAutomaticIndex(
2132 Parse pParse, /* The parsing context */
2133 WhereClause pWC, /* The WHERE clause */
2134 SrcList_item pSrc, /* The FROM clause term to get the next index */
2135 Bitmask notReady, /* Mask of cursors that are not available */
2136 WhereLevel pLevel /* Write new index here */
2137 )
2138 {
2139 int nColumn; /* Number of columns in the constructed index */
2140 WhereTerm pTerm; /* A single term of the WHERE clause */
2141 WhereTerm pWCEnd; /* End of pWC.a[] */
2142 int nByte; /* Byte of memory needed for pIdx */
2143 Index pIdx; /* Object describing the transient index */
2144 Vdbe v; /* Prepared statement under construction */
2145 int regIsInit; /* Register set by initialization */
2146 int addrInit; /* Address of the initialization bypass jump */
2147 Table pTable; /* The table being indexed */
2148 KeyInfo pKeyinfo; /* Key information for the index */
2149 int addrTop; /* Top of the index fill loop */
2150 int regRecord; /* Register holding an index record */
2151 int n; /* Column counter */
2152 int i; /* Loop counter */
2153 int mxBitCol; /* Maximum column in pSrc.colUsed */
2154 CollSeq pColl; /* Collating sequence to on a column */
2155 Bitmask idxCols; /* Bitmap of columns used for indexing */
2156 Bitmask extraCols; /* Bitmap of additional columns */
2157  
2158 /* Generate code to skip over the creation and initialization of the
2159 ** transient index on 2nd and subsequent iterations of the loop. */
2160 v = pParse.pVdbe;
2161 Debug.Assert( v != null );
2162 regIsInit = ++pParse.nMem;
2163 addrInit = sqlite3VdbeAddOp1( v, OP_If, regIsInit );
2164 sqlite3VdbeAddOp2( v, OP_Integer, 1, regIsInit );
2165  
2166 /* Count the number of columns that will be added to the index
2167 ** and used to match WHERE clause constraints */
2168 nColumn = 0;
2169 pTable = pSrc.pTab;
2170 //pWCEnd = pWC.a[pWC.nTerm];
2171 idxCols = 0;
2172 for ( int ipTerm = 0; ipTerm < pWC.nTerm; ipTerm++ )//; pTerm<pWCEnd; pTerm++)
2173 {
2174 pTerm = pWC.a[ipTerm];
2175 if ( termCanDriveIndex( pTerm, pSrc, notReady ) != 0 )
2176 {
2177 int iCol = pTerm.u.leftColumn;
2178 Bitmask cMask = iCol >= BMS ? ( (Bitmask)1 ) << ( BMS - 1 ) : ( (Bitmask)1 ) << iCol;
2179 testcase( iCol == BMS );
2180 testcase( iCol == BMS - 1 );
2181 if ( ( idxCols & cMask ) == 0 )
2182 {
2183 nColumn++;
2184 idxCols |= cMask;
2185 }
2186 }
2187 }
2188 Debug.Assert( nColumn > 0 );
2189 pLevel.plan.nEq = (u32)nColumn;
2190  
2191 /* Count the number of additional columns needed to create a
2192 ** covering index. A "covering index" is an index that contains all
2193 ** columns that are needed by the query. With a covering index, the
2194 ** original table never needs to be accessed. Automatic indices must
2195 ** be a covering index because the index will not be updated if the
2196 ** original table changes and the index and table cannot both be used
2197 ** if they go out of sync.
2198 */
2199 extraCols = pSrc.colUsed & ( ~idxCols | ( ( (Bitmask)1 ) << ( BMS - 1 ) ) );
2200 mxBitCol = ( pTable.nCol >= BMS - 1 ) ? BMS - 1 : pTable.nCol;
2201 testcase( pTable.nCol == BMS - 1 );
2202 testcase( pTable.nCol == BMS - 2 );
2203 for ( i = 0; i < mxBitCol; i++ )
2204 {
2205 if ( ( extraCols & ( ( (Bitmask)1 ) << i ) ) != 0 )
2206 nColumn++;
2207 }
2208 if ( ( pSrc.colUsed & ( ( (Bitmask)1 ) << ( BMS - 1 ) ) ) != 0 )
2209 {
2210 nColumn += pTable.nCol - BMS + 1;
2211 }
2212 pLevel.plan.wsFlags |= WHERE_COLUMN_EQ | WHERE_IDX_ONLY | WO_EQ;
2213  
2214 /* Construct the Index object to describe this index */
2215 //nByte = sizeof(Index);
2216 //nByte += nColumn*sizeof(int); /* Index.aiColumn */
2217 //nByte += nColumn*sizeof(char); /* Index.azColl */
2218 //nByte += nColumn; /* Index.aSortOrder */
2219 //pIdx = sqlite3DbMallocZero(pParse.db, nByte);
2220 //if( pIdx==null) return;
2221 pIdx = new Index();
2222 pLevel.plan.u.pIdx = pIdx;
2223 pIdx.azColl = new string[nColumn + 1];// pIdx[1];
2224 pIdx.aiColumn = new int[nColumn + 1];// pIdx.azColl[nColumn];
2225 pIdx.aSortOrder = new u8[nColumn + 1];// pIdx.aiColumn[nColumn];
2226 pIdx.zName = "auto-index";
2227 pIdx.nColumn = nColumn;
2228 pIdx.pTable = pTable;
2229 n = 0;
2230 idxCols = 0;
2231 //for(pTerm=pWC.a; pTerm<pWCEnd; pTerm++){
2232 for ( int ipTerm = 0; ipTerm < pWC.nTerm; ipTerm++ )
2233 {
2234 pTerm = pWC.a[ipTerm];
2235 if ( termCanDriveIndex( pTerm, pSrc, notReady ) != 0 )
2236 {
2237 int iCol = pTerm.u.leftColumn;
2238 Bitmask cMask = iCol >= BMS ? ( (Bitmask)1 ) << ( BMS - 1 ) : ( (Bitmask)1 ) << iCol;
2239 if ( ( idxCols & cMask ) == 0 )
2240 {
2241 Expr pX = pTerm.pExpr;
2242 idxCols |= cMask;
2243 pIdx.aiColumn[n] = pTerm.u.leftColumn;
2244 pColl = sqlite3BinaryCompareCollSeq( pParse, pX.pLeft, pX.pRight );
2245 pIdx.azColl[n] = ALWAYS( pColl != null ) ? pColl.zName : "BINARY";
2246 n++;
2247 }
2248 }
2249 }
2250 Debug.Assert( (u32)n == pLevel.plan.nEq );
2251  
2252 /* Add additional columns needed to make the automatic index into
2253 ** a covering index */
2254 for ( i = 0; i < mxBitCol; i++ )
2255 {
2256 if ( ( extraCols & ( ( (Bitmask)1 ) << i ) ) != 0 )
2257 {
2258 pIdx.aiColumn[n] = i;
2259 pIdx.azColl[n] = "BINARY";
2260 n++;
2261 }
2262 }
2263 if ( ( pSrc.colUsed & ( ( (Bitmask)1 ) << ( BMS - 1 ) ) ) != 0 )
2264 {
2265 for ( i = BMS - 1; i < pTable.nCol; i++ )
2266 {
2267 pIdx.aiColumn[n] = i;
2268 pIdx.azColl[n] = "BINARY";
2269 n++;
2270 }
2271 }
2272 Debug.Assert( n == nColumn );
2273  
2274 /* Create the automatic index */
2275 pKeyinfo = sqlite3IndexKeyinfo( pParse, pIdx );
2276 Debug.Assert( pLevel.iIdxCur >= 0 );
2277 sqlite3VdbeAddOp4( v, OP_OpenAutoindex, pLevel.iIdxCur, nColumn + 1, 0,
2278 pKeyinfo, P4_KEYINFO_HANDOFF );
2279 VdbeComment( v, "for %s", pTable.zName );
2280  
2281 /* Fill the automatic index with content */
2282 addrTop = sqlite3VdbeAddOp1( v, OP_Rewind, pLevel.iTabCur );
2283 regRecord = sqlite3GetTempReg( pParse );
2284 sqlite3GenerateIndexKey( pParse, pIdx, pLevel.iTabCur, regRecord, true );
2285 sqlite3VdbeAddOp2( v, OP_IdxInsert, pLevel.iIdxCur, regRecord );
2286 sqlite3VdbeChangeP5( v, OPFLAG_USESEEKRESULT );
2287 sqlite3VdbeAddOp2( v, OP_Next, pLevel.iTabCur, addrTop + 1 );
2288 sqlite3VdbeChangeP5( v, SQLITE_STMTSTATUS_AUTOINDEX );
2289 sqlite3VdbeJumpHere( v, addrTop );
2290 sqlite3ReleaseTempReg( pParse, regRecord );
2291  
2292 /* Jump here when skipping the initialization */
2293 sqlite3VdbeJumpHere( v, addrInit );
2294 }
2295 #endif //* SQLITE_OMIT_AUTOMATIC_INDEX */
2296  
2297 #if !SQLITE_OMIT_VIRTUALTABLE
2298 /*
2299 ** Allocate and populate an sqlite3_index_info structure. It is the
2300 ** responsibility of the caller to eventually release the structure
2301 ** by passing the pointer returned by this function to //sqlite3_free().
2302 */
2303 static sqlite3_index_info allocateIndexInfo(
2304 Parse pParse,
2305 WhereClause pWC,
2306 SrcList_item pSrc,
2307 ExprList pOrderBy
2308 )
2309 {
2310 int i, j;
2311 int nTerm;
2312 sqlite3_index_constraint[] pIdxCons;
2313 sqlite3_index_orderby[] pIdxOrderBy;
2314 sqlite3_index_constraint_usage[] pUsage;
2315 WhereTerm pTerm;
2316 int nOrderBy;
2317 sqlite3_index_info pIdxInfo;
2318  
2319 #if (SQLITE_TEST) && (SQLITE_DEBUG)
2320 WHERETRACE( "Recomputing index info for %s...\n", pSrc.pTab.zName );
2321 #endif
2322  
2323 /* Count the number of possible WHERE clause constraints referring
2324 ** to this virtual table */
2325 for ( i = nTerm = 0; i < pWC.nTerm; i++)//, pTerm++ )
2326 {
2327 pTerm = pWC.a[i];
2328 if ( pTerm.leftCursor != pSrc.iCursor )
2329 continue;
2330 Debug.Assert( ( pTerm.eOperator & ( pTerm.eOperator - 1 ) ) == 0 );
2331 testcase( pTerm.eOperator == WO_IN );
2332 testcase( pTerm.eOperator == WO_ISNULL );
2333 if ( ( pTerm.eOperator & ( WO_IN | WO_ISNULL ) ) != 0 )
2334 continue;
2335 nTerm++;
2336 }
2337  
2338 /* If the ORDER BY clause contains only columns in the current
2339 ** virtual table then allocate space for the aOrderBy part of
2340 ** the sqlite3_index_info structure.
2341 */
2342 nOrderBy = 0;
2343 if ( pOrderBy != null )
2344 {
2345 for ( i = 0; i < pOrderBy.nExpr; i++ )
2346 {
2347 Expr pExpr = pOrderBy.a[i].pExpr;
2348 if ( pExpr.op != TK_COLUMN || pExpr.iTable != pSrc.iCursor )
2349 break;
2350 }
2351 if ( i == pOrderBy.nExpr )
2352 {
2353 nOrderBy = pOrderBy.nExpr;
2354 }
2355 }
2356  
2357 /* Allocate the sqlite3_index_info structure
2358 */
2359 pIdxInfo = new sqlite3_index_info();
2360 //sqlite3DbMallocZero(pParse.db, sizeof(*pIdxInfo)
2361 //+ (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm
2362 //+ sizeof(*pIdxOrderBy)*nOrderBy );
2363 //if ( pIdxInfo == null )
2364 //{
2365 // sqlite3ErrorMsg( pParse, "out of memory" );
2366 // /* (double)0 In case of SQLITE_OMIT_FLOATING_POINT... */
2367 // return null;
2368 //}
2369  
2370 /* Initialize the structure. The sqlite3_index_info structure contains
2371 ** many fields that are declared "const" to prevent xBestIndex from
2372 ** changing them. We have to do some funky casting in order to
2373 ** initialize those fields.
2374 */
2375 pIdxCons = new sqlite3_index_constraint[nTerm];//(sqlite3_index_constraint)pIdxInfo[1];
2376 pIdxOrderBy = new sqlite3_index_orderby[nOrderBy];//(sqlite3_index_orderby)pIdxCons[nTerm];
2377 pUsage = new sqlite3_index_constraint_usage[nTerm];//(sqlite3_index_constraint_usage)pIdxOrderBy[nOrderBy];
2378 pIdxInfo.nConstraint = nTerm;
2379 pIdxInfo.nOrderBy = nOrderBy;
2380 pIdxInfo.aConstraint = pIdxCons;
2381 pIdxInfo.aOrderBy = pIdxOrderBy;
2382 pIdxInfo.aConstraintUsage =
2383 pUsage;
2384  
2385 for ( i = j = 0; i < pWC.nTerm; i++)//, pTerm++ )
2386 {
2387 pTerm = pWC.a[i];
2388 if ( pTerm.leftCursor != pSrc.iCursor )
2389 continue;
2390 Debug.Assert( ( pTerm.eOperator & ( pTerm.eOperator - 1 ) ) == 0 );
2391 testcase( pTerm.eOperator == WO_IN );
2392 testcase( pTerm.eOperator == WO_ISNULL );
2393 if ( ( pTerm.eOperator & ( WO_IN | WO_ISNULL ) ) != 0 )
2394 continue;
2395 if ( pIdxCons[j] == null )
2396 pIdxCons[j] = new sqlite3_index_constraint();
2397 pIdxCons[j].iColumn = pTerm.u.leftColumn;
2398 pIdxCons[j].iTermOffset = i;
2399 pIdxCons[j].op = (u8)pTerm.eOperator;
2400 /* The direct Debug.Assignment in the previous line is possible only because
2401 ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The
2402 ** following Debug.Asserts verify this fact. */
2403 Debug.Assert( WO_EQ == SQLITE_INDEX_CONSTRAINT_EQ );
2404 Debug.Assert( WO_LT == SQLITE_INDEX_CONSTRAINT_LT );
2405 Debug.Assert( WO_LE == SQLITE_INDEX_CONSTRAINT_LE );
2406 Debug.Assert( WO_GT == SQLITE_INDEX_CONSTRAINT_GT );
2407 Debug.Assert( WO_GE == SQLITE_INDEX_CONSTRAINT_GE );
2408 Debug.Assert( WO_MATCH == SQLITE_INDEX_CONSTRAINT_MATCH );
2409 Debug.Assert( ( pTerm.eOperator & ( WO_EQ | WO_LT | WO_LE | WO_GT | WO_GE | WO_MATCH ) ) != 0 );
2410 j++;
2411 }
2412 for ( i = 0; i < nOrderBy; i++ )
2413 {
2414 Expr pExpr = pOrderBy.a[i].pExpr;
2415 if ( pIdxOrderBy[i] == null )
2416 pIdxOrderBy[i] = new sqlite3_index_orderby();
2417 pIdxOrderBy[i].iColumn = pExpr.iColumn;
2418 pIdxOrderBy[i].desc = pOrderBy.a[i].sortOrder != 0;
2419 }
2420  
2421 return pIdxInfo;
2422 }
2423  
2424 /*
2425 ** The table object reference passed as the second argument to this function
2426 ** must represent a virtual table. This function invokes the xBestIndex()
2427 ** method of the virtual table with the sqlite3_index_info pointer passed
2428 ** as the argument.
2429 **
2430 ** If an error occurs, pParse is populated with an error message and a
2431 ** non-zero value is returned. Otherwise, 0 is returned and the output
2432 ** part of the sqlite3_index_info structure is left populated.
2433 **
2434 ** Whether or not an error is returned, it is the responsibility of the
2435 ** caller to eventually free p.idxStr if p.needToFreeIdxStr indicates
2436 ** that this is required.
2437 */
2438 static int vtabBestIndex( Parse pParse, Table pTab, sqlite3_index_info p )
2439 {
2440 sqlite3_vtab pVtab = sqlite3GetVTable( pParse.db, pTab ).pVtab;
2441 int i;
2442 int rc;
2443  
2444 #if (SQLITE_TEST) && (SQLITE_DEBUG)
2445 WHERETRACE( "xBestIndex for %s\n", pTab.zName );
2446 #endif
2447 TRACE_IDX_INPUTS( p );
2448 rc = pVtab.pModule.xBestIndex( pVtab, ref p );
2449 TRACE_IDX_OUTPUTS( p );
2450  
2451 if ( rc != SQLITE_OK )
2452 {
2453 //if ( rc == SQLITE_NOMEM )
2454 //{
2455 // pParse.db.mallocFailed = 1;
2456 //}
2457 // else
2458 if ( string.IsNullOrEmpty( pVtab.zErrMsg ) )
2459 {
2460 sqlite3ErrorMsg( pParse, "%s", sqlite3ErrStr( rc ) );
2461 }
2462 else
2463 {
2464 sqlite3ErrorMsg( pParse, "%s", pVtab.zErrMsg );
2465 }
2466 }
2467 //sqlite3_free( pVtab.zErrMsg );
2468 pVtab.zErrMsg = null;
2469  
2470 for ( i = 0; i < p.nConstraint; i++ )
2471 {
2472 if ( !p.aConstraint[i].usable && p.aConstraintUsage[i].argvIndex > 0 )
2473 {
2474 sqlite3ErrorMsg( pParse,
2475 "table %s: xBestIndex returned an invalid plan", pTab.zName );
2476 }
2477 }
2478  
2479 return pParse.nErr;
2480 }
2481  
2482  
2483 /*
2484 ** Compute the best index for a virtual table.
2485 **
2486 ** The best index is computed by the xBestIndex method of the virtual
2487 ** table module. This routine is really just a wrapper that sets up
2488 ** the sqlite3_index_info structure that is used to communicate with
2489 ** xBestIndex.
2490 **
2491 ** In a join, this routine might be called multiple times for the
2492 ** same virtual table. The sqlite3_index_info structure is created
2493 ** and initialized on the first invocation and reused on all subsequent
2494 ** invocations. The sqlite3_index_info structure is also used when
2495 ** code is generated to access the virtual table. The whereInfoDelete()
2496 ** routine takes care of freeing the sqlite3_index_info structure after
2497 ** everybody has finished with it.
2498 */
2499 static void bestVirtualIndex(
2500 Parse pParse, /* The parsing context */
2501 WhereClause pWC, /* The WHERE clause */
2502 SrcList_item pSrc, /* The FROM clause term to search */
2503 Bitmask notReady, /* Mask of cursors not available for index */
2504 Bitmask notValid, /* Cursors not valid for any purpose */
2505 ExprList pOrderBy, /* The order by clause */
2506 ref WhereCost pCost, /* Lowest cost query plan */
2507 ref sqlite3_index_info ppIdxInfo /* Index information passed to xBestIndex */
2508 )
2509 {
2510 Table pTab = pSrc.pTab;
2511 sqlite3_index_info pIdxInfo;
2512 sqlite3_index_constraint pIdxCons;
2513 sqlite3_index_constraint_usage[] pUsage = null;
2514 WhereTerm pTerm;
2515 int i, j;
2516 int nOrderBy;
2517 double rCost;
2518  
2519  
2520 /* Make sure wsFlags is initialized to some sane value. Otherwise, if the
2521 ** malloc in allocateIndexInfo() fails and this function returns leaving
2522 ** wsFlags in an uninitialized state, the caller may behave unpredictably.
2523 */
2524 pCost = new WhereCost();//memset(pCost, 0, sizeof(*pCost));
2525 pCost.plan.wsFlags = WHERE_VIRTUALTABLE;
2526  
2527 /* If the sqlite3_index_info structure has not been previously
2528 ** allocated and initialized, then allocate and initialize it now.
2529 */
2530 pIdxInfo = ppIdxInfo;
2531 if ( pIdxInfo == null )
2532 {
2533 ppIdxInfo = pIdxInfo = allocateIndexInfo( pParse, pWC, pSrc, pOrderBy );
2534 }
2535 if ( pIdxInfo == null )
2536 {
2537 return;
2538 }
2539  
2540 /* At this point, the sqlite3_index_info structure that pIdxInfo points
2541 ** to will have been initialized, either during the current invocation or
2542 ** during some prior invocation. Now we just have to customize the
2543 ** details of pIdxInfo for the current invocation and pDebug.Ass it to
2544 ** xBestIndex.
2545 */
2546  
2547 /* The module name must be defined. Also, by this point there must
2548 ** be a pointer to an sqlite3_vtab structure. Otherwise
2549 ** sqlite3ViewGetColumnNames() would have picked up the error.
2550 */
2551 Debug.Assert( pTab.azModuleArg != null && pTab.azModuleArg[0] != null );
2552 Debug.Assert( sqlite3GetVTable( pParse.db, pTab ) != null );
2553  
2554 /* Set the aConstraint[].usable fields and initialize all
2555 ** output variables to zero.
2556 **
2557 ** aConstraint[].usable is true for constraints where the right-hand
2558 ** side contains only references to tables to the left of the current
2559 ** table. In other words, if the constraint is of the form:
2560 **
2561 ** column = expr
2562 **
2563 ** and we are evaluating a join, then the constraint on column is
2564 ** only valid if all tables referenced in expr occur to the left
2565 ** of the table containing column.
2566 **
2567 ** The aConstraints[] array contains entries for all constraints
2568 ** on the current table. That way we only have to compute it once
2569 ** even though we might try to pick the best index multiple times.
2570 ** For each attempt at picking an index, the order of tables in the
2571 ** join might be different so we have to recompute the usable flag
2572 ** each time.
2573 */
2574 //pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
2575 //pUsage = pIdxInfo->aConstraintUsage;
2576 for ( i = 0; i < pIdxInfo.nConstraint; i++)
2577 {
2578 pIdxCons = pIdxInfo.aConstraint[i];
2579 pUsage = pIdxInfo.aConstraintUsage;
2580 j = pIdxCons.iTermOffset;
2581 pTerm = pWC.a[j];
2582 pIdxCons.usable = ( pTerm.prereqRight & notReady ) == 0;
2583 pUsage[i] = new sqlite3_index_constraint_usage();
2584 }
2585 // memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo.nConstraint);
2586 if ( pIdxInfo.needToFreeIdxStr!=0 )
2587 {
2588 //sqlite3_free(ref pIdxInfo.idxStr);
2589 }
2590 pIdxInfo.idxStr = null;
2591 pIdxInfo.idxNum = 0;
2592 pIdxInfo.needToFreeIdxStr = 0;
2593 pIdxInfo.orderByConsumed = false;
2594 /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */
2595 pIdxInfo.estimatedCost = SQLITE_BIG_DBL / ( (double)2 );
2596 nOrderBy = pIdxInfo.nOrderBy;
2597 if ( null == pOrderBy )
2598 {
2599 pIdxInfo.nOrderBy = 0;
2600 }
2601  
2602 if ( vtabBestIndex( pParse, pTab, pIdxInfo ) != 0 )
2603 {
2604 return;
2605 }
2606  
2607 //pIdxCons = (sqlite3_index_constraint)pIdxInfo.aConstraint;
2608 for ( i = 0; i < pIdxInfo.nConstraint; i++ )
2609 {
2610 if ( pUsage[i].argvIndex > 0 )
2611 {
2612 //pCost.used |= pWC.a[pIdxCons[i].iTermOffset].prereqRight;
2613 pCost.used |= pWC.a[pIdxInfo.aConstraint[i].iTermOffset].prereqRight;
2614 }
2615 }
2616  
2617 /* If there is an ORDER BY clause, and the selected virtual table index
2618 ** does not satisfy it, increase the cost of the scan accordingly. This
2619 ** matches the processing for non-virtual tables in bestBtreeIndex().
2620 */
2621 rCost = pIdxInfo.estimatedCost;
2622 if ( pOrderBy != null && !pIdxInfo.orderByConsumed )
2623 {
2624 rCost += estLog( rCost ) * rCost;
2625 }
2626  
2627 /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the
2628 ** inital value of lowestCost in this loop. If it is, then the
2629 ** (cost<lowestCost) test below will never be true.
2630 **
2631 ** Use "(double)2" instead of "2.0" in case OMIT_FLOATING_POINT
2632 ** is defined.
2633 */
2634 if ( ( SQLITE_BIG_DBL / ( (double)2 ) ) < rCost )
2635 {
2636 pCost.rCost = ( SQLITE_BIG_DBL / ( (double)2 ) );
2637 }
2638 else
2639 {
2640 pCost.rCost = rCost;
2641 }
2642 pCost.plan.u.pVtabIdx = pIdxInfo;
2643 if ( pIdxInfo.orderByConsumed )
2644 {
2645 pCost.plan.wsFlags |= WHERE_ORDERBY;
2646 }
2647 pCost.plan.nEq = 0;
2648 pIdxInfo.nOrderBy = nOrderBy;
2649  
2650 /* Try to find a more efficient access pattern by using multiple indexes
2651 ** to optimize an OR expression within the WHERE clause.
2652 */
2653 bestOrClauseIndex( pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost );
2654 }
2655 #endif //* SQLITE_OMIT_VIRTUALTABLE */
2656  
2657 /*
2658 ** Argument pIdx is a pointer to an index structure that has an array of
2659 ** SQLITE_INDEX_SAMPLES evenly spaced samples of the first indexed column
2660 ** stored in Index.aSample. These samples divide the domain of values stored
2661 ** the index into (SQLITE_INDEX_SAMPLES+1) regions.
2662 ** Region 0 contains all values less than the first sample value. Region
2663 ** 1 contains values between the first and second samples. Region 2 contains
2664 ** values between samples 2 and 3. And so on. Region SQLITE_INDEX_SAMPLES
2665 ** contains values larger than the last sample.
2666 **
2667 ** If the index contains many duplicates of a single value, then it is
2668 ** possible that two or more adjacent samples can hold the same value.
2669 ** When that is the case, the smallest possible region code is returned
2670 ** when roundUp is false and the largest possible region code is returned
2671 ** when roundUp is true.
2672 **
2673 ** If successful, this function determines which of the regions value
2674 ** pVal lies in, sets *piRegion to the region index (a value between 0
2675 ** and SQLITE_INDEX_SAMPLES+1, inclusive) and returns SQLITE_OK.
2676 ** Or, if an OOM occurs while converting text values between encodings,
2677 ** SQLITE_NOMEM is returned and *piRegion is undefined.
2678 */
2679 #if SQLITE_ENABLE_STAT2
2680 static int whereRangeRegion(
2681 Parse pParse, /* Database connection */
2682 Index pIdx, /* Index to consider domain of */
2683 sqlite3_value pVal, /* Value to consider */
2684 int roundUp, /* Return largest valid region if true */
2685 out int piRegion /* OUT: Region of domain in which value lies */
2686 )
2687 {
2688 piRegion = 0;
2689 Debug.Assert( roundUp == 0 || roundUp == 1 );
2690 if ( ALWAYS( pVal ) )
2691 {
2692 IndexSample[] aSample = pIdx.aSample;
2693 int i = 0;
2694 int eType = sqlite3_value_type( pVal );
2695  
2696 if ( eType == SQLITE_INTEGER || eType == SQLITE_FLOAT )
2697 {
2698 double r = sqlite3_value_double( pVal );
2699 for ( i = 0; i < SQLITE_INDEX_SAMPLES; i++ )
2700 {
2701 if ( aSample[i].eType == SQLITE_NULL )
2702 continue;
2703 if ( aSample[i].eType >= SQLITE_TEXT )
2704 break;
2705 if ( roundUp != 0 )
2706 {
2707 if ( aSample[i].u.r > r )
2708 break;
2709 }
2710 else
2711 {
2712 if ( aSample[i].u.r >= r )
2713 break;
2714 }
2715 }
2716 }
2717 else if ( eType == SQLITE_NULL )
2718 {
2719 i = 0;
2720 if ( roundUp != 0 )
2721 {
2722 while ( i < SQLITE_INDEX_SAMPLES && aSample[i].eType == SQLITE_NULL )
2723 i++;
2724 }
2725 }
2726 else
2727 {
2728 sqlite3 db = pParse.db;
2729 CollSeq pColl;
2730 string z;
2731 int n;
2732  
2733 /* pVal comes from sqlite3ValueFromExpr() so the type cannot be NULL */
2734 Debug.Assert( eType == SQLITE_TEXT || eType == SQLITE_BLOB );
2735  
2736 if ( eType == SQLITE_BLOB )
2737 {
2738 byte[] blob = sqlite3_value_blob( pVal );
2739 z = Encoding.UTF8.GetString( blob, 0, blob.Length );
2740 pColl = db.pDfltColl;
2741 Debug.Assert( pColl.enc == SQLITE_UTF8 );
2742 }
2743 else
2744 {
2745 pColl = sqlite3GetCollSeq( db, SQLITE_UTF8, null, pIdx.azColl[0] );
2746 if ( pColl == null )
2747 {
2748 sqlite3ErrorMsg( pParse, "no such collation sequence: %s",
2749 pIdx.azColl );
2750 return SQLITE_ERROR;
2751 }
2752 z = sqlite3ValueText( pVal, pColl.enc );
2753 //if( null==z ){
2754 // return SQLITE_NOMEM;
2755 //}
2756 Debug.Assert( z != string.Empty && pColl != null && pColl.xCmp != null );
2757 }
2758 n = sqlite3ValueBytes( pVal, pColl.enc );
2759  
2760 for ( i = 0; i < SQLITE_INDEX_SAMPLES; i++ )
2761 {
2762 int c;
2763 int eSampletype = aSample[i].eType;
2764 if ( eSampletype == SQLITE_NULL || eSampletype < eType )
2765 continue;
2766 if ( ( eSampletype != eType ) )
2767 break;
2768 #if !SQLITE_OMIT_UTF16
2769 if( pColl.enc!=SQLITE_UTF8 ){
2770 int nSample;
2771 string zSample;
2772 zSample = sqlite3Utf8to16(
2773 db, pColl.enc, aSample[i].u.z, aSample[i].nByte, ref nSample
2774 );
2775 zSample = aSample[i].u.z;
2776 nSample = aSample[i].u.z.Length;
2777 //if( null==zSample ){
2778 // Debug.Assert( db.mallocFailed );
2779 // return SQLITE_NOMEM;
2780 //}
2781 c = pColl.xCmp(pColl.pUser, nSample, zSample, n, z);
2782 sqlite3DbFree(db, ref zSample);
2783 }else
2784 #endif
2785 {
2786 c = pColl.xCmp( pColl.pUser, aSample[i].nByte, aSample[i].u.z, n, z );
2787 }
2788 if ( c - roundUp >= 0 )
2789 break;
2790 }
2791 }
2792  
2793 Debug.Assert( i >= 0 && i <= SQLITE_INDEX_SAMPLES );
2794 piRegion = i;
2795 }
2796 return SQLITE_OK;
2797 }
2798 #endif //* #if SQLITE_ENABLE_STAT2 */
2799  
2800 /*
2801 ** If expression pExpr represents a literal value, set *pp to point to
2802 ** an sqlite3_value structure containing the same value, with affinity
2803 ** aff applied to it, before returning. It is the responsibility of the
2804 ** caller to eventually release this structure by passing it to
2805 ** sqlite3ValueFree().
2806 **
2807 ** If the current parse is a recompile (sqlite3Reprepare()) and pExpr
2808 ** is an SQL variable that currently has a non-NULL value bound to it,
2809 ** create an sqlite3_value structure containing this value, again with
2810 ** affinity aff applied to it, instead.
2811 **
2812 ** If neither of the above apply, set *pp to NULL.
2813 **
2814 ** If an error occurs, return an error code. Otherwise, SQLITE_OK.
2815 */
2816 #if SQLITE_ENABLE_STAT2
2817 static int valueFromExpr(
2818 Parse pParse,
2819 Expr pExpr,
2820 char aff,
2821 ref sqlite3_value pp
2822 )
2823 {
2824 if ( pExpr.op == TK_VARIABLE
2825 || ( pExpr.op == TK_REGISTER && pExpr.op2 == TK_VARIABLE )
2826 )
2827 {
2828 int iVar = pExpr.iColumn;
2829 sqlite3VdbeSetVarmask( pParse.pVdbe, iVar ); /* IMP: R-23257-02778 */
2830 pp = sqlite3VdbeGetValue( pParse.pReprepare, iVar, (u8)aff );
2831 return SQLITE_OK;
2832 }
2833 return sqlite3ValueFromExpr( pParse.db, pExpr, SQLITE_UTF8, aff, ref pp );
2834 }
2835 #endif
2836  
2837 /*
2838 ** This function is used to estimate the number of rows that will be visited
2839 ** by scanning an index for a range of values. The range may have an upper
2840 ** bound, a lower bound, or both. The WHERE clause terms that set the upper
2841 ** and lower bounds are represented by pLower and pUpper respectively. For
2842 ** example, assuming that index p is on t1(a):
2843 **
2844 ** ... FROM t1 WHERE a > ? AND a < ? ...
2845 ** |_____| |_____|
2846 ** | |
2847 ** pLower pUpper
2848 **
2849 ** If either of the upper or lower bound is not present, then NULL is passed in
2850 ** place of the corresponding WhereTerm.
2851 **
2852 ** The nEq parameter is passed the index of the index column subject to the
2853 ** range constraint. Or, equivalently, the number of equality constraints
2854 ** optimized by the proposed index scan. For example, assuming index p is
2855 ** on t1(a, b), and the SQL query is:
2856 **
2857 ** ... FROM t1 WHERE a = ? AND b > ? AND b < ? ...
2858 **
2859 ** then nEq should be passed the value 1 (as the range restricted column,
2860 ** b, is the second left-most column of the index). Or, if the query is:
2861 **
2862 ** ... FROM t1 WHERE a > ? AND a < ? ...
2863 **
2864 ** then nEq should be passed 0.
2865 **
2866 ** The returned value is an integer between 1 and 100, inclusive. A return
2867 ** value of 1 indicates that the proposed range scan is expected to visit
2868 ** approximately 1/100th (1%) of the rows selected by the nEq equality
2869 ** constraints (if any). A return value of 100 indicates that it is expected
2870 ** that the range scan will visit every row (100%) selected by the equality
2871 ** constraints.
2872 **
2873 ** In the absence of sqlite_stat2 ANALYZE data, each range inequality
2874 ** reduces the search space by 3/4ths. Hence a single constraint (x>?)
2875 ** results in a return of 25 and a range constraint (x>? AND x<?) results
2876 ** in a return of 6.
2877 */
2878 static int whereRangeScanEst(
2879 Parse pParse, /* Parsing & code generating context */
2880 Index p, /* The index containing the range-compared column; "x" */
2881 int nEq, /* index into p.aCol[] of the range-compared column */
2882 WhereTerm pLower, /* Lower bound on the range. ex: "x>123" Might be NULL */
2883 WhereTerm pUpper, /* Upper bound on the range. ex: "x<455" Might be NULL */
2884 out int piEst /* OUT: Return value */
2885 )
2886 {
2887 int rc = SQLITE_OK;
2888  
2889 #if SQLITE_ENABLE_STAT2
2890  
2891 if ( nEq == 0 && p.aSample != null )
2892 {
2893 sqlite3_value pLowerVal = null;
2894 sqlite3_value pUpperVal = null;
2895 int iEst;
2896 int iLower = 0;
2897 int iUpper = SQLITE_INDEX_SAMPLES;
2898 int roundUpUpper = 0;
2899 int roundUpLower = 0;
2900 char aff = p.pTable.aCol[p.aiColumn[0]].affinity;
2901  
2902 if ( pLower != null )
2903 {
2904 Expr pExpr = pLower.pExpr.pRight;
2905 rc = valueFromExpr( pParse, pExpr, aff, ref pLowerVal );
2906 Debug.Assert( pLower.eOperator == WO_GT || pLower.eOperator == WO_GE );
2907 roundUpLower = ( pLower.eOperator == WO_GT ) ? 1 : 0;
2908 }
2909 if ( rc == SQLITE_OK && pUpper != null )
2910 {
2911 Expr pExpr = pUpper.pExpr.pRight;
2912 rc = valueFromExpr( pParse, pExpr, aff, ref pUpperVal );
2913 Debug.Assert( pUpper.eOperator == WO_LT || pUpper.eOperator == WO_LE );
2914 roundUpUpper = ( pUpper.eOperator == WO_LE ) ? 1 : 0;
2915 }
2916  
2917 if ( rc != SQLITE_OK || ( pLowerVal == null && pUpperVal == null ) )
2918 {
2919 sqlite3ValueFree( ref pLowerVal );
2920 sqlite3ValueFree( ref pUpperVal );
2921 goto range_est_fallback;
2922 }
2923 else if ( pLowerVal == null )
2924 {
2925 rc = whereRangeRegion( pParse, p, pUpperVal, roundUpUpper, out iUpper );
2926 if ( pLower != null )
2927 iLower = iUpper / 2;
2928 }
2929 else if ( pUpperVal == null )
2930 {
2931 rc = whereRangeRegion( pParse, p, pLowerVal, roundUpLower, out iLower );
2932 if ( pUpper != null )
2933 iUpper = ( iLower + SQLITE_INDEX_SAMPLES + 1 ) / 2;
2934 }
2935 else
2936 {
2937 rc = whereRangeRegion( pParse, p, pUpperVal, roundUpUpper, out iUpper );
2938 if ( rc == SQLITE_OK )
2939 {
2940 rc = whereRangeRegion( pParse, p, pLowerVal, roundUpLower, out iLower );
2941 }
2942 }
2943 WHERETRACE( "range scan regions: %d..%d\n", iLower, iUpper );
2944  
2945 iEst = iUpper - iLower;
2946 testcase( iEst == SQLITE_INDEX_SAMPLES );
2947 Debug.Assert( iEst <= SQLITE_INDEX_SAMPLES );
2948 if ( iEst < 1 )
2949 {
2950 piEst = 50 / SQLITE_INDEX_SAMPLES;
2951 }
2952 else
2953 {
2954 piEst = ( iEst * 100 ) / SQLITE_INDEX_SAMPLES;
2955 }
2956  
2957 sqlite3ValueFree( ref pLowerVal );
2958 sqlite3ValueFree( ref pUpperVal );
2959 return rc;
2960 }
2961 range_est_fallback:
2962 #else
2963 UNUSED_PARAMETER(pParse);
2964 UNUSED_PARAMETER(p);
2965 UNUSED_PARAMETER(nEq);
2966 #endif
2967 Debug.Assert( pLower != null || pUpper != null );
2968 piEst = 100;
2969 if ( pLower != null && ( pLower.wtFlags & TERM_VNULL ) == 0 )
2970 piEst /= 4;
2971 if ( pUpper != null )
2972 piEst /= 4;
2973 return rc;
2974 }
2975  
2976 #if SQLITE_ENABLE_STAT2
2977 /*
2978 ** Estimate the number of rows that will be returned based on
2979 ** an equality constraint x=VALUE and where that VALUE occurs in
2980 ** the histogram data. This only works when x is the left-most
2981 ** column of an index and sqlite_stat2 histogram data is available
2982 ** for that index. When pExpr==NULL that means the constraint is
2983 ** "x IS NULL" instead of "x=VALUE".
2984 **
2985 ** Write the estimated row count into *pnRow and return SQLITE_OK.
2986 ** If unable to make an estimate, leave *pnRow unchanged and return
2987 ** non-zero.
2988 **
2989 ** This routine can fail if it is unable to load a collating sequence
2990 ** required for string comparison, or if unable to allocate memory
2991 ** for a UTF conversion required for comparison. The error is stored
2992 ** in the pParse structure.
2993 */
2994 static int whereEqualScanEst(
2995 Parse pParse, /* Parsing & code generating context */
2996 Index p, /* The index whose left-most column is pTerm */
2997 Expr pExpr, /* Expression for VALUE in the x=VALUE constraint */
2998 ref double pnRow /* Write the revised row estimate here */
2999 )
3000 {
3001 sqlite3_value pRhs = null;/* VALUE on right-hand side of pTerm */
3002 int iLower = 0;
3003 int iUpper = 0; /* Range of histogram regions containing pRhs */
3004 char aff; /* Column affinity */
3005 int rc; /* Subfunction return code */
3006 double nRowEst; /* New estimate of the number of rows */
3007  
3008 Debug.Assert( p.aSample != null );
3009 aff = p.pTable.aCol[p.aiColumn[0]].affinity;
3010 if ( pExpr != null )
3011 {
3012 rc = valueFromExpr( pParse, pExpr, aff, ref pRhs );
3013 if ( rc != 0 )
3014 goto whereEqualScanEst_cancel;
3015 }
3016 else
3017 {
3018 pRhs = sqlite3ValueNew( pParse.db );
3019 }
3020 if ( pRhs == null )
3021 return SQLITE_NOTFOUND;
3022 rc = whereRangeRegion( pParse, p, pRhs, 0, out iLower );
3023 if ( rc != 0 )
3024 goto whereEqualScanEst_cancel;
3025 rc = whereRangeRegion( pParse, p, pRhs, 1, out iUpper );
3026 if ( rc != 0 )
3027 goto whereEqualScanEst_cancel;
3028 WHERETRACE( "equality scan regions: %d..%d\n", iLower, iUpper );
3029 if ( iLower >= iUpper )
3030 {
3031 nRowEst = p.aiRowEst[0] / ( SQLITE_INDEX_SAMPLES * 2 );
3032 if ( nRowEst < pnRow )
3033 pnRow = nRowEst;
3034 }
3035 else
3036 {
3037 nRowEst = ( iUpper - iLower ) * p.aiRowEst[0] / SQLITE_INDEX_SAMPLES;
3038 pnRow = nRowEst;
3039 }
3040  
3041 whereEqualScanEst_cancel:
3042 sqlite3ValueFree( ref pRhs );
3043 return rc;
3044 }
3045 #endif //* defined(SQLITE_ENABLE_STAT2) */
3046  
3047 #if SQLITE_ENABLE_STAT2
3048 /*
3049 ** Estimate the number of rows that will be returned based on
3050 ** an IN constraint where the right-hand side of the IN operator
3051 ** is a list of values. Example:
3052 **
3053 ** WHERE x IN (1,2,3,4)
3054 **
3055 ** Write the estimated row count into *pnRow and return SQLITE_OK.
3056 ** If unable to make an estimate, leave *pnRow unchanged and return
3057 ** non-zero.
3058 **
3059 ** This routine can fail if it is unable to load a collating sequence
3060 ** required for string comparison, or if unable to allocate memory
3061 ** for a UTF conversion required for comparison. The error is stored
3062 ** in the pParse structure.
3063 */
3064 static int whereInScanEst(
3065 Parse pParse, /* Parsing & code generating context */
3066 Index p, /* The index whose left-most column is pTerm */
3067 ExprList pList, /* The value list on the RHS of "x IN (v1,v2,v3,...)" */
3068 ref double pnRow /* Write the revised row estimate here */
3069 )
3070 {
3071 sqlite3_value pVal = null;/* One value from list */
3072 int iLower = 0;
3073 int iUpper = 0; /* Range of histogram regions containing pRhs */
3074 char aff; /* Column affinity */
3075 int rc = SQLITE_OK; /* Subfunction return code */
3076 double nRowEst; /* New estimate of the number of rows */
3077 int nSpan = 0; /* Number of histogram regions spanned */
3078 int nSingle = 0; /* Histogram regions hit by a single value */
3079 int nNotFound = 0; /* Count of values that are not constants */
3080 int i; /* Loop counter */
3081 u8[] aSpan = new u8[SQLITE_INDEX_SAMPLES + 1]; /* Histogram regions that are spanned */
3082 u8[] aSingle = new u8[SQLITE_INDEX_SAMPLES + 1]; /* Histogram regions hit once */
3083  
3084 Debug.Assert( p.aSample != null );
3085 aff = p.pTable.aCol[p.aiColumn[0]].affinity;
3086 //memset(aSpan, 0, sizeof(aSpan));
3087 //memset(aSingle, 0, sizeof(aSingle));
3088 for ( i = 0; i < pList.nExpr; i++ )
3089 {
3090 sqlite3ValueFree( ref pVal );
3091 rc = valueFromExpr( pParse, pList.a[i].pExpr, aff, ref pVal );
3092 if ( rc != 0 )
3093 break;
3094 if ( pVal == null || sqlite3_value_type( pVal ) == SQLITE_NULL )
3095 {
3096 nNotFound++;
3097 continue;
3098 }
3099 rc = whereRangeRegion( pParse, p, pVal, 0, out iLower );
3100 if ( rc != 0 )
3101 break;
3102 rc = whereRangeRegion( pParse, p, pVal, 1, out iUpper );
3103 if ( rc != 0 )
3104 break;
3105 if ( iLower >= iUpper )
3106 {
3107 aSingle[iLower] = 1;
3108 }
3109 else
3110 {
3111 Debug.Assert( iLower >= 0 && iUpper <= SQLITE_INDEX_SAMPLES );
3112 while ( iLower < iUpper )
3113 aSpan[iLower++] = 1;
3114 }
3115 }
3116 if ( rc == SQLITE_OK )
3117 {
3118 for ( i = nSpan = 0; i <= SQLITE_INDEX_SAMPLES; i++ )
3119 {
3120 if ( aSpan[i] != 0 )
3121 {
3122 nSpan++;
3123 }
3124 else if ( aSingle[i] != 0 )
3125 {
3126 nSingle++;
3127 }
3128 }
3129 nRowEst = ( nSpan * 2 + nSingle ) * p.aiRowEst[0] / ( 2 * SQLITE_INDEX_SAMPLES )
3130 + nNotFound * p.aiRowEst[1];
3131 if ( nRowEst > p.aiRowEst[0] )
3132 nRowEst = p.aiRowEst[0];
3133 pnRow = nRowEst;
3134 WHERETRACE( "IN row estimate: nSpan=%d, nSingle=%d, nNotFound=%d, est=%g\n",
3135 nSpan, nSingle, nNotFound, nRowEst );
3136 }
3137 sqlite3ValueFree( ref pVal );
3138 return rc;
3139 }
3140 #endif //* defined(SQLITE_ENABLE_STAT2) */
3141  
3142  
3143 /*
3144 ** Find the best query plan for accessing a particular table. Write the
3145 ** best query plan and its cost into the WhereCost object supplied as the
3146 ** last parameter.
3147 **
3148 ** The lowest cost plan wins. The cost is an estimate of the amount of
3149 ** CPU and disk I/O needed to process the requested result.
3150 ** Factors that influence cost include:
3151 **
3152 ** * The estimated number of rows that will be retrieved. (The
3153 ** fewer the better.)
3154 **
3155 ** * Whether or not sorting must occur.
3156 **
3157 ** * Whether or not there must be separate lookups in the
3158 ** index and in the main table.
3159 **
3160 ** If there was an INDEXED BY clause (pSrc->pIndex) attached to the table in
3161 ** the SQL statement, then this function only considers plans using the
3162 ** named index. If no such plan is found, then the returned cost is
3163 ** SQLITE_BIG_DBL. If a plan is found that uses the named index,
3164 ** then the cost is calculated in the usual way.
3165 **
3166 ** If a NOT INDEXED clause (pSrc->notIndexed!=0) was attached to the table
3167 ** in the SELECT statement, then no indexes are considered. However, the
3168 ** selected plan may still take advantage of the built-in rowid primary key
3169 ** index.
3170 */
3171 static void bestBtreeIndex(
3172 Parse pParse, /* The parsing context */
3173 WhereClause pWC, /* The WHERE clause */
3174 SrcList_item pSrc, /* The FROM clause term to search */
3175 Bitmask notReady, /* Mask of cursors not available for indexing */
3176 Bitmask notValid, /* Cursors not available for any purpose */
3177 ExprList pOrderBy, /* The ORDER BY clause */
3178 ref WhereCost pCost /* Lowest cost query plan */
3179 )
3180 {
3181 int iCur = pSrc.iCursor; /* The cursor of the table to be accessed */
3182 Index pProbe; /* An index we are evaluating */
3183 Index pIdx; /* Copy of pProbe, or zero for IPK index */
3184 u32 eqTermMask; /* Current mask of valid equality operators */
3185 u32 idxEqTermMask; /* Index mask of valid equality operators */
3186 Index sPk; /* A fake index object for the primary key */
3187 int[] aiRowEstPk = new int[2]; /* The aiRowEst[] value for the sPk index */
3188 int aiColumnPk = -1; /* The aColumn[] value for the sPk index */
3189 int wsFlagMask; /* Allowed flags in pCost.plan.wsFlag */
3190  
3191 /* Initialize the cost to a worst-case value */
3192 if ( pCost == null )
3193 pCost = new WhereCost();
3194 else
3195 pCost.Clear(); //memset(pCost, 0, sizeof(*pCost));
3196 pCost.rCost = SQLITE_BIG_DBL;
3197  
3198 /* If the pSrc table is the right table of a LEFT JOIN then we may not
3199 ** use an index to satisfy IS NULL constraints on that table. This is
3200 ** because columns might end up being NULL if the table does not match -
3201 ** a circumstance which the index cannot help us discover. Ticket #2177.
3202 */
3203 if ( ( pSrc.jointype & JT_LEFT ) != 0 )
3204 {
3205 idxEqTermMask = WO_EQ | WO_IN;
3206 }
3207 else
3208 {
3209 idxEqTermMask = WO_EQ | WO_IN | WO_ISNULL;
3210 }
3211  
3212 if ( pSrc.pIndex != null )
3213 {
3214 /* An INDEXED BY clause specifies a particular index to use */
3215 pIdx = pProbe = pSrc.pIndex;
3216 wsFlagMask = ~( WHERE_ROWID_EQ | WHERE_ROWID_RANGE );
3217 eqTermMask = idxEqTermMask;
3218 }
3219 else
3220 {
3221 /* There is no INDEXED BY clause. Create a fake Index object in local
3222 ** variable sPk to represent the rowid primary key index. Make this
3223 ** fake index the first in a chain of Index objects with all of the real
3224 ** indices to follow */
3225 Index pFirst; /* First of real indices on the table */
3226 sPk = new Index(); // memset( &sPk, 0, sizeof( Index ) );
3227 sPk.aSortOrder = new byte[1];
3228 sPk.azColl = new string[1];
3229 sPk.azColl[0] = string.Empty;
3230 sPk.nColumn = 1;
3231 sPk.aiColumn = new int[1];
3232 sPk.aiColumn[0] = aiColumnPk;
3233 sPk.aiRowEst = aiRowEstPk;
3234 sPk.onError = OE_Replace;
3235 sPk.pTable = pSrc.pTab;
3236 aiRowEstPk[0] = (int)pSrc.pTab.nRowEst;
3237 aiRowEstPk[1] = 1;
3238 pFirst = pSrc.pTab.pIndex;
3239 if ( pSrc.notIndexed == 0 )
3240 {
3241 /* The real indices of the table are only considered if the
3242 ** NOT INDEXED qualifier is omitted from the FROM clause */
3243 sPk.pNext = pFirst;
3244 }
3245 pProbe = sPk;
3246 wsFlagMask = ~(
3247 WHERE_COLUMN_IN | WHERE_COLUMN_EQ | WHERE_COLUMN_NULL | WHERE_COLUMN_RANGE
3248 );
3249 eqTermMask = WO_EQ | WO_IN;
3250 pIdx = null;
3251 }
3252  
3253 /* Loop over all indices looking for the best one to use
3254 */
3255 for ( ; pProbe != null; pIdx = pProbe = pProbe.pNext )
3256 {
3257 int[] aiRowEst = pProbe.aiRowEst;
3258 double cost; /* Cost of using pProbe */
3259 double nRow; /* Estimated number of rows in result set */
3260 double log10N = 0; /* base-10 logarithm of nRow (inexact) */
3261 int rev = 0; /* True to scan in reverse order */
3262 int wsFlags = 0;
3263 Bitmask used = 0;
3264  
3265 /* The following variables are populated based on the properties of
3266 ** index being evaluated. They are then used to determine the expected
3267 ** cost and number of rows returned.
3268 **
3269 ** nEq:
3270 ** Number of equality terms that can be implemented using the index.
3271 ** In other words, the number of initial fields in the index that
3272 ** are used in == or IN or NOT NULL constraints of the WHERE clause.
3273 **
3274 ** nInMul:
3275 ** The "in-multiplier". This is an estimate of how many seek operations
3276 ** SQLite must perform on the index in question. For example, if the
3277 ** WHERE clause is:
3278 **
3279 ** WHERE a IN (1, 2, 3) AND b IN (4, 5, 6)
3280 **
3281 ** SQLite must perform 9 lookups on an index on (a, b), so nInMul is
3282 ** set to 9. Given the same schema and either of the following WHERE
3283 ** clauses:
3284 **
3285 ** WHERE a = 1
3286 ** WHERE a >= 2
3287 **
3288 ** nInMul is set to 1.
3289 **
3290 ** If there exists a WHERE term of the form "x IN (SELECT ...)", then
3291 ** the sub-select is assumed to return 25 rows for the purposes of
3292 ** determining nInMul.
3293 **
3294 ** bInEst:
3295 ** Set to true if there was at least one "x IN (SELECT ...)" term used
3296 ** in determining the value of nInMul. Note that the RHS of the
3297 ** IN operator must be a SELECT, not a value list, for this variable
3298 ** to be true.
3299 **
3300 ** estBound:
3301 ** An estimate on the amount of the table that must be searched. A
3302 ** value of 100 means the entire table is searched. Range constraints
3303 ** might reduce this to a value less than 100 to indicate that only
3304 ** a fraction of the table needs searching. In the absence of
3305 ** sqlite_stat2 ANALYZE data, a single inequality reduces the search
3306 ** space to 1/4rd its original size. So an x>? constraint reduces
3307 ** estBound to 25. Two constraints (x>? AND x<?) reduce estBound to 6.
3308 **
3309 ** bSort:
3310 ** Boolean. True if there is an ORDER BY clause that will require an
3311 ** external sort (i.e. scanning the index being evaluated will not
3312 ** correctly order records).
3313 **
3314 ** bLookup:
3315 ** Boolean. True if a table lookup is required for each index entry
3316 ** visited. In other words, true if this is not a covering index.
3317 ** This is always false for the rowid primary key index of a table.
3318 ** For other indexes, it is true unless all the columns of the table
3319 ** used by the SELECT statement are present in the index (such an
3320 ** index is sometimes described as a covering index).
3321 ** For example, given the index on (a, b), the second of the following
3322 ** two queries requires table b-tree lookups in order to find the value
3323 ** of column c, but the first does not because columns a and b are
3324 ** both available in the index.
3325 **
3326 ** SELECT a, b FROM tbl WHERE a = 1;
3327 ** SELECT a, b, c FROM tbl WHERE a = 1;
3328 */
3329 int nEq; /* Number of == or IN terms matching index */
3330 int bInEst = 0; /* True if "x IN (SELECT...)" seen */
3331 int nInMul = 1; /* Number of distinct equalities to lookup */
3332 int estBound = 100; /* Estimated reduction in search space */
3333 int nBound = 0; /* Number of range constraints seen */
3334 int bSort = 0; /* True if external sort required */
3335 int bLookup = 0; /* True if not a covering index */
3336 WhereTerm pTerm; /* A single term of the WHERE clause */
3337 #if SQLITE_ENABLE_STAT2
3338 WhereTerm pFirstTerm = null; /* First term matching the index */
3339 #endif
3340  
3341 /* Determine the values of nEq and nInMul */
3342 for ( nEq = 0; nEq < pProbe.nColumn; nEq++ )
3343 {
3344 int j = pProbe.aiColumn[nEq];
3345 pTerm = findTerm( pWC, iCur, j, notReady, eqTermMask, pIdx );
3346 if ( pTerm == null )
3347 break;
3348 wsFlags |= ( WHERE_COLUMN_EQ | WHERE_ROWID_EQ );
3349 if ( ( pTerm.eOperator & WO_IN ) != 0 )
3350 {
3351 Expr pExpr = pTerm.pExpr;
3352 wsFlags |= WHERE_COLUMN_IN;
3353 if ( ExprHasProperty( pExpr, EP_xIsSelect ) )
3354 {
3355 /* "x IN (SELECT ...)": Assume the SELECT returns 25 rows */
3356 nInMul *= 25;
3357 bInEst = 1;
3358 }
3359 else if ( ALWAYS( pExpr.x.pList != null ) && pExpr.x.pList.nExpr != 0 )
3360 {
3361 /* "x IN (value, value, ...)" */
3362 nInMul *= pExpr.x.pList.nExpr;
3363 }
3364 }
3365 else if ( ( pTerm.eOperator & WO_ISNULL ) != 0 )
3366 {
3367 wsFlags |= WHERE_COLUMN_NULL;
3368 }
3369 #if SQLITE_ENABLE_STAT2
3370 if ( nEq == 0 && pProbe.aSample != null )
3371 pFirstTerm = pTerm;
3372 #endif
3373 used |= pTerm.prereqRight;
3374 }
3375  
3376 /* Determine the value of estBound. */
3377 if ( nEq < pProbe.nColumn && pProbe.bUnordered == 0 )
3378 {
3379 int j = pProbe.aiColumn[nEq];
3380 if ( findTerm( pWC, iCur, j, notReady, WO_LT | WO_LE | WO_GT | WO_GE, pIdx ) != null )
3381 {
3382 WhereTerm pTop = findTerm( pWC, iCur, j, notReady, WO_LT | WO_LE, pIdx );
3383 WhereTerm pBtm = findTerm( pWC, iCur, j, notReady, WO_GT | WO_GE, pIdx );
3384 whereRangeScanEst( pParse, pProbe, nEq, pBtm, pTop, out estBound );
3385 if ( pTop != null )
3386 {
3387 nBound = 1;
3388 wsFlags |= WHERE_TOP_LIMIT;
3389 used |= pTop.prereqRight;
3390 }
3391 if ( pBtm != null )
3392 {
3393 nBound++;
3394 wsFlags |= WHERE_BTM_LIMIT;
3395 used |= pBtm.prereqRight;
3396 }
3397 wsFlags |= ( WHERE_COLUMN_RANGE | WHERE_ROWID_RANGE );
3398 }
3399 }
3400 else if ( pProbe.onError != OE_None )
3401 {
3402 testcase( wsFlags & WHERE_COLUMN_IN );
3403 testcase( wsFlags & WHERE_COLUMN_NULL );
3404 if ( ( wsFlags & ( WHERE_COLUMN_IN | WHERE_COLUMN_NULL ) ) == 0 )
3405 {
3406 wsFlags |= WHERE_UNIQUE;
3407 }
3408 }
3409  
3410 /* If there is an ORDER BY clause and the index being considered will
3411 ** naturally scan rows in the required order, set the appropriate flags
3412 ** in wsFlags. Otherwise, if there is an ORDER BY clause but the index
3413 ** will scan rows in a different order, set the bSort variable. */
3414 if ( pOrderBy != null )
3415 {
3416 if ( ( wsFlags & WHERE_COLUMN_IN ) == 0
3417 && pProbe.bUnordered == 0
3418 && isSortingIndex( pParse, pWC.pMaskSet, pProbe, iCur, pOrderBy,
3419 nEq, wsFlags, ref rev )
3420 )
3421 {
3422 wsFlags |= WHERE_ROWID_RANGE | WHERE_COLUMN_RANGE | WHERE_ORDERBY;
3423 wsFlags |= ( rev != 0 ? WHERE_REVERSE : 0 );
3424 }
3425 else
3426 {
3427 bSort = 1;
3428 }
3429 }
3430  
3431 /* If currently calculating the cost of using an index (not the IPK
3432 ** index), determine if all required column data may be obtained without
3433 ** using the main table (i.e. if the index is a covering
3434 ** index for this query). If it is, set the WHERE_IDX_ONLY flag in
3435 ** wsFlags. Otherwise, set the bLookup variable to true. */
3436 if ( pIdx != null && wsFlags != 0 )
3437 {
3438 Bitmask m = pSrc.colUsed;
3439 int j;
3440 for ( j = 0; j < pIdx.nColumn; j++ )
3441 {
3442 int x = pIdx.aiColumn[j];
3443 if ( x < BMS - 1 )
3444 {
3445 m &= ~( ( (Bitmask)1 ) << x );
3446 }
3447 }
3448 if ( m == 0 )
3449 {
3450 wsFlags |= WHERE_IDX_ONLY;
3451 }
3452 else
3453 {
3454 bLookup = 1;
3455 }
3456 }
3457  
3458 /*
3459 ** Estimate the number of rows of output. For an "x IN (SELECT...)"
3460 ** constraint, do not let the estimate exceed half the rows in the table.
3461 */
3462 nRow = (double)( aiRowEst[nEq] * nInMul );
3463 if ( bInEst != 0 && nRow * 2 > aiRowEst[0] )
3464 {
3465 nRow = aiRowEst[0] / 2;
3466 nInMul = (int)( nRow / aiRowEst[nEq] );
3467 }
3468  
3469 #if SQLITE_ENABLE_STAT2
3470 /* If the constraint is of the form x=VALUE and histogram
3471 ** data is available for column x, then it might be possible
3472 ** to get a better estimate on the number of rows based on
3473 ** VALUE and how common that value is according to the histogram.
3474 */
3475 if ( nRow > (double)1 && nEq == 1 && pFirstTerm != null )
3476 {
3477 if ( ( pFirstTerm.eOperator & ( WO_EQ | WO_ISNULL ) ) != 0 )
3478 {
3479 testcase( pFirstTerm.eOperator == WO_EQ );
3480 testcase( pFirstTerm.eOperator == WO_ISNULL );
3481 whereEqualScanEst( pParse, pProbe, pFirstTerm.pExpr.pRight, ref nRow );
3482 }
3483 else if ( pFirstTerm.eOperator == WO_IN && bInEst == 0 )
3484 {
3485 whereInScanEst( pParse, pProbe, pFirstTerm.pExpr.x.pList, ref nRow );
3486 }
3487 }
3488 #endif //* SQLITE_ENABLE_STAT2 */
3489  
3490 /* Adjust the number of output rows and downward to reflect rows
3491 ** that are excluded by range constraints.
3492 */
3493 nRow = ( nRow * (double)estBound ) / (double)100;
3494 if ( nRow < 1 )
3495 nRow = 1;
3496  
3497 /* Experiments run on real SQLite databases show that the time needed
3498 ** to do a binary search to locate a row in a table or index is roughly
3499 ** log10(N) times the time to move from one row to the next row within
3500 ** a table or index. The actual times can vary, with the size of
3501 ** records being an important factor. Both moves and searches are
3502 ** slower with larger records, presumably because fewer records fit
3503 ** on one page and hence more pages have to be fetched.
3504 **
3505 ** The ANALYZE command and the sqlite_stat1 and sqlite_stat2 tables do
3506 ** not give us data on the relative sizes of table and index records.
3507 ** So this computation assumes table records are about twice as big
3508 ** as index records
3509 */
3510 if ( ( wsFlags & WHERE_NOT_FULLSCAN ) == 0 )
3511 {
3512 /* The cost of a full table scan is a number of move operations equal
3513 ** to the number of rows in the table.
3514 **
3515 ** We add an additional 4x penalty to full table scans. This causes
3516 ** the cost function to err on the side of choosing an index over
3517 ** choosing a full scan. This 4x full-scan penalty is an arguable
3518 ** decision and one which we expect to revisit in the future. But
3519 ** it seems to be working well enough at the moment.
3520 */
3521 cost = aiRowEst[0] * 4;
3522 }
3523 else
3524 {
3525 log10N = estLog( aiRowEst[0] );
3526 cost = nRow;
3527 if ( pIdx != null )
3528 {
3529 if ( bLookup != 0 )
3530 {
3531 /* For an index lookup followed by a table lookup:
3532 ** nInMul index searches to find the start of each index range
3533 ** + nRow steps through the index
3534 ** + nRow table searches to lookup the table entry using the rowid
3535 */
3536 cost += ( nInMul + nRow ) * log10N;
3537 }
3538 else
3539 {
3540 /* For a covering index:
3541 ** nInMul index searches to find the initial entry
3542 ** + nRow steps through the index
3543 */
3544 cost += nInMul * log10N;
3545 }
3546 }
3547 else
3548 {
3549 /* For a rowid primary key lookup:
3550 ** nInMult table searches to find the initial entry for each range
3551 ** + nRow steps through the table
3552 */
3553 cost += nInMul * log10N;
3554 }
3555 }
3556  
3557 /* Add in the estimated cost of sorting the result. Actual experimental
3558 ** measurements of sorting performance in SQLite show that sorting time
3559 ** adds C*N*log10(N) to the cost, where N is the number of rows to be
3560 ** sorted and C is a factor between 1.95 and 4.3. We will split the
3561 ** difference and select C of 3.0.
3562 */
3563 if ( bSort != 0 )
3564 {
3565 cost += nRow * estLog( nRow ) * 3;
3566 }
3567  
3568 /**** Cost of using this index has now been computed ****/
3569  
3570 /* If there are additional constraints on this table that cannot
3571 ** be used with the current index, but which might lower the number
3572 ** of output rows, adjust the nRow value accordingly. This only
3573 ** matters if the current index is the least costly, so do not bother
3574 ** with this step if we already know this index will not be chosen.
3575 ** Also, never reduce the output row count below 2 using this step.
3576 **
3577 ** It is critical that the notValid mask be used here instead of
3578 ** the notReady mask. When computing an "optimal" index, the notReady
3579 ** mask will only have one bit set - the bit for the current table.
3580 ** The notValid mask, on the other hand, always has all bits set for
3581 ** tables that are not in outer loops. If notReady is used here instead
3582 ** of notValid, then a optimal index that depends on inner joins loops
3583 ** might be selected even when there exists an optimal index that has
3584 ** no such dependency.
3585 */
3586 if ( nRow > 2 && cost <= pCost.rCost )
3587 {
3588 //int k; /* Loop counter */
3589 int nSkipEq = nEq; /* Number of == constraints to skip */
3590 int nSkipRange = nBound; /* Number of < constraints to skip */
3591 Bitmask thisTab; /* Bitmap for pSrc */
3592  
3593 thisTab = getMask( pWC.pMaskSet, iCur );
3594 for ( int ipTerm = 0, k = pWC.nTerm; nRow > 2 && k != 0; k--, ipTerm++ )//pTerm++)
3595 {
3596 pTerm = pWC.a[ipTerm];
3597 if ( ( pTerm.wtFlags & TERM_VIRTUAL ) != 0 )
3598 continue;
3599 if ( ( pTerm.prereqAll & notValid ) != thisTab )
3600 continue;
3601 if ( ( pTerm.eOperator & ( WO_EQ | WO_IN | WO_ISNULL ) ) != 0 )
3602 {
3603 if ( nSkipEq != 0 )
3604 {
3605 /* Ignore the first nEq equality matches since the index
3606 ** has already accounted for these */
3607 nSkipEq--;
3608 }
3609 else
3610 {
3611 /* Assume each additional equality match reduces the result
3612 ** set size by a factor of 10 */
3613 nRow /= 10;
3614 }
3615 }
3616 else if ( ( pTerm.eOperator & ( WO_LT | WO_LE | WO_GT | WO_GE ) ) != 0 )
3617 {
3618 if ( nSkipRange != 0 )
3619 {
3620 /* Ignore the first nSkipRange range constraints since the index
3621 ** has already accounted for these */
3622 nSkipRange--;
3623 }
3624 else
3625 {
3626 /* Assume each additional range constraint reduces the result
3627 ** set size by a factor of 3. Indexed range constraints reduce
3628 ** the search space by a larger factor: 4. We make indexed range
3629 ** more selective intentionally because of the subjective
3630 ** observation that indexed range constraints really are more
3631 ** selective in practice, on average. */
3632 nRow /= 3;
3633 }
3634 }
3635 else if ( pTerm.eOperator != WO_NOOP )
3636 {
3637 /* Any other expression lowers the output row count by half */
3638 nRow /= 2;
3639 }
3640 }
3641 if ( nRow < 2 )
3642 nRow = 2;
3643 }
3644  
3645 #if (SQLITE_TEST) && (SQLITE_DEBUG)
3646 WHERETRACE(
3647 "%s(%s): nEq=%d nInMul=%d estBound=%d bSort=%d bLookup=%d wsFlags=0x%x\n" +
3648 " notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f used=0x%llx\n",
3649 pSrc.pTab.zName, ( pIdx != null ? pIdx.zName : "ipk" ),
3650 nEq, nInMul, estBound, bSort, bLookup, wsFlags,
3651 notReady, log10N, cost, used
3652 );
3653 #endif
3654 /* If this index is the best we have seen so far, then record this
3655 ** index and its cost in the pCost structure.
3656 */
3657 if ( ( null == pIdx || wsFlags != 0 )
3658 && ( cost < pCost.rCost || ( cost <= pCost.rCost && nRow < pCost.plan.nRow ) )
3659 )
3660 {
3661 pCost.rCost = cost;
3662 pCost.used = used;
3663 pCost.plan.nRow = nRow;
3664 pCost.plan.wsFlags = (uint)( wsFlags & wsFlagMask );
3665 pCost.plan.nEq = (uint)nEq;
3666 pCost.plan.u.pIdx = pIdx;
3667 }
3668  
3669 /* If there was an INDEXED BY clause, then only that one index is
3670 ** considered. */
3671 if ( pSrc.pIndex != null )
3672 break;
3673  
3674 /* Reset masks for the next index in the loop */
3675 wsFlagMask = ~( WHERE_ROWID_EQ | WHERE_ROWID_RANGE );
3676 eqTermMask = idxEqTermMask;
3677 }
3678  
3679 /* If there is no ORDER BY clause and the SQLITE_ReverseOrder flag
3680 ** is set, then reverse the order that the index will be scanned
3681 ** in. This is used for application testing, to help find cases
3682 ** where application behaviour depends on the (undefined) order that
3683 ** SQLite outputs rows in in the absence of an ORDER BY clause. */
3684 if ( null == pOrderBy && ( pParse.db.flags & SQLITE_ReverseOrder ) != 0 )
3685 {
3686 pCost.plan.wsFlags |= WHERE_REVERSE;
3687 }
3688  
3689 Debug.Assert( pOrderBy != null || ( pCost.plan.wsFlags & WHERE_ORDERBY ) == 0 );
3690 Debug.Assert( pCost.plan.u.pIdx == null || ( pCost.plan.wsFlags & WHERE_ROWID_EQ ) == 0 );
3691 Debug.Assert( pSrc.pIndex == null
3692 || pCost.plan.u.pIdx == null
3693 || pCost.plan.u.pIdx == pSrc.pIndex
3694 );
3695  
3696 #if (SQLITE_TEST) && (SQLITE_DEBUG)
3697 WHERETRACE( "best index is: %s\n",
3698 ( ( pCost.plan.wsFlags & WHERE_NOT_FULLSCAN ) == 0 ? "none" :
3699 pCost.plan.u.pIdx != null ? pCost.plan.u.pIdx.zName : "ipk" )
3700 );
3701 #endif
3702 bestOrClauseIndex( pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost );
3703 bestAutomaticIndex( pParse, pWC, pSrc, notReady, pCost );
3704 pCost.plan.wsFlags |= (u32)eqTermMask;
3705 }
3706  
3707  
3708 /*
3709 ** Find the query plan for accessing table pSrc.pTab. Write the
3710 ** best query plan and its cost into the WhereCost object supplied
3711 ** as the last parameter. This function may calculate the cost of
3712 ** both real and virtual table scans.
3713 */
3714 static void bestIndex(
3715 Parse pParse, /* The parsing context */
3716 WhereClause pWC, /* The WHERE clause */
3717 SrcList_item pSrc, /* The FROM clause term to search */
3718 Bitmask notReady, /* Mask of cursors not available for indexing */
3719 Bitmask notValid, /* Cursors not available for any purpose */
3720 ExprList pOrderBy, /* The ORDER BY clause */
3721 ref WhereCost pCost /* Lowest cost query plan */
3722 )
3723 {
3724 #if !SQLITE_OMIT_VIRTUALTABLE
3725 if ( IsVirtual( pSrc.pTab ) )
3726 {
3727 sqlite3_index_info p = null;
3728 bestVirtualIndex( pParse, pWC, pSrc, notReady, notValid, pOrderBy, ref pCost, ref p );
3729 if ( p.needToFreeIdxStr != 0 )
3730 {
3731 //sqlite3_free(ref p.idxStr);
3732 }
3733 sqlite3DbFree( pParse.db, ref p );
3734 }
3735 else
3736 #endif
3737 {
3738 bestBtreeIndex( pParse, pWC, pSrc, notReady, notValid, pOrderBy, ref pCost );
3739 }
3740 }
3741  
3742 /*
3743 ** Disable a term in the WHERE clause. Except, do not disable the term
3744 ** if it controls a LEFT OUTER JOIN and it did not originate in the ON
3745 ** or USING clause of that join.
3746 **
3747 ** Consider the term t2.z='ok' in the following queries:
3748 **
3749 ** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
3750 ** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
3751 ** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
3752 **
3753 ** The t2.z='ok' is disabled in the in (2) because it originates
3754 ** in the ON clause. The term is disabled in (3) because it is not part
3755 ** of a LEFT OUTER JOIN. In (1), the term is not disabled.
3756 **
3757 ** IMPLEMENTATION-OF: R-24597-58655 No tests are done for terms that are
3758 ** completely satisfied by indices.
3759 **
3760 ** Disabling a term causes that term to not be tested in the inner loop
3761 ** of the join. Disabling is an optimization. When terms are satisfied
3762 ** by indices, we disable them to prevent redundant tests in the inner
3763 ** loop. We would get the correct results if nothing were ever disabled,
3764 ** but joins might run a little slower. The trick is to disable as much
3765 ** as we can without disabling too much. If we disabled in (1), we'd get
3766 ** the wrong answer. See ticket #813.
3767 */
3768 static void disableTerm( WhereLevel pLevel, WhereTerm pTerm )
3769 {
3770 if ( pTerm != null
3771 && ( pTerm.wtFlags & TERM_CODED ) == 0
3772 && ( pLevel.iLeftJoin == 0 || ExprHasProperty( pTerm.pExpr, EP_FromJoin ) ) )
3773 {
3774 pTerm.wtFlags |= TERM_CODED;
3775 if ( pTerm.iParent >= 0 )
3776 {
3777 WhereTerm pOther = pTerm.pWC.a[pTerm.iParent];
3778 if ( ( --pOther.nChild ) == 0 )
3779 {
3780 disableTerm( pLevel, pOther );
3781 }
3782 }
3783 }
3784 }
3785  
3786 /*
3787 ** Code an OP_Affinity opcode to apply the column affinity string zAff
3788 ** to the n registers starting at base.
3789 **
3790 ** As an optimization, SQLITE_AFF_NONE entries (which are no-ops) at the
3791 ** beginning and end of zAff are ignored. If all entries in zAff are
3792 ** SQLITE_AFF_NONE, then no code gets generated.
3793 **
3794 ** This routine makes its own copy of zAff so that the caller is free
3795 ** to modify zAff after this routine returns.
3796 */
3797 static void codeApplyAffinity( Parse pParse, int _base, int n, string zAff )
3798 {
3799 Vdbe v = pParse.pVdbe;
3800 //if (zAff == 0)
3801 //{
3802 // Debug.Assert(pParse.db.mallocFailed);
3803 // return;
3804 //}
3805 Debug.Assert( v != null );
3806 /* Adjust base and n to skip over SQLITE_AFF_NONE entries at the beginning
3807 ** and end of the affinity string.
3808 */
3809 while ( n > 0 && zAff[0] == SQLITE_AFF_NONE )
3810 {
3811 n--;
3812 _base++;
3813 zAff = zAff.Substring( 1 );// zAff++;
3814 }
3815 while ( n > 1 && zAff[n - 1] == SQLITE_AFF_NONE )
3816 {
3817 n--;
3818 }
3819  
3820 /* Code the OP_Affinity opcode if there is anything left to do. */
3821 if ( n > 0 )
3822 {
3823 sqlite3VdbeAddOp2( v, OP_Affinity, _base, n );
3824 sqlite3VdbeChangeP4( v, -1, zAff, n );
3825 sqlite3ExprCacheAffinityChange( pParse, _base, n );
3826 }
3827 }
3828  
3829 /*
3830 ** Generate code for a single equality term of the WHERE clause. An equality
3831 ** term can be either X=expr or X IN (...). pTerm is the term to be
3832 ** coded.
3833 **
3834 ** The current value for the constraint is left in register iReg.
3835 **
3836 ** For a constraint of the form X=expr, the expression is evaluated and its
3837 ** result is left on the stack. For constraints of the form X IN (...)
3838 ** this routine sets up a loop that will iterate over all values of X.
3839 */
3840 static int codeEqualityTerm(
3841 Parse pParse, /* The parsing context */
3842 WhereTerm pTerm, /* The term of the WHERE clause to be coded */
3843 WhereLevel pLevel, /* When level of the FROM clause we are working on */
3844 int iTarget /* Attempt to leave results in this register */
3845 )
3846 {
3847 Expr pX = pTerm.pExpr;
3848 Vdbe v = pParse.pVdbe;
3849 int iReg; /* Register holding results */
3850  
3851 Debug.Assert( iTarget > 0 );
3852 if ( pX.op == TK_EQ )
3853 {
3854 iReg = sqlite3ExprCodeTarget( pParse, pX.pRight, iTarget );
3855 }
3856 else if ( pX.op == TK_ISNULL )
3857 {
3858 iReg = iTarget;
3859 sqlite3VdbeAddOp2( v, OP_Null, 0, iReg );
3860 #if !SQLITE_OMIT_SUBQUERY
3861 }
3862 else
3863 {
3864 int eType;
3865 int iTab;
3866 InLoop pIn;
3867  
3868 Debug.Assert( pX.op == TK_IN );
3869 iReg = iTarget;
3870 int iDummy = -1;
3871 eType = sqlite3FindInIndex( pParse, pX, ref iDummy );
3872 iTab = pX.iTable;
3873 sqlite3VdbeAddOp2( v, OP_Rewind, iTab, 0 );
3874 Debug.Assert( ( pLevel.plan.wsFlags & WHERE_IN_ABLE ) != 0 );
3875 if ( pLevel.u._in.nIn == 0 )
3876 {
3877 pLevel.addrNxt = sqlite3VdbeMakeLabel( v );
3878 }
3879 pLevel.u._in.nIn++;
3880 if ( pLevel.u._in.aInLoop == null )
3881 pLevel.u._in.aInLoop = new InLoop[pLevel.u._in.nIn];
3882 else
3883 Array.Resize( ref pLevel.u._in.aInLoop, pLevel.u._in.nIn );
3884 //sqlite3DbReallocOrFree(pParse.db, pLevel.u._in.aInLoop,
3885 // sizeof(pLevel.u._in.aInLoop[0])*pLevel.u._in.nIn);
3886 //pIn = pLevel.u._in.aInLoop;
3887 if ( pLevel.u._in.aInLoop != null )//(pIn )
3888 {
3889 pLevel.u._in.aInLoop[pLevel.u._in.nIn - 1] = new InLoop();
3890 pIn = pLevel.u._in.aInLoop[pLevel.u._in.nIn - 1];//pIn++
3891 pIn.iCur = iTab;
3892 if ( eType == IN_INDEX_ROWID )
3893 {
3894 pIn.addrInTop = sqlite3VdbeAddOp2( v, OP_Rowid, iTab, iReg );
3895 }
3896 else
3897 {
3898 pIn.addrInTop = sqlite3VdbeAddOp3( v, OP_Column, iTab, 0, iReg );
3899 }
3900 sqlite3VdbeAddOp1( v, OP_IsNull, iReg );
3901 }
3902 else
3903 {
3904 pLevel.u._in.nIn = 0;
3905 }
3906 #endif
3907 }
3908 disableTerm( pLevel, pTerm );
3909 return iReg;
3910 }
3911  
3912 /*
3913 ** Generate code for a single equality term of the WHERE clause. An equality
3914 ** term can be either X=expr or X IN (...). pTerm is the term to be
3915 ** coded.
3916 **
3917 ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
3918 ** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10
3919 ** The index has as many as three equality constraints, but in this
3920 ** example, the third "c" value is an inequality. So only two
3921 ** constraints are coded. This routine will generate code to evaluate
3922 ** a==5 and b IN (1,2,3). The current values for a and b will be stored
3923 ** in consecutive registers and the index of the first register is returned.
3924 **
3925 ** In the example above nEq==2. But this subroutine works for any value
3926 ** of nEq including 0. If nEq==null, this routine is nearly a no-op.
3927 ** The only thing it does is allocate the pLevel.iMem memory cell and
3928 ** compute the affinity string.
3929 **
3930 ** This routine always allocates at least one memory cell and returns
3931 ** the index of that memory cell. The code that
3932 ** calls this routine will use that memory cell to store the termination
3933 ** key value of the loop. If one or more IN operators appear, then
3934 ** this routine allocates an additional nEq memory cells for internal
3935 ** use.
3936 **
3937 ** Before returning, *pzAff is set to point to a buffer containing a
3938 ** copy of the column affinity string of the index allocated using
3939 ** sqlite3DbMalloc(). Except, entries in the copy of the string associated
3940 ** with equality constraints that use NONE affinity are set to
3941 ** SQLITE_AFF_NONE. This is to deal with SQL such as the following:
3942 **
3943 ** CREATE TABLE t1(a TEXT PRIMARY KEY, b);
3944 ** SELECT ... FROM t1 AS t2, t1 WHERE t1.a = t2.b;
3945 **
3946 ** In the example above, the index on t1(a) has TEXT affinity. But since
3947 ** the right hand side of the equality constraint (t2.b) has NONE affinity,
3948 ** no conversion should be attempted before using a t2.b value as part of
3949 ** a key to search the index. Hence the first byte in the returned affinity
3950 ** string in this example would be set to SQLITE_AFF_NONE.
3951 */
3952 static int codeAllEqualityTerms(
3953 Parse pParse, /* Parsing context */
3954 WhereLevel pLevel, /* Which nested loop of the FROM we are coding */
3955 WhereClause pWC, /* The WHERE clause */
3956 Bitmask notReady, /* Which parts of FROM have not yet been coded */
3957 int nExtraReg, /* Number of extra registers to allocate */
3958 out StringBuilder pzAff /* OUT: Set to point to affinity string */
3959 )
3960 {
3961 int nEq = (int)pLevel.plan.nEq; /* The number of == or IN constraints to code */
3962 Vdbe v = pParse.pVdbe; /* The vm under construction */
3963 Index pIdx; /* The index being used for this loop */
3964 int iCur = pLevel.iTabCur; /* The cursor of the table */
3965 WhereTerm pTerm; /* A single constraint term */
3966 int j; /* Loop counter */
3967 int regBase; /* Base register */
3968 int nReg; /* Number of registers to allocate */
3969 StringBuilder zAff; /* Affinity string to return */
3970  
3971 /* This module is only called on query plans that use an index. */
3972 Debug.Assert( ( pLevel.plan.wsFlags & WHERE_INDEXED ) != 0 );
3973 pIdx = pLevel.plan.u.pIdx;
3974  
3975 /* Figure out how many memory cells we will need then allocate them.
3976 */
3977 regBase = pParse.nMem + 1;
3978 nReg = (int)( pLevel.plan.nEq + nExtraReg );
3979 pParse.nMem += nReg;
3980  
3981 zAff = new StringBuilder( sqlite3IndexAffinityStr( v, pIdx ) );//sqlite3DbStrDup(pParse.db, sqlite3IndexAffinityStr(v, pIdx));
3982 //if( null==zAff ){
3983 // pParse.db.mallocFailed = 1;
3984 //}
3985  
3986 /* Evaluate the equality constraints
3987 */
3988 Debug.Assert( pIdx.nColumn >= nEq );
3989 for ( j = 0; j < nEq; j++ )
3990 {
3991 int r1;
3992 int k = pIdx.aiColumn[j];
3993 pTerm = findTerm( pWC, iCur, k, notReady, pLevel.plan.wsFlags, pIdx );
3994 if ( NEVER( pTerm == null ) )
3995 break;
3996 /* The following true for indices with redundant columns.
3997 ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
3998 testcase( ( pTerm.wtFlags & TERM_CODED ) != 0 );
3999 testcase( pTerm.wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
4000 r1 = codeEqualityTerm( pParse, pTerm, pLevel, regBase + j );
4001 if ( r1 != regBase + j )
4002 {
4003 if ( nReg == 1 )
4004 {
4005 sqlite3ReleaseTempReg( pParse, regBase );
4006 regBase = r1;
4007 }
4008 else
4009 {
4010 sqlite3VdbeAddOp2( v, OP_SCopy, r1, regBase + j );
4011 }
4012 }
4013 testcase( pTerm.eOperator & WO_ISNULL );
4014 testcase( pTerm.eOperator & WO_IN );
4015 if ( ( pTerm.eOperator & ( WO_ISNULL | WO_IN ) ) == 0 )
4016 {
4017 Expr pRight = pTerm.pExpr.pRight;
4018 sqlite3ExprCodeIsNullJump( v, pRight, regBase + j, pLevel.addrBrk );
4019 if ( zAff.Length > 0 )
4020 {
4021 if ( sqlite3CompareAffinity( pRight, zAff[j] ) == SQLITE_AFF_NONE )
4022 {
4023 zAff[j] = SQLITE_AFF_NONE;
4024 }
4025 if ( ( sqlite3ExprNeedsNoAffinityChange( pRight, zAff[j] ) ) != 0 )
4026 {
4027 zAff[j] = SQLITE_AFF_NONE;
4028 }
4029 }
4030 }
4031 }
4032 pzAff = zAff;
4033 return regBase;
4034 }
4035  
4036 #if !SQLITE_OMIT_EXPLAIN
4037 /*
4038 ** This routine is a helper for explainIndexRange() below
4039 **
4040 ** pStr holds the text of an expression that we are building up one term
4041 ** at a time. This routine adds a new term to the end of the expression.
4042 ** Terms are separated by AND so add the "AND" text for second and subsequent
4043 ** terms only.
4044 */
4045 static void explainAppendTerm(
4046 StrAccum pStr, /* The text expression being built */
4047 int iTerm, /* Index of this term. First is zero */
4048 string zColumn, /* Name of the column */
4049 string zOp /* Name of the operator */
4050 )
4051 {
4052 if ( iTerm != 0 )
4053 sqlite3StrAccumAppend( pStr, " AND ", 5 );
4054 sqlite3StrAccumAppend( pStr, zColumn, -1 );
4055 sqlite3StrAccumAppend( pStr, zOp, 1 );
4056 sqlite3StrAccumAppend( pStr, "?", 1 );
4057 }
4058  
4059 /*
4060 ** Argument pLevel describes a strategy for scanning table pTab. This
4061 ** function returns a pointer to a string buffer containing a description
4062 ** of the subset of table rows scanned by the strategy in the form of an
4063 ** SQL expression. Or, if all rows are scanned, NULL is returned.
4064 **
4065 ** For example, if the query:
4066 **
4067 ** SELECT * FROM t1 WHERE a=1 AND b>2;
4068 **
4069 ** is run and there is an index on (a, b), then this function returns a
4070 ** string similar to:
4071 **
4072 ** "a=? AND b>?"
4073 **
4074 ** The returned pointer points to memory obtained from sqlite3DbMalloc().
4075 ** It is the responsibility of the caller to free the buffer when it is
4076 ** no longer required.
4077 */
4078 static string explainIndexRange( sqlite3 db, WhereLevel pLevel, Table pTab )
4079 {
4080 WherePlan pPlan = pLevel.plan;
4081 Index pIndex = pPlan.u.pIdx;
4082 uint nEq = pPlan.nEq;
4083 int i, j;
4084 Column[] aCol = pTab.aCol;
4085 int[] aiColumn = pIndex.aiColumn;
4086 StrAccum txt = new StrAccum( 100 );
4087  
4088 if ( nEq == 0 && ( pPlan.wsFlags & ( WHERE_BTM_LIMIT | WHERE_TOP_LIMIT ) ) == 0 )
4089 {
4090 return null;
4091 }
4092 sqlite3StrAccumInit( txt, null, 0, SQLITE_MAX_LENGTH );
4093 txt.db = db;
4094 sqlite3StrAccumAppend( txt, " (", 2 );
4095 for ( i = 0; i < nEq; i++ )
4096 {
4097 explainAppendTerm( txt, i, aCol[aiColumn[i]].zName, "=" );
4098 }
4099  
4100 j = i;
4101 if ( ( pPlan.wsFlags & WHERE_BTM_LIMIT ) != 0 )
4102 {
4103 explainAppendTerm( txt, i++, aCol[aiColumn[j]].zName, ">" );
4104 }
4105 if ( ( pPlan.wsFlags & WHERE_TOP_LIMIT ) != 0 )
4106 {
4107 explainAppendTerm( txt, i, aCol[aiColumn[j]].zName, "<" );
4108 }
4109 sqlite3StrAccumAppend( txt, ")", 1 );
4110 return sqlite3StrAccumFinish( txt );
4111 }
4112  
4113 /*
4114 ** This function is a no-op unless currently processing an EXPLAIN QUERY PLAN
4115 ** command. If the query being compiled is an EXPLAIN QUERY PLAN, a single
4116 ** record is added to the output to describe the table scan strategy in
4117 ** pLevel.
4118 */
4119 static void explainOneScan(
4120 Parse pParse, /* Parse context */
4121 SrcList pTabList, /* Table list this loop refers to */
4122 WhereLevel pLevel, /* Scan to write OP_Explain opcode for */
4123 int iLevel, /* Value for "level" column of output */
4124 int iFrom, /* Value for "from" column of output */
4125 u16 wctrlFlags /* Flags passed to sqlite3WhereBegin() */
4126 )
4127 {
4128 if ( pParse.explain == 2 )
4129 {
4130 u32 flags = pLevel.plan.wsFlags;
4131 SrcList_item pItem = pTabList.a[pLevel.iFrom];
4132 Vdbe v = pParse.pVdbe; /* VM being constructed */
4133 sqlite3 db = pParse.db; /* Database handle */
4134 StringBuilder zMsg = new StringBuilder( 1000 ); /* Text to add to EQP output */
4135 sqlite3_int64 nRow; /* Expected number of rows visited by scan */
4136 int iId = pParse.iSelectId; /* Select id (left-most output column) */
4137 bool isSearch; /* True for a SEARCH. False for SCAN. */
4138  
4139 if ( ( flags & WHERE_MULTI_OR ) != 0 || ( wctrlFlags & WHERE_ONETABLE_ONLY ) != 0 )
4140 return;
4141  
4142 isSearch = ( pLevel.plan.nEq > 0 )
4143 || ( flags & ( WHERE_BTM_LIMIT | WHERE_TOP_LIMIT ) ) != 0
4144 || ( wctrlFlags & ( WHERE_ORDERBY_MIN | WHERE_ORDERBY_MAX ) ) != 0;
4145  
4146 zMsg.Append( sqlite3MPrintf( db, "%s", isSearch ? "SEARCH" : "SCAN" ) );
4147 if ( pItem.pSelect != null )
4148 {
4149 zMsg.Append( sqlite3MAppendf( db, null, " SUBQUERY %d", pItem.iSelectId ) );
4150 }
4151 else
4152 {
4153 zMsg.Append( sqlite3MAppendf( db, null, " TABLE %s", pItem.zName ) );
4154 }
4155  
4156 if ( pItem.zAlias != null )
4157 {
4158 zMsg.Append( sqlite3MAppendf( db, null, " AS %s", pItem.zAlias ) );
4159 }
4160 if ( ( flags & WHERE_INDEXED ) != 0 )
4161 {
4162 string zWhere = explainIndexRange( db, pLevel, pItem.pTab );
4163 zMsg.Append( sqlite3MAppendf( db, null, " USING %s%sINDEX%s%s%s",
4164 ( ( flags & WHERE_TEMP_INDEX ) != 0 ? "AUTOMATIC " : string.Empty ),
4165 ( ( flags & WHERE_IDX_ONLY ) != 0 ? "COVERING " : string.Empty ),
4166 ( ( flags & WHERE_TEMP_INDEX ) != 0 ? string.Empty : " " ),
4167 ( ( flags & WHERE_TEMP_INDEX ) != 0 ? string.Empty : pLevel.plan.u.pIdx.zName ),
4168 zWhere ?? string.Empty
4169 ) );
4170 sqlite3DbFree( db, ref zWhere );
4171 }
4172 else if ( ( flags & ( WHERE_ROWID_EQ | WHERE_ROWID_RANGE ) ) != 0 )
4173 {
4174 zMsg.Append( " USING INTEGER PRIMARY KEY" );
4175  
4176 if ( ( flags & WHERE_ROWID_EQ ) != 0 )
4177 {
4178 zMsg.Append( " (rowid=?)" );
4179 }
4180 else if ( ( flags & WHERE_BOTH_LIMIT ) == WHERE_BOTH_LIMIT )
4181 {
4182 zMsg.Append( " (rowid>? AND rowid<?)" );
4183 }
4184 else if ( ( flags & WHERE_BTM_LIMIT ) != 0 )
4185 {
4186 zMsg.Append( " (rowid>?)" );
4187 }
4188 else if ( ( flags & WHERE_TOP_LIMIT ) != 0 )
4189 {
4190 zMsg.Append( " (rowid<?)" );
4191 }
4192 }
4193 #if !SQLITE_OMIT_VIRTUALTABLE
4194 else if ( ( flags & WHERE_VIRTUALTABLE ) != 0 )
4195 {
4196 sqlite3_index_info pVtabIdx = pLevel.plan.u.pVtabIdx;
4197 zMsg.Append( sqlite3MAppendf( db, null, " VIRTUAL TABLE INDEX %d:%s",
4198 pVtabIdx.idxNum, pVtabIdx.idxStr ) );
4199 }
4200 #endif
4201 if ( ( wctrlFlags & ( WHERE_ORDERBY_MIN | WHERE_ORDERBY_MAX ) ) != 0 )
4202 {
4203 testcase( wctrlFlags & WHERE_ORDERBY_MIN );
4204 nRow = 1;
4205 }
4206 else
4207 {
4208 nRow = (sqlite3_int64)pLevel.plan.nRow;
4209 }
4210 zMsg.Append( sqlite3MAppendf( db, null, " (~%lld rows)", nRow ) );
4211 sqlite3VdbeAddOp4( v, OP_Explain, iId, iLevel, iFrom, zMsg, P4_DYNAMIC );
4212 }
4213 }
4214 #else
4215 //# define explainOneScan(u,v,w,x,y,z)
4216 static void explainOneScan( Parse u, SrcList v, WhereLevel w, int x, int y, u16 z){}
4217 #endif //* SQLITE_OMIT_EXPLAIN */
4218  
4219  
4220 /*
4221 ** Generate code for the start of the iLevel-th loop in the WHERE clause
4222 ** implementation described by pWInfo.
4223 */
4224 static Bitmask codeOneLoopStart(
4225 WhereInfo pWInfo, /* Complete information about the WHERE clause */
4226 int iLevel, /* Which level of pWInfo.a[] should be coded */
4227 u16 wctrlFlags, /* One of the WHERE_* flags defined in sqliteInt.h */
4228 Bitmask notReady /* Which tables are currently available */
4229 )
4230 {
4231 int j, k; /* Loop counters */
4232 int iCur; /* The VDBE cursor for the table */
4233 int addrNxt; /* Where to jump to continue with the next IN case */
4234 int omitTable; /* True if we use the index only */
4235 int bRev; /* True if we need to scan in reverse order */
4236 WhereLevel pLevel; /* The where level to be coded */
4237 WhereClause pWC; /* Decomposition of the entire WHERE clause */
4238 WhereTerm pTerm; /* A WHERE clause term */
4239 Parse pParse; /* Parsing context */
4240 Vdbe v; /* The prepared stmt under constructions */
4241 SrcList_item pTabItem; /* FROM clause term being coded */
4242 int addrBrk; /* Jump here to break out of the loop */
4243 int addrCont; /* Jump here to continue with next cycle */
4244 int iRowidReg = 0; /* Rowid is stored in this register, if not zero */
4245 int iReleaseReg = 0; /* Temp register to free before returning */
4246  
4247 pParse = pWInfo.pParse;
4248 v = pParse.pVdbe;
4249 pWC = pWInfo.pWC;
4250 pLevel = pWInfo.a[iLevel];
4251 pTabItem = pWInfo.pTabList.a[pLevel.iFrom];
4252 iCur = pTabItem.iCursor;
4253 bRev = ( pLevel.plan.wsFlags & WHERE_REVERSE ) != 0 ? 1 : 0;
4254 omitTable = ( ( pLevel.plan.wsFlags & WHERE_IDX_ONLY ) != 0
4255 && ( wctrlFlags & WHERE_FORCE_TABLE ) == 0 ) ? 1 : 0;
4256  
4257 /* Create labels for the "break" and "continue" instructions
4258 ** for the current loop. Jump to addrBrk to break out of a loop.
4259 ** Jump to cont to go immediately to the next iteration of the
4260 ** loop.
4261 **
4262 ** When there is an IN operator, we also have a "addrNxt" label that
4263 ** means to continue with the next IN value combination. When
4264 ** there are no IN operators in the constraints, the "addrNxt" label
4265 ** is the same as "addrBrk".
4266 */
4267 addrBrk = pLevel.addrBrk = pLevel.addrNxt = sqlite3VdbeMakeLabel( v );
4268 addrCont = pLevel.addrCont = sqlite3VdbeMakeLabel( v );
4269  
4270 /* If this is the right table of a LEFT OUTER JOIN, allocate and
4271 ** initialize a memory cell that records if this table matches any
4272 ** row of the left table of the join.
4273 */
4274 if ( pLevel.iFrom > 0 && ( pTabItem.jointype & JT_LEFT ) != 0 )// Check value of pTabItem[0].jointype
4275 {
4276 pLevel.iLeftJoin = ++pParse.nMem;
4277 sqlite3VdbeAddOp2( v, OP_Integer, 0, pLevel.iLeftJoin );
4278 #if SQLITE_DEBUG
4279 VdbeComment( v, "init LEFT JOIN no-match flag" );
4280 #endif
4281 }
4282  
4283 #if !SQLITE_OMIT_VIRTUALTABLE
4284 if ( ( pLevel.plan.wsFlags & WHERE_VIRTUALTABLE ) != 0 )
4285 {
4286 /* Case 0: The table is a virtual-table. Use the VFilter and VNext
4287 ** to access the data.
4288 */
4289 int iReg; /* P3 Value for OP_VFilter */
4290 sqlite3_index_info pVtabIdx = pLevel.plan.u.pVtabIdx;
4291 int nConstraint = pVtabIdx.nConstraint;
4292 sqlite3_index_constraint_usage[] aUsage = pVtabIdx.aConstraintUsage;
4293 sqlite3_index_constraint[] aConstraint = pVtabIdx.aConstraint;
4294  
4295 sqlite3ExprCachePush( pParse );
4296 iReg = sqlite3GetTempRange( pParse, nConstraint + 2 );
4297 for ( j = 1; j <= nConstraint; j++ )
4298 {
4299 for ( k = 0; k < nConstraint; k++ )
4300 {
4301 if ( aUsage[k].argvIndex == j )
4302 {
4303 int iTerm = aConstraint[k].iTermOffset;
4304 sqlite3ExprCode( pParse, pWC.a[iTerm].pExpr.pRight, iReg + j + 1 );
4305 break;
4306 }
4307 }
4308 if ( k == nConstraint )
4309 break;
4310 }
4311 sqlite3VdbeAddOp2( v, OP_Integer, pVtabIdx.idxNum, iReg );
4312 sqlite3VdbeAddOp2( v, OP_Integer, j - 1, iReg + 1 );
4313 sqlite3VdbeAddOp4( v, OP_VFilter, iCur, addrBrk, iReg, pVtabIdx.idxStr,
4314 pVtabIdx.needToFreeIdxStr != 0 ? P4_MPRINTF : P4_STATIC );
4315 pVtabIdx.needToFreeIdxStr = 0;
4316 for ( j = 0; j < nConstraint; j++ )
4317 {
4318 if ( aUsage[j].omit != false )
4319 {
4320 int iTerm = aConstraint[j].iTermOffset;
4321 disableTerm( pLevel, pWC.a[iTerm] );
4322 }
4323 }
4324 pLevel.op = OP_VNext;
4325 pLevel.p1 = iCur;
4326 pLevel.p2 = sqlite3VdbeCurrentAddr( v );
4327 sqlite3ReleaseTempRange( pParse, iReg, nConstraint + 2 );
4328 sqlite3ExprCachePop( pParse, 1 );
4329 }
4330 else
4331 #endif //* SQLITE_OMIT_VIRTUALTABLE */
4332  
4333 if ( ( pLevel.plan.wsFlags & WHERE_ROWID_EQ ) != 0 )
4334 {
4335 /* Case 1: We can directly reference a single row using an
4336 ** equality comparison against the ROWID field. Or
4337 ** we reference multiple rows using a "rowid IN (...)"
4338 ** construct.
4339 */
4340 iReleaseReg = sqlite3GetTempReg( pParse );
4341 pTerm = findTerm( pWC, iCur, -1, notReady, WO_EQ | WO_IN, null );
4342 Debug.Assert( pTerm != null );
4343 Debug.Assert( pTerm.pExpr != null );
4344 Debug.Assert( pTerm.leftCursor == iCur );
4345 Debug.Assert( omitTable == 0 );
4346 testcase( pTerm.wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
4347 iRowidReg = codeEqualityTerm( pParse, pTerm, pLevel, iReleaseReg );
4348 addrNxt = pLevel.addrNxt;
4349 sqlite3VdbeAddOp2( v, OP_MustBeInt, iRowidReg, addrNxt );
4350 sqlite3VdbeAddOp3( v, OP_NotExists, iCur, addrNxt, iRowidReg );
4351 sqlite3ExprCacheStore( pParse, iCur, -1, iRowidReg );
4352 #if SQLITE_DEBUG
4353 VdbeComment( v, "pk" );
4354 #endif
4355 pLevel.op = OP_Noop;
4356 }
4357 else if ( ( pLevel.plan.wsFlags & WHERE_ROWID_RANGE ) != 0 )
4358 {
4359 /* Case 2: We have an inequality comparison against the ROWID field.
4360 */
4361 int testOp = OP_Noop;
4362 int start;
4363 int memEndValue = 0;
4364 WhereTerm pStart, pEnd;
4365  
4366 Debug.Assert( omitTable == 0 );
4367 pStart = findTerm( pWC, iCur, -1, notReady, WO_GT | WO_GE, null );
4368 pEnd = findTerm( pWC, iCur, -1, notReady, WO_LT | WO_LE, null );
4369 if ( bRev != 0 )
4370 {
4371 pTerm = pStart;
4372 pStart = pEnd;
4373 pEnd = pTerm;
4374 }
4375 if ( pStart != null )
4376 {
4377 Expr pX; /* The expression that defines the start bound */
4378 int r1, rTemp = 0; /* Registers for holding the start boundary */
4379  
4380 /* The following constant maps TK_xx codes into corresponding
4381 ** seek opcodes. It depends on a particular ordering of TK_xx
4382 */
4383 u8[] aMoveOp = new u8[]{
4384 /* TK_GT */ OP_SeekGt,
4385 /* TK_LE */ OP_SeekLe,
4386 /* TK_LT */ OP_SeekLt,
4387 /* TK_GE */ OP_SeekGe
4388 };
4389 Debug.Assert( TK_LE == TK_GT + 1 ); /* Make sure the ordering.. */
4390 Debug.Assert( TK_LT == TK_GT + 2 ); /* ... of the TK_xx values... */
4391 Debug.Assert( TK_GE == TK_GT + 3 ); /* ... is correcct. */
4392  
4393 testcase( pStart.wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
4394 pX = pStart.pExpr;
4395 Debug.Assert( pX != null );
4396 Debug.Assert( pStart.leftCursor == iCur );
4397 r1 = sqlite3ExprCodeTemp( pParse, pX.pRight, ref rTemp );
4398 sqlite3VdbeAddOp3( v, aMoveOp[pX.op - TK_GT], iCur, addrBrk, r1 );
4399 #if SQLITE_DEBUG
4400 VdbeComment( v, "pk" );
4401 #endif
4402 sqlite3ExprCacheAffinityChange( pParse, r1, 1 );
4403 sqlite3ReleaseTempReg( pParse, rTemp );
4404 disableTerm( pLevel, pStart );
4405 }
4406 else
4407 {
4408 sqlite3VdbeAddOp2( v, bRev != 0 ? OP_Last : OP_Rewind, iCur, addrBrk );
4409 }
4410 if ( pEnd != null )
4411 {
4412 Expr pX;
4413 pX = pEnd.pExpr;
4414 Debug.Assert( pX != null );
4415 Debug.Assert( pEnd.leftCursor == iCur );
4416 testcase( pEnd.wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
4417 memEndValue = ++pParse.nMem;
4418 sqlite3ExprCode( pParse, pX.pRight, memEndValue );
4419 if ( pX.op == TK_LT || pX.op == TK_GT )
4420 {
4421 testOp = bRev != 0 ? OP_Le : OP_Ge;
4422 }
4423 else
4424 {
4425 testOp = bRev != 0 ? OP_Lt : OP_Gt;
4426 }
4427 disableTerm( pLevel, pEnd );
4428 }
4429 start = sqlite3VdbeCurrentAddr( v );
4430 pLevel.op = (u8)( bRev != 0 ? OP_Prev : OP_Next );
4431 pLevel.p1 = iCur;
4432 pLevel.p2 = start;
4433 if ( pStart == null && pEnd == null )
4434 {
4435 pLevel.p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
4436 }
4437 else
4438 {
4439 Debug.Assert( pLevel.p5 == 0 );
4440 }
4441 if ( testOp != OP_Noop )
4442 {
4443 iRowidReg = iReleaseReg = sqlite3GetTempReg( pParse );
4444 sqlite3VdbeAddOp2( v, OP_Rowid, iCur, iRowidReg );
4445 sqlite3ExprCacheStore( pParse, iCur, -1, iRowidReg );
4446 sqlite3VdbeAddOp3( v, testOp, memEndValue, addrBrk, iRowidReg );
4447 sqlite3VdbeChangeP5( v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL );
4448 }
4449 }
4450 else if ( ( pLevel.plan.wsFlags & ( WHERE_COLUMN_RANGE | WHERE_COLUMN_EQ ) ) != 0 )
4451 {
4452 /* Case 3: A scan using an index.
4453 **
4454 ** The WHERE clause may contain zero or more equality
4455 ** terms ("==" or "IN" operators) that refer to the N
4456 ** left-most columns of the index. It may also contain
4457 ** inequality constraints (>, <, >= or <=) on the indexed
4458 ** column that immediately follows the N equalities. Only
4459 ** the right-most column can be an inequality - the rest must
4460 ** use the "==" and "IN" operators. For example, if the
4461 ** index is on (x,y,z), then the following clauses are all
4462 ** optimized:
4463 **
4464 ** x=5
4465 ** x=5 AND y=10
4466 ** x=5 AND y<10
4467 ** x=5 AND y>5 AND y<10
4468 ** x=5 AND y=5 AND z<=10
4469 **
4470 ** The z<10 term of the following cannot be used, only
4471 ** the x=5 term:
4472 **
4473 ** x=5 AND z<10
4474 **
4475 ** N may be zero if there are inequality constraints.
4476 ** If there are no inequality constraints, then N is at
4477 ** least one.
4478 **
4479 ** This case is also used when there are no WHERE clause
4480 ** constraints but an index is selected anyway, in order
4481 ** to force the output order to conform to an ORDER BY.
4482 */
4483 u8[] aStartOp = new u8[] {
4484 0,
4485 0,
4486 OP_Rewind, /* 2: (!start_constraints && startEq && !bRev) */
4487 OP_Last, /* 3: (!start_constraints && startEq && bRev) */
4488 OP_SeekGt, /* 4: (start_constraints && !startEq && !bRev) */
4489 OP_SeekLt, /* 5: (start_constraints && !startEq && bRev) */
4490 OP_SeekGe, /* 6: (start_constraints && startEq && !bRev) */
4491 OP_SeekLe /* 7: (start_constraints && startEq && bRev) */
4492 };
4493 u8[] aEndOp = new u8[] {
4494 OP_Noop, /* 0: (!end_constraints) */
4495 OP_IdxGE, /* 1: (end_constraints && !bRev) */
4496 OP_IdxLT /* 2: (end_constraints && bRev) */
4497 };
4498 int nEq = (int)pLevel.plan.nEq; /* Number of == or IN terms */
4499 int isMinQuery = 0; /* If this is an optimized SELECT min(x).. */
4500 int regBase; /* Base register holding constraint values */
4501 int r1; /* Temp register */
4502 WhereTerm pRangeStart = null; /* Inequality constraint at range start */
4503 WhereTerm pRangeEnd = null; /* Inequality constraint at range end */
4504 int startEq; /* True if range start uses ==, >= or <= */
4505 int endEq; /* True if range end uses ==, >= or <= */
4506 int start_constraints; /* Start of range is constrained */
4507 int nConstraint; /* Number of constraint terms */
4508 Index pIdx; /* The index we will be using */
4509 int iIdxCur; /* The VDBE cursor for the index */
4510 int nExtraReg = 0; /* Number of extra registers needed */
4511 int op; /* Instruction opcode */
4512 StringBuilder zStartAff = new StringBuilder();
4513 ;/* Affinity for start of range constraint */
4514 StringBuilder zEndAff; /* Affinity for end of range constraint */
4515  
4516 pIdx = pLevel.plan.u.pIdx;
4517 iIdxCur = pLevel.iIdxCur;
4518 k = pIdx.aiColumn[nEq]; /* Column for inequality constraints */
4519  
4520 /* If this loop satisfies a sort order (pOrderBy) request that
4521 ** was pDebug.Assed to this function to implement a "SELECT min(x) ..."
4522 ** query, then the caller will only allow the loop to run for
4523 ** a single iteration. This means that the first row returned
4524 ** should not have a NULL value stored in 'x'. If column 'x' is
4525 ** the first one after the nEq equality constraints in the index,
4526 ** this requires some special handling.
4527 */
4528 if ( ( wctrlFlags & WHERE_ORDERBY_MIN ) != 0
4529 && ( ( pLevel.plan.wsFlags & WHERE_ORDERBY ) != 0 )
4530 && ( pIdx.nColumn > nEq )
4531 )
4532 {
4533 /* Debug.Assert( pOrderBy.nExpr==1 ); */
4534 /* Debug.Assert( pOrderBy.a[0].pExpr.iColumn==pIdx.aiColumn[nEq] ); */
4535 isMinQuery = 1;
4536 nExtraReg = 1;
4537 }
4538  
4539 /* Find any inequality constraint terms for the start and end
4540 ** of the range.
4541 */
4542 if ( ( pLevel.plan.wsFlags & WHERE_TOP_LIMIT ) != 0 )
4543 {
4544 pRangeEnd = findTerm( pWC, iCur, k, notReady, ( WO_LT | WO_LE ), pIdx );
4545 nExtraReg = 1;
4546 }
4547 if ( ( pLevel.plan.wsFlags & WHERE_BTM_LIMIT ) != 0 )
4548 {
4549 pRangeStart = findTerm( pWC, iCur, k, notReady, ( WO_GT | WO_GE ), pIdx );
4550 nExtraReg = 1;
4551 }
4552  
4553 /* Generate code to evaluate all constraint terms using == or IN
4554 ** and store the values of those terms in an array of registers
4555 ** starting at regBase.
4556 */
4557 regBase = codeAllEqualityTerms(
4558 pParse, pLevel, pWC, notReady, nExtraReg, out zStartAff
4559 );
4560 zEndAff = new StringBuilder( zStartAff.ToString() );//sqlite3DbStrDup(pParse.db, zStartAff);
4561 addrNxt = pLevel.addrNxt;
4562  
4563 /* If we are doing a reverse order scan on an ascending index, or
4564 ** a forward order scan on a descending index, interchange the
4565 ** start and end terms (pRangeStart and pRangeEnd).
4566 */
4567 if ( nEq < pIdx.nColumn && bRev == ( pIdx.aSortOrder[nEq] == SQLITE_SO_ASC ? 1 : 0 ) )
4568 {
4569 SWAP( ref pRangeEnd, ref pRangeStart );
4570 }
4571  
4572 testcase( pRangeStart != null && ( pRangeStart.eOperator & WO_LE ) != 0 );
4573 testcase( pRangeStart != null && ( pRangeStart.eOperator & WO_GE ) != 0 );
4574 testcase( pRangeEnd != null && ( pRangeEnd.eOperator & WO_LE ) != 0 );
4575 testcase( pRangeEnd != null && ( pRangeEnd.eOperator & WO_GE ) != 0 );
4576 startEq = ( null == pRangeStart || ( pRangeStart.eOperator & ( WO_LE | WO_GE ) ) != 0 ) ? 1 : 0;
4577 endEq = ( null == pRangeEnd || ( pRangeEnd.eOperator & ( WO_LE | WO_GE ) ) != 0 ) ? 1 : 0;
4578 start_constraints = ( pRangeStart != null || nEq > 0 ) ? 1 : 0;
4579  
4580 /* Seek the index cursor to the start of the range. */
4581 nConstraint = nEq;
4582 if ( pRangeStart != null )
4583 {
4584 Expr pRight = pRangeStart.pExpr.pRight;
4585 sqlite3ExprCode( pParse, pRight, regBase + nEq );
4586 if ( ( pRangeStart.wtFlags & TERM_VNULL ) == 0 )
4587 {
4588 sqlite3ExprCodeIsNullJump( v, pRight, regBase + nEq, addrNxt );
4589 }
4590 if ( zStartAff.Length != 0 )
4591 {
4592 if ( sqlite3CompareAffinity( pRight, zStartAff[nEq] ) == SQLITE_AFF_NONE )
4593 {
4594 /* Since the comparison is to be performed with no conversions
4595 ** applied to the operands, set the affinity to apply to pRight to
4596 ** SQLITE_AFF_NONE. */
4597 zStartAff[nEq] = SQLITE_AFF_NONE;
4598 }
4599 if ( ( sqlite3ExprNeedsNoAffinityChange( pRight, zStartAff[nEq] ) ) != 0 )
4600 {
4601 zStartAff[nEq] = SQLITE_AFF_NONE;
4602 }
4603 }
4604 nConstraint++;
4605 testcase( pRangeStart.wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
4606 }
4607 else if ( isMinQuery != 0 )
4608 {
4609 sqlite3VdbeAddOp2( v, OP_Null, 0, regBase + nEq );
4610 nConstraint++;
4611 startEq = 0;
4612 start_constraints = 1;
4613 }
4614 codeApplyAffinity( pParse, regBase, nConstraint, zStartAff.ToString() );
4615 op = aStartOp[( start_constraints << 2 ) + ( startEq << 1 ) + bRev];
4616 Debug.Assert( op != 0 );
4617 testcase( op == OP_Rewind );
4618 testcase( op == OP_Last );
4619 testcase( op == OP_SeekGt );
4620 testcase( op == OP_SeekGe );
4621 testcase( op == OP_SeekLe );
4622 testcase( op == OP_SeekLt );
4623 sqlite3VdbeAddOp4Int( v, op, iIdxCur, addrNxt, regBase, nConstraint );
4624  
4625 /* Load the value for the inequality constraint at the end of the
4626 ** range (if any).
4627 */
4628 nConstraint = nEq;
4629 if ( pRangeEnd != null )
4630 {
4631 Expr pRight = pRangeEnd.pExpr.pRight;
4632 sqlite3ExprCacheRemove( pParse, regBase + nEq, 1 );
4633 sqlite3ExprCode( pParse, pRight, regBase + nEq );
4634 if ( ( pRangeEnd.wtFlags & TERM_VNULL ) == 0 )
4635 {
4636 sqlite3ExprCodeIsNullJump( v, pRight, regBase + nEq, addrNxt );
4637 }
4638 if ( zEndAff.Length > 0 )
4639 {
4640 if ( sqlite3CompareAffinity( pRight, zEndAff[nEq] ) == SQLITE_AFF_NONE )
4641 {
4642 /* Since the comparison is to be performed with no conversions
4643 ** applied to the operands, set the affinity to apply to pRight to
4644 ** SQLITE_AFF_NONE. */
4645 zEndAff[nEq] = SQLITE_AFF_NONE;
4646 }
4647 if ( ( sqlite3ExprNeedsNoAffinityChange( pRight, zEndAff[nEq] ) ) != 0 )
4648 {
4649 zEndAff[nEq] = SQLITE_AFF_NONE;
4650 }
4651 }
4652 codeApplyAffinity( pParse, regBase, nEq + 1, zEndAff.ToString() );
4653 nConstraint++;
4654 testcase( pRangeEnd.wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
4655 }
4656 sqlite3DbFree( pParse.db, ref zStartAff );
4657 sqlite3DbFree( pParse.db, ref zEndAff );
4658  
4659 /* Top of the loop body */
4660 pLevel.p2 = sqlite3VdbeCurrentAddr( v );
4661  
4662 /* Check if the index cursor is past the end of the range. */
4663 op = aEndOp[( ( pRangeEnd != null || nEq != 0 ) ? 1 : 0 ) * ( 1 + bRev )];
4664 testcase( op == OP_Noop );
4665 testcase( op == OP_IdxGE );
4666 testcase( op == OP_IdxLT );
4667 if ( op != OP_Noop )
4668 {
4669 sqlite3VdbeAddOp4Int( v, op, iIdxCur, addrNxt, regBase, nConstraint );
4670 sqlite3VdbeChangeP5( v, (u8)( endEq != bRev ? 1 : 0 ) );
4671 }
4672  
4673 /* If there are inequality constraints, check that the value
4674 ** of the table column that the inequality contrains is not NULL.
4675 ** If it is, jump to the next iteration of the loop.
4676 */
4677 r1 = sqlite3GetTempReg( pParse );
4678 testcase( pLevel.plan.wsFlags & WHERE_BTM_LIMIT );
4679 testcase( pLevel.plan.wsFlags & WHERE_TOP_LIMIT );
4680 if ( ( pLevel.plan.wsFlags & ( WHERE_BTM_LIMIT | WHERE_TOP_LIMIT ) ) != 0 )
4681 {
4682 sqlite3VdbeAddOp3( v, OP_Column, iIdxCur, nEq, r1 );
4683 sqlite3VdbeAddOp2( v, OP_IsNull, r1, addrCont );
4684 }
4685 sqlite3ReleaseTempReg( pParse, r1 );
4686  
4687 /* Seek the table cursor, if required */
4688 disableTerm( pLevel, pRangeStart );
4689 disableTerm( pLevel, pRangeEnd );
4690 if ( 0 == omitTable )
4691 {
4692 iRowidReg = iReleaseReg = sqlite3GetTempReg( pParse );
4693 sqlite3VdbeAddOp2( v, OP_IdxRowid, iIdxCur, iRowidReg );
4694 sqlite3ExprCacheStore( pParse, iCur, -1, iRowidReg );
4695 sqlite3VdbeAddOp2( v, OP_Seek, iCur, iRowidReg ); /* Deferred seek */
4696 }
4697  
4698 /* Record the instruction used to terminate the loop. Disable
4699 ** WHERE clause terms made redundant by the index range scan.
4700 */
4701 if ( ( pLevel.plan.wsFlags & WHERE_UNIQUE ) != 0 )
4702 {
4703 pLevel.op = OP_Noop;
4704 }
4705 else if ( bRev != 0 )
4706 {
4707 pLevel.op = OP_Prev;
4708 }
4709 else
4710 {
4711 pLevel.op = OP_Next;
4712 }
4713 pLevel.p1 = iIdxCur;
4714 }
4715 else
4716  
4717 #if !SQLITE_OMIT_OR_OPTIMIZATION
4718 if ( ( pLevel.plan.wsFlags & WHERE_MULTI_OR ) != 0 )
4719 {
4720 /* Case 4: Two or more separately indexed terms connected by OR
4721 **
4722 ** Example:
4723 **
4724 ** CREATE TABLE t1(a,b,c,d);
4725 ** CREATE INDEX i1 ON t1(a);
4726 ** CREATE INDEX i2 ON t1(b);
4727 ** CREATE INDEX i3 ON t1(c);
4728 **
4729 ** SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
4730 **
4731 ** In the example, there are three indexed terms connected by OR.
4732 ** The top of the loop looks like this:
4733 **
4734 ** Null 1 # Zero the rowset in reg 1
4735 **
4736 ** Then, for each indexed term, the following. The arguments to
4737 ** RowSetTest are such that the rowid of the current row is inserted
4738 ** into the RowSet. If it is already present, control skips the
4739 ** Gosub opcode and jumps straight to the code generated by WhereEnd().
4740 **
4741 ** sqlite3WhereBegin(<term>)
4742 ** RowSetTest # Insert rowid into rowset
4743 ** Gosub 2 A
4744 ** sqlite3WhereEnd()
4745 **
4746 ** Following the above, code to terminate the loop. Label A, the target
4747 ** of the Gosub above, jumps to the instruction right after the Goto.
4748 **
4749 ** Null 1 # Zero the rowset in reg 1
4750 ** Goto B # The loop is finished.
4751 **
4752 ** A: <loop body> # Return data, whatever.
4753 **
4754 ** Return 2 # Jump back to the Gosub
4755 **
4756 ** B: <after the loop>
4757 **
4758 */
4759 WhereClause pOrWc; /* The OR-clause broken out into subterms */
4760 SrcList pOrTab; /* Shortened table list or OR-clause generation */
4761  
4762 int regReturn = ++pParse.nMem; /* Register used with OP_Gosub */
4763 int regRowset = 0; /* Register for RowSet object */
4764 int regRowid = 0; /* Register holding rowid */
4765 int iLoopBody = sqlite3VdbeMakeLabel( v );/* Start of loop body */
4766 int iRetInit; /* Address of regReturn init */
4767 int untestedTerms = 0; /* Some terms not completely tested */
4768 int ii;
4769 pTerm = pLevel.plan.u.pTerm;
4770 Debug.Assert( pTerm != null );
4771 Debug.Assert( pTerm.eOperator == WO_OR );
4772 Debug.Assert( ( pTerm.wtFlags & TERM_ORINFO ) != 0 );
4773 pOrWc = pTerm.u.pOrInfo.wc;
4774 pLevel.op = OP_Return;
4775 pLevel.p1 = regReturn;
4776  
4777 /* Set up a new SrcList in pOrTab containing the table being scanned
4778 ** by this loop in the a[0] slot and all notReady tables in a[1..] slots.
4779 ** This becomes the SrcList in the recursive call to sqlite3WhereBegin().
4780 */
4781 if ( pWInfo.nLevel > 1 )
4782 {
4783 int nNotReady; /* The number of notReady tables */
4784 SrcList_item[] origSrc; /* Original list of tables */
4785 nNotReady = pWInfo.nLevel - iLevel - 1;
4786 //sqlite3StackAllocRaw(pParse.db,
4787 //sizeof(*pOrTab)+ nNotReady*sizeof(pOrTab.a[0]));
4788 pOrTab = new SrcList();
4789 pOrTab.a = new SrcList_item[nNotReady + 1];
4790 //if( pOrTab==0 ) return notReady;
4791 pOrTab.nAlloc = (i16)( nNotReady + 1 );
4792 pOrTab.nSrc = pOrTab.nAlloc;
4793 pOrTab.a[0] = pTabItem;//memcpy(pOrTab.a, pTabItem, sizeof(*pTabItem));
4794 origSrc = pWInfo.pTabList.a;
4795 for ( k = 1; k <= nNotReady; k++ )
4796 {
4797 pOrTab.a[k] = origSrc[pWInfo.a[iLevel + k].iFrom];// memcpy(&pOrTab.a[k], &origSrc[pLevel[k].iFrom], sizeof(pOrTab.a[k]));
4798 }
4799 }
4800 else
4801 {
4802 pOrTab = pWInfo.pTabList;
4803 }
4804  
4805 /* Initialize the rowset register to contain NULL. An SQL NULL is
4806 ** equivalent to an empty rowset.
4807 **
4808 ** Also initialize regReturn to contain the address of the instruction
4809 ** immediately following the OP_Return at the bottom of the loop. This
4810 ** is required in a few obscure LEFT JOIN cases where control jumps
4811 ** over the top of the loop into the body of it. In this case the
4812 ** correct response for the end-of-loop code (the OP_Return) is to
4813 ** fall through to the next instruction, just as an OP_Next does if
4814 ** called on an uninitialized cursor.
4815 */
4816 if ( ( wctrlFlags & WHERE_DUPLICATES_OK ) == 0 )
4817 {
4818 regRowset = ++pParse.nMem;
4819 regRowid = ++pParse.nMem;
4820 sqlite3VdbeAddOp2( v, OP_Null, 0, regRowset );
4821 }
4822 iRetInit = sqlite3VdbeAddOp2( v, OP_Integer, 0, regReturn );
4823  
4824 for ( ii = 0; ii < pOrWc.nTerm; ii++ )
4825 {
4826 WhereTerm pOrTerm = pOrWc.a[ii];
4827 if ( pOrTerm.leftCursor == iCur || pOrTerm.eOperator == WO_AND )
4828 {
4829 WhereInfo pSubWInfo; /* Info for single OR-term scan */
4830  
4831 /* Loop through table entries that match term pOrTerm. */
4832 ExprList elDummy = null;
4833 pSubWInfo = sqlite3WhereBegin( pParse, pOrTab, pOrTerm.pExpr, ref elDummy,
4834 WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE |
4835 WHERE_FORCE_TABLE | WHERE_ONETABLE_ONLY );
4836 if ( pSubWInfo != null )
4837 {
4838 explainOneScan(
4839 pParse, pOrTab, pSubWInfo.a[0], iLevel, pLevel.iFrom, 0
4840 );
4841 if ( ( wctrlFlags & WHERE_DUPLICATES_OK ) == 0 )
4842 {
4843 int iSet = ( ( ii == pOrWc.nTerm - 1 ) ? -1 : ii );
4844 int r;
4845 r = sqlite3ExprCodeGetColumn( pParse, pTabItem.pTab, -1, iCur,
4846 regRowid );
4847 sqlite3VdbeAddOp4Int( v, OP_RowSetTest, regRowset,
4848 sqlite3VdbeCurrentAddr( v ) + 2, r, iSet );
4849 }
4850 sqlite3VdbeAddOp2( v, OP_Gosub, regReturn, iLoopBody );
4851  
4852 /* The pSubWInfo.untestedTerms flag means that this OR term
4853 ** contained one or more AND term from a notReady table. The
4854 ** terms from the notReady table could not be tested and will
4855 ** need to be tested later.
4856 */
4857 if ( pSubWInfo.untestedTerms != 0 )
4858 untestedTerms = 1;
4859  
4860 /* Finish the loop through table entries that match term pOrTerm. */
4861 sqlite3WhereEnd( pSubWInfo );
4862 }
4863 }
4864 }
4865 sqlite3VdbeChangeP1( v, iRetInit, sqlite3VdbeCurrentAddr( v ) );
4866 sqlite3VdbeAddOp2( v, OP_Goto, 0, pLevel.addrBrk );
4867 sqlite3VdbeResolveLabel( v, iLoopBody );
4868  
4869 if ( pWInfo.nLevel > 1 )
4870 sqlite3DbFree( pParse.db, ref pOrTab );//sqlite3DbFree(pParse.db, pOrTab)
4871 if ( 0 == untestedTerms )
4872 disableTerm( pLevel, pTerm );
4873 }
4874 else
4875 #endif //* SQLITE_OMIT_OR_OPTIMIZATION */
4876  
4877 {
4878 /* Case 5: There is no usable index. We must do a complete
4879 ** scan of the entire table.
4880 */
4881 u8[] aStep = new u8[] { OP_Next, OP_Prev };
4882 u8[] aStart = new u8[] { OP_Rewind, OP_Last };
4883 Debug.Assert( bRev == 0 || bRev == 1 );
4884 Debug.Assert( omitTable == 0 );
4885 pLevel.op = aStep[bRev];
4886 pLevel.p1 = iCur;
4887 pLevel.p2 = 1 + sqlite3VdbeAddOp2( v, aStart[bRev], iCur, addrBrk );
4888 pLevel.p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
4889 }
4890 notReady &= ~getMask( pWC.pMaskSet, iCur );
4891  
4892 /* Insert code to test every subexpression that can be completely
4893 ** computed using the current set of tables.
4894 **
4895 ** IMPLEMENTATION-OF: R-49525-50935 Terms that cannot be satisfied through
4896 ** the use of indices become tests that are evaluated against each row of
4897 ** the relevant input tables.
4898 */
4899 for ( j = pWC.nTerm; j > 0; j-- )//, pTerm++)
4900 {
4901 pTerm = pWC.a[pWC.nTerm - j];
4902 Expr pE;
4903 testcase( pTerm.wtFlags & TERM_VIRTUAL ); /* IMP: R-30575-11662 */
4904 testcase( pTerm.wtFlags & TERM_CODED );
4905 if ( ( pTerm.wtFlags & ( TERM_VIRTUAL | TERM_CODED ) ) != 0 )
4906 continue;
4907 if ( ( pTerm.prereqAll & notReady ) != 0 )
4908 {
4909 testcase( pWInfo.untestedTerms == 0
4910 && ( pWInfo.wctrlFlags & WHERE_ONETABLE_ONLY ) != 0 );
4911 pWInfo.untestedTerms = 1;
4912 continue;
4913 }
4914 pE = pTerm.pExpr;
4915 Debug.Assert( pE != null );
4916 if ( pLevel.iLeftJoin != 0 && !( ( pE.flags & EP_FromJoin ) == EP_FromJoin ) )// !ExprHasProperty(pE, EP_FromJoin) ){
4917 {
4918 continue;
4919 }
4920 sqlite3ExprIfFalse( pParse, pE, addrCont, SQLITE_JUMPIFNULL );
4921 pTerm.wtFlags |= TERM_CODED;
4922 }
4923  
4924 /* For a LEFT OUTER JOIN, generate code that will record the fact that
4925 ** at least one row of the right table has matched the left table.
4926 */
4927 if ( pLevel.iLeftJoin != 0 )
4928 {
4929 pLevel.addrFirst = sqlite3VdbeCurrentAddr( v );
4930 sqlite3VdbeAddOp2( v, OP_Integer, 1, pLevel.iLeftJoin );
4931 #if SQLITE_DEBUG
4932 VdbeComment( v, "record LEFT JOIN hit" );
4933 #endif
4934 sqlite3ExprCacheClear( pParse );
4935 for ( j = 0; j < pWC.nTerm; j++ )//, pTerm++)
4936 {
4937 pTerm = pWC.a[j];
4938 testcase( pTerm.wtFlags & TERM_VIRTUAL ); /* IMP: R-30575-11662 */
4939 testcase( pTerm.wtFlags & TERM_CODED );
4940 if ( ( pTerm.wtFlags & ( TERM_VIRTUAL | TERM_CODED ) ) != 0 )
4941 continue;
4942 if ( ( pTerm.prereqAll & notReady ) != 0 )
4943 {
4944 Debug.Assert( pWInfo.untestedTerms != 0 );
4945 continue;
4946 }
4947 Debug.Assert( pTerm.pExpr != null );
4948 sqlite3ExprIfFalse( pParse, pTerm.pExpr, addrCont, SQLITE_JUMPIFNULL );
4949 pTerm.wtFlags |= TERM_CODED;
4950 }
4951 }
4952  
4953 sqlite3ReleaseTempReg( pParse, iReleaseReg );
4954 return notReady;
4955 }
4956  
4957 #if (SQLITE_TEST)
4958 /*
4959 ** The following variable holds a text description of query plan generated
4960 ** by the most recent call to sqlite3WhereBegin(). Each call to WhereBegin
4961 ** overwrites the previous. This information is used for testing and
4962 ** analysis only.
4963 */
4964 #if !TCLSH
4965 //char sqlite3_query_plan[BMS*2*40]; /* Text of the join */
4966 static StringBuilder sqlite3_query_plan;
4967 #else
4968 static tcl.lang.Var.SQLITE3_GETSET sqlite3_query_plan = new tcl.lang.Var.SQLITE3_GETSET( "sqlite3_query_plan" );
4969 #endif
4970 static int nQPlan = 0; /* Next free slow in _query_plan[] */
4971  
4972 #endif //* SQLITE_TEST */
4973  
4974  
4975 /*
4976 ** Free a WhereInfo structure
4977 */
4978 static void whereInfoFree( sqlite3 db, WhereInfo pWInfo )
4979 {
4980 if ( ALWAYS( pWInfo != null ) )
4981 {
4982 int i;
4983 for ( i = 0; i < pWInfo.nLevel; i++ )
4984 {
4985 sqlite3_index_info pInfo = pWInfo.a[i] != null ? pWInfo.a[i].pIdxInfo : null;
4986 if ( pInfo != null )
4987 {
4988 /* Debug.Assert( pInfo.needToFreeIdxStr==0 || db.mallocFailed ); */
4989 if ( pInfo.needToFreeIdxStr != 0 )
4990 {
4991 //sqlite3_free( ref pInfo.idxStr );
4992 }
4993 sqlite3DbFree( db, ref pInfo );
4994 }
4995 if ( pWInfo.a[i] != null && ( pWInfo.a[i].plan.wsFlags & WHERE_TEMP_INDEX ) != 0 )
4996 {
4997 Index pIdx = pWInfo.a[i].plan.u.pIdx;
4998 if ( pIdx != null )
4999 {
5000 sqlite3DbFree( db, ref pIdx.zColAff );
5001 sqlite3DbFree( db, ref pIdx );
5002 }
5003 }
5004 }
5005 whereClauseClear( pWInfo.pWC );
5006 sqlite3DbFree( db, ref pWInfo );
5007 }
5008 }
5009  
5010  
5011 /*
5012 ** Generate the beginning of the loop used for WHERE clause processing.
5013 ** The return value is a pointer to an opaque structure that contains
5014 ** information needed to terminate the loop. Later, the calling routine
5015 ** should invoke sqlite3WhereEnd() with the return value of this function
5016 ** in order to complete the WHERE clause processing.
5017 **
5018 ** If an error occurs, this routine returns NULL.
5019 **
5020 ** The basic idea is to do a nested loop, one loop for each table in
5021 ** the FROM clause of a select. (INSERT and UPDATE statements are the
5022 ** same as a SELECT with only a single table in the FROM clause.) For
5023 ** example, if the SQL is this:
5024 **
5025 ** SELECT * FROM t1, t2, t3 WHERE ...;
5026 **
5027 ** Then the code generated is conceptually like the following:
5028 **
5029 ** foreach row1 in t1 do \ Code generated
5030 ** foreach row2 in t2 do |-- by sqlite3WhereBegin()
5031 ** foreach row3 in t3 do /
5032 ** ...
5033 ** end \ Code generated
5034 ** end |-- by sqlite3WhereEnd()
5035 ** end /
5036 **
5037 ** Note that the loops might not be nested in the order in which they
5038 ** appear in the FROM clause if a different order is better able to make
5039 ** use of indices. Note also that when the IN operator appears in
5040 ** the WHERE clause, it might result in additional nested loops for
5041 ** scanning through all values on the right-hand side of the IN.
5042 **
5043 ** There are Btree cursors Debug.Associated with each table. t1 uses cursor
5044 ** number pTabList.a[0].iCursor. t2 uses the cursor pTabList.a[1].iCursor.
5045 ** And so forth. This routine generates code to open those VDBE cursors
5046 ** and sqlite3WhereEnd() generates the code to close them.
5047 **
5048 ** The code that sqlite3WhereBegin() generates leaves the cursors named
5049 ** in pTabList pointing at their appropriate entries. The [...] code
5050 ** can use OP_Column and OP_Rowid opcodes on these cursors to extract
5051 ** data from the various tables of the loop.
5052 **
5053 ** If the WHERE clause is empty, the foreach loops must each scan their
5054 ** entire tables. Thus a three-way join is an O(N^3) operation. But if
5055 ** the tables have indices and there are terms in the WHERE clause that
5056 ** refer to those indices, a complete table scan can be avoided and the
5057 ** code will run much faster. Most of the work of this routine is checking
5058 ** to see if there are indices that can be used to speed up the loop.
5059 **
5060 ** Terms of the WHERE clause are also used to limit which rows actually
5061 ** make it to the "..." in the middle of the loop. After each "foreach",
5062 ** terms of the WHERE clause that use only terms in that loop and outer
5063 ** loops are evaluated and if false a jump is made around all subsequent
5064 ** inner loops (or around the "..." if the test occurs within the inner-
5065 ** most loop)
5066 **
5067 ** OUTER JOINS
5068 **
5069 ** An outer join of tables t1 and t2 is conceptally coded as follows:
5070 **
5071 ** foreach row1 in t1 do
5072 ** flag = 0
5073 ** foreach row2 in t2 do
5074 ** start:
5075 ** ...
5076 ** flag = 1
5077 ** end
5078 ** if flag==null then
5079 ** move the row2 cursor to a null row
5080 ** goto start
5081 ** fi
5082 ** end
5083 **
5084 ** ORDER BY CLAUSE PROCESSING
5085 **
5086 ** ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
5087 ** if there is one. If there is no ORDER BY clause or if this routine
5088 ** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.
5089 **
5090 ** If an index can be used so that the natural output order of the table
5091 ** scan is correct for the ORDER BY clause, then that index is used and
5092 ** ppOrderBy is set to NULL. This is an optimization that prevents an
5093 ** unnecessary sort of the result set if an index appropriate for the
5094 ** ORDER BY clause already exists.
5095 **
5096 ** If the where clause loops cannot be arranged to provide the correct
5097 ** output order, then the ppOrderBy is unchanged.
5098 */
5099 static WhereInfo sqlite3WhereBegin(
5100 Parse pParse, /* The parser context */
5101 SrcList pTabList, /* A list of all tables to be scanned */
5102 Expr pWhere, /* The WHERE clause */
5103 ref ExprList ppOrderBy, /* An ORDER BY clause, or NULL */
5104 u16 wctrlFlags /* One of the WHERE_* flags defined in sqliteInt.h */
5105 )
5106 {
5107 int i; /* Loop counter */
5108 int nByteWInfo; /* Num. bytes allocated for WhereInfo struct */
5109 int nTabList; /* Number of elements in pTabList */
5110 WhereInfo pWInfo; /* Will become the return value of this function */
5111 Vdbe v = pParse.pVdbe; /* The virtual data_base engine */
5112 Bitmask notReady; /* Cursors that are not yet positioned */
5113 WhereMaskSet pMaskSet; /* The expression mask set */
5114 WhereClause pWC = new WhereClause(); /* Decomposition of the WHERE clause */
5115 SrcList_item pTabItem; /* A single entry from pTabList */
5116 WhereLevel pLevel; /* A single level in the pWInfo list */
5117 int iFrom; /* First unused FROM clause element */
5118 int andFlags; /* AND-ed combination of all pWC.a[].wtFlags */
5119 sqlite3 db; /* Data_base connection */
5120  
5121 /* The number of tables in the FROM clause is limited by the number of
5122 ** bits in a Bitmask
5123 */
5124 testcase( pTabList.nSrc == BMS );
5125 if ( pTabList.nSrc > BMS )
5126 {
5127 sqlite3ErrorMsg( pParse, "at most %d tables in a join", BMS );
5128 return null;
5129 }
5130  
5131 /* This function normally generates a nested loop for all tables in
5132 ** pTabList. But if the WHERE_ONETABLE_ONLY flag is set, then we should
5133 ** only generate code for the first table in pTabList and assume that
5134 ** any cursors associated with subsequent tables are uninitialized.
5135 */
5136 nTabList = ( ( wctrlFlags & WHERE_ONETABLE_ONLY ) != 0 ) ? 1 : (int)pTabList.nSrc;
5137  
5138 /* Allocate and initialize the WhereInfo structure that will become the
5139 ** return value. A single allocation is used to store the WhereInfo
5140 ** struct, the contents of WhereInfo.a[], the WhereClause structure
5141 ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
5142 ** field (type Bitmask) it must be aligned on an 8-byte boundary on
5143 ** some architectures. Hence the ROUND8() below.
5144 */
5145 db = pParse.db;
5146 pWInfo = new WhereInfo();
5147 //nByteWInfo = ROUND8(sizeof(WhereInfo)+(nTabList-1)*sizeof(WhereLevel));
5148 //pWInfo = sqlite3DbMallocZero( db,
5149 // nByteWInfo +
5150 // sizeof( WhereClause ) +
5151 // sizeof( WhereMaskSet )
5152 //);
5153 pWInfo.a = new WhereLevel[pTabList.nSrc];
5154 for ( int ai = 0; ai < pWInfo.a.Length; ai++ )
5155 {
5156 pWInfo.a[ai] = new WhereLevel();
5157 }
5158 //if ( db.mallocFailed != 0 )
5159 //{
5160 //sqlite3DbFree(db, pWInfo);
5161 //pWInfo = 0;
5162 // goto whereBeginError;
5163 //}
5164 pWInfo.nLevel = nTabList;
5165 pWInfo.pParse = pParse;
5166 pWInfo.pTabList = pTabList;
5167 pWInfo.iBreak = sqlite3VdbeMakeLabel( v );
5168 pWInfo.pWC = pWC = new WhereClause();// (WhereClause )((u8 )pWInfo)[nByteWInfo];
5169 pWInfo.wctrlFlags = wctrlFlags;
5170 pWInfo.savedNQueryLoop = pParse.nQueryLoop;
5171 //pMaskSet = (WhereMaskSet)pWC[1];
5172  
5173 /* Split the WHERE clause into separate subexpressions where each
5174 ** subexpression is separated by an AND operator.
5175 */
5176 pMaskSet = new WhereMaskSet();//initMaskSet(pMaskSet);
5177 whereClauseInit( pWC, pParse, pMaskSet );
5178 sqlite3ExprCodeConstants( pParse, pWhere );
5179 whereSplit( pWC, pWhere, TK_AND ); /* IMP: R-15842-53296 */
5180  
5181 /* Special case: a WHERE clause that is constant. Evaluate the
5182 ** expression and either jump over all of the code or fall thru.
5183 */
5184 if ( pWhere != null && ( nTabList == 0 || sqlite3ExprIsConstantNotJoin( pWhere ) != 0 ) )
5185 {
5186 sqlite3ExprIfFalse( pParse, pWhere, pWInfo.iBreak, SQLITE_JUMPIFNULL );
5187 pWhere = null;
5188 }
5189  
5190 /* Assign a bit from the bitmask to every term in the FROM clause.
5191 **
5192 ** When assigning bitmask values to FROM clause cursors, it must be
5193 ** the case that if X is the bitmask for the N-th FROM clause term then
5194 ** the bitmask for all FROM clause terms to the left of the N-th term
5195 ** is (X-1). An expression from the ON clause of a LEFT JOIN can use
5196 ** its Expr.iRightJoinTable value to find the bitmask of the right table
5197 ** of the join. Subtracting one from the right table bitmask gives a
5198 ** bitmask for all tables to the left of the join. Knowing the bitmask
5199 ** for all tables to the left of a left join is important. Ticket #3015.
5200 **
5201 ** Configure the WhereClause.vmask variable so that bits that correspond
5202 ** to virtual table cursors are set. This is used to selectively disable
5203 ** the OR-to-IN transformation in exprAnalyzeOrTerm(). It is not helpful
5204 ** with virtual tables.
5205 **
5206 ** Note that bitmasks are created for all pTabList.nSrc tables in
5207 ** pTabList, not just the first nTabList tables. nTabList is normally
5208 ** equal to pTabList.nSrc but might be shortened to 1 if the
5209 ** WHERE_ONETABLE_ONLY flag is set.
5210 */
5211 Debug.Assert( pWC.vmask == 0 && pMaskSet.n == 0 );
5212 for ( i = 0; i < pTabList.nSrc; i++ )
5213 {
5214 createMask( pMaskSet, pTabList.a[i].iCursor );
5215 #if !SQLITE_OMIT_VIRTUALTABLE
5216 if ( ALWAYS( pTabList.a[i].pTab ) && IsVirtual( pTabList.a[i].pTab ) )
5217 {
5218 pWC.vmask |= ( (Bitmask)1 << i );
5219 }
5220 #endif
5221 }
5222 #if !NDEBUG
5223 {
5224 Bitmask toTheLeft = 0;
5225 for ( i = 0; i < pTabList.nSrc; i++ )
5226 {
5227 Bitmask m = getMask( pMaskSet, pTabList.a[i].iCursor );
5228 Debug.Assert( ( m - 1 ) == toTheLeft );
5229 toTheLeft |= m;
5230 }
5231 }
5232 #endif
5233  
5234 /* Analyze all of the subexpressions. Note that exprAnalyze() might
5235 ** add new virtual terms onto the end of the WHERE clause. We do not
5236 ** want to analyze these virtual terms, so start analyzing at the end
5237 ** and work forward so that the added virtual terms are never processed.
5238 */
5239 exprAnalyzeAll( pTabList, pWC );
5240 //if ( db.mallocFailed != 0 )
5241 //{
5242 // goto whereBeginError;
5243 //}
5244  
5245 /* Chose the best index to use for each table in the FROM clause.
5246 **
5247 ** This loop fills in the following fields:
5248 **
5249 ** pWInfo.a[].pIdx The index to use for this level of the loop.
5250 ** pWInfo.a[].wsFlags WHERE_xxx flags Debug.Associated with pIdx
5251 ** pWInfo.a[].nEq The number of == and IN constraints
5252 ** pWInfo.a[].iFrom Which term of the FROM clause is being coded
5253 ** pWInfo.a[].iTabCur The VDBE cursor for the data_base table
5254 ** pWInfo.a[].iIdxCur The VDBE cursor for the index
5255 ** pWInfo.a[].pTerm When wsFlags==WO_OR, the OR-clause term
5256 **
5257 ** This loop also figures out the nesting order of tables in the FROM
5258 ** clause.
5259 */
5260 notReady = ~(Bitmask)0;
5261 andFlags = ~0;
5262 #if (SQLITE_TEST) && (SQLITE_DEBUG)
5263 WHERETRACE( "*** Optimizer Start ***\n" );
5264 #endif
5265 for ( i = iFrom = 0; i < nTabList; i++ )//, pLevel++ )
5266 {
5267 pLevel = pWInfo.a[i];
5268 WhereCost bestPlan; /* Most efficient plan seen so far */
5269 Index pIdx; /* Index for FROM table at pTabItem */
5270 int j; /* For looping over FROM tables */
5271 int bestJ = -1; /* The value of j */
5272 Bitmask m; /* Bitmask value for j or bestJ */
5273 int isOptimal; /* Iterator for optimal/non-optimal search */
5274 int nUnconstrained; /* Number tables without INDEXED BY */
5275 Bitmask notIndexed; /* Mask of tables that cannot use an index */
5276  
5277 bestPlan = new WhereCost();// memset( &bestPlan, 0, sizeof( bestPlan ) );
5278 bestPlan.rCost = SQLITE_BIG_DBL;
5279 #if (SQLITE_TEST) && (SQLITE_DEBUG)
5280 WHERETRACE( "*** Begin search for loop %d ***\n", i );
5281 #endif
5282  
5283 /* Loop through the remaining entries in the FROM clause to find the
5284 ** next nested loop. The loop tests all FROM clause entries
5285 ** either once or twice.
5286 **
5287 ** The first test is always performed if there are two or more entries
5288 ** remaining and never performed if there is only one FROM clause entry
5289 ** to choose from. The first test looks for an "optimal" scan. In
5290 ** this context an optimal scan is one that uses the same strategy
5291 ** for the given FROM clause entry as would be selected if the entry
5292 ** were used as the innermost nested loop. In other words, a table
5293 ** is chosen such that the cost of running that table cannot be reduced
5294 ** by waiting for other tables to run first. This "optimal" test works
5295 ** by first assuming that the FROM clause is on the inner loop and finding
5296 ** its query plan, then checking to see if that query plan uses any
5297 ** other FROM clause terms that are notReady. If no notReady terms are
5298 ** used then the "optimal" query plan works.
5299 **
5300 ** Note that the WhereCost.nRow parameter for an optimal scan might
5301 ** not be as small as it would be if the table really were the innermost
5302 ** join. The nRow value can be reduced by WHERE clause constraints
5303 ** that do not use indices. But this nRow reduction only happens if the
5304 ** table really is the innermost join.
5305 **
5306 ** The second loop iteration is only performed if no optimal scan
5307 ** strategies were found by the first iteration. This second iteration
5308 ** is used to search for the lowest cost scan overall.
5309 **
5310 ** Previous versions of SQLite performed only the second iteration -
5311 ** the next outermost loop was always that with the lowest overall
5312 ** cost. However, this meant that SQLite could select the wrong plan
5313 ** for scripts such as the following:
5314 **
5315 ** CREATE TABLE t1(a, b);
5316 ** CREATE TABLE t2(c, d);
5317 ** SELECT * FROM t2, t1 WHERE t2.rowid = t1.a;
5318 **
5319 ** The best strategy is to iterate through table t1 first. However it
5320 ** is not possible to determine this with a simple greedy algorithm.
5321 ** Since the cost of a linear scan through table t2 is the same
5322 ** as the cost of a linear scan through table t1, a simple greedy
5323 ** algorithm may choose to use t2 for the outer loop, which is a much
5324 ** costlier approach.
5325 */
5326 nUnconstrained = 0;
5327 notIndexed = 0;
5328 for ( isOptimal = ( iFrom < nTabList - 1 ) ? 1 : 0; isOptimal >= 0 && bestJ < 0; isOptimal-- )
5329 {
5330 Bitmask mask; /* Mask of tables not yet ready */
5331 for ( j = iFrom; j < nTabList; j++ )//, pTabItem++)
5332 {
5333 pTabItem = pTabList.a[j];
5334 int doNotReorder; /* True if this table should not be reordered */
5335 WhereCost sCost = new WhereCost(); /* Cost information from best[Virtual]Index() */
5336 ExprList pOrderBy; /* ORDER BY clause for index to optimize */
5337  
5338 doNotReorder = ( pTabItem.jointype & ( JT_LEFT | JT_CROSS ) ) != 0 ? 1 : 0;
5339 if ( ( j != iFrom && doNotReorder != 0 ) )
5340 break;
5341 m = getMask( pMaskSet, pTabItem.iCursor );
5342 if ( ( m & notReady ) == 0 )
5343 {
5344 if ( j == iFrom )
5345 iFrom++;
5346 continue;
5347 }
5348 mask = ( isOptimal != 0 ? m : notReady );
5349 pOrderBy = ( ( i == 0 && ppOrderBy != null ) ? ppOrderBy : null );
5350 if ( pTabItem.pIndex == null )
5351 nUnconstrained++;
5352  
5353 #if (SQLITE_TEST) && (SQLITE_DEBUG)
5354 WHERETRACE( "=== trying table %d with isOptimal=%d ===\n",
5355 j, isOptimal );
5356 #endif
5357 Debug.Assert( pTabItem.pTab != null );
5358 #if !SQLITE_OMIT_VIRTUALTABLE
5359 if ( IsVirtual( pTabItem.pTab ) )
5360 {
5361 sqlite3_index_info pp = pWInfo.a[j].pIdxInfo;
5362 bestVirtualIndex( pParse, pWC, pTabItem, mask, notReady, pOrderBy,
5363 ref sCost, ref pp );
5364 }
5365 else
5366 #endif
5367 {
5368 bestBtreeIndex( pParse, pWC, pTabItem, mask, notReady, pOrderBy,
5369 ref sCost );
5370 }
5371 Debug.Assert( isOptimal != 0 || ( sCost.used & notReady ) == 0 );
5372  
5373 /* If an INDEXED BY clause is present, then the plan must use that
5374 ** index if it uses any index at all */
5375 Debug.Assert( pTabItem.pIndex == null
5376 || ( sCost.plan.wsFlags & WHERE_NOT_FULLSCAN ) == 0
5377 || sCost.plan.u.pIdx == pTabItem.pIndex );
5378  
5379 if ( isOptimal != 0 && ( sCost.plan.wsFlags & WHERE_NOT_FULLSCAN ) == 0 )
5380 {
5381 notIndexed |= m;
5382 }
5383  
5384 /* Conditions under which this table becomes the best so far:
5385 **
5386 ** (1) The table must not depend on other tables that have not
5387 ** yet run.
5388 **
5389 ** (2) A full-table-scan plan cannot supercede indexed plan unless
5390 ** the full-table-scan is an "optimal" plan as defined above.
5391 **
5392 ** (3) All tables have an INDEXED BY clause or this table lacks an
5393 ** INDEXED BY clause or this table uses the specific
5394 ** index specified by its INDEXED BY clause. This rule ensures
5395 ** that a best-so-far is always selected even if an impossible
5396 ** combination of INDEXED BY clauses are given. The error
5397 ** will be detected and relayed back to the application later.
5398 ** The NEVER() comes about because rule (2) above prevents
5399 ** An indexable full-table-scan from reaching rule (3).
5400 **
5401 ** (4) The plan cost must be lower than prior plans or else the
5402 ** cost must be the same and the number of rows must be lower.
5403 */
5404 if ( ( sCost.used & notReady ) == 0 /* (1) */
5405 && ( bestJ < 0 || ( notIndexed & m ) != 0 /* (2) */
5406 || ( bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN ) == 0
5407 || ( sCost.plan.wsFlags & WHERE_NOT_FULLSCAN ) != 0 )
5408 && ( nUnconstrained == 0 || pTabItem.pIndex == null /* (3) */
5409 || NEVER( ( sCost.plan.wsFlags & WHERE_NOT_FULLSCAN ) != 0 ) )
5410 && ( bestJ < 0 || sCost.rCost < bestPlan.rCost /* (4) */
5411 || ( sCost.rCost <= bestPlan.rCost
5412 && sCost.plan.nRow < bestPlan.plan.nRow ) )
5413 )
5414 {
5415 #if (SQLITE_TEST) && (SQLITE_DEBUG)
5416 WHERETRACE( "=== table %d is best so far" +
5417 " with cost=%g and nRow=%g\n",
5418 j, sCost.rCost, sCost.plan.nRow );
5419 #endif
5420 bestPlan = sCost;
5421 bestJ = j;
5422 }
5423 if ( doNotReorder != 0 )
5424 break;
5425 }
5426 }
5427 Debug.Assert( bestJ >= 0 );
5428 Debug.Assert( ( notReady & getMask( pMaskSet, pTabList.a[bestJ].iCursor ) ) != 0 );
5429 #if (SQLITE_TEST) && (SQLITE_DEBUG)
5430 WHERETRACE( "*** Optimizer selects table %d for loop %d" +
5431 " with cost=%g and nRow=%g\n",
5432 bestJ, i,//pLevel-pWInfo.a,
5433 bestPlan.rCost, bestPlan.plan.nRow );
5434 #endif
5435 if ( ( bestPlan.plan.wsFlags & WHERE_ORDERBY ) != 0 )
5436 {
5437 ppOrderBy = null;
5438 }
5439 andFlags = (int)( andFlags & bestPlan.plan.wsFlags );
5440 pLevel.plan = bestPlan.plan;
5441 testcase( bestPlan.plan.wsFlags & WHERE_INDEXED );
5442 testcase( bestPlan.plan.wsFlags & WHERE_TEMP_INDEX );
5443 if ( ( bestPlan.plan.wsFlags & ( WHERE_INDEXED | WHERE_TEMP_INDEX ) ) != 0 )
5444 {
5445 pLevel.iIdxCur = pParse.nTab++;
5446 }
5447 else
5448 {
5449 pLevel.iIdxCur = -1;
5450 }
5451 notReady &= ~getMask( pMaskSet, pTabList.a[bestJ].iCursor );
5452 pLevel.iFrom = (u8)bestJ;
5453 if ( bestPlan.plan.nRow >= (double)1 )
5454 {
5455 pParse.nQueryLoop *= bestPlan.plan.nRow;
5456 }
5457  
5458 /* Check that if the table scanned by this loop iteration had an
5459 ** INDEXED BY clause attached to it, that the named index is being
5460 ** used for the scan. If not, then query compilation has failed.
5461 ** Return an error.
5462 */
5463 pIdx = pTabList.a[bestJ].pIndex;
5464 if ( pIdx != null )
5465 {
5466 if ( ( bestPlan.plan.wsFlags & WHERE_INDEXED ) == 0 )
5467 {
5468 sqlite3ErrorMsg( pParse, "cannot use index: %s", pIdx.zName );
5469 goto whereBeginError;
5470 }
5471 else
5472 {
5473 /* If an INDEXED BY clause is used, the bestIndex() function is
5474 ** guaranteed to find the index specified in the INDEXED BY clause
5475 ** if it find an index at all. */
5476 Debug.Assert( bestPlan.plan.u.pIdx == pIdx );
5477 }
5478 }
5479 }
5480 #if (SQLITE_TEST) && (SQLITE_DEBUG)
5481 WHERETRACE( "*** Optimizer Finished ***\n" );
5482 #endif
5483 if ( pParse.nErr != 0 /*|| db.mallocFailed != 0 */ )
5484 {
5485 goto whereBeginError;
5486 }
5487  
5488 /* If the total query only selects a single row, then the ORDER BY
5489 ** clause is irrelevant.
5490 */
5491 if ( ( andFlags & WHERE_UNIQUE ) != 0 && ppOrderBy != null )
5492 {
5493 ppOrderBy = null;
5494 }
5495  
5496 /* If the caller is an UPDATE or DELETE statement that is requesting
5497 ** to use a one-pDebug.Ass algorithm, determine if this is appropriate.
5498 ** The one-pass algorithm only works if the WHERE clause constraints
5499 ** the statement to update a single row.
5500 */
5501 Debug.Assert( ( wctrlFlags & WHERE_ONEPASS_DESIRED ) == 0 || pWInfo.nLevel == 1 );
5502 if ( ( wctrlFlags & WHERE_ONEPASS_DESIRED ) != 0 && ( andFlags & WHERE_UNIQUE ) != 0 )
5503 {
5504 pWInfo.okOnePass = 1;
5505 pWInfo.a[0].plan.wsFlags = (u32)( pWInfo.a[0].plan.wsFlags & ~WHERE_IDX_ONLY );
5506 }
5507  
5508 /* Open all tables in the pTabList and any indices selected for
5509 ** searching those tables.
5510 */
5511 sqlite3CodeVerifySchema( pParse, -1 ); /* Insert the cookie verifier Goto */
5512 notReady = ~(Bitmask)0;
5513 pWInfo.nRowOut = (double)1;
5514 for ( i = 0; i < nTabList; i++ )//, pLevel++ )
5515 {
5516 pLevel = pWInfo.a[i];
5517 Table pTab; /* Table to open */
5518 int iDb; /* Index of data_base containing table/index */
5519  
5520 pTabItem = pTabList.a[pLevel.iFrom];
5521 pTab = pTabItem.pTab;
5522 pLevel.iTabCur = pTabItem.iCursor;
5523 pWInfo.nRowOut *= pLevel.plan.nRow;
5524 iDb = sqlite3SchemaToIndex( db, pTab.pSchema );
5525 if ( ( pTab.tabFlags & TF_Ephemeral ) != 0 || pTab.pSelect != null )
5526 {
5527 /* Do nothing */
5528 }
5529 else
5530 #if !SQLITE_OMIT_VIRTUALTABLE
5531 if ( ( pLevel.plan.wsFlags & WHERE_VIRTUALTABLE ) != 0 )
5532 {
5533 VTable pVTab = sqlite3GetVTable( db, pTab );
5534 int iCur = pTabItem.iCursor;
5535 sqlite3VdbeAddOp4( v, OP_VOpen, iCur, 0, 0,
5536 pVTab, P4_VTAB );
5537 }
5538 else
5539 #endif
5540 if ( ( pLevel.plan.wsFlags & WHERE_IDX_ONLY ) == 0
5541 && ( wctrlFlags & WHERE_OMIT_OPEN ) == 0 )
5542 {
5543 int op = pWInfo.okOnePass != 0 ? OP_OpenWrite : OP_OpenRead;
5544 sqlite3OpenTable( pParse, pTabItem.iCursor, iDb, pTab, op );
5545 testcase( pTab.nCol == BMS - 1 );
5546 testcase( pTab.nCol == BMS );
5547 if ( 0 == pWInfo.okOnePass && pTab.nCol < BMS )
5548 {
5549 Bitmask b = pTabItem.colUsed;
5550 int n = 0;
5551 for ( ; b != 0; b = b >> 1, n++ )
5552 {
5553 }
5554 sqlite3VdbeChangeP4( v, sqlite3VdbeCurrentAddr( v ) - 1,
5555 n, P4_INT32 );//SQLITE_INT_TO_PTR(n)
5556 Debug.Assert( n <= pTab.nCol );
5557 }
5558 }
5559 else
5560 {
5561 sqlite3TableLock( pParse, iDb, pTab.tnum, 0, pTab.zName );
5562 }
5563 #if !SQLITE_OMIT_AUTOMATIC_INDEX
5564 if ( ( pLevel.plan.wsFlags & WHERE_TEMP_INDEX ) != 0 )
5565 {
5566 constructAutomaticIndex( pParse, pWC, pTabItem, notReady, pLevel );
5567 }
5568 else
5569 #endif
5570 if ( ( pLevel.plan.wsFlags & WHERE_INDEXED ) != 0 )
5571 {
5572 Index pIx = pLevel.plan.u.pIdx;
5573 KeyInfo pKey = sqlite3IndexKeyinfo( pParse, pIx );
5574 int iIdxCur = pLevel.iIdxCur;
5575 Debug.Assert( pIx.pSchema == pTab.pSchema );
5576 Debug.Assert( iIdxCur >= 0 );
5577 sqlite3VdbeAddOp4( v, OP_OpenRead, iIdxCur, pIx.tnum, iDb,
5578 pKey, P4_KEYINFO_HANDOFF );
5579 #if SQLITE_DEBUG
5580 VdbeComment( v, "%s", pIx.zName );
5581 #endif
5582 }
5583 sqlite3CodeVerifySchema( pParse, iDb );
5584 notReady &= ~getMask( pWC.pMaskSet, pTabItem.iCursor );
5585 }
5586 pWInfo.iTop = sqlite3VdbeCurrentAddr( v );
5587 //if( db.mallocFailed ) goto whereBeginError;
5588  
5589 /* Generate the code to do the search. Each iteration of the for
5590 ** loop below generates code for a single nested loop of the VM
5591 ** program.
5592 */
5593 notReady = ~(Bitmask)0;
5594 for ( i = 0; i < nTabList; i++ )
5595 {
5596 pLevel = pWInfo.a[i];
5597 explainOneScan( pParse, pTabList, pLevel, i, pLevel.iFrom, wctrlFlags );
5598 notReady = codeOneLoopStart( pWInfo, i, wctrlFlags, notReady );
5599 pWInfo.iContinue = pLevel.addrCont;
5600 }
5601  
5602 #if SQLITE_TEST //* For testing and debugging use only */
5603 /* Record in the query plan information about the current table
5604 ** and the index used to access it (if any). If the table itself
5605 ** is not used, its name is just '{}'. If no index is used
5606 ** the index is listed as "{}". If the primary key is used the
5607 ** index name is '*'.
5608 */
5609 #if !TCLSH
5610 sqlite3_query_plan.Length = 0;
5611 #else
5612 sqlite3_query_plan.sValue = string.Empty;
5613 #endif
5614 for ( i = 0; i < nTabList; i++ )
5615 {
5616 string z;
5617 int n;
5618 pLevel = pWInfo.a[i];
5619 pTabItem = pTabList.a[pLevel.iFrom];
5620 z = pTabItem.zAlias;
5621 if ( z == null )
5622 z = pTabItem.pTab.zName;
5623 n = sqlite3Strlen30( z );
5624 if ( true ) //n+nQPlan < sizeof(sqlite3_query_plan)-10 )
5625 {
5626 if ( ( pLevel.plan.wsFlags & WHERE_IDX_ONLY ) != 0 )
5627 {
5628 sqlite3_query_plan.Append( "{}" ); //memcpy( &sqlite3_query_plan[nQPlan], "{}", 2 );
5629 nQPlan += 2;
5630 }
5631 else
5632 {
5633 sqlite3_query_plan.Append( z ); //memcpy( &sqlite3_query_plan[nQPlan], z, n );
5634 nQPlan += n;
5635 }
5636 sqlite3_query_plan.Append( " " );
5637 nQPlan++; //sqlite3_query_plan[nQPlan++] = ' ';
5638 }
5639 testcase( pLevel.plan.wsFlags & WHERE_ROWID_EQ );
5640 testcase( pLevel.plan.wsFlags & WHERE_ROWID_RANGE );
5641 if ( ( pLevel.plan.wsFlags & ( WHERE_ROWID_EQ | WHERE_ROWID_RANGE ) ) != 0 )
5642 {
5643 sqlite3_query_plan.Append( "* " ); //memcpy(&sqlite3_query_plan[nQPlan], "* ", 2);
5644 nQPlan += 2;
5645 }
5646 else if ( ( pLevel.plan.wsFlags & WHERE_INDEXED ) != 0 )
5647 {
5648 n = sqlite3Strlen30( pLevel.plan.u.pIdx.zName );
5649 if ( true ) //n+nQPlan < sizeof(sqlite3_query_plan)-2 )//if( n+nQPlan < sizeof(sqlite3_query_plan)-2 )
5650 {
5651 sqlite3_query_plan.Append( pLevel.plan.u.pIdx.zName ); //memcpy(&sqlite3_query_plan[nQPlan], pLevel.plan.u.pIdx.zName, n);
5652 nQPlan += n;
5653 sqlite3_query_plan.Append( " " ); //sqlite3_query_plan[nQPlan++] = ' ';
5654 }
5655 }
5656 else
5657 {
5658 sqlite3_query_plan.Append( "{} " ); //memcpy( &sqlite3_query_plan[nQPlan], "{} ", 3 );
5659 nQPlan += 3;
5660 }
5661 }
5662 //while( nQPlan>0 && sqlite3_query_plan[nQPlan-1]==' ' ){
5663 // sqlite3_query_plan[--nQPlan] = 0;
5664 //}
5665 //sqlite3_query_plan[nQPlan] = 0;
5666 #if !TCLSH
5667 sqlite3_query_plan = new StringBuilder( sqlite3_query_plan.ToString().Trim() );
5668 #else
5669 sqlite3_query_plan.Trim();
5670 #endif
5671 nQPlan = 0;
5672 #endif //* SQLITE_TEST // Testing and debugging use only */
5673  
5674 /* Record the continuation address in the WhereInfo structure. Then
5675 ** clean up and return.
5676 */
5677 return pWInfo;
5678  
5679 /* Jump here if malloc fails */
5680 whereBeginError:
5681 if ( pWInfo != null )
5682 {
5683 pParse.nQueryLoop = pWInfo.savedNQueryLoop;
5684 whereInfoFree( db, pWInfo );
5685 }
5686 return null;
5687 }
5688  
5689 /*
5690 ** Generate the end of the WHERE loop. See comments on
5691 ** sqlite3WhereBegin() for additional information.
5692 */
5693 static void sqlite3WhereEnd( WhereInfo pWInfo )
5694 {
5695 Parse pParse = pWInfo.pParse;
5696 Vdbe v = pParse.pVdbe;
5697 int i;
5698 WhereLevel pLevel;
5699 SrcList pTabList = pWInfo.pTabList;
5700 sqlite3 db = pParse.db;
5701  
5702 /* Generate loop termination code.
5703 */
5704 sqlite3ExprCacheClear( pParse );
5705 for ( i = pWInfo.nLevel - 1; i >= 0; i-- )
5706 {
5707 pLevel = pWInfo.a[i];
5708 sqlite3VdbeResolveLabel( v, pLevel.addrCont );
5709 if ( pLevel.op != OP_Noop )
5710 {
5711 sqlite3VdbeAddOp2( v, pLevel.op, pLevel.p1, pLevel.p2 );
5712 sqlite3VdbeChangeP5( v, pLevel.p5 );
5713 }
5714 if ( ( pLevel.plan.wsFlags & WHERE_IN_ABLE ) != 0 && pLevel.u._in.nIn > 0 )
5715 {
5716 InLoop pIn;
5717 int j;
5718 sqlite3VdbeResolveLabel( v, pLevel.addrNxt );
5719 for ( j = pLevel.u._in.nIn; j > 0; j-- )//, pIn--)
5720 {
5721 pIn = pLevel.u._in.aInLoop[j - 1];
5722 sqlite3VdbeJumpHere( v, pIn.addrInTop + 1 );
5723 sqlite3VdbeAddOp2( v, OP_Next, pIn.iCur, pIn.addrInTop );
5724 sqlite3VdbeJumpHere( v, pIn.addrInTop - 1 );
5725 }
5726 sqlite3DbFree( db, ref pLevel.u._in.aInLoop );
5727 }
5728 sqlite3VdbeResolveLabel( v, pLevel.addrBrk );
5729 if ( pLevel.iLeftJoin != 0 )
5730 {
5731 int addr;
5732 addr = sqlite3VdbeAddOp1( v, OP_IfPos, pLevel.iLeftJoin );
5733 Debug.Assert( ( pLevel.plan.wsFlags & WHERE_IDX_ONLY ) == 0
5734 || ( pLevel.plan.wsFlags & WHERE_INDEXED ) != 0 );
5735 if ( ( pLevel.plan.wsFlags & WHERE_IDX_ONLY ) == 0 )
5736 {
5737 sqlite3VdbeAddOp1( v, OP_NullRow, pTabList.a[i].iCursor );
5738 }
5739 if ( pLevel.iIdxCur >= 0 )
5740 {
5741 sqlite3VdbeAddOp1( v, OP_NullRow, pLevel.iIdxCur );
5742 }
5743 if ( pLevel.op == OP_Return )
5744 {
5745 sqlite3VdbeAddOp2( v, OP_Gosub, pLevel.p1, pLevel.addrFirst );
5746 }
5747 else
5748 {
5749 sqlite3VdbeAddOp2( v, OP_Goto, 0, pLevel.addrFirst );
5750 }
5751 sqlite3VdbeJumpHere( v, addr );
5752 }
5753 }
5754  
5755 /* The "break" point is here, just past the end of the outer loop.
5756 ** Set it.
5757 */
5758 sqlite3VdbeResolveLabel( v, pWInfo.iBreak );
5759  
5760 /* Close all of the cursors that were opened by sqlite3WhereBegin.
5761 */
5762 Debug.Assert( pWInfo.nLevel == 1 || pWInfo.nLevel == pTabList.nSrc );
5763 for ( i = 0; i < pWInfo.nLevel; i++ )// for(i=0, pLevel=pWInfo.a; i<pWInfo.nLevel; i++, pLevel++){
5764 {
5765 pLevel = pWInfo.a[i];
5766 SrcList_item pTabItem = pTabList.a[pLevel.iFrom];
5767 Table pTab = pTabItem.pTab;
5768 Debug.Assert( pTab != null );
5769 if ( ( pTab.tabFlags & TF_Ephemeral ) == 0
5770 && pTab.pSelect == null
5771 && ( pWInfo.wctrlFlags & WHERE_OMIT_CLOSE ) == 0
5772 )
5773 {
5774 u32 ws = pLevel.plan.wsFlags;
5775 if ( 0 == pWInfo.okOnePass && ( ws & WHERE_IDX_ONLY ) == 0 )
5776 {
5777 sqlite3VdbeAddOp1( v, OP_Close, pTabItem.iCursor );
5778 }
5779 if ( ( ws & WHERE_INDEXED ) != 0 && ( ws & WHERE_TEMP_INDEX ) == 0 )
5780 {
5781 sqlite3VdbeAddOp1( v, OP_Close, pLevel.iIdxCur );
5782 }
5783 }
5784  
5785 /* If this scan uses an index, make code substitutions to read data
5786 ** from the index in preference to the table. Sometimes, this means
5787 ** the table need never be read from. This is a performance boost,
5788 ** as the vdbe level waits until the table is read before actually
5789 ** seeking the table cursor to the record corresponding to the current
5790 ** position in the index.
5791 **
5792 ** Calls to the code generator in between sqlite3WhereBegin and
5793 ** sqlite3WhereEnd will have created code that references the table
5794 ** directly. This loop scans all that code looking for opcodes
5795 ** that reference the table and converts them into opcodes that
5796 ** reference the index.
5797 */
5798 if ( ( pLevel.plan.wsFlags & WHERE_INDEXED ) != 0 )///* && 0 == db.mallocFailed */ )
5799 {
5800 int k, j, last;
5801 VdbeOp pOp;
5802 Index pIdx = pLevel.plan.u.pIdx;
5803  
5804 Debug.Assert( pIdx != null );
5805 //pOp = sqlite3VdbeGetOp( v, pWInfo.iTop );
5806 last = sqlite3VdbeCurrentAddr( v );
5807 for ( k = pWInfo.iTop; k < last; k++ )//, pOp++ )
5808 {
5809 pOp = sqlite3VdbeGetOp( v, k );
5810 if ( pOp.p1 != pLevel.iTabCur )
5811 continue;
5812 if ( pOp.opcode == OP_Column )
5813 {
5814 for ( j = 0; j < pIdx.nColumn; j++ )
5815 {
5816 if ( pOp.p2 == pIdx.aiColumn[j] )
5817 {
5818 pOp.p2 = j;
5819 pOp.p1 = pLevel.iIdxCur;
5820 break;
5821 }
5822 }
5823 Debug.Assert( ( pLevel.plan.wsFlags & WHERE_IDX_ONLY ) == 0
5824 || j < pIdx.nColumn );
5825  
5826 }
5827 else if ( pOp.opcode == OP_Rowid )
5828 {
5829 pOp.p1 = pLevel.iIdxCur;
5830 pOp.opcode = OP_IdxRowid;
5831 }
5832 }
5833 }
5834 }
5835  
5836 /* Final cleanup
5837 */
5838 pParse.nQueryLoop = pWInfo.savedNQueryLoop;
5839 whereInfoFree( db, pWInfo );
5840 return;
5841 }
5842 }
5843 }