SQLite

Check-in [335863e4d1]
Login

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

Overview
Comment:Make sure the IS NULL optimization introduced by check-in (3494) correctly handles a LEFT JOIN where the a term from the right table of the join uses an IS NULL constraint. Ticket #2177. This check-in also adds the new test cases that were suppose to have been added with (3494) but which were mistakenly omitted. (CVS 3595)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 335863e4d16113fb9ecebce35d2db043771d98b1
User & Date: drh 2007-01-19 01:06:02.000
Context
2007-01-19
22:59
http://www.sqlite.org/cvstrac/tktview?tn=2166,35

Calling UPDATE against an fts table in a UTF-16 database inserts corrupted data into the database. The UTF-8 data is being inserted directly. This appears to happen because sqlite3_ value_text() destructively coerces a value to UTF-8, and it's never converted back when updating the table. This works around the problem by rearranging things so that the update happens before the coercion. (CVS 3596) (check-in: 4f2ab4b632 user: shess tags: trunk)

01:06
Make sure the IS NULL optimization introduced by check-in (3494) correctly handles a LEFT JOIN where the a term from the right table of the join uses an IS NULL constraint. Ticket #2177. This check-in also adds the new test cases that were suppose to have been added with (3494) but which were mistakenly omitted. (CVS 3595) (check-in: 335863e4d1 user: drh tags: trunk)
2007-01-16
18:19
Additional memory initialization in lemon - bug reported from wireshark. Ticket #2172. Note this problem only comes up with certain grammars, and does not impact SQLite. On the other hand, it might cause SQLite to run slower. So we might want to revisit this change at some point. (CVS 3594) (check-in: d537aa5ede user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/sqliteInt.h.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
** 2001 September 15
**
** 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.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.532 2006/12/21 01:29:23 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Extra interface definitions for those who need them
*/













|







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
** 2001 September 15
**
** 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.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.533 2007/01/19 01:06:02 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Extra interface definitions for those who need them
*/
1087
1088
1089
1090
1091
1092
1093





1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
** the SrcList.a[] array.
**
** With the addition of multiple database support, the following structure
** can also be used to describe a particular table such as the table that
** is modified by an INSERT, DELETE, or UPDATE statement.  In standard SQL,
** such a table must be a simple name: ID.  But in SQLite, the table can
** now be identified by a database name, a dot, then the table name: ID.ID.





*/
struct SrcList {
  i16 nSrc;        /* Number of tables or subqueries in the FROM clause */
  i16 nAlloc;      /* Number of entries allocated in a[] below */
  struct SrcList_item {
    char *zDatabase;  /* Name of database holding this table */
    char *zName;      /* Name of the table */
    char *zAlias;     /* The "B" part of a "A AS B" phrase.  zName is the "A" */
    Table *pTab;      /* An SQL table corresponding to zName */
    Select *pSelect;  /* A SELECT statement used in place of a table name */
    u8 isPopulated;   /* Temporary table associated with SELECT is populated */
    u8 jointype;      /* Type of join between this table and the next */
    i16 iCursor;      /* The VDBE cursor number used to access this table */
    Expr *pOn;        /* The ON clause of a join */
    IdList *pUsing;   /* The USING clause of a join */
    Bitmask colUsed;  /* Bit N (1<<N) set if column N or pTab is used */
  } a[1];             /* One entry for each identifier on the list */
};








>
>
>
>
>











|







1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
** the SrcList.a[] array.
**
** With the addition of multiple database support, the following structure
** can also be used to describe a particular table such as the table that
** is modified by an INSERT, DELETE, or UPDATE statement.  In standard SQL,
** such a table must be a simple name: ID.  But in SQLite, the table can
** now be identified by a database name, a dot, then the table name: ID.ID.
**
** The jointype starts out showing the join type between the current table
** and the next table on the list.  The parser builds the list this way.
** But sqlite3SrcListShiftJoinType() later shifts the jointypes so that each
** jointype expresses the join between the table and the previous table.
*/
struct SrcList {
  i16 nSrc;        /* Number of tables or subqueries in the FROM clause */
  i16 nAlloc;      /* Number of entries allocated in a[] below */
  struct SrcList_item {
    char *zDatabase;  /* Name of database holding this table */
    char *zName;      /* Name of the table */
    char *zAlias;     /* The "B" part of a "A AS B" phrase.  zName is the "A" */
    Table *pTab;      /* An SQL table corresponding to zName */
    Select *pSelect;  /* A SELECT statement used in place of a table name */
    u8 isPopulated;   /* Temporary table associated with SELECT is populated */
    u8 jointype;      /* Type of join between this able and the previous */
    i16 iCursor;      /* The VDBE cursor number used to access this table */
    Expr *pOn;        /* The ON clause of a join */
    IdList *pUsing;   /* The USING clause of a join */
    Bitmask colUsed;  /* Bit N (1<<N) set if column N or pTab is used */
  } a[1];             /* One entry for each identifier on the list */
};

Changes to src/where.c.
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
** 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.234 2006/12/20 03:24:19 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)







|







12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
** 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.235 2007/01/19 01:06:03 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
1271
1272
1273
1274
1275
1276
1277

1278
1279
1280
1281
1282
1283
1284
  int bestFlags = 0;          /* Flags associated with bestIdx */
  int bestNEq = 0;            /* Best value for nEq */
  int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
  Index *pProbe;              /* An index we are evaluating */
  int rev;                    /* True to scan in reverse order */
  int flags;                  /* Flags associated with pProbe */
  int nEq;                    /* Number of == or IN constraints */

  double cost;                /* Cost of using pProbe */

  TRACE(("bestIndex: tbl=%s notReady=%x\n", pSrc->pTab->zName, notReady));
  lowestCost = SQLITE_BIG_DBL;
  pProbe = pSrc->pTab->pIndex;

  /* If the table has no indices and there are no terms in the where







>







1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
  int bestFlags = 0;          /* Flags associated with bestIdx */
  int bestNEq = 0;            /* Best value for nEq */
  int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
  Index *pProbe;              /* An index we are evaluating */
  int rev;                    /* True to scan in reverse order */
  int flags;                  /* Flags associated with pProbe */
  int nEq;                    /* Number of == or IN constraints */
  int eqTermMask;             /* Mask of valid equality operators */
  double cost;                /* Cost of using pProbe */

  TRACE(("bestIndex: tbl=%s notReady=%x\n", pSrc->pTab->zName, notReady));
  lowestCost = SQLITE_BIG_DBL;
  pProbe = pSrc->pTab->pIndex;

  /* If the table has no indices and there are no terms in the where
1361
1362
1363
1364
1365
1366
1367











1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
      TRACE(("... sorting increases cost to %.9g\n", cost));
    }
  }
  if( cost<lowestCost ){
    lowestCost = cost;
    bestFlags = flags;
  }












  /* Look at each index.
  */
  for(; pProbe; pProbe=pProbe->pNext){
    int i;                       /* Loop counter */
    double inMultiplier = 1;

    TRACE(("... index %s:\n", pProbe->zName));

    /* Count the number of columns in the index that are satisfied
    ** by x=EXPR constraints or x IN (...) constraints.
    */
    flags = 0;
    for(i=0; i<pProbe->nColumn; i++){
      int j = pProbe->aiColumn[i];
      pTerm = findTerm(pWC, iCur, j, notReady, WO_EQ|WO_IN|WO_ISNULL, pProbe);
      if( pTerm==0 ) break;
      flags |= WHERE_COLUMN_EQ;
      if( pTerm->eOperator & WO_IN ){
        Expr *pExpr = pTerm->pExpr;
        flags |= WHERE_COLUMN_IN;
        if( pExpr->pSelect!=0 ){
          inMultiplier *= 25;







>
>
>
>
>
>
>
>
>
>
>















|







1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
      TRACE(("... sorting increases cost to %.9g\n", cost));
    }
  }
  if( cost<lowestCost ){
    lowestCost = cost;
    bestFlags = flags;
  }

  /* If the pSrc table is the right table of a LEFT JOIN then we may not
  ** use an index to satisfy IS NULL constraints on that table.  This is
  ** because columns might end up being NULL if the table does not match -
  ** a circumstance which the index cannot help us discover.  Ticket #2177.
  */
  if( (pSrc->jointype & JT_LEFT)!=0 ){
    eqTermMask = WO_EQ|WO_IN;
  }else{
    eqTermMask = WO_EQ|WO_IN|WO_ISNULL;
  }

  /* Look at each index.
  */
  for(; pProbe; pProbe=pProbe->pNext){
    int i;                       /* Loop counter */
    double inMultiplier = 1;

    TRACE(("... index %s:\n", pProbe->zName));

    /* Count the number of columns in the index that are satisfied
    ** by x=EXPR constraints or x IN (...) constraints.
    */
    flags = 0;
    for(i=0; i<pProbe->nColumn; i++){
      int j = pProbe->aiColumn[i];
      pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pProbe);
      if( pTerm==0 ) break;
      flags |= WHERE_COLUMN_EQ;
      if( pTerm->eOperator & WO_IN ){
        Expr *pExpr = pTerm->pExpr;
        flags |= WHERE_COLUMN_IN;
        if( pExpr->pSelect!=0 ){
          inMultiplier *= 25;
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
  if( pLevel->flags & WHERE_COLUMN_IN ){
    pParse->nMem += pLevel->nEq;
    termsInMem = 1;
  }

  /* Evaluate the equality constraints
  */

  for(j=0; j<pIdx->nColumn; j++){
    int k = pIdx->aiColumn[j];
    pTerm = findTerm(pWC, iCur, k, notReady, WO_EQ|WO_IN|WO_ISNULL, pIdx);
    if( pTerm==0 ) break;
    assert( (pTerm->flags & TERM_CODED)==0 );
    codeEqualityTerm(pParse, pTerm, brk, pLevel);
    if( (pTerm->eOperator & WO_ISNULL)==0 ){
      sqlite3VdbeAddOp(v, OP_IsNull, termsInMem ? -1 : -(j+1), brk);
    }
    if( termsInMem ){
      sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem+j+1, 1);
    }
  }
  assert( j==nEq );

  /* Make sure all the constraint values are on the top of the stack
  */
  if( termsInMem ){
    for(j=0; j<nEq; j++){
      sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem+j+1, 0);
    }







>
|












<







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
1669
1670
1671
  if( pLevel->flags & WHERE_COLUMN_IN ){
    pParse->nMem += pLevel->nEq;
    termsInMem = 1;
  }

  /* Evaluate the equality constraints
  */
  assert( pIdx->nColumn>=nEq );
  for(j=0; j<nEq; j++){
    int k = pIdx->aiColumn[j];
    pTerm = findTerm(pWC, iCur, k, notReady, WO_EQ|WO_IN|WO_ISNULL, pIdx);
    if( pTerm==0 ) break;
    assert( (pTerm->flags & TERM_CODED)==0 );
    codeEqualityTerm(pParse, pTerm, brk, pLevel);
    if( (pTerm->eOperator & WO_ISNULL)==0 ){
      sqlite3VdbeAddOp(v, OP_IsNull, termsInMem ? -1 : -(j+1), brk);
    }
    if( termsInMem ){
      sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem+j+1, 1);
    }
  }


  /* Make sure all the constraint values are on the top of the stack
  */
  if( termsInMem ){
    for(j=0; j<nEq; j++){
      sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem+j+1, 0);
    }
Added test/where4.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
# 2006 October 27
#
# 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 implements regression tests for SQLite library.  The
# focus of this file is testing the use of indices in WHERE clauses.
# This file was created when support for optimizing IS NULL phrases
# was added.  And so the principle purpose of this file is to test
# that IS NULL phrases are correctly optimized.  But you can never
# have too many tests, so some other tests are thrown in as well.
#
# $Id: where4.test,v 1.1 2007/01/19 01:06:03 drh Exp $

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

# Build some test data
#
do_test where4-1.0 {
  execsql {
    CREATE TABLE t1(w, x, y);
    CREATE INDEX i1wxy ON t1(w,x,y);
    INSERT INTO t1 VALUES(1,2,3);
    INSERT INTO t1 VALUES(1,NULL,3);
    INSERT INTO t1 VALUES('a','b','c');
    INSERT INTO t1 VALUES('a',NULL,'c');
    INSERT INTO t1 VALUES(X'78',x'79',x'7a');
    INSERT INTO t1 VALUES(X'78',NULL,X'7A');
    INSERT INTO t1 VALUES(NULL,NULL,NULL);
    SELECT count(*) FROM t1;
  }
} {7}

# Do an SQL statement.  Append the search count to the end of the result.
#
proc count sql {
  set ::sqlite_search_count 0
  return [concat [execsql $sql] $::sqlite_search_count]
}

# Verify that queries use an index.  We are using the special variable
# "sqlite_search_count" which tallys the number of executions of MoveTo
# and Next operators in the VDBE.  By verifing that the search count is
# small we can be assured that indices are being used properly.
#
do_test where4-1.1 {
  count {SELECT rowid FROM t1 WHERE w IS NULL}
} {7 2}
do_test where4-1.2 {
  count {SELECT rowid FROM t1 WHERE +w IS NULL}
} {7 6}
do_test where4-1.3 {
  count {SELECT rowid FROM t1 WHERE w=1 AND x IS NULL}
} {2 2}
do_test where4-1.4 {
  count {SELECT rowid FROM t1 WHERE w=1 AND +x IS NULL}
} {2 3}
do_test where4-1.5 {
  count {SELECT rowid FROM t1 WHERE w=1 AND x>0}
} {1 2}
do_test where4-1.6 {
  count {SELECT rowid FROM t1 WHERE w=1 AND x<9}
} {1 3}
do_test where4-1.7 {
  count {SELECT rowid FROM t1 WHERE w=1 AND x IS NULL AND y=3}
} {2 2}
do_test where4-1.8 {
  count {SELECT rowid FROM t1 WHERE w=1 AND x IS NULL AND y>2}
} {2 2}
do_test where4-1.9 {
  count {SELECT rowid FROM t1 WHERE w='a' AND x IS NULL AND y='c'}
} {4 2}
do_test where4-1.10 {
  count {SELECT rowid FROM t1 WHERE w=x'78' AND x IS NULL}
} {6 2}
do_test where4-1.11 {
  count {SELECT rowid FROM t1 WHERE w=x'78' AND x IS NULL AND y=123}
} {1}
do_test where4-1.12 {
  count {SELECT rowid FROM t1 WHERE w=x'78' AND x IS NULL AND y=x'7A'}
} {6 2}
do_test where4-1.13 {
  count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL}
} {7 2}
do_test where4-1.14 {
  count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL AND y IS NULL}
} {7 2}
do_test where4-1.15 {
  count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL AND y<0}
} {2}
do_test where4-1.16 {
  count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL AND y>=0}
} {1}

do_test where4-2.1 {
  execsql {SELECT rowid FROM t1 ORDER BY w, x, y}
} {7 2 1 4 3 6 5}
do_test where4-2.2 {
  execsql {SELECT rowid FROM t1 ORDER BY w DESC, x, y}
} {6 5 4 3 2 1 7}
do_test where4-2.3 {
  execsql {SELECT rowid FROM t1 ORDER BY w, x DESC, y}
} {7 1 2 3 4 5 6}


# Ticket #2177
#
# Suppose you have a left join where the right table of the left
# join (the one that can be NULL) has an index on two columns.
# The first indexed column is used in the ON clause of the join.
# The second indexed column is used in the WHERE clause with an IS NULL
# constraint.  It is not allowed to use the IS NULL optimization to
# optimize the query because the second column might be NULL because
# the right table did not match - something the index does not know
# about.
#
do_test where4-3.1 {
  execsql {
    CREATE TABLE t2(a);
    INSERT INTO t2 VALUES(1);
    INSERT INTO t2 VALUES(2);
    INSERT INTO t2 VALUES(3);
    CREATE TABLE t3(x,y,UNIQUE(x,y));
    INSERT INTO t3 VALUES(1,11);
    INSERT INTO t3 VALUES(2,NULL);
 
    SELECT * FROM t2 LEFT JOIN t3 ON a=x WHERE +y IS NULL;
  }
} {2 2 {} 3 {} {}}
do_test where4-3.2 {
  execsql {
    SELECT * FROM t2 LEFT JOIN t3 ON a=x WHERE y IS NULL;
  }
} {2 2 {} 3 {} {}}

integrity_check {where4-99.0}

finish_test