/ Check-in [0cd82ee9]
Login
Overview
Comment: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.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256:0cd82ee9a8413cf127b5ca65770e3f363bd579941cd592298d3b0c27715583f3
User & Date: dan 2017-11-21 20:53:14
References
2017-11-23
04:45
Fix a problem in the omit-table-from-left-join optimization from check-in [0cd82ee9a8413cf] that was discovered by OSSFuzz. check-in: b016c28f user: drh tags: trunk
Context
2017-11-21
21:14
Fix compilation issue (C99-ism) in the shell seen with MSVC. check-in: 9cb47430 user: mistachkin tags: trunk
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: 0cd82ee9 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: 618ca9fe 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: 7fdb1e2a user: dan tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

4673
4674
4675
4676
4677
4678
4679

4680




























4681
4682
4683
4684

4685
4686
4687
4688
4689
4690

4691
4692

4693
4694
4695
4696
4697
4698
4699
4700
4701
4702

4703
4704
4705
4706

4707
4708




4709
4710
4711
4712
4713
4714
4715
....
4986
4987
4988
4989
4990
4991
4992

4993
4994
4995
4996
4997
4998
4999
5000
    }
    sqlite3DebugPrintf("\n");
    for(ii=0; ii<pWInfo->nLevel; ii++){
      whereLoopPrint(pWInfo->a[ii].pWLoop, sWLB.pWC);
    }
  }
#endif

  /* Attempt to omit tables from the join that do not effect the result */




























  if( pWInfo->nLevel>=2
   && pResultSet!=0
   && OptimizationEnabled(db, SQLITE_OmitNoopJoin)
  ){

    Bitmask tabUsed = sqlite3WhereExprListUsage(pMaskSet, pResultSet);
    if( sWLB.pOrderBy ){
      tabUsed |= sqlite3WhereExprListUsage(pMaskSet, sWLB.pOrderBy);
    }
    while( pWInfo->nLevel>=2 ){
      WhereTerm *pTerm, *pEnd;

      pLoop = pWInfo->a[pWInfo->nLevel-1].pWLoop;
      if( (pWInfo->pTabList->a[pLoop->iTab].fg.jointype & JT_LEFT)==0 ) break;

      if( (wctrlFlags & WHERE_WANT_DISTINCT)==0
       && (pLoop->wsFlags & WHERE_ONEROW)==0
      ){
        break;
      }
      if( (tabUsed & pLoop->maskSelf)!=0 ) break;
      pEnd = sWLB.pWC->a + sWLB.pWC->nTerm;
      for(pTerm=sWLB.pWC->a; pTerm<pEnd; pTerm++){
        if( (pTerm->prereqAll & pLoop->maskSelf)!=0
         && !ExprHasProperty(pTerm->pExpr, EP_FromJoin)

        ){
          break;
        }
      }

      if( pTerm<pEnd ) break;
      WHERETRACE(0xffff, ("-> drop loop %c not used\n", pLoop->cId));




      pWInfo->nLevel--;
      nTabList--;
    }
  }
  WHERETRACE(0xffff,("*** Optimizer Finished ***\n"));
  pWInfo->pParse->nQueryLoop += pWInfo->nRowOut;

................................................................................
    }
#endif
    if( pLevel->iLeftJoin ){
      int ws = pLoop->wsFlags;
      addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin); VdbeCoverage(v);
      assert( (ws & WHERE_IDX_ONLY)==0 || (ws & WHERE_INDEXED)!=0 );
      if( (ws & WHERE_IDX_ONLY)==0 ){

        sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);
      }
      if( (ws & WHERE_INDEXED) 
       || ((ws & WHERE_MULTI_OR) && pLevel->u.pCovidx) 
      ){
        sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iIdxCur);
      }
      if( pLevel->op==OP_Return ){







>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

|


>




|

>
|
|
>



|

|


|
|
>
|
|
|
|
>
|

>
>
>
>







 







>
|







4673
4674
4675
4676
4677
4678
4679
4680
4681
4682
4683
4684
4685
4686
4687
4688
4689
4690
4691
4692
4693
4694
4695
4696
4697
4698
4699
4700
4701
4702
4703
4704
4705
4706
4707
4708
4709
4710
4711
4712
4713
4714
4715
4716
4717
4718
4719
4720
4721
4722
4723
4724
4725
4726
4727
4728
4729
4730
4731
4732
4733
4734
4735
4736
4737
4738
4739
4740
4741
4742
4743
4744
4745
4746
4747
4748
4749
4750
4751
4752
4753
....
5024
5025
5026
5027
5028
5029
5030
5031
5032
5033
5034
5035
5036
5037
5038
5039
    }
    sqlite3DebugPrintf("\n");
    for(ii=0; ii<pWInfo->nLevel; ii++){
      whereLoopPrint(pWInfo->a[ii].pWLoop, sWLB.pWC);
    }
  }
#endif

  /* Attempt to omit tables from the join that do not affect the result.
  ** For a table to not affect the result, the following must be true:
  **
  **   1) The query must not be an aggregate.
  **   2) The table must be the RHS of a LEFT JOIN.
  **   3) Either the query must be DISTINCT, or else the ON or USING clause
  **      must contain a constraint that limits the scan of the table to 
  **      at most a single row.
  **   4) The table must not be referenced by any part of the query apart
  **      from its own USING or ON clause.
  **
  ** For example, given:
  **
  **     CREATE TABLE t1(ipk INTEGER PRIMARY KEY, v1);
  **     CREATE TABLE t2(ipk INTEGER PRIMARY KEY, v2);
  **     CREATE TABLE t3(ipk INTEGER PRIMARY KEY, v3);
  **
  ** then table t2 can be omitted from the following:
  **
  **     SELECT v1, v3 FROM t1 
  **       LEFT JOIN t2 USING (t1.ipk=t2.ipk)
  **       LEFT JOIN t3 USING (t1.ipk=t3.ipk)
  **
  ** or from:
  **
  **     SELECT DISTINCT v1, v3 FROM t1 
  **       LEFT JOIN t2
  **       LEFT JOIN t3 USING (t1.ipk=t3.ipk)
  */
  if( pWInfo->nLevel>=2
   && pResultSet!=0               /* guarantees condition (1) above */
   && OptimizationEnabled(db, SQLITE_OmitNoopJoin)
  ){
    int i;
    Bitmask tabUsed = sqlite3WhereExprListUsage(pMaskSet, pResultSet);
    if( sWLB.pOrderBy ){
      tabUsed |= sqlite3WhereExprListUsage(pMaskSet, sWLB.pOrderBy);
    }
    for(i=pWInfo->nLevel-1; i>=1; i--){
      WhereTerm *pTerm, *pEnd;
      struct SrcList_item *pItem;
      pLoop = pWInfo->a[i].pWLoop;
      pItem = &pWInfo->pTabList->a[pLoop->iTab];
      if( (pItem->fg.jointype & JT_LEFT)==0 ) continue;
      if( (wctrlFlags & WHERE_WANT_DISTINCT)==0
       && (pLoop->wsFlags & WHERE_ONEROW)==0
      ){
        continue;
      }
      if( (tabUsed & pLoop->maskSelf)!=0 ) continue;
      pEnd = sWLB.pWC->a + sWLB.pWC->nTerm;
      for(pTerm=sWLB.pWC->a; pTerm<pEnd; pTerm++){
        if( (pTerm->prereqAll & pLoop->maskSelf)!=0 ){
          if( !ExprHasProperty(pTerm->pExpr, EP_FromJoin)
           || pTerm->pExpr->iRightJoinTable!=pItem->iCursor
          ){
            break;
          }
        }
      }
      if( pTerm<pEnd ) continue;
      WHERETRACE(0xffff, ("-> drop loop %c not used\n", pLoop->cId));
      if( i!=pWInfo->nLevel-1 ){
        int nByte = (pWInfo->nLevel-1-i) * sizeof(WhereLevel);
        memmove(&pWInfo->a[i], &pWInfo->a[i+1], nByte);
      }
      pWInfo->nLevel--;
      nTabList--;
    }
  }
  WHERETRACE(0xffff,("*** Optimizer Finished ***\n"));
  pWInfo->pParse->nQueryLoop += pWInfo->nRowOut;

................................................................................
    }
#endif
    if( pLevel->iLeftJoin ){
      int ws = pLoop->wsFlags;
      addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin); VdbeCoverage(v);
      assert( (ws & WHERE_IDX_ONLY)==0 || (ws & WHERE_INDEXED)!=0 );
      if( (ws & WHERE_IDX_ONLY)==0 ){
        assert( pLevel->iTabCur==pTabList->a[pLevel->iFrom].iCursor );
        sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iTabCur);
      }
      if( (ws & WHERE_INDEXED) 
       || ((ws & WHERE_MULTI_OR) && pLevel->u.pCovidx) 
      ){
        sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iIdxCur);
      }
      if( pLevel->op==OP_Return ){

Changes to test/join2.test.

118
119
120
121
122
123
124
125
















































126

do_eqp_test 3.2 {
  SELECT v2 FROM t1 LEFT JOIN t2 USING (k2) LEFT JOIN t3_2 USING (k3);
} {
  0 0 0 {SCAN TABLE t1} 
  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
}

















































finish_test








>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

do_eqp_test 3.2 {
  SELECT v2 FROM t1 LEFT JOIN t2 USING (k2) LEFT JOIN t3_2 USING (k3);
} {
  0 0 0 {SCAN TABLE t1} 
  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
}

#-------------------------------------------------------------------------
# Test that tables other than the rightmost can be omitted from a
# LEFT JOIN query.
#
do_execsql_test 4.0 {
  CREATE TABLE c1(k INTEGER PRIMARY KEY, v1);
  CREATE TABLE c2(k INTEGER PRIMARY KEY, v2);
  CREATE TABLE c3(k INTEGER PRIMARY KEY, v3);

  INSERT INTO c1 VALUES(1, 2);
  INSERT INTO c2 VALUES(2, 3);
  INSERT INTO c3 VALUES(3, 'v3');

  INSERT INTO c1 VALUES(111, 1112);
  INSERT INTO c2 VALUES(112, 1113);
  INSERT INTO c3 VALUES(113, 'v1113');
}
do_execsql_test 4.1.1 {
  SELECT v1, v3 FROM c1 LEFT JOIN c2 ON (c2.k=v1) LEFT JOIN c3 ON (c3.k=v2);
} {2 v3 1112 {}}
do_execsql_test 4.1.2 {
  SELECT v1, v3 FROM c1 LEFT JOIN c2 ON (c2.k=v1) LEFT JOIN c3 ON (c3.k=v1+1);
} {2 v3 1112 {}}

do_execsql_test 4.1.3 {
  SELECT DISTINCT v1, v3 FROM c1 LEFT JOIN c2 LEFT JOIN c3 ON (c3.k=v1+1);
} {2 v3 1112 {}}

do_execsql_test 4.1.4 {
  SELECT v1, v3 FROM c1 LEFT JOIN c2 LEFT JOIN c3 ON (c3.k=v1+1);
} {2 v3 2 v3 1112 {} 1112 {}}

do_eqp_test 4.2.1 {
  SELECT v1, v3 FROM c1 LEFT JOIN c2 ON (c2.k=v1) LEFT JOIN c3 ON (c3.k=v2);
} {
  0 0 0 {SCAN TABLE c1} 
  0 1 1 {SEARCH TABLE c2 USING INTEGER PRIMARY KEY (rowid=?)}
  0 2 2 {SEARCH TABLE c3 USING INTEGER PRIMARY KEY (rowid=?)}
}
do_eqp_test 4.2.2 {
  SELECT v1, v3 FROM c1 LEFT JOIN c2 ON (c2.k=v1) LEFT JOIN c3 ON (c3.k=v1+1);
} {
  0 0 0 {SCAN TABLE c1} 
  0 1 2 {SEARCH TABLE c3 USING INTEGER PRIMARY KEY (rowid=?)}
}



finish_test