Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Query planner enhancements to be more agressive about optimizing out ORDER BY clauses - in particular the query planner now has the ability to omit ORDER BY clauses that span multiple tables in a join. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
1e874629d7cf568368b912b295bd3001 |
User & Date: | drh 2012-09-28 00:44:28.903 |
References
2013-06-03
| ||
13:23 | • New ticket [bc1aea7b72] Incorrect result on LEFT JOIN with OR constraints and an ORDER BY clause. (artifact: a92b978f85 user: drh) | |
2013-04-22
| ||
18:16 | • New ticket [ba82a4a41e] Query optimizer removes ORDER BY when it is needed. (artifact: 393965027d user: drh) | |
Context
2012-09-28
| ||
18:13 | Modify the clearCell function to use SQLITE_CORRUPT_BKPT in the one place it was not. (check-in: 472beb306a user: mistachkin tags: trunk) | |
13:05 | Merge the latest trunk changes (especially "PRAGMA busy_timeout" and the ORDER BY query planner optimizations) into the sessions branch. (check-in: 6ca8eae1f8 user: drh tags: sessions) | |
10:57 | Merge the latest trunk changes (PRAGMA busy_timeout and the ORDER BY query planner enhancements) into the apple-osx branch. (check-in: 6a5c59dd7e user: drh tags: apple-osx) | |
00:44 | Query planner enhancements to be more agressive about optimizing out ORDER BY clauses - in particular the query planner now has the ability to omit ORDER BY clauses that span multiple tables in a join. (check-in: 1e874629d7 user: drh tags: trunk) | |
2012-09-27
| ||
23:27 | Fix some corner case behavior in the new ORDER BY optimization logic. Remove the SQLITE_OrderByIdx bit from the SQLITE_TESTCTRL_OPTIMIZATIONS mask, since enabling it caused many TH3 tests to fail when the NO_OPT configuration parameter was engaged, and since there really isn't any need to turn that optimization off. The SQLITE_OrderByIdxJoin bit remains. (Closed-Leaf check-in: 98b633717a user: drh tags: qp-enhancements) | |
21:03 | Modify generation of resource header file for MSVC so that it can work from outside the working directory. (check-in: 20caf80cb3 user: mistachkin tags: trunk) | |
Changes
Changes to src/delete.c.
︙ | ︙ | |||
634 635 636 637 638 639 640 | }else{ sqlite3VdbeAddOp3(v, OP_Column, iCur, idx, regBase+j); sqlite3ColumnDefault(v, pTab, idx, -1); } } if( doMakeRec ){ const char *zAff; | | > > | 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 | }else{ sqlite3VdbeAddOp3(v, OP_Column, iCur, idx, regBase+j); sqlite3ColumnDefault(v, pTab, idx, -1); } } if( doMakeRec ){ const char *zAff; if( pTab->pSelect || OptimizationDisabled(pParse->db, SQLITE_IdxRealAsInt) ){ zAff = 0; }else{ zAff = sqlite3IndexAffinityStr(v, pIdx); } sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nCol+1, regOut); sqlite3VdbeChangeP4(v, -1, zAff, P4_TRANSIENT); } |
︙ | ︙ |
Changes to src/expr.c.
︙ | ︙ | |||
2062 2063 2064 2065 2066 2067 2068 | assert( iReg>0 ); /* Register numbers are always positive */ assert( iCol>=-1 && iCol<32768 ); /* Finite column numbers */ /* The SQLITE_ColumnCache flag disables the column cache. This is used ** for testing only - to verify that SQLite always gets the same answer ** with and without the column cache. */ | | | 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 | assert( iReg>0 ); /* Register numbers are always positive */ assert( iCol>=-1 && iCol<32768 ); /* Finite column numbers */ /* The SQLITE_ColumnCache flag disables the column cache. This is used ** for testing only - to verify that SQLite always gets the same answer ** with and without the column cache. */ if( OptimizationDisabled(pParse->db, SQLITE_ColumnCache) ) return; /* First replace any existing entry. ** ** Actually, the way the column cache is currently used, we are guaranteed ** that the object will never already be in cache. Verify this guarantee. */ #ifndef NDEBUG |
︙ | ︙ | |||
3378 3379 3380 3381 3382 3383 3384 | ** interface. This allows test logic to verify that the same answer is ** obtained for queries regardless of whether or not constants are ** precomputed into registers or if they are inserted in-line. */ void sqlite3ExprCodeConstants(Parse *pParse, Expr *pExpr){ Walker w; if( pParse->cookieGoto ) return; | | | 3378 3379 3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 | ** interface. This allows test logic to verify that the same answer is ** obtained for queries regardless of whether or not constants are ** precomputed into registers or if they are inserted in-line. */ void sqlite3ExprCodeConstants(Parse *pParse, Expr *pExpr){ Walker w; if( pParse->cookieGoto ) return; if( OptimizationDisabled(pParse->db, SQLITE_FactorOutConst) ) return; w.xExprCallback = evalConstExpr; w.xSelectCallback = 0; w.pParse = pParse; sqlite3WalkExpr(&w, pExpr); } |
︙ | ︙ |
Changes to src/main.c.
︙ | ︙ | |||
3015 3016 3017 3018 3019 3020 3021 | ** operation N should be 0. The idea is that a test program (like the ** SQL Logic Test or SLT test module) can run the same SQL multiple times ** with various optimizations disabled to verify that the same answer ** is obtained in every case. */ case SQLITE_TESTCTRL_OPTIMIZATIONS: { sqlite3 *db = va_arg(ap, sqlite3*); | | < | 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 | ** operation N should be 0. The idea is that a test program (like the ** SQL Logic Test or SLT test module) can run the same SQL multiple times ** with various optimizations disabled to verify that the same answer ** is obtained in every case. */ case SQLITE_TESTCTRL_OPTIMIZATIONS: { sqlite3 *db = va_arg(ap, sqlite3*); db->dbOptFlags = (u16)(va_arg(ap, int) & 0xffff); break; } #ifdef SQLITE_N_KEYWORD /* sqlite3_test_control(SQLITE_TESTCTRL_ISKEYWORD, const char *zWord) ** ** If zWord is a keyword recognized by the parser, then return the |
︙ | ︙ |
Changes to src/select.c.
︙ | ︙ | |||
2805 2806 2807 2808 2809 2810 2811 | struct SrcList_item *pSubitem; /* The subquery */ sqlite3 *db = pParse->db; /* Check to see if flattening is permitted. Return 0 if not. */ assert( p!=0 ); assert( p->pPrior==0 ); /* Unable to flatten compound queries */ | | | 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819 | struct SrcList_item *pSubitem; /* The subquery */ sqlite3 *db = pParse->db; /* Check to see if flattening is permitted. Return 0 if not. */ assert( p!=0 ); assert( p->pPrior==0 ); /* Unable to flatten compound queries */ if( OptimizationDisabled(db, SQLITE_QueryFlattener) ) return 0; pSrc = p->pSrc; assert( pSrc && iFrom>=0 && iFrom<pSrc->nSrc ); pSubitem = &pSrc->a[iFrom]; iParent = pSubitem->iCursor; pSub = pSubitem->pSelect; assert( pSub!=0 ); if( isAgg && subqueryIsAgg ) return 0; /* Restriction (1) */ |
︙ | ︙ | |||
4008 4009 4010 4011 4012 4013 4014 | ** identical, then disable the ORDER BY clause since the GROUP BY ** will cause elements to come out in the correct order. This is ** an optimization - the correct answer should result regardless. ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER ** to disable this optimization for testing purposes. */ if( sqlite3ExprListCompare(p->pGroupBy, pOrderBy)==0 | | | 4008 4009 4010 4011 4012 4013 4014 4015 4016 4017 4018 4019 4020 4021 4022 | ** identical, then disable the ORDER BY clause since the GROUP BY ** will cause elements to come out in the correct order. This is ** an optimization - the correct answer should result regardless. ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER ** to disable this optimization for testing purposes. */ if( sqlite3ExprListCompare(p->pGroupBy, pOrderBy)==0 && OptimizationEnabled(db, SQLITE_GroupByOrder) ){ pOrderBy = 0; } /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and ** if the select-list is the same as the ORDER BY list, then this query ** can be rewritten as a GROUP BY. In other words, this: ** |
︙ | ︙ | |||
4502 4503 4504 4505 4506 4507 4508 4509 4510 4511 4512 4513 4514 4515 | resetAccumulator(pParse, &sAggInfo); pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pMinMax,0,flag,0); if( pWInfo==0 ){ sqlite3ExprListDelete(db, pDel); goto select_end; } updateAccumulator(pParse, &sAggInfo); if( pWInfo->nOBSat>0 ){ sqlite3VdbeAddOp2(v, OP_Goto, 0, pWInfo->iBreak); VdbeComment((v, "%s() by index", (flag==WHERE_ORDERBY_MIN?"min":"max"))); } sqlite3WhereEnd(pWInfo); finalizeAggFunctions(pParse, &sAggInfo); | > | 4502 4503 4504 4505 4506 4507 4508 4509 4510 4511 4512 4513 4514 4515 4516 | resetAccumulator(pParse, &sAggInfo); pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pMinMax,0,flag,0); if( pWInfo==0 ){ sqlite3ExprListDelete(db, pDel); goto select_end; } updateAccumulator(pParse, &sAggInfo); assert( pMinMax==0 || pMinMax->nExpr==1 ); if( pWInfo->nOBSat>0 ){ sqlite3VdbeAddOp2(v, OP_Goto, 0, pWInfo->iBreak); VdbeComment((v, "%s() by index", (flag==WHERE_ORDERBY_MIN?"min":"max"))); } sqlite3WhereEnd(pWInfo); finalizeAggFunctions(pParse, &sAggInfo); |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
823 824 825 826 827 828 829 830 831 832 833 834 835 836 | Db *aDb; /* All backends */ int nDb; /* Number of backends currently in use */ int flags; /* Miscellaneous flags. See below */ i64 lastRowid; /* ROWID of most recent insert (see above) */ unsigned int openFlags; /* Flags passed to sqlite3_vfs.xOpen() */ int errCode; /* Most recent error code (SQLITE_*) */ int errMask; /* & result codes with this before returning */ u8 autoCommit; /* The auto-commit flag. */ u8 temp_store; /* 1: file 2: memory 0: default */ u8 mallocFailed; /* True if we have seen a malloc failure */ u8 dfltLockMode; /* Default locking-mode for attached dbs */ signed char nextAutovac; /* Autovac setting after VACUUM if >=0 */ u8 suppressErr; /* Do not issue error messages if true */ u8 vtabOnConflict; /* Value to return for s3_vtab_on_conflict() */ | > | 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 | Db *aDb; /* All backends */ int nDb; /* Number of backends currently in use */ int flags; /* Miscellaneous flags. See below */ i64 lastRowid; /* ROWID of most recent insert (see above) */ unsigned int openFlags; /* Flags passed to sqlite3_vfs.xOpen() */ int errCode; /* Most recent error code (SQLITE_*) */ int errMask; /* & result codes with this before returning */ u8 dbOptFlags; /* Flags to enable/disable optimizations */ u8 autoCommit; /* The auto-commit flag. */ u8 temp_store; /* 1: file 2: memory 0: default */ u8 mallocFailed; /* True if we have seen a malloc failure */ u8 dfltLockMode; /* Default locking-mode for attached dbs */ signed char nextAutovac; /* Autovac setting after VACUUM if >=0 */ u8 suppressErr; /* Do not issue error messages if true */ u8 vtabOnConflict; /* Value to return for s3_vtab_on_conflict() */ |
︙ | ︙ | |||
927 928 929 930 931 932 933 | ** A macro to discover the encoding of a database. */ #define ENC(db) ((db)->aDb[0].pSchema->enc) /* ** Possible values for the sqlite3.flags. */ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | > > | > > > > > > > > > > | 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 | ** A macro to discover the encoding of a database. */ #define ENC(db) ((db)->aDb[0].pSchema->enc) /* ** Possible values for the sqlite3.flags. */ #define SQLITE_VdbeTrace 0x00000001 /* True to trace VDBE execution */ #define SQLITE_InternChanges 0x00000002 /* Uncommitted Hash table changes */ #define SQLITE_FullColNames 0x00000004 /* Show full column names on SELECT */ #define SQLITE_ShortColNames 0x00000008 /* Show short columns names */ #define SQLITE_CountRows 0x00000010 /* Count rows changed by INSERT, */ /* DELETE, or UPDATE and return */ /* the count using a callback. */ #define SQLITE_NullCallback 0x00000020 /* Invoke the callback once if the */ /* result set is empty */ #define SQLITE_SqlTrace 0x00000040 /* Debug print SQL as it executes */ #define SQLITE_VdbeListing 0x00000080 /* Debug listings of VDBE programs */ #define SQLITE_WriteSchema 0x00000100 /* OK to update SQLITE_MASTER */ /* 0x00000200 Unused */ #define SQLITE_IgnoreChecks 0x00000400 /* Do not enforce check constraints */ #define SQLITE_ReadUncommitted 0x0000800 /* For shared-cache mode */ #define SQLITE_LegacyFileFmt 0x00001000 /* Create new databases in format 1 */ #define SQLITE_FullFSync 0x00002000 /* Use full fsync on the backend */ #define SQLITE_CkptFullFSync 0x00004000 /* Use full fsync for checkpoint */ #define SQLITE_RecoveryMode 0x00008000 /* Ignore schema errors */ #define SQLITE_ReverseOrder 0x00010000 /* Reverse unordered SELECTs */ #define SQLITE_RecTriggers 0x00020000 /* Enable recursive triggers */ #define SQLITE_ForeignKeys 0x00040000 /* Enforce foreign key constraints */ #define SQLITE_AutoIndex 0x00080000 /* Enable automatic indexes */ #define SQLITE_PreferBuiltin 0x00100000 /* Preference to built-in funcs */ #define SQLITE_LoadExtension 0x00200000 /* Enable load_extension */ #define SQLITE_EnableTrigger 0x00400000 /* True to enable triggers */ /* ** Bits of the sqlite3.dbOptFlags field that are used by the ** sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS,...) interface to ** selectively disable various optimizations. */ #define SQLITE_QueryFlattener 0x0001 /* Query flattening */ #define SQLITE_ColumnCache 0x0002 /* Column cache */ #define SQLITE_GroupByOrder 0x0004 /* GROUPBY cover of ORDERBY */ #define SQLITE_FactorOutConst 0x0008 /* Constant factoring */ #define SQLITE_IdxRealAsInt 0x0010 /* Store REAL as INT in indices */ #define SQLITE_DistinctOpt 0x0020 /* DISTINCT using indexes */ #define SQLITE_CoverIdxScan 0x0040 /* Covering index scans */ #define SQLITE_OrderByIdxJoin 0x0080 /* ORDER BY of joins via index */ #define SQLITE_AllOpts 0x00ff /* All optimizations */ /* ** Macros for testing whether or not optimizations are enabled or disabled. */ #ifndef SQLITE_OMIT_BUILTIN_TEST #define OptimizationDisabled(db, mask) (((db)->dbOptFlags&(mask))!=0) #define OptimizationEnabled(db, mask) (((db)->dbOptFlags&(mask))==0) #else #define OptimizationDisabled(db, mask) 0 #define OptimizationEnabled(db, mask) 1 #endif /* ** Possible values for the sqlite.magic field. ** The numbers are obtained at random and have no special meaning, other ** than being distinct from one another. */ #define SQLITE_MAGIC_OPEN 0xa029a697 /* Database is open */ |
︙ | ︙ | |||
1902 1903 1904 1905 1906 1907 1908 | ** Within the union, pIdx is only used when wsFlags&WHERE_INDEXED is true. ** pTerm is only used when wsFlags&WHERE_MULTI_OR is true. And pVtabIdx ** is only used when wsFlags&WHERE_VIRTUALTABLE is true. It is never the ** case that more than one of these conditions is true. */ struct WherePlan { u32 wsFlags; /* WHERE_* flags that describe the strategy */ | | > | 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 | ** Within the union, pIdx is only used when wsFlags&WHERE_INDEXED is true. ** pTerm is only used when wsFlags&WHERE_MULTI_OR is true. And pVtabIdx ** is only used when wsFlags&WHERE_VIRTUALTABLE is true. It is never the ** case that more than one of these conditions is true. */ struct WherePlan { u32 wsFlags; /* WHERE_* flags that describe the strategy */ u16 nEq; /* Number of == constraints */ u16 nOBSat; /* Number of ORDER BY terms satisfied */ double nRow; /* Estimated number of rows (for EQP) */ union { Index *pIdx; /* Index when WHERE_INDEXED is true */ struct WhereTerm *pTerm; /* WHERE clause term for OR-search */ sqlite3_index_info *pVtabIdx; /* Virtual table index to use */ } u; }; |
︙ | ︙ |
Changes to src/test1.c.
︙ | ︙ | |||
5929 5930 5931 5932 5933 5934 5935 | const char *zOpt; int onoff; int mask = 0; static const struct { const char *zOptName; int mask; } aOpt[] = { | | > | 5929 5930 5931 5932 5933 5934 5935 5936 5937 5938 5939 5940 5941 5942 5943 5944 5945 5946 5947 5948 5949 5950 5951 | const char *zOpt; int onoff; int mask = 0; static const struct { const char *zOptName; int mask; } aOpt[] = { { "all", SQLITE_AllOpts }, { "query-flattener", SQLITE_QueryFlattener }, { "column-cache", SQLITE_ColumnCache }, { "groupby-order", SQLITE_GroupByOrder }, { "factor-constants", SQLITE_FactorOutConst }, { "real-as-int", SQLITE_IdxRealAsInt }, { "distinct-opt", SQLITE_DistinctOpt }, { "cover-idx-scan", SQLITE_CoverIdxScan }, { "order-by-idx-join",SQLITE_OrderByIdxJoin }, }; if( objc!=4 ){ Tcl_WrongNumArgs(interp, 1, objv, "DB OPT BOOLEAN"); return TCL_ERROR; } if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR; |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
263 264 265 266 267 268 269 270 271 272 273 274 275 276 | #define WHERE_UNIQUE 0x04000000 /* Selects no more than 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 */ /* ** Initialize a preallocated WhereClause structure. */ static void whereClauseInit( WhereClause *pWC, /* The WhereClause to be initialized */ Parse *pParse, /* The parsing context */ WhereMaskSet *pMaskSet, /* Mapping from table cursor numbers to bitmasks */ | > > > > > > > > > > > > > > > > > > > > > > | 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 | #define WHERE_UNIQUE 0x04000000 /* Selects no more than 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 */ /* ** This module contains many separate subroutines that work together to ** find the best indices to use for accessing a particular table in a query. ** An instance of the following structure holds context information about the ** index search so that it can be more easily passed between the various ** routines. */ typedef struct WhereBestIdx WhereBestIdx; struct WhereBestIdx { Parse *pParse; /* Parser context */ WhereClause *pWC; /* The WHERE clause */ struct SrcList_item *pSrc; /* The FROM clause term to search */ Bitmask notReady; /* Mask of cursors not available */ Bitmask notValid; /* Cursors not available for any purpose */ ExprList *pOrderBy; /* The ORDER BY clause */ ExprList *pDistinct; /* The select-list if query is DISTINCT */ sqlite3_index_info **ppIdxInfo; /* Index information passed to xBestIndex */ int i, n; /* Which loop is being coded; # of loops */ WhereLevel *aLevel; /* Info about outer loops */ WhereCost cost; /* Lowest cost query plan */ }; /* ** Initialize a preallocated WhereClause structure. */ static void whereClauseInit( WhereClause *pWC, /* The WhereClause to be initialized */ Parse *pParse, /* The parsing context */ WhereMaskSet *pMaskSet, /* Mapping from table cursor numbers to bitmasks */ |
︙ | ︙ | |||
1405 1406 1407 1408 1409 1410 1411 | /* 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; } /* | | | | | < < | > | < < < > | | < | | 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 | /* 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]; if( j>=0 && 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 |
︙ | ︙ | |||
1586 1587 1588 1589 1590 1591 1592 | } return 0; } /* ** This routine decides if pIdx can be used to satisfy the ORDER BY | | | > < < | > | > > > > | < < | < < > | < | | < | | > | > | | | | > > | > > > > > > > > > > > > > > | | | < | | 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 | } 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; nEqOneRow = nEqCol; }else{ if( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return 0; nPriorSat = p->aLevel[p->i-1].plan.nOBSat; sortOrder = bOuterRev; nEqOneRow = 0; } if( p->i>0 && nEqCol==0 /*&& !allOuterLoopsUnique(p)*/ ) return nPriorSat; pOrderBy = p->pOrderBy; if( !pOrderBy ) return nPriorSat; 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 */ |
︙ | ︙ | |||
1683 1684 1685 1686 1687 1688 1689 | }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. */ | | | | | < < < < < < | > < | < < < < | > > > > | | < < | > | > | < < < < < < < < < < > > > | < < | | 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 | }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; } /* ** 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 |
︙ | ︙ | |||
1807 1808 1809 1810 1811 1812 1813 | #define TRACE_IDX_INPUTS(A) #define TRACE_IDX_OUTPUTS(A) #endif /* ** Required because bestIndex() is called by bestOrClauseIndex() */ | | < < | < < < < < < < < > > | | | > > > > > < | | > | | | | | | | | | | | | | 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 | #define TRACE_IDX_INPUTS(A) #define TRACE_IDX_OUTPUTS(A) #endif /* ** Required because bestIndex() is called by bestOrClauseIndex() */ static void bestIndex(WhereBestIdx*); /* ** This routine attempts to find an scanning strategy that can be used ** to optimize an 'OR' expression that is part of a WHERE clause. ** ** The table associated with FROM clause term pSrc may be either a ** regular B-Tree table or a virtual table. */ static void bestOrClauseIndex(WhereBestIdx *p){ #ifndef SQLITE_OMIT_OR_OPTIMIZATION WhereClause *pWC = p->pWC; /* The WHERE clause */ struct SrcList_item *pSrc = p->pSrc; /* The FROM clause term to search */ const int iCur = pSrc->iCursor; /* The cursor of the table */ const Bitmask maskSrc = getMask(pWC->pMaskSet, iCur); /* Bitmask for pSrc */ WhereTerm * const pWCEnd = &pWC->a[pWC->nTerm]; /* End of pWC->a[] */ WhereTerm *pTerm; /* A single term of the WHERE clause */ /* The OR-clause optimization is disallowed if the INDEXED BY or ** NOT INDEXED clauses are used or if the WHERE_AND_ONLY bit is set. */ if( pSrc->notIndexed || pSrc->pIndex!=0 ){ return; } if( pWC->wctrlFlags & WHERE_AND_ONLY ){ return; } /* Search the WHERE clause terms for a usable WO_OR term. */ for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){ if( pTerm->eOperator==WO_OR && ((pTerm->prereqAll & ~maskSrc) & p->notReady)==0 && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 ){ WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc; WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm]; WhereTerm *pOrTerm; int flags = WHERE_MULTI_OR; double rTotal = 0; double nRow = 0; Bitmask used = 0; WhereBestIdx sBOI; sBOI = *p; sBOI.pOrderBy = 0; sBOI.pDistinct = 0; sBOI.ppIdxInfo = 0; for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){ WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", (pOrTerm - pOrWC->a), (pTerm - pWC->a) )); if( pOrTerm->eOperator==WO_AND ){ sBOI.pWC = &pOrTerm->u.pAndInfo->wc; bestIndex(&sBOI); }else if( pOrTerm->leftCursor==iCur ){ WhereClause tempWC; tempWC.pParse = pWC->pParse; tempWC.pMaskSet = pWC->pMaskSet; tempWC.pOuter = pWC; tempWC.op = TK_AND; tempWC.a = pOrTerm; tempWC.wctrlFlags = 0; tempWC.nTerm = 1; sBOI.pWC = &tempWC; bestIndex(&sBOI); }else{ continue; } rTotal += sBOI.cost.rCost; nRow += sBOI.cost.plan.nRow; used |= sBOI.cost.used; if( rTotal>=p->cost.rCost ) break; } /* If there is an ORDER BY clause, increase the scan cost to account ** for the cost of the sort. */ if( p->pOrderBy!=0 ){ WHERETRACE(("... sorting increases OR cost %.9g to %.9g\n", rTotal, rTotal+nRow*estLog(nRow))); rTotal += nRow*estLog(nRow); } /* If the cost of scanning using this OR term for optimization is ** less than the current cost stored in pCost, replace the contents ** of pCost. */ WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow)); if( rTotal<p->cost.rCost ){ p->cost.rCost = rTotal; p->cost.used = used; p->cost.plan.nRow = nRow; p->cost.plan.wsFlags = flags; p->cost.plan.u.pTerm = pTerm; } } } #endif /* SQLITE_OMIT_OR_OPTIMIZATION */ } #ifndef SQLITE_OMIT_AUTOMATIC_INDEX |
︙ | ︙ | |||
1937 1938 1939 1940 1941 1942 1943 | ** If the query plan for pSrc specified in pCost is a full table scan ** and indexing is allows (if there is no NOT INDEXED clause) and it ** possible to construct a transient index that would perform better ** than a full table scan even when the cost of constructing the index ** is taken into account, then alter the query plan to use the ** transient index. */ | | | | | < < < | | | | | | | | | | | | 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 | ** If the query plan for pSrc specified in pCost is a full table scan ** and indexing is allows (if there is no NOT INDEXED clause) and it ** possible to construct a transient index that would perform better ** than a full table scan even when the cost of constructing the index ** is taken into account, then alter the query plan to use the ** transient index. */ static void bestAutomaticIndex(WhereBestIdx *p){ Parse *pParse = p->pParse; /* The parsing context */ WhereClause *pWC = p->pWC; /* The WHERE clause */ struct SrcList_item *pSrc = p->pSrc; /* The FROM clause term to search */ double nTableRow; /* Rows in the input table */ double logN; /* log(nTableRow) */ double costTempIdx; /* per-query cost of the transient index */ WhereTerm *pTerm; /* A single term of the WHERE clause */ WhereTerm *pWCEnd; /* End of pWC->a[] */ Table *pTable; /* Table tht might be indexed */ if( pParse->nQueryLoop<=(double)1 ){ /* There is no point in building an automatic index for a single scan */ return; } if( (pParse->db->flags & SQLITE_AutoIndex)==0 ){ /* Automatic indices are disabled at run-time */ return; } if( (p->cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0 ){ /* We already have some kind of index in use for this query. */ return; } if( pSrc->notIndexed ){ /* The NOT INDEXED clause appears in the SQL. */ return; } if( pSrc->isCorrelated ){ /* The source is a correlated sub-query. No point in indexing it. */ return; } assert( pParse->nQueryLoop >= (double)1 ); pTable = pSrc->pTab; nTableRow = pTable->nRowEst; logN = estLog(nTableRow); costTempIdx = 2*logN*(nTableRow/pParse->nQueryLoop + 1); if( costTempIdx>=p->cost.rCost ){ /* The cost of creating the transient table would be greater than ** doing the full table scan */ return; } /* Search for any equality comparison term */ pWCEnd = &pWC->a[pWC->nTerm]; for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){ if( termCanDriveIndex(pTerm, pSrc, p->notReady) ){ WHERETRACE(("auto-index reduces cost from %.1f to %.1f\n", p->cost.rCost, costTempIdx)); p->cost.rCost = costTempIdx; p->cost.plan.nRow = logN + 1; p->cost.plan.wsFlags = WHERE_TEMP_INDEX; p->cost.used = pTerm->prereqRight; break; } } } #else # define bestAutomaticIndex(A) /* no-op */ #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */ #ifndef SQLITE_OMIT_AUTOMATIC_INDEX /* ** Generate code to construct the Index object for an automatic index ** and to set up the WhereLevel object pLevel so that the code generator |
︙ | ︙ | |||
2159 2160 2161 2162 2163 2164 2165 | #ifndef SQLITE_OMIT_VIRTUALTABLE /* ** Allocate and populate an sqlite3_index_info structure. It is the ** responsibility of the caller to eventually release the structure ** by passing the pointer returned by this function to sqlite3_free(). */ | | | | | | < | 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 | #ifndef SQLITE_OMIT_VIRTUALTABLE /* ** Allocate and populate an sqlite3_index_info structure. It is the ** responsibility of the caller to eventually release the structure ** by passing the pointer returned by this function to sqlite3_free(). */ static sqlite3_index_info *allocateIndexInfo(WhereBestIdx *p){ Parse *pParse = p->pParse; WhereClause *pWC = p->pWC; struct SrcList_item *pSrc = p->pSrc; ExprList *pOrderBy = p->pOrderBy; int i, j; int nTerm; struct sqlite3_index_constraint *pIdxCons; struct sqlite3_index_orderby *pIdxOrderBy; struct sqlite3_index_constraint_usage *pUsage; WhereTerm *pTerm; int nOrderBy; |
︙ | ︙ | |||
2194 2195 2196 2197 2198 2199 2200 | /* If the ORDER BY clause contains only columns in the current ** virtual table then allocate space for the aOrderBy part of ** the sqlite3_index_info structure. */ nOrderBy = 0; if( pOrderBy ){ | > | | | | 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 | /* If the ORDER BY clause contains only columns in the current ** virtual table then allocate space for the aOrderBy part of ** the sqlite3_index_info structure. */ nOrderBy = 0; if( pOrderBy ){ int n = pOrderBy->nExpr; for(i=0; i<n; i++){ Expr *pExpr = pOrderBy->a[i].pExpr; if( pExpr->op!=TK_COLUMN || pExpr->iTable!=pSrc->iCursor ) break; } if( i==n){ nOrderBy = n; } } /* Allocate the sqlite3_index_info structure */ pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo) + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm |
︙ | ︙ | |||
2323 2324 2325 2326 2327 2328 2329 | ** same virtual table. The sqlite3_index_info structure is created ** and initialized on the first invocation and reused on all subsequent ** invocations. The sqlite3_index_info structure is also used when ** code is generated to access the virtual table. The whereInfoDelete() ** routine takes care of freeing the sqlite3_index_info structure after ** everybody has finished with it. */ | | | | | < < < < < < | | | | | 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 | ** same virtual table. The sqlite3_index_info structure is created ** and initialized on the first invocation and reused on all subsequent ** invocations. The sqlite3_index_info structure is also used when ** code is generated to access the virtual table. The whereInfoDelete() ** routine takes care of freeing the sqlite3_index_info structure after ** everybody has finished with it. */ static void bestVirtualIndex(WhereBestIdx *p){ Parse *pParse = p->pParse; /* The parsing context */ WhereClause *pWC = p->pWC; /* The WHERE clause */ struct SrcList_item *pSrc = p->pSrc; /* The FROM clause term to search */ Table *pTab = pSrc->pTab; sqlite3_index_info *pIdxInfo; struct sqlite3_index_constraint *pIdxCons; struct sqlite3_index_constraint_usage *pUsage; WhereTerm *pTerm; int i, j; int nOrderBy; double rCost; /* Make sure wsFlags is initialized to some sane value. Otherwise, if the ** malloc in allocateIndexInfo() fails and this function returns leaving ** wsFlags in an uninitialized state, the caller may behave unpredictably. */ memset(&p->cost, 0, sizeof(p->cost)); p->cost.plan.wsFlags = WHERE_VIRTUALTABLE; /* If the sqlite3_index_info structure has not been previously ** allocated and initialized, then allocate and initialize it now. */ pIdxInfo = *p->ppIdxInfo; if( pIdxInfo==0 ){ *p->ppIdxInfo = pIdxInfo = allocateIndexInfo(p); } if( pIdxInfo==0 ){ return; } /* At this point, the sqlite3_index_info structure that pIdxInfo points ** to will have been initialized, either during the current invocation or |
︙ | ︙ | |||
2399 2400 2401 2402 2403 2404 2405 | ** each time. */ pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint; pUsage = pIdxInfo->aConstraintUsage; for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){ j = pIdxCons->iTermOffset; pTerm = &pWC->a[j]; | | | | | | | | | | | | 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 | ** each time. */ pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint; pUsage = pIdxInfo->aConstraintUsage; for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){ j = pIdxCons->iTermOffset; pTerm = &pWC->a[j]; pIdxCons->usable = (pTerm->prereqRight&p->notReady) ? 0 : 1; } memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint); if( pIdxInfo->needToFreeIdxStr ){ sqlite3_free(pIdxInfo->idxStr); } pIdxInfo->idxStr = 0; pIdxInfo->idxNum = 0; pIdxInfo->needToFreeIdxStr = 0; pIdxInfo->orderByConsumed = 0; /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */ pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2); nOrderBy = pIdxInfo->nOrderBy; if( !p->pOrderBy ){ pIdxInfo->nOrderBy = 0; } if( vtabBestIndex(pParse, pTab, pIdxInfo) ){ return; } pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint; for(i=0; i<pIdxInfo->nConstraint; i++){ if( pUsage[i].argvIndex>0 ){ p->cost.used |= pWC->a[pIdxCons[i].iTermOffset].prereqRight; } } /* If there is an ORDER BY clause, and the selected virtual table index ** does not satisfy it, increase the cost of the scan accordingly. This ** matches the processing for non-virtual tables in bestBtreeIndex(). */ rCost = pIdxInfo->estimatedCost; if( p->pOrderBy && pIdxInfo->orderByConsumed==0 ){ rCost += estLog(rCost)*rCost; } /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the ** inital value of lowestCost in this loop. If it is, then the ** (cost<lowestCost) test below will never be true. ** ** Use "(double)2" instead of "2.0" in case OMIT_FLOATING_POINT ** is defined. */ if( (SQLITE_BIG_DBL/((double)2))<rCost ){ p->cost.rCost = (SQLITE_BIG_DBL/((double)2)); }else{ p->cost.rCost = rCost; } p->cost.plan.u.pVtabIdx = pIdxInfo; if( pIdxInfo->orderByConsumed ){ p->cost.plan.wsFlags |= WHERE_ORDERBY; } p->cost.plan.nEq = 0; pIdxInfo->nOrderBy = nOrderBy; /* Try to find a more efficient access pattern by using multiple indexes ** to optimize an OR expression within the WHERE clause. */ bestOrClauseIndex(p); } #endif /* SQLITE_OMIT_VIRTUALTABLE */ #ifdef SQLITE_ENABLE_STAT3 /* ** Estimate the location of a particular key among all keys in an ** index. Store the results in aStat as follows: |
︙ | ︙ | |||
2857 2858 2859 2860 2861 2862 2863 | *pnRow = nRowEst; WHERETRACE(("IN row estimate: est=%g\n", nRowEst)); } return rc; } #endif /* defined(SQLITE_ENABLE_STAT3) */ | > > > > > > > > > > > > > > > > > > > > > > > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | < | 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 2955 | *pnRow = nRowEst; WHERETRACE(("IN row estimate: est=%g\n", nRowEst)); } return rc; } #endif /* defined(SQLITE_ENABLE_STAT3) */ /* ** Check to see if column iCol of the table with cursor iTab will appear ** in sorted order according to the current query plan. Return true if ** it will and false if not. ** ** If *pbRev is initially 2 (meaning "unknown") then set *pbRev to the ** sort order of iTab.iCol. If *pbRev is 0 or 1 but does not match ** the sort order of iTab.iCol, then consider the column to be unordered. */ 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++){ if( iCol==pIdx->aiColumn[j] ) break; } if( j>=pIdx->nColumn ) return 0; sortOrder = pIdx->aSortOrder[j]; testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 ); } }else{ if( iCol!=(-1) ) return 0; sortOrder = 0; testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 ); } if( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 ){ assert( sortOrder==0 || sortOrder==1 ); testcase( sortOrder==1 ); sortOrder = 1 - sortOrder; } if( *pbRev==2 ){ *pbRev = sortOrder; return 1; } 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( p->i==0 ){ return 1; /* All == are ordered in the outer loop */ } 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; } /* ** 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. ** Factors that influence cost include: ** ** * The estimated number of rows that will be retrieved. (The ** fewer the better.) |
︙ | ︙ | |||
2886 2887 2888 2889 2890 2891 2892 | ** then the cost is calculated in the usual way. ** ** If a NOT INDEXED clause (pSrc->notIndexed!=0) was attached to the table ** in the SELECT statement, then no indexes are considered. However, the ** selected plan may still take advantage of the built-in rowid primary key ** index. */ | | | | | < < < < < < | | | | 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994 2995 2996 | ** then the cost is calculated in the usual way. ** ** If a NOT INDEXED clause (pSrc->notIndexed!=0) was attached to the table ** in the SELECT statement, then no indexes are considered. However, the ** selected plan may still take advantage of the built-in rowid primary key ** index. */ static void bestBtreeIndex(WhereBestIdx *p){ Parse *pParse = p->pParse; /* The parsing context */ WhereClause *pWC = p->pWC; /* The WHERE clause */ struct SrcList_item *pSrc = p->pSrc; /* The FROM clause term to search */ int iCur = pSrc->iCursor; /* The cursor of the table to be accessed */ Index *pProbe; /* An index we are evaluating */ Index *pIdx; /* Copy of pProbe, or zero for IPK index */ int eqTermMask; /* Current mask of valid equality operators */ int idxEqTermMask; /* Index mask of valid equality operators */ Index sPk; /* A fake index object for the primary key */ tRowcnt aiRowEstPk[2]; /* The aiRowEst[] value for the sPk index */ int aiColumnPk = -1; /* The aColumn[] value for the sPk index */ int wsFlagMask; /* Allowed flags in p->cost.plan.wsFlag */ /* Initialize the cost to a worst-case value */ memset(&p->cost, 0, sizeof(p->cost)); p->cost.rCost = SQLITE_BIG_DBL; /* If the pSrc table is the right table of a LEFT JOIN then we may not ** use an index to satisfy IS NULL constraints on that table. This is ** because columns might end up being NULL if the table does not match - ** a circumstance which the index cannot help us discover. Ticket #2177. */ if( pSrc->jointype & JT_LEFT ){ |
︙ | ︙ | |||
2961 2962 2963 2964 2965 2966 2967 | /* Loop over all indices looking for the best one to use */ for(; pProbe; pIdx=pProbe=pProbe->pNext){ const tRowcnt * const aiRowEst = pProbe->aiRowEst; double cost; /* Cost of using pProbe */ double nRow; /* Estimated number of rows in result set */ double log10N = (double)1; /* base-10 logarithm of nRow (inexact) */ | | | 3035 3036 3037 3038 3039 3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 | /* Loop over all indices looking for the best one to use */ for(; pProbe; pIdx=pProbe=pProbe->pNext){ const tRowcnt * const aiRowEst = pProbe->aiRowEst; double cost; /* Cost of using pProbe */ double nRow; /* Estimated number of rows in result set */ double log10N = (double)1; /* base-10 logarithm of nRow (inexact) */ int bRev = 2; /* 0=forward scan. 1=reverse. 2=undecided */ int wsFlags = 0; Bitmask used = 0; /* The following variables are populated based on the properties of ** index being evaluated. They are then used to determine the expected ** cost and number of rows returned. ** |
︙ | ︙ | |||
2994 2995 2996 2997 2998 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 | ** ** 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: ** An estimate of a divisor by which to reduce the search space due ** to inequality constraints. In the absence of sqlite_stat3 ANALYZE ** data, a single inequality reduces the search space to 1/4rd its ** original size (rangeDiv==4). Two inequalities reduce the search ** space to 1/16th of its original size (rangeDiv==16). ** ** bSort: ** Boolean. True if there is an ORDER BY clause that will require an ** external sort (i.e. scanning the index being evaluated will not ** correctly order records). ** ** bLookup: ** Boolean. True if a table lookup is required for each index entry ** visited. In other words, true if this is not a covering index. ** This is always false for the rowid primary key index of a table. ** For other indexes, it is true unless all the columns of the table ** used by the SELECT statement are present in the index (such an ** index is sometimes described as a covering index). ** For example, given the index on (a, b), the second of the following ** 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 nEq; /* Number of == or IN 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 */ | > > > > > > > > > | | > > > > > > | | > > > | 3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 3115 3116 3117 3118 3119 3120 3121 3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132 3133 3134 3135 3136 3137 3138 3139 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149 3150 3151 3152 3153 3154 3155 3156 3157 3158 3159 3160 3161 3162 3163 3164 3165 | ** ** 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: ** An estimate of a divisor by which to reduce the search space due ** to inequality constraints. In the absence of sqlite_stat3 ANALYZE ** data, a single inequality reduces the search space to 1/4rd its ** original size (rangeDiv==4). Two inequalities reduce the search ** space to 1/16th of its original size (rangeDiv==16). ** ** bSort: ** Boolean. True if there is an ORDER BY clause that will require an ** external sort (i.e. scanning the index being evaluated will not ** correctly order records). ** ** bDistinct: ** Boolean. True if there is a DISTINCT clause that will require an ** external btree. ** ** bLookup: ** Boolean. True if a table lookup is required for each index entry ** visited. In other words, true if this is not a covering index. ** This is always false for the rowid primary key index of a table. ** For other indexes, it is true unless all the columns of the table ** used by the SELECT statement are present in the index (such an ** index is sometimes described as a covering index). ** For example, given the index on (a, b), the second of the following ** 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 nEq; /* Number of == or IN terms matching index */ 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 */ int nOBSat = 0; /* Number of ORDER BY terms satisfied */ int nOrderBy; /* Number of ORDER BY terms */ WhereTerm *pTerm; /* A single term of the WHERE clause */ #ifdef SQLITE_ENABLE_STAT3 WhereTerm *pFirstTerm = 0; /* First term matching the index */ #endif nOrderBy = p->pOrderBy ? p->pOrderBy->nExpr : 0; bSort = nOrderBy>0 && (p->i==0 || p->aLevel[p->i-1].plan.nOBSat<nOrderBy); bDist = p->i==0 && p->pDistinct!=0; /* Determine the values of nEq and nInMul */ for(nEq=nOrdered=0; nEq<pProbe->nColumn; nEq++){ int j = pProbe->aiColumn[nEq]; pTerm = findTerm(pWC, iCur, j, p->notReady, eqTermMask, pIdx); if( pTerm==0 ) break; wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ); testcase( pTerm->pWC!=pWC ); if( pTerm->eOperator & WO_IN ){ Expr *pExpr = pTerm->pExpr; 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 ){ wsFlags |= WHERE_COLUMN_NULL; if( nEq==nOrdered ) nOrdered++; }else if( bSort && nEq==nOrdered && isOrderedTerm(p, pTerm, &bRev) ){ nOrdered++; } #ifdef SQLITE_ENABLE_STAT3 if( nEq==0 && pProbe->aSample ) pFirstTerm = pTerm; #endif used |= pTerm->prereqRight; } |
︙ | ︙ | |||
3084 3085 3086 3087 3088 3089 3090 | 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]); | | | > | | 3176 3177 3178 3179 3180 3181 3182 3183 3184 3185 3186 3187 3188 3189 3190 3191 3192 3193 | 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); whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &rangeDiv); if( pTop ){ nBound = 1; wsFlags |= WHERE_TOP_LIMIT; used |= pTop->prereqRight; testcase( pTop->pWC!=pWC ); } |
︙ | ︙ | |||
3108 3109 3110 3111 3112 3113 3114 | } } /* If there is an ORDER BY clause and the index being considered will ** naturally scan rows in the required order, set the appropriate flags ** in wsFlags. Otherwise, if there is an ORDER BY clause but the index ** will scan rows in a different order, set the bSort variable. */ | > > > > > | | | | | > | > | | 3201 3202 3203 3204 3205 3206 3207 3208 3209 3210 3211 3212 3213 3214 3215 3216 3217 3218 3219 3220 3221 3222 3223 3224 3225 3226 3227 3228 3229 3230 3231 3232 3233 | } } /* If there is an ORDER BY clause and the index being considered will ** naturally scan rows in the required order, set the appropriate flags ** in wsFlags. Otherwise, if there is an ORDER BY clause but 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 ); nOBSat = isSortingIndex(p, pProbe, iCur, nOrdered, wsFlags, bRev&1, &bRev); if( nOrderBy==nOBSat ){ bSort = 0; wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_ORDERBY; } if( bRev & 1 ) wsFlags |= WHERE_REVERSE; } /* If there is a DISTINCT qualifier and this index will scan rows in ** order of the DISTINCT expressions, clear bDist and set the appropriate ** flags in wsFlags. */ if( bDist && isDistinctIndex(pParse, pWC, pProbe, iCur, p->pDistinct, nEq) && (wsFlags & WHERE_COLUMN_IN)==0 ){ bDist = 0; wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_DISTINCT; } /* If currently calculating the cost of using an index (not the IPK |
︙ | ︙ | |||
3196 3197 3198 3199 3200 3201 3202 | ** on one page and hence more pages have to be fetched. ** ** The ANALYZE command and the sqlite_stat1 and sqlite_stat3 tables do ** not give us data on the relative sizes of table and index records. ** So this computation assumes table records are about twice as big ** as index records */ | | < | < | 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 | ** on one page and hence more pages have to be fetched. ** ** The ANALYZE command and the sqlite_stat1 and sqlite_stat3 tables do ** not give us data on the relative sizes of table and index records. ** So this computation assumes table records are about twice as big ** as index records */ if( (wsFlags&~WHERE_REVERSE)==WHERE_IDX_ONLY && (pWC->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 && sqlite3GlobalConfig.bUseCis && OptimizationEnabled(pParse->db, SQLITE_CoverIdxScan) ){ /* This index is not useful for indexing, but it is a covering index. ** A full-scan of the index might be a little faster than a full-scan ** of the table, so give this case a cost slightly less than a table ** scan. */ cost = aiRowEst[0]*3 + pProbe->nColumn; wsFlags |= WHERE_COVER_SCAN|WHERE_COLUMN_RANGE; |
︙ | ︙ | |||
3255 3256 3257 3258 3259 3260 3261 | /* Add in the estimated cost of sorting the result. Actual experimental ** measurements of sorting performance in SQLite show that sorting time ** adds C*N*log10(N) to the cost, where N is the number of rows to be ** sorted and C is a factor between 1.95 and 4.3. We will split the ** difference and select C of 3.0. */ if( bSort ){ | | | 3353 3354 3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365 3366 3367 | /* Add in the estimated cost of sorting the result. Actual experimental ** measurements of sorting performance in SQLite show that sorting time ** adds C*N*log10(N) to the cost, where N is the number of rows to be ** sorted and C is a factor between 1.95 and 4.3. We will split the ** difference and select C of 3.0. */ if( bSort ){ cost += nRow*estLog(nRow*(nOrderBy - nOBSat)/nOrderBy)*3; } if( bDist ){ cost += nRow*estLog(nRow)*3; } /**** Cost of using this index has now been computed ****/ |
︙ | ︙ | |||
3279 3280 3281 3282 3283 3284 3285 | ** mask will only have one bit set - the bit for the current table. ** The notValid mask, on the other hand, always has all bits set for ** tables that are not in outer loops. If notReady is used here instead ** of notValid, then a optimal index that depends on inner joins loops ** might be selected even when there exists an optimal index that has ** no such dependency. */ | | | | 3377 3378 3379 3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 | ** mask will only have one bit set - the bit for the current table. ** The notValid mask, on the other hand, always has all bits set for ** tables that are not in outer loops. If notReady is used here instead ** of notValid, then a optimal index that depends on inner joins loops ** might be selected even when there exists an optimal index that has ** no such dependency. */ if( nRow>2 && cost<=p->cost.rCost ){ int k; /* Loop counter */ int nSkipEq = nEq; /* Number of == constraints to skip */ int nSkipRange = nBound; /* Number of < constraints to skip */ Bitmask thisTab; /* Bitmap for pSrc */ thisTab = getMask(pWC->pMaskSet, iCur); for(pTerm=pWC->a, k=pWC->nTerm; nRow>2 && k; k--, pTerm++){ if( pTerm->wtFlags & TERM_VIRTUAL ) continue; if( (pTerm->prereqAll & p->notValid)!=thisTab ) continue; if( pTerm->eOperator & (WO_EQ|WO_IN|WO_ISNULL) ){ if( nSkipEq ){ /* Ignore the first nEq equality matches since the index ** has already accounted for these */ nSkipEq--; }else{ /* Assume each additional equality match reduces the result |
︙ | ︙ | |||
3323 3324 3325 3326 3327 3328 3329 | } } if( nRow<2 ) nRow = 2; } WHERETRACE(( | > | | > | | | | | | | > | | | | | | | | | | | | | < < < < < < < | | > | | | | | | 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 3448 3449 3450 3451 3452 3453 3454 3455 3456 3457 3458 3459 3460 3461 3462 3463 3464 3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485 3486 3487 3488 3489 3490 3491 3492 3493 3494 3495 3496 3497 3498 3499 3500 3501 3502 3503 3504 3505 3506 3507 3508 3509 3510 3511 3512 3513 3514 3515 3516 3517 3518 3519 | } } if( nRow<2 ) nRow = 2; } 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"), nEq, nInMul, (int)rangeDiv, bSort, bLookup, wsFlags, p->notReady, log10N, nRow, cost, used, nOrdered, nOBSat )); /* If this index is the best we have seen so far, then record this ** index and its cost in the pCost structure. */ if( (!pIdx || wsFlags) && (cost<p->cost.rCost || (cost<=p->cost.rCost && nRow<p->cost.plan.nRow)) ){ p->cost.rCost = cost; p->cost.used = used; p->cost.plan.nRow = nRow; p->cost.plan.wsFlags = (wsFlags&wsFlagMask); p->cost.plan.nEq = nEq; p->cost.plan.nOBSat = nOBSat; p->cost.plan.u.pIdx = pIdx; } /* If there was an INDEXED BY clause, then only that one index is ** considered. */ if( pSrc->pIndex ) break; /* Reset masks for the next index in the loop */ wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE); eqTermMask = idxEqTermMask; } /* If there is no ORDER BY clause and the SQLITE_ReverseOrder flag ** is set, then reverse the order that the index will be scanned ** in. This is used for application testing, to help find cases ** where application behaviour depends on the (undefined) order that ** SQLite outputs rows in in the absence of an ORDER BY clause. */ if( !p->pOrderBy && pParse->db->flags & SQLITE_ReverseOrder ){ p->cost.plan.wsFlags |= WHERE_REVERSE; } assert( p->pOrderBy || (p->cost.plan.wsFlags&WHERE_ORDERBY)==0 ); assert( p->cost.plan.u.pIdx==0 || (p->cost.plan.wsFlags&WHERE_ROWID_EQ)==0 ); assert( pSrc->pIndex==0 || p->cost.plan.u.pIdx==0 || p->cost.plan.u.pIdx==pSrc->pIndex ); WHERETRACE(("best index is: %s\n", ((p->cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ? "none" : p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk") )); bestOrClauseIndex(p); bestAutomaticIndex(p); p->cost.plan.wsFlags |= eqTermMask; } /* ** Find the query plan for accessing table pSrc->pTab. Write the ** best query plan and its cost into the WhereCost object supplied ** as the last parameter. This function may calculate the cost of ** both real and virtual table scans. ** ** This function does not take ORDER BY or DISTINCT into account. Nor ** does it remember the virtual table query plan. All it does is compute ** the cost while determining if an OR optimization is applicable. The ** details will be reconsidered later if the optimization is found to be ** applicable. */ static void bestIndex(WhereBestIdx *p){ #ifndef SQLITE_OMIT_VIRTUALTABLE if( IsVirtual(p->pSrc->pTab) ){ sqlite3_index_info *pIdxInfo = 0; p->ppIdxInfo = &pIdxInfo; bestVirtualIndex(p); if( pIdxInfo->needToFreeIdxStr ){ sqlite3_free(pIdxInfo->idxStr); } sqlite3DbFree(p->pParse->db, pIdxInfo); }else #endif { bestBtreeIndex(p); } } /* ** Disable a term in the WHERE clause. Except, do not disable the term ** if it controls a LEFT OUTER JOIN and it did not originate in the ON ** or USING clause of that join. |
︙ | ︙ | |||
4690 4691 4692 4693 4694 4695 4696 | SrcList *pTabList, /* A list of all tables to be scanned */ Expr *pWhere, /* The WHERE clause */ ExprList *pOrderBy, /* An ORDER BY clause, or NULL */ ExprList *pDistinct, /* The select-list for DISTINCT queries - or NULL */ u16 wctrlFlags, /* One of the WHERE_* flags defined in sqliteInt.h */ int iIdxCur /* If WHERE_ONETABLE_ONLY is set, index cursor number */ ){ | < > < < | | > > > > > > | 4785 4786 4787 4788 4789 4790 4791 4792 4793 4794 4795 4796 4797 4798 4799 4800 4801 4802 4803 4804 4805 4806 4807 4808 4809 4810 4811 4812 4813 4814 4815 4816 | SrcList *pTabList, /* A list of all tables to be scanned */ Expr *pWhere, /* The WHERE clause */ ExprList *pOrderBy, /* An ORDER BY clause, or NULL */ ExprList *pDistinct, /* The select-list for DISTINCT queries - or NULL */ u16 wctrlFlags, /* One of the WHERE_* flags defined in sqliteInt.h */ int iIdxCur /* If WHERE_ONETABLE_ONLY is set, index cursor number */ ){ int nByteWInfo; /* Num. bytes allocated for WhereInfo struct */ int nTabList; /* Number of elements in pTabList */ WhereInfo *pWInfo; /* Will become the return value of this function */ Vdbe *v = pParse->pVdbe; /* The virtual database engine */ Bitmask notReady; /* Cursors that are not yet positioned */ WhereBestIdx sWBI; /* Best index search context */ WhereMaskSet *pMaskSet; /* The expression mask set */ WhereLevel *pLevel; /* A single level in pWInfo->a[] */ int iFrom; /* First unused FROM clause element */ int andFlags; /* AND-ed combination of all pWC->a[].wtFlags */ int ii; /* Loop counter */ sqlite3 *db; /* Database connection */ /* Variable initialization */ memset(&sWBI, 0, sizeof(sWBI)); sWBI.pParse = pParse; /* The number of tables in the FROM clause is limited by the number of ** bits in a Bitmask */ testcase( pTabList->nSrc==BMS ); if( pTabList->nSrc>BMS ){ sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS); return 0; |
︙ | ︙ | |||
4743 4744 4745 4746 4747 4748 4749 | pWInfo = 0; goto whereBeginError; } pWInfo->nLevel = nTabList; pWInfo->pParse = pParse; pWInfo->pTabList = pTabList; pWInfo->iBreak = sqlite3VdbeMakeLabel(v); | | | > | | | | 4842 4843 4844 4845 4846 4847 4848 4849 4850 4851 4852 4853 4854 4855 4856 4857 4858 4859 4860 4861 4862 4863 4864 4865 4866 4867 4868 4869 4870 4871 4872 | pWInfo = 0; goto whereBeginError; } pWInfo->nLevel = nTabList; pWInfo->pParse = pParse; pWInfo->pTabList = pTabList; pWInfo->iBreak = sqlite3VdbeMakeLabel(v); pWInfo->pWC = sWBI.pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo]; pWInfo->wctrlFlags = wctrlFlags; pWInfo->savedNQueryLoop = pParse->nQueryLoop; pMaskSet = (WhereMaskSet*)&sWBI.pWC[1]; sWBI.aLevel = pWInfo->a; /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */ if( OptimizationDisabled(db, SQLITE_DistinctOpt) ) pDistinct = 0; /* Split the WHERE clause into separate subexpressions where each ** subexpression is separated by an AND operator. */ initMaskSet(pMaskSet); whereClauseInit(sWBI.pWC, pParse, pMaskSet, wctrlFlags); sqlite3ExprCodeConstants(pParse, pWhere); whereSplit(sWBI.pWC, pWhere, TK_AND); /* IMP: R-15842-53296 */ /* Special case: a WHERE clause that is constant. Evaluate the ** expression and either jump over all of the code or fall thru. */ if( pWhere && (nTabList==0 || sqlite3ExprIsConstantNotJoin(pWhere)) ){ sqlite3ExprIfFalse(pParse, pWhere, pWInfo->iBreak, SQLITE_JUMPIFNULL); pWhere = 0; |
︙ | ︙ | |||
4789 4790 4791 4792 4793 4794 4795 | ** with virtual tables. ** ** Note that bitmasks are created for all pTabList->nSrc tables in ** pTabList, not just the first nTabList tables. nTabList is normally ** equal to pTabList->nSrc but might be shortened to 1 if the ** WHERE_ONETABLE_ONLY flag is set. */ | | | | | | | | | | | > > > | | | | | 4889 4890 4891 4892 4893 4894 4895 4896 4897 4898 4899 4900 4901 4902 4903 4904 4905 4906 4907 4908 4909 4910 4911 4912 4913 4914 4915 4916 4917 4918 4919 4920 4921 4922 4923 4924 4925 4926 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 4974 4975 4976 4977 4978 4979 4980 4981 4982 4983 4984 4985 4986 4987 4988 4989 4990 4991 4992 | ** with virtual tables. ** ** Note that bitmasks are created for all pTabList->nSrc tables in ** pTabList, not just the first nTabList tables. nTabList is normally ** equal to pTabList->nSrc but might be shortened to 1 if the ** WHERE_ONETABLE_ONLY flag is set. */ assert( sWBI.pWC->vmask==0 && pMaskSet->n==0 ); for(ii=0; ii<pTabList->nSrc; ii++){ createMask(pMaskSet, pTabList->a[ii].iCursor); #ifndef SQLITE_OMIT_VIRTUALTABLE if( ALWAYS(pTabList->a[ii].pTab) && IsVirtual(pTabList->a[ii].pTab) ){ sWBI.pWC->vmask |= ((Bitmask)1 << ii); } #endif } #ifndef NDEBUG { Bitmask toTheLeft = 0; for(ii=0; ii<pTabList->nSrc; ii++){ Bitmask m = getMask(pMaskSet, pTabList->a[ii].iCursor); assert( (m-1)==toTheLeft ); toTheLeft |= m; } } #endif /* Analyze all of the subexpressions. Note that exprAnalyze() might ** add new virtual terms onto the end of the WHERE clause. We do not ** want to analyze these virtual terms, so start analyzing at the end ** and work forward so that the added virtual terms are never processed. */ exprAnalyzeAll(pTabList, sWBI.pWC); if( db->mallocFailed ){ goto whereBeginError; } /* Check if the DISTINCT qualifier, if there is one, is redundant. ** If it is, then set pDistinct to NULL and WhereInfo.eDistinct to ** WHERE_DISTINCT_UNIQUE to tell the caller to ignore the DISTINCT. */ if( pDistinct && isDistinctRedundant(pParse, pTabList, sWBI.pWC, pDistinct) ){ pDistinct = 0; pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE; } /* Chose the best index to use for each table in the FROM clause. ** ** This loop fills in the following fields: ** ** pWInfo->a[].pIdx The index to use for this level of the loop. ** pWInfo->a[].wsFlags WHERE_xxx flags associated with pIdx ** pWInfo->a[].nEq The number of == and IN constraints ** pWInfo->a[].iFrom Which term of the FROM clause is being coded ** pWInfo->a[].iTabCur The VDBE cursor for the database table ** pWInfo->a[].iIdxCur The VDBE cursor for the index ** pWInfo->a[].pTerm When wsFlags==WO_OR, the OR-clause term ** ** This loop also figures out the nesting order of tables in the FROM ** clause. */ sWBI.notValid = ~(Bitmask)0; sWBI.pOrderBy = pOrderBy; sWBI.n = nTabList; sWBI.pDistinct = pDistinct; andFlags = ~0; WHERETRACE(("*** Optimizer Start ***\n")); for(sWBI.i=iFrom=0, pLevel=pWInfo->a; sWBI.i<nTabList; sWBI.i++, pLevel++){ WhereCost bestPlan; /* Most efficient plan seen so far */ Index *pIdx; /* Index for FROM table at pTabItem */ int j; /* For looping over FROM tables */ int bestJ = -1; /* The value of j */ Bitmask m; /* Bitmask value for j or bestJ */ int isOptimal; /* Iterator for optimal/non-optimal search */ int nUnconstrained; /* Number tables without INDEXED BY */ Bitmask notIndexed; /* Mask of tables that cannot use an index */ memset(&bestPlan, 0, sizeof(bestPlan)); bestPlan.rCost = SQLITE_BIG_DBL; WHERETRACE(("*** Begin search for loop %d ***\n", sWBI.i)); /* Loop through the remaining entries in the FROM clause to find the ** next nested loop. The loop tests all FROM clause entries ** either once or twice. ** ** The first test is always performed if there are two or more entries ** remaining and never performed if there is only one FROM clause entry ** to choose from. The first test looks for an "optimal" scan. In ** this context an optimal scan is one that uses the same strategy ** for the given FROM clause entry as would be selected if the entry ** were used as the innermost nested loop. In other words, a table ** is chosen such that the cost of running that table cannot be reduced ** by waiting for other tables to run first. This "optimal" test works ** by first assuming that the FROM clause is on the inner loop and finding ** its query plan, then checking to see if that query plan uses any ** other FROM clause terms that are sWBI.notValid. If no notValid terms ** are used then the "optimal" query plan works. ** ** Note that the WhereCost.nRow parameter for an optimal scan might ** not be as small as it would be if the table really were the innermost ** join. The nRow value can be reduced by WHERE clause constraints ** that do not use indices. But this nRow reduction only happens if the ** table really is the innermost join. ** |
︙ | ︙ | |||
4906 4907 4908 4909 4910 4911 4912 | ** as the cost of a linear scan through table t1, a simple greedy ** algorithm may choose to use t2 for the outer loop, which is a much ** costlier approach. */ nUnconstrained = 0; notIndexed = 0; for(isOptimal=(iFrom<nTabList-1); isOptimal>=0 && bestJ<0; isOptimal--){ | < | < < < | | | | < < | | | | | < | < | | | | | | > | | | | | | | | | > | | | | | | > | 5009 5010 5011 5012 5013 5014 5015 5016 5017 5018 5019 5020 5021 5022 5023 5024 5025 5026 5027 5028 5029 5030 5031 5032 5033 5034 5035 5036 5037 5038 5039 5040 5041 5042 5043 5044 5045 5046 5047 5048 5049 5050 5051 5052 5053 5054 5055 5056 5057 5058 5059 5060 5061 5062 5063 5064 5065 5066 5067 5068 5069 5070 5071 5072 5073 5074 5075 5076 5077 5078 5079 5080 5081 5082 5083 5084 5085 5086 5087 5088 5089 5090 5091 5092 5093 5094 5095 5096 5097 5098 5099 5100 5101 5102 5103 5104 5105 5106 | ** as the cost of a linear scan through table t1, a simple greedy ** algorithm may choose to use t2 for the outer loop, which is a much ** costlier approach. */ nUnconstrained = 0; notIndexed = 0; for(isOptimal=(iFrom<nTabList-1); isOptimal>=0 && bestJ<0; isOptimal--){ for(j=iFrom, sWBI.pSrc=&pTabList->a[j]; j<nTabList; j++, sWBI.pSrc++){ int doNotReorder; /* True if this table should not be reordered */ doNotReorder = (sWBI.pSrc->jointype & (JT_LEFT|JT_CROSS))!=0; if( j!=iFrom && doNotReorder ) break; m = getMask(pMaskSet, sWBI.pSrc->iCursor); if( (m & sWBI.notValid)==0 ){ if( j==iFrom ) iFrom++; continue; } sWBI.notReady = (isOptimal ? m : sWBI.notValid); if( sWBI.pSrc->pIndex==0 ) nUnconstrained++; WHERETRACE(("=== trying table %d with isOptimal=%d ===\n", j, isOptimal)); assert( sWBI.pSrc->pTab ); #ifndef SQLITE_OMIT_VIRTUALTABLE if( IsVirtual(sWBI.pSrc->pTab) ){ sWBI.ppIdxInfo = &pWInfo->a[j].pIdxInfo; bestVirtualIndex(&sWBI); }else #endif { bestBtreeIndex(&sWBI); } assert( isOptimal || (sWBI.cost.used&sWBI.notValid)==0 ); /* If an INDEXED BY clause is present, then the plan must use that ** index if it uses any index at all */ assert( sWBI.pSrc->pIndex==0 || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 || sWBI.cost.plan.u.pIdx==sWBI.pSrc->pIndex ); if( isOptimal && (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){ notIndexed |= m; } /* Conditions under which this table becomes the best so far: ** ** (1) The table must not depend on other tables that have not ** yet run. (In other words, it must not depend on tables ** in inner loops.) ** ** (2) A full-table-scan plan cannot supercede indexed plan unless ** the full-table-scan is an "optimal" plan as defined above. ** ** (3) All tables have an INDEXED BY clause or this table lacks an ** INDEXED BY clause or this table uses the specific ** index specified by its INDEXED BY clause. This rule ensures ** that a best-so-far is always selected even if an impossible ** combination of INDEXED BY clauses are given. The error ** will be detected and relayed back to the application later. ** The NEVER() comes about because rule (2) above prevents ** An indexable full-table-scan from reaching rule (3). ** ** (4) The plan cost must be lower than prior plans or else the ** cost must be the same and the number of rows must be lower. */ if( (sWBI.cost.used&sWBI.notValid)==0 /* (1) */ && (bestJ<0 || (notIndexed&m)!=0 /* (2) */ || (bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0) && (nUnconstrained==0 || sWBI.pSrc->pIndex==0 /* (3) */ || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)) && (bestJ<0 || sWBI.cost.rCost<bestPlan.rCost /* (4) */ || (sWBI.cost.rCost<=bestPlan.rCost && sWBI.cost.plan.nRow<bestPlan.plan.nRow)) ){ WHERETRACE(("=== table %d is best so far" " with cost=%.1f, nRow=%.1f, nOBSat=%d\n", j, sWBI.cost.rCost, sWBI.cost.plan.nRow, sWBI.cost.plan.nOBSat)); bestPlan = sWBI.cost; bestJ = j; } if( doNotReorder ) break; } } assert( bestJ>=0 ); assert( sWBI.notValid & getMask(pMaskSet, pTabList->a[bestJ].iCursor) ); WHERETRACE(("*** Optimizer selects table %d for loop %d with:\n" " cost=%.1f, nRow=%.1f, nOBSat=%d wsFlags=0x%08x\n", bestJ, pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow, bestPlan.plan.nOBSat, bestPlan.plan.wsFlags)); if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){ pWInfo->nOBSat = pOrderBy->nExpr; } if( (bestPlan.plan.wsFlags & WHERE_DISTINCT)!=0 ){ assert( pWInfo->eDistinct==0 ); pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; } |
︙ | ︙ | |||
5017 5018 5019 5020 5021 5022 5023 | pLevel->iIdxCur = iIdxCur; }else{ pLevel->iIdxCur = pParse->nTab++; } }else{ pLevel->iIdxCur = -1; } | | | 5115 5116 5117 5118 5119 5120 5121 5122 5123 5124 5125 5126 5127 5128 5129 | pLevel->iIdxCur = iIdxCur; }else{ pLevel->iIdxCur = pParse->nTab++; } }else{ pLevel->iIdxCur = -1; } sWBI.notValid &= ~getMask(pMaskSet, pTabList->a[bestJ].iCursor); pLevel->iFrom = (u8)bestJ; if( bestPlan.plan.nRow>=(double)1 ){ pParse->nQueryLoop *= bestPlan.plan.nRow; } /* Check that if the table scanned by this loop iteration had an ** INDEXED BY clause attached to it, that the named index is being |
︙ | ︙ | |||
5070 5071 5072 5073 5074 5075 5076 | /* Open all tables in the pTabList and any indices selected for ** searching those tables. */ sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */ notReady = ~(Bitmask)0; pWInfo->nRowOut = (double)1; | | > | 5168 5169 5170 5171 5172 5173 5174 5175 5176 5177 5178 5179 5180 5181 5182 5183 5184 5185 | /* Open all tables in the pTabList and any indices selected for ** searching those tables. */ sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */ notReady = ~(Bitmask)0; pWInfo->nRowOut = (double)1; for(ii=0, pLevel=pWInfo->a; ii<nTabList; ii++, pLevel++){ Table *pTab; /* Table to open */ int iDb; /* Index of database containing table/index */ struct SrcList_item *pTabItem; pTabItem = &pTabList->a[pLevel->iFrom]; pTab = pTabItem->pTab; pLevel->iTabCur = pTabItem->iCursor; pWInfo->nRowOut *= pLevel->plan.nRow; iDb = sqlite3SchemaToIndex(db, pTab->pSchema); if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){ |
︙ | ︙ | |||
5108 5109 5110 5111 5112 5113 5114 | assert( n<=pTab->nCol ); } }else{ sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName); } #ifndef SQLITE_OMIT_AUTOMATIC_INDEX if( (pLevel->plan.wsFlags & WHERE_TEMP_INDEX)!=0 ){ | | | | | | | | > > | | 5207 5208 5209 5210 5211 5212 5213 5214 5215 5216 5217 5218 5219 5220 5221 5222 5223 5224 5225 5226 5227 5228 5229 5230 5231 5232 5233 5234 5235 5236 5237 5238 5239 5240 5241 5242 5243 5244 5245 5246 5247 5248 5249 5250 5251 5252 5253 5254 5255 5256 5257 5258 5259 5260 5261 5262 5263 5264 5265 | assert( n<=pTab->nCol ); } }else{ sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName); } #ifndef SQLITE_OMIT_AUTOMATIC_INDEX if( (pLevel->plan.wsFlags & WHERE_TEMP_INDEX)!=0 ){ constructAutomaticIndex(pParse, sWBI.pWC, pTabItem, notReady, pLevel); }else #endif if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){ Index *pIx = pLevel->plan.u.pIdx; KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIx); int iIndexCur = pLevel->iIdxCur; assert( pIx->pSchema==pTab->pSchema ); assert( iIndexCur>=0 ); sqlite3VdbeAddOp4(v, OP_OpenRead, iIndexCur, pIx->tnum, iDb, (char*)pKey, P4_KEYINFO_HANDOFF); VdbeComment((v, "%s", pIx->zName)); } sqlite3CodeVerifySchema(pParse, iDb); notReady &= ~getMask(sWBI.pWC->pMaskSet, pTabItem->iCursor); } pWInfo->iTop = sqlite3VdbeCurrentAddr(v); if( db->mallocFailed ) goto whereBeginError; /* Generate the code to do the search. Each iteration of the for ** loop below generates code for a single nested loop of the VM ** program. */ notReady = ~(Bitmask)0; for(ii=0; ii<nTabList; ii++){ pLevel = &pWInfo->a[ii]; explainOneScan(pParse, pTabList, pLevel, ii, pLevel->iFrom, wctrlFlags); notReady = codeOneLoopStart(pWInfo, ii, wctrlFlags, notReady); pWInfo->iContinue = pLevel->addrCont; } #ifdef SQLITE_TEST /* For testing and debugging use only */ /* Record in the query plan information about the current table ** and the index used to access it (if any). If the table itself ** is not used, its name is just '{}'. If no index is used ** the index is listed as "{}". If the primary key is used the ** index name is '*'. */ for(ii=0; ii<nTabList; ii++){ char *z; int n; int w; struct SrcList_item *pTabItem; pLevel = &pWInfo->a[ii]; w = pLevel->plan.wsFlags; pTabItem = &pTabList->a[pLevel->iFrom]; z = pTabItem->zAlias; if( z==0 ) z = pTabItem->pTab->zName; n = sqlite3Strlen30(z); if( n+nQPlan < sizeof(sqlite3_query_plan)-10 ){ if( (w & WHERE_IDX_ONLY)!=0 && (w & WHERE_COVER_SCAN)==0 ){ |
︙ | ︙ |
Changes to test/collate5.test.
︙ | ︙ | |||
217 218 219 220 221 222 223 | # These tests - collate5-3.* - focus on compound SELECT queries that # feature ORDER BY clauses. # do_test collate5-3.0 { execsql { SELECT a FROM collate5t1 UNION ALL SELECT a FROM collate5t2 ORDER BY 1; } | | | 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 | # These tests - collate5-3.* - focus on compound SELECT queries that # feature ORDER BY clauses. # do_test collate5-3.0 { execsql { SELECT a FROM collate5t1 UNION ALL SELECT a FROM collate5t2 ORDER BY 1; } } {/[aA] [aA] [aA] [aA] [bB] [bB] [bB] [bB] [nN] [nN]/} do_test collate5-3.1 { execsql { SELECT a FROM collate5t2 UNION ALL SELECT a FROM collate5t1 ORDER BY 1; } } {A A B B N a a b b n} do_test collate5-3.2 { execsql { |
︙ | ︙ | |||
278 279 280 281 282 283 284 | SELECT a, count(*) FROM collate5t1 GROUP BY a; }] } {a 2 b 2} do_test collate5-4.2 { execsql { SELECT a, b, count(*) FROM collate5t1 GROUP BY a, b ORDER BY a, b; } | | | 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 | SELECT a, count(*) FROM collate5t1 GROUP BY a; }] } {a 2 b 2} do_test collate5-4.2 { execsql { SELECT a, b, count(*) FROM collate5t1 GROUP BY a, b ORDER BY a, b; } } {/[aA] 1(.0)? 2 [bB] 2 1 [bB] 3 1/} do_test collate5-4.3 { execsql { DROP TABLE collate5t1; } } {} finish_test |
Changes to test/e_select.test.
︙ | ︙ | |||
1019 1020 1021 1022 1023 1024 1025 | # These tests also show that the following is not untrue: # # EVIDENCE-OF: R-25883-55063 The expressions in the GROUP BY clause do # not have to be expressions that appear in the result. # do_select_tests e_select-4.9 { 1 "SELECT group_concat(one), two FROM b1 GROUP BY two" { | | | | 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 | # These tests also show that the following is not untrue: # # EVIDENCE-OF: R-25883-55063 The expressions in the GROUP BY clause do # not have to be expressions that appear in the result. # do_select_tests e_select-4.9 { 1 "SELECT group_concat(one), two FROM b1 GROUP BY two" { /#,# f 1 o #,# s #,# t/ } 2 "SELECT group_concat(one), sum(one) FROM b1 GROUP BY (one>4)" { 1,2,3,4 10 5,6,7 18 } 3 "SELECT group_concat(one) FROM b1 GROUP BY (two>'o'), one%2" { 4 1,5 2,6 3,7 } 4 "SELECT group_concat(one) FROM b1 GROUP BY (one==2 OR two=='o')" { 4,3,5,7,6 1,2 } } # EVIDENCE-OF: R-14926-50129 For the purposes of grouping rows, NULL # values are considered equal. # do_select_tests e_select-4.10 { 1 "SELECT group_concat(y) FROM b2 GROUP BY x" {/#,# 3 #,#/} 2 "SELECT count(*) FROM b2 GROUP BY CASE WHEN y<4 THEN NULL ELSE 0 END" {4 1} } # EVIDENCE-OF: R-10470-30318 The usual rules for selecting a collation # sequence with which to compare text values apply when evaluating # expressions in a GROUP BY clause. # |
︙ | ︙ | |||
1741 1742 1743 1744 1745 1746 1747 | 1 2 3 1 2 -20 1 4 93 1 5 -1 } 7 "SELECT * FROM d1 ORDER BY 1 DESC, 2, 3" { 2 4 93 2 5 -1 1 2 -20 1 2 3 1 2 7 1 2 8 1 4 93 1 5 -1 } 8 "SELECT z, x FROM d1 ORDER BY 2" { | | | | | | | | 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 | 1 2 3 1 2 -20 1 4 93 1 5 -1 } 7 "SELECT * FROM d1 ORDER BY 1 DESC, 2, 3" { 2 4 93 2 5 -1 1 2 -20 1 2 3 1 2 7 1 2 8 1 4 93 1 5 -1 } 8 "SELECT z, x FROM d1 ORDER BY 2" { /# 1 # 1 # 1 # 1 # 1 # 1 # 2 # 2/ } 9 "SELECT z, x FROM d1 ORDER BY 1" { /-20 1 -1 # -1 # 3 1 7 1 8 1 93 # 93 #/ } } # EVIDENCE-OF: R-63286-51977 If the ORDER BY expression is an identifier # that corresponds to the alias of one of the output columns, then the # expression is considered an alias for that column. # do_select_tests e_select-8.5 { 1 "SELECT z+1 AS abc FROM d1 ORDER BY abc" { -19 0 0 4 8 9 94 94 } 2 "SELECT z+1 AS abc FROM d1 ORDER BY abc DESC" { 94 94 9 8 4 0 0 -19 } 3 "SELECT z AS x, x AS z FROM d1 ORDER BY z" { /# 1 # 1 # 1 # 1 # 1 # 1 # 2 # 2/ } 4 "SELECT z AS x, x AS z FROM d1 ORDER BY x" { /-20 1 -1 # -1 # 3 1 7 1 8 1 93 # 93 #/ } } # EVIDENCE-OF: R-65068-27207 Otherwise, if the ORDER BY expression is # any other expression, it is evaluated and the returned value used to # order the output rows. # |
︙ | ︙ |
Added test/orderby1.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 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 | # 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 orderby1 # Generate test data for a join. Verify that the join gets the # correct answer. # do_test 1.0 { db eval { BEGIN; CREATE TABLE album( aid INTEGER PRIMARY KEY, title TEXT UNIQUE NOT NULL ); CREATE TABLE track( tid INTEGER PRIMARY KEY, aid INTEGER NOT NULL REFERENCES album, tn INTEGER NOT NULL, name TEXT, UNIQUE(aid, tn) ); INSERT INTO album VALUES(1, '1-one'), (2, '2-two'), (3, '3-three'); INSERT INTO track VALUES (NULL, 1, 1, 'one-a'), (NULL, 2, 2, 'two-b'), (NULL, 3, 3, 'three-c'), (NULL, 1, 3, 'one-c'), (NULL, 2, 1, 'two-a'), (NULL, 3, 1, 'three-a'); COMMIT; } } {} do_test 1.1a { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn } } {one-a one-c two-a two-b three-a three-c} # Verify that the ORDER BY clause is optimized out # do_test 1.1b { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn } } {~/ORDER BY/} ;# ORDER BY optimized out # The same query with ORDER BY clause optimization disabled via + operators # should give exactly the same answer. # do_test 1.2a { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn } } {one-a one-c two-a two-b three-a three-c} # The output is sorted manually in this case. # do_test 1.2b { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn } } {/ORDER BY/} ;# separate sorting pass due to "+" on ORDER BY terms # The same query with ORDER BY optimizations turned off via built-in test. # do_test 1.3a { optimization_control db order-by-idx-join 0 db cache flush db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn } } {one-a one-c two-a two-b three-a three-c} do_test 1.3b { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn } } {/ORDER BY/} ;# separate sorting pass due to disabled optimization optimization_control db all 1 db cache flush # Reverse order sorts # do_test 1.4a { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn } } {three-a three-c two-a two-b one-a one-c} do_test 1.4b { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn } } {three-a three-c two-a two-b one-a one-c} ;# verify same order after sorting do_test 1.4c { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn } } {/ORDER BY/} ;# separate sorting pass due to mixed DESC/ASC do_test 1.5a { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC } } {one-c one-a two-b two-a three-c three-a} do_test 1.5b { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC } } {one-c one-a two-b two-a three-c three-a} ;# verify same order after sorting do_test 1.5c { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC } } {/ORDER BY/} ;# separate sorting pass due to mixed DESC/ASC do_test 1.6a { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC } } {three-c three-a two-b two-a one-c one-a} do_test 1.6b { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC } } {three-c three-a two-b two-a one-c one-a} ;# verify same order after sorting do_test 1.6c { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC } } {~/ORDER BY/} ;# ORDER BY optimized-out # Reconstruct the test data to use indices rather than integer primary keys. # do_test 2.0 { db eval { BEGIN; DROP TABLE album; DROP TABLE track; CREATE TABLE album( aid INT PRIMARY KEY, title TEXT NOT NULL ); CREATE INDEX album_i1 ON album(title, aid); CREATE TABLE track( aid INTEGER NOT NULL REFERENCES album, tn INTEGER NOT NULL, name TEXT, UNIQUE(aid, tn) ); INSERT INTO album VALUES(1, '1-one'), (2, '2-two'), (3, '3-three'); INSERT INTO track VALUES (1, 1, 'one-a'), (2, 2, 'two-b'), (3, 3, 'three-c'), (1, 3, 'one-c'), (2, 1, 'two-a'), (3, 1, 'three-a'); COMMIT; } } {} do_test 2.1a { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn } } {one-a one-c two-a two-b three-a three-c} # Verify that the ORDER BY clause is optimized out # do_test 2.1b { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn } } {~/ORDER BY/} ;# ORDER BY optimized out # The same query with ORDER BY clause optimization disabled via + operators # should give exactly the same answer. # do_test 2.2a { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn } } {one-a one-c two-a two-b three-a three-c} # The output is sorted manually in this case. # do_test 2.2b { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn } } {/ORDER BY/} ;# separate sorting pass due to "+" on ORDER BY terms # The same query with ORDER BY optimizations turned off via built-in test. # do_test 2.3a { optimization_control db order-by-idx-join 0 db cache flush db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn } } {one-a one-c two-a two-b three-a three-c} do_test 2.3b { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn } } {/ORDER BY/} ;# separate sorting pass due to disabled optimization optimization_control db all 1 db cache flush # Reverse order sorts # do_test 2.4a { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn } } {three-a three-c two-a two-b one-a one-c} do_test 2.4b { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn } } {three-a three-c two-a two-b one-a one-c} ;# verify same order after sorting do_test 2.4c { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn } } {/ORDER BY/} ;# separate sorting pass due to mixed DESC/ASC do_test 2.5a { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC } } {one-c one-a two-b two-a three-c three-a} do_test 2.5b { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC } } {one-c one-a two-b two-a three-c three-a} ;# verify same order after sorting do_test 2.5c { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC } } {/ORDER BY/} ;# separate sorting pass due to mixed ASC/DESC do_test 2.6a { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC } } {three-c three-a two-b two-a one-c one-a} do_test 2.6b { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC } } {three-c three-a two-b two-a one-c one-a} ;# verify same order after sorting do_test 2.6c { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC } } {~/ORDER BY/} ;# ORDER BY optimized-out # Generate another test dataset, but this time using mixed ASC/DESC indices. # do_test 3.0 { db eval { BEGIN; DROP TABLE album; DROP TABLE track; CREATE TABLE album( aid INTEGER PRIMARY KEY, title TEXT UNIQUE NOT NULL ); CREATE TABLE track( tid INTEGER PRIMARY KEY, aid INTEGER NOT NULL REFERENCES album, tn INTEGER NOT NULL, name TEXT, UNIQUE(aid ASC, tn DESC) ); INSERT INTO album VALUES(1, '1-one'), (2, '2-two'), (3, '3-three'); INSERT INTO track VALUES (NULL, 1, 1, 'one-a'), (NULL, 2, 2, 'two-b'), (NULL, 3, 3, 'three-c'), (NULL, 1, 3, 'one-c'), (NULL, 2, 1, 'two-a'), (NULL, 3, 1, 'three-a'); COMMIT; } } {} do_test 3.1a { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC } } {one-c one-a two-b two-a three-c three-a} # Verify that the ORDER BY clause is optimized out # do_test 3.1b { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC } } {~/ORDER BY/} ;# ORDER BY optimized out # The same query with ORDER BY clause optimization disabled via + operators # should give exactly the same answer. # do_test 3.2a { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC } } {one-c one-a two-b two-a three-c three-a} # The output is sorted manually in this case. # do_test 3.2b { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC } } {/ORDER BY/} ;# separate sorting pass due to "+" on ORDER BY terms # The same query with ORDER BY optimizations turned off via built-in test. # do_test 3.3a { optimization_control db order-by-idx-join 0 db cache flush db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC } } {one-c one-a two-b two-a three-c three-a} do_test 3.3b { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC } } {/ORDER BY/} ;# separate sorting pass due to disabled optimization optimization_control db all 1 db cache flush # Without the mixed ASC/DESC on ORDER BY # do_test 3.4a { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn } } {one-a one-c two-a two-b three-a three-c} do_test 3.4b { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn } } {one-a one-c two-a two-b three-a three-c} ;# verify same order after sorting do_test 3.4c { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn } } {/ORDER BY/} ;# separate sorting pass due to mismatched DESC/ASC do_test 3.5a { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC } } {three-c three-a two-b two-a one-c one-a} do_test 3.5b { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC } } {three-c three-a two-b two-a one-c one-a} ;# verify same order after sorting do_test 3.5c { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC } } {/ORDER BY/} ;# separate sorting pass due to mismatched ASC/DESC do_test 3.6a { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn } } {three-a three-c two-a two-b one-a one-c} do_test 3.6b { db eval { SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn } } {three-a three-c two-a two-b one-a one-c} ;# verify same order after sorting do_test 3.6c { db eval { EXPLAIN QUERY PLAN SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn } } {~/ORDER BY/} ;# inverted ASC/DESC is optimized out finish_test |
Changes to test/tester.tcl.
︙ | ︙ | |||
534 535 536 537 538 539 540 | if {![info exists ::G(match)] || [string match $::G(match) $name]} { if {[catch {uplevel #0 "$cmd;\n"} result]} { puts "\nError: $result" fail_test $name } else { if {[regexp {^~?/.*/$} $expected]} { if {[string index $expected 0]=="~"} { | | | | 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 | if {![info exists ::G(match)] || [string match $::G(match) $name]} { if {[catch {uplevel #0 "$cmd;\n"} result]} { puts "\nError: $result" fail_test $name } else { if {[regexp {^~?/.*/$} $expected]} { if {[string index $expected 0]=="~"} { set re [string map {# {[-0-9.]+}} [string range $expected 2 end-1]] set ok [expr {![regexp $re $result]}] } else { set re [string map {# {[-0-9.]+}} [string range $expected 1 end-1]] set ok [regexp $re $result] } } else { set ok [expr {[string compare $result $expected]==0}] } if {!$ok} { # if {![info exists ::testprefix] || $::testprefix eq ""} { |
︙ | ︙ |
Changes to test/tkt-cbd054fa6b.test.
︙ | ︙ | |||
46 47 48 49 50 51 52 | do_test tkt-cbd05-1.3 { execsql { SELECT tbl,idx,group_concat(sample,' ') FROM sqlite_stat3 WHERE idx = 't1_x' GROUP BY tbl,idx } | | | 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | do_test tkt-cbd05-1.3 { execsql { SELECT tbl,idx,group_concat(sample,' ') FROM sqlite_stat3 WHERE idx = 't1_x' GROUP BY tbl,idx } } {/t1 t1_x .[ ABCDEFGHI]{10}./} do_test tkt-cbd05-2.1 { db eval { DROP TABLE t1; CREATE TABLE t1(a INTEGER PRIMARY KEY, b BLOB UNIQUE NOT NULL); CREATE INDEX t1_x ON t1(b); INSERT INTO t1 VALUES(NULL, X''); |
︙ | ︙ | |||
78 79 80 81 82 83 84 | do_test tkt-cbd05-2.3 { execsql { SELECT tbl,idx,group_concat(sample,' ') FROM sqlite_stat3 WHERE idx = 't1_x' GROUP BY tbl,idx } | | | 78 79 80 81 82 83 84 85 86 87 | do_test tkt-cbd05-2.3 { execsql { SELECT tbl,idx,group_concat(sample,' ') FROM sqlite_stat3 WHERE idx = 't1_x' GROUP BY tbl,idx } } {/t1 t1_x .[ ABCDEFGHI]{10}./} finish_test |
Changes to test/where.test.
︙ | ︙ | |||
1105 1106 1107 1108 1109 1110 1111 | } } {1/4 1/1 4/4 4/1 nosort} do_test where-14.5 { # This test case changed from "nosort" to "sort". See ticket 2a5629202f. cksort { SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b } | | | | 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 | } } {1/4 1/1 4/4 4/1 nosort} do_test where-14.5 { # This test case changed from "nosort" to "sort". See ticket 2a5629202f. cksort { SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b } } {/4/[14] 4/[14] 1/[14] 1/[14] sort/} do_test where-14.6 { # This test case changed from "nosort" to "sort". See ticket 2a5629202f. cksort { SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b DESC } } {/4/[14] 4/[14] 1/[14] 1/[14] sort/} do_test where-14.7 { cksort { SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, y.a||y.b } } {4/1 4/4 1/1 1/4 sort} do_test where-14.7.1 { cksort { |
︙ | ︙ |