SQLite

Check-in [908daaa9ab]
Login

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

Overview
Comment:Disable the OR optimization if it would conflict with column affinity coercions. Ticket #2249. Additional cleanup and testing of the OR optimization. (CVS 3658)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 908daaa9ab86e0bd1da6d0807d6aaba240c3cee0
User & Date: drh 2007-02-23 23:13:34.000
Context
2007-02-24
11:52
Make sure that integer values are converted to real when pulled from a REAL table column by GROUP BY. Ticket #2251. Also make sure default values are correctly expanded. There may be other places in the code where this issue comes up - we need to look further. (CVS 3659) (check-in: e11bbf174c user: drh tags: trunk)
2007-02-23
23:13
Disable the OR optimization if it would conflict with column affinity coercions. Ticket #2249. Additional cleanup and testing of the OR optimization. (CVS 3658) (check-in: 908daaa9ab user: drh tags: trunk)
14:20
Clarifications to the datatype3.html document. (CVS 3657) (check-in: 4692a85edb user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
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.237 2007/02/06 13:26:33 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.238 2007/02/23 23:13:34 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
578
579
580
581
582
583
584






















































































585
586
587
588
589
590
591
** a join, then transfer the appropriate markings over to derived.
*/
static void transferJoinMarkings(Expr *pDerived, Expr *pBase){
  pDerived->flags |= pBase->flags & EP_FromJoin;
  pDerived->iRightJoinTable = pBase->iRightJoinTable;
}
























































































/*
** The input to this routine is an WhereTerm structure with only the
** "pExpr" field filled in.  The job of this routine is to analyze the
** subexpression and populate all the other fields of the WhereTerm
** structure.
**







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







578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
** a join, then transfer the appropriate markings over to derived.
*/
static void transferJoinMarkings(Expr *pDerived, Expr *pBase){
  pDerived->flags |= pBase->flags & EP_FromJoin;
  pDerived->iRightJoinTable = pBase->iRightJoinTable;
}

#if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
/*
** Return TRUE if the given term of an OR clause can be converted
** into an IN clause.  The iCursor and iColumn define the left-hand
** side of the IN clause.
**
** The context is that we have multiple OR-connected equality terms
** like this:
**
**           a=<expr1> OR  a=<expr2> OR b=<expr3>  OR ...
**
** The pOrTerm input to this routine corresponds to a single term of
** this OR clause.  In order for the term to be a condidate for
** conversion to an IN operator, the following must be true:
**
**     *  The left-hand side of the term must be the column which
**        is identified by iCursor and iColumn.
**
**     *  If the right-hand side is also a column, then the affinities
**        of both right and left sides must be such that no type
**        conversions are required on the right.  (Ticket #2249)
**
** If both of these conditions are true, then return true.  Otherwise
** return false.
*/
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);
  if( affRight!=affLeft ){
    return 0;
  }
  return 1;
}

/*
** Return true if the given term of an OR clause can be ignored during
** a check to make sure all OR terms are candidates for optimization.
** In other words, return true if a call to the orTermIsOptCandidate()
** above returned false but it is not necessary to disqualify the
** optimization.
**
** Suppose the original OR phrase was this:
**
**           a=4  OR  a=11  OR  a=b
**
** During analysis, the third term gets flipped around and duplicate
** so that we are left with this:
**
**           a=4  OR  a=11  OR  a=b  OR  b=a
**
** Since the last two terms are duplicates, only one of them
** has to qualify in order for the whole phrase to qualify.  When
** this routine is called, we know that pOrTerm did not qualify.
** This routine merely checks to see if pOrTerm has a duplicate that
** might qualify.  If there is a duplicate that has not yet been
** disqualified, then return true.  If there are no duplicates, or
** the duplicate has also been disqualifed, return false.
*/
static int orTermHasOkDuplicate(WhereClause *pOr, WhereTerm *pOrTerm){
  if( pOrTerm->flags & TERM_COPIED ){
    /* This is the original term.  The duplicate is to the left had
    ** has not yet been analyzed and thus has not yet been disqualified. */
    return 1;
  }
  if( (pOrTerm->flags & TERM_VIRTUAL)!=0
     && (pOr->a[pOrTerm->iParent].flags & TERM_OR_OK)!=0 ){
    /* This is a duplicate term.  The original qualified so this one
    ** does not have to. */
    return 1;
  }
  /* This is either a singleton term or else it is a duplicate for
  ** which the original did not qualify.  Either way we are done for. */
  return 0;
}
#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */

/*
** The input to this routine is an WhereTerm structure with only the
** "pExpr" field filled in.  The job of this routine is to analyze the
** subexpression and populate all the other fields of the WhereTerm
** structure.
**
712
713
714
715
716
717
718
719
720
721

722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
    WhereClause sOr;
    WhereTerm *pOrTerm;

    assert( (pTerm->flags & TERM_DYNAMIC)==0 );
    whereClauseInit(&sOr, pWC->pParse, pMaskSet);
    whereSplit(&sOr, pExpr, TK_OR);
    exprAnalyzeAll(pSrc, &sOr);
    assert( sOr.nTerm>0 );
    j = 0;
    do{

      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( pOrTerm->leftCursor==iCursor && pOrTerm->leftColumn==iColumn ){
          pOrTerm->flags |= TERM_OR_OK;
        }else if( (pOrTerm->flags & TERM_COPIED)!=0 ||
                    ((pOrTerm->flags & TERM_VIRTUAL)!=0 &&
                     (sOr.a[pOrTerm->iParent].flags & TERM_OR_OK)!=0) ){
          pOrTerm->flags &= ~TERM_OR_OK;
        }else{
          ok = 0;
        }
      }
    }while( !ok && (sOr.a[j++].flags & TERM_COPIED)!=0 && j<sOr.nTerm );
    if( ok ){
      ExprList *pList = 0;
      Expr *pNew, *pDup;
      Expr *pLeft = 0;
      for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){
        if( (pOrTerm->flags & TERM_OR_OK)==0 ) continue;
        pDup = sqlite3ExprDup(pOrTerm->pExpr->pRight);







|


>







|

|
<
<





|







798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818


819
820
821
822
823
824
825
826
827
828
829
830
831
    WhereClause sOr;
    WhereTerm *pOrTerm;

    assert( (pTerm->flags & TERM_DYNAMIC)==0 );
    whereClauseInit(&sOr, pWC->pParse, pMaskSet);
    whereSplit(&sOr, pExpr, TK_OR);
    exprAnalyzeAll(pSrc, &sOr);
    assert( sOr.nTerm>=2 );
    j = 0;
    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) ){
          pOrTerm->flags |= TERM_OR_OK;
        }else if( orTermHasOkDuplicate(&sOr, pOrTerm) ){


          pOrTerm->flags &= ~TERM_OR_OK;
        }else{
          ok = 0;
        }
      }
    }while( !ok && (sOr.a[j++].flags & TERM_COPIED)!=0 && j<2 );
    if( ok ){
      ExprList *pList = 0;
      Expr *pNew, *pDup;
      Expr *pLeft = 0;
      for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){
        if( (pOrTerm->flags & TERM_OR_OK)==0 ) continue;
        pDup = sqlite3ExprDup(pOrTerm->pExpr->pRight);
Changes to test/where2.test.
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#    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
# based on recent changes to the optimizer.
#
# $Id: where2.test,v 1.10 2006/11/06 15:10:06 drh Exp $

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

# Build some test data
#
do_test where2-1.0 {







|







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#    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
# based on recent changes to the optimizer.
#
# $Id: where2.test,v 1.11 2007/02/23 23:13:34 drh Exp $

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

# Build some test data
#
do_test where2-1.0 {
215
216
217
218
219
220
221
222
223
224





225
226
227
228
229
230
231
  } {99 6 10000 10006 sort t1 i1w}
}

# Verify that OR clauses get translated into IN operators.
#
set ::idx {}
ifcapable subquery {set ::idx i1w}
do_test where2-6.1 {
  queryplan {
    SELECT * FROM t1 WHERE w=99 OR w=100 ORDER BY +w





  }
} [list 99 6 10000 10006 100 6 10201 10207 sort t1 $::idx]
do_test where2-6.2 {
  queryplan {
    SELECT * FROM t1 WHERE w=99 OR w=100 OR 6=w ORDER BY +w
  }
} [list 6 2 49 51 99 6 10000 10006 100 6 10201 10207 sort t1 $::idx]







|


>
>
>
>
>







215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
  } {99 6 10000 10006 sort t1 i1w}
}

# Verify that OR clauses get translated into IN operators.
#
set ::idx {}
ifcapable subquery {set ::idx i1w}
do_test where2-6.1.1 {
  queryplan {
    SELECT * FROM t1 WHERE w=99 OR w=100 ORDER BY +w
  }
} [list 99 6 10000 10006 100 6 10201 10207 sort t1 $::idx]
do_test where2-6.1.2 {
  queryplan {
    SELECT * FROM t1 WHERE 99=w OR 100=w ORDER BY +w
  }
} [list 99 6 10000 10006 100 6 10201 10207 sort t1 $::idx]
do_test where2-6.2 {
  queryplan {
    SELECT * FROM t1 WHERE w=99 OR w=100 OR 6=w ORDER BY +w
  }
} [list 6 2 49 51 99 6 10000 10006 100 6 10201 10207 sort t1 $::idx]
253
254
255
256
257
258
259
























































































































260
261
262
263
264
265
266
do_test where2-6.6 {
  queryplan {
    SELECT b.* FROM t1 a, t1 b
     WHERE a.w=1 AND (b.z=10 OR a.y=b.z OR b.z=10)
     ORDER BY +b.w
  }
} [list 1 0 4 4 2 1 9 10 sort a i1w b $::idx]

























































































































# Unique queries (queries that are guaranteed to return only a single
# row of result) do not call the sorter.  But all tables must give
# a unique result.  If any one table in the join does not give a unique
# result then sorting is necessary.
#
do_test where2-7.1 {







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







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
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
do_test where2-6.6 {
  queryplan {
    SELECT b.* FROM t1 a, t1 b
     WHERE a.w=1 AND (b.z=10 OR a.y=b.z OR b.z=10)
     ORDER BY +b.w
  }
} [list 1 0 4 4 2 1 9 10 sort a i1w b $::idx]

# Ticket #2249.  Make sure the OR optimization is not attempted if
# comparisons between columns of different affinities are needed.
#
do_test where2-6.7 {
  execsql {
    CREATE TABLE t2249a(a TEXT UNIQUE);
    CREATE TABLE t2249b(b INTEGER);
    INSERT INTO t2249a VALUES('0123');
    INSERT INTO t2249b VALUES(123);
  }
  queryplan {
    -- Because a is type TEXT and b is type INTEGER, both a and b
    -- will attempt to convert to NUMERIC before the comparison.
    -- They will thus compare equal.
    --
    SELECT * FROM t2249b CROSS JOIN t2249a WHERE a=b;
  }
} {123 0123 nosort t2249b {} t2249a {}}
do_test where2-6.9 {
  queryplan {
    -- The + operator removes affinity from the rhs.  No conversions
    -- occur and the comparison is false.  The result is an empty set.
    --
    SELECT * FROM t2249b CROSS JOIN t2249a WHERE a=+b;
  }
} {nosort t2249b {} {} sqlite_autoindex_t2249a_1}
do_test where2-6.9.2 {
  # The same thing but with the expression flipped around.
  queryplan {
    SELECT * FROM t2249b CROSS JOIN t2249a WHERE +b=a
  }
} {nosort t2249b {} {} sqlite_autoindex_t2249a_1}
do_test where2-6.10 {
  queryplan {
    -- Use + on both sides of the comparison to disable indices
    -- completely.  Make sure we get the same result.
    --
    SELECT * FROM t2249b CROSS JOIN t2249a WHERE +a=+b;
  }
} {nosort t2249b {} t2249a {}}
do_test where2-6.11 {
  # This will not attempt the OR optimization because of the a=b
  # comparison.
  queryplan {
    SELECT * FROM t2249b CROSS JOIN t2249a WHERE a=b OR a='hello';
  }
} {123 0123 nosort t2249b {} t2249a {}}
do_test where2-6.11.2 {
  # Permutations of the expression terms.
  queryplan {
    SELECT * FROM t2249b CROSS JOIN t2249a WHERE b=a OR a='hello';
  }
} {123 0123 nosort t2249b {} t2249a {}}
do_test where2-6.11.3 {
  # Permutations of the expression terms.
  queryplan {
    SELECT * FROM t2249b CROSS JOIN t2249a WHERE 'hello'=a OR b=a;
  }
} {123 0123 nosort t2249b {} t2249a {}}
do_test where2-6.11.4 {
  # Permutations of the expression terms.
  queryplan {
    SELECT * FROM t2249b CROSS JOIN t2249a WHERE a='hello' OR b=a;
  }
} {123 0123 nosort t2249b {} t2249a {}}
do_test where2-6.12 {
  # In this case, the +b disables the affinity conflict and allows
  # the OR optimization to be used again.  The result is now an empty
  # set, the same as in where2-6.9.
  queryplan {
    SELECT * FROM t2249b CROSS JOIN t2249a WHERE a=+b OR a='hello';
  }
} {nosort t2249b {} {} sqlite_autoindex_t2249a_1}
do_test where2-6.12.2 {
  # In this case, the +b disables the affinity conflict and allows
  # the OR optimization to be used again.  The result is now an empty
  # set, the same as in where2-6.9.
  queryplan {
    SELECT * FROM t2249b CROSS JOIN t2249a WHERE a='hello' OR +b=a;
  }
} {nosort t2249b {} {} sqlite_autoindex_t2249a_1}
do_test where2-6.12.3 {
  # In this case, the +b disables the affinity conflict and allows
  # the OR optimization to be used again.  The result is now an empty
  # set, the same as in where2-6.9.
  queryplan {
    SELECT * FROM t2249b CROSS JOIN t2249a WHERE +b=a OR a='hello';
  }
} {nosort t2249b {} {} sqlite_autoindex_t2249a_1}
do_test where2-6.13 {
  # The addition of +a on the second term disabled the OR optimization.
  # But we should still get the same empty-set result as in where2-6.9.
  queryplan {
    SELECT * FROM t2249b CROSS JOIN t2249a WHERE a=+b OR +a='hello';
  }
} {nosort t2249b {} t2249a {}}

# Variations on the order of terms in a WHERE clause in order
# to make sure the OR optimizer can recognize them all.
do_test where2-6.20 {
  queryplan {
    SELECT * FROM t2249a x CROSS JOIN t2249a y WHERE x.a=y.a
  }
} {0123 0123 nosort x {} {} sqlite_autoindex_t2249a_1}
do_test where2-6.21 {
  queryplan {
    SELECT * FROM t2249a x CROSS JOIN t2249a y WHERE x.a=y.a OR y.a='hello'
  }
} {0123 0123 nosort x {} {} sqlite_autoindex_t2249a_1}
do_test where2-6.22 {
  queryplan {
    SELECT * FROM t2249a x CROSS JOIN t2249a y WHERE y.a=x.a OR y.a='hello'
  }
} {0123 0123 nosort x {} {} sqlite_autoindex_t2249a_1}
do_test where2-6.23 {
  queryplan {
    SELECT * FROM t2249a x CROSS JOIN t2249a y WHERE y.a='hello' OR x.a=y.a
  }
} {0123 0123 nosort x {} {} sqlite_autoindex_t2249a_1}

# Unique queries (queries that are guaranteed to return only a single
# row of result) do not call the sorter.  But all tables must give
# a unique result.  If any one table in the join does not give a unique
# result then sorting is necessary.
#
do_test where2-7.1 {