Repository navigation
Reorder boolean expressions (including filter predicates) according to evaluation cost / selectivity #11262
Description
Is your feature request related to a problem or challenge?
After #11247 is merged we can look at ordering the boolean expressions according to a measure of evaluation cost.
Describe the solution you'd like
We can reorder expressions:
E.g. a expression like the following:
URL LIKE '%google%' AND code = 404.
Likely would be better reordered to code = 404 AND URL LIKE '%google%' in order to benefit most from short circuiting as code = 404 is less expensive.
One could also combine it with the estimate of selectivity to further optimize the order (low selectivity, batches more likely to be all false, high selectivity, batches more likely to be all true)
Describe alternatives you've considered
No response
Additional context
No response
Reacted by Andrew Lamb
Activity
[-]Reorder filter predicates according to evaluation cost[/-][+]Reorder boolean expressions (including filter predicates) according to evaluation cost[/+][-]Reorder boolean expressions (including filter predicates) according to evaluation cost[/-][+]Reorder boolean expressions (including filter predicates) according to evaluation cost / selectivity[/+]suibianwanwank commentedon Jul 4, 2024
I've seen discussions about predicate reordering in the calcite community before, and one of the big problems is that the engine doing reordering of predicates invalidates the user-designed order of predicates, if the user understands that our short circuit optimisation writes the sql as a better order, but the engine reordering invalidates his efforts.
Dandandan commentedon Jul 4, 2024
Good call, if we do it, it needs to be configurable so users/engines can disable the optimization.
alamb commentedon Jul 5, 2024
We could potentially do some simple heuristics that would catch the common case -- like "treat regexp as very slow and do them after other predicates"
neilconway commentedon May 18, 2026
take
alamb commentedon May 18, 2026
I think @adriangb has had some more recent ideas on this (to more dynamically re-order expressions based on actual observed selectivity rather than trying to heuristically update them):
ALso possibly related
alamb commentedon May 18, 2026
Related to
adriangb commentedon May 18, 2026
@neilconway I wonder what you were thinking of tackling? edit: I see #22343 now, had missed that.
IMO the version of this that #22144 is trying to tackle necessarily needs to live external to the expression itself. It's much more tightly wound with the parquet scan itself because we aren't just deciding the order in which filters are evaluated but also where the IO happens (eager vs. late materialization).
It could still make sense to have
BinaryExprdo reordering itself. For example we are not going to split / trackid = 1 OR message ilike '%foo%'as separate filters during scans. And there are stillFilterExecs, join conditions, other places where binary expressions are used.I was also wondering if a "flattened" binary expression that can do a better job of re-using buffers, etc. would make sense. It seems necessary to do some sort of re-ordering sanely (otherwise you have to re-build the expression tree which would be hard once the query is executing).
Another issue that appears is the "what is an expression anyway" issue. Various places remap children / rewrite the expression in ways. It's not always clear when the expression is the same (should share selectivity tracking) or not.
bench: simplify predicate_eval descriptions, link to apache#11262
perf: Reorder predicates in conjuncts via simple heuristic (apache#22343
bench: simplify predicate_eval descriptions, link to apache#11262
bench: add correlated-proxy case to the predicate_eval suite (apache#…
bench(predicate_eval): add expensive-first and wide-column shapes (ap…