/ Changes On Branch left-join-optimization
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Changes In Branch left-join-optimization Excluding Merge-Ins

This is equivalent to a diff from 7fdb1e2ac2 to 618ca9fe53

2017-11-21
20:53
Update the omit-table-from-left-join optimization so that it can omit tables from the middle of the join as well as the end. (check-in: 0cd82ee9a8 user: dan tags: trunk)
19:22
Update the omit-table-from-left-join optimization so that it can omit tables from the middle of the join as well as the end. (Closed-Leaf check-in: 618ca9fe53 user: dan tags: left-join-optimization)
2017-11-20
15:46
Fix a problem preventing the planner from identifying scans that visit at most one row in cases where that property is guaranteed by a unique, not-null, non-IPK column that is the leftmost in its table. (check-in: 7fdb1e2ac2 user: dan tags: trunk)
15:45
Fix a typo in a test script on this branch. (Closed-Leaf check-in: bff5dcfd2b user: dan tags: left-join-omit-fix)
2017-11-18
18:07
Enhance the log messages produced in some cases if database corruption is encountered by an SQLITE_DEBUG build. (check-in: ee840a7669 user: dan tags: trunk)

Changes to src/where.c.

  4673   4673       }
  4674   4674       sqlite3DebugPrintf("\n");
  4675   4675       for(ii=0; ii<pWInfo->nLevel; ii++){
  4676   4676         whereLoopPrint(pWInfo->a[ii].pWLoop, sWLB.pWC);
  4677   4677       }
  4678   4678     }
  4679   4679   #endif
  4680         -  /* Attempt to omit tables from the join that do not effect the result */
         4680  +
         4681  +  /* Attempt to omit tables from the join that do not affect the result.
         4682  +  ** For a table to not affect the result, the following must be true:
         4683  +  **
         4684  +  **   1) The query must not be an aggregate.
         4685  +  **   2) The table must be the RHS of a LEFT JOIN.
         4686  +  **   3) Either the query must be DISTINCT, or else the ON or USING clause
         4687  +  **      must contain a constraint that limits the scan of the table to 
         4688  +  **      at most a single row.
         4689  +  **   4) The table must not be referenced by any part of the query apart
         4690  +  **      from its own USING or ON clause.
         4691  +  **
         4692  +  ** For example, given:
         4693  +  **
         4694  +  **     CREATE TABLE t1(ipk INTEGER PRIMARY KEY, v1);
         4695  +  **     CREATE TABLE t2(ipk INTEGER PRIMARY KEY, v2);
         4696  +  **     CREATE TABLE t3(ipk INTEGER PRIMARY KEY, v3);
         4697  +  **
         4698  +  ** then table t2 can be omitted from the following:
         4699  +  **
         4700  +  **     SELECT v1, v3 FROM t1 
         4701  +  **       LEFT JOIN t2 USING (t1.ipk=t2.ipk)
         4702  +  **       LEFT JOIN t3 USING (t1.ipk=t3.ipk)
         4703  +  **
         4704  +  ** or from:
         4705  +  **
         4706  +  **     SELECT DISTINCT v1, v3 FROM t1 
         4707  +  **       LEFT JOIN t2
         4708  +  **       LEFT JOIN t3 USING (t1.ipk=t3.ipk)
         4709  +  */
  4681   4710     if( pWInfo->nLevel>=2
  4682         -   && pResultSet!=0
         4711  +   && pResultSet!=0               /* guarantees condition (1) above */
  4683   4712      && OptimizationEnabled(db, SQLITE_OmitNoopJoin)
  4684   4713     ){
         4714  +    int i;
  4685   4715       Bitmask tabUsed = sqlite3WhereExprListUsage(pMaskSet, pResultSet);
  4686   4716       if( sWLB.pOrderBy ){
  4687   4717         tabUsed |= sqlite3WhereExprListUsage(pMaskSet, sWLB.pOrderBy);
  4688   4718       }
  4689         -    while( pWInfo->nLevel>=2 ){
         4719  +    for(i=pWInfo->nLevel-1; i>=1; i--){
  4690   4720         WhereTerm *pTerm, *pEnd;
  4691         -      pLoop = pWInfo->a[pWInfo->nLevel-1].pWLoop;
  4692         -      if( (pWInfo->pTabList->a[pLoop->iTab].fg.jointype & JT_LEFT)==0 ) break;
         4721  +      struct SrcList_item *pItem;
         4722  +      pLoop = pWInfo->a[i].pWLoop;
         4723  +      pItem = &pWInfo->pTabList->a[pLoop->iTab];
         4724  +      if( (pItem->fg.jointype & JT_LEFT)==0 ) continue;
  4693   4725         if( (wctrlFlags & WHERE_WANT_DISTINCT)==0
  4694   4726          && (pLoop->wsFlags & WHERE_ONEROW)==0
  4695   4727         ){
  4696         -        break;
         4728  +        continue;
  4697   4729         }
  4698         -      if( (tabUsed & pLoop->maskSelf)!=0 ) break;
         4730  +      if( (tabUsed & pLoop->maskSelf)!=0 ) continue;
  4699   4731         pEnd = sWLB.pWC->a + sWLB.pWC->nTerm;
  4700   4732         for(pTerm=sWLB.pWC->a; pTerm<pEnd; pTerm++){
  4701         -        if( (pTerm->prereqAll & pLoop->maskSelf)!=0
  4702         -         && !ExprHasProperty(pTerm->pExpr, EP_FromJoin)
  4703         -        ){
  4704         -          break;
         4733  +        if( (pTerm->prereqAll & pLoop->maskSelf)!=0 ){
         4734  +          if( !ExprHasProperty(pTerm->pExpr, EP_FromJoin)
         4735  +           || pTerm->pExpr->iRightJoinTable!=pItem->iCursor
         4736  +          ){
         4737  +            break;
         4738  +          }
  4705   4739           }
  4706   4740         }
  4707         -      if( pTerm<pEnd ) break;
         4741  +      if( pTerm<pEnd ) continue;
  4708   4742         WHERETRACE(0xffff, ("-> drop loop %c not used\n", pLoop->cId));
         4743  +      if( i!=pWInfo->nLevel-1 ){
         4744  +        int nByte = (pWInfo->nLevel-1-i) * sizeof(WhereLevel);
         4745  +        memmove(&pWInfo->a[i], &pWInfo->a[i+1], nByte);
         4746  +      }
  4709   4747         pWInfo->nLevel--;
  4710   4748         nTabList--;
  4711   4749       }
  4712   4750     }
  4713   4751     WHERETRACE(0xffff,("*** Optimizer Finished ***\n"));
  4714   4752     pWInfo->pParse->nQueryLoop += pWInfo->nRowOut;
  4715   4753   
................................................................................
  4986   5024       }
  4987   5025   #endif
  4988   5026       if( pLevel->iLeftJoin ){
  4989   5027         int ws = pLoop->wsFlags;
  4990   5028         addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin); VdbeCoverage(v);
  4991   5029         assert( (ws & WHERE_IDX_ONLY)==0 || (ws & WHERE_INDEXED)!=0 );
  4992   5030         if( (ws & WHERE_IDX_ONLY)==0 ){
  4993         -        sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);
         5031  +        assert( pLevel->iTabCur==pTabList->a[pLevel->iFrom].iCursor );
         5032  +        sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iTabCur);
  4994   5033         }
  4995   5034         if( (ws & WHERE_INDEXED) 
  4996   5035          || ((ws & WHERE_MULTI_OR) && pLevel->u.pCovidx) 
  4997   5036         ){
  4998   5037           sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iIdxCur);
  4999   5038         }
  5000   5039         if( pLevel->op==OP_Return ){

Changes to test/join2.test.

   118    118   
   119    119   do_eqp_test 3.2 {
   120    120     SELECT v2 FROM t1 LEFT JOIN t2 USING (k2) LEFT JOIN t3_2 USING (k3);
   121    121   } {
   122    122     0 0 0 {SCAN TABLE t1} 
   123    123     0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
   124    124   }
          125  +
          126  +#-------------------------------------------------------------------------
          127  +# Test that tables other than the rightmost can be omitted from a
          128  +# LEFT JOIN query.
          129  +#
          130  +do_execsql_test 4.0 {
          131  +  CREATE TABLE c1(k INTEGER PRIMARY KEY, v1);
          132  +  CREATE TABLE c2(k INTEGER PRIMARY KEY, v2);
          133  +  CREATE TABLE c3(k INTEGER PRIMARY KEY, v3);
          134  +
          135  +  INSERT INTO c1 VALUES(1, 2);
          136  +  INSERT INTO c2 VALUES(2, 3);
          137  +  INSERT INTO c3 VALUES(3, 'v3');
          138  +
          139  +  INSERT INTO c1 VALUES(111, 1112);
          140  +  INSERT INTO c2 VALUES(112, 1113);
          141  +  INSERT INTO c3 VALUES(113, 'v1113');
          142  +}
          143  +do_execsql_test 4.1.1 {
          144  +  SELECT v1, v3 FROM c1 LEFT JOIN c2 ON (c2.k=v1) LEFT JOIN c3 ON (c3.k=v2);
          145  +} {2 v3 1112 {}}
          146  +do_execsql_test 4.1.2 {
          147  +  SELECT v1, v3 FROM c1 LEFT JOIN c2 ON (c2.k=v1) LEFT JOIN c3 ON (c3.k=v1+1);
          148  +} {2 v3 1112 {}}
          149  +
          150  +do_execsql_test 4.1.3 {
          151  +  SELECT DISTINCT v1, v3 FROM c1 LEFT JOIN c2 LEFT JOIN c3 ON (c3.k=v1+1);
          152  +} {2 v3 1112 {}}
          153  +
          154  +do_execsql_test 4.1.4 {
          155  +  SELECT v1, v3 FROM c1 LEFT JOIN c2 LEFT JOIN c3 ON (c3.k=v1+1);
          156  +} {2 v3 2 v3 1112 {} 1112 {}}
          157  +
          158  +do_eqp_test 4.2.1 {
          159  +  SELECT v1, v3 FROM c1 LEFT JOIN c2 ON (c2.k=v1) LEFT JOIN c3 ON (c3.k=v2);
          160  +} {
          161  +  0 0 0 {SCAN TABLE c1} 
          162  +  0 1 1 {SEARCH TABLE c2 USING INTEGER PRIMARY KEY (rowid=?)}
          163  +  0 2 2 {SEARCH TABLE c3 USING INTEGER PRIMARY KEY (rowid=?)}
          164  +}
          165  +do_eqp_test 4.2.2 {
          166  +  SELECT v1, v3 FROM c1 LEFT JOIN c2 ON (c2.k=v1) LEFT JOIN c3 ON (c3.k=v1+1);
          167  +} {
          168  +  0 0 0 {SCAN TABLE c1} 
          169  +  0 1 2 {SEARCH TABLE c3 USING INTEGER PRIMARY KEY (rowid=?)}
          170  +}
          171  +
          172  +
   125    173   
   126    174   finish_test