Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Add a new ORDER BY optimization that bypasses ORDER BY terms that are constrained by == and IS NULL terms of the WHERE clause. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | nextgen-query-plan-exp |
Files: | files | file ages | folders |
SHA1: |
b920bb70bb009b7c54e7667544c9810c |
User & Date: | drh 2013-06-14 02:51:48.285 |
Context
2013-06-14
| ||
13:27 | Comment tweaks in where.c. No changes to code. (check-in: cecc5fdd5d user: drh tags: nextgen-query-plan-exp) | |
02:51 | Add a new ORDER BY optimization that bypasses ORDER BY terms that are constrained by == and IS NULL terms of the WHERE clause. (check-in: b920bb70bb user: drh tags: nextgen-query-plan-exp) | |
2013-06-13
| ||
17:58 | An index might be useful for ORDER BY if any indexed column is in the ORDER BY clause, not just the first indexed column. (check-in: ade473b5ae user: drh tags: nextgen-query-plan-exp) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
4887 4888 4889 4890 4891 4892 4893 | Expr *pOBExpr; /* An expression from the ORDER BY clause */ CollSeq *pColl; /* COLLATE function from an ORDER BY clause term */ Index *pIndex; /* The index associated with pLoop */ sqlite3 *db = pWInfo->pParse->db; /* Database connection */ Bitmask obSat = 0; /* Mask of ORDER BY terms satisfied so far */ Bitmask obDone; /* Mask of all ORDER BY terms */ Bitmask orderDistinctMask; /* Mask of all well-ordered loops */ | | | 4887 4888 4889 4890 4891 4892 4893 4894 4895 4896 4897 4898 4899 4900 4901 | Expr *pOBExpr; /* An expression from the ORDER BY clause */ CollSeq *pColl; /* COLLATE function from an ORDER BY clause term */ Index *pIndex; /* The index associated with pLoop */ sqlite3 *db = pWInfo->pParse->db; /* Database connection */ Bitmask obSat = 0; /* Mask of ORDER BY terms satisfied so far */ Bitmask obDone; /* Mask of all ORDER BY terms */ Bitmask orderDistinctMask; /* Mask of all well-ordered loops */ Bitmask ready; /* Mask of inner loops */ /* ** We say the WhereLoop is "one-row" if it generates no more than one ** row of output. A WhereLoop is one-row if all of the following are true: ** (a) All index columns match with WHERE_COLUMN_EQ. ** (b) The index is unique ** Any WhereLoop with an WHERE_COLUMN_EQ constraint on the rowid is one-row. |
︙ | ︙ | |||
4927 4928 4929 4930 4931 4932 4933 4934 4935 4936 4937 4938 4939 4940 4941 4942 4943 4944 | if( nLoop && OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return 0; nOrderBy = pOrderBy->nExpr; if( nOrderBy>BMS-1 ) return 0; /* Cannot optimize overly large ORDER BYs */ isOrderDistinct = 1; obDone = MASKBIT(nOrderBy)-1; orderDistinctMask = 0; for(iLoop=0; isOrderDistinct && obSat<obDone && iLoop<=nLoop; iLoop++){ pLoop = iLoop<nLoop ? pPath->aLoop[iLoop] : pLast; assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 ); iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor; if( (pLoop->wsFlags & WHERE_ONEROW)==0 ){ if( pLoop->wsFlags & WHERE_IPK ){ pIndex = 0; nColumn = 0; }else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){ return 0; }else{ | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 4927 4928 4929 4930 4931 4932 4933 4934 4935 4936 4937 4938 4939 4940 4941 4942 4943 4944 4945 4946 4947 4948 4949 4950 4951 4952 4953 4954 4955 4956 4957 4958 4959 4960 4961 4962 4963 4964 4965 4966 4967 4968 4969 4970 4971 4972 4973 | if( nLoop && OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return 0; nOrderBy = pOrderBy->nExpr; if( nOrderBy>BMS-1 ) return 0; /* Cannot optimize overly large ORDER BYs */ isOrderDistinct = 1; obDone = MASKBIT(nOrderBy)-1; orderDistinctMask = 0; ready = 0; for(iLoop=0; isOrderDistinct && obSat<obDone && iLoop<=nLoop; iLoop++){ if( iLoop>0 ) ready |= pLoop->maskSelf; pLoop = iLoop<nLoop ? pPath->aLoop[iLoop] : pLast; assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 ); iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor; /* Mark off any ORDER BY term X that is a column in the table of ** the current loop for which there is term in the WHERE ** clause of the form X IS NULL or X=? that reference only outer ** loops. */ for(i=0; i<nOrderBy; i++){ if( MASKBIT(i) & obSat ) continue; pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr); if( pOBExpr->op!=TK_COLUMN ) continue; if( pOBExpr->iTable!=iCur ) continue; pTerm = findTerm(&pWInfo->sWC, iCur, pOBExpr->iColumn, ~ready, WO_EQ|WO_ISNULL, 0); if( pTerm==0 ) continue; if( pOBExpr->iColumn>=0 ){ const char *z1, *z2; pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr); if( !pColl ) pColl = db->pDfltColl; z1 = pColl->zName; pColl = sqlite3ExprCollSeq(pWInfo->pParse, pTerm->pExpr); if( !pColl ) pColl = db->pDfltColl; z2 = pColl->zName; if( sqlite3StrICmp(z1, z2)!=0 ) continue; } obSat |= MASKBIT(i); } if( (pLoop->wsFlags & WHERE_ONEROW)==0 ){ if( pLoop->wsFlags & WHERE_IPK ){ pIndex = 0; nColumn = 0; }else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){ return 0; }else{ |
︙ | ︙ | |||
5062 5063 5064 5065 5066 5067 5068 | if( MASKBIT(i) & obSat ) continue; p = pOrderBy->a[i].pExpr; if( (exprTableUsage(&pWInfo->sMaskSet, p)&~orderDistinctMask)==0 ){ obSat |= MASKBIT(i); } } } | | | 5091 5092 5093 5094 5095 5096 5097 5098 5099 5100 5101 5102 5103 5104 5105 | if( MASKBIT(i) & obSat ) continue; p = pOrderBy->a[i].pExpr; if( (exprTableUsage(&pWInfo->sMaskSet, p)&~orderDistinctMask)==0 ){ obSat |= MASKBIT(i); } } } } /* End the loop over all WhereLoops from outer-most down to inner-most */ if( obSat==obDone ) return 1; if( !isOrderDistinct ) return 0; if( isLastLoop ) return 1; return -1; } #ifdef WHERETRACE_ENABLED |
︙ | ︙ |
Added test/orderby5.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 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | # 2013-06-14 # # 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 work correctly # set testdir [file dirname $argv0] source $testdir/tester.tcl set ::testprefix orderby5 # Generate test data for a join. Verify that the join gets the # correct answer. # do_execsql_test 1.1 { CREATE TABLE t1(a,b,c); CREATE INDEX t1bc ON t1(b,c); EXPLAIN QUERY PLAN SELECT DISTINCT a, b, c FROM t1 WHERE a=0; } {~/B-TREE/} do_execsql_test 1.2.1 { EXPLAIN QUERY PLAN SELECT DISTINCT a, c, b FROM t1 WHERE a=0; } {~/B-TREE/} do_execsql_test 1.2.2 { EXPLAIN QUERY PLAN SELECT DISTINCT a, c, b FROM t1 WHERE a='xyz' COLLATE nocase; } {/B-TREE/} do_execsql_test 1.2.3 { EXPLAIN QUERY PLAN SELECT DISTINCT a COLLATE nocase, c, b FROM t1 WHERE a='xyz'; } {/B-TREE/} do_execsql_test 1.2.4 { EXPLAIN QUERY PLAN SELECT DISTINCT a COLLATE nocase, c, b FROM t1 WHERE a='xyz' COLLATE nocase; } {~/B-TREE/} do_execsql_test 1.3 { EXPLAIN QUERY PLAN SELECT DISTINCT b, a, c FROM t1 WHERE a=0; } {~/B-TREE/} do_execsql_test 1.4 { EXPLAIN QUERY PLAN SELECT DISTINCT b, c, a FROM t1 WHERE a=0; } {~/B-TREE/} do_execsql_test 1.5 { EXPLAIN QUERY PLAN SELECT DISTINCT c, a, b FROM t1 WHERE a=0; } {~/B-TREE/} do_execsql_test 1.6 { EXPLAIN QUERY PLAN SELECT DISTINCT c, b, a FROM t1 WHERE a=0; } {~/B-TREE/} do_execsql_test 1.7 { EXPLAIN QUERY PLAN SELECT DISTINCT c, b, a FROM t1 WHERE +a=0; } {/B-TREE/} do_execsql_test 2.1 { EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=0 ORDER BY a, b, c; } {~/B-TREE/} do_execsql_test 2.2 { EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE +a=0 ORDER BY a, b, c; } {/B-TREE/} do_execsql_test 2.3 { EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=0 ORDER BY b, a, c; } {~/B-TREE/} do_execsql_test 2.4 { EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=0 ORDER BY b, c, a; } {~/B-TREE/} do_execsql_test 2.5 { EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=0 ORDER BY a, c, b; } {/B-TREE/} do_execsql_test 2.6 { EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=0 ORDER BY c, a, b; } {/B-TREE/} do_execsql_test 2.7 { EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=0 ORDER BY c, b, a; } {/B-TREE/} finish_test |