Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | The BETWEEN operator in a WHERE clause is now able to use indices. (CVS 2568) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
cdf8c9584b945212e065e044df801c20 |
User & Date: | drh 2005-07-28 23:12:08.000 |
Context
2005-07-29
| ||
15:10 | Optimizer now converts OR-connected WHERE-clause terms into an IN operator so that they can be used with indices. There are known problems with the ORDER BY optimization in this and in several prior check-ins. This check-in is not recommended for production use. (CVS 2569) (check-in: d23c8bf81e user: drh tags: trunk) | |
2005-07-28
| ||
23:12 | The BETWEEN operator in a WHERE clause is now able to use indices. (CVS 2568) (check-in: cdf8c9584b user: drh tags: trunk) | |
20:51 | Test cases and tuning of the new optimizer code. (CVS 2567) (check-in: 4b02703dec user: drh tags: trunk) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
12 13 14 15 16 17 18 | ** 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". ** | | | 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.156 2005/07/28 23:12:08 drh Exp $ */ #include "sqliteInt.h" /* ** The number of bits in a Bitmask. "BMS" means "BitMask Size". */ #define BMS (sizeof(Bitmask)*8) |
︙ | ︙ | |||
82 83 84 85 86 87 88 89 90 91 92 93 94 95 | Expr *pExpr; /* Pointer to the subexpression */ u16 idx; /* Index of this term in pWC->a[] */ i16 iPartner; /* Disable pWC->a[iPartner] when this term disabled */ u16 flags; /* Bit flags. See below */ i16 leftCursor; /* Cursor number of X in "X <op> <expr>" */ i16 leftColumn; /* Column number of X in "X <op> <expr>" */ u16 operator; /* A WO_xx value describing <op> */ WhereClause *pWC; /* The clause this term is part of */ Bitmask prereqRight; /* Bitmask of tables used by pRight */ Bitmask prereqAll; /* Bitmask of tables referenced by p */ }; /* ** Allowed values of WhereTerm.flags | > | 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | Expr *pExpr; /* Pointer to the subexpression */ u16 idx; /* Index of this term in pWC->a[] */ i16 iPartner; /* Disable pWC->a[iPartner] when this term disabled */ u16 flags; /* Bit flags. See below */ i16 leftCursor; /* Cursor number of X in "X <op> <expr>" */ i16 leftColumn; /* Column number of X in "X <op> <expr>" */ u16 operator; /* A WO_xx value describing <op> */ u8 nPartner; /* Number of partners that must disable us */ WhereClause *pWC; /* The clause this term is part of */ Bitmask prereqRight; /* Bitmask of tables used by pRight */ Bitmask prereqAll; /* Bitmask of tables referenced by p */ }; /* ** Allowed values of WhereTerm.flags |
︙ | ︙ | |||
473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 | WhereTerm *pNew; Expr *pDup; if( pTerm->leftCursor>=0 ){ pDup = sqlite3ExprDup(pExpr); pNew = whereClauseInsert(pTerm->pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC); if( pNew==0 ) return; pNew->iPartner = pTerm->idx; }else{ pDup = pExpr; pNew = pTerm; } exprCommute(pDup); pLeft = pDup->pLeft; pNew->leftCursor = pLeft->iTable; pNew->leftColumn = pLeft->iColumn; pNew->prereqRight = prereqLeft; pNew->prereqAll = prereqAll; pNew->operator = operatorMask(pDup->op); } } } /* ** This routine decides if pIdx can be used to satisfy the ORDER BY ** clause. If it can, it returns 1. If pIdx cannot satisfy the ** ORDER BY clause, this routine returns 0. | > > > > > > > > > > > > > > > > > > > > > > > > > | 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 | WhereTerm *pNew; Expr *pDup; if( pTerm->leftCursor>=0 ){ pDup = sqlite3ExprDup(pExpr); pNew = whereClauseInsert(pTerm->pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC); if( pNew==0 ) return; pNew->iPartner = pTerm->idx; pTerm->nPartner = 1; }else{ pDup = pExpr; pNew = pTerm; } exprCommute(pDup); pLeft = pDup->pLeft; pNew->leftCursor = pLeft->iTable; pNew->leftColumn = pLeft->iColumn; pNew->prereqRight = prereqLeft; pNew->prereqAll = prereqAll; pNew->operator = operatorMask(pDup->op); } } /* If a term is the BETWEEN operator, create two new virtual terms ** that define the range that the BETWEEN implements. */ else if( pExpr->op==TK_BETWEEN ){ ExprList *pList = pExpr->pList; int i; static const u8 ops[] = {TK_GE, TK_LE}; assert( pList!=0 ); assert( pList->nExpr==2 ); for(i=0; i<2; i++){ Expr *pNewExpr; WhereTerm *pNewTerm; pNewExpr = sqlite3Expr(ops[i], sqlite3ExprDup(pExpr->pLeft), sqlite3ExprDup(pList->a[i].pExpr), 0); pNewTerm = whereClauseInsert(pTerm->pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC); exprAnalyze(pSrc, pMaskSet, pNewTerm); pNewTerm->iPartner = pTerm->idx; } pTerm->nPartner = 2; } } /* ** This routine decides if pIdx can be used to satisfy the ORDER BY ** clause. If it can, it returns 1. If pIdx cannot satisfy the ** ORDER BY clause, this routine returns 0. |
︙ | ︙ | |||
886 887 888 889 890 891 892 | static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){ if( pTerm && (pTerm->flags & TERM_CODED)==0 && (pLevel->iLeftJoin==0 || ExprHasProperty(pTerm->pExpr, EP_FromJoin)) ){ pTerm->flags |= TERM_CODED; if( pTerm->iPartner>=0 ){ | > > | > | 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 | static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){ if( pTerm && (pTerm->flags & TERM_CODED)==0 && (pLevel->iLeftJoin==0 || ExprHasProperty(pTerm->pExpr, EP_FromJoin)) ){ pTerm->flags |= TERM_CODED; if( pTerm->iPartner>=0 ){ WhereTerm *pOther = &pTerm->pWC->a[pTerm->iPartner]; if( (--pOther->nPartner)<=0 ){ disableTerm(pLevel, pOther); } } } } /* ** Generate code that builds a probe for an index. Details: ** |
︙ | ︙ |
Added test/between.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 | # 2005 July 28 # # 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 # when the WHERE clause contains the BETWEEN operator. # # $Id: between.test,v 1.1 2005/07/28 23:12:08 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Build some test data # do_test between-1.0 { execsql { BEGIN; CREATE TABLE t1(w int, x int, y int, z 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}] set z [expr {$x+$y}] execsql {INSERT INTO t1 VALUES($::w,$::x,$::y,$::z)} } execsql { CREATE UNIQUE INDEX i1w ON t1(w); CREATE INDEX i1xy ON t1(x,y); CREATE INDEX i1zyx ON t1(z,y,x); COMMIT; } } {} # This procedure executes the SQL. Then it appends to the result the # "sort" or "nosort" keyword depending on whether or not any sorting # is done. Then it appends the ::sqlite_query_plan variable. # proc queryplan {sql} { set ::sqlite_sort_count 0 set data [execsql $sql] if {$::sqlite_sort_count} {set x sort} {set x nosort} lappend data $x return [concat $data $::sqlite_query_plan] } do_test between-1.1.1 { queryplan { SELECT * FROM t1 WHERE w BETWEEN 5 AND 6 ORDER BY +w } } {5 2 36 38 6 2 49 51 sort t1 i1w} do_test between-1.1.2 { queryplan { SELECT * FROM t1 WHERE +w BETWEEN 5 AND 6 ORDER BY +w } } {5 2 36 38 6 2 49 51 sort t1 {}} do_test between-1.2.1 { queryplan { SELECT * FROM t1 WHERE w BETWEEN 5 AND 65-y ORDER BY +w } } {5 2 36 38 6 2 49 51 sort t1 i1w} do_test between-1.2.2 { queryplan { SELECT * FROM t1 WHERE +w BETWEEN 5 AND 65-y ORDER BY +w } } {5 2 36 38 6 2 49 51 sort t1 {}} do_test between-1.3.1 { queryplan { SELECT * FROM t1 WHERE w BETWEEN 41-y AND 6 ORDER BY +w } } {5 2 36 38 6 2 49 51 sort t1 i1w} do_test between-1.3.2 { queryplan { SELECT * FROM t1 WHERE +w BETWEEN 41-y AND 6 ORDER BY +w } } {5 2 36 38 6 2 49 51 sort t1 {}} do_test between-1.4 { queryplan { SELECT * FROM t1 WHERE w BETWEEN 41-y AND 65-y ORDER BY +w } } {5 2 36 38 6 2 49 51 sort t1 {}} do_test between-1.5.1 { queryplan { SELECT * FROM t1 WHERE 26 BETWEEN y AND z ORDER BY +w } } {4 2 25 27 sort t1 i1zyx} do_test between-1.5.2 { queryplan { SELECT * FROM t1 WHERE 26 BETWEEN +y AND z ORDER BY +w } } {4 2 25 27 sort t1 i1zyx} do_test between-1.5.3 { queryplan { SELECT * FROM t1 WHERE 26 BETWEEN y AND +z ORDER BY +w } } {4 2 25 27 sort t1 {}} finish_test |
Changes to test/where2.test.
︙ | ︙ | |||
8 9 10 11 12 13 14 | # 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. # | | | 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.2 2005/07/28 23:12:08 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Build some test data # do_test where2-1.0 { |
︙ | ︙ | |||
196 197 198 199 200 201 202 | } } {99 6 10000 10006 nosort t1 i1w} do_test where2-5.2 { queryplan { SELECT * FROM t1 WHERE w IN (99) ORDER BY w } } {99 6 10000 10006 sort t1 i1w} | < | 196 197 198 199 200 201 202 203 204 205 206 | } } {99 6 10000 10006 nosort t1 i1w} do_test where2-5.2 { queryplan { SELECT * FROM t1 WHERE w IN (99) ORDER BY w } } {99 6 10000 10006 sort t1 i1w} integrity_check {where2-99.0} finish_test |