/ Check-in [78401b33]
Login

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

Overview
Comment:Update the WHERE clause processing infrastructure in preparation for adding multi-index OR evaluation. (CVS 6037)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:78401b33febf678cfeec2a35514eb4172de420ab
User & Date: drh 2008-12-17 19:22:16
Context
2008-12-18
05:30
Fix a bug in icuOpen() in fts2. (CVS 6038) check-in: b9c722bd user: danielk1977 tags: trunk
2008-12-17
19:22
Update the WHERE clause processing infrastructure in preparation for adding multi-index OR evaluation. (CVS 6037) check-in: 78401b33 user: drh tags: trunk
17:30
Add the savepoint feature. This feature is largely untested at this point. (CVS 6036) check-in: 34b56600 user: danielk1977 tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/sqliteInt.h.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
....
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546

1547
1548
1549
1550
1551
1552
1553
1554

1555
1556
1557
1558
1559
1560
1561
1562
1563
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.810 2008/12/17 17:30:26 danielk1977 Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if we're using the
** autoconf-based build
................................................................................
** for WhereInfo.pTabList.a[i].  WhereInfo.a[i].pBestInfo is the
** index information for the i-th loop of the join.  pBestInfo is always
** either NULL or a copy of some pIdxInfo.  So for cleanup it is 
** sufficient to free all of the pIdxInfo pointers.
** 
*/
struct WhereLevel {
  int iFrom;            /* Which entry in the FROM clause */
  int wsFlags;          /* "Where-Scan" flags show the choosen scan strategy */
  int iMem;             /* First memory cell used by this level */
  int iLeftJoin;        /* Memory cell used to implement LEFT OUTER JOIN */
  Index *pIdx;          /* Index used.  NULL if no index */

  int iTabCur;          /* The VDBE cursor used to access the table */
  int iIdxCur;          /* The VDBE cursor used to access pIdx */
  int addrBrk;          /* Jump here to break out of the loop */
  int addrNxt;          /* Jump here to start the next IN combination */
  int addrCont;         /* Jump here to continue with the next loop cycle */
  int addrFirst;        /* First instruction of interior of the loop */
  int op, p1, p2;       /* Opcode used to terminate the loop */
  u8 p5;                /* P5 operand of the opcode that terminates the loop */

  int nEq;              /* Number of == or IN constraints on this loop */
  int nIn;              /* Number of IN operators constraining this loop */
  struct InLoop {
    int iCur;              /* The VDBE cursor used by this IN operator */
    int addrInTop;         /* Top of the IN loop */
  } *aInLoop;           /* Information about each nested IN operator */
  sqlite3_index_info *pBestIdx;  /* Index information for this level */

  /* The following field is really not part of the current level.  But







|







 







<
|
<


>








>
|
|







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
....
1535
1536
1537
1538
1539
1540
1541

1542

1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.811 2008/12/17 19:22:16 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if we're using the
** autoconf-based build
................................................................................
** for WhereInfo.pTabList.a[i].  WhereInfo.a[i].pBestInfo is the
** index information for the i-th loop of the join.  pBestInfo is always
** either NULL or a copy of some pIdxInfo.  So for cleanup it is 
** sufficient to free all of the pIdxInfo pointers.
** 
*/
struct WhereLevel {

  u32 wsFlags;          /* "Where-Scan" flags show the choosen scan strategy */

  int iLeftJoin;        /* Memory cell used to implement LEFT OUTER JOIN */
  Index *pIdx;          /* Index used.  NULL if no index */
  struct WhereTerm *pTerm; /* Where term containing OR clause */
  int iTabCur;          /* The VDBE cursor used to access the table */
  int iIdxCur;          /* The VDBE cursor used to access pIdx */
  int addrBrk;          /* Jump here to break out of the loop */
  int addrNxt;          /* Jump here to start the next IN combination */
  int addrCont;         /* Jump here to continue with the next loop cycle */
  int addrFirst;        /* First instruction of interior of the loop */
  int op, p1, p2;       /* Opcode used to terminate the loop */
  u8 p5;                /* P5 operand of the opcode that terminates the loop */
  u8 iFrom;             /* Which entry in the FROM clause */
  u16 nEq;              /* Number of == or IN constraints on this loop */
  u16 nIn;              /* Number of IN operators constraining this loop */
  struct InLoop {
    int iCur;              /* The VDBE cursor used by this IN operator */
    int addrInTop;         /* Top of the IN loop */
  } *aInLoop;           /* Information about each nested IN operator */
  sqlite3_index_info *pBestIdx;  /* Index information for this level */

  /* The following field is really not part of the current level.  But

Changes to src/where.c.

12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
..
32
33
34
35
36
37
38


39
40
41
42
43
44
45
..
51
52
53
54
55
56
57
58
59
60
61
62
63













64
65
66
67
68
69
70
71
..
78
79
80
81
82
83
84

85



86
87
88
89
90
91
92
..
94
95
96
97
98
99
100


101
102
103
104
105
106
107
108
109
110
111
112
113
114



















115
116
117
118
119
120
121
...
154
155
156
157
158
159
160
161

162
163
164
165
166

167
168
169
170
171
172
173
174
175
176
177
178
179
...
198
199
200
201
202
203
204





















205
206
207
208
209
210
211
212
213
214
215
216
217





218
219
220
221
222
223
224
...
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
...
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
...
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
...
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
...
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
...
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
....
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
....
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
....
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
....
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
....
2476
2477
2478
2479
2480
2481
2482

2483
2484
2485
2486
2487
2488
2489
....
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
....
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
....
2730
2731
2732
2733
2734
2735
2736




























2737
2738
2739
2740
2741
2742
2743
2744
2745
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is responsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.337 2008/12/12 17:56:16 drh Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
................................................................................
# define WHERETRACE(X)
#endif

/* Forward reference
*/
typedef struct WhereClause WhereClause;
typedef struct ExprMaskSet ExprMaskSet;



/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by AND operators.
** (Note: the same data structure is also reused to hold a group of terms
** separated by OR operators.  But at the top-level, everything is AND
................................................................................
**        WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm
**
** When a term is of the form:
**
**              X <op> <expr>
**
** where X is a column name and <op> is one of certain operators,
** then WhereTerm.leftCursor and WhereTerm.leftColumn record the
** cursor number and column number for X.  WhereTerm.operator records
** the <op> using a bitmask encoding defined by WO_xxx below.  The
** use of a bitmask encoding for the operator allows us to search
** quickly for terms that match any of several different operators.
**













** prereqRight and prereqAll record sets of cursor numbers,
** but they do so indirectly.  A single ExprMaskSet structure translates
** cursor number into bits and the translated bit is stored in the prereq
** fields.  The translation is used in order to maximize the number of
** bits that will fit in a Bitmask.  The VDBE cursor numbers might be
** spread out over the non-negative integers.  For example, the cursor
** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45.  The ExprMaskSet
** translates these sparse cursor numbers into consecutive integers
................................................................................
** is only able to process joins with 64 or fewer tables.
*/
typedef struct WhereTerm WhereTerm;
struct WhereTerm {
  Expr *pExpr;            /* Pointer to the subexpression that is this term */
  int iParent;            /* Disable pWC->a[iParent] when this term disabled */
  int leftCursor;         /* Cursor number of X in "X <op> <expr>" */

  int leftColumn;         /* Column number of X in "X <op> <expr>" */



  u16 eOperator;          /* A WO_xx value describing <op> */
  u8 wtFlags;             /* TERM_xxx bit flags.  See below */
  u8 nChild;              /* Number of children that must disable us */
  WhereClause *pWC;       /* The clause this term is part of */
  Bitmask prereqRight;    /* Bitmask of tables used by pExpr->pRight */
  Bitmask prereqAll;      /* Bitmask of tables referenced by pExpr */
};
................................................................................
/*
** Allowed values of WhereTerm.wtFlags
*/
#define TERM_DYNAMIC    0x01   /* Need to call sqlite3ExprDelete(db, pExpr) */
#define TERM_VIRTUAL    0x02   /* Added by the optimizer.  Do not code */
#define TERM_CODED      0x04   /* This term is already coded */
#define TERM_COPIED     0x08   /* Has a child */


#define TERM_OR_OK      0x10   /* Used during OR-clause processing */

/*
** An instance of the following structure holds all information about a
** WHERE clause.  Mostly this is a container for one or more WhereTerms.
*/
struct WhereClause {
  Parse *pParse;           /* The parser context */
  ExprMaskSet *pMaskSet;   /* Mapping of table indices to bitmasks */
  int nTerm;               /* Number of terms */
  int nSlot;               /* Number of entries in a[] */
  WhereTerm *a;            /* Each a[] describes a term of the WHERE cluase */
  WhereTerm aStatic[4];    /* Initial static space for a[] */
};




















/*
** An instance of the following structure keeps track of a mapping
** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.
**
** The VDBE cursor numbers are small integers contained in 
** SrcList_item.iCursor and Expr.iTable fields.  For any given WHERE 
................................................................................
#define WO_EQ     0x002
#define WO_LT     (WO_EQ<<(TK_LT-TK_EQ))
#define WO_LE     (WO_EQ<<(TK_LE-TK_EQ))
#define WO_GT     (WO_EQ<<(TK_GT-TK_EQ))
#define WO_GE     (WO_EQ<<(TK_GE-TK_EQ))
#define WO_MATCH  0x040
#define WO_ISNULL 0x080
#define WO_OR     0x100


#define WO_ALL    0xfff       /* Mask of all possible WO_* values */

/*
** Value for wsFlags returned by bestIndex().  These flags determine which

** search strategies are appropriate.
**
** The least significant 12 bits is reserved as a mask for WO_ values above.
** The WhereLevel.wtFlags field is usually set to WO_IN|WO_EQ|WO_ISNULL.
** But if the table is the right table of a left join, WhereLevel.wtFlags
** is set to WO_IN|WO_EQ.  The WhereLevel.wtFlags field can then be used as
** the "op" parameter to findTerm when we are resolving equality constraints.
** ISNULL constraints will then not be used on the right table of a left
** join.  Tickets #2177 and #2189.
*/
#define WHERE_ROWID_EQ     0x00001000  /* rowid=EXPR or rowid IN (...) */
#define WHERE_ROWID_RANGE  0x00002000  /* rowid<EXPR and/or rowid>EXPR */
#define WHERE_COLUMN_EQ    0x00010000  /* x=EXPR or x IN (...) */
................................................................................
){
  pWC->pParse = pParse;
  pWC->pMaskSet = pMaskSet;
  pWC->nTerm = 0;
  pWC->nSlot = ArraySize(pWC->aStatic);
  pWC->a = pWC->aStatic;
}






















/*
** Deallocate a WhereClause structure.  The WhereClause structure
** itself is not freed.  This routine is the inverse of whereClauseInit().
*/
static void whereClauseClear(WhereClause *pWC){
  int i;
  WhereTerm *a;
  sqlite3 *db = pWC->pParse->db;
  for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){
    if( a->wtFlags & TERM_DYNAMIC ){
      sqlite3ExprDelete(db, a->pExpr);
    }





  }
  if( pWC->a!=pWC->aStatic ){
    sqlite3DbFree(db, pWC->a);
  }
}

/*
................................................................................
  WhereTerm *pTerm;
  int k;
  assert( iCur>=0 );
  op &= WO_ALL;
  for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
    if( pTerm->leftCursor==iCur
       && (pTerm->prereqRight & notReady)==0
       && pTerm->leftColumn==iColumn
       && (pTerm->eOperator & op)!=0
    ){
      if( pIdx && pTerm->eOperator!=WO_ISNULL ){
        Expr *pX = pTerm->pExpr;
        CollSeq *pColl;
        char idxaff;
        int j;
................................................................................
*/
static int orTermIsOptCandidate(WhereTerm *pOrTerm, int iCursor, int iColumn){
  int affLeft, affRight;
  assert( pOrTerm->eOperator==WO_EQ );
  if( pOrTerm->leftCursor!=iCursor ){
    return 0;
  }
  if( pOrTerm->leftColumn!=iColumn ){
    return 0;
  }
  affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);
  if( affRight==0 ){
    return 1;
  }
  affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);
................................................................................
  pTerm->iParent = -1;
  pTerm->eOperator = 0;
  if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
    Expr *pLeft = pExpr->pLeft;
    Expr *pRight = pExpr->pRight;
    if( pLeft->op==TK_COLUMN ){
      pTerm->leftCursor = pLeft->iTable;
      pTerm->leftColumn = pLeft->iColumn;
      pTerm->eOperator = operatorMask(op);
    }
    if( pRight && pRight->op==TK_COLUMN ){
      WhereTerm *pNew;
      Expr *pDup;
      if( pTerm->leftCursor>=0 ){
        int idxNew;
................................................................................
      }else{
        pDup = pExpr;
        pNew = pTerm;
      }
      exprCommute(pParse, pDup);
      pLeft = pDup->pLeft;
      pNew->leftCursor = pLeft->iTable;
      pNew->leftColumn = pLeft->iColumn;
      pNew->prereqRight = prereqLeft;
      pNew->prereqAll = prereqAll;
      pNew->eOperator = operatorMask(pDup->op);
    }
  }

#ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
................................................................................
    whereSplit(&sOr, pExpr, TK_OR);
    exprAnalyzeAll(pSrc, &sOr);
    assert( sOr.nTerm>=2 );
    j = 0;
    if( db->mallocFailed ) goto or_not_possible;
    do{
      assert( j<sOr.nTerm );
      iColumn = sOr.a[j].leftColumn;
      iCursor = sOr.a[j].leftCursor;
      ok = iCursor>=0;
      for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){
        if( pOrTerm->eOperator!=WO_EQ ){
          goto or_not_possible;
        }
        if( orTermIsOptCandidate(pOrTerm, iCursor, iColumn) ){
................................................................................
      Expr *pNewExpr;
      pNewExpr = sqlite3Expr(db, TK_MATCH, 0, sqlite3ExprDup(db, pRight), 0);
      idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
      testcase( idxNew==0 );
      pNewTerm = &pWC->a[idxNew];
      pNewTerm->prereqRight = prereqExpr;
      pNewTerm->leftCursor = pLeft->iTable;
      pNewTerm->leftColumn = pLeft->iColumn;
      pNewTerm->eOperator = WO_MATCH;
      pNewTerm->iParent = idxTerm;
      pTerm = &pWC->a[idxTerm];
      pTerm->nChild = 1;
      pTerm->wtFlags |= TERM_COPIED;
      pNewTerm->prereqAll = pTerm->prereqAll;
    }
................................................................................

    for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
      if( pTerm->leftCursor != pSrc->iCursor ) continue;
      assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
      testcase( pTerm->eOperator==WO_IN );
      testcase( pTerm->eOperator==WO_ISNULL );
      if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
      pIdxCons[j].iColumn = pTerm->leftColumn;
      pIdxCons[j].iTermOffset = i;
      pIdxCons[j].op = (u8)pTerm->eOperator;
      /* The direct assignment in the previous line is possible only because
      ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical.  The
      ** following asserts verify this fact. */
      assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
      assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
................................................................................
  
    /* Check for constraints on a range of rowids in a table scan.
    */
    pTerm = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE|WO_GT|WO_GE, 0);
    if( pTerm ){
      if( findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0) ){
        wsFlags |= WHERE_TOP_LIMIT;
        cost /= 3;  /* Guess that rowid<EXPR eliminates two-thirds or rows */
      }
      if( findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0) ){
        wsFlags |= WHERE_BTM_LIMIT;
        cost /= 3;  /* Guess that rowid>EXPR eliminates two-thirds of rows */
      }
      WHERETRACE(("... rowid range reduces cost to %.9g\n", cost));
    }else{
................................................................................
** a==5 and b IN (1,2,3).  The current values for a and b will be left
** on the stack - a is the deepest and b the shallowest.
**
** In the example above nEq==2.  But this subroutine works for any value
** of nEq including 0.  If nEq==0, this routine is nearly a no-op.
** The only thing it does is allocate the pLevel->iMem memory cell.
**
** This routine always allocates at least one memory cell and puts
** the address of that memory cell in pLevel->iMem.  The code that
** calls this routine will use pLevel->iMem to store the termination
** key value of the loop.  If one or more IN operators appear, then
** this routine allocates an additional nEq memory cells for internal
** use.
*/
static int codeAllEqualityTerms(
  Parse *pParse,        /* Parsing context */
  WhereLevel *pLevel,   /* Which nested loop of the FROM we are coding */
................................................................................
  int regBase;                  /* Base register */

  /* Figure out how many memory cells we will need then allocate them.
  ** We always need at least one used to store the loop terminator
  ** value.  If there are IN operators we'll need one for each == or
  ** IN constraint.
  */
  pLevel->iMem = pParse->nMem + 1;
  regBase = pParse->nMem + 2;
  pParse->nMem += pLevel->nEq + 2 + nExtraReg;

  /* Evaluate the equality constraints
  */
  assert( pIdx->nColumn>=nEq );
  for(j=0; j<nEq; j++){
    int r1;
    int k = pIdx->aiColumn[j];
................................................................................
      VdbeComment((v, "pk"));
      pLevel->op = OP_Noop;
    }else if( pLevel->wsFlags & WHERE_ROWID_RANGE ){
      /* Case 2:  We have an inequality comparison against the ROWID field.
      */
      int testOp = OP_Noop;
      int start;

      WhereTerm *pStart, *pEnd;

      assert( omitTable==0 );
      pStart = findTerm(&wc, iCur, -1, notReady, WO_GT|WO_GE, 0);
      pEnd = findTerm(&wc, iCur, -1, notReady, WO_LT|WO_LE, 0);
      if( bRev ){
        pTerm = pStart;
................................................................................
        sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrBrk);
      }
      if( pEnd ){
        Expr *pX;
        pX = pEnd->pExpr;
        assert( pX!=0 );
        assert( pEnd->leftCursor==iCur );
        pLevel->iMem = ++pParse->nMem;
        sqlite3ExprCode(pParse, pX->pRight, pLevel->iMem);
        if( pX->op==TK_LT || pX->op==TK_GT ){
          testOp = bRev ? OP_Le : OP_Ge;
        }else{
          testOp = bRev ? OP_Lt : OP_Gt;
        }
        disableTerm(pLevel, pEnd);
      }
................................................................................
      start = sqlite3VdbeCurrentAddr(v);
      pLevel->op = bRev ? OP_Prev : OP_Next;
      pLevel->p1 = iCur;
      pLevel->p2 = start;
      if( testOp!=OP_Noop ){
        int r1 = sqlite3GetTempReg(pParse);
        sqlite3VdbeAddOp2(v, OP_Rowid, iCur, r1);
        /* sqlite3VdbeAddOp2(v, OP_SCopy, pLevel->iMem, 0); */
        sqlite3VdbeAddOp3(v, testOp, pLevel->iMem, addrBrk, r1);
        sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
        sqlite3ReleaseTempReg(pParse, r1);
      }
    }else if( pLevel->wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ) ){
      /* Case 3: A scan using an index.
      **
      **         The WHERE clause may contain zero or more equality 
................................................................................
      /* Record the instruction used to terminate the loop. Disable 
      ** WHERE clause terms made redundant by the index range scan.
      */
      pLevel->op = bRev ? OP_Prev : OP_Next;
      pLevel->p1 = iIdxCur;
      disableTerm(pLevel, pRangeStart);
      disableTerm(pLevel, pRangeEnd);




























    }else{
      /* Case 4:  There is no usable index.  We must do a complete
      **          scan of the entire table.
      */
      assert( omitTable==0 );
      assert( bRev==0 );
      pLevel->op = OP_Next;
      pLevel->p1 = iCur;
      pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, OP_Rewind, iCur, addrBrk);







|







 







>
>







 







|
|




>
>
>
>
>
>
>
>
>
>
>
>
>
|







 







>
|
>
>
>







 







>
>
|













>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|
>




|
>
|


|
|
|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>













>
>
>
>
>







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|
|
|







 







<
|
|







 







>







 







|
|







 







<
|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

|







12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
..
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
..
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
..
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
...
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
...
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
...
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
...
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
...
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
...
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
...
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
...
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
....
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
....
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
....
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
....
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
....
1975
1976
1977
1978
1979
1980
1981

1982
1983
1984
1985
1986
1987
1988
1989
1990
....
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
....
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
....
2604
2605
2606
2607
2608
2609
2610

2611
2612
2613
2614
2615
2616
2617
2618
....
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is responsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.338 2008/12/17 19:22:16 drh Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
................................................................................
# define WHERETRACE(X)
#endif

/* Forward reference
*/
typedef struct WhereClause WhereClause;
typedef struct ExprMaskSet ExprMaskSet;
typedef struct WhereOrInfo WhereOrInfo;
typedef struct WhereAndInfo WhereAndInfo;

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by AND operators.
** (Note: the same data structure is also reused to hold a group of terms
** separated by OR operators.  But at the top-level, everything is AND
................................................................................
**        WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm
**
** When a term is of the form:
**
**              X <op> <expr>
**
** where X is a column name and <op> is one of certain operators,
** then WhereTerm.leftCursor and WhereTerm.u.leftColumn record the
** cursor number and column number for X.  WhereTerm.eOperator records
** the <op> using a bitmask encoding defined by WO_xxx below.  The
** 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,
** but they do so indirectly.  A single ExprMaskSet structure translates
** cursor number into bits and the translated bit is stored in the prereq
** fields.  The translation is used in order to maximize the number of
** bits that will fit in a Bitmask.  The VDBE cursor numbers might be
** spread out over the non-negative integers.  For example, the cursor
** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45.  The ExprMaskSet
** translates these sparse cursor numbers into consecutive integers
................................................................................
** is only able to process joins with 64 or fewer tables.
*/
typedef struct WhereTerm WhereTerm;
struct WhereTerm {
  Expr *pExpr;            /* Pointer to the subexpression that is this term */
  int iParent;            /* Disable pWC->a[iParent] when this term disabled */
  int leftCursor;         /* Cursor number of X in "X <op> <expr>" */
  union {
    int leftColumn;         /* Column number of X in "X <op> <expr>" */
    WhereOrInfo *pOrInfo;   /* Extra information if eOperator==WO_OR */
    WhereAndInfo *pAndInfo; /* Extra information if eOperator==WO_AND */
  } u;
  u16 eOperator;          /* A WO_xx value describing <op> */
  u8 wtFlags;             /* TERM_xxx bit flags.  See below */
  u8 nChild;              /* Number of children that must disable us */
  WhereClause *pWC;       /* The clause this term is part of */
  Bitmask prereqRight;    /* Bitmask of tables used by pExpr->pRight */
  Bitmask prereqAll;      /* Bitmask of tables referenced by pExpr */
};
................................................................................
/*
** Allowed values of WhereTerm.wtFlags
*/
#define TERM_DYNAMIC    0x01   /* Need to call sqlite3ExprDelete(db, pExpr) */
#define TERM_VIRTUAL    0x02   /* Added by the optimizer.  Do not code */
#define TERM_CODED      0x04   /* This term is already coded */
#define TERM_COPIED     0x08   /* Has a child */
#define TERM_ORINFO     0x10   /* Need to free the WhereTerm.u.pOrInfo object */
#define TERM_ANDINFO    0x20   /* Need to free the WhereTerm.u.pAndInfo obj */
#define TERM_OR_OK      0x40   /* Used during OR-clause processing */

/*
** An instance of the following structure holds all information about a
** WHERE clause.  Mostly this is a container for one or more WhereTerms.
*/
struct WhereClause {
  Parse *pParse;           /* The parser context */
  ExprMaskSet *pMaskSet;   /* Mapping of table indices to bitmasks */
  int nTerm;               /* Number of terms */
  int nSlot;               /* Number of entries in a[] */
  WhereTerm *a;            /* Each a[] describes a term of the WHERE cluase */
  WhereTerm aStatic[4];    /* Initial static space for a[] */
};

/*
** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to
** a dynamically allocated instance of the following structure.
*/
struct WhereOrInfo {
  WhereClause wc;          /* The OR subexpression broken out */
  double cost;             /* Cost of evaluating this OR subexpression */
};

/*
** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to
** a dynamically allocated instance of the following structure.
*/
struct WhereAndInfo {
  WhereClause wc;          /* The OR subexpression broken out */
  Index *pIdx;             /* Index to use */
  double cost;             /* Cost of evaluating this OR subexpression */
};

/*
** An instance of the following structure keeps track of a mapping
** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.
**
** The VDBE cursor numbers are small integers contained in 
** SrcList_item.iCursor and Expr.iTable fields.  For any given WHERE 
................................................................................
#define WO_EQ     0x002
#define WO_LT     (WO_EQ<<(TK_LT-TK_EQ))
#define WO_LE     (WO_EQ<<(TK_LE-TK_EQ))
#define WO_GT     (WO_EQ<<(TK_GT-TK_EQ))
#define WO_GE     (WO_EQ<<(TK_GE-TK_EQ))
#define WO_MATCH  0x040
#define WO_ISNULL 0x080
#define WO_OR     0x100       /* Two or more OR-connected terms */
#define WO_AND    0x200       /* Two or more AND-connected terms */

#define WO_ALL    0xfff       /* Mask of all possible WO_* values */

/*
** Value for wsFlags returned by bestIndex() and stored in
** WhereLevel.wsFlags.  These flags determine which search
** strategies are appropriate.
**
** The least significant 12 bits is reserved as a mask for WO_ values above.
** The WhereLevel.wsFlags field is usually set to WO_IN|WO_EQ|WO_ISNULL.
** But if the table is the right table of a left join, WhereLevel.wsFlags
** is set to WO_IN|WO_EQ.  The WhereLevel.wsFlags field can then be used as
** the "op" parameter to findTerm when we are resolving equality constraints.
** ISNULL constraints will then not be used on the right table of a left
** join.  Tickets #2177 and #2189.
*/
#define WHERE_ROWID_EQ     0x00001000  /* rowid=EXPR or rowid IN (...) */
#define WHERE_ROWID_RANGE  0x00002000  /* rowid<EXPR and/or rowid>EXPR */
#define WHERE_COLUMN_EQ    0x00010000  /* x=EXPR or x IN (...) */
................................................................................
){
  pWC->pParse = pParse;
  pWC->pMaskSet = pMaskSet;
  pWC->nTerm = 0;
  pWC->nSlot = ArraySize(pWC->aStatic);
  pWC->a = pWC->aStatic;
}

/* Forward reference */
static void whereClauseClear(WhereClause*);

/*
** Deallocate all memory associated with a WhereOrInfo object.
*/
static void whereOrInfoDelete(sqlite3 *db, WhereOrInfo *p){
  if( p ){
    whereClauseClear(&p->wc);
  }
}

/*
** Deallocate all memory associated with a WhereAndInfo object.
*/
static void whereAndInfoDelete(sqlite3 *db, WhereAndInfo *p){
  if( p ){
    whereClauseClear(&p->wc);
  }
}

/*
** Deallocate a WhereClause structure.  The WhereClause structure
** itself is not freed.  This routine is the inverse of whereClauseInit().
*/
static void whereClauseClear(WhereClause *pWC){
  int i;
  WhereTerm *a;
  sqlite3 *db = pWC->pParse->db;
  for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){
    if( a->wtFlags & TERM_DYNAMIC ){
      sqlite3ExprDelete(db, a->pExpr);
    }
    if( a->wtFlags & TERM_ORINFO ){
      whereOrInfoDelete(db, a->u.pOrInfo);
    }else if( a->wtFlags & TERM_ANDINFO ){
      whereAndInfoDelete(db, a->u.pAndInfo);
    }
  }
  if( pWC->a!=pWC->aStatic ){
    sqlite3DbFree(db, pWC->a);
  }
}

/*
................................................................................
  WhereTerm *pTerm;
  int k;
  assert( iCur>=0 );
  op &= WO_ALL;
  for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
    if( pTerm->leftCursor==iCur
       && (pTerm->prereqRight & notReady)==0
       && pTerm->u.leftColumn==iColumn
       && (pTerm->eOperator & op)!=0
    ){
      if( pIdx && pTerm->eOperator!=WO_ISNULL ){
        Expr *pX = pTerm->pExpr;
        CollSeq *pColl;
        char idxaff;
        int j;
................................................................................
*/
static int orTermIsOptCandidate(WhereTerm *pOrTerm, int iCursor, int iColumn){
  int affLeft, affRight;
  assert( pOrTerm->eOperator==WO_EQ );
  if( pOrTerm->leftCursor!=iCursor ){
    return 0;
  }
  if( pOrTerm->u.leftColumn!=iColumn ){
    return 0;
  }
  affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);
  if( affRight==0 ){
    return 1;
  }
  affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);
................................................................................
  pTerm->iParent = -1;
  pTerm->eOperator = 0;
  if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
    Expr *pLeft = pExpr->pLeft;
    Expr *pRight = pExpr->pRight;
    if( pLeft->op==TK_COLUMN ){
      pTerm->leftCursor = pLeft->iTable;
      pTerm->u.leftColumn = pLeft->iColumn;
      pTerm->eOperator = operatorMask(op);
    }
    if( pRight && pRight->op==TK_COLUMN ){
      WhereTerm *pNew;
      Expr *pDup;
      if( pTerm->leftCursor>=0 ){
        int idxNew;
................................................................................
      }else{
        pDup = pExpr;
        pNew = pTerm;
      }
      exprCommute(pParse, pDup);
      pLeft = pDup->pLeft;
      pNew->leftCursor = pLeft->iTable;
      pNew->u.leftColumn = pLeft->iColumn;
      pNew->prereqRight = prereqLeft;
      pNew->prereqAll = prereqAll;
      pNew->eOperator = operatorMask(pDup->op);
    }
  }

#ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
................................................................................
    whereSplit(&sOr, pExpr, TK_OR);
    exprAnalyzeAll(pSrc, &sOr);
    assert( sOr.nTerm>=2 );
    j = 0;
    if( db->mallocFailed ) goto or_not_possible;
    do{
      assert( j<sOr.nTerm );
      iColumn = sOr.a[j].u.leftColumn;
      iCursor = sOr.a[j].leftCursor;
      ok = iCursor>=0;
      for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){
        if( pOrTerm->eOperator!=WO_EQ ){
          goto or_not_possible;
        }
        if( orTermIsOptCandidate(pOrTerm, iCursor, iColumn) ){
................................................................................
      Expr *pNewExpr;
      pNewExpr = sqlite3Expr(db, TK_MATCH, 0, sqlite3ExprDup(db, pRight), 0);
      idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
      testcase( idxNew==0 );
      pNewTerm = &pWC->a[idxNew];
      pNewTerm->prereqRight = prereqExpr;
      pNewTerm->leftCursor = pLeft->iTable;
      pNewTerm->u.leftColumn = pLeft->iColumn;
      pNewTerm->eOperator = WO_MATCH;
      pNewTerm->iParent = idxTerm;
      pTerm = &pWC->a[idxTerm];
      pTerm->nChild = 1;
      pTerm->wtFlags |= TERM_COPIED;
      pNewTerm->prereqAll = pTerm->prereqAll;
    }
................................................................................

    for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
      if( pTerm->leftCursor != pSrc->iCursor ) continue;
      assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
      testcase( pTerm->eOperator==WO_IN );
      testcase( pTerm->eOperator==WO_ISNULL );
      if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
      pIdxCons[j].iColumn = pTerm->u.leftColumn;
      pIdxCons[j].iTermOffset = i;
      pIdxCons[j].op = (u8)pTerm->eOperator;
      /* The direct assignment in the previous line is possible only because
      ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical.  The
      ** following asserts verify this fact. */
      assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
      assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
................................................................................
  
    /* Check for constraints on a range of rowids in a table scan.
    */
    pTerm = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE|WO_GT|WO_GE, 0);
    if( pTerm ){
      if( findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0) ){
        wsFlags |= WHERE_TOP_LIMIT;
        cost /= 3;  /* Guess that rowid<EXPR eliminates two-thirds of rows */
      }
      if( findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0) ){
        wsFlags |= WHERE_BTM_LIMIT;
        cost /= 3;  /* Guess that rowid>EXPR eliminates two-thirds of rows */
      }
      WHERETRACE(("... rowid range reduces cost to %.9g\n", cost));
    }else{
................................................................................
** a==5 and b IN (1,2,3).  The current values for a and b will be left
** on the stack - a is the deepest and b the shallowest.
**
** In the example above nEq==2.  But this subroutine works for any value
** of nEq including 0.  If nEq==0, this routine is nearly a no-op.
** The only thing it does is allocate the pLevel->iMem memory cell.
**
** This routine always allocates at least one memory cell and returns
** the index of that memory cell. The code that
** calls this routine will use that memory cell to store the termination
** key value of the loop.  If one or more IN operators appear, then
** this routine allocates an additional nEq memory cells for internal
** use.
*/
static int codeAllEqualityTerms(
  Parse *pParse,        /* Parsing context */
  WhereLevel *pLevel,   /* Which nested loop of the FROM we are coding */
................................................................................
  int regBase;                  /* Base register */

  /* Figure out how many memory cells we will need then allocate them.
  ** We always need at least one used to store the loop terminator
  ** value.  If there are IN operators we'll need one for each == or
  ** IN constraint.
  */

  regBase = pParse->nMem + 1;
  pParse->nMem += pLevel->nEq + 1 + nExtraReg;

  /* Evaluate the equality constraints
  */
  assert( pIdx->nColumn>=nEq );
  for(j=0; j<nEq; j++){
    int r1;
    int k = pIdx->aiColumn[j];
................................................................................
      VdbeComment((v, "pk"));
      pLevel->op = OP_Noop;
    }else if( pLevel->wsFlags & WHERE_ROWID_RANGE ){
      /* Case 2:  We have an inequality comparison against the ROWID field.
      */
      int testOp = OP_Noop;
      int start;
      int memEndValue = 0;
      WhereTerm *pStart, *pEnd;

      assert( omitTable==0 );
      pStart = findTerm(&wc, iCur, -1, notReady, WO_GT|WO_GE, 0);
      pEnd = findTerm(&wc, iCur, -1, notReady, WO_LT|WO_LE, 0);
      if( bRev ){
        pTerm = pStart;
................................................................................
        sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrBrk);
      }
      if( pEnd ){
        Expr *pX;
        pX = pEnd->pExpr;
        assert( pX!=0 );
        assert( pEnd->leftCursor==iCur );
        memEndValue = ++pParse->nMem;
        sqlite3ExprCode(pParse, pX->pRight, memEndValue);
        if( pX->op==TK_LT || pX->op==TK_GT ){
          testOp = bRev ? OP_Le : OP_Ge;
        }else{
          testOp = bRev ? OP_Lt : OP_Gt;
        }
        disableTerm(pLevel, pEnd);
      }
................................................................................
      start = sqlite3VdbeCurrentAddr(v);
      pLevel->op = bRev ? OP_Prev : OP_Next;
      pLevel->p1 = iCur;
      pLevel->p2 = start;
      if( testOp!=OP_Noop ){
        int r1 = sqlite3GetTempReg(pParse);
        sqlite3VdbeAddOp2(v, OP_Rowid, iCur, r1);

        sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, r1);
        sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
        sqlite3ReleaseTempReg(pParse, r1);
      }
    }else if( pLevel->wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ) ){
      /* Case 3: A scan using an index.
      **
      **         The WHERE clause may contain zero or more equality 
................................................................................
      /* Record the instruction used to terminate the loop. Disable 
      ** WHERE clause terms made redundant by the index range scan.
      */
      pLevel->op = bRev ? OP_Prev : OP_Next;
      pLevel->p1 = iIdxCur;
      disableTerm(pLevel, pRangeStart);
      disableTerm(pLevel, pRangeEnd);
    }else if( pLevel->wsFlags & WHERE_MULTI_OR ){
      /* Case 4:  Two or more separately indexed terms connected by OR
      **
      ** Example:
      **
      **   CREATE TABLE t1(a,b,c,d);
      **   CREATE INDEX i1 ON t1(a);
      **   CREATE INDEX i2 ON t1(b);
      **   CREATE INDEX i3 ON t1(c);
      **
      **   SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
      **
      ** In the example, there are three indexed terms connected by OR.
      ** The top of the loop is constructed by creating a RowSet object
      ** and populating it.  Then looping over elements of the rowset.
      **
      **        Null 1
      **        # fill RowSet 1 with entries where a=5 using i1
      **        # fill Rowset 1 with entries where b=7 using i2
      **        # fill Rowset 1 with entries where c=11 and d=13 i3 and t1
      **     A: RowSetRead 1, B, 2
      **        Seek       i, 2
      **
      ** The bottom of the loop looks like this:
      **
      **     C: Goto       0, A
      **     B:
      */
    }else{
      /* Case 5:  There is no usable index.  We must do a complete
      **          scan of the entire table.
      */
      assert( omitTable==0 );
      assert( bRev==0 );
      pLevel->op = OP_Next;
      pLevel->p1 = iCur;
      pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, OP_Rewind, iCur, addrBrk);