citusdata / citusdata/citus

Consider decreasing the algorithmic complexity of restriction equivalence

Open
#1,322 2 comments 0 reactions 0 assignees View on GitHub
technical debt
Dominant language
C
Stars
12.8k
Forks
794
Avg merge
2d 14h
Merged PRs (30d)
31

Description

While @anarazel reviewing the changes for subquery pushdown in #1268 , he had some concerns about the algorithmic complexity of the `RestrictionEquivalenceForPartitionKeys()` function. I'm opening this issue to discuss some more details on the specifics of the algorithm, share some benchmark results and keep track of it.

Firstly, let me share the pseudo code of the discussed algorithm:
```python

for each `join restriction` or planner `eq_class` :
if the restriction is NOT on the partition key:
continue

if restriction is not `(Var = Var)` form
continue

Find the RTE_RELATION that the restriction belongs to
Create an equivalence member
Add member to the equivalence class
Add the equivalence class to equivalence class list
While adding an equivalence class to the list, ensure that the list doesn't have an equal equivalence class in the list

Concat all the equivalence classes into a list
Add the first equivalence class to the common equivalence class

For each equivalence class:
if the equivalence class is already on the common equivalence class
continue

if the equivalence class has an equivalent member in the common eq. class:
Add the members of the equivalence class that don't appear in the common equivalence class (i.e., ensure uniqueness of the equivalence member in the common class)

check whether the common equivalence class contains all RTE_RELATIONs that appear in the query

```

Some parts of the above algorithm have high algorithmic complexity. Especially checking the uniqueness of the equivalence members on the common equivalence class. However, as the benchmarks show, the algorithmic complexity doesn't show a big performance bottleneck, given that we're following a very conservative approach while adding a restriction to an equivalence class.

Now, I'd like to share some benchmark results. Below, I wanted to give different parts of the planning. The last item in each test shows the time that has passed for executing the whole algorithm that decides whether to push down the query or not (i.e., ``Attribute Eq. Execution``) .

Note that I've run the tests on my local machine, and the test table creation queries are already in the regression tests in case anyone wants to re-produce the tests.

[`Query 1:`](https://gist.github.com/onderkalaci/7a354fd0e9aac51601e164e2a2cd8d15#file-ten_joins-sql) 10 Joins on the partition key

* `Copying origianal query`: Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 0
* `Assigning RTE Ids` : Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 0
* `Standard planner:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 2
* `Logical planner:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 0
* `Attribute Eq. Execution:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 0

[`Query 2:`](https://gist.github.com/onderkalaci/7a354fd0e9aac51601e164e2a2cd8d15#file-hundred_joins-sql) 100 Joins on the partition key

* `Copying origianal query`: Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 5
* `Assigning RTE Ids` : Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 1
* `Standard planner:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 25
* `Logical planner:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 5
* `Attribute Eq. Execution:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 2

[`Query 3:`](https://gist.github.com/onderkalaci/7a354fd0e9aac51601e164e2a2cd8d15#file-thousand_joins-sql) 1000 Joins on the partition key
* `Copying origianal query`: Hours: 0 - Minutes: 0 - Seconds: 2 - Msecs: 845
* `Assigning RTE Ids` : Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 354
* `Standard planner:` Hours: 0 - Minutes: 0 - Seconds: 6 - Msecs: 630
* `Logical planner:` Hours: 0 - Minutes: 1 - Seconds: 21 - Msecs: 811
* `Attribute Eq. Execution:` Hours: 0 - Minutes: 0 - Seconds: 2 - Msecs: 226

[`Query 4:`](https://gist.github.com/onderkalaci/7a354fd0e9aac51601e164e2a2cd8d15#file-five_thousands_join-sql) 5000 Joins on the partition key

* `Copying origianal query`: Hours: 0 - Minutes: 1 - Seconds: 19 - Msecs: 619
* `Assigning RTE Ids` : Hours: 0 - Minutes: 0 - Seconds: 59 - Msecs: 555
* `Standard planner:` Hours: 0 - Minutes: 5 - Seconds: 48 - Msecs: 662
* `Logical planner:` Hours: 0 - Minutes: 1 - Seconds: 21 - Msecs: 811
* `Attribute Eq. Execution:` Hours: 0 - Minutes: 5 - Seconds: 0 - Msecs: 675

[`Query 5:`](https://gist.github.com/onderkalaci/7a354fd0e9aac51601e164e2a2cd8d15#file-ten_thousands_joins-sql) 10000 Joins on the partition key
* Not able to run the query due to stack size limit on Postgres.

[`Query 6:`](https://gist.github.com/onderkalaci/43b2f73dee8829924961169d44c6acfe) 100 joins and each join contains 20 filters on the partition key - some filters are joins and some are consts (mostly conts are `And` ed ):

* `Copying origianal query`: Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 1
* `Assigning RTE Ids` : Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 1
* `Standard planner:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 34
* `Logical planner:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 11
* `Attribute Eq. Execution:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 4

[`Query 7:`](https://gist.github.com/onderkalaci/dfed01f39f4fff56ca5817837f803350#file-five_table_five_restrictions-sql) 5 tables, 5 joins on partition keys, 5 joins on partition key and non partition keys ):

* `Copying origianal query`: Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 0
* `Assigning RTE Ids` : Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 0
* `Standard planner:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 5
* `Logical planner:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 6
* `Attribute Eq. Execution:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 1

[`Query 8:`](https://gist.github.com/onderkalaci/dfed01f39f4fff56ca5817837f803350#file-five_table_twenty_restrictions-sql) 5 tables, 5 joins on partition keys, 20 joins on partition key and non partition keys):

* `Copying origianal query`: Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 0
* `Assigning RTE Ids` : Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 0
* `Standard planner:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 6
* `Logical planner:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 7
* `Attribute Eq. Execution:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 1

[`Query 9:`](https://gist.github.com/onderkalaci/dfed01f39f4fff56ca5817837f803350#file-five_tables_fifty_restrictions-sql) 5 tables, 5 joins on partition keys, 50 joins on partition key and non partition keys):

* `Copying origianal query`: Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 0
* `Assigning RTE Ids` : Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 0
* `Standard planner:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 8
* `Logical planner:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 9
* `Attribute Eq. Execution:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 2

[`Query 10:`](https://gist.github.com/onderkalaci/dfed01f39f4fff56ca5817837f803350#file-five_tables_two_hundreds_restrictions-sql) 5 tables, 5 joins on partition keys, 200 joins on partition key and non partition keys):

* `Copying origianal query`: Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs:1
* `Assigning RTE Ids` : Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 0
* `Standard planner:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 14
* `Logical planner:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 6
* `Attribute Eq. Execution:` Hours: 0 - Minutes: 0 - Seconds: 0 - Msecs: 2

As I mentioned above, the algorithmic complexity doesn't seem to lead to a performance bottleneck, given that we're following a very conservative approach while adding a restriction to an equivalence class.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.