/ Check-in [bfb9a2aa]
Login

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 | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:bfb9a2aa939ecffc5dc2c7c23bddd57d357bdf13
User & Date: drh 2002-12-04 21:50:16
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: 0051c87d 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: bfb9a2aa 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: c7a34879 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
...
160
161
162
163
164
165
166









167
168
169
170
171
172

173
174
175
176
177
178
179
180
181
182
...
201
202
203
204
205
206
207
208






209
210
211
212
213
214
215
216
217
218
219
...
617
618
619
620
621
622
623

624
625
626
627
628
629
630
631
**    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.68 2002/12/04 20:01:06 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.
................................................................................
** 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 */
){
  int i;
  Index *pMatch;
  Index *pIdx;
  int sortOrder;

  assert( pOrderBy!=0 );
  assert( pOrderBy->nExpr>0 );
  sortOrder = pOrderBy->a[0].sortOrder & SQLITE_SO_DIRMASK;
................................................................................
  
  /* 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){
    if( pIdx->nColumn<pOrderBy->nExpr ) continue;






    for(i=0; i<pOrderBy->nExpr; i++){
      if( pOrderBy->a[i].pExpr->iColumn!=pIdx->aiColumn[i] ) break;
    }
    if( i>=pOrderBy->nExpr ){
      pMatch = pIdx;
      if( pIdx==pPreferredIdx ) break;
    }
  }
  if( pMatch && pbRev ){
    *pbRev = sortOrder==SQLITE_SO_DESC;
  }
................................................................................
       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{

       pSortIdx = findSortingIndex(pTab, base, *ppOrderBy, pIdx, &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;
       }







|







 







>
>
>
>
>
>
>
>
>






>


|







 







|
>
>
>
>
>
>
|
|

|







 







>
|







9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
...
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
...
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
...
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
**    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.
................................................................................
** 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;
................................................................................
  
  /* 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;
  }
................................................................................
       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
15
16
17
18
19
20
21
22
...
634
635
636
637
638
639
640





641
642
643
644
645
646
647
#    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.1 2002/08/31 16:52:45 drh Exp $

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

# Create a bunch of data to sort against
#
do_test format3-1.0 {
................................................................................
    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 {







|







 







>
>
>
>
>







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
#    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 {
................................................................................
    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.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
411
412
413
414
415
416
417
418
419
420
421
422








































423
424
425
426
427
428
429
...
435
436
437
438
439
440
441





442
443
444
445
446
447
448
...
467
468
469
470
471
472
473

474



475



































































476
#    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.11 2002/10/22 23:38:04 drh Exp $

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

# Build some test data
#
do_test where-1.0 {
................................................................................
  }
} {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 {
  cksort {
    SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a LIMIT 3
  }
} {1 100 4 nosort}








































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,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 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 {
................................................................................
} {4 9 16 sort}
do_test where-6.19 {
  cksort {
    SELECT y FROM t1 ORDER BY w LIMIT 3;
  }
} {4 9 16 nosort}










































































finish_test







|







 







|




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







 







>
>
>
>
>







 







>
|
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
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
...
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
...
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
#    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 {
................................................................................
  }
} {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,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 {
................................................................................
} {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