Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Avoid passing constraints that are unusable due to LEFT or CROSS joins to virtual table xBestIndex() methods. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
7b446771cadedafbe8924ad0658adc25 |
| User & Date: | dan 2015-06-10 14:27:40 |
Context
|
2015-06-10
| ||
| 18:53 | "test" targets on all makefiles use --verbose=file --output=test-out.txt. Add the new "quicktest" target to all makefiles - designed to run in under three minutes. The --quick option on releasetest.tcl now uses quicktest. check-in: 6ddef2ad user: drh tags: trunk | |
| 14:27 | Avoid passing constraints that are unusable due to LEFT or CROSS joins to virtual table xBestIndex() methods. check-in: 7b446771 user: dan tags: trunk | |
|
2015-06-09
| ||
| 15:58 | Add the --output=$file and --verbose=(0|1|file) options to tester.tcl. check-in: f7b2c703 user: dan tags: trunk | |
| 10:58 | Remove some repeated lines of source code. Probably introduced by careless cut'n'pasting. Closed-Leaf check-in: a34cd71c user: dan tags: vtab-left-join | |
Changes
Changes to ext/rtree/rtreeC.test.
264 264 sqlite3 db2 test.db 265 265 db2 eval { DROP TABLE sqlite_stat1 } 266 266 db2 close 267 267 execsql { SELECT * FROM rt } 268 268 } {1 2.0 3.0} 269 269 db close 270 270 } 271 + 272 +#-------------------------------------------------------------------- 273 +# Test that queries featuring LEFT or CROSS JOINS are handled correctly. 274 +# Handled correctly in this case means: 275 +# 276 +# * Terms with prereqs that appear to the left of a LEFT JOIN against 277 +# the virtual table are always available to xBestIndex. 278 +# 279 +# * Terms with prereqs that appear to the right of a LEFT JOIN against 280 +# the virtual table are never available to xBestIndex. 281 +# 282 +# And the same behaviour for CROSS joins. 283 +# 284 +reset_db 285 +do_execsql_test 7.0 { 286 + CREATE TABLE xdir(x1); 287 + CREATE TABLE ydir(y1); 288 + CREATE VIRTUAL TABLE rt USING rtree_i32(id, xmin, xmax, ymin, ymax); 289 + 290 + INSERT INTO xdir VALUES(5); 291 + INSERT INTO ydir VALUES(10); 292 + 293 + INSERT INTO rt VALUES(1, 2, 7, 12, 14); -- Not a hit 294 + INSERT INTO rt VALUES(2, 2, 7, 8, 12); -- A hit! 295 + INSERT INTO rt VALUES(3, 7, 11, 8, 12); -- Not a hit! 296 + INSERT INTO rt VALUES(4, 5, 5, 10, 10); -- A hit! 297 + 298 +} 299 + 300 +proc do_eqp_execsql_test {tn sql res} { 301 + set query "EXPLAIN QUERY PLAN $sql ; $sql " 302 + uplevel [list do_execsql_test $tn $query $res] 303 +} 304 + 305 +do_eqp_execsql_test 7.1 { 306 + SELECT id FROM xdir, rt, ydir 307 + ON (y1 BETWEEN ymin AND ymax) 308 + WHERE (x1 BETWEEN xmin AND xmax); 309 +} { 310 + 0 0 0 {SCAN TABLE xdir} 311 + 0 1 2 {SCAN TABLE ydir} 312 + 0 2 1 {SCAN TABLE rt VIRTUAL TABLE INDEX 2:B2D3B0D1} 313 + 2 4 314 +} 315 + 316 +do_eqp_execsql_test 7.2 { 317 + SELECT * FROM xdir, rt LEFT JOIN ydir 318 + ON (y1 BETWEEN ymin AND ymax) 319 + WHERE (x1 BETWEEN xmin AND xmax); 320 +} { 321 + 0 0 0 {SCAN TABLE xdir} 322 + 0 1 1 {SCAN TABLE rt VIRTUAL TABLE INDEX 2:B0D1} 323 + 0 2 2 {SCAN TABLE ydir} 324 + 325 + 5 1 2 7 12 14 {} 326 + 5 2 2 7 8 12 10 327 + 5 4 5 5 10 10 10 328 +} 329 + 330 +do_eqp_execsql_test 7.3 { 331 + SELECT id FROM xdir, rt CROSS JOIN ydir 332 + ON (y1 BETWEEN ymin AND ymax) 333 + WHERE (x1 BETWEEN xmin AND xmax); 334 +} { 335 + 0 0 0 {SCAN TABLE xdir} 336 + 0 1 1 {SCAN TABLE rt VIRTUAL TABLE INDEX 2:B0D1} 337 + 0 2 2 {SCAN TABLE ydir} 338 + 2 4 339 +} 340 + 341 +do_eqp_execsql_test 7.4 { 342 + SELECT id FROM rt, xdir CROSS JOIN ydir 343 + ON (y1 BETWEEN ymin AND ymax) 344 + WHERE (x1 BETWEEN xmin AND xmax); 345 +} { 346 + 0 0 1 {SCAN TABLE xdir} 347 + 0 1 0 {SCAN TABLE rt VIRTUAL TABLE INDEX 2:B0D1} 348 + 0 2 2 {SCAN TABLE ydir} 349 + 2 4 350 +} 351 + 352 +finish_test 353 + 271 354 272 355 273 356 finish_test
Changes to src/where.c.
753 753 ** Allocate and populate an sqlite3_index_info structure. It is the 754 754 ** responsibility of the caller to eventually release the structure 755 755 ** by passing the pointer returned by this function to sqlite3_free(). 756 756 */ 757 757 static sqlite3_index_info *allocateIndexInfo( 758 758 Parse *pParse, 759 759 WhereClause *pWC, 760 + Bitmask mUnusable, /* Ignore terms with these prereqs */ 760 761 struct SrcList_item *pSrc, 761 762 ExprList *pOrderBy 762 763 ){ 763 764 int i, j; 764 765 int nTerm; 765 766 struct sqlite3_index_constraint *pIdxCons; 766 767 struct sqlite3_index_orderby *pIdxOrderBy; ................................................................................ 769 770 int nOrderBy; 770 771 sqlite3_index_info *pIdxInfo; 771 772 772 773 /* Count the number of possible WHERE clause constraints referring 773 774 ** to this virtual table */ 774 775 for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){ 775 776 if( pTerm->leftCursor != pSrc->iCursor ) continue; 777 + if( pTerm->prereqRight & mUnusable ) continue; 776 778 assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) ); 777 779 testcase( pTerm->eOperator & WO_IN ); 778 780 testcase( pTerm->eOperator & WO_ISNULL ); 779 781 testcase( pTerm->eOperator & WO_IS ); 780 782 testcase( pTerm->eOperator & WO_ALL ); 781 783 if( (pTerm->eOperator & ~(WO_ISNULL|WO_EQUIV|WO_IS))==0 ) continue; 782 784 if( pTerm->wtFlags & TERM_VNULL ) continue; ................................................................................ 823 825 *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy; 824 826 *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage = 825 827 pUsage; 826 828 827 829 for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){ 828 830 u8 op; 829 831 if( pTerm->leftCursor != pSrc->iCursor ) continue; 832 + if( pTerm->prereqRight & mUnusable ) continue; 830 833 assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) ); 831 834 testcase( pTerm->eOperator & WO_IN ); 832 835 testcase( pTerm->eOperator & WO_IS ); 833 836 testcase( pTerm->eOperator & WO_ISNULL ); 834 837 testcase( pTerm->eOperator & WO_ALL ); 835 838 if( (pTerm->eOperator & ~(WO_ISNULL|WO_EQUIV|WO_IS))==0 ) continue; 836 839 if( pTerm->wtFlags & TERM_VNULL ) continue; ................................................................................ 2662 2665 return rc; 2663 2666 } 2664 2667 2665 2668 #ifndef SQLITE_OMIT_VIRTUALTABLE 2666 2669 /* 2667 2670 ** Add all WhereLoop objects for a table of the join identified by 2668 2671 ** pBuilder->pNew->iTab. That table is guaranteed to be a virtual table. 2672 +** 2673 +** If there are no LEFT or CROSS JOIN joins in the query, both mExtra and 2674 +** mUnusable are set to 0. Otherwise, mExtra is a mask of all FROM clause 2675 +** entries that occur before the virtual table in the FROM clause and are 2676 +** separated from it by at least one LEFT or CROSS JOIN. Similarly, the 2677 +** mUnusable mask contains all FROM clause entries that occur after the 2678 +** virtual table and are separated from it by at least one LEFT or 2679 +** CROSS JOIN. 2680 +** 2681 +** For example, if the query were: 2682 +** 2683 +** ... FROM t1, t2 LEFT JOIN t3, t4, vt CROSS JOIN t5, t6; 2684 +** 2685 +** then mExtra corresponds to (t1, t2) and mUnusable to (t5, t6). 2686 +** 2687 +** All the tables in mExtra must be scanned before the current virtual 2688 +** table. So any terms for which all prerequisites are satisfied by 2689 +** mExtra may be specified as "usable" in all calls to xBestIndex. 2690 +** Conversely, all tables in mUnusable must be scanned after the current 2691 +** virtual table, so any terms for which the prerequisites overlap with 2692 +** mUnusable should always be configured as "not-usable" for xBestIndex. 2669 2693 */ 2670 2694 static int whereLoopAddVirtual( 2671 2695 WhereLoopBuilder *pBuilder, /* WHERE clause information */ 2672 - Bitmask mExtra 2696 + Bitmask mExtra, /* Tables that must be scanned before this one */ 2697 + Bitmask mUnusable /* Tables that must be scanned after this one */ 2673 2698 ){ 2674 2699 WhereInfo *pWInfo; /* WHERE analysis context */ 2675 2700 Parse *pParse; /* The parsing context */ 2676 2701 WhereClause *pWC; /* The WHERE clause */ 2677 2702 struct SrcList_item *pSrc; /* The FROM clause term to search */ 2678 2703 Table *pTab; 2679 2704 sqlite3 *db; ................................................................................ 2686 2711 int nConstraint; 2687 2712 int seenIn = 0; /* True if an IN operator is seen */ 2688 2713 int seenVar = 0; /* True if a non-constant constraint is seen */ 2689 2714 int iPhase; /* 0: const w/o IN, 1: const, 2: no IN, 2: IN */ 2690 2715 WhereLoop *pNew; 2691 2716 int rc = SQLITE_OK; 2692 2717 2718 + assert( (mExtra & mUnusable)==0 ); 2693 2719 pWInfo = pBuilder->pWInfo; 2694 2720 pParse = pWInfo->pParse; 2695 2721 db = pParse->db; 2696 2722 pWC = pBuilder->pWC; 2697 2723 pNew = pBuilder->pNew; 2698 2724 pSrc = &pWInfo->pTabList->a[pNew->iTab]; 2699 2725 pTab = pSrc->pTab; 2700 2726 assert( IsVirtual(pTab) ); 2701 - pIdxInfo = allocateIndexInfo(pParse, pWC, pSrc, pBuilder->pOrderBy); 2727 + pIdxInfo = allocateIndexInfo(pParse, pWC, mUnusable, pSrc,pBuilder->pOrderBy); 2702 2728 if( pIdxInfo==0 ) return SQLITE_NOMEM; 2703 2729 pNew->prereq = 0; 2704 2730 pNew->rSetup = 0; 2705 2731 pNew->wsFlags = WHERE_VIRTUALTABLE; 2706 2732 pNew->nLTerm = 0; 2707 2733 pNew->u.vtab.needFree = 0; 2708 2734 pUsage = pIdxInfo->aConstraintUsage; ................................................................................ 2724 2750 pTerm = &pWC->a[j]; 2725 2751 switch( iPhase ){ 2726 2752 case 0: /* Constants without IN operator */ 2727 2753 pIdxCons->usable = 0; 2728 2754 if( (pTerm->eOperator & WO_IN)!=0 ){ 2729 2755 seenIn = 1; 2730 2756 } 2731 - if( pTerm->prereqRight!=0 ){ 2757 + if( (pTerm->prereqRight & ~mExtra)!=0 ){ 2732 2758 seenVar = 1; 2733 2759 }else if( (pTerm->eOperator & WO_IN)==0 ){ 2734 2760 pIdxCons->usable = 1; 2735 2761 } 2736 2762 break; 2737 2763 case 1: /* Constants with IN operators */ 2738 2764 assert( seenIn ); 2739 - pIdxCons->usable = (pTerm->prereqRight==0); 2765 + pIdxCons->usable = (pTerm->prereqRight & ~mExtra)==0; 2740 2766 break; 2741 2767 case 2: /* Variables without IN */ 2742 2768 assert( seenVar ); 2743 2769 pIdxCons->usable = (pTerm->eOperator & WO_IN)==0; 2744 2770 break; 2745 2771 default: /* Variables with IN */ 2746 2772 assert( seenVar && seenIn ); ................................................................................ 2831 2857 } 2832 2858 #endif /* SQLITE_OMIT_VIRTUALTABLE */ 2833 2859 2834 2860 /* 2835 2861 ** Add WhereLoop entries to handle OR terms. This works for either 2836 2862 ** btrees or virtual tables. 2837 2863 */ 2838 -static int whereLoopAddOr(WhereLoopBuilder *pBuilder, Bitmask mExtra){ 2864 +static int whereLoopAddOr( 2865 + WhereLoopBuilder *pBuilder, 2866 + Bitmask mExtra, 2867 + Bitmask mUnusable 2868 +){ 2839 2869 WhereInfo *pWInfo = pBuilder->pWInfo; 2840 2870 WhereClause *pWC; 2841 2871 WhereLoop *pNew; 2842 2872 WhereTerm *pTerm, *pWCEnd; 2843 2873 int rc = SQLITE_OK; 2844 2874 int iCur; 2845 2875 WhereClause tempWC; ................................................................................ 2890 2920 for(i=0; i<sSubBuild.pWC->nTerm; i++){ 2891 2921 whereTermPrint(&sSubBuild.pWC->a[i], i); 2892 2922 } 2893 2923 } 2894 2924 #endif 2895 2925 #ifndef SQLITE_OMIT_VIRTUALTABLE 2896 2926 if( IsVirtual(pItem->pTab) ){ 2897 - rc = whereLoopAddVirtual(&sSubBuild, mExtra); 2927 + rc = whereLoopAddVirtual(&sSubBuild, mExtra, mUnusable); 2898 2928 }else 2899 2929 #endif 2900 2930 { 2901 2931 rc = whereLoopAddBtree(&sSubBuild, mExtra); 2902 2932 } 2903 2933 if( rc==SQLITE_OK ){ 2904 - rc = whereLoopAddOr(&sSubBuild, mExtra); 2934 + rc = whereLoopAddOr(&sSubBuild, mExtra, mUnusable); 2905 2935 } 2906 2936 assert( rc==SQLITE_OK || sCur.n==0 ); 2907 2937 if( sCur.n==0 ){ 2908 2938 sSum.n = 0; 2909 2939 break; 2910 2940 }else if( once ){ 2911 2941 whereOrMove(&sSum, &sCur); ................................................................................ 2959 2989 static int whereLoopAddAll(WhereLoopBuilder *pBuilder){ 2960 2990 WhereInfo *pWInfo = pBuilder->pWInfo; 2961 2991 Bitmask mExtra = 0; 2962 2992 Bitmask mPrior = 0; 2963 2993 int iTab; 2964 2994 SrcList *pTabList = pWInfo->pTabList; 2965 2995 struct SrcList_item *pItem; 2996 + struct SrcList_item *pEnd = &pTabList->a[pWInfo->nLevel]; 2966 2997 sqlite3 *db = pWInfo->pParse->db; 2967 - int nTabList = pWInfo->nLevel; 2968 2998 int rc = SQLITE_OK; 2969 - u8 priorJoinType = 0; 2970 2999 WhereLoop *pNew; 3000 + u8 priorJointype = 0; 2971 3001 2972 3002 /* Loop over the tables in the join, from left to right */ 2973 3003 pNew = pBuilder->pNew; 2974 3004 whereLoopInit(pNew); 2975 - for(iTab=0, pItem=pTabList->a; iTab<nTabList; iTab++, pItem++){ 3005 + for(iTab=0, pItem=pTabList->a; pItem<pEnd; iTab++, pItem++){ 3006 + Bitmask mUnusable = 0; 2976 3007 pNew->iTab = iTab; 2977 3008 pNew->maskSelf = sqlite3WhereGetMask(&pWInfo->sMaskSet, pItem->iCursor); 2978 - if( ((pItem->jointype|priorJoinType) & (JT_LEFT|JT_CROSS))!=0 ){ 3009 + if( ((pItem->jointype|priorJointype) & (JT_LEFT|JT_CROSS))!=0 ){ 3010 + /* This condition is true when pItem is the FROM clause term on the 3011 + ** right-hand-side of a LEFT or CROSS JOIN. */ 2979 3012 mExtra = mPrior; 2980 3013 } 2981 - priorJoinType = pItem->jointype; 3014 + priorJointype = pItem->jointype; 2982 3015 if( IsVirtual(pItem->pTab) ){ 2983 - rc = whereLoopAddVirtual(pBuilder, mExtra); 3016 + struct SrcList_item *p; 3017 + for(p=&pItem[1]; p<pEnd; p++){ 3018 + if( mUnusable || (p->jointype & (JT_LEFT|JT_CROSS)) ){ 3019 + mUnusable |= sqlite3WhereGetMask(&pWInfo->sMaskSet, p->iCursor); 3020 + } 3021 + } 3022 + rc = whereLoopAddVirtual(pBuilder, mExtra, mUnusable); 2984 3023 }else{ 2985 3024 rc = whereLoopAddBtree(pBuilder, mExtra); 2986 3025 } 2987 3026 if( rc==SQLITE_OK ){ 2988 - rc = whereLoopAddOr(pBuilder, mExtra); 3027 + rc = whereLoopAddOr(pBuilder, mExtra, mUnusable); 2989 3028 } 2990 3029 mPrior |= pNew->maskSelf; 2991 3030 if( rc || db->mallocFailed ) break; 2992 3031 } 3032 + 2993 3033 whereLoopClear(db, pNew); 2994 3034 return rc; 2995 3035 } 2996 3036 2997 3037 /* 2998 3038 ** Examine a WherePath (with the addition of the extra WhereLoop of the 5th 2999 3039 ** parameters) to see if it outputs rows in the requested ORDER BY
Changes to test/join.test.
682 682 if {[lsearch [db eval {PRAGMA compile_options}] MEMDEBUG]<0} { 683 683 jointest join-12.10 65534 {1 {at most 64 tables in a join}} 684 684 jointest join-12.11 65535 {1 {too many references to "t14": max 65535}} 685 685 jointest join-12.12 65536 {1 {too many references to "t14": max 65535}} 686 686 jointest join-12.13 65537 {1 {too many references to "t14": max 65535}} 687 687 } 688 688 } 689 + 690 + 691 +#------------------------------------------------------------------------- 692 +# Test a problem with reordering tables following a LEFT JOIN. 693 +# 694 +do_execsql_test join-13.0 { 695 + CREATE TABLE aa(a); 696 + CREATE TABLE bb(b); 697 + CREATE TABLE cc(c); 698 + 699 + INSERT INTO aa VALUES(45); 700 + INSERT INTO cc VALUES(45); 701 + INSERT INTO cc VALUES(45); 702 +} 703 + 704 +do_execsql_test join-13.1 { 705 + SELECT * FROM aa LEFT JOIN bb, cc WHERE cc.c=aa.a; 706 +} {45 {} 45 45 {} 45} 707 + 708 +# In the following, the order of [cc] and [bb] must not be exchanged, even 709 +# though this would be helpful if the query used an inner join. 710 +do_execsql_test join-13.2 { 711 + CREATE INDEX ccc ON cc(c); 712 + SELECT * FROM aa LEFT JOIN bb, cc WHERE cc.c=aa.a; 713 +} {45 {} 45 45 {} 45} 714 + 689 715 690 716 finish_test