Reorder boolean expressions (including filter predicates) according to evaluation cost / selectivity

[Dandandan]

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

[suibianwanwank]

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]

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.

Good call, if we do it, it needs to be configurable so users/engines can disable the optimization.

[alamb]

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]

take

[alamb]

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

• Add SelectivityTracker adaptive filter cost model #22236

ALso possibly related

• Adaptive filter pushdown for the parquet scan #22237

[alamb]

Related to

• [Experiment] Adaptive filter pushdown #22144

[adriangb]

@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 BinaryExpr do reordering itself. For example we are not going to split / track id = 1 OR message ilike '%foo%' as separate filters during scans. And there are still FilterExecs, 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.