/ Check-in [8f448745]
Login

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

Overview
Comment:Yet another refactoring of ORDER BY logic in the query planner. This particular check-in works mostly, but still has a few minor issues.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | qp-enhancements
Files: files | file ages | folders
SHA1:8f4487450be1a2b0371f8251a967cbe341b2dea1
User & Date: drh 2012-10-04 12:10:25
Context
2012-10-08
18:23
Continued refactoring of the ORDER BY optimization logic. This check-in is close to working, but it still has issues. A few test cases fail. check-in: adbdc663 user: drh tags: qp-enhancements
2012-10-04
12:10
Yet another refactoring of ORDER BY logic in the query planner. This particular check-in works mostly, but still has a few minor issues. check-in: 8f448745 user: drh tags: qp-enhancements
2012-10-03
18:09
Fix an out-of-order memset() that occurs before all variable declarations are finished. Also fix a line that exceeds the 80-character line length limit. check-in: ba2f492f user: drh 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
....
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
....
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
....
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889

2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
....
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
....
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
....
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
....
3162
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
....
3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
....
3244
3245
3246
3247
3248
3249
3250

3251
3252

3253
3254
3255
3256
3257
3258
3259
....
3471
3472
3473
3474
3475
3476
3477
3478
3479
3480
3481
3482
3483
3484
3485
3486
3487
3488

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


    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) ){







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







 







|
|
|
>
>
>
>
>
>
>

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

>







 







<
<
<




|


>





|







<
<
<
<
<
<
<
<
<
<
<


<


>







 







|





>


<







 







>
>
>
>
>
>


|
|
|
>


<
<
<







|
<
<
|
<
<












>
>


|





<
<
|
<
<
<







 







<
<
<
<







 







<







 







|







 







<
<
<
<







 







>
|
<
>







 







|


|







1438
1439
1440
1441
1442
1443
1444
















1445
1446
1447
1448
1449
1450
1451
....
2761
2762
2763
2764
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
2811
2812
2813
2814
2815
2816
2817
....
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
....
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885

2886
2887
2888
2889
2890
2891
2892
....
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
....
3083
3084
3085
3086
3087
3088
3089




3090
3091
3092
3093
3094
3095
3096
....
3120
3121
3122
3123
3124
3125
3126

3127
3128
3129
3130
3131
3132
3133
....
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
....
3166
3167
3168
3169
3170
3171
3172




3173
3174
3175
3176
3177
3178
3179
....
3225
3226
3227
3228
3229
3230
3231
3232
3233

3234
3235
3236
3237
3238
3239
3240
3241
....
3453
3454
3455
3456
3457
3458
3459
3460
3461
3462
3463
3464
3465
3466
3467
3468
3469
3470

  /* 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 (*pbRev==sortOrder);
  }
  return 0;
}

/*
** Check to see if there is an == or IS NULL constraint in the WHERE clause
** that restricts base.iColumn to be well-ordered.  If base.iColumn must
** be a constant or must be NULL, that qualifies as well-ordered.  If
** base.iColumn must equal the value of a column in an outer loop that is
** ordered, that also qualifies as being well ordered.
**
** In the second case (when base.iColumn == an ordered value in an outer
** loop) set or verify the sort order.  If *pbRev is initially 2, then set
** it approprately.  If *pbRev is 0 or 1, make sure it matches the sort
** order of the outer loop constraint.
*/
static int existsEqualityColumnConstraint(
  WhereBestIdx *p,    /* Best index search context */
  Index *pIdx,        /* Constraint must be compatible with this index */
  int base,           /* Cursor number for the table to be sorted */
  int iColumn,        /* Index of a column on the "base" table */
  int *pbRev,         /* Set to 1 for reverse-order constraint */
  int *notNull        /* Set to 0 if an IS NULL constraint is seen */
){
  WhereTerm *pTerm;






  int rc;

WHERETRACE(("EQ Constraint on %d.%d: pbRev-in=%d", base, iColumn, *pbRev));
  pTerm = findTerm(p->pWC, base, iColumn, p->notReady, WO_EQ|WO_ISNULL, pIdx);
  if( pTerm==0 ){
    rc = 0;
  }else if( pTerm->prereqRight==0 ){
    rc = 1;
  }else if( pTerm->eOperator & WO_ISNULL ){
    *notNull = 0;
    rc = 1;
  }else{
    Expr *pRight = pTerm->pExpr->pRight;
    if( pRight->op==TK_COLUMN ){



      rc = isOrderedColumn(p, pRight->iTable, pRight->iColumn, pbRev);
    }else{
      rc = 0;
    }
  }

WHERETRACE((" rc=%d pbRev-out=%d\n", rc, *pbRev));
  return rc;
}
  

/*
** 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 *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 *pTerm;  /* 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 = 1;        /* 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( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return nPriorSat;
  }











  pOrderBy = p->pOrderBy;
  assert( pOrderBy!=0 );

  if( pIdx->bUnordered ) 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.
  */
  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 */
    int isEq;          /* Subject to an == or IS NULL constraint */
    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);
................................................................................
      iSortOrder = pIdx->aSortOrder[i];
      zColl = pIdx->azColl[i];
    }else{
      iColumn = -1;
      iSortOrder = 0;
      zColl = pColl->zName;
    }
    assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );
    assert( iSortOrder==0 || iSortOrder==1 );
    termSortOrder = pTerm->sortOrder;
    isEq = existsEqualityColumnConstraint(p, pIdx, base, iColumn,
                                         &termSortOrder, &uniqueNotNull);
    termSortOrder = iSortOrder ^ pTerm->sortOrder;
    if( pExpr->iColumn!=iColumn || sqlite3StrICmp(pColl->zName, zColl) ){
      /* Term j of the ORDER BY clause does not match column i of the index */
      if( isEq ){
        /* If an index column that is constrained by == or IS NULL fails to
        ** match an ORDER BY term, that is OK.  Just ignore that column of
        ** the index
        */
        continue;



      }else{
        /* If an index column fails to match and is not constrained by ==
        ** then the index cannot satisfy the ORDER BY constraint.
        */
        return nPriorSat;
      }
    }
    if( sortOrder<2 ){


      if( sortOrder!=termSortOrder ){


        /* 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;
    }else if( pTab->aCol[iColumn].notNull==0 ){
      uniqueNotNull = 0;
    }
  }
  *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++;
    }
  }
................................................................................
    **
    **    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;
    }
 
................................................................................
    ** 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 );
WHERETRACE(("--> before isSortingIndex: bRev=%d nPriorSat=%d\n", bRev, 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;
      }
................................................................................
    }


    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 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,
      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) ){