SQLite

Check-in [efbb4bc83c]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Fix over-aggressive optimization of ORDER BY as reported on the mailing list. (CVS 2655)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: efbb4bc83cd86b6a26d58c5818c58c2e3edaab18
User & Date: drh 2005-09-01 17:47:51.000
Context
2005-09-05
19:08
Use the unicode API to win32 where available. Tickets #1407, #1396, #1331, #1243, #1206 (CVS 2656) (check-in: 3ec58c673a user: drh tags: trunk)
2005-09-01
17:47
Fix over-aggressive optimization of ORDER BY as reported on the mailing list. (CVS 2655) (check-in: efbb4bc83c user: drh tags: trunk)
12:16
All regression tests now pass with the new bounded-memory sort code. There is still lots of opportunity for optimization, however. (CVS 2654) (check-in: 81259a01f1 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
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.167 2005/08/29 16:40:53 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)







|







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.168 2005/09/01 17:47:51 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
809
810
811
812
813
814
815
816

817
818
819
820
821
822
823
  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;
}

/*







|
>







809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
  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( pOrderBy->nExpr==1 && p->op==TK_COLUMN && p->iTable==base
          && p->iColumn==-1 ){
    *pbRev = pOrderBy->a[0].sortOrder;
    return 1;
  }
  return 0;
}

/*
Changes to test/sort.test.
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 {













|







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.23 2005/09/01 17:47:52 drh Exp $

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

# Create a bunch of data to sort against
#
do_test sort-1.0 {
442
443
444
445
446
447
448
449

















450
    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








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

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
    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}

# Trouble reported on the mailing list.  Check for overly aggressive
# (which is to say, incorrect) optimization of order-by with a rowid
# in a join.
#
do_test sort-12.1 {
  execsql {
    create table a (id integer primary key);
    create table b (id integer primary key, aId integer, text);
    insert into a values (1);
    insert into b values (2, 1, 'xxx');
    insert into b values (1, 1, 'zzz');
    insert into b values (3, 1, 'yyy');
    select a.id, b.id, b.text from a join b on (a.id = b.aId)
      order by a.id, b.text;
  }
} {1 2 xxx 1 3 yyy 1 1 zzz}

finish_test
Changes to test/where.test.
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.34 2005/09/01 12:16:29 drh Exp $

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

# Build some test data
#
do_test where-1.0 {













|







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.35 2005/09/01 17:47:52 drh Exp $

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

# Build some test data
#
do_test where-1.0 {
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
630
    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;







|




|




|




|














|







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
630
    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 sort}
do_test where-6.22 {
  cksort {
    SELECT y FROM t1 ORDER BY rowid, y DESC LIMIT 3;
  }
} {4 9 16 sort}
do_test where-6.23 {
  cksort {
    SELECT y FROM t1 WHERE y>4 ORDER BY rowid, w, x LIMIT 3;
  }
} {9 16 25 sort}
do_test where-6.24 {
  cksort {
    SELECT y FROM t1 WHERE y>=9 ORDER BY rowid, x DESC, w LIMIT 3;
  }
} {9 16 25 sort}
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 sort}


# Tests for reverse-order sorting.
#
do_test where-7.1 {
  cksort {
    SELECT w FROM t1 WHERE x=3 ORDER BY y;
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
do_test where-7.31 {
  cksort {
    SELECT y FROM t1 ORDER BY rowid DESC LIMIT 3
  }
} {10201 10000 9801 nosort}
do_test where-7.32 {
  cksort {
    SELECT y FROM t1 WHERE y<25 ORDER BY rowid DESC, x
  }
} {16 9 4 nosort}
do_test where-7.33 {
  cksort {
    SELECT y FROM t1 WHERE y<=25 ORDER BY rowid DESC, x
  }
} {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 {







|




|






|







778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
do_test where-7.31 {
  cksort {
    SELECT y FROM t1 ORDER BY rowid DESC LIMIT 3
  }
} {10201 10000 9801 nosort}
do_test where-7.32 {
  cksort {
    SELECT y FROM t1 WHERE y<25 ORDER BY rowid DESC
  }
} {16 9 4 nosort}
do_test where-7.33 {
  cksort {
    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 sort}
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 {