From a76ac88af86bb5a3753b7fec6c86bfcfaf64f439 Mon Sep 17 00:00:00 2001 From: drh <> Date: Fri, 8 Apr 2022 19:20:12 +0000 Subject: Preliminary code to support RIGHT JOIN. Everything seems to work, except that the code to compute the unmatched rows for the RIGHT JOIN has not yet been added, so the result of a RIGHT JOIN is currently the same as an INNER JOIN. FossilOrigin-Name: 415abd6731b8e8a605adabfa6066c8a852a8531c300df41325d5f7e75cae5a70 --- src/wherecode.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'src/wherecode.c') diff --git a/src/wherecode.c b/src/wherecode.c index bab514a69..d349a9402 100644 --- a/src/wherecode.c +++ b/src/wherecode.c @@ -2604,7 +2604,9 @@ Bitmask sqlite3WhereCodeOneLoopStart( } pE = pTerm->pExpr; assert( pE!=0 ); - if( (pTabItem->fg.jointype&JT_LEFT) && !ExprHasProperty(pE,EP_FromJoin) ){ + if( (pTabItem->fg.jointype & (JT_LEFT|JT_LTORJ)) + && !ExprHasProperty(pE,EP_FromJoin) + ){ continue; } @@ -2666,7 +2668,7 @@ Bitmask sqlite3WhereCodeOneLoopStart( if( (pTerm->eOperator & (WO_EQ|WO_IS))==0 ) continue; if( (pTerm->eOperator & WO_EQUIV)==0 ) continue; if( pTerm->leftCursor!=iCur ) continue; - if( pTabItem->fg.jointype & JT_LEFT ) continue; + if( pTabItem->fg.jointype & (JT_LEFT|JT_LTORJ) ) continue; pE = pTerm->pExpr; #ifdef WHERETRACE_ENABLED /* 0x800 */ if( sqlite3WhereTrace & 0x800 ){ -- cgit v1.2.3 From c2308ad2a0cb4f6d957518c615d308ed79b42d04 Mon Sep 17 00:00:00 2001 From: drh <> Date: Sat, 9 Apr 2022 03:16:26 +0000 Subject: A few bits and bobs of code generation toward getting RIGHT JOIN to work. Much more remains to do. FossilOrigin-Name: 55b4543122646997d928598343bc467c993f971e86e9037c85430cc948750576 --- src/wherecode.c | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+) (limited to 'src/wherecode.c') diff --git a/src/wherecode.c b/src/wherecode.c index 74873de09..5b8ed8934 100644 --- a/src/wherecode.c +++ b/src/wherecode.c @@ -2721,6 +2721,41 @@ Bitmask sqlite3WhereCodeOneLoopStart( } } + /* For a RIGHT OUTER JOIN, record the fact that the current row has + ** been matched at least once. + */ + if( pLevel->iRJMatch ){ + Table *pTab; + int nPk; + int r; + int jmp1 = 0; + + pTab = pWInfo->pTabList->a[pLevel->iFrom].pTab; + if( HasRowid(pTab) ){ + r = sqlite3GetTempRange(pParse, 2); + sqlite3ExprCodeGetColumnOfTable(v, pTab, pLevel->iTabCur, -1, r+1); + nPk = 1; + }else{ + int iPk; + Index *pPk = sqlite3PrimaryKeyIndex(pTab); + nPk = pPk->nKeyCol; + r = sqlite3GetTempRange(pParse, nPk+1); + for(iPk=0; iPkaiColumn[iPk]; + sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, iCol,r+1+iPk); + } + } + jmp1 = sqlite3VdbeAddOp4Int(v, OP_Found, pLevel->iRJMatch, 0, r+1, nPk); + VdbeCoverage(v); + sqlite3VdbeAddOp3(v, OP_MakeRecord, r+1, nPk, r); + sqlite3VdbeAddOp4Int(v, OP_IdxInsert, pLevel->iRJMatch, r, r+1, nPk); + sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT); + sqlite3VdbeJumpHere(v, jmp1); + + /* Release the array of temp registers */ + sqlite3ReleaseTempRange(pParse, r, nPk+1); + } + #if WHERETRACE_ENABLED /* 0x20800 */ if( sqlite3WhereTrace & 0x20000 ){ sqlite3DebugPrintf("All WHERE-clause terms after coding level %d:\n", -- cgit v1.2.3 From 7c1734b09e436176c2aac461e835c29532403ad4 Mon Sep 17 00:00:00 2001 From: drh <> Date: Sat, 9 Apr 2022 12:27:20 +0000 Subject: The interior of the RIGHT JOIN loop is now a subroutine. FossilOrigin-Name: 549f5a7ee639de80f049445002f58e93c805f9a3d3db1987ec9d139ccef4805e --- src/wherecode.c | 24 +++++++++++++++++++----- 1 file changed, 19 insertions(+), 5 deletions(-) (limited to 'src/wherecode.c') diff --git a/src/wherecode.c b/src/wherecode.c index 5b8ed8934..853646c71 100644 --- a/src/wherecode.c +++ b/src/wherecode.c @@ -2724,12 +2724,18 @@ Bitmask sqlite3WhereCodeOneLoopStart( /* For a RIGHT OUTER JOIN, record the fact that the current row has ** been matched at least once. */ - if( pLevel->iRJMatch ){ + if( pLevel->pRJ ){ Table *pTab; int nPk; int r; int jmp1 = 0; + WhereRightJoin *pRJ = pLevel->pRJ; + /* pTab is the right-hand table of the RIGHT JOIN. Generate code that + ** will record that the current row of that table has been matched at + ** least once. This is accomplished by storing the PK for the row in + ** both the iMatch index and the regBloom Bloom filter. + */ pTab = pWInfo->pTabList->a[pLevel->iFrom].pTab; if( HasRowid(pTab) ){ r = sqlite3GetTempRange(pParse, 2); @@ -2745,15 +2751,23 @@ Bitmask sqlite3WhereCodeOneLoopStart( sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, iCol,r+1+iPk); } } - jmp1 = sqlite3VdbeAddOp4Int(v, OP_Found, pLevel->iRJMatch, 0, r+1, nPk); + jmp1 = sqlite3VdbeAddOp4Int(v, OP_Found, pRJ->iMatch, 0, r+1, nPk); VdbeCoverage(v); sqlite3VdbeAddOp3(v, OP_MakeRecord, r+1, nPk, r); - sqlite3VdbeAddOp4Int(v, OP_IdxInsert, pLevel->iRJMatch, r, r+1, nPk); + sqlite3VdbeAddOp4Int(v, OP_IdxInsert, pRJ->iMatch, r, r+1, nPk); + sqlite3VdbeAddOp4Int(v, OP_FilterAdd, pRJ->regBloom, 0, r+1, nPk); sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT); sqlite3VdbeJumpHere(v, jmp1); - - /* Release the array of temp registers */ sqlite3ReleaseTempRange(pParse, r, nPk+1); + + /* Create a subroutine used to process all interior loops and code + ** of the RIGHT JOIN. During normal operation, the subroutine will + ** be in-line with the rest of the code. But at the end, a separate + ** loop will run that invokes this subroutine for unmatched rows + ** of pTab, with all tables to left begin set to NULL. + */ + sqlite3VdbeAddOp2(v, OP_BeginSubrtn, 0, pRJ->regReturn); + pRJ->addrSubrtn = sqlite3VdbeCurrentAddr(v); } #if WHERETRACE_ENABLED /* 0x20800 */ -- cgit v1.2.3 From c583719b65d2fca51178d40826f3b325329fe12a Mon Sep 17 00:00:00 2001 From: drh <> Date: Mon, 11 Apr 2022 14:26:37 +0000 Subject: Show LEFT and RIGHT JOIN processing in the EXPLAIN QUERY PLAN output. FossilOrigin-Name: d91faeffea5cf0585fb71e5311fdcc6b8be85c7e9c732050b4448e617c970101 --- src/wherecode.c | 13 ++++++++----- 1 file changed, 8 insertions(+), 5 deletions(-) (limited to 'src/wherecode.c') diff --git a/src/wherecode.c b/src/wherecode.c index 0c8104867..410d6f206 100644 --- a/src/wherecode.c +++ b/src/wherecode.c @@ -204,6 +204,9 @@ int sqlite3WhereExplainOneScan( pLoop->u.vtab.idxNum, pLoop->u.vtab.idxStr); } #endif + if( pItem->fg.jointype & JT_LEFT ){ + sqlite3_str_appendf(&str, " LEFT-JOIN"); + } #ifdef SQLITE_EXPLAIN_ESTIMATED_ROWS if( pLoop->nOut>=10 ){ sqlite3_str_appendf(&str, " (~%llu rows)", @@ -1150,7 +1153,7 @@ static void codeDeferredSeek( pWInfo->bDeferredSeek = 1; sqlite3VdbeAddOp3(v, OP_DeferredSeek, iIdxCur, 0, iCur); - if( (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE) + if( (pWInfo->wctrlFlags & (WHERE_OR_SUBCLAUSE|WHERE_RIGHT_JOIN)) && DbMaskAllZero(sqlite3ParseToplevel(pParse)->writeMask) ){ int i; @@ -1502,7 +1505,7 @@ Bitmask sqlite3WhereCodeOneLoopStart( ** initialize a memory cell that records if this table matches any ** row of the left table of the join. */ - assert( (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE) + assert( (pWInfo->wctrlFlags & (WHERE_OR_SUBCLAUSE|WHERE_RIGHT_JOIN)) || pLevel->iFrom>0 || (pTabItem[0].fg.jointype & JT_LEFT)==0 ); if( pLevel->iFrom>0 && (pTabItem[0].fg.jointype & JT_LEFT)!=0 ){ @@ -2140,7 +2143,7 @@ Bitmask sqlite3WhereCodeOneLoopStart( /* Seek the table cursor, if required */ omitTable = (pLoop->wsFlags & WHERE_IDX_ONLY)!=0 - && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)==0; + && (pWInfo->wctrlFlags & (WHERE_OR_SUBCLAUSE|WHERE_RIGHT_JOIN))==0; if( omitTable ){ /* pIdx is a covering index. No need to access the main table. */ }else if( HasRowid(pIdx->pTable) ){ @@ -2174,7 +2177,7 @@ Bitmask sqlite3WhereCodeOneLoopStart( ** move forward to the next index. ** https://sqlite.org/src/info/4e8e4857d32d401f */ - if( (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)==0 ){ + if( (pWInfo->wctrlFlags & (WHERE_OR_SUBCLAUSE|WHERE_RIGHT_JOIN))==0 ){ whereIndexExprTrans(pIdx, iCur, iIdxCur, pWInfo); } @@ -2193,7 +2196,7 @@ Bitmask sqlite3WhereCodeOneLoopStart( /* The following assert() is not a requirement, merely an observation: ** The OR-optimization doesn't work for the right hand table of ** a LEFT JOIN: */ - assert( (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)==0 ); + assert( (pWInfo->wctrlFlags & (WHERE_OR_SUBCLAUSE|WHERE_RIGHT_JOIN))==0 ); } /* Record the instruction used to terminate the loop. */ -- cgit v1.2.3 From 949e2ab49a8a815796d491506651043dd7d5fb55 Mon Sep 17 00:00:00 2001 From: drh <> Date: Tue, 12 Apr 2022 18:04:29 +0000 Subject: Factor out the RIGHT JOIN non-matched row loop from sqlite3WhereEnd(). This reduces the register pressure on that routine and helps it to run faster in the common case where there is no RIGHT JOIN. FossilOrigin-Name: beeecf1604d4fb11e45058f48cb2289c6542e0bc218d63a245198113d8d5476b --- src/wherecode.c | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 76 insertions(+) (limited to 'src/wherecode.c') diff --git a/src/wherecode.c b/src/wherecode.c index 410d6f206..d2cb85aee 100644 --- a/src/wherecode.c +++ b/src/wherecode.c @@ -2786,3 +2786,79 @@ Bitmask sqlite3WhereCodeOneLoopStart( #endif return pLevel->notReady; } + +/* +** Generate the code for the loop that finds all non-matched terms +** for a RIGHT JOIN. +*/ +SQLITE_NOINLINE void sqlite3WhereRightJoinLoop( + WhereInfo *pWInfo, + int iLevel, + WhereLevel *pLevel +){ + Parse *pParse = pWInfo->pParse; + Vdbe *v = pParse->pVdbe; + WhereRightJoin *pRJ = pLevel->pRJ; + Expr *pSubWhere = 0; + WhereClause *pWC = &pWInfo->sWC; + WhereInfo *pSubWInfo; + WhereLoop *pLoop = pLevel->pWLoop; + SrcItem *pTabItem = &pWInfo->pTabList->a[pLevel->iFrom]; + SrcList sFrom; + Bitmask mAll = 0; + int k; + + for(k=0; ka[k].pWLoop->maskSelf; + sqlite3VdbeAddOp1(v, OP_NullRow, pWInfo->a[k].iTabCur); + iIdxCur = pWInfo->a[k].iIdxCur; + if( iIdxCur ){ + sqlite3VdbeAddOp1(v, OP_NullRow, iIdxCur); + } + } + mAll |= pLoop->maskSelf; + for(k=0; knTerm; k++){ + WhereTerm *pTerm = &pWC->a[k]; + if( pTerm->wtFlags & TERM_VIRTUAL ) break; + if( pTerm->prereqAll & ~mAll ) continue; + if( ExprHasProperty(pTerm->pExpr, EP_FromJoin|EP_InnerJoin) ) continue; + pSubWhere = sqlite3ExprAnd(pParse, pSubWhere, + sqlite3ExprDup(pParse->db, pTerm->pExpr, 0)); + } + sFrom.nSrc = 1; + sFrom.nAlloc = 1; + memcpy(&sFrom.a[0], pTabItem, sizeof(SrcItem)); + sFrom.a[0].fg.jointype = 0; + ExplainQueryPlan((pParse, 1, "RIGHT-JOIN %s", pTabItem->pTab->zName)); + pSubWInfo = sqlite3WhereBegin(pParse, &sFrom, pSubWhere, 0, 0, 0, + WHERE_RIGHT_JOIN, 0); + if( pSubWInfo ){ + int iCur = pLevel->iTabCur; + int r = ++pParse->nMem; + int nPk; + int jmp; + int addrCont = sqlite3WhereContinueLabel(pSubWInfo); + Table *pTab = pTabItem->pTab; + if( HasRowid(pTab) ){ + sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, -1, r); + nPk = 1; + }else{ + int iPk; + Index *pPk = sqlite3PrimaryKeyIndex(pTab); + nPk = pPk->nKeyCol; + pParse->nMem += nPk - 1; + for(iPk=0; iPkaiColumn[iPk]; + sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, iCol,r+iPk); + } + } + jmp = sqlite3VdbeAddOp4Int(v, OP_Filter, pRJ->regBloom, 0, r, nPk); + sqlite3VdbeAddOp4Int(v, OP_Found, pRJ->iMatch, addrCont, r, nPk); + sqlite3VdbeJumpHere(v, jmp); + sqlite3VdbeAddOp2(v, OP_Gosub, pRJ->regReturn, pRJ->addrSubrtn); + sqlite3WhereEnd(pSubWInfo); + } + sqlite3ExprDelete(pParse->db, pSubWhere); + ExplainQueryPlanPop(pParse); +} -- cgit v1.2.3 From 146e64d2e4f9ef6e3ce55eb87ebaeca794ec9396 Mon Sep 17 00:00:00 2001 From: drh <> Date: Wed, 13 Apr 2022 01:52:32 +0000 Subject: Add missing VdbeCoverage() macros on new branch byte-code opcodes. FossilOrigin-Name: 218c7167e562f5c327124f02a92de85079315320a221fb0508310d927596b14c --- src/wherecode.c | 2 ++ 1 file changed, 2 insertions(+) (limited to 'src/wherecode.c') diff --git a/src/wherecode.c b/src/wherecode.c index d2cb85aee..a438db530 100644 --- a/src/wherecode.c +++ b/src/wherecode.c @@ -2854,7 +2854,9 @@ SQLITE_NOINLINE void sqlite3WhereRightJoinLoop( } } jmp = sqlite3VdbeAddOp4Int(v, OP_Filter, pRJ->regBloom, 0, r, nPk); + VdbeCoverage(v); sqlite3VdbeAddOp4Int(v, OP_Found, pRJ->iMatch, addrCont, r, nPk); + VdbeCoverage(v); sqlite3VdbeJumpHere(v, jmp); sqlite3VdbeAddOp2(v, OP_Gosub, pRJ->regReturn, pRJ->addrSubrtn); sqlite3WhereEnd(pSubWInfo); -- cgit v1.2.3