/ Check-in [56d0e326]
Login

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

Overview
Comment:Optimisations for expressions of the form "<value> IN (SELECT <column> FROM )". (CVS 4579)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 56d0e32677744df8570b519fae1c04da4ea4984d
User & Date: danielk1977 2007-11-29 17:05:18
Context
2007-11-29
17:43
When using an index to scan a database table, read column data from the index in preference to the table. This increases the likelihood that the table will not be required at all. (CVS 4580) check-in: 061608c7 user: danielk1977 tags: trunk
17:05
Optimisations for expressions of the form "<value> IN (SELECT <column> FROM )". (CVS 4579)
check-in: 56d0e326 user: danielk1977 tags: trunk
2007-11-28
22:36
Add the {quote: StrAccum} object for accumulating strings. Revamp xprintf to use the new object. Rewrite the group_concat() function to use the new object. Productize and test the group_concat() function. (CVS 4578) check-in: 221aee72 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/expr.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
....
1518
1519
1520
1521
1522
1523
1524









































































































































1525
1526
1527
1528
1529
1530
1531
....
2032
2033
2034
2035
2036
2037
2038
2039



2040
2041
2042
2043
2044
2045
2046
....
2051
2052
2053
2054
2055
2056
2057
2058






2059
2060

2061

2062
2063
2064
2065
2066
2067
2068
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains routines used for analyzing expressions and
** for generating VDBE code that evaluates expressions in SQLite.
**
** $Id: expr.c,v 1.316 2007/11/12 09:50:26 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** Return the 'affinity' of the expression pExpr if any.
**
................................................................................
*/
typedef struct QueryCoder QueryCoder;
struct QueryCoder {
  Parse *pParse;       /* The parsing context */
  NameContext *pNC;    /* Namespace of first enclosing query */
};











































































































































/*
** Generate code for scalar subqueries used as an expression
** and IN operators.  Examples:
**
**     (SELECT a FROM b)          -- subquery
**     EXISTS (SELECT a FROM b)   -- EXISTS subquery
................................................................................
      VdbeComment((v, "# load subquery result"));
      break;
    }
    case TK_IN: {
      int addr;
      char affinity;
      int ckOffset = pParse->ckOffset;
      sqlite3CodeSubselect(pParse, pExpr);




      /* Figure out the affinity to use to create a key from the results
      ** of the expression. affinityStr stores a static string suitable for
      ** P3 of OP_MakeRecord.
      */
      affinity = comparisonAffinity(pExpr);

................................................................................
      ** pExpr->iTable contains the values that make up the (...) set.
      */
      sqlite3ExprCode(pParse, pExpr->pLeft);
      addr = sqlite3VdbeCurrentAddr(v);
      sqlite3VdbeAddOp(v, OP_NotNull, -1, addr+4);            /* addr + 0 */
      sqlite3VdbeAddOp(v, OP_Pop, 2, 0);
      sqlite3VdbeAddOp(v, OP_Null, 0, 0);
      sqlite3VdbeAddOp(v, OP_Goto, 0, addr+7);






      sqlite3VdbeOp3(v, OP_MakeRecord, 1, 0, &affinity, 1);   /* addr + 4 */
      sqlite3VdbeAddOp(v, OP_Found, pExpr->iTable, addr+7);

      sqlite3VdbeAddOp(v, OP_AddImm, -1, 0);                  /* addr + 6 */


      break;
    }
#endif
    case TK_BETWEEN: {
      Expr *pLeft = pExpr->pLeft;
      struct ExprList_item *pLItem = pExpr->pList->a;







|







 







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







 







|
>
>
>







 







|
>
>
>
>
>
>
|
|
>

>







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
....
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
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
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
....
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
....
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains routines used for analyzing expressions and
** for generating VDBE code that evaluates expressions in SQLite.
**
** $Id: expr.c,v 1.317 2007/11/29 17:05:18 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** Return the 'affinity' of the expression pExpr if any.
**
................................................................................
*/
typedef struct QueryCoder QueryCoder;
struct QueryCoder {
  Parse *pParse;       /* The parsing context */
  NameContext *pNC;    /* Namespace of first enclosing query */
};

#ifdef SQLITE_TEST
  int sqlite3_enable_in_opt = 1;
#else
  #define sqlite3_enable_in_opt 1
#endif

/*
** This function is used by the implementation of the IN (...) operator.
** It's job is to find or create a b-tree structure that may be used
** either to test for membership of the (...) set or to iterate through
** it's members, skipping duplicates.
**
** The cursor opened on the structure (database table, database index 
** or ephermal table) is stored in pX->iTable before this function returns.
** The returned value indicates the structure type, as follows:
**
**   IN_INDEX_ROWID - The cursor was opened on a database table.
**   IN_INDEX_INDEX - The cursor was opened on a database indec.
**   IN_INDEX_EPH -   The cursor was opened on a specially created and
**                    populated epheremal table.
**
** An existing structure may only be used if the SELECT is of the simple
** form:
**
**     SELECT <column> FROM <table>
**
** If the mustBeUnique parameter is false, the structure will be used 
** for fast set membership tests. In this case an epheremal table must 
** be used unless <column> is an INTEGER PRIMARY KEY or an index can 
** be found with <column> as it's left-most column.
**
** If mustBeUnique is true, then the structure will be used to iterate
** through the set members, skipping any duplicates. In this case an
** epheremal table must be used unless the selected <column> is guaranteed
** to be unique - either because it is an INTEGER PRIMARY KEY or it
** is unique by virtue of a constraint or implicit index.
*/
int sqlite3FindInIndex(Parse *pParse, Expr *pX, int mustBeUnique){
  Select *p;
  int eType = 0;
  int iTab = pParse->nTab++;

  /* The follwing if(...) expression is true if the SELECT is of the 
  ** simple form:
  **
  **     SELECT <column> FROM <table>
  **
  ** If this is the case, it may be possible to use an existing table
  ** or index instead of generating an epheremal table.
  */
  if( sqlite3_enable_in_opt
   && (p=pX->pSelect) && !p->pPrior
   && !p->isDistinct && !p->isAgg && !p->pGroupBy
   && p->pSrc && p->pSrc->nSrc==1 && !p->pSrc->a[0].pSelect
   && !p->pSrc->a[0].pTab->pSelect                                  
   && p->pEList->nExpr==1 && p->pEList->a[0].pExpr->op==TK_COLUMN
   && !p->pLimit && !p->pOffset && !p->pWhere
  ){
    sqlite3 *db = pParse->db;
    Index *pIdx;
    Expr *pExpr = p->pEList->a[0].pExpr;
    int iCol = pExpr->iColumn;
    Vdbe *v = sqlite3GetVdbe(pParse);

    /* This function is only called from two places. In both cases the vdbe
    ** has already been allocated. So assume sqlite3GetVdbe() is always
    ** successful here.
    */
    assert(v);
    if( iCol<0 ){
      int iMem = pParse->nMem++;
      int iAddr;
      Table *pTab = p->pSrc->a[0].pTab;
      int iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
      sqlite3VdbeUsesBtree(v, iDb);

      sqlite3VdbeAddOp(v, OP_MemLoad, iMem, 0);
      iAddr = sqlite3VdbeAddOp(v, OP_If, 0, iMem);
      sqlite3VdbeAddOp(v, OP_MemInt, 1, iMem);

      sqlite3OpenTable(pParse, iTab, iDb, pTab, OP_OpenRead);
      eType = IN_INDEX_ROWID;

      sqlite3VdbeJumpHere(v, iAddr);
    }else{
      /* The collation sequence used by the comparison. If an index is to 
      ** be used in place of a temp-table, it must be ordered according
      ** to this collation sequence.
      */
      CollSeq *pReq = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pExpr);

      /* Check that the affinity that will be used to perform the 
      ** comparison is the same as the affinity of the column. If
      ** it is not, it is not possible to use any index.
      */
      Table *pTab = p->pSrc->a[0].pTab;
      char aff = comparisonAffinity(pX);
      int affinity_ok = (pTab->aCol[iCol].affinity==aff||aff==SQLITE_AFF_NONE);

      for(pIdx=pTab->pIndex; pIdx && eType==0 && affinity_ok; pIdx=pIdx->pNext){
        if( (pIdx->aiColumn[0]==iCol)
         && (pReq==sqlite3FindCollSeq(db, ENC(db), pIdx->azColl[0], -1, 0))
         && (!mustBeUnique || (pIdx->nColumn==1 && pIdx->onError!=OE_None))
        ){
          int iDb;
          int iMem = pParse->nMem++;
          int iAddr;
          char *pKey;
  
          pKey = (char *)sqlite3IndexKeyinfo(pParse, pIdx);
          iDb = sqlite3SchemaToIndex(db, pIdx->pSchema);
          sqlite3VdbeUsesBtree(v, iDb);

          sqlite3VdbeAddOp(v, OP_MemLoad, iMem, 0);
          iAddr = sqlite3VdbeAddOp(v, OP_If, 0, iMem);
          sqlite3VdbeAddOp(v, OP_MemInt, 1, iMem);
  
          sqlite3VdbeAddOp(v, OP_Integer, iDb, 0);
          VdbeComment((v, "# %s", pIdx->zName));
          sqlite3VdbeOp3(v,OP_OpenRead,iTab,pIdx->tnum,pKey,P3_KEYINFO_HANDOFF);
          eType = IN_INDEX_INDEX;
          sqlite3VdbeAddOp(v, OP_SetNumColumns, iTab, pIdx->nColumn);

          sqlite3VdbeJumpHere(v, iAddr);
        }
      }
    }
  }

  if( eType==0 ){
    sqlite3CodeSubselect(pParse, pX);
    eType = IN_INDEX_EPH;
  }else{
    pX->iTable = iTab;
  }
  return eType;
}

/*
** Generate code for scalar subqueries used as an expression
** and IN operators.  Examples:
**
**     (SELECT a FROM b)          -- subquery
**     EXISTS (SELECT a FROM b)   -- EXISTS subquery
................................................................................
      VdbeComment((v, "# load subquery result"));
      break;
    }
    case TK_IN: {
      int addr;
      char affinity;
      int ckOffset = pParse->ckOffset;
      int eType;
      int iLabel = sqlite3VdbeMakeLabel(v);

      eType = sqlite3FindInIndex(pParse, pExpr, 0);

      /* Figure out the affinity to use to create a key from the results
      ** of the expression. affinityStr stores a static string suitable for
      ** P3 of OP_MakeRecord.
      */
      affinity = comparisonAffinity(pExpr);

................................................................................
      ** pExpr->iTable contains the values that make up the (...) set.
      */
      sqlite3ExprCode(pParse, pExpr->pLeft);
      addr = sqlite3VdbeCurrentAddr(v);
      sqlite3VdbeAddOp(v, OP_NotNull, -1, addr+4);            /* addr + 0 */
      sqlite3VdbeAddOp(v, OP_Pop, 2, 0);
      sqlite3VdbeAddOp(v, OP_Null, 0, 0);
      sqlite3VdbeAddOp(v, OP_Goto, 0, iLabel);
      if( eType==IN_INDEX_ROWID ){
        int iAddr = sqlite3VdbeCurrentAddr(v)+3;
        sqlite3VdbeAddOp(v, OP_MustBeInt, 1, iAddr);
        sqlite3VdbeAddOp(v, OP_NotExists, pExpr->iTable, iAddr);
        sqlite3VdbeAddOp(v, OP_Goto, pExpr->iTable, iLabel);
      }else{
        sqlite3VdbeOp3(v, OP_MakeRecord, 1, 0, &affinity, 1);   /* addr + 4 */
        sqlite3VdbeAddOp(v, OP_Found, pExpr->iTable, iLabel);
      }
      sqlite3VdbeAddOp(v, OP_AddImm, -1, 0);                  /* addr + 6 */
      sqlite3VdbeResolveLabel(v, iLabel);

      break;
    }
#endif
    case TK_BETWEEN: {
      Expr *pLeft = pExpr->pLeft;
      struct ExprList_item *pLItem = pExpr->pList->a;

Changes to src/sqliteInt.h.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
880
881
882
883
884
885
886

887
888
889
890
891
892
893
....
1967
1968
1969
1970
1971
1972
1973





1974
1975
1976
1977
1978
1979
1980
**    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.621 2007/11/28 22:36:41 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** The macro unlikely() is a hint that surrounds a boolean
** expression that is usually false.  Macro likely() surrounds
................................................................................
** otherwise be equal, then return a result as if the second key
** were larger.
*/
struct KeyInfo {
  sqlite3 *db;        /* The database connection */
  u8 enc;             /* Text encoding - one of the TEXT_Utf* values */
  u8 incrKey;         /* Increase 2nd key by epsilon before comparison */

  int nField;         /* Number of entries in aColl[] */
  u8 *aSortOrder;     /* If defined an aSortOrder[i] is true, sort DESC */
  CollSeq *aColl[1];  /* Collating sequence for each term of the key */
};

/*
** Each SQL index is represented in memory by an
................................................................................
int sqlite3VtabBegin(sqlite3 *, sqlite3_vtab *);
FuncDef *sqlite3VtabOverloadFunction(sqlite3 *,FuncDef*, int nArg, Expr*);
void sqlite3InvalidFunction(sqlite3_context*,int,sqlite3_value**);
int sqlite3Reprepare(Vdbe*);
void sqlite3ExprListCheckLength(Parse*, ExprList*, int, const char*);
CollSeq *sqlite3BinaryCompareCollSeq(Parse *, Expr *, Expr *);






#ifdef SQLITE_ENABLE_ATOMIC_WRITE
  int sqlite3JournalOpen(sqlite3_vfs *, const char *, sqlite3_file *, int, int);
  int sqlite3JournalSize(sqlite3_vfs *);
  int sqlite3JournalCreate(sqlite3_file *);
#else
  #define sqlite3JournalSize(pVfs) ((pVfs)->szOsFile)
#endif







|







 







>







 







>
>
>
>
>







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
....
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
**    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.622 2007/11/29 17:05:18 danielk1977 Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** The macro unlikely() is a hint that surrounds a boolean
** expression that is usually false.  Macro likely() surrounds
................................................................................
** otherwise be equal, then return a result as if the second key
** were larger.
*/
struct KeyInfo {
  sqlite3 *db;        /* The database connection */
  u8 enc;             /* Text encoding - one of the TEXT_Utf* values */
  u8 incrKey;         /* Increase 2nd key by epsilon before comparison */
  u8 prefixIsEqual;   /* Treat a prefix as equal */
  int nField;         /* Number of entries in aColl[] */
  u8 *aSortOrder;     /* If defined an aSortOrder[i] is true, sort DESC */
  CollSeq *aColl[1];  /* Collating sequence for each term of the key */
};

/*
** Each SQL index is represented in memory by an
................................................................................
int sqlite3VtabBegin(sqlite3 *, sqlite3_vtab *);
FuncDef *sqlite3VtabOverloadFunction(sqlite3 *,FuncDef*, int nArg, Expr*);
void sqlite3InvalidFunction(sqlite3_context*,int,sqlite3_value**);
int sqlite3Reprepare(Vdbe*);
void sqlite3ExprListCheckLength(Parse*, ExprList*, int, const char*);
CollSeq *sqlite3BinaryCompareCollSeq(Parse *, Expr *, Expr *);

#define IN_INDEX_ROWID           1
#define IN_INDEX_EPH             2
#define IN_INDEX_INDEX           3
int sqlite3FindInIndex(Parse *, Expr *, int);

#ifdef SQLITE_ENABLE_ATOMIC_WRITE
  int sqlite3JournalOpen(sqlite3_vfs *, const char *, sqlite3_file *, int, int);
  int sqlite3JournalSize(sqlite3_vfs *);
  int sqlite3JournalCreate(sqlite3_file *);
#else
  #define sqlite3JournalSize(pVfs) ((pVfs)->szOsFile)
#endif

Changes to src/test1.c.

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
....
4429
4430
4431
4432
4433
4434
4435

4436
4437
4438
4439
4440
4441
4442
....
4508
4509
4510
4511
4512
4513
4514




4515
4516
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing all sorts of SQLite interfaces.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test1.c,v 1.279 2007/10/23 15:39:45 drh Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>

/*
................................................................................
#endif
#ifdef SQLITE_DEBUG
  extern int sqlite3_where_trace;
  extern int sqlite3_os_trace;
  extern int sqlite3_vdbe_addop_trace;
#endif
#ifdef SQLITE_TEST

  extern char sqlite3_query_plan[];
  static char *query_plan = sqlite3_query_plan;
#endif

  for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
    Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);
  }
................................................................................
      (char*)&sqlite3_temp_directory, TCL_LINK_STRING);
  Tcl_LinkVar(interp, "bitmask_size",
      (char*)&bitmask_size, TCL_LINK_INT|TCL_LINK_READ_ONLY);
  Tcl_LinkVar(interp, "sqlite_sync_count",
      (char*)&sqlite3_sync_count, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_fullsync_count",
      (char*)&sqlite3_fullsync_count, TCL_LINK_INT);




  return TCL_OK;
}







|







 







>







 







>
>
>
>


9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
....
4429
4430
4431
4432
4433
4434
4435
4436
4437
4438
4439
4440
4441
4442
4443
....
4509
4510
4511
4512
4513
4514
4515
4516
4517
4518
4519
4520
4521
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing all sorts of SQLite interfaces.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test1.c,v 1.280 2007/11/29 17:05:18 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>

/*
................................................................................
#endif
#ifdef SQLITE_DEBUG
  extern int sqlite3_where_trace;
  extern int sqlite3_os_trace;
  extern int sqlite3_vdbe_addop_trace;
#endif
#ifdef SQLITE_TEST
  extern int sqlite3_enable_in_opt;
  extern char sqlite3_query_plan[];
  static char *query_plan = sqlite3_query_plan;
#endif

  for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
    Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);
  }
................................................................................
      (char*)&sqlite3_temp_directory, TCL_LINK_STRING);
  Tcl_LinkVar(interp, "bitmask_size",
      (char*)&bitmask_size, TCL_LINK_INT|TCL_LINK_READ_ONLY);
  Tcl_LinkVar(interp, "sqlite_sync_count",
      (char*)&sqlite3_sync_count, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_fullsync_count",
      (char*)&sqlite3_fullsync_count, TCL_LINK_INT);
#ifdef SQLITE_TEST
  Tcl_LinkVar(interp, "sqlite_enable_in_opt",
      (char*)&sqlite3_enable_in_opt, TCL_LINK_INT);
#endif
  return TCL_OK;
}

Changes to src/vdbe.c.

39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
....
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
....
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063





3064
3065
3066
3067
3068
3069
3070
....
3086
3087
3088
3089
3090
3091
3092



3093

3094
3095
3096
3097
3098
3099
3100
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.654 2007/11/12 08:09:35 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
** The following global variable is incremented every time a cursor
................................................................................
  break;
}

/* Opcode: MustBeInt P1 P2 *
** 
** Force the top of the stack to be an integer.  If the top of the
** stack is not an integer and cannot be converted into an integer
** with out data loss, then jump immediately to P2, or if P2==0
** raise an SQLITE_MISMATCH exception.
**
** If the top of the stack is not an integer and P2 is not zero and
** P1 is 1, then the stack is popped.  In all other cases, the depth
** of the stack is unchanged.
*/
case OP_MustBeInt: {            /* no-push */
................................................................................
** Top of the stack holds a blob constructed by MakeRecord.  P1 is an index.
** If an entry that matches the top of the stack exists in P1 then
** jump to P2.  If the top of the stack does not match any entry in P1
** then fall thru.  The P1 cursor is left pointing at the matching entry
** if it exists.  The blob is popped off the top of the stack.
**
** This instruction is used to implement the IN operator where the
** left-hand side is a SELECT statement.  P1 is not a true index but
** is instead a temporary index that holds the results of the SELECT
** statement.  This instruction just checks to see if the left-hand side
** of the IN operator (stored on the top of the stack) exists in the
** result of the SELECT statement.





**
** See also: Distinct, NotFound, MoveTo, IsUnique, NotExists
*/
/* Opcode: NotFound P1 P2 *
**
** The top of the stack holds a blob constructed by MakeRecord.  P1 is
** an index.  If no entry exists in P1 that matches the blob then jump
................................................................................
  assert( i>=0 && i<p->nCursor );
  assert( p->apCsr[i]!=0 );
  if( (pC = p->apCsr[i])->pCursor!=0 ){
    int res;
    assert( pC->isTable==0 );
    assert( pTos->flags & MEM_Blob );
    Stringify(pTos, encoding);



    rc = sqlite3BtreeMoveto(pC->pCursor, pTos->z, pTos->n, 0, &res);

    if( rc!=SQLITE_OK ){
      break;
    }
    alreadyExists = (res==0);
    pC->deferredMoveto = 0;
    pC->cacheStatus = CACHE_STALE;
  }







|







 







|







 







|
|
<
<
|
>
>
>
>
>







 







>
>
>

>







39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
....
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
....
3052
3053
3054
3055
3056
3057
3058
3059
3060


3061
3062
3063
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
....
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.655 2007/11/29 17:05:18 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
** The following global variable is incremented every time a cursor
................................................................................
  break;
}

/* Opcode: MustBeInt P1 P2 *
** 
** Force the top of the stack to be an integer.  If the top of the
** stack is not an integer and cannot be converted into an integer
** without data loss, then jump immediately to P2, or if P2==0
** raise an SQLITE_MISMATCH exception.
**
** If the top of the stack is not an integer and P2 is not zero and
** P1 is 1, then the stack is popped.  In all other cases, the depth
** of the stack is unchanged.
*/
case OP_MustBeInt: {            /* no-push */
................................................................................
** Top of the stack holds a blob constructed by MakeRecord.  P1 is an index.
** If an entry that matches the top of the stack exists in P1 then
** jump to P2.  If the top of the stack does not match any entry in P1
** then fall thru.  The P1 cursor is left pointing at the matching entry
** if it exists.  The blob is popped off the top of the stack.
**
** This instruction is used to implement the IN operator where the
** left-hand side is a SELECT statement.  P1 may be a true index, or it
** may be a temporary index that holds the results of the SELECT


** statement. 
**
** This instruction checks if index P1 contains a record for which 
** the first N serialised values exactly match the N serialised values
** in the record on the stack, where N is the total number of values in
** the stack record (stack record is a prefix of the P1 record). 
**
** See also: Distinct, NotFound, MoveTo, IsUnique, NotExists
*/
/* Opcode: NotFound P1 P2 *
**
** The top of the stack holds a blob constructed by MakeRecord.  P1 is
** an index.  If no entry exists in P1 that matches the blob then jump
................................................................................
  assert( i>=0 && i<p->nCursor );
  assert( p->apCsr[i]!=0 );
  if( (pC = p->apCsr[i])->pCursor!=0 ){
    int res;
    assert( pC->isTable==0 );
    assert( pTos->flags & MEM_Blob );
    Stringify(pTos, encoding);
    if( pOp->opcode==OP_Found ){
      pC->pKeyInfo->prefixIsEqual = 1;
    }
    rc = sqlite3BtreeMoveto(pC->pCursor, pTos->z, pTos->n, 0, &res);
    pC->pKeyInfo->prefixIsEqual = 0;
    if( rc!=SQLITE_OK ){
      break;
    }
    alreadyExists = (res==0);
    pC->deferredMoveto = 0;
    pC->cacheStatus = CACHE_STALE;
  }

Changes to src/vdbeaux.c.

2107
2108
2109
2110
2111
2112
2113

2114
2115
2116
2117

2118
2119
2120
2121
2122
2123
2124
  /* One of the keys ran out of fields, but all the fields up to that point
  ** were equal. If the incrKey flag is true, then the second key is
  ** treated as larger.
  */
  if( rc==0 ){
    if( pKeyInfo->incrKey ){
      rc = -1;

    }else if( d1<nKey1 ){
      rc = 1;
    }else if( d2<nKey2 ){
      rc = -1;

    }
  }else if( pKeyInfo->aSortOrder && i<pKeyInfo->nField
               && pKeyInfo->aSortOrder[i] ){
    rc = -rc;
  }

  return rc;







>
|
|
|
|
>







2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
  /* One of the keys ran out of fields, but all the fields up to that point
  ** were equal. If the incrKey flag is true, then the second key is
  ** treated as larger.
  */
  if( rc==0 ){
    if( pKeyInfo->incrKey ){
      rc = -1;
    }else if( !pKeyInfo->prefixIsEqual ){
      if( d1<nKey1 ){
        rc = 1;
      }else if( d2<nKey2 ){
        rc = -1;
      }
    }
  }else if( pKeyInfo->aSortOrder && i<pKeyInfo->nField
               && pKeyInfo->aSortOrder[i] ){
    rc = -rc;
  }

  return rc;

Changes to src/where.c.

12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
....
1732
1733
1734
1735
1736
1737
1738

1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754

1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is reponsible 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.263 2007/11/26 13:36:00 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
  Vdbe *v = pParse->pVdbe;
  if( pX->op==TK_EQ ){
    sqlite3ExprCode(pParse, pX->pRight);
  }else if( pX->op==TK_ISNULL ){
    sqlite3VdbeAddOp(v, OP_Null, 0, 0);
#ifndef SQLITE_OMIT_SUBQUERY
  }else{

    int iTab;
    struct InLoop *pIn;

    assert( pX->op==TK_IN );
    sqlite3CodeSubselect(pParse, pX);
    iTab = pX->iTable;
    sqlite3VdbeAddOp(v, OP_Rewind, iTab, 0);
    VdbeComment((v, "# %.*s", pX->span.n, pX->span.z));
    if( pLevel->nIn==0 ){
      pLevel->nxt = sqlite3VdbeMakeLabel(v);
    }
    pLevel->nIn++;
    pLevel->aInLoop = sqlite3DbReallocOrFree(pParse->db, pLevel->aInLoop,
                                    sizeof(pLevel->aInLoop[0])*pLevel->nIn);
    pIn = pLevel->aInLoop;
    if( pIn ){

      pIn += pLevel->nIn - 1;
      pIn->iCur = iTab;
      pIn->topAddr = sqlite3VdbeAddOp(v, OP_Column, iTab, 0);
      sqlite3VdbeAddOp(v, OP_IsNull, -1, 0);
    }else{
      pLevel->nIn = 0;
    }
#endif
  }
  disableTerm(pLevel, pTerm);







|







 







>




|











>


|







12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
....
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is reponsible 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.264 2007/11/29 17:05:18 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
................................................................................
  Vdbe *v = pParse->pVdbe;
  if( pX->op==TK_EQ ){
    sqlite3ExprCode(pParse, pX->pRight);
  }else if( pX->op==TK_ISNULL ){
    sqlite3VdbeAddOp(v, OP_Null, 0, 0);
#ifndef SQLITE_OMIT_SUBQUERY
  }else{
    int eType;
    int iTab;
    struct InLoop *pIn;

    assert( pX->op==TK_IN );
    eType = sqlite3FindInIndex(pParse, pX, 1);
    iTab = pX->iTable;
    sqlite3VdbeAddOp(v, OP_Rewind, iTab, 0);
    VdbeComment((v, "# %.*s", pX->span.n, pX->span.z));
    if( pLevel->nIn==0 ){
      pLevel->nxt = sqlite3VdbeMakeLabel(v);
    }
    pLevel->nIn++;
    pLevel->aInLoop = sqlite3DbReallocOrFree(pParse->db, pLevel->aInLoop,
                                    sizeof(pLevel->aInLoop[0])*pLevel->nIn);
    pIn = pLevel->aInLoop;
    if( pIn ){
      int op = ((eType==IN_INDEX_ROWID)?OP_Rowid:OP_Column);
      pIn += pLevel->nIn - 1;
      pIn->iCur = iTab;
      pIn->topAddr = sqlite3VdbeAddOp(v, op, iTab, 0);
      sqlite3VdbeAddOp(v, OP_IsNull, -1, 0);
    }else{
      pLevel->nIn = 0;
    }
#endif
  }
  disableTerm(pLevel, pTerm);

Added test/in3.test.

















































































































































































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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
87
88
89
90
91
92
93
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
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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
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
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
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
# 2007 November 29
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    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.
#
#***********************************************************************
# This file tests the optimisations made in November 2007 of expressions 
# of the following form:
#
#     <value> IN (SELECT <column> FROM <table>)
#
# $Id: in3.test,v 1.1 2007/11/29 17:05:18 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Return the number of OpenEphemeral instructions used in the
# implementation of the sql statement passed as a an argument.
#
proc nEphemeral {sql} {
  set nEph 0
  foreach op [execsql "EXPLAIN $sql"] {
    if {$op eq "OpenEphemeral"} {incr nEph}
  }
  set nEph
}

# This proc works the same way as execsql, except that the number
# of OpenEphemeral instructions used in the implementation of the
# statement is inserted into the start of the returned list.
#
proc exec_neph {sql} {
  return [concat [nEphemeral $sql] [execsql $sql]]
}

do_test in3-1.1 {
  execsql {
    CREATE TABLE t1(a PRIMARY KEY, b);
    INSERT INTO t1 VALUES(1, 2);
    INSERT INTO t1 VALUES(3, 4);
    INSERT INTO t1 VALUES(5, 6);
  }
} {}

# All of these queries should avoid using a temp-table:
#
do_test in3-1.2 {
  exec_neph { SELECT rowid FROM t1 WHERE rowid IN (SELECT rowid FROM t1); }
} {0 1 2 3}
do_test in3-1.3 {
  exec_neph { SELECT a FROM t1 WHERE a IN (SELECT a FROM t1); }
} {0 1 3 5}
do_test in3-1.4 {
  exec_neph { SELECT rowid FROM t1 WHERE rowid+0 IN (SELECT rowid FROM t1); }
} {0 1 2 3}
do_test in3-1.5 {
  exec_neph { SELECT a FROM t1 WHERE a+0 IN (SELECT a FROM t1); }
} {0 1 3 5}

# Because none of the sub-select queries in the following statements
# match the pattern ("SELECT <column> FROM <table>"), the following do 
# require a temp table.
#
do_test in3-1.6 {
  exec_neph { SELECT rowid FROM t1 WHERE rowid IN (SELECT rowid+0 FROM t1); }
} {1 1 2 3}
do_test in3-1.7 {
  exec_neph { SELECT a FROM t1 WHERE a IN (SELECT a+0 FROM t1); }
} {1 1 3 5}
do_test in3-1.8 {
  exec_neph { SELECT a FROM t1 WHERE a IN (SELECT a FROM t1 WHERE 1); }
} {1 1 3 5}
do_test in3-1.9 {
  exec_neph { SELECT a FROM t1 WHERE a IN (SELECT a FROM t1 GROUP BY a); }
} {1 1 3 5}

# This should not use a temp-table. Even though the sub-select does
# not exactly match the pattern "SELECT <column> FROM <table>", in
# this case the ORDER BY is a no-op and can be ignored.
do_test in3-1.10 {
  exec_neph { SELECT a FROM t1 WHERE a IN (SELECT a FROM t1 ORDER BY a); }
} {0 1 3 5}

# These do use the temp-table. Adding the LIMIT clause means the 
# ORDER BY cannot be ignored.
do_test in3-1.11 {
  exec_neph {SELECT a FROM t1 WHERE a IN (SELECT a FROM t1 ORDER BY a LIMIT 1)}
} {1 1}
do_test in3-1.12 {
  exec_neph {
    SELECT a FROM t1 WHERE a IN (SELECT a FROM t1 ORDER BY a LIMIT 1 OFFSET 1)
  }
} {1 3}

# Has to use a temp-table because of the compound sub-select.
#
do_test in3-1.13 {
  exec_neph {
    SELECT a FROM t1 WHERE a IN (
      SELECT a FROM t1 UNION ALL SELECT a FROM t1
    )
  }
} {1 1 3 5}

# The first of these queries has to use the temp-table, because the 
# collation sequence used for the index on "t1.a" does not match the
# collation sequence used by the "IN" comparison. The second does not
# require a temp-table, because the collation sequences match.
#
do_test in3-1.14 {
  exec_neph { SELECT a FROM t1 WHERE a COLLATE nocase IN (SELECT a FROM t1) }
} {1 1 3 5}
do_test in3-1.15 {
  exec_neph { SELECT a FROM t1 WHERE a COLLATE binary IN (SELECT a FROM t1) }
} {0 1 3 5}

# Neither of these queries require a temp-table. The collation sequence
# makes no difference when using a rowid.
#
do_test in3-1.16 {
  exec_neph {SELECT a FROM t1 WHERE a COLLATE nocase IN (SELECT rowid FROM t1)}
} {0 1 3}
do_test in3-1.17 {
  exec_neph {SELECT a FROM t1 WHERE a COLLATE binary IN (SELECT rowid FROM t1)}
} {0 1 3}

# The following tests - in3.2.* - test a bug that was difficult to track
# down during development. They are not particularly well focused.
#
do_test in3-2.1 {
  execsql {
    DROP TABLE IF EXISTS t1;
    CREATE TABLE t1(w int, x int, y int);
    CREATE TABLE t2(p int, q int, r int, s int);
  }
  for {set i 1} {$i<=100} {incr i} {
    set w $i
    set x [expr {int(log($i)/log(2))}]
    set y [expr {$i*$i + 2*$i + 1}]
    execsql "INSERT INTO t1 VALUES($w,$x,$y)"
  }
  set maxy [execsql {select max(y) from t1}]
  db eval { INSERT INTO t2 SELECT 101-w, x, $maxy+1-y, y FROM t1 }
} {}
do_test in3-2.2 {
  execsql {
    SELECT rowid 
    FROM t1 
    WHERE rowid IN (SELECT rowid FROM t1 WHERE rowid IN (1, 2));
  }
} {1 2}
do_test in3-2.3 {
  execsql {
    select rowid from t1 where rowid IN (-1,2,4)
  }
} {2 4}
do_test in3-2.4 {
  execsql {
    SELECT rowid FROM t1 WHERE rowid IN 
       (select rowid from t1 where rowid IN (-1,2,4))
  }
} {2 4}

#-------------------------------------------------------------------------
# This next block of tests - in3-3.* - verify that column affinity is
# correctly handled in cases where an index might be used to optimise
# an IN (SELECT) expression.
#
do_test in3-3.1 {
  catch {execsql {
    DROP TABLE t1;
    DROP TABLE t2;
  }}

  execsql {

    CREATE TABLE t1(a BLOB, b NUMBER ,c TEXT);
    CREATE UNIQUE INDEX t1_i1 ON t1(a);        /* no affinity */
    CREATE UNIQUE INDEX t1_i2 ON t1(b);        /* numeric affinity */
    CREATE UNIQUE INDEX t1_i3 ON t1(c);        /* text affinity */

    CREATE TABLE t2(x BLOB, y NUMBER, z TEXT);
    CREATE UNIQUE INDEX t2_i1 ON t2(x);        /* no affinity */
    CREATE UNIQUE INDEX t2_i2 ON t2(y);        /* numeric affinity */
    CREATE UNIQUE INDEX t2_i3 ON t2(z);        /* text affinity */

    INSERT INTO t1 VALUES(1, 1, 1);
    INSERT INTO t2 VALUES('1', '1', '1');
  }
} {}

do_test in3-3.2 {
  # No affinity is applied before comparing "x" and "a". Therefore
  # the index can be used (the comparison is false, text!=number).
  exec_neph { SELECT x IN (SELECT a FROM t1) FROM t2 }
} {0 0}
do_test in3-3.3 {
  # Logically, numeric affinity is applied to both sides before 
  # the comparison.  Therefore it is possible to use index t1_i2.
  exec_neph { SELECT x IN (SELECT b FROM t1) FROM t2 }
} {0 1}
do_test in3-3.4 {
  # No affinity is applied before the comparison takes place. Making
  # it possible to use index t1_i3.
  exec_neph { SELECT x IN (SELECT c FROM t1) FROM t2 }
} {0 1}

do_test in3-3.5 {
  # Numeric affinity should be applied to each side before the comparison
  # takes place. Therefore we cannot use index t1_i1, which has no affinity.
  exec_neph { SELECT y IN (SELECT a FROM t1) FROM t2 }
} {1 1}
do_test in3-3.6 {
  # Numeric affinity is applied to both sides before 
  # the comparison.  Therefore it is possible to use index t1_i2.
  exec_neph { SELECT y IN (SELECT b FROM t1) FROM t2 }
} {0 1}
do_test in3-3.7 {
  # Numeric affinity is applied before the comparison takes place. 
  # Making it impossible to use index t1_i3.
  exec_neph { SELECT y IN (SELECT c FROM t1) FROM t2 }
} {1 1}

#---------------------------------------------------------------------
#
# Test using a multi-column index.
#
do_test in3-4.1 {
  execsql {
    CREATE TABLE t3(a, b, c);
    CREATE UNIQUE INDEX t3_i ON t3(b, a);
  }

  execsql {
    INSERT INTO t3 VALUES(1, 'numeric', 2);
    INSERT INTO t3 VALUES(2, 'text', 2);
    INSERT INTO t3 VALUES(3, 'real', 2);
    INSERT INTO t3 VALUES(4, 'none', 2);
  }
} {}
do_test in3-4.2 {
  exec_neph { SELECT 'text' IN (SELECT b FROM t3) }
} {0 1}
do_test in3-4.3 {
  exec_neph { SELECT 'TEXT' COLLATE nocase IN (SELECT b FROM t3) }
} {1 1}
do_test in3-4.4 {
  # A temp table must be used because t3_i.b is not guaranteed to be unique.
  exec_neph { SELECT b FROM t3 WHERE b IN (SELECT b FROM t3) }
} {1 none numeric real text}
do_test in3-4.5 {
  execsql { CREATE UNIQUE INDEX t3_i2 ON t3(b) }
  exec_neph { SELECT b FROM t3 WHERE b IN (SELECT b FROM t3) }
} {0 none numeric real text}
do_test in3-4.6 {
  execsql { DROP INDEX t3_i2 }
} {}

finish_test