Optimized version of `SortPreservingMerge` that doesn't actually compare sort keys of the key ranges are ordered about arrow-datafusion HOT 15 OPEN

Oh yeah, we're going to be hitting this all the time. Definitely want to see this! 😁

from arrow-datafusion.

Thanks @alamb. I am happy to port ProgressiveEval from InfluxDB to DB

from arrow-datafusion.

@alamb Just to be absolutely clear, if the plan consists entirely of Parquet files from a single table, then the SortPreservingMerge will be eliminated. As you can see in this sqllogictest, a single file group is produced if none of the files overlap, and DataFusion correctly understands a SortPreservingMergeExec is not required. In particular, after #9593, #6672 should be fixed.

That said, it's worth pointing out that ProgressiveEval is more general (it can work for arbitrary plans e.g. heterogeneous unions).

from arrow-datafusion.

@alamb : I am starting porting ProgresssiveEval from IOx. Do you want me to use this ticket or #10433 for that work or you want me to open a new ticket for the porting?

How about we open a new ticketfor porting and link it to this epic?

from arrow-datafusion.

Here is the entire implementation in case anyone wants this: https://github.com/influxdata/influxdb3_core/blob/b546e7f86ee9adbff0dd3c5e687140848397604a/iox_query/src/provider/progressive_eval.rs

from arrow-datafusion.

I probably should have mentioned that in order to use this operator, one needs to be able to determine if the input streams to SortPreservingMerge are non overlapping in value. Conveniently, that is basically the analysis that @suremarc has implemented in #9593

from arrow-datafusion.

Oh yeah, we're going to be hitting this all the time. Definitely want to see this! 😁

Also to be clear to everyone else -- we have this code in InfluxDB already but it would be great to have other people be able to use it (and help maintain it)

from arrow-datafusion.

FYI @ozankabak @mustafasrepo @matthewmturner

from arrow-datafusion.

I think we should both port ProgressiveEval as well as hook it up in the optimizer so it is is used (likely based on the analysis in #9593)

from arrow-datafusion.

If the hooking work is not that tricky (which I think the case), I am happy to do that, too

from arrow-datafusion.

What comes to my mind is that if we can successfully bring the statistics to SortPreservingMerge, it could handle this work without a separate operator (This will probably need a change in statistics API to return statistics for each partition).

from arrow-datafusion.

What comes to my mind is that if we can successfully bring the statistics to SortPreservingMerge, it could handle this work without a separate operator (This will probably need a change in statistics API to return statistics for each partition).

I think this approach would work as well -- or maybe just a flag on the SortPreservingMerge and a different stream rather than an entirely ExecutionPlan 🤔

Per partition statistics is an interesting idea 🤔 -- it certainly makes sense for things like data sources. I wonder how generally useful it could be

from arrow-datafusion.

@alamb : I am starting porting ProgresssiveEval from IOx. Do you want me to use this ticket or #10433 for that work or you want me to open a new ticket for the porting?

from arrow-datafusion.

This is the ticket to port ProgressiveEval from InfluxDB #10488

from arrow-datafusion.

Update here:

1. @NGA-TRAN has a PR open to port this operator into DataFusion: #10490
2. We don't want to merge it into DataFusion until at least one other user could get value from it.

So in my mind, what is required to move on with this ticket is:

1. Update one of the existing optimizer passes to detect when the sort keys of a SortPreservingMerge don't overlap in value and replace with ProgressiveEval
2. Tests showing it working

For the "do key ranges overlap" detection code I think we can use what @suremarc added in #9593

from arrow-datafusion.