Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Improved ORDER BY optimization when outer loops of a join return a single row. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
62225b4a4c4bfe1820ef54cb202edf2c |
User & Date: | drh 2012-09-29 19:10:29.355 |
Context
2012-10-01
| ||
06:50 | Ensure that the value returned by xSectorSize() is reasonable (currently defined as between 2^5 and 2^16 bytes) before using it to calculate the amount of padding to add to a wal file. (check-in: 6b4ff83bff user: dan tags: trunk) | |
2012-09-29
| ||
19:10 | Improved ORDER BY optimization when outer loops of a join return a single row. (check-in: 62225b4a4c user: drh tags: trunk) | |
15:45 | Disable the bigfile tests on Macs. (check-in: d869eddaf2 user: drh tags: trunk) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
253 254 255 256 257 258 259 | #define WHERE_COLUMN_NULL 0x00080000 /* x IS NULL */ #define WHERE_INDEXED 0x000f0000 /* Anything that uses an index */ #define WHERE_NOT_FULLSCAN 0x100f3000 /* Does not do a full table scan */ #define WHERE_IN_ABLE 0x000f1000 /* Able to support an IN operator */ #define WHERE_TOP_LIMIT 0x00100000 /* x<EXPR or x<=EXPR constraint */ #define WHERE_BTM_LIMIT 0x00200000 /* x>EXPR or x>=EXPR constraint */ #define WHERE_BOTH_LIMIT 0x00300000 /* Both x>EXPR and x<EXPR */ | | | | | > | 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 | #define WHERE_COLUMN_NULL 0x00080000 /* x IS NULL */ #define WHERE_INDEXED 0x000f0000 /* Anything that uses an index */ #define WHERE_NOT_FULLSCAN 0x100f3000 /* Does not do a full table scan */ #define WHERE_IN_ABLE 0x000f1000 /* Able to support an IN operator */ #define WHERE_TOP_LIMIT 0x00100000 /* x<EXPR or x<=EXPR constraint */ #define WHERE_BTM_LIMIT 0x00200000 /* x>EXPR or x>=EXPR constraint */ #define WHERE_BOTH_LIMIT 0x00300000 /* Both x>EXPR and x<EXPR */ #define WHERE_IDX_ONLY 0x00400000 /* Use index only - omit table */ #define WHERE_ORDERBY 0x00800000 /* Output will appear in correct order */ #define WHERE_REVERSE 0x01000000 /* Scan in reverse order */ #define WHERE_UNIQUE 0x02000000 /* Selects no more than one row */ #define WHERE_ALL_UNIQUE 0x04000000 /* This and all prior have one row */ #define WHERE_VIRTUALTABLE 0x08000000 /* Use virtual-table processing */ #define WHERE_MULTI_OR 0x10000000 /* OR using multiple indices */ #define WHERE_TEMP_INDEX 0x20000000 /* Uses an ephemeral index */ #define WHERE_DISTINCT 0x40000000 /* Correct order for DISTINCT */ #define WHERE_COVER_SCAN 0x80000000 /* Full scan of a covering index */ /* |
︙ | ︙ | |||
1602 1603 1604 1605 1606 1607 1608 | return 1; } } return 0; } | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < | 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 | return 1; } } return 0; } /* ** Prepare a crude estimate of the logarithm of the input value. ** The results need not be exact. This is only used for estimating ** the total cost of performing operations with O(logN) or O(NlogN) ** complexity. Because N is just a guess, it is no great tragedy if ** logN is a little off. */ |
︙ | ︙ | |||
2880 2881 2882 2883 2884 2885 2886 2887 2888 2889 2890 2891 2892 2893 | static int isOrderedColumn(WhereBestIdx *p, int iTab, int iCol, int *pbRev){ int i, j; WhereLevel *pLevel = &p->aLevel[p->i-1]; Index *pIdx; u8 sortOrder; for(i=p->i-1; i>=0; i--, pLevel--){ if( pLevel->iTabCur!=iTab ) continue; if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){ pIdx = pLevel->plan.u.pIdx; if( iCol<0 ){ sortOrder = 0; testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 ); }else{ for(j=0; j<pIdx->nColumn; j++){ | > > > | 2721 2722 2723 2724 2725 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 | static int isOrderedColumn(WhereBestIdx *p, int iTab, int iCol, int *pbRev){ int i, j; WhereLevel *pLevel = &p->aLevel[p->i-1]; Index *pIdx; u8 sortOrder; for(i=p->i-1; i>=0; i--, pLevel--){ if( pLevel->iTabCur!=iTab ) continue; if( (pLevel->plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){ return 1; } if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){ pIdx = pLevel->plan.u.pIdx; if( iCol<0 ){ sortOrder = 0; testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 ); }else{ for(j=0; j<pIdx->nColumn; j++){ |
︙ | ︙ | |||
2922 2923 2924 2925 2926 2927 2928 | ** 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 ); | < < < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 2766 2767 2768 2769 2770 2771 2772 2773 2774 2775 2776 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 2793 2794 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 2823 2824 2825 2826 2827 2828 2829 2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841 2842 2843 2844 2845 2846 2847 2848 2849 2850 2851 2852 2853 2854 2855 2856 2857 2858 2859 2860 2861 2862 2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874 2875 2876 2877 2878 2879 2880 2881 2882 2883 2884 2885 2886 2887 2888 2889 2890 2891 2892 2893 2894 2895 2896 2897 2898 2899 2900 2901 2902 2903 2904 2905 2906 2907 2908 2909 2910 2911 2912 2913 2914 2915 2916 2917 2918 2919 2920 2921 2922 2923 2924 2925 2926 2927 2928 2929 2930 2931 2932 2933 2934 2935 2936 2937 2938 2939 2940 2941 2942 2943 2944 2945 2946 2947 2948 2949 2950 2951 2952 2953 2954 | ** by outer loops. Return 1 if pTerm is ordered, and 0 if not. */ static int isOrderedTerm(WhereBestIdx *p, WhereTerm *pTerm, int *pbRev){ Expr *pExpr = pTerm->pExpr; assert( pExpr->op==TK_EQ ); assert( pExpr->pLeft!=0 && pExpr->pLeft->op==TK_COLUMN ); assert( pExpr->pRight!=0 ); if( pTerm->prereqRight==0 ){ return 1; /* RHS of the == is a constant */ } if( pExpr->pRight->op==TK_COLUMN && isOrderedColumn(p, pExpr->pRight->iTable, pExpr->pRight->iColumn, pbRev) ){ return 1; } /* If we cannot prove that the constraint is ordered, assume it is not */ return 0; } /* ** This routine decides if pIdx can be used to satisfy the ORDER BY ** clause, either in whole or in part. The return value is the ** cumulative number of terms in the ORDER BY clause that are satisfied ** by the index pIdx and other indices in outer loops. ** ** The table being queried has a cursor number of "base". pIdx is the ** index that is postulated for use to access the table. ** ** nEqCol is the number of columns of pIdx that are used as equality ** constraints and where the other side of the == is an ordered column ** or constant. An "order column" in the previous sentence means a column ** in table from an outer loop whose values will always appear in the ** correct order due to othre index, or because the outer loop generates ** a unique result. Any of the first nEqCol columns of pIdx may be missing ** from the ORDER BY clause and the match can still be a success. ** ** The *pbRev value is set to 0 order 1 depending on whether or not ** pIdx should be run in the forward order or in reverse order. */ static int isSortingIndex( WhereBestIdx *p, /* Best index search context */ Index *pIdx, /* The index we are testing */ int base, /* Cursor number for the table to be sorted */ int nEqCol, /* Number of index columns with ordered == constraints */ int wsFlags, /* Index usages flags */ int bOuterRev, /* True if outer loops scan in reverse order */ int *pbRev /* Set to 1 for reverse-order scan of pIdx */ ){ int i; /* Number of pIdx terms used */ int j; /* Number of ORDER BY terms satisfied */ int sortOrder = 0; /* XOR of index and ORDER BY sort direction */ int nTerm; /* Number of ORDER BY terms */ struct ExprList_item *pTerm; /* A term of the ORDER BY clause */ ExprList *pOrderBy; /* The ORDER BY clause */ Parse *pParse = p->pParse; /* Parser context */ sqlite3 *db = pParse->db; /* Database connection */ int nPriorSat; /* ORDER BY terms satisfied by outer loops */ int seenRowid = 0; /* True if an ORDER BY rowid term is seen */ int nEqOneRow; /* Idx columns that ref unique values */ if( p->i==0 ){ nPriorSat = 0; }else{ nPriorSat = p->aLevel[p->i-1].plan.nOBSat; if( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return nPriorSat; } if( p->i==0 || (p->aLevel[p->i-1].plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){ nEqOneRow = nEqCol; }else{ if( nEqCol==0 ) return nPriorSat; sortOrder = bOuterRev; nEqOneRow = 0; } pOrderBy = p->pOrderBy; assert( pOrderBy!=0 ); if( wsFlags & WHERE_COLUMN_IN ) return nPriorSat; if( pIdx->bUnordered ) return nPriorSat; nTerm = pOrderBy->nExpr; assert( nTerm>0 ); /* Argument pIdx must either point to a 'real' named index structure, ** or an index structure allocated on the stack by bestBtreeIndex() to ** represent the rowid index that is part of every table. */ assert( pIdx->zName || (pIdx->nColumn==1 && pIdx->aiColumn[0]==-1) ); /* Match terms of the ORDER BY clause against columns of ** the index. ** ** Note that indices have pIdx->nColumn regular columns plus ** one additional column containing the rowid. The rowid column ** of the index is also allowed to match against the ORDER BY ** clause. */ for(i=0,j=nPriorSat,pTerm=&pOrderBy->a[j]; j<nTerm && i<=pIdx->nColumn; i++){ Expr *pExpr; /* The expression of the ORDER BY pTerm */ CollSeq *pColl; /* The collating sequence of pExpr */ int termSortOrder; /* Sort order for this term */ int iColumn; /* The i-th column of the index. -1 for rowid */ int iSortOrder; /* 1 for DESC, 0 for ASC on the i-th index term */ const char *zColl; /* Name of the collating sequence for i-th index term */ pExpr = pTerm->pExpr; if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){ /* Can not use an index sort on anything that is not a column in the ** left-most table of the FROM clause */ break; } pColl = sqlite3ExprCollSeq(pParse, pExpr); if( !pColl ){ pColl = db->pDfltColl; } if( pIdx->zName && i<pIdx->nColumn ){ iColumn = pIdx->aiColumn[i]; if( iColumn==pIdx->pTable->iPKey ){ iColumn = -1; } iSortOrder = pIdx->aSortOrder[i]; zColl = pIdx->azColl[i]; }else{ iColumn = -1; iSortOrder = 0; zColl = pColl->zName; } if( pExpr->iColumn!=iColumn || sqlite3StrICmp(pColl->zName, zColl) ){ /* Term j of the ORDER BY clause does not match column i of the index */ if( i<nEqCol ){ /* If an index column that is constrained by == fails to match an ** ORDER BY term, that is OK. Just ignore that column of the index */ continue; }else if( i==pIdx->nColumn ){ /* Index column i is the rowid. All other terms match. */ break; }else{ /* If an index column fails to match and is not constrained by == ** then the index cannot satisfy the ORDER BY constraint. */ return nPriorSat; } } assert( pIdx->aSortOrder!=0 || iColumn==-1 ); assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 ); assert( iSortOrder==0 || iSortOrder==1 ); termSortOrder = iSortOrder ^ pTerm->sortOrder; if( i>nEqOneRow ){ if( termSortOrder!=sortOrder ){ /* Indices can only be used if all ORDER BY terms past the ** equality constraints are all either DESC or ASC. */ break; } }else{ sortOrder = termSortOrder; } j++; pTerm++; if( iColumn<0 ){ seenRowid = 1; break; } } *pbRev = sortOrder; /* If there was an "ORDER BY rowid" term that matched, or it is only ** possible for a single row from this table to match, then skip over ** any additional ORDER BY terms dealing with this table. */ if( seenRowid || ( (wsFlags & WHERE_COLUMN_NULL)==0 && i>=pIdx->nColumn && indexIsUniqueNotNull(pIdx, nEqCol) ) ){ /* Advance j over additional ORDER BY terms associated with base */ WhereMaskSet *pMS = p->pWC->pMaskSet; Bitmask m = ~getMask(pMS, base); while( j<nTerm && (exprTableUsage(pMS, pOrderBy->a[j].pExpr)&m)==0 ){ j++; } } return j; } /* ** Find the best query plan for accessing a particular table. Write the ** best query plan and its cost into the p->cost. ** ** The lowest cost plan wins. The cost is an estimate of the amount of ** CPU and disk I/O needed to process the requested result. |
︙ | ︙ | |||
3173 3174 3175 3176 3177 3178 3179 3180 3181 3182 3183 3184 3185 3186 | ** optimized using the index. */ if( nEq==pProbe->nColumn && pProbe->onError!=OE_None ){ testcase( wsFlags & WHERE_COLUMN_IN ); testcase( wsFlags & WHERE_COLUMN_NULL ); if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){ wsFlags |= WHERE_UNIQUE; } }else if( pProbe->bUnordered==0 ){ int j = (nEq==pProbe->nColumn ? -1 : pProbe->aiColumn[nEq]); if( findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){ WhereTerm *pTop, *pBtm; pTop = findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE, pIdx); pBtm = findTerm(pWC, iCur, j, p->notReady, WO_GT|WO_GE, pIdx); | > > > | 3176 3177 3178 3179 3180 3181 3182 3183 3184 3185 3186 3187 3188 3189 3190 3191 3192 | ** optimized using the index. */ if( nEq==pProbe->nColumn && pProbe->onError!=OE_None ){ testcase( wsFlags & WHERE_COLUMN_IN ); testcase( wsFlags & WHERE_COLUMN_NULL ); if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){ wsFlags |= WHERE_UNIQUE; if( p->i==0 || (p->aLevel[p->i-1].plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){ wsFlags |= WHERE_ALL_UNIQUE; } } }else if( pProbe->bUnordered==0 ){ int j = (nEq==pProbe->nColumn ? -1 : pProbe->aiColumn[nEq]); if( findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){ WhereTerm *pTop, *pBtm; pTop = findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE, pIdx); pBtm = findTerm(pWC, iCur, j, p->notReady, WO_GT|WO_GE, pIdx); |
︙ | ︙ |
Added test/orderby2.test.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | # 2012 Sept 27 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this file is testing that the optimizations that disable # ORDER BY clauses when the natural order of a query is correct. # set testdir [file dirname $argv0] source $testdir/tester.tcl set ::testprefix orderby2 # Generate test data for a join. Verify that the join gets the # correct answer. # do_test 1.0 { db eval { CREATE TABLE t1(a INTEGER PRIMARY KEY, b); INSERT INTO t1 VALUES(1,11), (2,22); CREATE TABLE t2(d, e, UNIQUE(d,e)); INSERT INTO t2 VALUES(10, 'ten'), (11,'eleven'), (12,'twelve'), (11, 'oneteen'); } } {} do_test 1.1a { db eval { SELECT e FROM t1, t2 WHERE a=1 AND d=b ORDER BY d, e; } } {eleven oneteen} do_test 1.1b { db eval { EXPLAIN QUERY PLAN SELECT e FROM t1, t2 WHERE a=1 AND d=b ORDER BY d, e; } } {~/ORDER BY/} do_test 1.2a { db eval { SELECT e FROM t1, t2 WHERE a=1 AND d=b ORDER BY e; } } {eleven oneteen} do_test 1.2b { db eval { EXPLAIN QUERY PLAN SELECT e FROM t1, t2 WHERE a=1 AND d=b ORDER BY e; } } {~/ORDER BY/} do_test 1.3a { db eval { SELECT e, b FROM t1, t2 WHERE a=1 ORDER BY d, e; } } {ten 11 eleven 11 oneteen 11 twelve 11} do_test 1.3b { db eval { EXPLAIN QUERY PLAN SELECT e, b FROM t1, t2 WHERE a=1 ORDER BY d, e; } } {~/ORDER BY/} finish_test |