You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "tobixdev (via GitHub)" <gi...@apache.org> on 2025/09/09 14:35:43 UTC
[I] Performance Regression of Nested Loop Joins in DataFusion 50 [datafusion]
tobixdev opened a new issue, #17488:
URL: https://github.com/apache/datafusion/issues/17488
### Describe the bug
As part of trying to update [RDF Fusion](https://github.com/tobixdev/rdf-fusion) to DataFusion 50, we observed a significant performance regression for a query that makes use of a Nested Loop Join.
[Original comment](https://github.com/apache/datafusion/issues/16799#issuecomment-3270869325) was in the Release issue for DataFusion 50.
I think the regression foots on two points:
- Apparently `build_row_join_batch` calls `ScalarValue::to_array_of_size` and creates a `UnionArray` which seems to be slow.
- Furthermore, much more time seems to be spent during evaluation of expressions
This could be related to https://github.com/apache/datafusion/pull/16996
@2010YOUY01 do you have a take on this?
### To Reproduce
I don't have a reproducer with the DataFusion CLI. Below is a part of our execution plan that causes the problem. I know its tough to read without knowing the system and the filters are rather messy.
If we cannot triage the regression with this information I can try to come up with a custom program. I think we need two ingredients: Union values and complex filter expressions.
```
NestedLoopJoinExec: join_type=Inner, filter=coalesce(coalesce(EBV(LT(join_proj_push_down_6@0, join_proj_push_down_8@2)), false) AND coalesce(EBV(GT(join_proj_push_down_7@1, join_proj_push_down_9@3)), false), false), projection=[product@0, productLabel@1]
```
Column Types:
- `join_proj_push_down_6`: Large Union Type
- `join_proj_push_down_8`: Large Union Type
- `join_proj_push_down_7`: Large Union Type
- `join_proj_push_down_9`: Large Union Type
- `product`: `UInt32`
- `productLabel`: `UInt32`
### Expected behavior
Similar performance to DataFusion 49
### Additional context
Here is a flamegraph of the query sub plan on DataFusion 49 (Total Time: 4.2 ms):
<img width="1633" height="646" alt="Image" src="https://github.com/user-attachments/assets/9233d33b-9dbf-4663-b93c-e703aa2e1efe" />
Here is a flamegraph of the query sub plan on DataFusion 50 (Total Time: 190.2 ms):
<img width="1633" height="646" alt="Image" src="https://github.com/user-attachments/assets/d485d6f6-68a8-4b6d-ad06-e6b24ae5910b" />
There is also an interactive view on [CodSpeed](https://codspeed.io/tobixdev/rdf-fusion/branches/feature%2Fupdate-df-50?uri=bench%2Fbenches%2Fbsbm_explore.rs%3A%3Absbm_explore%3A%3Absbm_explore_10000_1_partition%3A%3ABSBM%2520Explore%252010000%2520%28target_partitions%3D1%29%2520-%2520Q5). You can switch between Base (DF 49) and Head (DF 50).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Nested Loop Join: Performance Regression in DataFusion 50 for Suboptimal Join Orderings [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on issue #17488:
URL: https://github.com/apache/datafusion/issues/17488#issuecomment-3287452130
> Per the comments above, let's close this ticket.
>
> [@tobixdev](https://github.com/tobixdev) / [@2010YOUY01](https://github.com/2010YOUY01) do you think it is worth tracking a potential performance improvement as a separate ticket, or is there mot much to do without causing other tradeoffs?
I have opened https://github.com/apache/datafusion/issues/17547, as a short summary of this issue's discussion.
I think it's worth trying to optimize this workload.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Nested Loop Join: Performance Regression in DataFusion 50 [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on issue #17488:
URL: https://github.com/apache/datafusion/issues/17488#issuecomment-3274655352
Yes, this reproducer totally makes sense.
DF in general is optimized for large inputs (batch size is several K, and the input consists of multiple batches), in such case we can expect an order of magnitude faster than traditional systems like Postgres, otherwise, with small inputs, the performance can degrade to close to traditional systems.
For this specific NLJ operator, it's inner logic is
```
for each right_batch:
for each left_row:
join(left_row, right_batch)
```
the inner-most `join()` function is optimized for large right batch with classical vectorization tricks. For large batch size, the amortized per-row cost will be very row; if this batch has only one row there is nothing to amortize.
The DF 49 version is using another high-level idea so that this small right case can be handled very efficiently, while at some other cost like huge memory usage.
Besides, this NLJ operator also assumes that the left side is the smaller side. This kind of workload is typically not optimized, mostly due to engineering cost — it's easier to implement something fast if users ensure it's used under specific constraints (in this case, large inputs with the smaller side on the left).
However, after checking the code, it seems fixable with some simple rules. I'll give it a try later this week, but if I find that it introduces too much extra complexity, I might give up considering the long-term maintainability.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Nested Loop Join: Performance Regression in DataFusion 50 for Suboptimal Join Orderings [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #17488:
URL: https://github.com/apache/datafusion/issues/17488#issuecomment-3285079247
Per the comments above, let's close this ticket.
@tobixdev / @2010YOUY01 do you think it is worth tracking a potential performance improvement as a separate ticket, or is there mot much to do without causing other tradeoffs?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Nested Loop Join: Performance Regression in DataFusion 50 [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on issue #17488:
URL: https://github.com/apache/datafusion/issues/17488#issuecomment-3271463087
In point 1: The difference I noticed so far is they're using different arrow kernel for repeating the same row: in `49.0` it's using `arrow_select::take()` with repeating indices for that `UnionArray`, in `50.0` it's using `ScalarValue::to_array_of_size` instead.
For point 2's expensive expression evaluation, I can't think of anything that has changed radically now.
Thanks for this interesting finding (and Codspeed looks cool — I’ll definitely check it out later). Do you have any runnable, maybe reduced, reproducer? I can help look into it.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Nested Loop Join: Performance Regression in DataFusion 50 for Suboptimal Join Orderings [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #17488:
URL: https://github.com/apache/datafusion/issues/17488#issuecomment-3288110701
THANK YOU!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Nested Loop Join: Performance Regression in DataFusion 50 [datafusion]
Posted by "tobixdev (via GitHub)" <gi...@apache.org>.
tobixdev commented on issue #17488:
URL: https://github.com/apache/datafusion/issues/17488#issuecomment-3274822960
> Besides, this NLJ operator also assumes that the left side is the smaller side. This kind of workload is typically not optimized, mostly due to engineering cost — it's easier to implement something fast if users ensure it's used under specific constraints (in this case, large inputs with the smaller side on the left).
> However, after checking the code, it seems fixable with some simple rules. I'll give it a try later this week, but if I find that it introduces too much extra complexity, I might give up considering the long-term maintainability.
Yeah I agree. Thanks for giving it a try, maybe there is a low-hanging fruit. I wanted to look into a better join ordering strategy for quite a while now, so this might be a good motivation.
That said, if this ends up adding complexity to the codebase, I agree it’s probably not worth pursuing. Please feel free to close the issue in that case. I think the reasoning is clear for anyone reading this later.
Either way, really appreciate your input!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Nested Loop Join: Performance Regression in DataFusion 50 [datafusion]
Posted by "tobixdev (via GitHub)" <gi...@apache.org>.
tobixdev commented on issue #17488:
URL: https://github.com/apache/datafusion/issues/17488#issuecomment-3274351360
You were right the reproducer wasnt quite there. I now improved it and I think we can now observe the issue. I consulted our query plan and basically tried to construct the physical plan directly as close as possible without copying further code.
My takeaway from that is that the implementation in DF 50 is more sensitive to a larger left side of the join. In the join that we are having issues with, the left side is 1224 rows, while the right side is a single row. DF 49 seems to perform on both workloads equally well. DF 50 seems to have problems with the larger left side. The planner will hide that problem (I think) as it will switch the join sides if possible. However, in our system were not quite there yet and therefore we currently have suboptimal joins.
Here are now the two files (exactly how I ran them). For switching between the larger left / right side, simply change the `LEFT_SIZE` and `RIGHT_SIZE` constants. I ran both of them with `cargo run --release` on an AMD Ryzen™ 9 9900X.
[repro-datafusion-49.zip](https://github.com/user-attachments/files/22252932/repro-datafusion-49.zip)
[repro-datafusion-50.zip](https://github.com/user-attachments/files/22253039/repro-datafusion-50.zip)
On a side note: I think, if we add statistics to our physical data source nodes the DF optimizer should be able to swap the sides. However, maybe we can still improve the situation if you have any ideas.
DataFusion 49:
```
NestedLoopJoin (left_size=1224, right_size=1):
Elapsed Time: 61.477 ms
Count: 13
Plan:
ProjectionExec: expr=[product@2 as product, product_label@3 as product_label, sim_property2@5 as sim_property2], metrics=[output_rows=13, elapsed_compute=1.443µs]
NestedLoopJoinExec: join_type=Inner, filter=compare(join_proj_push_down_1@0, join_proj_push_down_3@0) AND compare(join_proj_push_down_2@1, join_proj_push_down_4@1), metrics=[output_rows=13, elapsed_compute=2ns, build_input_batches=1, build_input_rows=1224, input_batches=1, input_rows=1, output_batches=1, build_mem_used=84544, build_time=19.747µs, join_time=61.445763ms]
DataSourceExec: partitions=1, partition_sizes=[1], metrics=[]
DataSourceExec: partitions=1, partition_sizes=[1], metrics=[]
NestedLoopJoin (left_size=1, right_size=1224):
Elapsed Time: 61.431 ms
Count: 13
Plan:
ProjectionExec: expr=[product@2 as product, product_label@3 as product_label, sim_property2@5 as sim_property2], metrics=[output_rows=13, elapsed_compute=1.092µs]
NestedLoopJoinExec: join_type=Inner, filter=compare(join_proj_push_down_1@0, join_proj_push_down_3@0) AND compare(join_proj_push_down_2@1, join_proj_push_down_4@1), metrics=[output_rows=13, elapsed_compute=2ns, build_input_batches=1, build_input_rows=1, input_batches=1, input_rows=1224, output_batches=1, build_mem_used=31472, build_time=28.734µs, join_time=61.393723ms]
DataSourceExec: partitions=1, partition_sizes=[1], metrics=[]
DataSourceExec: partitions=1, partition_sizes=[1], metrics=[]
```
DataFusion 50:
```
NestedLoopJoin (left_size=1224, right_size=1):
Elapsed Time: 1821.913 ms
Count: 1224
Plan:
ProjectionExec: expr=[product@2 as product, product_label@3 as product_label, sim_property2@5 as sim_property2], metrics=[output_rows=1224, elapsed_compute=6.081µs]
NestedLoopJoinExec: join_type=Inner, filter=compare(join_proj_push_down_1@0, join_proj_push_down_3@0) AND compare(join_proj_push_down_2@1, join_proj_push_down_4@1), metrics=[output_rows=1224, elapsed_compute=2ns, build_input_batches=1, build_input_rows=1224, input_batches=1, input_rows=1, output_batches=1, build_mem_used=83824, build_time=25.828µs, join_time=1.821812225s]
DataSourceExec: partitions=1, partition_sizes=[1], metrics=[]
DataSourceExec: partitions=1, partition_sizes=[1], metrics=[]
NestedLoopJoin (left_size=1, right_size=1224):
Elapsed Time: 60.65 ms
Count: 13
Plan:
ProjectionExec: expr=[product@2 as product, product_label@3 as product_label, sim_property2@5 as sim_property2], metrics=[output_rows=13, elapsed_compute=1.032µs]
NestedLoopJoinExec: join_type=Inner, filter=compare(join_proj_push_down_1@0, join_proj_push_down_3@0) AND compare(join_proj_push_down_2@1, join_proj_push_down_4@1), metrics=[output_rows=13, elapsed_compute=2ns, build_input_batches=1, build_input_rows=1, input_batches=1, input_rows=1224, output_batches=1, build_mem_used=30656, build_time=26.45µs, join_time=60.609296ms]
DataSourceExec: partitions=1, partition_sizes=[1], metrics=[]
DataSourceExec: partitions=1, partition_sizes=[1], metrics=[]
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Nested Loop Join: Performance Regression in DataFusion 50 [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on issue #17488:
URL: https://github.com/apache/datafusion/issues/17488#issuecomment-3273352390
I tried your reproducer, `branch-50` is 2x faster on my machine (M4 Pro Macbook):
1. Set a timer on the line that executes SQL
```rs
let start = std::time::Instant::now();
let results = df.collect().await.unwrap();
let elapsed = start.elapsed();
```
2. Run with `cargo run --release`, with different branch in `cargo.toml`
Note: Remove the comma in the sql, it seem not supported in DF49: `select 1,2, FROM` --> `select 1, 2 FROM ...`
`branch-49` is around 800ms, and `branch-50` is about 400ms. Maybe it's not enough to capture the behavior of the original benchmark?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Nested Loop Join: Performance Regression in DataFusion 50 [datafusion]
Posted by "Omega359 (via GitHub)" <gi...@apache.org>.
Omega359 commented on issue #17488:
URL: https://github.com/apache/datafusion/issues/17488#issuecomment-3271247739
Codspeed looks quite interesting, thanks for pointing it out
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Nested Loop Join: Performance Regression in DataFusion 50 [datafusion]
Posted by "tobixdev (via GitHub)" <gi...@apache.org>.
tobixdev commented on issue #17488:
URL: https://github.com/apache/datafusion/issues/17488#issuecomment-3273470200
> Maybe it's not enough to capture the behavior of the original benchmark?
Thanks for trying! I'll try it with release mode on my machine and provide an update.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Nested Loop Join: Performance Regression in DataFusion 50 [datafusion]
Posted by "tobixdev (via GitHub)" <gi...@apache.org>.
tobixdev commented on issue #17488:
URL: https://github.com/apache/datafusion/issues/17488#issuecomment-3271661746
Could it be that the function is called more often on smaller pieces of data? If yes, this could be the problem for 2.
Here is a minimal example that does something similar (even though I could not emulate the UDF yet). Unfortunately, I could only test it in debug mode, as I am now in a hurry. If you need more, I can help you tomorrow of the day after.
Just change the branch to `branch-49` in the Cargo.toml to see the difference.
DataFusion 50:
```
________________________________________________________
Executed in 8.17 secs fish external
usr time 8.05 secs 220.00 micros 8.05 secs
sys time 0.12 secs 561.00 micros 0.12 secs
```
DataFusion 49:
```
________________________________________________________
Executed in 7.40 secs fish external
usr time 132.61 millis 0.04 millis 132.57 millis
sys time 111.55 millis 1.08 millis 110.48 millis
```
Here is a zip of a profile (Debug Mode) and the zip of the source: Hopefully this works. Sorry I couldn't really test it due to the time constraints.
Thanks for looking into this!
[repro.zip](https://github.com/user-attachments/files/22239587/repro.zip)
[profile.json.gz](https://github.com/user-attachments/files/22239569/profile.json.gz)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Nested Loop Join: Performance Regression in DataFusion 50 for Suboptimal Join Orderings [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb closed issue #17488: Nested Loop Join: Performance Regression in DataFusion 50 for Suboptimal Join Orderings
URL: https://github.com/apache/datafusion/issues/17488
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org