Subquery Un-nesting?

[skyzh]

Most of the TPC-H queries have sub-queries. We should investigate how to implement this in the future.

[jiangzhe]

I recommend two papers:

1. Orthogonal Optimization of Subqueries and Aggregation, published in 2001.
   This paper describes basic rules to unnest subqueries and I think is a good start point to work on.
   If focus on TPC-H, somes rules can be postponed to implement, UNION, EXCEPT, INTERSECT, etc, and the rest still cover all cases of TPC-H.
2. Unnesting Arbitrary Queries, published in 2015.
   This paper provides more advanced techniques to unnest subqueries, which is general and can cover most scenarios. But it also brings considerable complecity, by introducing DAG data flow, new join operators, etc.

I also wrote a post about how to unnest subqueries recently in my own project wiki, trying to classify and explain all use cases of subqueries.
You could have a look if interested, and comments are welcome.

[skyzh]

Thanks a lot!

[arkbriar]

Here's a blog written by ericfu about subqueries and the possible way to unnest the main forms of subqueries, which IMO is insightful. To implement subqueries and un-nesting in risinglight, we will need to do a lot works on most of the components such as binder (recognize the subqueries), optimizer (decide and do the unnest), executor (implement the apply operator, semi/anti join and many others, and a refactor must be done on the executor if we try to do like what HyPer does). I haven't thought of a complete plan how to achieve this but I think it's ok to begin with the simple apply (correlated join).

[jiangzhe]

One important point mentioned in HyPer's paper is to bring up some particular join types for subquery unnesting, e.g. SingleJoin, MarkJoin, and even GroupJoin.
In this way, subqueries can be always unnested at first, and then grouped in join tree/graph to involve cost-based join reorder.

[arkbriar]

Yes, that is exciting. Although these operators are not in standard relational algebra, which makes it a big problem to be introduced in some mature systems, I prefer to follow the Hyper's way since we are still in an early stage.