Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | The query optimizer does a better job of optimizing out ORDER BY clauses that contain the rowid or which use indices that contain the rowid. Ticket #2116. (CVS 3536) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
f245f5c2c2d337fe6458824beb7f9e72 |
User & Date: | drh 2006-12-20 03:24:19.000 |
Context
2006-12-20
| ||
03:37 | Patch to get extension loading working on wince. Ticket #2023. (CVS 3537) (check-in: a81f3ddfd0 user: drh tags: trunk) | |
03:24 | The query optimizer does a better job of optimizing out ORDER BY clauses that contain the rowid or which use indices that contain the rowid. Ticket #2116. (CVS 3536) (check-in: f245f5c2c2 user: drh tags: trunk) | |
02:15 | Allow constraint names on DEFAULT values in a table definition. Ticket #2109. (CVS 3535) (check-in: 893d58c23d 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.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) |
︙ | ︙ | |||
864 865 866 867 868 869 870 871 | assert( pOrderBy!=0 ); nTerm = pOrderBy->nExpr; assert( nTerm>0 ); /* Match terms of the ORDER BY clause against columns of ** the index. */ | > > > > > | > > > > | > > | > > > > > > > > > > | | | > > > > > > > | | | | < > | > > > > > | < | 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 | assert( pOrderBy!=0 ); nTerm = pOrderBy->nExpr; assert( nTerm>0 ); /* Match terms of the ORDER BY clause against columns of ** the index. ** ** Note that indices have pIdx->nColumn regular columns plus ** one additional column containing the rowid. The rowid column ** of the index is also allowed to match against the ORDER BY ** clause. */ for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<=pIdx->nColumn; i++){ Expr *pExpr; /* The expression of the ORDER BY pTerm */ CollSeq *pColl; /* The collating sequence of pExpr */ int termSortOrder; /* Sort order for this term */ int iColumn; /* The i-th column of the index. -1 for rowid */ int iSortOrder; /* 1 for DESC, 0 for ASC on the i-th index term */ const char *zColl; /* Name of the collating sequence for i-th index term */ pExpr = pTerm->pExpr; if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){ /* Can not use an index sort on anything that is not a column in the ** left-most table of the FROM clause */ return 0; } pColl = sqlite3ExprCollSeq(pParse, pExpr); if( !pColl ){ pColl = db->pDfltColl; } if( i<pIdx->nColumn ){ iColumn = pIdx->aiColumn[i]; if( iColumn==pIdx->pTable->iPKey ){ iColumn = -1; } iSortOrder = pIdx->aSortOrder[i]; zColl = pIdx->azColl[i]; }else{ iColumn = -1; iSortOrder = 0; zColl = pColl->zName; } if( pExpr->iColumn!=iColumn || sqlite3StrICmp(pColl->zName, zColl) ){ /* Term j of the ORDER BY clause does not match column i of the index */ if( i<nEqCol ){ /* If an index column that is constrained by == fails to match an ** ORDER BY term, that is OK. Just ignore that column of the index */ continue; }else{ /* If an index column fails to match and is not constrained by == ** then the index cannot satisfy the ORDER BY constraint. */ return 0; } } assert( pIdx->aSortOrder!=0 ); assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 ); assert( iSortOrder==0 || iSortOrder==1 ); termSortOrder = iSortOrder ^ pTerm->sortOrder; if( i>nEqCol ){ if( termSortOrder!=sortOrder ){ /* Indices can only be used if all ORDER BY terms past the ** equality constraints are all either DESC or ASC. */ return 0; } }else{ sortOrder = termSortOrder; } j++; pTerm++; if( iColumn<0 ){ /* If the indexed column is the primary key and everything matches ** so far, then we are assured that the index can be used to sort ** because the primary key is unique and so none of the other columns ** will make any difference */ j = nTerm; } } *pbRev = sortOrder!=0; if( j>=nTerm ){ /* All terms of the ORDER BY clause are covered by this index so ** this index can be used for sorting. */ return 1; } if( j==pIdx->nColumn && pIdx->onError!=OE_None ){ /* All terms of this index match some prefix of the ORDER BY clause ** and this index is UNIQUE, so this index can be used for sorting. */ return 1; } return 0; } /* ** Check table to see if the ORDER BY clause in pOrderBy can be satisfied ** by sorting in order of ROWID. Return true if so and set *pbRev to be ** true for reverse ROWID and false for forward ROWID order. */ static int sortableByRowid( int base, /* Cursor number for table to be sorted */ ExprList *pOrderBy, /* The ORDER BY clause */ int *pbRev /* Set to 1 if ORDER BY is DESC */ ){ Expr *p; assert( pOrderBy!=0 ); assert( pOrderBy->nExpr>0 ); p = pOrderBy->a[0].pExpr; if( p->op==TK_COLUMN && p->iTable==base && p->iColumn==-1 ){ *pbRev = pOrderBy->a[0].sortOrder; return 1; } return 0; } /* |
︙ | ︙ |
Changes to test/where.test.
1 2 3 4 5 6 7 8 9 10 11 12 13 | # 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. # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this file is testing the use of indices in WHERE clases. # | | | 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. # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this file is testing the use of indices in WHERE clases. # # $Id: where.test,v 1.39 2006/12/20 03:24:19 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Build some test data # do_test where-1.0 { |
︙ | ︙ | |||
585 586 587 588 589 590 591 | SELECT y FROM t1 ORDER BY rowid LIMIT 3; } } {4 9 16 nosort} do_test where-6.21 { cksort { SELECT y FROM t1 ORDER BY rowid, y LIMIT 3; } | | | | | | | 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 | SELECT y FROM t1 ORDER BY rowid LIMIT 3; } } {4 9 16 nosort} do_test where-6.21 { cksort { SELECT y FROM t1 ORDER BY rowid, y LIMIT 3; } } {4 9 16 nosort} do_test where-6.22 { cksort { SELECT y FROM t1 ORDER BY rowid, y DESC LIMIT 3; } } {4 9 16 nosort} do_test where-6.23 { cksort { SELECT y FROM t1 WHERE y>4 ORDER BY rowid, w, x LIMIT 3; } } {9 16 25 nosort} do_test where-6.24 { cksort { SELECT y FROM t1 WHERE y>=9 ORDER BY rowid, x DESC, w LIMIT 3; } } {9 16 25 nosort} do_test where-6.25 { cksort { SELECT y FROM t1 WHERE y>4 AND y<25 ORDER BY rowid; } } {9 16 nosort} do_test where-6.26 { cksort { SELECT y FROM t1 WHERE y>=4 AND y<=25 ORDER BY oid; } } {4 9 16 25 nosort} do_test where-6.27 { cksort { SELECT y FROM t1 WHERE y<=25 ORDER BY _rowid_, w+y; } } {4 9 16 25 nosort} # Tests for reverse-order sorting. # do_test where-7.1 { cksort { SELECT w FROM t1 WHERE x=3 ORDER BY y; |
︙ | ︙ | |||
789 790 791 792 793 794 795 | SELECT y FROM t1 WHERE y<=25 ORDER BY rowid DESC } } {25 16 9 4 nosort} do_test where-7.34 { cksort { SELECT y FROM t1 WHERE y<25 AND y>4 ORDER BY rowid DESC, y DESC } | | | 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 | SELECT y FROM t1 WHERE y<=25 ORDER BY rowid DESC } } {25 16 9 4 nosort} do_test where-7.34 { cksort { SELECT y FROM t1 WHERE y<25 AND y>4 ORDER BY rowid DESC, y DESC } } {16 9 nosort} do_test where-7.35 { cksort { SELECT y FROM t1 WHERE y<25 AND y>=4 ORDER BY rowid DESC } } {16 9 4 nosort} do_test where-8.1 { |
︙ | ︙ | |||
870 871 872 873 874 875 876 | # Ticket #1376. The query below was causing a segfault. # The problem was the age-old error of calling realloc() on an # array while there are still pointers to individual elements of # that array. # do_test where-11.1 { | < | 870 871 872 873 874 875 876 877 878 879 880 881 882 883 | # Ticket #1376. The query below was causing a segfault. # The problem was the age-old error of calling realloc() on an # array while there are still pointers to individual elements of # that array. # do_test where-11.1 { execsql { CREATE TABLE t99(Dte INT, X INT); DELETE FROM t99 WHERE (Dte = 2451337) OR (Dte = 2451339) OR (Dte BETWEEN 2451345 AND 2451347) OR (Dte = 2451351) OR (Dte BETWEEN 2451355 AND 2451356) OR (Dte = 2451358) OR (Dte = 2451362) OR (Dte = 2451365) OR (Dte = 2451367) OR (Dte BETWEEN 2451372 AND 2451376) OR (Dte BETWEEN 2451382 AND 2451384) OR |
︙ | ︙ | |||
897 898 899 900 901 902 903 904 | (Dte BETWEEN 2451565 AND 2451566) OR (Dte BETWEEN 2451569 AND 2451571) OR (Dte = 2451573) OR (Dte = 2451575) OR (Dte = 2451577) OR (Dte = 2451581) OR (Dte BETWEEN 2451583 AND 2451586) OR (Dte BETWEEN 2451588 AND 2451592) OR (Dte BETWEEN 2451596 AND 2451598) OR (Dte = 2451600) OR (Dte BETWEEN 2451602 AND 2451603) OR (Dte = 2451606) OR (Dte = 2451611); } } {} | > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 | (Dte BETWEEN 2451565 AND 2451566) OR (Dte BETWEEN 2451569 AND 2451571) OR (Dte = 2451573) OR (Dte = 2451575) OR (Dte = 2451577) OR (Dte = 2451581) OR (Dte BETWEEN 2451583 AND 2451586) OR (Dte BETWEEN 2451588 AND 2451592) OR (Dte BETWEEN 2451596 AND 2451598) OR (Dte = 2451600) OR (Dte BETWEEN 2451602 AND 2451603) OR (Dte = 2451606) OR (Dte = 2451611); } } {} # Ticket #2116: Make sure sorting by index works well with nn INTEGER PRIMARY # KEY. # do_test where-12.1 { execsql { CREATE TABLE t6(a INTEGER PRIMARY KEY, b TEXT); INSERT INTO t6 VALUES(1,'one'); INSERT INTO t6 VALUES(4,'four'); CREATE INDEX t6i1 ON t6(b); } cksort { SELECT * FROM t6 ORDER BY b; } } {4 four 1 one nosort} do_test where-12.2 { cksort { SELECT * FROM t6 ORDER BY b, a; } } {4 four 1 one nosort} do_test where-12.3 { cksort { SELECT * FROM t6 ORDER BY a; } } {1 one 4 four nosort} do_test where-12.4 { cksort { SELECT * FROM t6 ORDER BY a, b; } } {1 one 4 four nosort} do_test where-12.5 { cksort { SELECT * FROM t6 ORDER BY b DESC; } } {1 one 4 four nosort} do_test where-12.6 { cksort { SELECT * FROM t6 ORDER BY b DESC, a DESC; } } {1 one 4 four nosort} do_test where-12.7 { cksort { SELECT * FROM t6 ORDER BY b DESC, a ASC; } } {1 one 4 four sort} do_test where-12.8 { cksort { SELECT * FROM t6 ORDER BY b ASC, a DESC; } } {4 four 1 one sort} do_test where-12.9 { cksort { SELECT * FROM t6 ORDER BY a DESC; } } {4 four 1 one nosort} do_test where-12.10 { cksort { SELECT * FROM t6 ORDER BY a DESC, b DESC; } } {4 four 1 one nosort} do_test where-12.11 { cksort { SELECT * FROM t6 ORDER BY a DESC, b ASC; } } {4 four 1 one nosort} do_test where-12.12 { cksort { SELECT * FROM t6 ORDER BY a ASC, b DESC; } } {1 one 4 four nosort} do_test where-13.1 { execsql { CREATE TABLE t7(a INTEGER PRIMARY KEY, b TEXT); INSERT INTO t7 VALUES(1,'one'); INSERT INTO t7 VALUES(4,'four'); CREATE INDEX t7i1 ON t7(b); } cksort { SELECT * FROM t7 ORDER BY b; } } {4 four 1 one nosort} do_test where-13.2 { cksort { SELECT * FROM t7 ORDER BY b, a; } } {4 four 1 one nosort} do_test where-13.3 { cksort { SELECT * FROM t7 ORDER BY a; } } {1 one 4 four nosort} do_test where-13.4 { cksort { SELECT * FROM t7 ORDER BY a, b; } } {1 one 4 four nosort} do_test where-13.5 { cksort { SELECT * FROM t7 ORDER BY b DESC; } } {1 one 4 four nosort} do_test where-13.6 { cksort { SELECT * FROM t7 ORDER BY b DESC, a DESC; } } {1 one 4 four nosort} do_test where-13.7 { cksort { SELECT * FROM t7 ORDER BY b DESC, a ASC; } } {1 one 4 four sort} do_test where-13.8 { cksort { SELECT * FROM t7 ORDER BY b ASC, a DESC; } } {4 four 1 one sort} do_test where-13.9 { cksort { SELECT * FROM t7 ORDER BY a DESC; } } {4 four 1 one nosort} do_test where-13.10 { cksort { SELECT * FROM t7 ORDER BY a DESC, b DESC; } } {4 four 1 one nosort} do_test where-13.11 { cksort { SELECT * FROM t7 ORDER BY a DESC, b ASC; } } {4 four 1 one nosort} do_test where-13.12 { cksort { SELECT * FROM t7 ORDER BY a ASC, b DESC; } } {1 one 4 four nosort} integrity_check {where-99.0} finish_test |