Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Use transitivity to move constraints into the outer loops of a join whenever possible, thereby reducing the amount of work that needs to occur in inner loops. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
5f4907e1c6230e3dd904bd99e1c48c57 |
User & Date: | drh 2013-04-22 02:39:10.341 |
References
2013-07-01
| ||
16:47 | • New ticket [868145d012] Assertion fault on double LEFT JOIN. (artifact: 7bb99dad20 user: drh) | |
Context
2013-04-22
| ||
13:51 | Enhanced documentation for the SQLITE_CONFIG_SQLLOG mechanism and the test_sqllog.c demonstration file. No changes to code. (check-in: 206caf21f6 user: drh tags: trunk) | |
02:39 | Use transitivity to move constraints into the outer loops of a join whenever possible, thereby reducing the amount of work that needs to occur in inner loops. (check-in: 5f4907e1c6 user: drh tags: trunk) | |
2013-04-19
| ||
12:32 | Add the "warning" command to the TCL test infrastructure. Fix problems with the loadext.test module. (check-in: 514adbbd8c user: drh tags: trunk) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
4157 4158 4159 4160 4161 4162 4163 4164 4165 4166 4167 4168 4169 4170 4171 4172 4173 4174 4175 4176 4177 4178 4179 4180 | Parse *pParse; /* Parsing context */ Vdbe *v; /* The prepared stmt under constructions */ struct SrcList_item *pTabItem; /* FROM clause term being coded */ int addrBrk; /* Jump here to break out of the loop */ int addrCont; /* Jump here to continue with next cycle */ int iRowidReg = 0; /* Rowid is stored in this register, if not zero */ int iReleaseReg = 0; /* Temp register to free before returning */ pParse = pWInfo->pParse; v = pParse->pVdbe; pWC = pWInfo->pWC; pLevel = &pWInfo->a[iLevel]; pTabItem = &pWInfo->pTabList->a[pLevel->iFrom]; iCur = pTabItem->iCursor; bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0; omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0 && (wctrlFlags & WHERE_FORCE_TABLE)==0; /* Create labels for the "break" and "continue" instructions ** for the current loop. Jump to addrBrk to break out of a loop. ** Jump to cont to go immediately to the next iteration of the ** loop. ** ** When there is an IN operator, we also have a "addrNxt" label that | > > | 4157 4158 4159 4160 4161 4162 4163 4164 4165 4166 4167 4168 4169 4170 4171 4172 4173 4174 4175 4176 4177 4178 4179 4180 4181 4182 | Parse *pParse; /* Parsing context */ Vdbe *v; /* The prepared stmt under constructions */ struct SrcList_item *pTabItem; /* FROM clause term being coded */ int addrBrk; /* Jump here to break out of the loop */ int addrCont; /* Jump here to continue with next cycle */ int iRowidReg = 0; /* Rowid is stored in this register, if not zero */ int iReleaseReg = 0; /* Temp register to free before returning */ Bitmask newNotReady; /* Return value */ pParse = pWInfo->pParse; v = pParse->pVdbe; pWC = pWInfo->pWC; pLevel = &pWInfo->a[iLevel]; pTabItem = &pWInfo->pTabList->a[pLevel->iFrom]; iCur = pTabItem->iCursor; bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0; omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0 && (wctrlFlags & WHERE_FORCE_TABLE)==0; VdbeNoopComment((v, "Begin Join Loop %d", iLevel)); /* Create labels for the "break" and "continue" instructions ** for the current loop. Jump to addrBrk to break out of a loop. ** Jump to cont to go immediately to the next iteration of the ** loop. ** ** When there is an IN operator, we also have a "addrNxt" label that |
︙ | ︙ | |||
4817 4818 4819 4820 4821 4822 4823 | assert( bRev==0 || bRev==1 ); assert( omitTable==0 ); pLevel->op = aStep[bRev]; pLevel->p1 = iCur; pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk); pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; } | | | > > > > > > > > > > > > > > > > > > > > > > > > > > | | | 4819 4820 4821 4822 4823 4824 4825 4826 4827 4828 4829 4830 4831 4832 4833 4834 4835 4836 4837 4838 4839 4840 4841 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 4873 4874 4875 4876 4877 4878 4879 4880 4881 4882 4883 4884 4885 4886 4887 4888 4889 4890 4891 4892 4893 4894 4895 4896 4897 4898 4899 4900 4901 4902 4903 4904 4905 4906 4907 4908 4909 4910 4911 | assert( bRev==0 || bRev==1 ); assert( omitTable==0 ); pLevel->op = aStep[bRev]; pLevel->p1 = iCur; pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk); pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; } newNotReady = notReady & ~getMask(pWC->pMaskSet, iCur); /* Insert code to test every subexpression that can be completely ** computed using the current set of tables. ** ** IMPLEMENTATION-OF: R-49525-50935 Terms that cannot be satisfied through ** the use of indices become tests that are evaluated against each row of ** the relevant input tables. */ for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){ Expr *pE; testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* IMP: R-30575-11662 */ testcase( pTerm->wtFlags & TERM_CODED ); if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue; if( (pTerm->prereqAll & newNotReady)!=0 ){ testcase( pWInfo->untestedTerms==0 && (pWInfo->wctrlFlags & WHERE_ONETABLE_ONLY)!=0 ); pWInfo->untestedTerms = 1; continue; } pE = pTerm->pExpr; assert( pE!=0 ); if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){ continue; } sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL); pTerm->wtFlags |= TERM_CODED; } /* Insert code to test for implied constraints based on transitivity ** of the "==" operator. ** ** Example: If the WHERE clause contains "t1.a=t2.b" and "t2.b=123" ** and we are coding the t1 loop and the t2 loop has not yet coded, ** then we cannot use the "t1.a=t2.b" constraint, but we can code ** the implied "t1.a=123" constraint. */ for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){ Expr *pE; WhereTerm *pAlt; Expr sEq; if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue; if( pTerm->eOperator!=(WO_EQUIV|WO_EQ) ) continue; if( pTerm->leftCursor!=iCur ) continue; pE = pTerm->pExpr; assert( !ExprHasProperty(pE, EP_FromJoin) ); assert( (pTerm->prereqRight & newNotReady)!=0 ); pAlt = findTerm(pWC, iCur, pTerm->u.leftColumn, notReady, WO_EQ|WO_IN, 0); if( pAlt==0 ) continue; VdbeNoopComment((v, "begin transitive constraint")); sEq = *pAlt->pExpr; sEq.pLeft = pE->pLeft; sqlite3ExprIfFalse(pParse, &sEq, addrCont, SQLITE_JUMPIFNULL); } /* For a LEFT OUTER JOIN, generate code that will record the fact that ** at least one row of the right table has matched the left table. */ if( pLevel->iLeftJoin ){ pLevel->addrFirst = sqlite3VdbeCurrentAddr(v); sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin); VdbeComment((v, "record LEFT JOIN hit")); sqlite3ExprCacheClear(pParse); for(pTerm=pWC->a, j=0; j<pWC->nTerm; j++, pTerm++){ testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* IMP: R-30575-11662 */ testcase( pTerm->wtFlags & TERM_CODED ); if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue; if( (pTerm->prereqAll & newNotReady)!=0 ){ assert( pWInfo->untestedTerms ); continue; } assert( pTerm->pExpr ); sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL); pTerm->wtFlags |= TERM_CODED; } } sqlite3ReleaseTempReg(pParse, iReleaseReg); return newNotReady; } #if defined(SQLITE_TEST) /* ** The following variable holds a text description of query plan generated ** by the most recent call to sqlite3WhereBegin(). Each call to WhereBegin ** overwrites the previous. This information is used for testing and |
︙ | ︙ |