SQLite

Check-in [abcf6a5d05]
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
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: abcf6a5d054559ee5a093ba39180c47b4958d9cd
User & Date: drh 2012-10-02 15:19:19.625
References
2013-06-04
14:56 Ticket [5ed1772895] Incorrect ORDER BY on an indexed JOIN status still Open with 6 other changes (artifact: 114ba533cd user: drh)
14:48 New ticket [5ed1772895]. (artifact: 33be471b72 user: drh)
Context
2012-10-02
22:54
Work around an optimization issue with the MSVC compiler for ARM. (check-in: 7d301fdfee 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: abcf6a5d05 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: b0e7b4df6c user: drh tags: trunk)
Changes
Unified Diff 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
    }
    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 );
      }







<
<
|







2732
2733
2734
2735
2736
2737
2738


2739
2740
2741
2742
2743
2744
2745
2746
    }
    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 );
      }
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
    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 );







|







2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
    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 );
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
    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++;







|







2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
    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
# 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 {







|







190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
# 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 {
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
  }
} {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;







|







292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
  }
} {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;