/ Check-in [f8d8790e]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Fix typos and add clarification to comments in where.c. No code changes.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:f8d8790ede0fcaf6c5b60ac22919c1d97c74e838
User & Date: drh 2013-08-07 01:18:38
Context
2013-08-07
14:18
Add a guard #ifndef to test_intarray.h to prevent harm if it is #included more than once. Add a comment on the closing #endif of the guards on sqlite3.h and test_multiplex.h. check-in: 0ad83ceb user: drh tags: trunk
01:18
Fix typos and add clarification to comments in where.c. No code changes. check-in: f8d8790e user: drh tags: trunk
2013-08-06
19:18
Fix a test case related to partial indices so that it works even if STAT3 is disabled. check-in: 153c6450 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
..
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

66
67
68
69
70
71
72
...
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
...
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
...
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
....
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
....
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
    && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
# define WHERETRACE(K,X)  if(sqlite3WhereTrace&(K)) sqlite3DebugPrintf X
# define WHERETRACE_ENABLED 1
#else
# define WHERETRACE(K,X)
#endif

/* Forward reference
*/
typedef struct WhereClause WhereClause;
typedef struct WhereMaskSet WhereMaskSet;
typedef struct WhereOrInfo WhereOrInfo;
typedef struct WhereAndInfo WhereAndInfo;
typedef struct WhereLevel WhereLevel;
typedef struct WhereLoop WhereLoop;
................................................................................
/*
** Cost X is tracked as 10*log2(X) stored in a 16-bit integer.  The
** maximum cost for ordinary tables is 64*(2**63) which becomes 6900.
** (Virtual tables can return a larger cost, but let's assume they do not.)
** So all costs can be stored in a 16-bit unsigned integer without risk
** of overflow.
**
** Costs are estimates, so don't go to the computational trouble to compute
** 10*log2(X) exactly.  Instead, a close estimate is used.  Any value of
** X<=1 is stored as 0.  X=2 is 10.  X=3 is 16.  X=1000 is 99. etc.
**
** The tool/wherecosttest.c source file implements a command-line program
** that will convert between WhereCost to integers and do addition and
** multiplication on WhereCost values.  That command-line program is a
** useful utility to have around when working with this module.

*/
typedef unsigned short int WhereCost;

/*
** This object contains information needed to implement a single nested
** loop in WHERE clause.
**
................................................................................
struct WhereOrCost {
  Bitmask prereq;     /* Prerequisites */
  WhereCost rRun;     /* Cost of running this subquery */
  WhereCost nOut;     /* Number of outputs for this subquery */
};

/* The WhereOrSet object holds a set of possible WhereOrCosts that
** correspond to the subquery(s) of OR-clause processing.  At most
** favorable N_OR_COST elements are retained.
*/
#define N_OR_COST 3
struct WhereOrSet {
  u16 n;                      /* Number of valid a[] entries */
  WhereOrCost a[N_OR_COST];   /* Set of best costs */
};

................................................................................
** use of a bitmask encoding for the operator allows us to search
** quickly for terms that match any of several different operators.
**
** A WhereTerm might also be two or more subterms connected by OR:
**
**         (t1.X <op> <expr>) OR (t1.Y <op> <expr>) OR ....
**
** In this second case, wtFlag as the TERM_ORINFO set and eOperator==WO_OR
** and the WhereTerm.u.pOrInfo field points to auxiliary information that
** is collected about the
**
** If a term in the WHERE clause does not match either of the two previous
** categories, then eOperator==0.  The WhereTerm.pExpr field is still set
** to the original subexpression content and wtFlags is set up appropriately
** but no other fields in the WhereTerm object are meaningful.
**
** When eOperator!=0, prereqRight and prereqAll record sets of cursor numbers,
................................................................................
*/
static void createMask(WhereMaskSet *pMaskSet, int iCursor){
  assert( pMaskSet->n < ArraySize(pMaskSet->ix) );
  pMaskSet->ix[pMaskSet->n++] = iCursor;
}

/*
** These routine walk (recursively) an expression tree and generates
** a bitmask indicating which tables are used in that expression
** tree.
*/
static Bitmask exprListTableUsage(WhereMaskSet*, ExprList*);
static Bitmask exprSelectTableUsage(WhereMaskSet*, Select*);
static Bitmask exprTableUsage(WhereMaskSet *pMaskSet, Expr *p){
  Bitmask mask = 0;
................................................................................
** subsubterms at least one of which is indexable.  Indexable AND 
** subterms have their eOperator set to WO_AND and they have
** u.pAndInfo set to a dynamically allocated WhereAndTerm object.
**
** From another point of view, "indexable" means that the subterm could
** potentially be used with an index if an appropriate index exists.
** This analysis does not consider whether or not the index exists; that
** is something the bestIndex() routine will determine.  This analysis
** only looks at whether subterms appropriate for indexing exist.
**
** All examples A through E above all satisfy case 2.  But if a term
** also statisfies case 1 (such as B) we know that the optimizer will
** always prefer case 1, so in that case we pretend that case 2 is not
** satisfied.
**
** It might be the case that multiple tables are indexable.  For example,
** (E) above is indexable on tables P, Q, and R.
**
................................................................................
    }
  }

  return 0;
}

/* 
** The (an approximate) sum of two WhereCosts.  This computation is
** not a simple "+" operator because WhereCost is stored as a logarithmic
** value.
** 
*/
static WhereCost whereCostAdd(WhereCost a, WhereCost b){
  static const unsigned char x[] = {
     10, 10,                         /* 0,1 */







|







 







|
|
|


|
|
|
>







 







|
|







 







|

|







 







|







 







|
|

|







 







|







29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
..
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
...
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
...
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
...
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
....
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
....
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
    && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
# define WHERETRACE(K,X)  if(sqlite3WhereTrace&(K)) sqlite3DebugPrintf X
# define WHERETRACE_ENABLED 1
#else
# define WHERETRACE(K,X)
#endif

/* Forward references
*/
typedef struct WhereClause WhereClause;
typedef struct WhereMaskSet WhereMaskSet;
typedef struct WhereOrInfo WhereOrInfo;
typedef struct WhereAndInfo WhereAndInfo;
typedef struct WhereLevel WhereLevel;
typedef struct WhereLoop WhereLoop;
................................................................................
/*
** Cost X is tracked as 10*log2(X) stored in a 16-bit integer.  The
** maximum cost for ordinary tables is 64*(2**63) which becomes 6900.
** (Virtual tables can return a larger cost, but let's assume they do not.)
** So all costs can be stored in a 16-bit unsigned integer without risk
** of overflow.
**
** Costs are estimates, so no effort is made to compute 10*log2(X) exactly.
** Instead, a close estimate is used.  Any value of X<=1 is stored as 0.
** X=2 is 10.  X=3 is 16.  X=1000 is 99. etc.
**
** The tool/wherecosttest.c source file implements a command-line program
** that will convert WhereCosts to integers, convert integers to WhereCosts
** and do addition and multiplication on WhereCost values.  The wherecosttest
** command-line program is a useful utility to have around when working with
** this module.
*/
typedef unsigned short int WhereCost;

/*
** This object contains information needed to implement a single nested
** loop in WHERE clause.
**
................................................................................
struct WhereOrCost {
  Bitmask prereq;     /* Prerequisites */
  WhereCost rRun;     /* Cost of running this subquery */
  WhereCost nOut;     /* Number of outputs for this subquery */
};

/* The WhereOrSet object holds a set of possible WhereOrCosts that
** correspond to the subquery(s) of OR-clause processing.  Only the
** best N_OR_COST elements are retained.
*/
#define N_OR_COST 3
struct WhereOrSet {
  u16 n;                      /* Number of valid a[] entries */
  WhereOrCost a[N_OR_COST];   /* Set of best costs */
};

................................................................................
** use of a bitmask encoding for the operator allows us to search
** quickly for terms that match any of several different operators.
**
** A WhereTerm might also be two or more subterms connected by OR:
**
**         (t1.X <op> <expr>) OR (t1.Y <op> <expr>) OR ....
**
** In this second case, wtFlag has the TERM_ORINFO bit set and eOperator==WO_OR
** and the WhereTerm.u.pOrInfo field points to auxiliary information that
** is collected about the OR clause.
**
** If a term in the WHERE clause does not match either of the two previous
** categories, then eOperator==0.  The WhereTerm.pExpr field is still set
** to the original subexpression content and wtFlags is set up appropriately
** but no other fields in the WhereTerm object are meaningful.
**
** When eOperator!=0, prereqRight and prereqAll record sets of cursor numbers,
................................................................................
*/
static void createMask(WhereMaskSet *pMaskSet, int iCursor){
  assert( pMaskSet->n < ArraySize(pMaskSet->ix) );
  pMaskSet->ix[pMaskSet->n++] = iCursor;
}

/*
** These routines walk (recursively) an expression tree and generate
** a bitmask indicating which tables are used in that expression
** tree.
*/
static Bitmask exprListTableUsage(WhereMaskSet*, ExprList*);
static Bitmask exprSelectTableUsage(WhereMaskSet*, Select*);
static Bitmask exprTableUsage(WhereMaskSet *pMaskSet, Expr *p){
  Bitmask mask = 0;
................................................................................
** subsubterms at least one of which is indexable.  Indexable AND 
** subterms have their eOperator set to WO_AND and they have
** u.pAndInfo set to a dynamically allocated WhereAndTerm object.
**
** From another point of view, "indexable" means that the subterm could
** potentially be used with an index if an appropriate index exists.
** This analysis does not consider whether or not the index exists; that
** is decided elsewhere.  This analysis only looks at whether subterms
** appropriate for indexing exist.
**
** All examples A through E above satisfy case 2.  But if a term
** also statisfies case 1 (such as B) we know that the optimizer will
** always prefer case 1, so in that case we pretend that case 2 is not
** satisfied.
**
** It might be the case that multiple tables are indexable.  For example,
** (E) above is indexable on tables P, Q, and R.
**
................................................................................
    }
  }

  return 0;
}

/* 
** Find (an approximate) sum of two WhereCosts.  This computation is
** not a simple "+" operator because WhereCost is stored as a logarithmic
** value.
** 
*/
static WhereCost whereCostAdd(WhereCost a, WhereCost b){
  static const unsigned char x[] = {
     10, 10,                         /* 0,1 */