2N/A#
pragma ident "%Z%%M% %I% %E% SMI" 2N/A** The author disclaims copyright to this source code. In place of 2N/A** a legal notice, here is a blessing: 2N/A** May you do good and not evil. 2N/A** May you find forgiveness for yourself and forgive others. 2N/A** May you share freely, never taking more than you give. 2N/A************************************************************************* 2N/A** This module contains C code that generates VDBE code used to process 2N/A** the WHERE clause of SQL statements. 2N/A** $Id: where.c,v 1.89.2.2 2004/07/19 19:30:50 drh Exp $ 2N/A** The query generator uses an array of instances of this structure to 2N/A** help it analyze the subexpressions of the WHERE clause. Each WHERE 2N/A** clause subexpression is separated from the others by an AND operator. 2N/A Expr *p;
/* Pointer to the subexpression */ 2N/A short int idxLeft;
/* p->pLeft is a column in this table number. -1 if 2N/A ** p->pLeft is not the column of any table */ 2N/A short int idxRight;
/* p->pRight is a column in this table number. -1 if 2N/A ** p->pRight is not the column of any table */ 2N/A unsigned prereqLeft;
/* Bitmask of tables referenced by p->pLeft */ 2N/A** An instance of the following structure keeps track of a mapping 2N/A** between VDBE cursor numbers and bitmasks. The VDBE cursor numbers 2N/A** are small integers contained in SrcList_item.iCursor and Expr.iTable 2N/A** fields. For any given WHERE clause, we want to track which cursors 2N/A** are being used, so we assign a single bit in a 32-bit word to track 2N/A** that cursor. Then a 32-bit integer is able to show the set of all 2N/A** cursors being used. 2N/A int n;
/* Number of assigned cursor values */ 2N/A int ix[
31];
/* Cursor assigned to each bit */ 2N/A** Determine the number of elements in an array. 2N/A** This routine is used to divide the WHERE expression into subexpressions 2N/A** separated by the AND operator. 2N/A** aSlot[] is an array of subexpressions structures. 2N/A** There are nSlot spaces left in this array. This routine attempts to 2N/A** split pExpr into subexpressions and fills aSlot[] with those subexpressions. 2N/A** The return value is the number of slots filled. 2N/A** Initialize an expression mask set 2N/A** Return the bitmask for the given cursor. Assign a new bitmask 2N/A** if this is the first time the cursor has been seen. 2N/A** Destroy an expression mask set 2N/A** This routine walks (recursively) an expression tree and generates 2N/A** a bitmask indicating which tables are used in that expression 2N/A** In order for this routine to work, the calling function must have 2N/A** previously invoked sqliteExprResolveIds() on the expression. See 2N/A** the header comment on that routine for additional information. 2N/A** The sqliteExprResolveIds() routines looks for column names and 2N/A** sets their opcodes to TK_COLUMN and their Expr.iTable fields to 2N/A** the VDBE cursor number of the table. 2N/A if( p==0 )
return 0;
2N/A** Return TRUE if the given operator is one of the operators that is 2N/A** allowed for an indexable WHERE clause. The allowed operators are 2N/A** "=", "<", ">", "<=", ">=", and "IN". 2N/A** The input to this routine is an ExprInfo structure with only the 2N/A** "p" field filled in. The job of this routine is to analyze the 2N/A** subexpression and populate all the other fields of the ExprInfo 2N/A** pOrderBy is an ORDER BY clause from a SELECT statement. pTab is the 2N/A** left-most table in the FROM clause of that same SELECT statement and 2N/A** the table has a cursor number of "base". 2N/A** This routine attempts to find an index for pTab that generates the 2N/A** correct record sequence for the given ORDER BY clause. The return value 2N/A** is a pointer to an index that does the job. NULL is returned if the 2N/A** table has no index that will generate the correct sort order. 2N/A** If there are two or more indices that generate the correct sort order 2N/A** and pPreferredIdx is one of those indices, then return pPreferredIdx. 2N/A** nEqCol is the number of columns of pPreferredIdx that are used as 2N/A** equality constraints. Any index returned must have exactly this same 2N/A** set of columns. The ORDER BY clause only matches index columns beyond the 2N/A** the first nEqCol columns. 2N/A** All terms of the ORDER BY clause must be either ASC or DESC. The 2N/A** *pbRev value is set to 1 if the ORDER BY clause is all DESC and it is 2N/A** set to 0 if the ORDER BY clause is all ASC. 2N/A int base,
/* Cursor number for pTab */ 2N/A int nEqCol,
/* Number of index columns used with == constraints */ 2N/A int *
pbRev /* Set to 1 if ORDER BY is DESC */ 2N/A /* Indices can only be used if all ORDER BY terms are either 2N/A ** DESC or ASC. Indices cannot be used on a mixture. */ 2N/A /* Do not sort by index if there is a COLLATE clause */ 2N/A /* Can not use an index sort on anything that is not a column in the 2N/A ** left-most table of the FROM clause */ 2N/A /* If we get this far, it means the ORDER BY clause consists only of 2N/A ** ascending columns in the left-most table of the FROM clause. Now 2N/A ** check for a matching index. 2N/A** Disable a term in the WHERE clause. Except, do not disable the term 2N/A** if it controls a LEFT OUTER JOIN and it did not originate in the ON 2N/A** or USING clause of that join. 2N/A** Consider the term t2.z='ok' in the following queries: 2N/A** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok' 2N/A** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok' 2N/A** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok' 2N/A** The t2.z='ok' is disabled in the in (2) because it did not originate 2N/A** in the ON clause. The term is disabled in (3) because it is not part 2N/A** of a LEFT OUTER JOIN. In (1), the term is not disabled. 2N/A** Disabling a term causes that term to not be tested in the inner loop 2N/A** of the join. Disabling is an optimization. We would get the correct 2N/A** results if nothing were ever disabled, but joins might run a little 2N/A** slower. The trick is to disable as much as we can without disabling 2N/A** too much. If we disabled in (1), we'd get the wrong answer. 2N/A** Generate the beginning of the loop used for WHERE clause processing. 2N/A** The return value is a pointer to an (opaque) structure that contains 2N/A** information needed to terminate the loop. Later, the calling routine 2N/A** should invoke sqliteWhereEnd() with the return value of this function 2N/A** in order to complete the WHERE clause processing. 2N/A** If an error occurs, this routine returns NULL. 2N/A** The basic idea is to do a nested loop, one loop for each table in 2N/A** the FROM clause of a select. (INSERT and UPDATE statements are the 2N/A** same as a SELECT with only a single table in the FROM clause.) For 2N/A** example, if the SQL is this: 2N/A** SELECT * FROM t1, t2, t3 WHERE ...; 2N/A** Then the code generated is conceptually like the following: 2N/A** foreach row1 in t1 do \ Code generated 2N/A** foreach row2 in t2 do |-- by sqliteWhereBegin() 2N/A** foreach row3 in t3 do / 2N/A** end \ Code generated 2N/A** end |-- by sqliteWhereEnd() 2N/A** There are Btree cursors associated with each table. t1 uses cursor 2N/A** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor. 2N/A** And so forth. This routine generates code to open those VDBE cursors 2N/A** and sqliteWhereEnd() generates the code to close them. 2N/A** If the WHERE clause is empty, the foreach loops must each scan their 2N/A** entire tables. Thus a three-way join is an O(N^3) operation. But if 2N/A** the tables have indices and there are terms in the WHERE clause that 2N/A** refer to those indices, a complete table scan can be avoided and the 2N/A** code will run much faster. Most of the work of this routine is checking 2N/A** to see if there are indices that can be used to speed up the loop. 2N/A** Terms of the WHERE clause are also used to limit which rows actually 2N/A** make it to the "..." in the middle of the loop. After each "foreach", 2N/A** terms of the WHERE clause that use only terms in that loop and outer 2N/A** loops are evaluated and if false a jump is made around all subsequent 2N/A** inner loops (or around the "..." if the test occurs within the inner- 2N/A** An outer join of tables t1 and t2 is conceptally coded as follows: 2N/A** foreach row1 in t1 do 2N/A** foreach row2 in t2 do 2N/A** move the row2 cursor to a null row 2N/A** ORDER BY CLAUSE PROCESSING 2N/A** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement, 2N/A** if there is one. If there is no ORDER BY clause or if this routine 2N/A** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL. 2N/A** If an index can be used so that the natural output order of the table 2N/A** scan is correct for the ORDER BY clause, then that index is used and 2N/A** *ppOrderBy is set to NULL. This is an optimization that prevents an 2N/A** unnecessary sort of the result set if an index appropriate for the 2N/A** ORDER BY clause already exists. 2N/A** If the where clause loops cannot be arranged to provide the correct 2N/A** output order, then the *ppOrderBy is unchanged. 2N/A int pushKey,
/* If TRUE, leave the table key on the stack */ 2N/A int i;
/* Loop counter */ 2N/A int brk,
cont = 0;
/* Addresses used during code generation */ 2N/A int nExpr;
/* Number of subexpressions in the WHERE clause */ 2N/A int iDirectEq[
32];
/* Term of the form ROWID==X for the N-th table */ 2N/A int iDirectLt[
32];
/* Term of the form ROWID<X or ROWID<=X */ 2N/A int iDirectGt[
32];
/* Term of the form ROWID>X or ROWID>=X */ 2N/A /* pushKey is only allowed if there is a single table (as in an INSERT or 2N/A ** UPDATE statement) 2N/A /* Split the WHERE clause into separate subexpressions where each 2N/A ** subexpression is separated by an AND operator. If the aExpr[] 2N/A ** array fills up, the last entry might point to an expression which 2N/A ** contains additional unfactored AND operators. 2N/A /* Allocate and initialize the WhereInfo structure that will become the 2N/A /* Special case: a WHERE clause that is constant. Evaluate the 2N/A ** expression and either jump over all of the code or fall thru. 2N/A /* Analyze all of the subexpressions. 2N/A /* If we are executing a trigger body, remove all references to 2N/A ** new.* and old.* tables from the prerequisite masks. 2N/A /* Figure out what index to use (if any) for each nested loop. 2N/A ** Make pWInfo->a[i].pIdx point to the index to use for the i-th nested 2N/A ** loop where i==0 is the outer loop and i==pTabList->nSrc-1 is the inner 2N/A ** If terms exist that use the ROWID of any table, then set the 2N/A ** iDirectEq[], iDirectLt[], or iDirectGt[] elements for that table 2N/A ** to the index of the term containing the ROWID. We always prefer 2N/A ** to use a ROWID which can directly access a table rather than an 2N/A ** index which requires reading an index first to get the rowid then 2N/A ** doing a second read of the actual database table. 2N/A ** Actually, if there are more than 32 tables in the join, only the 2N/A ** first 32 tables are candidates for indices. This is (again) due 2N/A ** to the limit of 32 bits in an integer bitmask. 2N/A /* Check to see if there is an expression that uses only the 2N/A ** ROWID field of this table. For terms of the form ROWID==expr 2N/A ** set iDirectEq[i] to the index of the term. For terms of the 2N/A ** form ROWID<expr or ROWID<=expr set iDirectLt[i] to the term index. 2N/A ** For terms like ROWID>expr or ROWID>=expr set iDirectGt[i]. 2N/A ** (Added:) Treat ROWID IN expr like ROWID=expr. 2N/A /* Do a search for usable indices. Leave pBestIdx pointing to 2N/A ** the "best" index. pBestIdx is left set to NULL if no indices 2N/A ** The best index is determined as follows. For each of the 2N/A ** left-most terms that is fixed by an equality operator, add 2N/A ** 8 to the score. The right-most term of the index may be 2N/A ** constrained by an inequality. Add 1 if for an "x<..." constraint 2N/A ** and add 2 for an "x>..." constraint. Chose the index that 2N/A ** gives the best score. 2N/A ** This scoring system is designed so that the score can later be 2N/A ** used to determine how the index is used. If the score&7 is 0 2N/A ** then all constraints are equalities. If score&1 is not 0 then 2N/A ** there is an inequality used as a termination key. (ex: "x<...") 2N/A ** If score&2 is not 0 then there is an inequality used as the 2N/A ** start key. (ex: "x>..."). A score or 4 is the special case 2N/A ** of an IN operator constraint. (ex: "x IN ..."). 2N/A ** The IN operator (as in "<expr> IN (...)") is treated the same as 2N/A ** an equality comparison except that it can only be used on the 2N/A ** left-most column of an index and other terms of the WHERE clause 2N/A ** cannot be used in conjunction with the IN operator to help satisfy 2N/A ** other columns of the index. 2N/A int eqMask = 0;
/* Index columns covered by an x=... term */ 2N/A int ltMask = 0;
/* Index columns covered by an x<... term */ 2N/A int gtMask = 0;
/* Index columns covered by an x>... term */ 2N/A int inMask = 0;
/* Index columns covered by an x IN .. term */ 2N/A if(
pIdx->
nColumn>
32 )
continue;
/* Ignore indices too many columns */ 2N/A /* The following loop ends with nEq set to the number of columns 2N/A ** on the left of the index with == constraints. 2N/A score =
nEq*
8;
/* Base score is 8 times number of == constraints */ 2N/A /* Check to see if the ORDER BY clause is or can be satisfied by the 2N/A ** use of an index on the first table. 2N/A /* If there is already an IN index on the left-most table, 2N/A ** it will not give the correct sort order. 2N/A ** So, pretend that no suitable index is found. 2N/A /* If the left-most column is accessed using its ROWID, then do 2N/A ** not try to sort by index. 2N/A /* Open all tables in the pTabList and all indices used by those tables. 2N/A /* Generate the code to do the search 2N/A /* If this is the right table of a LEFT OUTER JOIN, allocate and 2N/A ** initialize a memory cell that records if this table matches any 2N/A ** row of the left table of the join. 2N/A /* Case 1: We can directly reference a single row using an 2N/A ** equality comparison against the ROWID field. Or 2N/A ** we reference multiple rows using a "rowid IN (...)" 2N/A /* Case 2: There is an index and all terms of the WHERE clause that 2N/A ** refer to the index use the "==" or "IN" operators. 2N/A /* Scan in reverse order */ 2N/A /* Scan in the forward order */ 2N/A /* Case 3: We have an inequality comparison against the ROWID field. 2N/A /* sqliteVdbeAddOp(v, OP_MustBeInt, 0, sqliteVdbeCurrentAddr(v)+1); */ 2N/A /* Case 4: There is no usable index. We must do a complete 2N/A ** scan of the entire database table. 2N/A /* Case 5: The WHERE clause term that refers to the right-most 2N/A ** column of the index is an inequality. For example, if 2N/A ** the index is on (x,y,z) and the WHERE clause is of the 2N/A ** form "x=5 AND y<10" then this case is used. Only the 2N/A ** right-most column can be an inequality - the rest must 2N/A ** use the "==" operator. 2N/A ** This case is also used when there are no WHERE clause 2N/A ** constraints but an index is selected anyway, in order 2N/A ** to force the output order to conform to an ORDER BY. 2N/A /* Evaluate the equality constraints 2N/A /* Duplicate the equality term values because they will all be 2N/A ** used twice: once to make the termination key and once to make the 2N/A /* Labels for the beginning and end of the loop 2N/A /* Generate the termination key. This is the key value that 2N/A ** will end the search. There is no termination key if there 2N/A ** are no equality terms and no "X<..." term. 2N/A ** 2002-Dec-04: On a reverse-order scan, the so-called "termination" 2N/A ** key computed here really ends up being the start key. 2N/A /* Generate the start key. This is the key that defines the lower 2N/A ** bound on the search. There is no start key if there are no 2N/A ** equality terms and if there is no "X>..." term. In 2N/A ** that case, generate a "Rewind" instruction in place of the 2N/A ** start key search. 2N/A ** 2002-Dec-04: In the case of a reverse-order search, the so-called 2N/A ** "start" key really ends up being used as the termination key. 2N/A /* Generate the the top of the loop. If there is a termination 2N/A ** key we have to test for that key and abort at the top of the 2N/A /* Record the instruction used to terminate the loop. 2N/A /* Insert code to test every subexpression that can be completely 2N/A ** computed using the current set of tables. 2N/A /* For a LEFT OUTER JOIN, generate code that will record the fact that 2N/A ** at least one row of the right table has matched the left table. 2N/A /* Cannot happen. "haveKey" can only be true if pushKey is true 2N/A ** an pushKey can only be true for DELETE and UPDATE and there are 2N/A ** no outer joins with DELETE and UPDATE. 2N/A** Generate the end of the WHERE loop. See comments on 2N/A** sqliteWhereBegin() for additional information. 2N/A#
if 0
/* Never reuse a cursor */