Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Enhance the query planner to exploit transitivity of join constraints in a multi-way join. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | transitive-constraints |
Files: | files | file ages | folders |
SHA1: |
13171eb5dc19733276fbfd5515d75b70 |
User & Date: | drh 2013-01-16 17:08:58.150 |
Context
2013-01-17
| ||
00:08 | Improved comments explaining the operation of the findTerm() utility routine in where.c. Increase the maximum number of levels of transitivity from 4 to 11. (check-in: fe152f8b04 user: drh tags: transitive-constraints) | |
2013-01-16
| ||
17:08 | Enhance the query planner to exploit transitivity of join constraints in a multi-way join. (check-in: 13171eb5dc user: drh tags: transitive-constraints) | |
00:46 | Improvements to query planning for joins: Avoid unnecessary calls to "optimal scan" checks in cases where table reordering is not possible. Make sure optimal scan checks are carried out for CROSS JOINs and LEFT JOINs. (check-in: d5ebb78778 user: drh tags: trunk) | |
Changes
Changes to src/sqliteInt.h.
︙ | ︙ | |||
571 572 573 574 575 576 577 578 579 580 581 582 583 584 | /* ** A convenience macro that returns the number of elements in ** an array. */ #define ArraySize(X) ((int)(sizeof(X)/sizeof(X[0]))) /* ** The following value as a destructor means to use sqlite3DbFree(). ** The sqlite3DbFree() routine requires two parameters instead of the ** one parameter that destructors normally want. So we have to introduce ** this magic value that the code knows to handle differently. Any ** pointer will work here as long as it is distinct from SQLITE_STATIC ** and SQLITE_TRANSIENT. | > > > > > | 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 | /* ** A convenience macro that returns the number of elements in ** an array. */ #define ArraySize(X) ((int)(sizeof(X)/sizeof(X[0]))) /* ** Determine if the argument is a power of two */ #define IsPowerOfTwo(X) (((X)&((X)-1))==0) /* ** The following value as a destructor means to use sqlite3DbFree(). ** The sqlite3DbFree() routine requires two parameters instead of the ** one parameter that destructors normally want. So we have to introduce ** this magic value that the code knows to handle differently. Any ** pointer will work here as long as it is distinct from SQLITE_STATIC ** and SQLITE_TRANSIENT. |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
94 95 96 97 98 99 100 | typedef struct WhereTerm WhereTerm; struct WhereTerm { Expr *pExpr; /* Pointer to the subexpression that is this term */ int iParent; /* Disable pWC->a[iParent] when this term disabled */ int leftCursor; /* Cursor number of X in "X <op> <expr>" */ union { int leftColumn; /* Column number of X in "X <op> <expr>" */ | | | | 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | typedef struct WhereTerm WhereTerm; struct WhereTerm { Expr *pExpr; /* Pointer to the subexpression that is this term */ int iParent; /* Disable pWC->a[iParent] when this term disabled */ int leftCursor; /* Cursor number of X in "X <op> <expr>" */ union { int leftColumn; /* Column number of X in "X <op> <expr>" */ WhereOrInfo *pOrInfo; /* Extra information if (eOperator & WO_OR)!=0 */ WhereAndInfo *pAndInfo; /* Extra information if (eOperator& WO_AND)!=0 */ } u; u16 eOperator; /* A WO_xx value describing <op> */ u8 wtFlags; /* TERM_xxx bit flags. See below */ u8 nChild; /* Number of children that must disable us */ WhereClause *pWC; /* The clause this term is part of */ Bitmask prereqRight; /* Bitmask of tables used by pExpr->pRight */ Bitmask prereqAll; /* Bitmask of tables referenced by pExpr */ |
︙ | ︙ | |||
223 224 225 226 227 228 229 230 231 232 233 234 235 236 | #define WO_LE (WO_EQ<<(TK_LE-TK_EQ)) #define WO_GT (WO_EQ<<(TK_GT-TK_EQ)) #define WO_GE (WO_EQ<<(TK_GE-TK_EQ)) #define WO_MATCH 0x040 #define WO_ISNULL 0x080 #define WO_OR 0x100 /* Two or more OR-connected terms */ #define WO_AND 0x200 /* Two or more AND-connected terms */ #define WO_NOOP 0x800 /* This term does not restrict search space */ #define WO_ALL 0xfff /* Mask of all possible WO_* values */ #define WO_SINGLE 0x0ff /* Mask of all non-compound WO_* values */ /* ** Value for wsFlags returned by bestIndex() and stored in | > | 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 | #define WO_LE (WO_EQ<<(TK_LE-TK_EQ)) #define WO_GT (WO_EQ<<(TK_GT-TK_EQ)) #define WO_GE (WO_EQ<<(TK_GE-TK_EQ)) #define WO_MATCH 0x040 #define WO_ISNULL 0x080 #define WO_OR 0x100 /* Two or more OR-connected terms */ #define WO_AND 0x200 /* Two or more AND-connected terms */ #define WO_EQUIV 0x400 /* Of the form A==B, both columns */ #define WO_NOOP 0x800 /* This term does not restrict search space */ #define WO_ALL 0xfff /* Mask of all possible WO_* values */ #define WO_SINGLE 0x0ff /* Mask of all non-compound WO_* values */ /* ** Value for wsFlags returned by bestIndex() and stored in |
︙ | ︙ | |||
635 636 637 638 639 640 641 | int iCur, /* Cursor number of LHS */ int iColumn, /* Column number of LHS */ Bitmask notReady, /* RHS must not overlap with this mask */ u32 op, /* Mask of WO_xx values describing operator */ Index *pIdx /* Must be compatible with this index, if not NULL */ ){ WhereTerm *pTerm; | > > | > > > > > > | > > | | | < | | | > | < | | | > | < | | | | | | | | | | | | | | | | | > | > > > > > > > > | > > > > | > > > > > > > > > > | | 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 | int iCur, /* Cursor number of LHS */ int iColumn, /* Column number of LHS */ Bitmask notReady, /* RHS must not overlap with this mask */ u32 op, /* Mask of WO_xx values describing operator */ Index *pIdx /* Must be compatible with this index, if not NULL */ ){ WhereTerm *pTerm; WhereTerm *pResult = 0; WhereClause *pWCOrig = pWC; int j, k; int aEquiv[8]; int nEquiv = 2; int iEquiv = 2; Expr *pX; Parse *pParse; assert( iCur>=0 ); aEquiv[0] = iCur; aEquiv[1] = iColumn; for(;;){ for(pWC=pWCOrig; pWC; pWC=pWC->pOuter){ for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){ if( pTerm->leftCursor==iCur && pTerm->u.leftColumn==iColumn && (pTerm->eOperator & op & WO_ALL)!=0 ){ if( (pTerm->prereqRight & notReady)==0 ){ if( iColumn>=0 && pIdx && (pTerm->eOperator & WO_ISNULL)==0 ){ CollSeq *pColl; char idxaff; pX = pTerm->pExpr; pParse = pWC->pParse; idxaff = pIdx->pTable->aCol[iColumn].affinity; if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue; /* Figure out the collation sequence required from an index for ** it to be useful for optimising expression pX. Store this ** value in variable pColl. */ assert(pX->pLeft); pColl = sqlite3BinaryCompareCollSeq(pParse,pX->pLeft,pX->pRight); if( pColl==0 ) pColl = pParse->db->pDfltColl; for(j=0; pIdx->aiColumn[j]!=iColumn; j++){ if( NEVER(j>=pIdx->nColumn) ) return 0; } if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue; } pResult = pTerm; if( pTerm->prereqRight==0 ) goto findTerm_success; } if( (op&WO_EQ)!=0 && (pTerm->eOperator & WO_EQUIV)!=0 && nEquiv<ArraySize(aEquiv) ){ pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight); assert( pX->op==TK_COLUMN ); for(j=0; j<nEquiv; j+=2){ if( aEquiv[j]==pX->iTable && aEquiv[j+1]==pX->iColumn ) break; } if( j==nEquiv ){ aEquiv[j] = pX->iTable; aEquiv[j+1] = pX->iColumn; nEquiv += 2; } } } } } if( iEquiv>=nEquiv ) break; iCur = aEquiv[iEquiv++]; iColumn = aEquiv[iEquiv++]; op &= WO_EQ; } findTerm_success: return pResult; } /* Forward reference */ static void exprAnalyze(SrcList*, WhereClause*, int); /* ** Call exprAnalyze on all terms in a WHERE clause. |
︙ | ︙ | |||
989 990 991 992 993 994 995 | Bitmask b; b = getMask(pMaskSet, pOrTerm->leftCursor); if( pOrTerm->wtFlags & TERM_VIRTUAL ){ WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent]; b |= getMask(pMaskSet, pOther->leftCursor); } indexable &= b; | | | 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 | Bitmask b; b = getMask(pMaskSet, pOrTerm->leftCursor); if( pOrTerm->wtFlags & TERM_VIRTUAL ){ WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent]; b |= getMask(pMaskSet, pOther->leftCursor); } indexable &= b; if( (pOrTerm->eOperator & WO_EQ)==0 ){ chngToIN = 0; }else{ chngToIN &= b; } } } |
︙ | ︙ | |||
1040 1041 1042 1043 1044 1045 1046 | ** will be recorded in iCursor and iColumn. There might not be any ** such table and column. Set okToChngToIN if an appropriate table ** and column is found but leave okToChngToIN false if not found. */ for(j=0; j<2 && !okToChngToIN; j++){ pOrTerm = pOrWc->a; for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){ | | | 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 | ** will be recorded in iCursor and iColumn. There might not be any ** such table and column. Set okToChngToIN if an appropriate table ** and column is found but leave okToChngToIN false if not found. */ for(j=0; j<2 && !okToChngToIN; j++){ pOrTerm = pOrWc->a; for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){ assert( pOrTerm->eOperator & WO_EQ ); pOrTerm->wtFlags &= ~TERM_OR_OK; if( pOrTerm->leftCursor==iCursor ){ /* This is the 2-bit case and we are on the second iteration and ** current term is from the first iteration. So skip this term. */ assert( j==1 ); continue; } |
︙ | ︙ | |||
1066 1067 1068 1069 1070 1071 1072 | iCursor = pOrTerm->leftCursor; break; } if( i<0 ){ /* No candidate table+column was found. This can only occur ** on the second iteration */ assert( j==1 ); | | | | 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 | iCursor = pOrTerm->leftCursor; break; } if( i<0 ){ /* No candidate table+column was found. This can only occur ** on the second iteration */ assert( j==1 ); assert( IsPowerOfTwo(chngToIN) ); assert( chngToIN==getMask(pMaskSet, iCursor) ); break; } testcase( j==1 ); /* We have found a candidate table and column. Check to see if that ** table and column is common to every term in the OR clause */ okToChngToIN = 1; for(; i>=0 && okToChngToIN; i--, pOrTerm++){ assert( pOrTerm->eOperator & WO_EQ ); if( pOrTerm->leftCursor!=iCursor ){ pOrTerm->wtFlags &= ~TERM_OR_OK; }else if( pOrTerm->u.leftColumn!=iColumn ){ okToChngToIN = 0; }else{ int affLeft, affRight; /* If the right-hand side is also a column, then the affinities |
︙ | ︙ | |||
1112 1113 1114 1115 1116 1117 1118 | Expr *pDup; /* A transient duplicate expression */ ExprList *pList = 0; /* The RHS of the IN operator */ Expr *pLeft = 0; /* The LHS of the IN operator */ Expr *pNew; /* The complete IN operator */ for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){ if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue; | | | 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 | Expr *pDup; /* A transient duplicate expression */ ExprList *pList = 0; /* The RHS of the IN operator */ Expr *pLeft = 0; /* The LHS of the IN operator */ Expr *pNew; /* The complete IN operator */ for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){ if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue; assert( pOrTerm->eOperator & WO_EQ ); assert( pOrTerm->leftCursor==iCursor ); assert( pOrTerm->u.leftColumn==iColumn ); pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0); pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup); pLeft = pOrTerm->pExpr->pLeft; } assert( pLeft!=0 ); |
︙ | ︙ | |||
1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 | } pTerm->eOperator = WO_NOOP; /* case 1 trumps case 2 */ } } } #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */ /* ** The input to this routine is an WhereTerm structure with only the ** "pExpr" field filled in. The job of this routine is to analyze the ** subexpression and populate all the other fields of the WhereTerm ** structure. ** | > > > > > > > > > > > > > > > > > > > > > | 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 | } pTerm->eOperator = WO_NOOP; /* case 1 trumps case 2 */ } } } #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */ /* ** Check to see if pExpr is an expression of the form A==B where both ** A and B are columns with the same affinity and collating sequence. ** If A and B are equivalent, return true. */ static int isEquivalenceExpr(Parse *pParse, Expr *pExpr){ const CollSeq *pCLeft, *pCRight; if( pExpr->op!=TK_EQ ) return 0; if( ExprHasProperty(pExpr, EP_FromJoin) ) return 0; assert( sqlite3ExprSkipCollate(pExpr->pRight)->op==TK_COLUMN ); assert( sqlite3ExprSkipCollate(pExpr->pLeft)->op==TK_COLUMN ); if( sqlite3ExprAffinity(pExpr->pLeft)!=sqlite3ExprAffinity(pExpr->pRight) ){ return 0; } pCLeft = sqlite3ExprCollSeq(pParse, pExpr->pLeft); if( pCLeft ){ pCRight = sqlite3ExprCollSeq(pParse, pExpr->pRight); if( pCRight && pCRight!=pCLeft ) return 0; } return 1; } /* ** The input to this routine is an WhereTerm structure with only the ** "pExpr" field filled in. The job of this routine is to analyze the ** subexpression and populate all the other fields of the WhereTerm ** structure. ** |
︙ | ︙ | |||
1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 | pTerm->leftCursor = pLeft->iTable; pTerm->u.leftColumn = pLeft->iColumn; pTerm->eOperator = operatorMask(op); } if( pRight && pRight->op==TK_COLUMN ){ WhereTerm *pNew; Expr *pDup; if( pTerm->leftCursor>=0 ){ int idxNew; pDup = sqlite3ExprDup(db, pExpr, 0); if( db->mallocFailed ){ sqlite3ExprDelete(db, pDup); return; } idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC); if( idxNew==0 ) return; pNew = &pWC->a[idxNew]; pNew->iParent = idxTerm; pTerm = &pWC->a[idxTerm]; pTerm->nChild = 1; pTerm->wtFlags |= TERM_COPIED; }else{ pDup = pExpr; pNew = pTerm; } exprCommute(pParse, pDup); pLeft = sqlite3ExprSkipCollate(pDup->pLeft); pNew->leftCursor = pLeft->iTable; pNew->u.leftColumn = pLeft->iColumn; testcase( (prereqLeft | extraRight) != prereqLeft ); pNew->prereqRight = prereqLeft | extraRight; pNew->prereqAll = prereqAll; | > > > > > | | 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 | pTerm->leftCursor = pLeft->iTable; pTerm->u.leftColumn = pLeft->iColumn; pTerm->eOperator = operatorMask(op); } if( pRight && pRight->op==TK_COLUMN ){ WhereTerm *pNew; Expr *pDup; u16 eExtraOp = 0; /* Extra bits for pNew->eOperator */ if( pTerm->leftCursor>=0 ){ int idxNew; pDup = sqlite3ExprDup(db, pExpr, 0); if( db->mallocFailed ){ sqlite3ExprDelete(db, pDup); return; } idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC); if( idxNew==0 ) return; pNew = &pWC->a[idxNew]; pNew->iParent = idxTerm; pTerm = &pWC->a[idxTerm]; pTerm->nChild = 1; pTerm->wtFlags |= TERM_COPIED; if( isEquivalenceExpr(pParse, pExpr) ){ pTerm->eOperator |= WO_EQUIV; eExtraOp = WO_EQUIV; } }else{ pDup = pExpr; pNew = pTerm; } exprCommute(pParse, pDup); pLeft = sqlite3ExprSkipCollate(pDup->pLeft); pNew->leftCursor = pLeft->iTable; pNew->u.leftColumn = pLeft->iColumn; testcase( (prereqLeft | extraRight) != prereqLeft ); pNew->prereqRight = prereqLeft | extraRight; pNew->prereqAll = prereqAll; pNew->eOperator = operatorMask(pDup->op) + eExtraOp; } } #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION /* If a term is the BETWEEN operator, create two new virtual terms ** that define the range that the BETWEEN implements. For example: ** |
︙ | ︙ | |||
1706 1707 1708 1709 1710 1711 1712 | } 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++){ | | | | 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 | } 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)!=0 && ((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)!=0 ){ 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; |
︙ | ︙ | |||
1788 1789 1790 1791 1792 1793 1794 | static int termCanDriveIndex( WhereTerm *pTerm, /* WHERE clause term to check */ struct SrcList_item *pSrc, /* Table we are trying to access */ Bitmask notReady /* Tables in outer loops of the join */ ){ char aff; if( pTerm->leftCursor!=pSrc->iCursor ) return 0; | | | 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 | static int termCanDriveIndex( WhereTerm *pTerm, /* WHERE clause term to check */ struct SrcList_item *pSrc, /* Table we are trying to access */ Bitmask notReady /* Tables in outer loops of the join */ ){ char aff; if( pTerm->leftCursor!=pSrc->iCursor ) return 0; if( (pTerm->eOperator & WO_EQ)==0 ) return 0; if( (pTerm->prereqRight & notReady)!=0 ) return 0; aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity; if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0; return 1; } #endif |
︙ | ︙ | |||
2050 2051 2052 2053 2054 2055 2056 | WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName)); /* Count the number of possible WHERE clause constraints referring ** to this virtual table */ for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){ if( pTerm->leftCursor != pSrc->iCursor ) continue; | | | | | 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 | WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName)); /* Count the number of possible WHERE clause constraints referring ** to this virtual table */ for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){ if( pTerm->leftCursor != pSrc->iCursor ) continue; assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) ); testcase( pTerm->eOperator & WO_IN ); testcase( pTerm->eOperator & WO_ISNULL ); if( pTerm->eOperator & (WO_ISNULL) ) continue; if( pTerm->wtFlags & TERM_VNULL ) continue; nTerm++; } /* If the ORDER BY clause contains only columns in the current ** virtual table then allocate space for the aOrderBy part of |
︙ | ︙ | |||
2103 2104 2105 2106 2107 2108 2109 | *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy; *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage = pUsage; for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){ u8 op; if( pTerm->leftCursor != pSrc->iCursor ) continue; | | | | | | 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 | *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy; *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage = pUsage; for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){ u8 op; if( pTerm->leftCursor != pSrc->iCursor ) continue; assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) ); testcase( pTerm->eOperator & WO_IN ); testcase( pTerm->eOperator & WO_ISNULL ); if( pTerm->eOperator & (WO_ISNULL) ) continue; if( pTerm->wtFlags & TERM_VNULL ) continue; pIdxCons[j].iColumn = pTerm->u.leftColumn; pIdxCons[j].iTermOffset = i; op = (u8)pTerm->eOperator & WO_ALL; if( op==WO_IN ) op = WO_EQ; pIdxCons[j].op = op; /* The direct assignment in the previous line is possible only because ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The ** following asserts verify this fact. */ assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ ); assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT ); |
︙ | ︙ | |||
2280 2281 2282 2283 2284 2285 2286 | */ 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]; if( (pTerm->prereqRight&p->notReady)==0 | | | 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 | */ 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]; if( (pTerm->prereqRight&p->notReady)==0 && (bAllowIN || (pTerm->eOperator & WO_IN)==0) ){ pIdxCons->usable = 1; }else{ pIdxCons->usable = 0; } } memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint); |
︙ | ︙ | |||
2312 2313 2314 2315 2316 2317 2318 | pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint; for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){ if( pUsage[i].argvIndex>0 ){ j = pIdxCons->iTermOffset; pTerm = &pWC->a[j]; p->cost.used |= pTerm->prereqRight; | | | 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 | pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint; for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){ if( pUsage[i].argvIndex>0 ){ j = pIdxCons->iTermOffset; pTerm = &pWC->a[j]; p->cost.used |= pTerm->prereqRight; if( (pTerm->eOperator & WO_IN)!=0 && pUsage[i].omit==0 ){ /* Do not attempt to use an IN constraint if the virtual table ** says that the equivalent EQ constraint cannot be safely omitted. ** If we do attempt to use such a constraint, some rows might be ** repeated in the output. */ break; } } |
︙ | ︙ | |||
2618 2619 2620 2621 2622 2623 2624 | tRowcnt iUpper = p->aiRowEst[0]; tRowcnt a[2]; u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity; if( pLower ){ Expr *pExpr = pLower->pExpr->pRight; rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal); | | | | | | 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 | tRowcnt iUpper = p->aiRowEst[0]; tRowcnt a[2]; u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity; if( pLower ){ Expr *pExpr = pLower->pExpr->pRight; rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal); assert( (pLower->eOperator & (WO_GT|WO_GE))!=0 ); if( rc==SQLITE_OK && whereKeyStats(pParse, p, pRangeVal, 0, a)==SQLITE_OK ){ iLower = a[0]; if( (pLower->eOperator & WO_GT)!=0 ) iLower += a[1]; } sqlite3ValueFree(pRangeVal); } if( rc==SQLITE_OK && pUpper ){ Expr *pExpr = pUpper->pExpr->pRight; rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal); assert( (pUpper->eOperator & (WO_LT|WO_LE))!=0 ); if( rc==SQLITE_OK && whereKeyStats(pParse, p, pRangeVal, 1, a)==SQLITE_OK ){ iUpper = a[0]; if( (pUpper->eOperator & WO_LE)!=0 ) iUpper += a[1]; } sqlite3ValueFree(pRangeVal); } if( rc==SQLITE_OK ){ if( iUpper<=iLower ){ *pRangeDiv = (double)p->aiRowEst[0]; }else{ |
︙ | ︙ | |||
2943 2944 2945 2946 2947 2948 2949 | /* If X is the column in the index and ORDER BY clause, check to see ** if there are any X= or X IS NULL constraints in the WHERE clause. */ pConstraint = findTerm(p->pWC, base, iColumn, p->notReady, WO_EQ|WO_ISNULL|WO_IN, pIdx); if( pConstraint==0 ){ isEq = 0; | | | | 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 | /* If X is the column in the index and ORDER BY clause, check to see ** if there are any X= or X IS NULL constraints in the WHERE clause. */ pConstraint = findTerm(p->pWC, base, iColumn, p->notReady, WO_EQ|WO_ISNULL|WO_IN, pIdx); if( pConstraint==0 ){ isEq = 0; }else if( (pConstraint->eOperator & WO_IN)!=0 ){ /* Constraints of the form: "X IN ..." cannot be used with an ORDER BY ** because we do not know in what order the values on the RHS of the IN ** operator will occur. */ break; }else if( (pConstraint->eOperator & WO_ISNULL)!=0 ){ uniqueNotNull = 0; isEq = 1; /* "X IS NULL" means X has only a single value */ }else if( pConstraint->prereqRight==0 ){ isEq = 1; /* Constraint "X=constant" means X has only a single value */ }else{ Expr *pRight = pConstraint->pExpr->pRight; if( pRight->op==TK_COLUMN ){ |
︙ | ︙ | |||
3361 3362 3363 3364 3365 3366 3367 | ** to get a better estimate on the number of rows based on ** VALUE and how common that value is according to the histogram. */ if( pc.plan.nRow>(double)1 && pc.plan.nEq==1 && pFirstTerm!=0 && aiRowEst[1]>1 ){ assert( (pFirstTerm->eOperator & (WO_EQ|WO_ISNULL|WO_IN))!=0 ); if( pFirstTerm->eOperator & (WO_EQ|WO_ISNULL) ){ | | | > | | 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 | ** to get a better estimate on the number of rows based on ** VALUE and how common that value is according to the histogram. */ if( pc.plan.nRow>(double)1 && pc.plan.nEq==1 && pFirstTerm!=0 && aiRowEst[1]>1 ){ assert( (pFirstTerm->eOperator & (WO_EQ|WO_ISNULL|WO_IN))!=0 ); if( pFirstTerm->eOperator & (WO_EQ|WO_ISNULL) ){ testcase( pFirstTerm->eOperator & WO_EQ ); testcase( pFirstTerm->eOperator & WO_EQUIV ); testcase( pFirstTerm->eOperator & WO_ISNULL ); whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight, &pc.plan.nRow); }else if( bInEst==0 ){ assert( pFirstTerm->eOperator & WO_IN ); whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList, &pc.plan.nRow); } } #endif /* SQLITE_ENABLE_STAT3 */ /* Adjust the number of output rows and downward to reflect rows |
︙ | ︙ | |||
3513 3514 3515 3516 3517 3518 3519 | ** set size by a factor of 3. Indexed range constraints reduce ** the search space by a larger factor: 4. We make indexed range ** more selective intentionally because of the subjective ** observation that indexed range constraints really are more ** selective in practice, on average. */ pc.plan.nRow /= 3; } | | | 3573 3574 3575 3576 3577 3578 3579 3580 3581 3582 3583 3584 3585 3586 3587 | ** set size by a factor of 3. Indexed range constraints reduce ** the search space by a larger factor: 4. We make indexed range ** more selective intentionally because of the subjective ** observation that indexed range constraints really are more ** selective in practice, on average. */ pc.plan.nRow /= 3; } }else if( (pTerm->eOperator & WO_NOOP)==0 ){ /* Any other expression lowers the output row count by half */ pc.plan.nRow /= 2; } } if( pc.plan.nRow<2 ) pc.plan.nRow = 2; } |
︙ | ︙ | |||
4149 4150 4151 4152 4153 4154 4155 | ** we reference multiple rows using a "rowid IN (...)" ** construct. */ iReleaseReg = sqlite3GetTempReg(pParse); pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0); assert( pTerm!=0 ); assert( pTerm->pExpr!=0 ); | < | 4209 4210 4211 4212 4213 4214 4215 4216 4217 4218 4219 4220 4221 4222 | ** we reference multiple rows using a "rowid IN (...)" ** construct. */ iReleaseReg = sqlite3GetTempReg(pParse); pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0); assert( pTerm!=0 ); assert( pTerm->pExpr!=0 ); assert( omitTable==0 ); testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */ iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg); addrNxt = pLevel->addrNxt; sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt); sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg); sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg); |
︙ | ︙ | |||
4540 4541 4542 4543 4544 4545 4546 | int iRetInit; /* Address of regReturn init */ int untestedTerms = 0; /* Some terms not completely tested */ int ii; /* Loop counter */ Expr *pAndExpr = 0; /* An ".. AND (...)" expression */ pTerm = pLevel->plan.u.pTerm; assert( pTerm!=0 ); | | | 4599 4600 4601 4602 4603 4604 4605 4606 4607 4608 4609 4610 4611 4612 4613 | int iRetInit; /* Address of regReturn init */ int untestedTerms = 0; /* Some terms not completely tested */ int ii; /* Loop counter */ Expr *pAndExpr = 0; /* An ".. AND (...)" expression */ pTerm = pLevel->plan.u.pTerm; assert( pTerm!=0 ); assert( pTerm->eOperator & WO_OR ); assert( (pTerm->wtFlags & TERM_ORINFO)!=0 ); pOrWc = &pTerm->u.pOrInfo->wc; pLevel->op = OP_Return; pLevel->p1 = regReturn; /* Set up a new SrcList in pOrTab containing the table being scanned ** by this loop in the a[0] slot and all notReady tables in a[1..] slots. |
︙ | ︙ | |||
4613 4614 4615 4616 4617 4618 4619 | if( pAndExpr ){ pAndExpr = sqlite3PExpr(pParse, TK_AND, 0, pAndExpr, 0); } } for(ii=0; ii<pOrWc->nTerm; ii++){ WhereTerm *pOrTerm = &pOrWc->a[ii]; | | | 4672 4673 4674 4675 4676 4677 4678 4679 4680 4681 4682 4683 4684 4685 4686 | if( pAndExpr ){ pAndExpr = sqlite3PExpr(pParse, TK_AND, 0, pAndExpr, 0); } } for(ii=0; ii<pOrWc->nTerm; ii++){ WhereTerm *pOrTerm = &pOrWc->a[ii]; if( pOrTerm->leftCursor==iCur || (pOrTerm->eOperator & WO_AND)!=0 ){ WhereInfo *pSubWInfo; /* Info for single OR-term scan */ Expr *pOrExpr = pOrTerm->pExpr; if( pAndExpr ){ pAndExpr->pLeft = pOrExpr; pOrExpr = pAndExpr; } /* Loop through table entries that match term pOrTerm. */ |
︙ | ︙ |