Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Disable an overzealous optimization the omitted sorting on a join if the first table gave a unique result. The sort can only be omitted if all tables in the join are unique. Ticket #1358. (CVS 2589) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
4f07661279fb11a06b3ddffeda672f07 |
User & Date: | drh 2005-08-13 16:13:05.000 |
Context
2005-08-13
| ||
17:17 | Give the same access permissions to journal files as is given to databases. (CVS 2590) (check-in: 7961ec0ccb user: drh tags: trunk) | |
16:13 | Disable an overzealous optimization the omitted sorting on a join if the first table gave a unique result. The sort can only be omitted if all tables in the join are unique. Ticket #1358. (CVS 2589) (check-in: 4f07661279 user: drh tags: trunk) | |
13:40 | Fix a comment in printf. (CVS 2588) (check-in: 1054685f15 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.161 2005/08/13 16:13:05 drh Exp $ */ #include "sqliteInt.h" /* ** The number of bits in a Bitmask. "BMS" means "BitMask Size". */ #define BMS (sizeof(Bitmask)*8) |
︙ | ︙ | |||
715 716 717 718 719 720 721 | ** left-most table in the FROM clause of that same SELECT statement and ** the table has a cursor number of "base". pIdx is an index on pTab. ** ** nEqCol is the number of columns of pIdx that are used as equality ** constraints. Any of these columns may be missing from the ORDER BY ** clause and the match can still be a success. ** | < < < < | 715 716 717 718 719 720 721 722 723 724 725 726 727 728 | ** left-most table in the FROM clause of that same SELECT statement and ** the table has a cursor number of "base". pIdx is an index on pTab. ** ** nEqCol is the number of columns of pIdx that are used as equality ** constraints. Any of these columns may be missing from the ORDER BY ** clause and the match can still be a success. ** ** All terms of the ORDER BY that match against the index must be either ** ASC or DESC. (Terms of the ORDER BY clause past the end of a UNIQUE ** index do not need to satisfy this constraint.) The *pbRev value is ** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if ** the ORDER BY clause is all ASC. */ static int isSortingIndex( |
︙ | ︙ | |||
787 788 789 790 791 792 793 | sortOrder = pTerm->sortOrder; } j++; pTerm++; } /* The index can be used for sorting if all terms of the ORDER BY clause | < | | | 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 | sortOrder = pTerm->sortOrder; } j++; pTerm++; } /* The index can be used for sorting if all terms of the ORDER BY clause ** are covered. */ if( j>=nTerm ){ *pbRev = sortOrder==SQLITE_SO_DESC; return 1; } return 0; } /* |
︙ | ︙ | |||
825 826 827 828 829 830 831 | /* ** Prepare a crude estimate of the logorithm of the input value. ** The results need not be exact. This is only used for estimating ** the total cost of performing operatings with O(logN) or O(NlogN) ** complexity. Because N is just a guess, it is no great tragedy if ** logN is a little off. | < < | | 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 | /* ** Prepare a crude estimate of the logorithm of the input value. ** The results need not be exact. This is only used for estimating ** the total cost of performing operatings with O(logN) or O(NlogN) ** complexity. Because N is just a guess, it is no great tragedy if ** logN is a little off. */ static double estLog(double N){ double logN = 1.0; double x = 10.0; while( N>x ){ logN += 1.0; x *= 10; } return logN; } /* ** Find the best index for accessing a particular table. Return a pointer |
︙ | ︙ | |||
1009 1010 1011 1012 1013 1014 1015 | } } /* Add the additional cost of sorting if that is a factor. */ if( pOrderBy ){ if( (flags & WHERE_COLUMN_IN)==0 && | | | 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 | } } /* Add the additional cost of sorting if that is a factor. */ if( pOrderBy ){ if( (flags & WHERE_COLUMN_IN)==0 && isSortingIndex(pParse,pProbe,pSrc->pTab,iCur,pOrderBy,nEq,&rev) ){ if( flags==0 ){ flags = WHERE_COLUMN_RANGE; } flags |= WHERE_ORDERBY; if( rev ){ flags |= WHERE_REVERSE; } |
︙ | ︙ |
Changes to test/sort.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 CREATE TABLE statement. # | | | 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 CREATE TABLE statement. # # $Id: sort.test,v 1.22 2005/08/13 16:13:06 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Create a bunch of data to sort against # do_test sort-1.0 { |
︙ | ︙ | |||
426 427 428 429 430 431 432 433 434 | } } {3 2 1} do_test sort-10.3 { execsql { SELECT c FROM t7 WHERE c<3 ORDER BY c DESC; } } {2 1} finish_test | > > > > > > > > > > > > > > > > | 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 | } } {3 2 1} do_test sort-10.3 { execsql { SELECT c FROM t7 WHERE c<3 ORDER BY c DESC; } } {2 1} # ticket #1358. Just because one table in a join gives a unique # result does not mean they all do. We cannot disable sorting unless # all tables in the join give unique results. # do_test sort-11.1 { execsql { create table t8(a unique, b, c); insert into t8 values(1,2,3); insert into t8 values(2,3,4); create table t9(x,y); insert into t9 values(2,4); insert into t9 values(2,3); select y from t8, t9 where a=1 order by a, y; } } {3 4} 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.5 2005/08/13 16:13:06 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Build some test data # do_test where2-1.0 { |
︙ | ︙ | |||
234 235 236 237 238 239 240 | 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 } } {1 0 4 4 2 1 9 10 sort a i1w b i1zyx} | > > > > | > > > > > > > > > | > > > > > > > > > > > > > > > > > > | 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 | 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 } } {1 0 4 4 2 1 9 10 sort a i1w b i1zyx} # 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 { cksort { create table t8(a unique, b, c); insert into t8 values(1,2,3); insert into t8 values(2,3,4); create table t9(x,y); insert into t9 values(2,4); insert into t9 values(2,3); select y from t8, t9 where a=1 order by a, y; } } {3 4 sort} do_test where2-7.2 { cksort { select * from t8 where a=1 order by b, c } } {1 2 3 nosort} do_test where2-7.3 { cksort { select * from t8, t9 where a=1 and y=3 order by b, x } } {1 2 3 2 3 sort} do_test where2-7.4 { cksort { create unique index i9y on t9(y); select * from t8, t9 where a=1 and y=3 order by b, x } } {1 2 3 2 3 nosort} finish_test |