/ 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 Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

  1438   1438   
  1439   1439     /* Prevent ON clause terms of a LEFT JOIN from being used to drive
  1440   1440     ** an index for tables to the left of the join.
  1441   1441     */
  1442   1442     pTerm->prereqRight |= extraRight;
  1443   1443   }
  1444   1444   
  1445         -/*
  1446         -** Return TRUE if the given index is UNIQUE and all columns past the
  1447         -** first nSkip columns are NOT NULL.
  1448         -*/
  1449         -static int indexIsUniqueNotNull(Index *pIdx, int nSkip){
  1450         -  Table *pTab = pIdx->pTable;
  1451         -  int i;
  1452         -  if( pIdx->onError==OE_None ) return 0;
  1453         -  for(i=nSkip; i<pIdx->nColumn; i++){
  1454         -    int j = pIdx->aiColumn[i];
  1455         -    assert( j>=0 && j<pTab->nCol );
  1456         -    if( pTab->aCol[j].notNull==0 ) return 0;
  1457         -  }
  1458         -  return 1;
  1459         -}
  1460         -
  1461   1445   /*
  1462   1446   ** This function searches the expression list passed as the second argument
  1463   1447   ** for an expression of type TK_COLUMN that refers to the same column and
  1464   1448   ** uses the same collation sequence as the iCol'th column of index pIdx.
  1465   1449   ** Argument iBase is the cursor number used for the table that pIdx refers
  1466   1450   ** to.
  1467   1451   **
................................................................................
  2722   2706     }
  2723   2707     return rc;
  2724   2708   }
  2725   2709   #endif /* defined(SQLITE_ENABLE_STAT3) */
  2726   2710   
  2727   2711   /*
  2728   2712   ** Check to see if column iCol of the table with cursor iTab will appear
  2729         -** in sorted order according to the current query plan.  Return true if
  2730         -** it will and false if not.  
         2713  +** in sorted order according to the current query plan.
  2731   2714   **
  2732         -** If *pbRev is initially 2 (meaning "unknown") then set *pbRev to the
  2733         -** sort order of iTab.iCol.  If *pbRev is 0 or 1 but does not match
  2734         -** the sort order of iTab.iCol, then consider the column to be unordered.
         2715  +** Return values:
         2716  +**
         2717  +**    0   iCol is not ordered
         2718  +**    1   iCol has only a single value
         2719  +**    2   iCol is in ASC order
         2720  +**    3   iCol is in DESC order
  2735   2721   */
  2736         -static int isOrderedColumn(WhereBestIdx *p, int iTab, int iCol, int *pbRev){
         2722  +static int isOrderedColumn(
         2723  +  WhereBestIdx *p,
         2724  +  int iTab,
         2725  +  int iCol
         2726  +){
  2737   2727     int i, j;
  2738   2728     WhereLevel *pLevel = &p->aLevel[p->i-1];
  2739   2729     Index *pIdx;
  2740   2730     u8 sortOrder;
  2741   2731     for(i=p->i-1; i>=0; i--, pLevel--){
  2742   2732       if( pLevel->iTabCur!=iTab ) continue;
  2743   2733       if( (pLevel->plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
................................................................................
  2765   2755         testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 );
  2766   2756       }
  2767   2757       if( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 ){
  2768   2758         assert( sortOrder==0 || sortOrder==1 );
  2769   2759         testcase( sortOrder==1 );
  2770   2760         sortOrder = 1 - sortOrder;
  2771   2761       }
  2772         -    if( *pbRev==2 ){
  2773         -      *pbRev = sortOrder;
  2774         -      return 1;
  2775         -    }
  2776         -    return (*pbRev==sortOrder);
         2762  +    return sortOrder+2;
  2777   2763     }
  2778   2764     return 0;
  2779   2765   }
  2780   2766   
  2781         -/*
  2782         -** pTerm is an == constraint.  Check to see if the other side of
  2783         -** the == is a constant or a value that is guaranteed to be ordered
  2784         -** by outer loops.  Return 1 if pTerm is ordered, and 0 if not.
  2785         -*/
  2786         -static int isOrderedTerm(WhereBestIdx *p, WhereTerm *pTerm, int *pbRev){
  2787         -  Expr *pExpr = pTerm->pExpr;
  2788         -  assert( pExpr->op==TK_EQ );
  2789         -  assert( pExpr->pLeft!=0 && pExpr->pLeft->op==TK_COLUMN );
  2790         -  assert( pExpr->pRight!=0 );
  2791         -  if( pTerm->prereqRight==0 ){
  2792         -    return 1;  /* RHS of the == is a constant */
  2793         -  }
  2794         -  if( pExpr->pRight->op==TK_COLUMN 
  2795         -   && isOrderedColumn(p, pExpr->pRight->iTable, pExpr->pRight->iColumn, pbRev)
  2796         -  ){
  2797         -    return 1;
  2798         -  }
  2799         -
  2800         -  /* If we cannot prove that the constraint is ordered, assume it is not */
  2801         -  return 0;
  2802         -}
  2803         -
  2804   2767   /*
  2805   2768   ** This routine decides if pIdx can be used to satisfy the ORDER BY
  2806   2769   ** clause, either in whole or in part.  The return value is the 
  2807   2770   ** cumulative number of terms in the ORDER BY clause that are satisfied
  2808   2771   ** by the index pIdx and other indices in outer loops.
  2809   2772   **
  2810   2773   ** The table being queried has a cursor number of "base".  pIdx is the
................................................................................
  2821   2784   ** The *pbRev value is set to 0 order 1 depending on whether or not
  2822   2785   ** pIdx should be run in the forward order or in reverse order.
  2823   2786   */
  2824   2787   static int isSortingIndex(
  2825   2788     WhereBestIdx *p,    /* Best index search context */
  2826   2789     Index *pIdx,        /* The index we are testing */
  2827   2790     int base,           /* Cursor number for the table to be sorted */
  2828         -  int nEqCol,         /* Number of index columns with ordered == constraints */
  2829         -  int wsFlags,        /* Index usages flags */
  2830         -  int bOuterRev,      /* True if outer loops scan in reverse order */
  2831   2791     int *pbRev          /* Set to 1 for reverse-order scan of pIdx */
  2832   2792   ){
  2833   2793     int i;                        /* Number of pIdx terms used */
  2834   2794     int j;                        /* Number of ORDER BY terms satisfied */
  2835         -  int sortOrder = 0;            /* XOR of index and ORDER BY sort direction */
         2795  +  int sortOrder = 2;            /* 0: forward.  1: backward.  2: unknown */
  2836   2796     int nTerm;                    /* Number of ORDER BY terms */
  2837         -  struct ExprList_item *pTerm;  /* A term of the ORDER BY clause */
         2797  +  struct ExprList_item *pOBItem;/* A term of the ORDER BY clause */
         2798  +  Table *pTab = pIdx->pTable;   /* Table that owns index pIdx */
  2838   2799     ExprList *pOrderBy;           /* The ORDER BY clause */
  2839   2800     Parse *pParse = p->pParse;    /* Parser context */
  2840   2801     sqlite3 *db = pParse->db;     /* Database connection */
  2841   2802     int nPriorSat;                /* ORDER BY terms satisfied by outer loops */
  2842   2803     int seenRowid = 0;            /* True if an ORDER BY rowid term is seen */
  2843         -  int nEqOneRow;                /* Idx columns that ref unique values */
         2804  +  int uniqueNotNull;            /* pIdx is UNIQUE with all terms are NOT NULL */
  2844   2805   
  2845   2806     if( p->i==0 ){
  2846   2807       nPriorSat = 0;
  2847   2808     }else{
  2848   2809       nPriorSat = p->aLevel[p->i-1].plan.nOBSat;
  2849         -    if( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return nPriorSat;
  2850         -  }
  2851         -  if( nEqCol==0 ){
  2852         -    if( p->i && (p->aLevel[p->i-1].plan.wsFlags & WHERE_ORDERED)==0 ){
         2810  +    if( (p->aLevel[p->i-1].plan.wsFlags & WHERE_ORDERED)==0 ){
         2811  +      /* This loop cannot be ordered unless the next outer loop is
         2812  +      ** also ordered */
         2813  +      return nPriorSat;
         2814  +    }
         2815  +    if( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ){
         2816  +      /* Only look at the outer-most loop if the OrderByIdxJoin
         2817  +      ** optimization is disabled */
  2853   2818         return nPriorSat;
  2854   2819       }
  2855         -    nEqOneRow = 0;
  2856         -  }else if( p->i==0 || (p->aLevel[p->i-1].plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
  2857         -    nEqOneRow = nEqCol;
  2858         -  }else{
  2859         -    sortOrder = bOuterRev;
  2860         -    nEqOneRow = -1;
  2861   2820     }
  2862   2821     pOrderBy = p->pOrderBy;
  2863   2822     assert( pOrderBy!=0 );
  2864         -  if( wsFlags & WHERE_COLUMN_IN ) return nPriorSat;
  2865         -  if( pIdx->bUnordered ) return nPriorSat;
         2823  +  if( pIdx->bUnordered ){
         2824  +    /* Hash indices (indicated by the "unordered" tag on sqlite_stat1) cannot
         2825  +    ** be used for sorting */
         2826  +    return nPriorSat;
         2827  +  }
  2866   2828     nTerm = pOrderBy->nExpr;
         2829  +  uniqueNotNull = pIdx->onError!=OE_None;
  2867   2830     assert( nTerm>0 );
  2868   2831   
  2869   2832     /* Argument pIdx must either point to a 'real' named index structure, 
  2870   2833     ** or an index structure allocated on the stack by bestBtreeIndex() to
  2871   2834     ** represent the rowid index that is part of every table.  */
  2872   2835     assert( pIdx->zName || (pIdx->nColumn==1 && pIdx->aiColumn[0]==-1) );
  2873   2836   
................................................................................
  2875   2838     ** the index.
  2876   2839     **
  2877   2840     ** Note that indices have pIdx->nColumn regular columns plus
  2878   2841     ** one additional column containing the rowid.  The rowid column
  2879   2842     ** of the index is also allowed to match against the ORDER BY
  2880   2843     ** clause.
  2881   2844     */
  2882         -  for(i=0,j=nPriorSat,pTerm=&pOrderBy->a[j]; j<nTerm; i++){
  2883         -    Expr *pExpr;       /* The expression of the ORDER BY pTerm */
  2884         -    CollSeq *pColl;    /* The collating sequence of pExpr */
  2885         -    int termSortOrder; /* Sort order for this term */
  2886         -    int iColumn;       /* The i-th column of the index.  -1 for rowid */
  2887         -    int iSortOrder;    /* 1 for DESC, 0 for ASC on the i-th index term */
  2888         -    const char *zColl; /* Name of the collating sequence for i-th index term */
         2845  +  j = nPriorSat;
         2846  +  for(i=0,pOBItem=&pOrderBy->a[j]; j<nTerm && i<=pIdx->nColumn; i++){
         2847  +    Expr *pOBExpr;          /* The expression of the ORDER BY pOBItem */
         2848  +    CollSeq *pColl;         /* The collating sequence of pOBExpr */
         2849  +    int termSortOrder;      /* Sort order for this term */
         2850  +    int iColumn;            /* The i-th column of the index.  -1 for rowid */
         2851  +    int iSortOrder;         /* 1 for DESC, 0 for ASC on the i-th index term */
         2852  +    int isEq;               /* Subject to an == or IS NULL constraint */
         2853  +    int isMatch;            /* ORDER BY term matches the index term */
         2854  +    const char *zColl;      /* Name of collating sequence for i-th index term */
         2855  +    WhereTerm *pConstraint; /* A constraint in the WHERE clause */
  2889   2856   
  2890         -    assert( i<=pIdx->nColumn );
  2891         -    pExpr = pTerm->pExpr;
  2892         -    if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){
  2893         -      /* Can not use an index sort on anything that is not a column in the
  2894         -      ** left-most table of the FROM clause */
         2857  +    /* If the next term of the ORDER BY clause refers to anything other than
         2858  +    ** a column in the "base" table, then this index will not be of any
         2859  +    ** further use in handling the ORDER BY. */
         2860  +    pOBExpr = pOBItem->pExpr;
         2861  +    if( pOBExpr->op!=TK_COLUMN || pOBExpr->iTable!=base ){
  2895   2862         break;
  2896   2863       }
  2897         -    pColl = sqlite3ExprCollSeq(pParse, pExpr);
  2898         -    if( !pColl ){
  2899         -      pColl = db->pDfltColl;
  2900         -    }
         2864  +
         2865  +    /* Find column number and collating sequence for the next entry
         2866  +    ** in the index */
  2901   2867       if( pIdx->zName && i<pIdx->nColumn ){
  2902   2868         iColumn = pIdx->aiColumn[i];
  2903   2869         if( iColumn==pIdx->pTable->iPKey ){
  2904   2870           iColumn = -1;
  2905   2871         }
  2906   2872         iSortOrder = pIdx->aSortOrder[i];
  2907   2873         zColl = pIdx->azColl[i];
         2874  +      assert( zColl!=0 );
  2908   2875       }else{
  2909   2876         iColumn = -1;
  2910   2877         iSortOrder = 0;
  2911         -      zColl = pColl->zName;
  2912         -    }
  2913         -    if( pExpr->iColumn!=iColumn || sqlite3StrICmp(pColl->zName, zColl) ){
  2914         -      /* Term j of the ORDER BY clause does not match column i of the index */
  2915         -      if( i<nEqCol ){
  2916         -        /* If an index column that is constrained by == fails to match an
  2917         -        ** ORDER BY term, that is OK.  Just ignore that column of the index
  2918         -        */
  2919         -        continue;
  2920         -      }else if( i==pIdx->nColumn ){
  2921         -        /* Index column i is the rowid.  All other terms match. */
         2878  +      zColl = 0;
         2879  +    }
         2880  +
         2881  +    /* Check to see if the column number and collating sequence of the
         2882  +    ** index match the column number and collating sequence of the ORDER BY
         2883  +    ** clause entry.  Set isMatch to 1 if they both match. */
         2884  +    if( pOBExpr->iColumn==iColumn ){
         2885  +      if( zColl ){
         2886  +        pColl = sqlite3ExprCollSeq(pParse, pOBExpr);
         2887  +        if( !pColl ) pColl = db->pDfltColl;
         2888  +        isMatch = sqlite3StrICmp(pColl->zName, zColl)==0;
         2889  +      }else{
         2890  +        isMatch = 1;
         2891  +      }
         2892  +    }else{
         2893  +      isMatch = 0;
         2894  +    }
         2895  +
         2896  +    /* termSortOrder is 0 or 1 for whether or not the access loop should
         2897  +    ** run forward or backwards (respectively) in order to satisfy this 
         2898  +    ** term of the ORDER BY clause. */
         2899  +    termSortOrder = iSortOrder ^ pOBItem->sortOrder;
         2900  +
         2901  +    /* If X is the column in the index and ORDER BY clause, check to see
         2902  +    ** if there are any X= or X IS NULL constraints in the WHERE clause. */
         2903  +    pConstraint = findTerm(p->pWC, base, iColumn, p->notReady,
         2904  +                           WO_EQ|WO_ISNULL|WO_IN, pIdx);
         2905  +    if( pConstraint==0 ){
         2906  +      isEq = 0;
         2907  +    }else if( pConstraint->eOperator==WO_IN ){
         2908  +      break;
         2909  +    }else if( pConstraint->eOperator==WO_ISNULL ){
         2910  +      uniqueNotNull = 0;
         2911  +      isEq = 1;
         2912  +    }else if( pConstraint->prereqRight==0 ){
         2913  +      isEq = 1;
         2914  +    }else{
         2915  +      Expr *pRight = pConstraint->pExpr->pRight;
         2916  +      if( pRight->op==TK_COLUMN ){
         2917  +        WHERETRACE(("       .. isOrderedColumn(tab=%d,col=%d)",
         2918  +                    pRight->iTable, pRight->iColumn));
         2919  +        isEq = isOrderedColumn(p, pRight->iTable, pRight->iColumn);
         2920  +        WHERETRACE((" -> isEq=%d\n", isEq));
         2921  +        if( isMatch && isEq>=2 && isEq!=pOBItem->sortOrder+2 ){
         2922  +          break;
         2923  +        }
         2924  +      }else{
         2925  +        isEq = 0;
         2926  +      }
         2927  +    }
         2928  +    assert( pOBItem->sortOrder==0 || pOBItem->sortOrder==1 );
         2929  +    assert( iSortOrder==0 || iSortOrder==1 );
         2930  +    if( !isMatch ){
         2931  +      if( isEq==0 ){
  2922   2932           break;
  2923   2933         }else{
  2924         -        /* If an index column fails to match and is not constrained by ==
  2925         -        ** then the index cannot satisfy the ORDER BY constraint.
  2926         -        */
  2927         -        return nPriorSat;
         2934  +        continue;
  2928   2935         }
  2929         -    }
  2930         -    assert( pIdx->aSortOrder!=0 || iColumn==-1 );
  2931         -    assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );
  2932         -    assert( iSortOrder==0 || iSortOrder==1 );
  2933         -    termSortOrder = iSortOrder ^ pTerm->sortOrder;
  2934         -    if( i>nEqOneRow ){
  2935         -      if( termSortOrder!=sortOrder ){
  2936         -        /* Indices can only be used if all ORDER BY terms past the
  2937         -        ** equality constraints have the correct DESC or ASC. */
         2936  +    }else if( isEq!=1 ){
         2937  +      if( sortOrder==2 ){
         2938  +        sortOrder = termSortOrder;
         2939  +      }else if( termSortOrder!=sortOrder ){
  2938   2940           break;
  2939   2941         }
  2940         -    }else{
  2941         -      sortOrder = termSortOrder;
  2942   2942       }
  2943   2943       j++;
  2944         -    pTerm++;
         2944  +    pOBItem++;
  2945   2945       if( iColumn<0 ){
  2946   2946         seenRowid = 1;
  2947   2947         break;
         2948  +    }else if( pTab->aCol[iColumn].notNull==0 && isEq==0 ){
         2949  +      uniqueNotNull = 0;
  2948   2950       }
  2949   2951     }
  2950         -  *pbRev = sortOrder;
         2952  +
         2953  +  /* If we have not found at least one ORDER BY term that matches the
         2954  +  ** index, then show no progress. */
         2955  +  if( pOBItem==&pOrderBy->a[nPriorSat] ) return nPriorSat;
         2956  +
         2957  +  /* Return the necessary scan order back to the caller */
         2958  +  *pbRev = sortOrder & 1;
  2951   2959   
  2952   2960     /* If there was an "ORDER BY rowid" term that matched, or it is only
  2953   2961     ** possible for a single row from this table to match, then skip over
  2954   2962     ** any additional ORDER BY terms dealing with this table.
  2955   2963     */
  2956         -  if( seenRowid ||
  2957         -     (   (wsFlags & WHERE_COLUMN_NULL)==0
  2958         -      && i>=pIdx->nColumn
  2959         -      && indexIsUniqueNotNull(pIdx, nEqCol)
  2960         -     )
  2961         -  ){
         2964  +  if( seenRowid || (uniqueNotNull && i>=pIdx->nColumn) ){
  2962   2965       /* Advance j over additional ORDER BY terms associated with base */
  2963   2966       WhereMaskSet *pMS = p->pWC->pMaskSet;
  2964   2967       Bitmask m = ~getMask(pMS, base);
  2965   2968       while( j<nTerm && (exprTableUsage(pMS, pOrderBy->a[j].pExpr)&m)==0 ){
  2966   2969         j++;
  2967   2970       }
  2968   2971     }
................................................................................
  3061   3064     /* Loop over all indices looking for the best one to use
  3062   3065     */
  3063   3066     for(; pProbe; pIdx=pProbe=pProbe->pNext){
  3064   3067       const tRowcnt * const aiRowEst = pProbe->aiRowEst;
  3065   3068       WhereCost pc;               /* Cost of using pProbe */
  3066   3069       double log10N = (double)1;  /* base-10 logarithm of nRow (inexact) */
  3067   3070       int bRev = 2;               /* 0=forward scan.  1=reverse.  2=undecided */
         3071  +
         3072  +    WHERETRACE((
         3073  +      "   %s(%s):\n",
         3074  +      pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk")
         3075  +    ));
  3068   3076   
  3069   3077       /* The following variables are populated based on the properties of
  3070   3078       ** index being evaluated. They are then used to determine the expected
  3071   3079       ** cost and number of rows returned.
  3072   3080       **
  3073   3081       **  pc.plan.nEq: 
  3074   3082       **    Number of equality terms that can be implemented using the index.
................................................................................
  3091   3099       **
  3092   3100       **    nInMul is set to 1.
  3093   3101       **
  3094   3102       **    If there exists a WHERE term of the form "x IN (SELECT ...)", then 
  3095   3103       **    the sub-select is assumed to return 25 rows for the purposes of 
  3096   3104       **    determining nInMul.
  3097   3105       **
  3098         -    **  nOrdered:
  3099         -    **    The number of equality terms that are constrainted by outer loop
  3100         -    **    variables that are well-ordered.
  3101         -    **
  3102   3106       **  bInEst:  
  3103   3107       **    Set to true if there was at least one "x IN (SELECT ...)" term used 
  3104   3108       **    in determining the value of nInMul.  Note that the RHS of the
  3105   3109       **    IN operator must be a SELECT, not a value list, for this variable
  3106   3110       **    to be true.
  3107   3111       **
  3108   3112       **  rangeDiv:
................................................................................
  3132   3136       **    two queries requires table b-tree lookups in order to find the value
  3133   3137       **    of column c, but the first does not because columns a and b are
  3134   3138       **    both available in the index.
  3135   3139       **
  3136   3140       **             SELECT a, b    FROM tbl WHERE a = 1;
  3137   3141       **             SELECT a, b, c FROM tbl WHERE a = 1;
  3138   3142       */
  3139         -    int nOrdered;                 /* Number of ordered terms matching index */
  3140   3143       int bInEst = 0;               /* True if "x IN (SELECT...)" seen */
  3141   3144       int nInMul = 1;               /* Number of distinct equalities to lookup */
  3142   3145       double rangeDiv = (double)1;  /* Estimated reduction in search space */
  3143   3146       int nBound = 0;               /* Number of range constraints seen */
  3144   3147       int bSort;                    /* True if external sort required */
  3145   3148       int bDist;                    /* True if index cannot help with DISTINCT */
  3146   3149       int bLookup = 0;              /* True if not a covering index */
................................................................................
  3160   3163       }else{
  3161   3164         nPriorSat = pc.plan.nOBSat = 0;
  3162   3165         bSort = nOrderBy>0;
  3163   3166         bDist = p->pDistinct!=0;
  3164   3167       }
  3165   3168   
  3166   3169       /* Determine the values of pc.plan.nEq and nInMul */
  3167         -    for(pc.plan.nEq=nOrdered=0; pc.plan.nEq<pProbe->nColumn; pc.plan.nEq++){
         3170  +    for(pc.plan.nEq=0; pc.plan.nEq<pProbe->nColumn; pc.plan.nEq++){
  3168   3171         int j = pProbe->aiColumn[pc.plan.nEq];
  3169   3172         pTerm = findTerm(pWC, iCur, j, p->notReady, eqTermMask, pIdx);
  3170   3173         if( pTerm==0 ) break;
  3171   3174         pc.plan.wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
  3172   3175         testcase( pTerm->pWC!=pWC );
  3173   3176         if( pTerm->eOperator & WO_IN ){
  3174   3177           Expr *pExpr = pTerm->pExpr;
................................................................................
  3179   3182             bInEst = 1;
  3180   3183           }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
  3181   3184             /* "x IN (value, value, ...)" */
  3182   3185             nInMul *= pExpr->x.pList->nExpr;
  3183   3186           }
  3184   3187         }else if( pTerm->eOperator & WO_ISNULL ){
  3185   3188           pc.plan.wsFlags |= WHERE_COLUMN_NULL;
  3186         -        if( pc.plan.nEq==nOrdered ) nOrdered++;
  3187         -      }else if( bSort && pc.plan.nEq==nOrdered
  3188         -             && isOrderedTerm(p,pTerm,&bRev) ){
  3189         -        nOrdered++;
  3190   3189         }
  3191   3190   #ifdef SQLITE_ENABLE_STAT3
  3192   3191         if( pc.plan.nEq==0 && pProbe->aSample ) pFirstTerm = pTerm;
  3193   3192   #endif
  3194   3193         pc.used |= pTerm->prereqRight;
  3195   3194       }
  3196   3195    
................................................................................
  3238   3237   
  3239   3238       /* If there is an ORDER BY clause and the index being considered will
  3240   3239       ** naturally scan rows in the required order, set the appropriate flags
  3241   3240       ** in pc.plan.wsFlags. Otherwise, if there is an ORDER BY clause but
  3242   3241       ** the index will scan rows in a different order, set the bSort
  3243   3242       ** variable.  */
  3244   3243       assert( bRev>=0 && bRev<=2 );
  3245         -    if( bSort ){
  3246         -      testcase( bRev==0 );
  3247         -      testcase( bRev==1 );
  3248         -      testcase( bRev==2 );
  3249         -      pc.plan.nOBSat = isSortingIndex(p, pProbe, iCur, nOrdered,
  3250         -                                 pc.plan.wsFlags, bRev&1, &bRev);
         3244  +    if( bSort && (pSrc->jointype & JT_LEFT)==0 ){
         3245  +      int bRev = 2;
         3246  +      WHERETRACE(("      --> before isSortingIndex: nPriorSat=%d\n",nPriorSat));
         3247  +      pc.plan.nOBSat = isSortingIndex(p, pProbe, iCur, &bRev);
         3248  +      WHERETRACE(("      --> after  isSortingIndex: bRev=%d nOBSat=%d\n",
         3249  +                  bRev, pc.plan.nOBSat));
  3251   3250         if( nPriorSat<pc.plan.nOBSat || (pc.plan.wsFlags & WHERE_UNIQUE)!=0 ){
  3252   3251           pc.plan.wsFlags |= WHERE_ORDERED;
  3253   3252         }
  3254   3253         if( nOrderBy==pc.plan.nOBSat ){
  3255   3254           bSort = 0;
  3256   3255           pc.plan.wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE;
  3257   3256         }
................................................................................
  3361   3360         ** the cost function to err on the side of choosing an index over
  3362   3361         ** choosing a full scan.  This 4x full-scan penalty is an arguable
  3363   3362         ** decision and one which we expect to revisit in the future.  But
  3364   3363         ** it seems to be working well enough at the moment.
  3365   3364         */
  3366   3365         pc.rCost = aiRowEst[0]*4;
  3367   3366         pc.plan.wsFlags &= ~WHERE_IDX_ONLY;
  3368         -      if( pIdx ) pc.plan.wsFlags &= ~WHERE_ORDERED;
         3367  +      if( pIdx ){
         3368  +        pc.plan.wsFlags &= ~WHERE_ORDERED;
         3369  +        pc.plan.nOBSat = nPriorSat;
         3370  +      }
  3369   3371       }else{
  3370   3372         log10N = estLog(aiRowEst[0]);
  3371   3373         pc.rCost = pc.plan.nRow;
  3372   3374         if( pIdx ){
  3373   3375           if( bLookup ){
  3374   3376             /* For an index lookup followed by a table lookup:
  3375   3377             **    nInMul index searches to find the start of each index range
................................................................................
  3466   3468           }
  3467   3469         }
  3468   3470         if( pc.plan.nRow<2 ) pc.plan.nRow = 2;
  3469   3471       }
  3470   3472   
  3471   3473   
  3472   3474       WHERETRACE((
  3473         -      "%s(%s):\n"
  3474         -      "    nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%08x\n"
  3475         -      "    notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f\n"
  3476         -      "    used=0x%llx nOrdered=%d nOBSat=%d\n",
  3477         -      pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"), 
         3475  +      "      nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%08x\n"
         3476  +      "      notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f\n"
         3477  +      "      used=0x%llx nOBSat=%d\n",
  3478   3478         pc.plan.nEq, nInMul, (int)rangeDiv, bSort, bLookup, pc.plan.wsFlags,
  3479         -      p->notReady, log10N, pc.plan.nRow, pc.rCost, pc.used, nOrdered,
         3479  +      p->notReady, log10N, pc.plan.nRow, pc.rCost, pc.used,
  3480   3480         pc.plan.nOBSat
  3481   3481       ));
  3482   3482   
  3483   3483       /* If this index is the best we have seen so far, then record this
  3484   3484       ** index and its cost in the p->cost structure.
  3485   3485       */
  3486   3486       if( (!pIdx || pc.plan.wsFlags) && compareCost(&pc, &p->cost) ){
................................................................................
  3510   3510     assert( p->pOrderBy || (p->cost.plan.wsFlags&WHERE_ORDERED)==0 );
  3511   3511     assert( p->cost.plan.u.pIdx==0 || (p->cost.plan.wsFlags&WHERE_ROWID_EQ)==0 );
  3512   3512     assert( pSrc->pIndex==0 
  3513   3513          || p->cost.plan.u.pIdx==0 
  3514   3514          || p->cost.plan.u.pIdx==pSrc->pIndex 
  3515   3515     );
  3516   3516   
  3517         -  WHERETRACE(("best index is: %s\n",
         3517  +  WHERETRACE(("   best index is: %s\n",
  3518   3518            p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk"));
  3519   3519     
  3520   3520     bestOrClauseIndex(p);
  3521   3521     bestAutomaticIndex(p);
  3522   3522     p->cost.plan.wsFlags |= eqTermMask;
  3523   3523   }
  3524   3524   
................................................................................
  5060   5060           if( (m & sWBI.notValid)==0 ){
  5061   5061             if( j==iFrom ) iFrom++;
  5062   5062             continue;
  5063   5063           }
  5064   5064           sWBI.notReady = (isOptimal ? m : sWBI.notValid);
  5065   5065           if( sWBI.pSrc->pIndex==0 ) nUnconstrained++;
  5066   5066     
  5067         -        WHERETRACE(("=== trying table %d (%s) with isOptimal=%d ===\n",
         5067  +        WHERETRACE(("   === trying table %d (%s) with isOptimal=%d ===\n",
  5068   5068                       j, sWBI.pSrc->pTab->zName, isOptimal));
  5069   5069           assert( sWBI.pSrc->pTab );
  5070   5070   #ifndef SQLITE_OMIT_VIRTUALTABLE
  5071   5071           if( IsVirtual(sWBI.pSrc->pTab) ){
  5072   5072             sWBI.ppIdxInfo = &pWInfo->a[j].pIdxInfo;
  5073   5073             bestVirtualIndex(&sWBI);
  5074   5074           }else 
................................................................................
  5113   5113               && (bestJ<0 || (notIndexed&m)!=0                     /* (2) */
  5114   5114                   || (bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
  5115   5115                   || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
  5116   5116               && (nUnconstrained==0 || sWBI.pSrc->pIndex==0        /* (3) */
  5117   5117                   || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
  5118   5118               && (bestJ<0 || compareCost(&sWBI.cost, &bestPlan))   /* (4) */
  5119   5119           ){
  5120         -          WHERETRACE(("=== table %d (%s) is best so far\n"
  5121         -                      "    cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=%08x\n",
         5120  +          WHERETRACE(("   === table %d (%s) is best so far\n"
         5121  +                      "       cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=%08x\n",
  5122   5122                         j, sWBI.pSrc->pTab->zName,
  5123   5123                         sWBI.cost.rCost, sWBI.cost.plan.nRow,
  5124   5124                         sWBI.cost.plan.nOBSat, sWBI.cost.plan.wsFlags));
  5125   5125             bestPlan = sWBI.cost;
  5126   5126             bestJ = j;
  5127   5127           }
  5128   5128           if( doNotReorder ) break;

Changes to test/orderby1.test.

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