Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Fixes to the logic that decides if the ORDER BY can be ignored due to the use of an index. Tests updated. (CVS 796) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
bfb9a2aa939ecffc5dc2c7c23bddd57d |
User & Date: | drh 2002-12-04 21:50:16.000 |
Context
2002-12-04
| ||
22:29 | Fix a bug in the reverse scan logic that comes up when the table being scanned is empty. Add additional tests for the reverse scan. (CVS 797) (check-in: 0051c87d5e user: drh tags: trunk) | |
21:50 | Fixes to the logic that decides if the ORDER BY can be ignored due to the use of an index. Tests updated. (CVS 796) (check-in: bfb9a2aa93 user: drh tags: trunk) | |
20:01 | Scan the table backwards if there is an ORDER BY ... DESC clause that can be satisfied by an index. (CVS 795) (check-in: c7a3487981 user: drh tags: trunk) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
9 10 11 12 13 14 15 | ** May you share freely, never taking more than you give. ** ************************************************************************* ** This module contains C code that generates VDBE code used to process ** the WHERE clause of SQL statements. Also found here are subroutines ** to generate VDBE code to evaluate expressions. ** | | | 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | ** May you share freely, never taking more than you give. ** ************************************************************************* ** This module contains C code that generates VDBE code used to process ** the WHERE clause of SQL statements. Also found here are subroutines ** to generate VDBE code to evaluate expressions. ** ** $Id: where.c,v 1.69 2002/12/04 21:50:16 drh Exp $ */ #include "sqliteInt.h" /* ** The query generator uses an array of instances of this structure to ** help it analyze the subexpressions of the WHERE clause. Each WHERE ** clause subexpression is separated from the others by an AND operator. |
︙ | ︙ | |||
160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 | ** This routine attempts to find an index for pTab that generates the ** correct record sequence for the given ORDER BY clause. The return value ** is a pointer to an index that does the job. NULL is returned if the ** table has no index that will generate the correct sort order. ** ** If there are two or more indices that generate the correct sort order ** and pPreferredIdx is one of those indices, then return pPreferredIdx. */ static Index *findSortingIndex( Table *pTab, /* The table to be sorted */ int base, /* Cursor number for pTab */ ExprList *pOrderBy, /* The ORDER BY clause */ Index *pPreferredIdx, /* Use this index, if possible and not NULL */ int *pbRev /* Set to 1 if ORDER BY is DESC */ ){ | > > > > > > > > > > | | 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 | ** This routine attempts to find an index for pTab that generates the ** correct record sequence for the given ORDER BY clause. The return value ** is a pointer to an index that does the job. NULL is returned if the ** table has no index that will generate the correct sort order. ** ** If there are two or more indices that generate the correct sort order ** and pPreferredIdx is one of those indices, then return pPreferredIdx. ** ** nEqCol is the number of columns of pPreferredIdx that are used as ** equality constraints. Any index returned must have exactly this same ** set of columns. The ORDER BY clause only matches index columns beyond the ** the first nEqCol columns. ** ** All terms of the ORDER BY clause must be either ASC or DESC. 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 Index *findSortingIndex( Table *pTab, /* The table to be sorted */ int base, /* Cursor number for pTab */ ExprList *pOrderBy, /* The ORDER BY clause */ Index *pPreferredIdx, /* Use this index, if possible and not NULL */ int nEqCol, /* Number of index columns used with == constraints */ int *pbRev /* Set to 1 if ORDER BY is DESC */ ){ int i, j; Index *pMatch; Index *pIdx; int sortOrder; assert( pOrderBy!=0 ); assert( pOrderBy->nExpr>0 ); sortOrder = pOrderBy->a[0].sortOrder & SQLITE_SO_DIRMASK; |
︙ | ︙ | |||
201 202 203 204 205 206 207 | /* If we get this far, it means the ORDER BY clause consists only of ** ascending columns in the left-most table of the FROM clause. Now ** check for a matching index. */ pMatch = 0; for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){ | | > > > > > > | | | | 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 | /* If we get this far, it means the ORDER BY clause consists only of ** ascending columns in the left-most table of the FROM clause. Now ** check for a matching index. */ pMatch = 0; for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){ int nExpr = pOrderBy->nExpr; if( pIdx->nColumn < nEqCol || pIdx->nColumn < nExpr ) continue; for(i=j=0; i<nEqCol; i++){ if( pPreferredIdx->aiColumn[i]!=pIdx->aiColumn[i] ) break; if( j<nExpr && pOrderBy->a[j].pExpr->iColumn==pIdx->aiColumn[i] ){ j++; } } if( i<nEqCol ) continue; for(i=0; i+j<nExpr; i++){ if( pOrderBy->a[i+j].pExpr->iColumn!=pIdx->aiColumn[i+nEqCol] ) break; } if( i+j>=nExpr ){ pMatch = pIdx; if( pIdx==pPreferredIdx ) break; } } if( pMatch && pbRev ){ *pbRev = sortOrder==SQLITE_SO_DESC; } |
︙ | ︙ | |||
617 618 619 620 621 622 623 | pSortIdx = 0; }else if( iDirectEq[0]>=0 || iDirectLt[0]>=0 || iDirectGt[0]>=0 ){ /* If the left-most column is accessed using its ROWID, then do ** not try to sort by index. */ pSortIdx = 0; }else{ | > | | 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 | pSortIdx = 0; }else if( iDirectEq[0]>=0 || iDirectLt[0]>=0 || iDirectGt[0]>=0 ){ /* If the left-most column is accessed using its ROWID, then do ** not try to sort by index. */ pSortIdx = 0; }else{ int nEqCol = (pWInfo->a[0].score+4)/8; pSortIdx = findSortingIndex(pTab, base, *ppOrderBy, pIdx, nEqCol, &bRev); } if( pSortIdx && (pIdx==0 || pIdx==pSortIdx) ){ if( pIdx==0 ){ pWInfo->a[0].pIdx = pSortIdx; pWInfo->a[0].iCur = pParse->nTab++; pWInfo->peakNTab = pParse->nTab; } |
︙ | ︙ |
Changes to test/format3.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 the library is able to correctly # handle file-format 3 (version 2.6.x) databases. # | | | 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 the library is able to correctly # handle file-format 3 (version 2.6.x) databases. # # $Id: format3.test,v 1.2 2002/12/04 21:50:16 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Create a bunch of data to sort against # do_test format3-1.0 { |
︙ | ︙ | |||
634 635 636 637 638 639 640 641 642 643 644 645 646 647 | SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a,c,b LIMIT 3 } } {1 100 4 nosort} do_test format3-10.13 { cksort { SELECT * FROM t3 WHERE a>0 ORDER BY a DESC LIMIT 3 } } {100 1 10201 99 2 10000 98 3 9801 sort} do_test format3-10.14 { cksort { SELECT * FROM t3 ORDER BY b LIMIT 3 } } {100 1 10201 99 2 10000 98 3 9801 nosort} do_test format3-10.15 { | > > > > > | 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 | SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a,c,b LIMIT 3 } } {1 100 4 nosort} do_test format3-10.13 { cksort { SELECT * FROM t3 WHERE a>0 ORDER BY a DESC LIMIT 3 } } {100 1 10201 99 2 10000 98 3 9801 nosort} do_test format3-10.13.1 { cksort { SELECT * FROM t3 WHERE a>0 ORDER BY a+1 DESC LIMIT 3 } } {100 1 10201 99 2 10000 98 3 9801 sort} do_test format3-10.14 { cksort { SELECT * FROM t3 ORDER BY b LIMIT 3 } } {100 1 10201 99 2 10000 98 3 9801 nosort} do_test format3-10.15 { |
︙ | ︙ |
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.12 2002/12/04 21:50:16 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Build some test data # do_test where-1.0 { |
︙ | ︙ | |||
411 412 413 414 415 416 417 | } } {1 100 4 2 99 9 3 98 16 sort} do_test where-6.8 { cksort { SELECT * FROM t3 WHERE a IN (3,5,7,1,9,4,2) ORDER BY a LIMIT 3 } } {1 100 4 2 99 9 3 98 16 sort} | | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 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 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 | } } {1 100 4 2 99 9 3 98 16 sort} do_test where-6.8 { cksort { SELECT * FROM t3 WHERE a IN (3,5,7,1,9,4,2) ORDER BY a LIMIT 3 } } {1 100 4 2 99 9 3 98 16 sort} do_test where-6.9.1 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a LIMIT 3 } } {1 100 4 nosort} do_test where-6.9.2 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a,c LIMIT 3 } } {1 100 4 nosort} do_test where-6.9.3 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY c LIMIT 3 } } {1 100 4 nosort} do_test where-6.9.4 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a DESC LIMIT 3 } } {1 100 4 nosort} do_test where-6.9.5 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a DESC, c DESC LIMIT 3 } } {1 100 4 nosort} do_test where-6.9.6 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY c DESC LIMIT 3 } } {1 100 4 nosort} do_test where-6.9.7 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY c,a LIMIT 3 } } {1 100 4 sort} do_test where-6.9.8 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a DESC, c ASC LIMIT 3 } } {1 100 4 sort} do_test where-6.9.9 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a ASC, c DESC LIMIT 3 } } {1 100 4 sort} do_test where-6.10 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a LIMIT 3 } } {1 100 4 nosort} do_test where-6.11 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a,c LIMIT 3 } } {1 100 4 nosort} do_test where-6.12 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a,c,b LIMIT 3 } } {1 100 4 nosort} do_test where-6.13 { cksort { SELECT * FROM t3 WHERE a>0 ORDER BY a DESC LIMIT 3 } } {100 1 10201 99 2 10000 98 3 9801 nosort} do_test where-6.13.1 { cksort { SELECT * FROM t3 WHERE a>0 ORDER BY -a LIMIT 3 } } {100 1 10201 99 2 10000 98 3 9801 sort} do_test where-6.14 { cksort { SELECT * FROM t3 ORDER BY b LIMIT 3 } } {100 1 10201 99 2 10000 98 3 9801 nosort} do_test where-6.15 { |
︙ | ︙ | |||
467 468 469 470 471 472 473 | } {4 9 16 sort} do_test where-6.19 { cksort { SELECT y FROM t1 ORDER BY w LIMIT 3; } } {4 9 16 nosort} | > | > > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 | } {4 9 16 sort} do_test where-6.19 { cksort { SELECT y FROM t1 ORDER BY w LIMIT 3; } } {4 9 16 nosort} # Tests for reverse-order sorting. # do_test where-7.1 { cksort { SELECT w FROM t1 WHERE x=3 ORDER BY y; } } {8 9 10 11 12 13 14 15 nosort} do_test where-7.2 { cksort { SELECT w FROM t1 WHERE x=3 ORDER BY y DESC; } } {15 14 13 12 11 10 9 8 nosort} do_test where-7.3 { cksort { SELECT w FROM t1 WHERE x=3 AND y>100 ORDER BY y LIMIT 3; } } {10 11 12 nosort} do_test where-7.4 { cksort { SELECT w FROM t1 WHERE x=3 AND y>100 ORDER BY y DESC LIMIT 3; } } {15 14 13 nosort} do_test where-7.5 { cksort { SELECT w FROM t1 WHERE x=3 AND y>121 ORDER BY y DESC; } } {15 14 13 12 11 nosort} do_test where-7.6 { cksort { SELECT w FROM t1 WHERE x=3 AND y>=121 ORDER BY y DESC; } } {15 14 13 12 11 10 nosort} do_test where-7.7 { cksort { SELECT w FROM t1 WHERE x=3 AND y>=121 AND y<196 ORDER BY y DESC; } } {12 11 10 nosort} do_test where-7.8 { cksort { SELECT w FROM t1 WHERE x=3 AND y>=121 AND y<=196 ORDER BY y DESC; } } {13 12 11 10 nosort} do_test where-7.9 { cksort { SELECT w FROM t1 WHERE x=3 AND y>121 AND y<=196 ORDER BY y DESC; } } {13 12 11 nosort} do_test where-7.10 { cksort { SELECT w FROM t1 WHERE x=3 AND y>100 AND y<196 ORDER BY y DESC; } } {12 11 10 nosort} do_test where-7.11 { cksort { SELECT w FROM t1 WHERE x=3 AND y>=121 AND y<196 ORDER BY y; } } {10 11 12 nosort} do_test where-7.12 { cksort { SELECT w FROM t1 WHERE x=3 AND y>=121 AND y<=196 ORDER BY y; } } {10 11 12 13 nosort} do_test where-7.13 { cksort { SELECT w FROM t1 WHERE x=3 AND y>121 AND y<=196 ORDER BY y; } } {11 12 13 nosort} do_test where-7.14 { cksort { SELECT w FROM t1 WHERE x=3 AND y>100 AND y<196 ORDER BY y; } } {10 11 12 nosort} finish_test |