Subquery pushdown changes in 6.2

## Why are we implementing it? (sales eng)

* This feature is only intended for real-time use case.
* Before this change, Citus had some limited support for multi-shard subqueries. The implementation that comes with 6.2 doesn't implement all kinds of subqueries either. But, it removes quite a few limitations of the existing implementation and providing much broader SQL support.
* Who doesn't want more SQL coverage? Although we intended a specific use-case described below, having broader SQL coverage could help other use cases as well.

### What are the typical use cases?

* Main motivation is to be able to run multi-shard behavioral analytics - segmentation type of queries.
* It can answer queries that groups/segments users and or events. For example:
* Find customers who have done X, Y and Z in the specified order (i.e., Funnel queries)
* Find customers who have done X and haven’t done Y, and satisfy other customer specific criteria
* Find me all users / events ...
* Many other queries that examine behaviors of users by classifying the users using subqueries.
* This [regression test file](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_behavioral_analytics.sql) is mostly intended for documentation purposes. Almost each query has an explanation. That should give you a better understanding of analysis/segmentation queries that Citus supports.

* What makes subqueries useful for writing such queries? The answer is that each group/segment can be expressed via a subquery. And, using subquery JOINs, it becomes easy to write very powerful analytics queries.

## Communication goals (e.g. detailed howto vs orientation)

### Good locations for content in docs structure

I think this should go into a separate section in the Docs. But, we should probably check with Sumedh and Ozgun.

## How does this work? (devs)

* A very critical note here is that we call this feature as `Subquery Pushdown`.
* `Pushdown` means Citus does minor modifications on the query
* Almost sends the query to the workers as it is, simply adding shard_ids
* Running the master query
* There are two major requirements to enable `pushdown`
* All tables should be co-located
* Each table should be joined on its partition key with at least one another table on partition key via equality operator
* See all [the examples](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_behavioral_analytics.sql) in the regression test file has partition key equality at least one another table
* The above helps us to form a partition key equality among all the tables
* All the required data is present on the workers, no need to move data/re-partition shards etc.
* Remember that there are other types of subqueries that we cannot pushdown

### Detailed list of requirements for subquery pushdown
* All tables should be co-located (i.e., no reference table support yet)
* **JOINS:**
* Each table should be joined on its partition key with at least one another table on partition key via equality operator.
* If the JOIN is INNER/OUTER/LATERAL joins, partition key equality is very obvious. For example:
* [In the query](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_behavioral_analytics.sql#L661), we see that `ON` clause has `ON a.user_id = b.user_id ` where `user_id` is the partition key for both tables.
* Similarly, [in this query](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_behavioral_analytics.sql#L722), each subquery is joined on `user_id` via `LATERAL` joines
* If the query has subqueries in `WHERE` clause, we have two ways of pushing down the queries:
1. Correlated subqueries with IN, NOT IN, EXISTS, NOT EXISTS, operator expressions such as (>, <, =, ALL, ANY etc.). Correlated subqueries mean that there is a reference in the `WHERE` clause from the `FROM` clause tables/subqueries. The reference/correlation should be again on partition keys and using equality operator. See a typical examples [Operators](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_in_where_clause.sql#L9), [`EXISTS`](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_behavioral_analytics.sql#L476)/ [`NOT EXISTS`](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_behavioral_analytics.sql#L486)) .
2. Non-correlated subqueries with `WHERE partition_key IN (SELECT partition_key ..)` . Some examples for [`IN`](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_behavioral_analytics.sql#L462) queries.
* **Important**: Note that Postgres internally converts these kinds of non-correlated queries into correlated queries. So, I think it makes sense to clarify whether this type of queries are classified as correlated in the literature and document it accordingly.

* **Aggregations:**
* If the query has an aggregate, it has to have a `GROUP BY` clause. In other words, Citus would error out if any of the subqueries is in the following format: `SELECT aggregate(column) FROM table`
* If there exists `GROUP BY`, the `GROUP BY` clause has to include the partition key.

* **Set Operations:**
* Citus supports `UNION` and `UNION ALL` clauses in subqueries. Note that in [this](https://gist.github.com/onderkalaci/52c7e661f200fbd6dfac317d6411182e#file-union_examples-sql-L13) example the `UNION` is not in a subquery, thus not supported by Citus yet. But, [here](https://gist.github.com/onderkalaci/52c7e661f200fbd6dfac317d6411182e#file-union_examples-sql-L2) the same query is wrapped into a `UNION`, thus Citus supports.
* Each leaf query (i.e., child queries of `UNION` / `UNION ALL` queries) should have partition key on their target lists.
* The partition keys should be in the same position in the target list.
* For example, see this [example](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_union.sql#L11). There are two leaf queries of the `UNION` query. Each leaf query has the partition key on the target list (i.e., `user_id`) at the same position (i.e., both is the first element in the target list). For example, see this [unsupported query example](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_union.sql#L483) where the 5th query returns `2 * user_id`, which is not the partition key.

### Side Effect: Expanded View Support

* Citus already supports Views for router queries (i.e., covers multi-tenant use case)
* With this change, Citus expands the View support with a wide range of multi-shard real-time queries
* Postgres sees views as subqueries
* If the query that is being used to create the View can be planned by the subquery pushdown planner, then Citus supports that View
* Joins, subqueries, aggregations on the partition key
* Also joins between views, tables, subqueries etc. is supported

### Example sql

1. [Generic SQLs](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_behavioral_analytics.sql)
2. [Subqueries in WHERE clause](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_in_where_clause.sql)
3. [UNION/UNION ALL queries that are below a JOIN query](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_complex_queries.sql)
* Just a private note here: These are equivalent of Heap's production queries with our regression test schema
4. [UNION/UNION ALL queries that are NOT below a JOIN query (i.e., `Top Level Unions`)](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_union.sql) -- See Corner cases below
5. [Expanded View Support](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_view.sql#L156)

### Corner cases, gotchas

#### UNIONs
* The most annoying limitation is on the `UNION` / `UNION ALL` queries. The limitation that I'm going to explain exists just because we didn't have time to implement it. There is nothing related to correctness or any other thing. We're going to tackle this limitation in the next release.

* When a `UNION` or `UNION ALL` query is below a `JOIN` in the query tree, we support arbitrary subqueries as the leaf queries. (Here arbitrary means that any query that subquery pushdown can plan/execute).
*, For example, see this [example](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_complex_queries.sql#L16). As you can see, the `UNION` query is below the `JOIN` in the query tree. In this case, the `UNION` leaf queries can be any subquery that Citus supports.
* When a `UNION` or `UNION ALL` query is **NOT** below a `JOIN` in the query tree, i.e., `Top Level Unions`, we have a very limited SQL coverage. The leaf queries cannot have arbitrary subqueries. They cannot have any JOINs/subqueries in the query. Instead, they could only be simple projection/aggregation queries.
* See a typical example [here](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_union.sql#L11)
* **Critical Note on UNION support documentation**: I think we could consider not documenting `UNIONs` in this release given that explaining the above limitations could be painful.

#### Views
* Note that aggregations on non-partition keys cannot be pushed down to the workers. So, for example, [this query](https://gist.github.com/onderkalaci/37496f5803d32cb4234c2426836dc39d#file-unsupported_view_example-sql-L17) can be planned by Citus, however, it is not supported by `VIEW`s.
* Similarly aggregates without `GROUP BY` are not supported. See example [here](https://gist.github.com/onderkalaci/37496f5803d32cb4234c2426836dc39d#file-unsupported_view_example-sql-L30)
* Although we have the above limitation, I think we should be documenting the expanded `VIEW`support given that it allows a very wide support.

#### Limits
* Citus supports `LIMIT`s on the outermost query such as this [one](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_union.sql#L11)
* However, by default, Citus errors out on `LIMIT`s in the subqueries such as [here](https://github.com/citusdata/citus/blob/ad5cd326a4b73e14088af0b8a9ee70611f9b88f5/src/test/regress/output/multi_subquery.source#L229).
* **Important:** This limitation could be relaxed by setting `subquery_pushdown` TO `ON`. However, that could lead to return wrong results depending on the data distribution/query (i.e., `ORDER BY`s in the query). The user has to be aware of that. I think we should **not** document this publicly.
* Even if the `subquery_pushdown` flag is set to `ON`, if the subqueries have a `LIMIT`, the outermost query has to have a `LIMIT` as well.
* `OFFSET` clause is prohibited in the subqueries.

#### DISTINCT/DISTINCT ON
* `DISTINCT` and `DISTINCT ON` should include partition key such as [here](https://github.com/citusdata/citus/blob/master/src/test/regress/sql/multi_subquery_behavioral_analytics.sql#L104)

### Are there relevant blog posts or outside documentation about the concept/feature?

Team meeting slides are [here](https://docs.google.com/presentation/d/1HL-MJ9Axoj3vmg_c69lzLDFhudRKy-uaZTQl3OG-LHY/edit#slide=id.p).

### Link to relevant commits and regression tests if applicable

We had two PRs, [main PR](https://github.com/citusdata/citus/pull/1323) and the following [PR](https://github.com/citusdata/citus/pull/1372). I already shared the related regression test files in `Example sql` section.