/ Check-in [abcf6a5d]
Login

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

Overview
Comment:More lenient handling of ORDER BY optimization in joins with mixed ASC/DESC. This is a better and less restrictive fix for the problem addressed by the previous check-in.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:abcf6a5d054559ee5a093ba39180c47b4958d9cd
User & Date: drh 2012-10-02 15:19:19
References
2013-06-04
14:56 Ticket [5ed17728] Incorrect ORDER BY on an indexed JOIN status still Open with 6 other changes artifact: 114ba533 user: drh
14:48 New ticket [5ed17728]. artifact: 33be471b user: drh
Context
2012-10-02
22:54
Work around an optimization issue with the MSVC compiler for ARM. check-in: 7d301fdf user: mistachkin tags: trunk
15:19
More lenient handling of ORDER BY optimization in joins with mixed ASC/DESC. This is a better and less restrictive fix for the problem addressed by the previous check-in. check-in: abcf6a5d user: drh tags: trunk
14:11
Only continue an ORDER BY optimization into inner loops if the equality constraints on the inner loop match terms of an outer ordered index that are actually used by the ORDER BY clause. check-in: b0e7b4df user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
....
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
....
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
    }
    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{
        int n = pLevel->plan.nOBSat;
        if( p->i>=2 ) n -= pLevel[-1].plan.nOBSat;
        assert( n<=pIdx->nColumn );
        for(j=0; j<n; j++){
          if( iCol==pIdx->aiColumn[j] ) break;
        }
        if( j>=n ) return 0;
        sortOrder = pIdx->aSortOrder[j];
        testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 );
      }
................................................................................
    if( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return nPriorSat;
  }
  if( p->i==0 || (p->aLevel[p->i-1].plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
    nEqOneRow = nEqCol;
  }else{
    if( nEqCol==0 ) return nPriorSat;
    sortOrder = bOuterRev;
    nEqOneRow = 0;
  }
  pOrderBy = p->pOrderBy;
  assert( pOrderBy!=0 );
  if( wsFlags & WHERE_COLUMN_IN ) return nPriorSat;
  if( pIdx->bUnordered ) return nPriorSat;
  nTerm = pOrderBy->nExpr;
  assert( nTerm>0 );
................................................................................
    assert( pIdx->aSortOrder!=0 || iColumn==-1 );
    assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );
    assert( iSortOrder==0 || iSortOrder==1 );
    termSortOrder = iSortOrder ^ pTerm->sortOrder;
    if( i>nEqOneRow ){
      if( termSortOrder!=sortOrder ){
        /* Indices can only be used if all ORDER BY terms past the
        ** equality constraints are all either DESC or ASC. */
        break;
      }
    }else{
      sortOrder = termSortOrder;
    }
    j++;
    pTerm++;







<
<
|







 







|







 







|







2732
2733
2734
2735
2736
2737
2738


2739
2740
2741
2742
2743
2744
2745
2746
....
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
....
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
    }
    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{


        int n = pIdx->nColumn;
        for(j=0; j<n; j++){
          if( iCol==pIdx->aiColumn[j] ) break;
        }
        if( j>=n ) return 0;
        sortOrder = pIdx->aSortOrder[j];
        testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 );
      }
................................................................................
    if( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return nPriorSat;
  }
  if( p->i==0 || (p->aLevel[p->i-1].plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
    nEqOneRow = nEqCol;
  }else{
    if( nEqCol==0 ) return nPriorSat;
    sortOrder = bOuterRev;
    nEqOneRow = -1;
  }
  pOrderBy = p->pOrderBy;
  assert( pOrderBy!=0 );
  if( wsFlags & WHERE_COLUMN_IN ) return nPriorSat;
  if( pIdx->bUnordered ) return nPriorSat;
  nTerm = pOrderBy->nExpr;
  assert( nTerm>0 );
................................................................................
    assert( pIdx->aSortOrder!=0 || iColumn==-1 );
    assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );
    assert( iSortOrder==0 || iSortOrder==1 );
    termSortOrder = iSortOrder ^ pTerm->sortOrder;
    if( i>nEqOneRow ){
      if( termSortOrder!=sortOrder ){
        /* Indices can only be used if all ORDER BY terms past the
        ** equality constraints have the correct DESC or ASC. */
        break;
      }
    }else{
      sortOrder = termSortOrder;
    }
    j++;
    pTerm++;

Changes to test/orderby1.test.

190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
...
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
# Verify that the ORDER BY clause is optimized out
#
do_test 2.1b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {/ORDER BY/}  ;# ORDER BY required because of missing aid term in ORDER BY

do_test 2.1c {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, aid, tn
  }
} {one-a one-c two-a two-b three-a three-c}
do_test 2.1d {
................................................................................
  }
} {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
do_test 2.6c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {/ORDER BY/}  ;# ORDER BY required


# Generate another test dataset, but this time using mixed ASC/DESC indices.
#
do_test 3.0 {
  db eval {
    BEGIN;







|







 







|







190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
...
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
# Verify that the ORDER BY clause is optimized out
#
do_test 2.1b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {~/ORDER BY/}  ;# ORDER BY optimized out

do_test 2.1c {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, aid, tn
  }
} {one-a one-c two-a two-b three-a three-c}
do_test 2.1d {
................................................................................
  }
} {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
do_test 2.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


# Generate another test dataset, but this time using mixed ASC/DESC indices.
#
do_test 3.0 {
  db eval {
    BEGIN;