/ Check-in [62225b4a]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Improved ORDER BY optimization when outer loops of a join return a single row.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 62225b4a4c4bfe1820ef54cb202edf2cd866429f
User & Date: drh 2012-09-29 19:10:29
Context
2012-10-01
06:50
Ensure that the value returned by xSectorSize() is reasonable (currently defined as between 2^5 and 2^16 bytes) before using it to calculate the amount of padding to add to a wal file. check-in: 6b4ff83b user: dan tags: trunk
2012-09-29
19:10
Improved ORDER BY optimization when outer loops of a join return a single row. check-in: 62225b4a user: drh tags: trunk
15:45
Disable the bigfile tests on Macs. check-in: d869edda user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

253
254
255
256
257
258
259
260
261
262
263

264
265
266
267
268
269
270
....
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
....
2880
2881
2882
2883
2884
2885
2886



2887
2888
2889
2890
2891
2892
2893
....
2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944


































































































































































2945
2946
2947
2948
2949
2950
2951
....
3173
3174
3175
3176
3177
3178
3179



3180
3181
3182
3183
3184
3185
3186
#define WHERE_COLUMN_NULL  0x00080000  /* x IS NULL */
#define WHERE_INDEXED      0x000f0000  /* Anything that uses an index */
#define WHERE_NOT_FULLSCAN 0x100f3000  /* Does not do a full table scan */
#define WHERE_IN_ABLE      0x000f1000  /* Able to support an IN operator */
#define WHERE_TOP_LIMIT    0x00100000  /* x<EXPR or x<=EXPR constraint */
#define WHERE_BTM_LIMIT    0x00200000  /* x>EXPR or x>=EXPR constraint */
#define WHERE_BOTH_LIMIT   0x00300000  /* Both x>EXPR and x<EXPR */
#define WHERE_IDX_ONLY     0x00800000  /* Use index only - omit table */
#define WHERE_ORDERBY      0x01000000  /* Output will appear in correct order */
#define WHERE_REVERSE      0x02000000  /* Scan in reverse order */
#define WHERE_UNIQUE       0x04000000  /* Selects no more than one row */

#define WHERE_VIRTUALTABLE 0x08000000  /* Use virtual-table processing */
#define WHERE_MULTI_OR     0x10000000  /* OR using multiple indices */
#define WHERE_TEMP_INDEX   0x20000000  /* Uses an ephemeral index */
#define WHERE_DISTINCT     0x40000000  /* Correct order for DISTINCT */
#define WHERE_COVER_SCAN   0x80000000  /* Full scan of a covering index */

/*
................................................................................
      return 1;
    }
  }

  return 0;
}

/*
** This routine decides if pIdx can be used to satisfy the ORDER BY
** clause, either in whole or in part.  The return value is the 
** cumulative number of terms in the ORDER BY clause that are satisfied
** by the index pIdx and other indices in outer loops.
**
** The table being queried has a cursor number of "base".  pIdx is the
** index that is postulated for use to access the table.
**
** nEqCol is the number of columns of pIdx that are used as equality
** constraints and where the other side of the == is an ordered column
** or constant.  An "order column" in the previous sentence means a column
** in table from an outer loop whose values will always appear in the 
** correct order due to othre index, or because the outer loop generates
** a unique result.  Any of the first nEqCol columns of pIdx may be missing
** from the ORDER BY clause and the match can still be a success.
**
** The *pbRev value is set to 0 order 1 depending on whether or not
** pIdx should be run in the forward order or in reverse order.
*/
static int isSortingIndex(
  WhereBestIdx *p,    /* Best index search context */
  Index *pIdx,        /* The index we are testing */
  int base,           /* Cursor number for the table to be sorted */
  int nEqCol,         /* Number of index columns with ordered == constraints */
  int wsFlags,        /* Index usages flags */
  int bOuterRev,      /* True if outer loops scan in reverse order */
  int *pbRev          /* Set to 1 for reverse-order scan of pIdx */
){
  int i;                        /* Number of pIdx terms used */
  int j;                        /* Number of ORDER BY terms satisfied */
  int sortOrder = 0;            /* XOR of index and ORDER BY sort direction */
  int nTerm;                    /* Number of ORDER BY terms */
  struct ExprList_item *pTerm;  /* A term of the ORDER BY clause */
  ExprList *pOrderBy;           /* The ORDER BY clause */
  Parse *pParse = p->pParse;    /* Parser context */
  sqlite3 *db = pParse->db;     /* Database connection */
  int nPriorSat;                /* ORDER BY terms satisfied by outer loops */
  int seenRowid = 0;            /* True if an ORDER BY rowid term is seen */
  int nEqOneRow;                /* Idx columns that ref unique values */

  if( p->i==0 ){
    nPriorSat = 0;
    nEqOneRow = nEqCol;
  }else{
    if( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return 0;
    nPriorSat = p->aLevel[p->i-1].plan.nOBSat;
    sortOrder = bOuterRev;
    nEqOneRow = 0;
  }
  if( p->i>0 && nEqCol==0 /*&& !allOuterLoopsUnique(p)*/ ) return nPriorSat;
  pOrderBy = p->pOrderBy;
  if( !pOrderBy ) return nPriorSat;
  if( wsFlags & WHERE_COLUMN_IN ) return nPriorSat;
  if( pIdx->bUnordered ) return nPriorSat;
  nTerm = pOrderBy->nExpr;
  assert( nTerm>0 );

  /* Argument pIdx must either point to a 'real' named index structure, 
  ** or an index structure allocated on the stack by bestBtreeIndex() to
  ** represent the rowid index that is part of every table.  */
  assert( pIdx->zName || (pIdx->nColumn==1 && pIdx->aiColumn[0]==-1) );

  /* Match terms of the ORDER BY clause against columns of
  ** the index.
  **
  ** Note that indices have pIdx->nColumn regular columns plus
  ** one additional column containing the rowid.  The rowid column
  ** of the index is also allowed to match against the ORDER BY
  ** clause.
  */
  for(i=0,j=nPriorSat,pTerm=&pOrderBy->a[j]; j<nTerm && i<=pIdx->nColumn; i++){
    Expr *pExpr;       /* The expression of the ORDER BY pTerm */
    CollSeq *pColl;    /* The collating sequence of pExpr */
    int termSortOrder; /* Sort order for this term */
    int iColumn;       /* The i-th column of the index.  -1 for rowid */
    int iSortOrder;    /* 1 for DESC, 0 for ASC on the i-th index term */
    const char *zColl; /* Name of the collating sequence for i-th index term */

    pExpr = pTerm->pExpr;
    if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){
      /* Can not use an index sort on anything that is not a column in the
      ** left-most table of the FROM clause */
      break;
    }
    pColl = sqlite3ExprCollSeq(pParse, pExpr);
    if( !pColl ){
      pColl = db->pDfltColl;
    }
    if( pIdx->zName && i<pIdx->nColumn ){
      iColumn = pIdx->aiColumn[i];
      if( iColumn==pIdx->pTable->iPKey ){
        iColumn = -1;
      }
      iSortOrder = pIdx->aSortOrder[i];
      zColl = pIdx->azColl[i];
    }else{
      iColumn = -1;
      iSortOrder = 0;
      zColl = pColl->zName;
    }
    if( pExpr->iColumn!=iColumn || sqlite3StrICmp(pColl->zName, zColl) ){
      /* Term j of the ORDER BY clause does not match column i of the index */
      if( i<nEqCol ){
        /* If an index column that is constrained by == fails to match an
        ** ORDER BY term, that is OK.  Just ignore that column of the index
        */
        continue;
      }else if( i==pIdx->nColumn ){
        /* Index column i is the rowid.  All other terms match. */
        break;
      }else{
        /* If an index column fails to match and is not constrained by ==
        ** then the index cannot satisfy the ORDER BY constraint.
        */
        return nPriorSat;
      }
    }
    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++;
    if( iColumn<0 ){
      seenRowid = 1;
      break;
    }
  }
  *pbRev = sortOrder;

  /* If there was an "ORDER BY rowid" term that matched, or it is only
  ** possible for a single row from this table to match, then skip over
  ** any additional ORDER BY terms dealing with this table.
  */
  if( seenRowid ||
     (   (wsFlags & WHERE_COLUMN_NULL)==0
      && i>=pIdx->nColumn
      && indexIsUniqueNotNull(pIdx, nEqCol)
     )
  ){
    /* Advance j over additional ORDER BY terms associated with base */
    WhereMaskSet *pMS = p->pWC->pMaskSet;
    Bitmask m = ~getMask(pMS, base);
    while( j<nTerm && (exprTableUsage(pMS, pOrderBy->a[j].pExpr)&m)==0 ){
      j++;
    }
  }
  return j;
}

/*
** Prepare a crude estimate of the logarithm of the input value.
** The results need not be exact.  This is only used for estimating
** the total cost of performing operations with O(logN) or O(NlogN)
** complexity.  Because N is just a guess, it is no great tragedy if
** logN is a little off.
*/
................................................................................
static int isOrderedColumn(WhereBestIdx *p, int iTab, int iCol, int *pbRev){
  int i, j;
  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++){
................................................................................
** by outer loops.  Return 1 if pTerm is ordered, and 0 if not.
*/
static int isOrderedTerm(WhereBestIdx *p, WhereTerm *pTerm, int *pbRev){
  Expr *pExpr = pTerm->pExpr;
  assert( pExpr->op==TK_EQ );
  assert( pExpr->pLeft!=0 && pExpr->pLeft->op==TK_COLUMN );
  assert( pExpr->pRight!=0 );
  if( p->i==0 ){
    return 1;  /* All == are ordered in the outer loop */
  }
  if( pTerm->prereqRight==0 ){
    return 1;  /* RHS of the == is a constant */
  }
  if( pExpr->pRight->op==TK_COLUMN 
   && isOrderedColumn(p, pExpr->pRight->iTable, pExpr->pRight->iColumn, pbRev)
  ){
    return 1;
  }

  /* If we cannot prove that the constraint is ordered, assume it is not */
  return 0;
}




































































































































































/*
** Find the best query plan for accessing a particular table.  Write the
** best query plan and its cost into the p->cost.
**
** The lowest cost plan wins.  The cost is an estimate of the amount of
** CPU and disk I/O needed to process the requested result.
................................................................................
    ** optimized using the index. 
    */
    if( nEq==pProbe->nColumn && pProbe->onError!=OE_None ){
      testcase( wsFlags & WHERE_COLUMN_IN );
      testcase( wsFlags & WHERE_COLUMN_NULL );
      if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
        wsFlags |= WHERE_UNIQUE;



      }
    }else if( pProbe->bUnordered==0 ){
      int j = (nEq==pProbe->nColumn ? -1 : pProbe->aiColumn[nEq]);
      if( findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
        WhereTerm *pTop, *pBtm;
        pTop = findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE, pIdx);
        pBtm = findTerm(pWC, iCur, j, p->notReady, WO_GT|WO_GE, pIdx);







|
|
|
|
>







 







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







>
>
>







 







<
<
<













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







 







>
>
>







253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
....
1603
1604
1605
1606
1607
1608
1609
































































































































































1610
1611
1612
1613
1614
1615
1616
....
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
....
2766
2767
2768
2769
2770
2771
2772



2773
2774
2775
2776
2777
2778
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
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
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
....
3176
3177
3178
3179
3180
3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
#define WHERE_COLUMN_NULL  0x00080000  /* x IS NULL */
#define WHERE_INDEXED      0x000f0000  /* Anything that uses an index */
#define WHERE_NOT_FULLSCAN 0x100f3000  /* Does not do a full table scan */
#define WHERE_IN_ABLE      0x000f1000  /* Able to support an IN operator */
#define WHERE_TOP_LIMIT    0x00100000  /* x<EXPR or x<=EXPR constraint */
#define WHERE_BTM_LIMIT    0x00200000  /* x>EXPR or x>=EXPR constraint */
#define WHERE_BOTH_LIMIT   0x00300000  /* Both x>EXPR and x<EXPR */
#define WHERE_IDX_ONLY     0x00400000  /* Use index only - omit table */
#define WHERE_ORDERBY      0x00800000  /* Output will appear in correct order */
#define WHERE_REVERSE      0x01000000  /* Scan in reverse order */
#define WHERE_UNIQUE       0x02000000  /* Selects no more than one row */
#define WHERE_ALL_UNIQUE   0x04000000  /* This and all prior have one row */
#define WHERE_VIRTUALTABLE 0x08000000  /* Use virtual-table processing */
#define WHERE_MULTI_OR     0x10000000  /* OR using multiple indices */
#define WHERE_TEMP_INDEX   0x20000000  /* Uses an ephemeral index */
#define WHERE_DISTINCT     0x40000000  /* Correct order for DISTINCT */
#define WHERE_COVER_SCAN   0x80000000  /* Full scan of a covering index */

/*
................................................................................
      return 1;
    }
  }

  return 0;
}

































































































































































/*
** Prepare a crude estimate of the logarithm of the input value.
** The results need not be exact.  This is only used for estimating
** the total cost of performing operations with O(logN) or O(NlogN)
** complexity.  Because N is just a guess, it is no great tragedy if
** logN is a little off.
*/
................................................................................
static int isOrderedColumn(WhereBestIdx *p, int iTab, int iCol, int *pbRev){
  int i, j;
  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_ALL_UNIQUE)!=0 ){
      return 1;
    }
    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++){
................................................................................
** by outer loops.  Return 1 if pTerm is ordered, and 0 if not.
*/
static int isOrderedTerm(WhereBestIdx *p, WhereTerm *pTerm, int *pbRev){
  Expr *pExpr = pTerm->pExpr;
  assert( pExpr->op==TK_EQ );
  assert( pExpr->pLeft!=0 && pExpr->pLeft->op==TK_COLUMN );
  assert( pExpr->pRight!=0 );



  if( pTerm->prereqRight==0 ){
    return 1;  /* RHS of the == is a constant */
  }
  if( pExpr->pRight->op==TK_COLUMN 
   && isOrderedColumn(p, pExpr->pRight->iTable, pExpr->pRight->iColumn, pbRev)
  ){
    return 1;
  }

  /* If we cannot prove that the constraint is ordered, assume it is not */
  return 0;
}

/*
** This routine decides if pIdx can be used to satisfy the ORDER BY
** clause, either in whole or in part.  The return value is the 
** cumulative number of terms in the ORDER BY clause that are satisfied
** by the index pIdx and other indices in outer loops.
**
** The table being queried has a cursor number of "base".  pIdx is the
** index that is postulated for use to access the table.
**
** nEqCol is the number of columns of pIdx that are used as equality
** constraints and where the other side of the == is an ordered column
** or constant.  An "order column" in the previous sentence means a column
** in table from an outer loop whose values will always appear in the 
** correct order due to othre index, or because the outer loop generates
** a unique result.  Any of the first nEqCol columns of pIdx may be missing
** from the ORDER BY clause and the match can still be a success.
**
** The *pbRev value is set to 0 order 1 depending on whether or not
** pIdx should be run in the forward order or in reverse order.
*/
static int isSortingIndex(
  WhereBestIdx *p,    /* Best index search context */
  Index *pIdx,        /* The index we are testing */
  int base,           /* Cursor number for the table to be sorted */
  int nEqCol,         /* Number of index columns with ordered == constraints */
  int wsFlags,        /* Index usages flags */
  int bOuterRev,      /* True if outer loops scan in reverse order */
  int *pbRev          /* Set to 1 for reverse-order scan of pIdx */
){
  int i;                        /* Number of pIdx terms used */
  int j;                        /* Number of ORDER BY terms satisfied */
  int sortOrder = 0;            /* XOR of index and ORDER BY sort direction */
  int nTerm;                    /* Number of ORDER BY terms */
  struct ExprList_item *pTerm;  /* A term of the ORDER BY clause */
  ExprList *pOrderBy;           /* The ORDER BY clause */
  Parse *pParse = p->pParse;    /* Parser context */
  sqlite3 *db = pParse->db;     /* Database connection */
  int nPriorSat;                /* ORDER BY terms satisfied by outer loops */
  int seenRowid = 0;            /* True if an ORDER BY rowid term is seen */
  int nEqOneRow;                /* Idx columns that ref unique values */

  if( p->i==0 ){
    nPriorSat = 0;
  }else{
    nPriorSat = p->aLevel[p->i-1].plan.nOBSat;
    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 );

  /* Argument pIdx must either point to a 'real' named index structure, 
  ** or an index structure allocated on the stack by bestBtreeIndex() to
  ** represent the rowid index that is part of every table.  */
  assert( pIdx->zName || (pIdx->nColumn==1 && pIdx->aiColumn[0]==-1) );

  /* Match terms of the ORDER BY clause against columns of
  ** the index.
  **
  ** Note that indices have pIdx->nColumn regular columns plus
  ** one additional column containing the rowid.  The rowid column
  ** of the index is also allowed to match against the ORDER BY
  ** clause.
  */
  for(i=0,j=nPriorSat,pTerm=&pOrderBy->a[j]; j<nTerm && i<=pIdx->nColumn; i++){
    Expr *pExpr;       /* The expression of the ORDER BY pTerm */
    CollSeq *pColl;    /* The collating sequence of pExpr */
    int termSortOrder; /* Sort order for this term */
    int iColumn;       /* The i-th column of the index.  -1 for rowid */
    int iSortOrder;    /* 1 for DESC, 0 for ASC on the i-th index term */
    const char *zColl; /* Name of the collating sequence for i-th index term */

    pExpr = pTerm->pExpr;
    if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){
      /* Can not use an index sort on anything that is not a column in the
      ** left-most table of the FROM clause */
      break;
    }
    pColl = sqlite3ExprCollSeq(pParse, pExpr);
    if( !pColl ){
      pColl = db->pDfltColl;
    }
    if( pIdx->zName && i<pIdx->nColumn ){
      iColumn = pIdx->aiColumn[i];
      if( iColumn==pIdx->pTable->iPKey ){
        iColumn = -1;
      }
      iSortOrder = pIdx->aSortOrder[i];
      zColl = pIdx->azColl[i];
    }else{
      iColumn = -1;
      iSortOrder = 0;
      zColl = pColl->zName;
    }
    if( pExpr->iColumn!=iColumn || sqlite3StrICmp(pColl->zName, zColl) ){
      /* Term j of the ORDER BY clause does not match column i of the index */
      if( i<nEqCol ){
        /* If an index column that is constrained by == fails to match an
        ** ORDER BY term, that is OK.  Just ignore that column of the index
        */
        continue;
      }else if( i==pIdx->nColumn ){
        /* Index column i is the rowid.  All other terms match. */
        break;
      }else{
        /* If an index column fails to match and is not constrained by ==
        ** then the index cannot satisfy the ORDER BY constraint.
        */
        return nPriorSat;
      }
    }
    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++;
    if( iColumn<0 ){
      seenRowid = 1;
      break;
    }
  }
  *pbRev = sortOrder;

  /* If there was an "ORDER BY rowid" term that matched, or it is only
  ** possible for a single row from this table to match, then skip over
  ** any additional ORDER BY terms dealing with this table.
  */
  if( seenRowid ||
     (   (wsFlags & WHERE_COLUMN_NULL)==0
      && i>=pIdx->nColumn
      && indexIsUniqueNotNull(pIdx, nEqCol)
     )
  ){
    /* Advance j over additional ORDER BY terms associated with base */
    WhereMaskSet *pMS = p->pWC->pMaskSet;
    Bitmask m = ~getMask(pMS, base);
    while( j<nTerm && (exprTableUsage(pMS, pOrderBy->a[j].pExpr)&m)==0 ){
      j++;
    }
  }
  return j;
}

/*
** Find the best query plan for accessing a particular table.  Write the
** best query plan and its cost into the p->cost.
**
** The lowest cost plan wins.  The cost is an estimate of the amount of
** CPU and disk I/O needed to process the requested result.
................................................................................
    ** optimized using the index. 
    */
    if( nEq==pProbe->nColumn && pProbe->onError!=OE_None ){
      testcase( wsFlags & WHERE_COLUMN_IN );
      testcase( wsFlags & WHERE_COLUMN_NULL );
      if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
        wsFlags |= WHERE_UNIQUE;
        if( p->i==0 || (p->aLevel[p->i-1].plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
          wsFlags |= WHERE_ALL_UNIQUE;
        }
      }
    }else if( pProbe->bUnordered==0 ){
      int j = (nEq==pProbe->nColumn ? -1 : pProbe->aiColumn[nEq]);
      if( findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
        WhereTerm *pTop, *pBtm;
        pTop = findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE, pIdx);
        pBtm = findTerm(pWC, iCur, j, p->notReady, WO_GT|WO_GE, pIdx);

Added test/orderby2.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
# 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 orderby2

# Generate test data for a join.  Verify that the join gets the
# correct answer.
#
do_test 1.0 {
  db eval {
    CREATE TABLE t1(a INTEGER PRIMARY KEY, b);
    INSERT INTO t1 VALUES(1,11), (2,22);
    CREATE TABLE t2(d, e, UNIQUE(d,e));
    INSERT INTO t2 VALUES(10, 'ten'), (11,'eleven'), (12,'twelve'),
                         (11, 'oneteen');
  }
} {}

do_test 1.1a {
  db eval {
    SELECT e FROM t1, t2 WHERE a=1 AND d=b ORDER BY d, e;
  }
} {eleven oneteen}
do_test 1.1b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT e FROM t1, t2 WHERE a=1 AND d=b ORDER BY d, e;
  }
} {~/ORDER BY/}

do_test 1.2a {
  db eval {
    SELECT e FROM t1, t2 WHERE a=1 AND d=b ORDER BY e;
  }
} {eleven oneteen}
do_test 1.2b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT e FROM t1, t2 WHERE a=1 AND d=b ORDER BY e;
  }
} {~/ORDER BY/}

do_test 1.3a {
  db eval {
    SELECT e, b FROM t1, t2 WHERE a=1 ORDER BY d, e;
  }
} {ten 11 eleven 11 oneteen 11 twelve 11}
do_test 1.3b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT e, b FROM t1, t2 WHERE a=1 ORDER BY d, e;
  }
} {~/ORDER BY/}


finish_test