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 |
Timelines: | family | ancestors | descendants | both | qp-enhancements |
Files: | files | file ages | folders |
SHA1: |
8f4487450be1a2b0371f8251a967cbe3 |
User & Date: | drh 2012-10-04 12:10:25.997 |
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: adbdc663f3 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: 8f4487450b 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: ba2f492f95 user: drh tags: trunk) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
1438 1439 1440 1441 1442 1443 1444 | /* 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; } | < < < < < < < < < < < < < < < < | 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 | /* 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. ** |
︙ | ︙ | |||
2777 2778 2779 2780 2781 2782 2783 | } return (*pbRev==sortOrder); } return 0; } /* | | > | > > > > > > | > | > > > > > > | > | < > > | > | | > > > | > | | < | > | | < > | > | 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 | } 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. ** |
︙ | ︙ | |||
2823 2824 2825 2826 2827 2828 2829 | ** 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 */ | < < < | > | < < < < < < < < < < < < > | > < | 2829 2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841 2842 2843 2844 2845 2846 2847 2848 2849 2850 2851 2852 2853 2854 2855 2856 2857 2858 2859 2860 2861 2862 2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874 2875 2876 2877 2878 2879 2880 2881 2882 2883 2884 2885 2886 2887 2888 2889 2890 2891 2892 | ** 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) ); /* Match terms of the ORDER BY clause against columns of ** the index. ** ** Note that indices have pIdx->nColumn regular columns plus ** one additional column containing the rowid. The rowid column ** of the index is also allowed to match against the ORDER BY ** clause. */ for(i=0,j=nPriorSat,pTerm=&pOrderBy->a[j]; j<nTerm && i<=pIdx->nColumn; i++){ Expr *pExpr; /* The expression of the ORDER BY pTerm */ CollSeq *pColl; /* The collating sequence of pExpr */ int termSortOrder; /* Sort order for this term */ int iColumn; /* The i-th column of the index. -1 for rowid */ int iSortOrder; /* 1 for DESC, 0 for ASC on the i-th index term */ 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); |
︙ | ︙ | |||
2908 2909 2910 2911 2912 2913 2914 2915 2916 | 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 */ | > > > > > > | | | > < < < < < | | < < > > | | < < < < < | 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 | 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++; } } |
︙ | ︙ | |||
3093 3094 3095 3096 3097 3098 3099 | ** ** 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. ** | < < < < | 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 | ** ** 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: |
︙ | ︙ | |||
3134 3135 3136 3137 3138 3139 3140 | ** 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; */ | < | 3120 3121 3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132 3133 | ** 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 */ |
︙ | ︙ | |||
3162 3163 3164 3165 3166 3167 3168 | }else{ nPriorSat = pc.plan.nOBSat = 0; bSort = nOrderBy>0; bDist = p->pDistinct!=0; } /* Determine the values of pc.plan.nEq and nInMul */ | | < < < < | 3147 3148 3149 3150 3151 3152 3153 3154 3155 3156 3157 3158 3159 3160 3161 3162 3163 3164 3165 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 | }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; pc.plan.wsFlags |= WHERE_COLUMN_IN; if( ExprHasProperty(pExpr, EP_xIsSelect) ){ /* "x IN (SELECT ...)": Assume the SELECT returns 25 rows */ nInMul *= 25; 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; } |
︙ | ︙ | |||
3244 3245 3246 3247 3248 3249 3250 | ** 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 ); | > | | | 3225 3226 3227 3228 3229 3230 3231 3232 3233 3234 3235 3236 3237 3238 3239 3240 3241 | ** 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; } |
︙ | ︙ | |||
3471 3472 3473 3474 3475 3476 3477 | } 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" | | | | 3453 3454 3455 3456 3457 3458 3459 3460 3461 3462 3463 3464 3465 3466 3467 3468 3469 3470 | } 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) ){ |
︙ | ︙ |