Presto: Pushing down expensive projections through selective joins might hurt query performance

[rongrong]

When we have expensive projections like json/map/array/regex functions on the prob side of a join, push it down to table scan is likely to cause worse performance, especially when join is very selective and reduces the number of rows in the output. Consider equijoins usually don't explode the number of rows, queries with these expensive operations are more likely to perform better when these projections are not pushed down.

[findepi]

especially when join is very selective and reduces the number of rows in the output ...
Consider equijoins usually don't explode the number of rows

I am not convinced this is a safe assumption. E.g. one could assume equijoin not to be selective at all, like joining "clicks" with "users" you expect your "user_id" will be found there.

Anyway, we already estimate join selectiveness (JoinStatsRule). What we should do is to consider the 3 things:

• a join's selectiveness
• cost of computing a projection (increased if we push down under a selective join)
• cost of transferring the data (eg. can be greatly decreased if the projection reduces size of data, eg. contains or regexp_like)

Here you see the CPU vs bandwidth tradeoff generally present in cost-based decisions. To address this, there is the CostComparator that (currently) assigns weights to those dimensions, allowing determination of the optimal plan.

[rongrong]

@findepi I agree with all you said. To cut an accurate line between whether push down a projection would improve performance or not is hard. As you mentioned you need to consider 3 things. If we want to always pick the right solution, we need accurate metrics on all three. However, there is a class of cases that we can very safely assume not pushing is better, which is, very expensive projections that do not reduce data size significantly on the probe size of inner join. This is the case that when you push the projection down, you'd see significant performance regression. And I think we should try to avoid this.

Specifically for equijoin, I only assumed that it's not likely to explode, I would not assume it would be selective.

[dain]

@findepi One other thing to consider, is it is difficult to force the system to not push down (need to combine with random), but it is normally straight forward to manually move a projection below a join. So, I think of this more as relaxing an overly aggressive heuristic rule, instead of adding a new rule.

[findepi]

When we write queries by hand -- I agree.
However, it's not uncommon for people not to even use JOIN keyword, so the queries look like this:

SELCT ... 
FROM t1, t2, t3 ...
WHERE <join conditions>
AND <other conditions>

In such a case, all filters are initially placed above all the JOINs.

[dain]

@findepi, I'm only talking about projections, and specifically not filters or join condition (or effective join conditions). I feel like there is a good reliable heuristic for not pushing down "known expensive" projections through the probe side of a join. I'm not sure there is a similar thing for the build side (thinking about memory size), or for filters.

[findepi]

@dain sorry, my last comment was really a poor one. Consider it off-topic.
Anyway, I would assume my "off-topic example" can be extended to an on-topic: I expect most of the projections directly after (first) SELECT

I feel like there is a good reliable heuristic for not pushing down "known expensive" projections through the probe side of a join.

👍 let's find it.

I'm not sure there is a similar thing for the build side (thinking about memory size)

with build side, things get more complex -- if a projection is above the join, it will be evaluated multiple times for each build value, as values are duplicated.
Compare this to probe side -- this shouldn't be the case for probe, as we build DictionaryBlocks. A projection should still be evaluated once per "source" probe value, even if rows multiplicated (once or actually: once per page).

[rongrong]

Seems like nobody followed up on this. Should we give it a go? I'm only proposing to not push down projections when all the following criteria are met:

• expensive projections involving UDFs related to JSON/map/array/regex
• estimated cost of change without pushing projection would not increase

This should be fairly conservative?

[martint]

expensive projections involving UDFs related to JSON/map/array/regex

There's no good way for the optimizer to know what's an "expensive" projection.

[rongrong]

For that part I'm more thinking of a hard coded selection of UDFs, until the cost estimation of these are built into the cost calculator. I think that's an ok trade off for now. Or we can ask UDFs to provide a cost function on a scale of 1-5 or just CHEAP(constant time), MEDIUM((sub or leaner to input), EXPENSIVE(above leaner).

[martint]

I'm more thinking of a hard coded selection of UDFs

Yeah, that's what's a bit complicated. We could hard code it now, but it would break as soon as the PR to change how function resolution works lands (all function references become opaque in the plan IR at that point).

[rongrong]

@martint I don't see the PR related to function resolution being merged in the near future so I'll give this a go as a temporary perf fix. I'll be working on the function resolution change as well so I'll clean this up once that's in. This should be a small enough change to add / revert anyways.

[stale[bot]]

This issue has been automatically marked as stale because it has not had any activity in the last 2 years. If you feel that this issue is important, just comment and the stale tag will be removed; otherwise it will be closed in 7 days. This is an attempt to ensure that our open issues remain valuable and relevant so that we can keep track of what needs to be done and prioritize the right things.