Skip to content

Address performance/execution plan of TPCH query 19 #78

Closed

Description

@Dandandan

Describe the bug
TPC-H Query 19 consumes a lot of memory and takes forever in memory on a 8 core machine on SF=1 in memory (with 100%cpu usage across cores) to execute. That likely has to do with the plan misses a equi-join and turns it into a cross join.

To Reproduce
Run query 19, check plan and execution time.

Expected behavior
The query is expected to finish faster (<1s) and shouldn't need a cross join.

Additional context
@alamb :

In order to get Q19 to work, the optimizer needs to be clever enough to recognize that p_partkey = l_partkey which appears in each of the three clauses is a join predicate. The query shouldn't be doing a CROSS JOIN, it should be doing an INNER JOIN on p_partkey = l_partkey

Note this is Q19:

select
sum(l_extendedprice * (1 - l_discount) ) as revenue
from
lineitem,
part
where
(
p_partkey = l_partkey
and p_brand = ‘[BRAND1]’
and p_container in ( ‘SM CASE’, ‘SM BOX’, ‘SM PACK’, ‘SM PKG’)
and l_quantity >= [QUANTITY1] and l_quantity <= [QUANTITY1] + 10
and p_size between 1 and 5
and l_shipmode in (‘AIR’, ‘AIR REG’)
and l_shipinstruct = ‘DELIVER IN PERSON’
)
or
(
p_partkey = l_partkey
and p_brand = ‘[BRAND2]’
and p_container in (‘MED BAG’, ‘MED BOX’, ‘MED PKG’, ‘MED PACK’)
and l_quantity >= [QUANTITY2] and l_quantity <= [QUANTITY2] + 10
and p_size between 1 and 10
and l_shipmode in (‘AIR’, ‘AIR REG’)
and l_shipinstruct = ‘DELIVER IN PERSON’
)
or
(
p_partkey = l_partkey
and p_brand = ‘[BRAND3]’
and p_container in ( ‘LG CASE’, ‘LG BOX’, ‘LG PACK’, ‘LG PKG’)
and l_quantity >= [QUANTITY3] and l_quantity <= [QUANTITY3] + 10
and p_size between 1 and 15
and l_shipmode in (‘AIR’, ‘AIR REG’)
and l_shipinstruct = ‘DELIVER IN PERSON’
);

Activity

  1. Dandandan commented on Apr 27, 2021

    @Dandandan
    ContributorAuthor

    @alamb I am wondering if you think it would be the solution to introduce this boolean optimization (Distributivity of and over or):
    (p and q1) OR (p and q2) should be replaced by p AND (q1 or q2)
    p in this example could be our join predicate.

    After this optimization, the physical planner should be able to see the predicate in the filter.

  2. alamb commented on Apr 27, 2021

    @alamb
    Contributor

    @Dandandan -- yes, I think the "classic" thing to do is a "predicate rewrite" pass that rearranges predicates for further downstream operations

    The goal is basically to get the predicate into a form of

    good_predicate1 AND good_predicate2 AND ...

    Where good_predicate means the predicate has special support in the execution engine.

    Since OR is not typically handled specially, rewrites to AND are helpful

    Rewrite 1: (p and q1) OR (p and q2) OR (p and ..) ==> p AND (q1 or q2)

    Another common rewrite I have seen is
    (col1 = A) OR (col1 = B) OR (col1 = C) ==> col1 IN (A, B, C)

    Which then the execution engine can treat like a single column predicate (push down to scan) and build a hash table for (A, B, C) and do fast filtering.

    Shall I file an issue to track this kind of rewrtite?

  3. Dandandan commented on Apr 27, 2021

    @Dandandan
    ContributorAuthor

    Cool, thanks @alamb !

    I guess there are also some more opportunities for rewriting in the above example:

    l_shipmode in (‘AIR’, ‘AIR REG’) and and l_shipinstruct = ‘DELIVER IN PERSON are repeated and could benefit from being simplified and then pushed down.

    p_container in ( ‘SM CASE’, ‘SM BOX’, ‘SM PACK’, ‘SM PKG’), p_container in (‘MED BAG’, ‘MED BOX’, ‘MED PKG’, ‘MED PACK’) ,p_container in ( ‘LG CASE’, ‘LG BOX’, ‘LG PACK’, ‘LG PKG’)

    could be adding a filter with all the items.

    p_size between 1 and 15 , p_size between 1 and 10, p_size between 1 and 5 could generate a filter with the least restrictive filter p_size between 1 and 15

    Shall I file an issue to track this kind of rewrtite?
    Would be nice to have some tracking issue 👍

  4. alamb commented on Apr 28, 2021

    @alamb
    Contributor

    Filed #217 to track the idea

  5. DhamoPS commented on Aug 30, 2022

    @DhamoPS
    Contributor

    @Dandandan I am working on a fix for this issue. I will create a PR this week for your approval.
    Currently, Join Predicates which are part of OR Expressions are not handling properly in planner.rs. I handle this scenario and ensure that Join Predicates are handled properly. With this fix, Q19 would run faster without any change in Query. Thanks

  6. alamb commented on Aug 31, 2022

    @alamb
    Contributor

    Thanks @DhamoPS -- note that @xudong963 implemented #2858 which may have helped

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions