/ Check-in [c027a9af]
Login

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

Overview
Comment:Merge ORDER BY optimization refactoring and repair into trunk.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:c027a9af9137f3346dbb5c5e100a087c2e89797b
User & Date: drh 2012-10-08 21:51:58
Context
2012-10-08
23:25
Changes to facilitate full test coverage. check-in: 28d1eb40 user: drh tags: trunk
21:51
Merge ORDER BY optimization refactoring and repair into trunk. check-in: c027a9af user: drh tags: trunk
21:01
All test cases (veryquick.tcl and min.rc) pass. A few branch operations in ORDER BY optimization logic are untested by min.rc. Closed-Leaf check-in: 8314fd60 user: drh tags: qp-enhancements
14:36
Manually define the Win32 file-mapping APIs for WAL if SQLITE_WIN32_FILEMAPPING_API is defined. check-in: 1c2c0a28 user: mistachkin tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
....
2722
2723
2724
2725
2726
2727
2728
2729
2730

2731
2732
2733
2734


2735
2736




2737
2738
2739
2740
2741
2742
2743
....
2765
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
....
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
....
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
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
....
3061
3062
3063
3064
3065
3066
3067





3068
3069
3070
3071
3072
3073
3074
....
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
....
3132
3133
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
....
3160
3161
3162
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
....
3179
3180
3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
....
3238
3239
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249

3250
3251
3252
3253
3254
3255
3256
3257
....
3361
3362
3363
3364
3365
3366
3367

3368


3369
3370
3371
3372
3373
3374
3375
....
3466
3467
3468
3469
3470
3471
3472
3473
3474
3475
3476
3477
3478
3479
3480
3481
3482
3483
3484
3485
3486
....
3510
3511
3512
3513
3514
3515
3516
3517
3518
3519
3520
3521
3522
3523
3524
....
5060
5061
5062
5063
5064
5065
5066
5067
5068
5069
5070
5071
5072
5073
5074
....
5113
5114
5115
5116
5117
5118
5119
5120
5121
5122
5123
5124
5125
5126
5127
5128

  /* Prevent ON clause terms of a LEFT JOIN from being used to drive
  ** an index for tables to the left of the join.
  */
  pTerm->prereqRight |= extraRight;
}

/*
** Return TRUE if the given index is UNIQUE and all columns past the
** first nSkip columns are NOT NULL.
*/
static int indexIsUniqueNotNull(Index *pIdx, int nSkip){
  Table *pTab = pIdx->pTable;
  int i;
  if( pIdx->onError==OE_None ) return 0;
  for(i=nSkip; i<pIdx->nColumn; i++){
    int j = pIdx->aiColumn[i];
    assert( j>=0 && j<pTab->nCol );
    if( pTab->aCol[j].notNull==0 ) return 0;
  }
  return 1;
}

/*
** This function searches the expression list passed as the second argument
** for an expression of type TK_COLUMN that refers to the same column and
** uses the same collation sequence as the iCol'th column of index pIdx.
** Argument iBase is the cursor number used for the table that pIdx refers
** to.
**
................................................................................
  }
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT3) */

/*
** Check to see if column iCol of the table with cursor iTab will appear
** in sorted order according to the current query plan.  Return true if
** it will and false if not.  

**
** If *pbRev is initially 2 (meaning "unknown") then set *pbRev to the
** sort order of iTab.iCol.  If *pbRev is 0 or 1 but does not match
** the sort order of iTab.iCol, then consider the column to be unordered.


*/
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 ){
................................................................................
      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;
}

/*
** pTerm is an == constraint.  Check to see if the other side of
** the == is a constant or a value that is guaranteed to be ordered
** 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
................................................................................
** 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( nEqCol==0 ){
    if( p->i && (p->aLevel[p->i-1].plan.wsFlags & WHERE_ORDERED)==0 ){



      return nPriorSat;
    }
    nEqOneRow = 0;
  }else if( p->i==0 || (p->aLevel[p->i-1].plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
    nEqOneRow = nEqCol;
  }else{
    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 );

  /* 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) );

................................................................................
  ** 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++){
    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 */

    assert( i<=pIdx->nColumn );
    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 have the correct 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++;
    }
  }
................................................................................
  /* Loop over all indices looking for the best one to use
  */
  for(; pProbe; pIdx=pProbe=pProbe->pNext){
    const tRowcnt * const aiRowEst = pProbe->aiRowEst;
    WhereCost pc;               /* Cost of using pProbe */
    double log10N = (double)1;  /* base-10 logarithm of nRow (inexact) */
    int bRev = 2;               /* 0=forward scan.  1=reverse.  2=undecided */






    /* The following variables are populated based on the properties of
    ** index being evaluated. They are then used to determine the expected
    ** cost and number of rows returned.
    **
    **  pc.plan.nEq: 
    **    Number of equality terms that can be implemented using the index.
................................................................................
    **
    **    nInMul is set to 1.
    **
    **    If there exists a WHERE term of the form "x IN (SELECT ...)", then 
    **    the sub-select is assumed to return 25 rows for the purposes of 
    **    determining nInMul.
    **
    **  nOrdered:
    **    The number of equality terms that are constrainted by outer loop
    **    variables that are well-ordered.
    **
    **  bInEst:  
    **    Set to true if there was at least one "x IN (SELECT ...)" term used 
    **    in determining the value of nInMul.  Note that the RHS of the
    **    IN operator must be a SELECT, not a value list, for this variable
    **    to be true.
    **
    **  rangeDiv:
................................................................................
    **    two queries requires table b-tree lookups in order to find the value
    **    of column c, but the first does not because columns a and b are
    **    both available in the index.
    **
    **             SELECT a, b    FROM tbl WHERE a = 1;
    **             SELECT a, b, c FROM tbl WHERE a = 1;
    */
    int nOrdered;                 /* Number of ordered terms matching index */
    int bInEst = 0;               /* True if "x IN (SELECT...)" seen */
    int nInMul = 1;               /* Number of distinct equalities to lookup */
    double rangeDiv = (double)1;  /* Estimated reduction in search space */
    int nBound = 0;               /* Number of range constraints seen */
    int bSort;                    /* True if external sort required */
    int bDist;                    /* True if index cannot help with DISTINCT */
    int bLookup = 0;              /* True if not a covering index */
................................................................................
    }else{
      nPriorSat = pc.plan.nOBSat = 0;
      bSort = nOrderBy>0;
      bDist = p->pDistinct!=0;
    }

    /* Determine the values of pc.plan.nEq and nInMul */
    for(pc.plan.nEq=nOrdered=0; pc.plan.nEq<pProbe->nColumn; pc.plan.nEq++){
      int j = pProbe->aiColumn[pc.plan.nEq];
      pTerm = findTerm(pWC, iCur, j, p->notReady, eqTermMask, pIdx);
      if( pTerm==0 ) break;
      pc.plan.wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
      testcase( pTerm->pWC!=pWC );
      if( pTerm->eOperator & WO_IN ){
        Expr *pExpr = pTerm->pExpr;
................................................................................
          bInEst = 1;
        }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
          /* "x IN (value, value, ...)" */
          nInMul *= pExpr->x.pList->nExpr;
        }
      }else if( pTerm->eOperator & WO_ISNULL ){
        pc.plan.wsFlags |= WHERE_COLUMN_NULL;
        if( pc.plan.nEq==nOrdered ) nOrdered++;
      }else if( bSort && pc.plan.nEq==nOrdered
             && isOrderedTerm(p,pTerm,&bRev) ){
        nOrdered++;
      }
#ifdef SQLITE_ENABLE_STAT3
      if( pc.plan.nEq==0 && pProbe->aSample ) pFirstTerm = pTerm;
#endif
      pc.used |= pTerm->prereqRight;
    }
 
................................................................................

    /* If there is an ORDER BY clause and the index being considered will
    ** naturally scan rows in the required order, set the appropriate flags
    ** in pc.plan.wsFlags. Otherwise, if there is an ORDER BY clause but
    ** the index will scan rows in a different order, set the bSort
    ** variable.  */
    assert( bRev>=0 && bRev<=2 );
    if( bSort ){
      testcase( bRev==0 );
      testcase( bRev==1 );
      testcase( bRev==2 );
      pc.plan.nOBSat = isSortingIndex(p, pProbe, iCur, nOrdered,

                                 pc.plan.wsFlags, bRev&1, &bRev);
      if( nPriorSat<pc.plan.nOBSat || (pc.plan.wsFlags & WHERE_UNIQUE)!=0 ){
        pc.plan.wsFlags |= WHERE_ORDERED;
      }
      if( nOrderBy==pc.plan.nOBSat ){
        bSort = 0;
        pc.plan.wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE;
      }
................................................................................
      ** the cost function to err on the side of choosing an index over
      ** choosing a full scan.  This 4x full-scan penalty is an arguable
      ** decision and one which we expect to revisit in the future.  But
      ** it seems to be working well enough at the moment.
      */
      pc.rCost = aiRowEst[0]*4;
      pc.plan.wsFlags &= ~WHERE_IDX_ONLY;

      if( pIdx ) pc.plan.wsFlags &= ~WHERE_ORDERED;


    }else{
      log10N = estLog(aiRowEst[0]);
      pc.rCost = pc.plan.nRow;
      if( pIdx ){
        if( bLookup ){
          /* For an index lookup followed by a table lookup:
          **    nInMul index searches to find the start of each index range
................................................................................
        }
      }
      if( pc.plan.nRow<2 ) pc.plan.nRow = 2;
    }


    WHERETRACE((
      "%s(%s):\n"
      "    nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%08x\n"
      "    notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f\n"
      "    used=0x%llx nOrdered=%d nOBSat=%d\n",
      pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"), 
      pc.plan.nEq, nInMul, (int)rangeDiv, bSort, bLookup, pc.plan.wsFlags,
      p->notReady, log10N, pc.plan.nRow, pc.rCost, pc.used, nOrdered,
      pc.plan.nOBSat
    ));

    /* If this index is the best we have seen so far, then record this
    ** index and its cost in the p->cost structure.
    */
    if( (!pIdx || pc.plan.wsFlags) && compareCost(&pc, &p->cost) ){
................................................................................
  assert( p->pOrderBy || (p->cost.plan.wsFlags&WHERE_ORDERED)==0 );
  assert( p->cost.plan.u.pIdx==0 || (p->cost.plan.wsFlags&WHERE_ROWID_EQ)==0 );
  assert( pSrc->pIndex==0 
       || p->cost.plan.u.pIdx==0 
       || p->cost.plan.u.pIdx==pSrc->pIndex 
  );

  WHERETRACE(("best index is: %s\n",
         p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk"));
  
  bestOrClauseIndex(p);
  bestAutomaticIndex(p);
  p->cost.plan.wsFlags |= eqTermMask;
}

................................................................................
        if( (m & sWBI.notValid)==0 ){
          if( j==iFrom ) iFrom++;
          continue;
        }
        sWBI.notReady = (isOptimal ? m : sWBI.notValid);
        if( sWBI.pSrc->pIndex==0 ) nUnconstrained++;
  
        WHERETRACE(("=== trying table %d (%s) with isOptimal=%d ===\n",
                    j, sWBI.pSrc->pTab->zName, isOptimal));
        assert( sWBI.pSrc->pTab );
#ifndef SQLITE_OMIT_VIRTUALTABLE
        if( IsVirtual(sWBI.pSrc->pTab) ){
          sWBI.ppIdxInfo = &pWInfo->a[j].pIdxInfo;
          bestVirtualIndex(&sWBI);
        }else 
................................................................................
            && (bestJ<0 || (notIndexed&m)!=0                     /* (2) */
                || (bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
                || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
            && (nUnconstrained==0 || sWBI.pSrc->pIndex==0        /* (3) */
                || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
            && (bestJ<0 || compareCost(&sWBI.cost, &bestPlan))   /* (4) */
        ){
          WHERETRACE(("=== table %d (%s) is best so far\n"
                      "    cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=%08x\n",
                      j, sWBI.pSrc->pTab->zName,
                      sWBI.cost.rCost, sWBI.cost.plan.nRow,
                      sWBI.cost.plan.nOBSat, sWBI.cost.plan.wsFlags));
          bestPlan = sWBI.cost;
          bestJ = j;
        }
        if( doNotReorder ) break;







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







 







|
|
>

<
|
|
>
>

|
>
>
>
>







 







<
|
<
<
<




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







 







<
<
<




|

|
>





|





>
>
>
|
|
<
<
>
>
>


<
<
<
<
<
<



|
>
>
|
>

>







 







|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
>
>
>







>



|

>
>
>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
|
<
<
<
<
<
<
<
>
>
>
>
>
>
>
>
>
|
>
>
>
>
>
|
<
<
<
<
>
>
>
>
>
>
>
>
|
>
>
|
<
>
|

<
<
<
<
<
>
>

>
>

|
>
|
>
>
|
>

|



>
>


>
>
>
>
>
>
|





<
<
|
<
<
<







 







>
>
>
>
>







 







<
<
<
<







 







<







 







|







 







<
<
<
<







 







|
|
|
<
|
>
|







 







>
|
>
>







 







<
|
|
|
<

|







 







|







 







|







 







|
|







1438
1439
1440
1441
1442
1443
1444
















1445
1446
1447
1448
1449
1450
1451
....
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716

2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
....
2755
2756
2757
2758
2759
2760
2761

2762



2763
2764
2765
2766























2767
2768
2769
2770
2771
2772
2773
....
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
....
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
2955
2956
2957
2958
2959
2960
2961
2962
2963


2964



2965
2966
2967
2968
2969
2970
2971
....
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
3074
3075
3076
3077
3078
3079
3080
3081
3082
....
3099
3100
3101
3102
3103
3104
3105




3106
3107
3108
3109
3110
3111
3112
....
3136
3137
3138
3139
3140
3141
3142

3143
3144
3145
3146
3147
3148
3149
....
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
....
3182
3183
3184
3185
3186
3187
3188




3189
3190
3191
3192
3193
3194
3195
....
3237
3238
3239
3240
3241
3242
3243
3244
3245
3246

3247
3248
3249
3250
3251
3252
3253
3254
3255
3256
....
3360
3361
3362
3363
3364
3365
3366
3367
3368
3369
3370
3371
3372
3373
3374
3375
3376
3377
....
3468
3469
3470
3471
3472
3473
3474

3475
3476
3477

3478
3479
3480
3481
3482
3483
3484
3485
3486
....
3510
3511
3512
3513
3514
3515
3516
3517
3518
3519
3520
3521
3522
3523
3524
....
5060
5061
5062
5063
5064
5065
5066
5067
5068
5069
5070
5071
5072
5073
5074
....
5113
5114
5115
5116
5117
5118
5119
5120
5121
5122
5123
5124
5125
5126
5127
5128

  /* Prevent ON clause terms of a LEFT JOIN from being used to drive
  ** an index for tables to the left of the join.
  */
  pTerm->prereqRight |= extraRight;
}

















/*
** This function searches the expression list passed as the second argument
** for an expression of type TK_COLUMN that refers to the same column and
** uses the same collation sequence as the iCol'th column of index pIdx.
** Argument iBase is the cursor number used for the table that pIdx refers
** to.
**
................................................................................
  }
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT3) */

/*
** Check to see if column iCol of the table with cursor iTab will appear
** in sorted order according to the current query plan.
**
** Return values:
**

**    0   iCol is not ordered
**    1   iCol has only a single value
**    2   iCol is in ASC order
**    3   iCol is in DESC order
*/
static int isOrderedColumn(
  WhereBestIdx *p,
  int iTab,
  int iCol
){
  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 ){
................................................................................
      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;
    }

    return sortOrder+2;



  }
  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
................................................................................
** 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 *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 = 2;            /* 0: forward.  1: backward.  2: unknown */
  int nTerm;                    /* Number of ORDER BY terms */
  struct ExprList_item *pOBItem;/* A term of the ORDER BY clause */
  Table *pTab = pIdx->pTable;   /* Table that owns index pIdx */
  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 uniqueNotNull;            /* pIdx is UNIQUE with all terms are NOT NULL */

  if( p->i==0 ){
    nPriorSat = 0;
  }else{
    nPriorSat = p->aLevel[p->i-1].plan.nOBSat;
    if( (p->aLevel[p->i-1].plan.wsFlags & WHERE_ORDERED)==0 ){
      /* This loop cannot be ordered unless the next outer loop is
      ** also ordered */
      return nPriorSat;
    }


    if( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ){
      /* Only look at the outer-most loop if the OrderByIdxJoin
      ** optimization is disabled */
      return nPriorSat;
    }






  }
  pOrderBy = p->pOrderBy;
  assert( pOrderBy!=0 );
  if( pIdx->bUnordered ){
    /* Hash indices (indicated by the "unordered" tag on sqlite_stat1) cannot
    ** be used for sorting */
    return nPriorSat;
  }
  nTerm = pOrderBy->nExpr;
  uniqueNotNull = pIdx->onError!=OE_None;
  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) );

................................................................................
  ** 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.
  */
  j = nPriorSat;
  for(i=0,pOBItem=&pOrderBy->a[j]; j<nTerm && i<=pIdx->nColumn; i++){
    Expr *pOBExpr;          /* The expression of the ORDER BY pOBItem */
    CollSeq *pColl;         /* The collating sequence of pOBExpr */
    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 */
    int isEq;               /* Subject to an == or IS NULL constraint */
    int isMatch;            /* ORDER BY term matches the index term */
    const char *zColl;      /* Name of collating sequence for i-th index term */
    WhereTerm *pConstraint; /* A constraint in the WHERE clause */

    /* If the next term of the ORDER BY clause refers to anything other than
    ** a column in the "base" table, then this index will not be of any
    ** further use in handling the ORDER BY. */
    pOBExpr = pOBItem->pExpr;
    if( pOBExpr->op!=TK_COLUMN || pOBExpr->iTable!=base ){
      break;
    }

    /* Find column number and collating sequence for the next entry
    ** in the index */
    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];
      assert( zColl!=0 );
    }else{
      iColumn = -1;
      iSortOrder = 0;
      zColl = 0;
    }

    /* Check to see if the column number and collating sequence of the
    ** index match the column number and collating sequence of the ORDER BY
    ** clause entry.  Set isMatch to 1 if they both match. */
    if( pOBExpr->iColumn==iColumn ){
      if( zColl ){
        pColl = sqlite3ExprCollSeq(pParse, pOBExpr);
        if( !pColl ) pColl = db->pDfltColl;
        isMatch = sqlite3StrICmp(pColl->zName, zColl)==0;
      }else{
        isMatch = 1;
      }
    }else{
      isMatch = 0;
    }

    /* termSortOrder is 0 or 1 for whether or not the access loop should
    ** run forward or backwards (respectively) in order to satisfy this 
    ** term of the ORDER BY clause. */







    termSortOrder = iSortOrder ^ pOBItem->sortOrder;

    /* If X is the column in the index and ORDER BY clause, check to see
    ** if there are any X= or X IS NULL constraints in the WHERE clause. */
    pConstraint = findTerm(p->pWC, base, iColumn, p->notReady,
                           WO_EQ|WO_ISNULL|WO_IN, pIdx);
    if( pConstraint==0 ){
      isEq = 0;
    }else if( pConstraint->eOperator==WO_IN ){
      break;
    }else if( pConstraint->eOperator==WO_ISNULL ){
      uniqueNotNull = 0;
      isEq = 1;
    }else if( pConstraint->prereqRight==0 ){
      isEq = 1;
    }else{




      Expr *pRight = pConstraint->pExpr->pRight;
      if( pRight->op==TK_COLUMN ){
        WHERETRACE(("       .. isOrderedColumn(tab=%d,col=%d)",
                    pRight->iTable, pRight->iColumn));
        isEq = isOrderedColumn(p, pRight->iTable, pRight->iColumn);
        WHERETRACE((" -> isEq=%d\n", isEq));
        if( isMatch && isEq>=2 && isEq!=pOBItem->sortOrder+2 ){
          break;
        }
      }else{
        isEq = 0;
      }

    }
    assert( pOBItem->sortOrder==0 || pOBItem->sortOrder==1 );
    assert( iSortOrder==0 || iSortOrder==1 );





    if( !isMatch ){
      if( isEq==0 ){
        break;
      }else{
        continue;
      }
    }else if( isEq!=1 ){
      if( sortOrder==2 ){
        sortOrder = termSortOrder;
      }else if( termSortOrder!=sortOrder ){
        break;
      }
    }
    j++;
    pOBItem++;
    if( iColumn<0 ){
      seenRowid = 1;
      break;
    }else if( pTab->aCol[iColumn].notNull==0 && isEq==0 ){
      uniqueNotNull = 0;
    }
  }

  /* If we have not found at least one ORDER BY term that matches the
  ** index, then show no progress. */
  if( pOBItem==&pOrderBy->a[nPriorSat] ) return nPriorSat;

  /* Return the necessary scan order back to the caller */
  *pbRev = sortOrder & 1;

  /* 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 || (uniqueNotNull && i>=pIdx->nColumn) ){



    /* 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++;
    }
  }
................................................................................
  /* Loop over all indices looking for the best one to use
  */
  for(; pProbe; pIdx=pProbe=pProbe->pNext){
    const tRowcnt * const aiRowEst = pProbe->aiRowEst;
    WhereCost pc;               /* Cost of using pProbe */
    double log10N = (double)1;  /* base-10 logarithm of nRow (inexact) */
    int bRev = 2;               /* 0=forward scan.  1=reverse.  2=undecided */

    WHERETRACE((
      "   %s(%s):\n",
      pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk")
    ));

    /* The following variables are populated based on the properties of
    ** index being evaluated. They are then used to determine the expected
    ** cost and number of rows returned.
    **
    **  pc.plan.nEq: 
    **    Number of equality terms that can be implemented using the index.
................................................................................
    **
    **    nInMul is set to 1.
    **
    **    If there exists a WHERE term of the form "x IN (SELECT ...)", then 
    **    the sub-select is assumed to return 25 rows for the purposes of 
    **    determining nInMul.
    **




    **  bInEst:  
    **    Set to true if there was at least one "x IN (SELECT ...)" term used 
    **    in determining the value of nInMul.  Note that the RHS of the
    **    IN operator must be a SELECT, not a value list, for this variable
    **    to be true.
    **
    **  rangeDiv:
................................................................................
    **    two queries requires table b-tree lookups in order to find the value
    **    of column c, but the first does not because columns a and b are
    **    both available in the index.
    **
    **             SELECT a, b    FROM tbl WHERE a = 1;
    **             SELECT a, b, c FROM tbl WHERE a = 1;
    */

    int bInEst = 0;               /* True if "x IN (SELECT...)" seen */
    int nInMul = 1;               /* Number of distinct equalities to lookup */
    double rangeDiv = (double)1;  /* Estimated reduction in search space */
    int nBound = 0;               /* Number of range constraints seen */
    int bSort;                    /* True if external sort required */
    int bDist;                    /* True if index cannot help with DISTINCT */
    int bLookup = 0;              /* True if not a covering index */
................................................................................
    }else{
      nPriorSat = pc.plan.nOBSat = 0;
      bSort = nOrderBy>0;
      bDist = p->pDistinct!=0;
    }

    /* Determine the values of pc.plan.nEq and nInMul */
    for(pc.plan.nEq=0; pc.plan.nEq<pProbe->nColumn; pc.plan.nEq++){
      int j = pProbe->aiColumn[pc.plan.nEq];
      pTerm = findTerm(pWC, iCur, j, p->notReady, eqTermMask, pIdx);
      if( pTerm==0 ) break;
      pc.plan.wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
      testcase( pTerm->pWC!=pWC );
      if( pTerm->eOperator & WO_IN ){
        Expr *pExpr = pTerm->pExpr;
................................................................................
          bInEst = 1;
        }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
          /* "x IN (value, value, ...)" */
          nInMul *= pExpr->x.pList->nExpr;
        }
      }else if( pTerm->eOperator & WO_ISNULL ){
        pc.plan.wsFlags |= WHERE_COLUMN_NULL;




      }
#ifdef SQLITE_ENABLE_STAT3
      if( pc.plan.nEq==0 && pProbe->aSample ) pFirstTerm = pTerm;
#endif
      pc.used |= pTerm->prereqRight;
    }
 
................................................................................

    /* If there is an ORDER BY clause and the index being considered will
    ** naturally scan rows in the required order, set the appropriate flags
    ** in pc.plan.wsFlags. Otherwise, if there is an ORDER BY clause but
    ** the index will scan rows in a different order, set the bSort
    ** variable.  */
    assert( bRev>=0 && bRev<=2 );
    if( bSort && (pSrc->jointype & JT_LEFT)==0 ){
      int bRev = 2;
      WHERETRACE(("      --> before isSortingIndex: nPriorSat=%d\n",nPriorSat));

      pc.plan.nOBSat = isSortingIndex(p, pProbe, iCur, &bRev);
      WHERETRACE(("      --> after  isSortingIndex: bRev=%d nOBSat=%d\n",
                  bRev, pc.plan.nOBSat));
      if( nPriorSat<pc.plan.nOBSat || (pc.plan.wsFlags & WHERE_UNIQUE)!=0 ){
        pc.plan.wsFlags |= WHERE_ORDERED;
      }
      if( nOrderBy==pc.plan.nOBSat ){
        bSort = 0;
        pc.plan.wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE;
      }
................................................................................
      ** the cost function to err on the side of choosing an index over
      ** choosing a full scan.  This 4x full-scan penalty is an arguable
      ** decision and one which we expect to revisit in the future.  But
      ** it seems to be working well enough at the moment.
      */
      pc.rCost = aiRowEst[0]*4;
      pc.plan.wsFlags &= ~WHERE_IDX_ONLY;
      if( pIdx ){
        pc.plan.wsFlags &= ~WHERE_ORDERED;
        pc.plan.nOBSat = nPriorSat;
      }
    }else{
      log10N = estLog(aiRowEst[0]);
      pc.rCost = pc.plan.nRow;
      if( pIdx ){
        if( bLookup ){
          /* For an index lookup followed by a table lookup:
          **    nInMul index searches to find the start of each index range
................................................................................
        }
      }
      if( pc.plan.nRow<2 ) pc.plan.nRow = 2;
    }


    WHERETRACE((

      "      nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%08x\n"
      "      notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f\n"
      "      used=0x%llx nOBSat=%d\n",

      pc.plan.nEq, nInMul, (int)rangeDiv, bSort, bLookup, pc.plan.wsFlags,
      p->notReady, log10N, pc.plan.nRow, pc.rCost, pc.used,
      pc.plan.nOBSat
    ));

    /* If this index is the best we have seen so far, then record this
    ** index and its cost in the p->cost structure.
    */
    if( (!pIdx || pc.plan.wsFlags) && compareCost(&pc, &p->cost) ){
................................................................................
  assert( p->pOrderBy || (p->cost.plan.wsFlags&WHERE_ORDERED)==0 );
  assert( p->cost.plan.u.pIdx==0 || (p->cost.plan.wsFlags&WHERE_ROWID_EQ)==0 );
  assert( pSrc->pIndex==0 
       || p->cost.plan.u.pIdx==0 
       || p->cost.plan.u.pIdx==pSrc->pIndex 
  );

  WHERETRACE(("   best index is: %s\n",
         p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk"));
  
  bestOrClauseIndex(p);
  bestAutomaticIndex(p);
  p->cost.plan.wsFlags |= eqTermMask;
}

................................................................................
        if( (m & sWBI.notValid)==0 ){
          if( j==iFrom ) iFrom++;
          continue;
        }
        sWBI.notReady = (isOptimal ? m : sWBI.notValid);
        if( sWBI.pSrc->pIndex==0 ) nUnconstrained++;
  
        WHERETRACE(("   === trying table %d (%s) with isOptimal=%d ===\n",
                    j, sWBI.pSrc->pTab->zName, isOptimal));
        assert( sWBI.pSrc->pTab );
#ifndef SQLITE_OMIT_VIRTUALTABLE
        if( IsVirtual(sWBI.pSrc->pTab) ){
          sWBI.ppIdxInfo = &pWInfo->a[j].pIdxInfo;
          bestVirtualIndex(&sWBI);
        }else 
................................................................................
            && (bestJ<0 || (notIndexed&m)!=0                     /* (2) */
                || (bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
                || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
            && (nUnconstrained==0 || sWBI.pSrc->pIndex==0        /* (3) */
                || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
            && (bestJ<0 || compareCost(&sWBI.cost, &bestPlan))   /* (4) */
        ){
          WHERETRACE(("   === table %d (%s) is best so far\n"
                      "       cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=%08x\n",
                      j, sWBI.pSrc->pTab->zName,
                      sWBI.cost.rCost, sWBI.cost.plan.nRow,
                      sWBI.cost.plan.nOBSat, sWBI.cost.plan.wsFlags));
          bestPlan = sWBI.cost;
          bestJ = j;
        }
        if( doNotReorder ) break;

Changes to test/orderby1.test.

110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
...
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
...
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
...
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
...
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
...
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
  }
} {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/}  ;# separate sorting pass due to mixed DESC/ASC


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}
................................................................................
  }
} {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, tn DESC
  }
} {/ORDER BY/}  ;# separate sorting pass due to mixed DESC/ASC

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 {
................................................................................
  }
} {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
do_test 2.4c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {/ORDER BY/}  ;# separate sorting pass due to mixed DESC/ASC


do_test 2.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}
................................................................................
  }
} {one-c one-a two-b two-a three-c three-a}  ;# verify same order after sorting
do_test 2.5c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {/ORDER BY/}  ;# separate sorting pass due to mixed ASC/DESC

do_test 2.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 2.6b {
................................................................................
  }
} {one-a one-c two-a two-b three-a three-c}  ;# verify same order after sorting
do_test 3.4c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {/ORDER BY/}  ;# separate sorting pass due to mismatched DESC/ASC


do_test 3.5a {
  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}
................................................................................
  }
} {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
do_test 3.5c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {/ORDER BY/}  ;# separate sorting pass due to mismatched ASC/DESC


do_test 3.6a {
  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}







|







 







|







 







|







 







|







 







|







 







|







110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
...
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
...
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
...
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
...
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
...
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
  }
} {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/}  ;# 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}
................................................................................
  }
} {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, tn DESC
  }
} {~/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 {
................................................................................
  }
} {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
do_test 2.4c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {~/ORDER BY/}  ;# optimized out


do_test 2.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}
................................................................................
  }
} {one-c one-a two-b two-a three-c three-a}  ;# verify same order after sorting
do_test 2.5c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {~/ORDER BY/}  ;# optimized out

do_test 2.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 2.6b {
................................................................................
  }
} {one-a one-c two-a two-b three-a three-c}  ;# verify same order after sorting
do_test 3.4c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {~/ORDER BY/}  ;# optimized out


do_test 3.5a {
  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}
................................................................................
  }
} {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
do_test 3.5c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {~/ORDER BY/}  ;# optimzed out


do_test 3.6a {
  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}