/ Check-in [b920bb70]
Login

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

Overview
Comment:Add a new ORDER BY optimization that bypasses ORDER BY terms that are constrained by == and IS NULL terms of the WHERE clause.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1:b920bb70bb009b7c54e7667544c9810c5ee25e19
User & Date: drh 2013-06-14 02:51:48
Context
2013-06-14
13:27
Comment tweaks in where.c. No changes to code. check-in: cecc5fdd user: drh tags: nextgen-query-plan-exp
02:51
Add a new ORDER BY optimization that bypasses ORDER BY terms that are constrained by == and IS NULL terms of the WHERE clause. check-in: b920bb70 user: drh tags: nextgen-query-plan-exp
2013-06-13
17:58
An index might be useful for ORDER BY if any indexed column is in the ORDER BY clause, not just the first indexed column. check-in: ade473b5 user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

4887
4888
4889
4890
4891
4892
4893
4894
4895
4896
4897
4898
4899
4900
4901
....
4927
4928
4929
4930
4931
4932
4933

4934

4935
4936
4937



























4938
4939
4940
4941
4942
4943
4944
....
5062
5063
5064
5065
5066
5067
5068
5069
5070
5071
5072
5073
5074
5075
5076
  Expr *pOBExpr;        /* An expression from the ORDER BY clause */
  CollSeq *pColl;       /* COLLATE function from an ORDER BY clause term */
  Index *pIndex;        /* The index associated with pLoop */
  sqlite3 *db = pWInfo->pParse->db;  /* Database connection */
  Bitmask obSat = 0;    /* Mask of ORDER BY terms satisfied so far */
  Bitmask obDone;       /* Mask of all ORDER BY terms */
  Bitmask orderDistinctMask;  /* Mask of all well-ordered loops */
  

  /*
  ** We say the WhereLoop is "one-row" if it generates no more than one
  ** row of output.  A WhereLoop is one-row if all of the following are true:
  **  (a) All index columns match with WHERE_COLUMN_EQ.
  **  (b) The index is unique
  ** Any WhereLoop with an WHERE_COLUMN_EQ constraint on the rowid is one-row.
................................................................................
  if( nLoop && OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return 0;

  nOrderBy = pOrderBy->nExpr;
  if( nOrderBy>BMS-1 ) return 0;  /* Cannot optimize overly large ORDER BYs */
  isOrderDistinct = 1;
  obDone = MASKBIT(nOrderBy)-1;
  orderDistinctMask = 0;

  for(iLoop=0; isOrderDistinct && obSat<obDone && iLoop<=nLoop; iLoop++){

    pLoop = iLoop<nLoop ? pPath->aLoop[iLoop] : pLast;
    assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
    iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;



























    if( (pLoop->wsFlags & WHERE_ONEROW)==0 ){
      if( pLoop->wsFlags & WHERE_IPK ){
        pIndex = 0;
        nColumn = 0;
      }else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){
        return 0;
      }else{
................................................................................
        if( MASKBIT(i) & obSat ) continue;
        p = pOrderBy->a[i].pExpr;
        if( (exprTableUsage(&pWInfo->sMaskSet, p)&~orderDistinctMask)==0 ){
          obSat |= MASKBIT(i);
        }
      }
    }
  }
  if( obSat==obDone ) return 1;
  if( !isOrderDistinct ) return 0;
  if( isLastLoop ) return 1;
  return -1;
}

#ifdef WHERETRACE_ENABLED







|







 







>

>



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







 







|







4887
4888
4889
4890
4891
4892
4893
4894
4895
4896
4897
4898
4899
4900
4901
....
4927
4928
4929
4930
4931
4932
4933
4934
4935
4936
4937
4938
4939
4940
4941
4942
4943
4944
4945
4946
4947
4948
4949
4950
4951
4952
4953
4954
4955
4956
4957
4958
4959
4960
4961
4962
4963
4964
4965
4966
4967
4968
4969
4970
4971
4972
4973
....
5091
5092
5093
5094
5095
5096
5097
5098
5099
5100
5101
5102
5103
5104
5105
  Expr *pOBExpr;        /* An expression from the ORDER BY clause */
  CollSeq *pColl;       /* COLLATE function from an ORDER BY clause term */
  Index *pIndex;        /* The index associated with pLoop */
  sqlite3 *db = pWInfo->pParse->db;  /* Database connection */
  Bitmask obSat = 0;    /* Mask of ORDER BY terms satisfied so far */
  Bitmask obDone;       /* Mask of all ORDER BY terms */
  Bitmask orderDistinctMask;  /* Mask of all well-ordered loops */
  Bitmask ready;              /* Mask of inner loops */

  /*
  ** We say the WhereLoop is "one-row" if it generates no more than one
  ** row of output.  A WhereLoop is one-row if all of the following are true:
  **  (a) All index columns match with WHERE_COLUMN_EQ.
  **  (b) The index is unique
  ** Any WhereLoop with an WHERE_COLUMN_EQ constraint on the rowid is one-row.
................................................................................
  if( nLoop && OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return 0;

  nOrderBy = pOrderBy->nExpr;
  if( nOrderBy>BMS-1 ) return 0;  /* Cannot optimize overly large ORDER BYs */
  isOrderDistinct = 1;
  obDone = MASKBIT(nOrderBy)-1;
  orderDistinctMask = 0;
  ready = 0;
  for(iLoop=0; isOrderDistinct && obSat<obDone && iLoop<=nLoop; iLoop++){
    if( iLoop>0 ) ready |= pLoop->maskSelf;
    pLoop = iLoop<nLoop ? pPath->aLoop[iLoop] : pLast;
    assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
    iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;

    /* Mark off any ORDER BY term X that is a column in the table of
    ** the current loop for which there is term in the WHERE
    ** clause of the form X IS NULL or X=? that reference only outer
    ** loops.
    */
    for(i=0; i<nOrderBy; i++){
      if( MASKBIT(i) & obSat ) continue;
      pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
      if( pOBExpr->op!=TK_COLUMN ) continue;
      if( pOBExpr->iTable!=iCur ) continue;
      pTerm = findTerm(&pWInfo->sWC, iCur, pOBExpr->iColumn,
                       ~ready, WO_EQ|WO_ISNULL, 0);
      if( pTerm==0 ) continue;
      if( pOBExpr->iColumn>=0 ){
        const char *z1, *z2;
        pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);
        if( !pColl ) pColl = db->pDfltColl;
        z1 = pColl->zName;
        pColl = sqlite3ExprCollSeq(pWInfo->pParse, pTerm->pExpr);
        if( !pColl ) pColl = db->pDfltColl;
        z2 = pColl->zName;
        if( sqlite3StrICmp(z1, z2)!=0 ) continue;
      }
      obSat |= MASKBIT(i);
    }

    if( (pLoop->wsFlags & WHERE_ONEROW)==0 ){
      if( pLoop->wsFlags & WHERE_IPK ){
        pIndex = 0;
        nColumn = 0;
      }else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){
        return 0;
      }else{
................................................................................
        if( MASKBIT(i) & obSat ) continue;
        p = pOrderBy->a[i].pExpr;
        if( (exprTableUsage(&pWInfo->sMaskSet, p)&~orderDistinctMask)==0 ){
          obSat |= MASKBIT(i);
        }
      }
    }
  } /* End the loop over all WhereLoops from outer-most down to inner-most */
  if( obSat==obDone ) return 1;
  if( !isOrderDistinct ) return 0;
  if( isLastLoop ) return 1;
  return -1;
}

#ifdef WHERETRACE_ENABLED

Added test/orderby5.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
# 2013-06-14
#
# 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 work correctly
#


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

# Generate test data for a join.  Verify that the join gets the
# correct answer.
#
do_execsql_test 1.1 {
  CREATE TABLE t1(a,b,c);
  CREATE INDEX t1bc ON t1(b,c);

  EXPLAIN QUERY PLAN
  SELECT DISTINCT a, b, c FROM t1 WHERE a=0;
} {~/B-TREE/}
do_execsql_test 1.2.1 {
  EXPLAIN QUERY PLAN
  SELECT DISTINCT a, c, b FROM t1 WHERE a=0;
} {~/B-TREE/}
do_execsql_test 1.2.2 {
  EXPLAIN QUERY PLAN
  SELECT DISTINCT a, c, b FROM t1 WHERE a='xyz' COLLATE nocase;
} {/B-TREE/}
do_execsql_test 1.2.3 {
  EXPLAIN QUERY PLAN
  SELECT DISTINCT a COLLATE nocase, c, b FROM t1 WHERE a='xyz';
} {/B-TREE/}
do_execsql_test 1.2.4 {
  EXPLAIN QUERY PLAN
  SELECT DISTINCT a COLLATE nocase, c, b FROM t1 WHERE a='xyz' COLLATE nocase;
} {~/B-TREE/}
do_execsql_test 1.3 {
  EXPLAIN QUERY PLAN
  SELECT DISTINCT b, a, c FROM t1 WHERE a=0;
} {~/B-TREE/}
do_execsql_test 1.4 {
  EXPLAIN QUERY PLAN
  SELECT DISTINCT b, c, a FROM t1 WHERE a=0;
} {~/B-TREE/}
do_execsql_test 1.5 {
  EXPLAIN QUERY PLAN
  SELECT DISTINCT c, a, b FROM t1 WHERE a=0;
} {~/B-TREE/}
do_execsql_test 1.6 {
  EXPLAIN QUERY PLAN
  SELECT DISTINCT c, b, a FROM t1 WHERE a=0;
} {~/B-TREE/}
do_execsql_test 1.7 {
  EXPLAIN QUERY PLAN
  SELECT DISTINCT c, b, a FROM t1 WHERE +a=0;
} {/B-TREE/}
do_execsql_test 2.1 {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE a=0 ORDER BY a, b, c;
} {~/B-TREE/}
do_execsql_test 2.2 {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE +a=0 ORDER BY a, b, c;
} {/B-TREE/}
do_execsql_test 2.3 {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE a=0 ORDER BY b, a, c;
} {~/B-TREE/}
do_execsql_test 2.4 {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE a=0 ORDER BY b, c, a;
} {~/B-TREE/}
do_execsql_test 2.5 {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE a=0 ORDER BY a, c, b;
} {/B-TREE/}
do_execsql_test 2.6 {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE a=0 ORDER BY c, a, b;
} {/B-TREE/}
do_execsql_test 2.7 {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE a=0 ORDER BY c, b, a;
} {/B-TREE/}


finish_test