/ Check-in [75cda864]
Login

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

Overview
Comment:Test cases and bug fixes applied to the ORDER BY optimization for joins. Some test cases fail, but except for the new orderby1.test failures, all failures appear to be issues with the tests, not with the core code.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | qp-enhancements
Files: files | file ages | folders
SHA1:75cda864ededb6dc0f84bd52ed3311753a58e351
User & Date: drh 2012-09-27 17:31:32
Context
2012-09-27
19:53
More test cases an bug fixes for the ORDER BY optimization of joins. All veryquick tests now pass. check-in: 0d573320 user: drh tags: qp-enhancements
17:31
Test cases and bug fixes applied to the ORDER BY optimization for joins. Some test cases fail, but except for the new orderby1.test failures, all failures appear to be issues with the tests, not with the core code. check-in: 75cda864 user: drh tags: qp-enhancements
15:05
Add more bits to the bit vector that is used to disable optimizations for built-in test. Add specific bit patterns to disable ORDER BY using an index in general and for joins. Use macros to test for bits in the disabled-optimization bit vector, in order to make the code clearer. check-in: d2fcba1e user: drh tags: qp-enhancements
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

2879
2880
2881
2882
2883
2884
2885




2886
2887
2888
2889
2890


2891
2892
2893

2894
2895




2896
2897
2898
2899
2900
2901
2902
....
3196
3197
3198
3199
3200
3201
3202
3203
3204

3205
3206
3207
3208
3209
3210
3211
  WhereLevel *pLevel = &p->aLevel[p->i-1];
  Index *pIdx;
  u8 sortOrder;
  for(i=p->i-1; i>=0; i--, pLevel--){
    if( pLevel->iTabCur!=iTab ) continue;
    if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
      pIdx = pLevel->plan.u.pIdx;




      for(j=0; j<pIdx->nColumn; j++){
        if( iCol==pIdx->aiColumn[j] ) break;
      }
      if( j>=pIdx->nColumn ) return 0;
      sortOrder = pIdx->aSortOrder[j];


    }else{
      if( iCol!=(-1) ) return 0;
      sortOrder = 0;

    }
    if( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 ) sortOrder = 1 - sortOrder;




    if( *pbRev==2 ){
      *pbRev = sortOrder;
      return 1;
    }
    return (*pbRev==sortOrder);
  }
  return 0;
................................................................................
      testcase( bRev==1 );
      testcase( bRev==2 );
      nOBSat = isSortingIndex(p, pProbe, iCur, nOrdered,
                              wsFlags, bRev&1, &bRev);
      if( nOrderBy==nOBSat ){
        bSort = 0;
        wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_ORDERBY;
        wsFlags |= (bRev==1 ? WHERE_REVERSE : 0);
      }

    }

    /* If there is a DISTINCT qualifier and this index will scan rows in
    ** order of the DISTINCT expressions, clear bDist and set the appropriate
    ** flags in wsFlags. */
    if( bDist
     && isDistinctIndex(pParse, pWC, pProbe, iCur, p->pDistinct, nEq)







>
>
>
>
|
|
|
|
|
>
>



>

|
>
>
>
>







 







<

>







2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
....
3207
3208
3209
3210
3211
3212
3213

3214
3215
3216
3217
3218
3219
3220
3221
3222
  WhereLevel *pLevel = &p->aLevel[p->i-1];
  Index *pIdx;
  u8 sortOrder;
  for(i=p->i-1; i>=0; i--, pLevel--){
    if( pLevel->iTabCur!=iTab ) continue;
    if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
      pIdx = pLevel->plan.u.pIdx;
      if( iCol<0 ){
        sortOrder = 0;
        testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 );
      }else{
        for(j=0; j<pIdx->nColumn; j++){
          if( iCol==pIdx->aiColumn[j] ) break;
        }
        if( j>=pIdx->nColumn ) return 0;
        sortOrder = pIdx->aSortOrder[j];
        testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 );
      }
    }else{
      if( iCol!=(-1) ) return 0;
      sortOrder = 0;
      testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 );
    }
    if( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 ){
      assert( sortOrder==0 || sortOrder==1 );
      testcase( sortOrder==1 );
      sortOrder = 1 - sortOrder;
    }
    if( *pbRev==2 ){
      *pbRev = sortOrder;
      return 1;
    }
    return (*pbRev==sortOrder);
  }
  return 0;
................................................................................
      testcase( bRev==1 );
      testcase( bRev==2 );
      nOBSat = isSortingIndex(p, pProbe, iCur, nOrdered,
                              wsFlags, bRev&1, &bRev);
      if( nOrderBy==nOBSat ){
        bSort = 0;
        wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_ORDERBY;

      }
      if( bRev ) wsFlags |= WHERE_REVERSE;
    }

    /* If there is a DISTINCT qualifier and this index will scan rows in
    ** order of the DISTINCT expressions, clear bDist and set the appropriate
    ** flags in wsFlags. */
    if( bDist
     && isDistinctIndex(pParse, pWC, pProbe, iCur, p->pDistinct, nEq)

Changes to test/collate4.test.

385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
      DROP INDEX collate4i1;
      CREATE INDEX collate4i1 ON collate4t1(a);
    }
    count {
      SELECT a FROM collate4t1 WHERE a IN (SELECT * FROM collate4t2)
       ORDER BY rowid
    }
  } {a A 6}
  do_test collate4-2.1.8 {
    count {
      SELECT a FROM collate4t1 WHERE a IN ('z', 'a');
    }
  } {a A 5}
  do_test collate4-2.1.9 {
    execsql {







|







385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
      DROP INDEX collate4i1;
      CREATE INDEX collate4i1 ON collate4t1(a);
    }
    count {
      SELECT a FROM collate4t1 WHERE a IN (SELECT * FROM collate4t2)
       ORDER BY rowid
    }
  } {a A 5}
  do_test collate4-2.1.8 {
    count {
      SELECT a FROM collate4t1 WHERE a IN ('z', 'a');
    }
  } {a A 5}
  do_test collate4-2.1.9 {
    execsql {

Changes to test/collate5.test.

217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
...
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
# These tests - collate5-3.* - focus on compound SELECT queries that 
# feature ORDER BY clauses.
#
do_test collate5-3.0 {
  execsql {
    SELECT a FROM collate5t1 UNION ALL SELECT a FROM collate5t2 ORDER BY 1;
  }
} {a A a A b B b B n N}
do_test collate5-3.1 {
  execsql {
    SELECT a FROM collate5t2 UNION ALL SELECT a FROM collate5t1 ORDER BY 1;
  }
} {A A B B N a a b b n}
do_test collate5-3.2 {
  execsql {
................................................................................
    SELECT a, count(*) FROM collate5t1 GROUP BY a;
  }]
} {a 2 b 2}
do_test collate5-4.2 {
  execsql {
    SELECT a, b, count(*) FROM collate5t1 GROUP BY a, b ORDER BY a, b;
  }
} {A 1.0 2 b 2 1 B 3 1}
do_test collate5-4.3 {
  execsql {
    DROP TABLE collate5t1;
  }
} {}

finish_test







|







 







|







217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
...
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
# These tests - collate5-3.* - focus on compound SELECT queries that 
# feature ORDER BY clauses.
#
do_test collate5-3.0 {
  execsql {
    SELECT a FROM collate5t1 UNION ALL SELECT a FROM collate5t2 ORDER BY 1;
  }
} {/[aA] [aA] [aA] [aA] [bB] [bB] [bB] [bB] [nN] [nN]/}
do_test collate5-3.1 {
  execsql {
    SELECT a FROM collate5t2 UNION ALL SELECT a FROM collate5t1 ORDER BY 1;
  }
} {A A B B N a a b b n}
do_test collate5-3.2 {
  execsql {
................................................................................
    SELECT a, count(*) FROM collate5t1 GROUP BY a;
  }]
} {a 2 b 2}
do_test collate5-4.2 {
  execsql {
    SELECT a, b, count(*) FROM collate5t1 GROUP BY a, b ORDER BY a, b;
  }
} {/[aA] 1(.0)? 2 [bB] 2 1 [bB] 3 1/}
do_test collate5-4.3 {
  execsql {
    DROP TABLE collate5t1;
  }
} {}

finish_test

Added test/orderby1.test.























































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
# 2012 Sept 27
#
# 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 that the optimizations that disable
# ORDER BY clauses when the natural order of a query is correct.
#


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

# Generate test data for a join.  Verify that the join gets the
# correct answer.
#
do_test 1.0 {
  db eval {
    BEGIN;
    CREATE TABLE album(
      aid INTEGER PRIMARY KEY,
      title TEXT UNIQUE NOT NULL
    );
    CREATE TABLE track(
      tid INTEGER PRIMARY KEY,
      aid INTEGER NOT NULL REFERENCES album,
      tn INTEGER NOT NULL,
      name TEXT,
      UNIQUE(aid, tn)
    );
    INSERT INTO album VALUES(1, '1-one'), (2, '2-two'), (3, '3-three');
    INSERT INTO track VALUES
        (NULL, 1, 1, 'one-a'),
        (NULL, 2, 2, 'two-b'),
        (NULL, 3, 3, 'three-c'),
        (NULL, 1, 3, 'one-c'),
        (NULL, 2, 1, 'two-a'),
        (NULL, 3, 1, 'three-a');
    COMMIT;
  }
} {}
do_test 1.1a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {one-a one-c two-a two-b three-a three-c}

# Verify that the ORDER BY clause is optimized out
#
do_test 1.1b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {~/ORDER BY/}  ;# ORDER BY optimized out

# The same query with ORDER BY clause optimization disabled via + operators
# should give exactly the same answer.
#
do_test 1.2a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
  }
} {one-a one-c two-a two-b three-a three-c}

# The output is sorted manually in this case.
#
do_test 1.2b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
  }
} {/ORDER BY/}   ;# separate sorting pass due to "+" on ORDER BY terms

# The same query with ORDER BY optimizations turned off via built-in test.
#
do_test 1.3a {
  optimization_control db order-by-idx-join 0
  db cache flush
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {one-a one-c two-a two-b three-a three-c}
do_test 1.3b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {/ORDER BY/}   ;# separate sorting pass due to disabled optimization
optimization_control db all 1
db cache flush

# Reverse order sorts
#
do_test 1.4a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {three-a three-c two-a two-b one-a one-c}
do_test 1.4b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn
  }
} {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
do_test 1.4c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {~/ORDER BY/}  ;# ORDER BY optimized-out


do_test 1.5a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}
do_test 1.5b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}  ;# verify same order after sorting
do_test 1.5c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {~/ORDER BY/}  ;# ORDER BY optimized-out

do_test 1.6a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}
do_test 1.6b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
do_test 1.6c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {~/ORDER BY/}  ;# ORDER BY optimized-out


finish_test