Derby
  1. Derby
  2. DERBY-4405

Transformation to inner join not performed for certain three-way joins

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: 10.6.1.0
    • Fix Version/s: 10.6.1.0
    • Component/s: SQL
    • Labels:
      None
    • Bug behavior facts:
      Performance

      Description

      In the CROSS JOIN section in the reference manual (http://db.apache.org/derby/docs/dev/ref/rrefsqljcrossjoin.html) there are three examples that are supposed to be equivalent. However, the performance differs significantly between the different queries.

      The queries use the tours db and look like this:

      (1)
      SELECT * FROM CITIES LEFT OUTER JOIN
      (FLIGHTS CROSS JOIN COUNTRIES)
      ON CITIES.AIRPORT = FLIGHTS.ORIG_AIRPORT
      WHERE COUNTRIES.COUNTRY_ISO_CODE = 'US'

      (2)
      SELECT * FROM CITIES LEFT OUTER JOIN
      FLIGHTS INNER JOIN COUNTRIES ON 1=1
      ON CITIES.AIRPORT = FLIGHTS.ORIG_AIRPORT
      WHERE COUNTRIES.COUNTRY_ISO_CODE = 'US'

      (3)
      SELECT * FROM CITIES LEFT OUTER JOIN
      (SELECT * FROM FLIGHTS, COUNTRIES) S
      ON CITIES.AIRPORT = S.ORIG_AIRPORT
      WHERE S.COUNTRY_ISO_CODE = 'US'

      When executed in ij, (1) and (2) need 6 seconds to complete, whereas (3) completes in 50 ms.

      The query plans for (1) and (2) use nested loop joins and table scans. (3) uses a combination of hash join and nested loop join, and index scans as well as table scans.

      It looks like (3) has been rewritten from a left outer join to an inner join internally. This is fine because all rows that have the right-side columns filled with NULLs will be filtered out by the predicate S.COUNTRY_ISO_CODE='US', so the extra rows generated by the outer join will not be returned.

      This optimization should also be possible for (1) and (2). We should improve the logic so that those joins are transformed too. The transformation happens in HalfOuterJoinNode.transformOuterJoins().

      1. derby-4405-2.stat
        0.2 kB
        Dag H. Wanvik
      2. derby-4405-2.diff
        39 kB
        Dag H. Wanvik
      3. derby-4405.stat
        0.4 kB
        Dag H. Wanvik
      4. derby-4405.diff
        38 kB
        Dag H. Wanvik

        Issue Links

          Activity

          Gavin made changes -
          Workflow jira [ 12479207 ] Default workflow, editable Closed status [ 12800825 ]
          Knut Anders Hatlen made changes -
          Link This issue is related to DERBY-4374 [ DERBY-4374 ]
          Knut Anders Hatlen made changes -
          Status Resolved [ 5 ] Closed [ 6 ]
          Dag H. Wanvik made changes -
          Status In Progress [ 3 ] Resolved [ 5 ]
          Issue & fix info [Patch Available]
          Fix Version/s 10.6.0.0 [ 12313727 ]
          Resolution Fixed [ 1 ]
          Dag H. Wanvik made changes -
          Attachment derby-4405-2.diff [ 12427972 ]
          Attachment derby-4405-2.stat [ 12427973 ]
          Dag H. Wanvik made changes -
          Status Open [ 1 ] In Progress [ 3 ]
          Dag H. Wanvik made changes -
          Assignee Dag H. Wanvik [ dagw ]
          Dag H. Wanvik made changes -
          Issue & fix info [Patch Available]
          Dag H. Wanvik made changes -
          Field Original Value New Value
          Attachment derby-4405.diff [ 12426352 ]
          Attachment derby-4405.stat [ 12426353 ]
          Knut Anders Hatlen created issue -

            People

            • Assignee:
              Dag H. Wanvik
              Reporter:
              Knut Anders Hatlen
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development