You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues-all@impala.apache.org by "Aman Sinha (Jira)" <ji...@apache.org> on 2020/02/04 18:41:00 UTC

[jira] [Commented] (IMPALA-9183) TPC-DS query 13 - customer_address predicates not propagated to scan

    [ https://issues.apache.org/jira/browse/IMPALA-9183?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17030056#comment-17030056 ] 

Aman Sinha commented on IMPALA-9183:
------------------------------------

Capturing some offline communication I had with [~stigahuang] and [~tarmstrong@cloudera.com]: 

[Aman]
Suppose a query has predicates of the form:
a = b
 and ((d = 1 and e = 10)
  or  (d = 2 and e = 20))
 
(Assume that a, d belong to table t1  and  b, e belong to t2)
 
Currently, we will evaluate these during and after the join without pushing any predicates to the scan.
 
I have made the code changes to convert this to a Conjunctive Normal Form (CNF) as follows:
a = b
 and (d = 1 or d = 2)                  <-- this can be pushed to t1
 and (d = 1 or e = 20)
 and (e = 10 or d = 2)
 and (e = 10 or e = 20)              <--- this can be pushed to t2
 
However, one downside of this is that it explodes the number of individual predicates since each combination will be exhaustively enumerated.  I am doing the conversion as a Rewrite rule which applies in the Analyzer, so it changes the original predicate ... this way all subsequent  'conjuncts' handling can apply. 
 
My question is: should I try to make this less disruptive by somehow only generating the CNF for the predicates that belong to the same table ? It will be more work, so I am trying to see how much time I should invest in it.
 
[Tim Armstrong]
My initial inclination is to avoid the complexity of checking whether the predicates belong to the same table. It seems like there are cases where the CNF would be useful even if it doesn't let you push the predicate all the way to the scan, e.g. maybe you can place it at a join lower in the tree.
The potential blow-up in predicates could be bad though - I wonder if we should be looking at instead capping the maximum number of predicates it generates somehow? I don't think we want this to be too much of a benchmark special that is overfitted for TPC-DS queries, but probably at some point we have to bail if the input query is too crazy.
What do other systems do in cases like this?
 
[Aman]
Thanks Tim for your feedback.  On Postgres 9.6, the Explain plan shows the original join predicate remains intact in the original form but the relevant filters have been pushed to the scan node.  So, I assume that internally it does the conversion to CNF and does the pushdown but still keeps the original predicate.  I don't know yet whether it imposes a maximum limit but yes I agree that there should be such a limit on the number of predicates. 
Another approach (from [wikipedia|https://en.wikipedia.org/wiki/Conjunctive_normal_form]) is the following: 
   _"There exist transformations into CNF that avoid an exponential increase in size by preserving [satisfiability|https://en.wikipedia.org/wiki/Boolean_satisfiability_problem] rather than [equivalence|https://en.wikipedia.org/wiki/Logical_equivalence].^[[2]|https://en.wikipedia.org/wiki/Conjunctive_normal_form#cite_note-2]^^[[3]|https://en.wikipedia.org/wiki/Conjunctive_normal_form#cite_note-3]^ These transformations are guaranteed to only linearly increase the size of the formula, but introduce new variables."_ 
I will probably not do the above since it introduces new intermediate variables.  I believe Hive does impose a limit on the number of new predicates, so I will check with the Hive folks on this.
 
[Quanlong]
I also stand by adding a limit for this. I think Postgres has a more theoretical mechanism for Predicate Pushdown. Maybe it's possible they do some functionality like given some predicates + a table then generate some new predicates on this table directly. We currently can only do this by predicate rewrite and then leverage the migrateConjunctsToInlineView or getBoundPredicates...
 

> TPC-DS query 13 - customer_address predicates not propagated to scan
> --------------------------------------------------------------------
>
>                 Key: IMPALA-9183
>                 URL: https://issues.apache.org/jira/browse/IMPALA-9183
>             Project: IMPALA
>          Issue Type: Bug
>          Components: Frontend
>    Affects Versions: Impala 3.4.0
>            Reporter: David Rorke
>            Assignee: Aman Sinha
>            Priority: Major
>              Labels: tpc-ds
>         Attachments: profile_q13.txt, profile_q13_mod.txt, q13_mod_plan.png, q13_plan.png, query13.sql, query13_mod.sql
>
>
> TPC-DS query 13 has a set of predicates on the customer_address table, ca_state column that are currently evaluated after the join of customer_address and store_sales.   The ca_state predicates could be pushed down to the customer_address scan node.  This would reduce the size of the join input by a factor of 3.4.
> As an experiment I added an additional redundant predicate to the query (see attached query13_mod.sql) which causes the planner to evaluate the predicate at the scan node. 
> Performance of the original and modified queries at 10 TB scale factor:
> Original:  164 seconds
> Modified: 44 seconds
> Query profiles for both versions attached.



--
This message was sent by Atlassian Jira
(v8.3.4#803005)

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-all-unsubscribe@impala.apache.org
For additional commands, e-mail: issues-all-help@impala.apache.org