/ Check-in [207335fd]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Make sure that the optimizer realizes that an "x IS NULL" contraint does not necessarily give a single-row result even on a UNIQUE index. Ticket #3824. (CVS 6545)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 207335fdbf992a2f5bc5982b3163a38016ba1b21
User & Date: drh 2009-04-24 14:51:42
Context
2009-04-24
15:46
Get rid of the special RowSet processing in where.c and move that into clients. Added the WHERE_DUPLICATES_OK option to eliminate an unnecessary RowSet during DELETE with a WHERE clause containing ORs. (CVS 6546) check-in: 98606bee user: drh tags: trunk
14:51
Make sure that the optimizer realizes that an "x IS NULL" contraint does not necessarily give a single-row result even on a UNIQUE index. Ticket #3824. (CVS 6545) check-in: 207335fd user: drh tags: trunk
10:13
Make selecting the asynchronous IO file-locking mode a runtime operation. Still untested. (CVS 6544) check-in: 577277e8 user: danielk1977 tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

    12     12   ** This module contains C code that generates VDBE code used to process
    13     13   ** the WHERE clause of SQL statements.  This module is responsible for
    14     14   ** generating the code that loops through a table looking for applicable
    15     15   ** rows.  Indices are selected and used to speed the search when doing
    16     16   ** so is applicable.  Because this module is responsible for selecting
    17     17   ** indices, you might also think of this module as the "query optimizer".
    18     18   **
    19         -** $Id: where.c,v 1.388 2009/04/23 13:22:44 drh Exp $
           19  +** $Id: where.c,v 1.389 2009/04/24 14:51:42 drh Exp $
    20     20   */
    21     21   #include "sqliteInt.h"
    22     22   
    23     23   /*
    24     24   ** Trace output macros
    25     25   */
    26     26   #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
................................................................................
   222    222   ** is set to WO_IN|WO_EQ.  The WhereLevel.wsFlags field can then be used as
   223    223   ** the "op" parameter to findTerm when we are resolving equality constraints.
   224    224   ** ISNULL constraints will then not be used on the right table of a left
   225    225   ** join.  Tickets #2177 and #2189.
   226    226   */
   227    227   #define WHERE_ROWID_EQ     0x00001000  /* rowid=EXPR or rowid IN (...) */
   228    228   #define WHERE_ROWID_RANGE  0x00002000  /* rowid<EXPR and/or rowid>EXPR */
   229         -#define WHERE_COLUMN_EQ    0x00010000  /* x=EXPR or x IN (...) */
          229  +#define WHERE_COLUMN_EQ    0x00010000  /* x=EXPR or x IN (...) or x IS NULL */
   230    230   #define WHERE_COLUMN_RANGE 0x00020000  /* x<EXPR and/or x>EXPR */
   231    231   #define WHERE_COLUMN_IN    0x00040000  /* x IN (...) */
   232         -#define WHERE_INDEXED      0x00070000  /* Anything that uses an index */
   233         -#define WHERE_IN_ABLE      0x00071000  /* Able to support an IN operator */
          232  +#define WHERE_COLUMN_NULL  0x00080000  /* x IS NULL */
          233  +#define WHERE_INDEXED      0x000f0000  /* Anything that uses an index */
          234  +#define WHERE_IN_ABLE      0x000f1000  /* Able to support an IN operator */
   234    235   #define WHERE_TOP_LIMIT    0x00100000  /* x<EXPR or x<=EXPR constraint */
   235    236   #define WHERE_BTM_LIMIT    0x00200000  /* x>EXPR or x>=EXPR constraint */
   236    237   #define WHERE_IDX_ONLY     0x00800000  /* Use index only - omit table */
   237    238   #define WHERE_ORDERBY      0x01000000  /* Output will appear in correct order */
   238    239   #define WHERE_REVERSE      0x02000000  /* Scan in reverse order */
   239    240   #define WHERE_UNIQUE       0x04000000  /* Selects no more than one row */
   240    241   #define WHERE_VIRTUALTABLE 0x08000000  /* Use virtual-table processing */
................................................................................
  2026   2027     for(; pProbe; pProbe=(pSrc->pIndex ? 0 : pProbe->pNext)){
  2027   2028       double inMultiplier = 1;  /* Number of equality look-ups needed */
  2028   2029       int inMultIsEst = 0;      /* True if inMultiplier is an estimate */
  2029   2030   
  2030   2031       WHERETRACE(("... index %s:\n", pProbe->zName));
  2031   2032   
  2032   2033       /* Count the number of columns in the index that are satisfied
  2033         -    ** by x=EXPR constraints or x IN (...) constraints.  For a term
  2034         -    ** of the form x=EXPR we only have to do a single binary search.
  2035         -    ** But for x IN (...) we have to do a number of binary searched
         2034  +    ** by x=EXPR or x IS NULL constraints or x IN (...) constraints.
         2035  +    ** For a term of the form x=EXPR or x IS NULL we only have to do 
         2036  +    ** a single binary search.  But for x IN (...) we have to do a
         2037  +    ** number of binary searched
  2036   2038       ** equal to the number of entries on the RHS of the IN operator.
  2037   2039       ** The inMultipler variable with try to estimate the number of
  2038   2040       ** binary searches needed.
  2039   2041       */
  2040   2042       wsFlags = 0;
  2041   2043       for(i=0; i<pProbe->nColumn; i++){
  2042   2044         int j = pProbe->aiColumn[i];
................................................................................
  2048   2050           wsFlags |= WHERE_COLUMN_IN;
  2049   2051           if( ExprHasProperty(pExpr, EP_xIsSelect) ){
  2050   2052             inMultiplier *= 25;
  2051   2053             inMultIsEst = 1;
  2052   2054           }else if( pExpr->x.pList ){
  2053   2055             inMultiplier *= pExpr->x.pList->nExpr + 1;
  2054   2056           }
         2057  +      }else if( pTerm->eOperator & WO_ISNULL ){
         2058  +        wsFlags |= WHERE_COLUMN_NULL;
  2055   2059         }
  2056   2060       }
  2057   2061       nRow = pProbe->aiRowEst[i] * inMultiplier;
  2058   2062       /* If inMultiplier is an estimate and that estimate results in an
  2059   2063       ** nRow it that is more than half number of rows in the table,
  2060   2064       ** then reduce inMultipler */
  2061   2065       if( inMultIsEst && nRow*2 > pProbe->aiRowEst[0] ){
  2062   2066         nRow = pProbe->aiRowEst[0]/2;
  2063   2067         inMultiplier = nRow/pProbe->aiRowEst[i];
  2064   2068       }
  2065   2069       cost = nRow + inMultiplier*estLog(pProbe->aiRowEst[0]);
  2066   2070       nEq = i;
  2067         -    if( pProbe->onError!=OE_None && (wsFlags & WHERE_COLUMN_IN)==0
  2068         -         && nEq==pProbe->nColumn ){
  2069         -      wsFlags |= WHERE_UNIQUE;
         2071  +    if( pProbe->onError!=OE_None && nEq==pProbe->nColumn ){
         2072  +      testcase( wsFlags & WHERE_COLUMN_IN );
         2073  +      testcase( wsFlags & WHERE_COLUMN_NULL );
         2074  +      if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
         2075  +        wsFlags |= WHERE_UNIQUE;
         2076  +      }
  2070   2077       }
  2071   2078       WHERETRACE(("...... nEq=%d inMult=%.9g nRow=%.9g cost=%.9g\n",
  2072   2079                   nEq, inMultiplier, nRow, cost));
  2073   2080   
  2074   2081       /* Look for range constraints.  Assume that each range constraint
  2075   2082       ** makes the search space 1/3rd smaller.
  2076   2083       */
................................................................................
  2093   2100                       nRow, cost));
  2094   2101         }
  2095   2102       }
  2096   2103   
  2097   2104       /* Add the additional cost of sorting if that is a factor.
  2098   2105       */
  2099   2106       if( pOrderBy ){
  2100         -      if( (wsFlags & WHERE_COLUMN_IN)==0 &&
  2101         -           isSortingIndex(pParse,pWC->pMaskSet,pProbe,iCur,pOrderBy,nEq,&rev) ){
         2107  +      if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0
         2108  +       && isSortingIndex(pParse,pWC->pMaskSet,pProbe,iCur,pOrderBy,nEq,&rev)
         2109  +      ){
  2102   2110           if( wsFlags==0 ){
  2103   2111             wsFlags = WHERE_COLUMN_RANGE;
  2104   2112           }
  2105   2113           wsFlags |= WHERE_ORDERBY;
  2106   2114           if( rev ){
  2107   2115             wsFlags |= WHERE_REVERSE;
  2108   2116           }

Added test/tkt3824.test.

            1  +# 2009 April 24                                                                 
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +#
           12  +# Ticket #3824
           13  +#
           14  +# When you use an "IS NULL" constraint on a UNIQUE index, the result
           15  +# is not necessarily UNIQUE.  Make sure the optimizer does not assume
           16  +# uniqueness.
           17  +#
           18  +# $Id: tkt3824.test,v 1.1 2009/04/24 14:51:42 drh Exp $
           19  +
           20  +set testdir [file dirname $argv0]
           21  +source $testdir/tester.tcl
           22  +
           23  +proc execsql_status {sql {db db}} {
           24  +  set result [uplevel $db eval [list $sql]]
           25  +  if {[db status sort]} {
           26  +    concat $result sort
           27  +  } else {
           28  +    concat $result nosort
           29  +  }
           30  +}
           31  +
           32  +do_test tkt3824-1.1 {
           33  +  db eval {
           34  +    CREATE TABLE t1(a,b);
           35  +    INSERT INTO t1 VALUES(1,NULL);
           36  +    INSERT INTO t1 VALUES(9,NULL);
           37  +    INSERT INTO t1 VALUES(5,NULL);
           38  +    INSERT INTO t1 VALUES(123,NULL);
           39  +    INSERT INTO t1 VALUES(-10,NULL);
           40  +    CREATE UNIQUE INDEX t1b ON t1(b);
           41  +  }
           42  +  execsql_status {
           43  +    SELECT a FROM t1 WHERE b IS NULL ORDER BY a;
           44  +  }
           45  +} {-10 1 5 9 123 sort}
           46  +do_test tkt3824-1.2 {
           47  +  execsql_status {
           48  +    SELECT a FROM t1 WHERE b IS NULL ORDER BY b, a;
           49  +  }
           50  +} {-10 1 5 9 123 sort}
           51  +
           52  +do_test tkt3824-2.1 {
           53  +  db eval {
           54  +    CREATE TABLE t2(a,b,c);
           55  +    INSERT INTO t2 VALUES(1,1,NULL);
           56  +    INSERT INTO t2 VALUES(9,2,NULL);
           57  +    INSERT INTO t2 VALUES(5,2,NULL);
           58  +    INSERT INTO t2 VALUES(123,3,NULL);
           59  +    INSERT INTO t2 VALUES(-10,3,NULL);
           60  +    CREATE UNIQUE INDEX t2bc ON t2(b,c);
           61  +  }
           62  +  execsql_status {
           63  +    SELECT a FROM t2 WHERE b=2 AND c IS NULL ORDER BY a;
           64  +  }
           65  +} {5 9 sort}
           66  +do_test tkt3824-2.2 {
           67  +  execsql_status {
           68  +    SELECT a FROM t2 WHERE b=2 AND c IS NULL ORDER BY b, a;
           69  +  }
           70  +} {5 9 sort}
           71  +do_test tkt3824-2.3 {
           72  +  lsort [execsql_status {
           73  +    SELECT a FROM t2 WHERE b=2 AND c IS NULL ORDER BY b;
           74  +  }]
           75  +} {5 9 sort}
           76  +
           77  +do_test tkt3824-3.1 {
           78  +  db eval {
           79  +    CREATE TABLE t3(x,y);
           80  +    INSERT INTO t3 SELECT a, b FROM t1;
           81  +    INSERT INTO t3 VALUES(234,567);
           82  +    CREATE UNIQUE INDEX t3y ON t3(y);
           83  +    DELETE FROM t3 WHERE y IS NULL;
           84  +    SELECT * FROM t3;
           85  +  }
           86  +} {234 567}
           87  +
           88  +finish_test