search

citusdata / citus

Distributed PostgreSQL as an extension
https://www.citusdata.com
GNU Affero General Public License v3.0
10.51k stars 666 forks source link

Consider decreasing the algorithmic complexity of restriction equivalence #1322

Open onderkalaci opened 7 years ago

onderkalaci commented 7 years ago

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:


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: 10 Joins on the partition key

Query 2: 100 Joins on the partition key

Query 3: 1000 Joins on the partition key

Query 4: 5000 Joins on the partition key

Query 5: 10000 Joins on the partition key

Query 6: 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 ):

Query 7: 5 tables, 5 joins on partition keys, 5 joins on partition key and non partition keys ):

Query 8: 5 tables, 5 joins on partition keys, 20 joins on partition key and non partition keys):

Query 9: 5 tables, 5 joins on partition keys, 50 joins on partition key and non partition keys):

Query 10: 5 tables, 5 joins on partition keys, 200 joins on partition key and non partition keys):

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.

anarazel commented 7 years ago

What about adding a number of a.partition_key = b.non_partition_key restrictions? IIRC they'd be hit by the current algoirthm, and it's quite realistic to have lot of them, without absurd numbers of joins.

onderkalaci commented 7 years ago

What about adding a number of a.partition_key = b.non_partition_key restrictions? IIRC they'd be hit by the current algoirthm, and it's quite realistic to have lot of them, without absurd numbers of joins.

@anarazel I've updated the issue, please see Query 7 to Query 10. Do the tests make sense to you? If yes, we're still OK with those tests given that the cost of running the algorithm is not high compared to the other parts of the planning & execution. (Btw, I'm using a similar approach to measure the time passed as log_disconnections() function in the postgres.c)