[SPARK-18455] General support for correlated subquery processing

• Type: Story
• Status: Resolved
• Priority: Major
• Resolution: Done
• Component/s: SQL
• Assignee: Dilip Biswal Assign to me
• Reporter: Nattavut Sutyanyong
• Shepherd: Herman van Hövell
• Created: 15/Nov/16 21:45
• Updated: 19/Jan/20 07:23
• Resolved: 09/Sep/19 16:29

Description

Subquery support has been introduced in Spark 2.0. The initial implementation covers the most common subquery use case: the ones used in TPC queries for instance.

Spark currently supports the following subqueries:

• Uncorrelated Scalar Subqueries. All cases are supported.
• Correlated Scalar Subqueries. We only allow subqueries that are aggregated and use equality predicates.
• Predicate Subqueries. IN or Exists type of queries. We allow most predicates, except when they are pulled from under an Aggregate or Window operator. In that case we only support equality predicates.
  However this does not cover the full range of possible subqueries. This, in part, has to do with the fact that we currently rewrite all correlated subqueries into a (LEFT/LEFT SEMI/LEFT ANTI) join.

We currently lack supports for the following use cases:

• The use of predicate subqueries in a projection.
• The use of non-equality predicates below Aggregates and or Window operators.
• The use of non-Aggregate subqueries for correlated scalar subqueries.

This JIRA aims to lift these current limitations in subquery processing.

Issue Links

• is related to: SPARK-18966 NOT IN subquery with correlated expressions may return incorrect result
• is related to: SPARK-15370 Some correlated subqueries return incorrect answers
• is related to: SPARK-15832 Embedded IN/EXISTS predicate subquery throws TreeNodeException
• is related to: SPARK-16804 Correlated subqueries containing non-deterministic operators return incorrect results
• is related to: SPARK-17348 Incorrect results from subquery transformation
• is related to: SPARK-18504 Scalar subquery with extra group by columns returning incorrect result
• is related to: SPARK-18578 Full outer join in correlated subquery returns incorrect results
• is related to: SPARK-16161 Ambiguous error message for unsupported correlated predicate subqueries
• relates to: SPARK-23945 Column.isin() should accept a single-column DataFrame as input

Sub-Tasks

• EXISTS and Left Semi join do not produce the same plan: Resolved
• Support `OuterReference` in projection list of IN correlated subqueries: Resolved
• NOT IN subquery with correlated expressions may return incorrect result: Resolved
• First phase: Deferring the correlated predicate pull up to Optimizer phase: Resolved
• New test cases for IN/NOT IN subquery: Resolved
• New test cases for scalar subquery: Resolved
• New test cases for EXISTS subquery: Resolved
• Alternative implementation of NOT IN to Anti-join: Closed
• Whitelist LogicalPlan operators allowed in correlated subqueries: Resolved
• Caching logical plans containing subquery expressions does not work.: Resolved
• Return a better error message when correlated predicates contain aggregate expression that has mixture of outer and local references: Resolved
• Move error reporting for subquery from Analyzer to CheckAnalysis: Resolved