Compare with results of AIList - some performance bottleneck for larger # of rows returned?

[mwiewior]

Check results - from AIList readme:

0, 4	7.512s	14.102s	6.573s	11.430

whereas our ~80s: test Coitrees-Medium-Medium-6-8-chainRn4-chainVicPac2 ... bench: 82630613406 ns/iter (+/- 31867343) test IntervalTree-Medium-Medium-6-8-chainRn4-chainVicPac2 ... bench: 84154500125 ns/iter (+/- 1509363265) test ArrayIntervalTree-Medium-Medium-6-8-chainRn4-chainVicPac2 ... bench: 87261188729 ns/iter (+/- 1237498415)

while

0, 1	0.441s	0.440s	0.774s	0.882s

and ours 0.1-0.2s test Coitrees-Medium-Small-6-1-chainRn4-fBrain ... bench: 131181208 ns/iter (+/- 845876) test IntervalTree-Medium-Small-6-1-chainRn4-fBrain ... bench: 250664333 ns/iter (+/- 1609728) test ArrayIntervalTree-Medium-Small-6-1-chainRn4-fBrain ... bench: 221450572 ns/iter (+/- 622091) test AIList-Medium-Small-6-1-chainRn4-fBrain ... bench: 257095135 ns/iter (+/- 44856)

https://github.com/databio/AIList

[mwiewior]

Analyzing results: 0,4:

[2024-11-17T10:48:27Z INFO  sequila_core::physical_planner::sequila_query_planner] Creating physical plan for logical plan: Aggregate: groupBy=[[]], aggr=[[count(Int64(1)) AS count(*)]]
[2024-11-17T10:48:27Z INFO  sequila_core::physical_planner::sequila_physical_planner] HashJoinExec detected
[2024-11-17T10:48:27Z INFO  sequila_core::physical_planner::sequila_physical_planner] Detected HashJoinExec with Range filters. Optimizing into IntervalJoinExec using Coitrees algorithm...
[2024-11-17T10:48:27Z INFO  sequila_core::physical_planner::joins::interval_join] ThreadId(1) is done building a hash table from 288 batches, 2350965 rows, took 86 ms
[2024-11-17T10:49:48Z INFO  sequila_core::physical_planner::joins::interval_join] ThreadId(1) finished execution, total processed batches: 939, total join time: 31893 ms
+------------+
| count(*)   |
+------------+
| 3898481884 |
+------------+
1 row(s) fetched. 
Elapsed 81.721 seconds.

@pkhamutou here is also sth strange IT build time: 86ms, join time ~32s - so what we're using the remaining 50s for (elapsed time ~82s)?

0,1

[2024-11-17T10:52:47Z INFO  sequila_core::physical_planner::sequila_query_planner] Creating physical plan for logical plan: Aggregate: groupBy=[[]], aggr=[[count(Int64(1)) AS count(*)]]
[2024-11-17T10:52:47Z INFO  sequila_core::physical_planner::sequila_physical_planner] HashJoinExec detected
[2024-11-17T10:52:47Z INFO  sequila_core::physical_planner::sequila_physical_planner] Detected HashJoinExec with Range filters. Optimizing into IntervalJoinExec using Coitrees algorithm...
[2024-11-17T10:52:47Z INFO  sequila_core::physical_planner::joins::interval_join] ThreadId(1) is done building a hash table from 288 batches, 2350965 rows, took 76 ms
[2024-11-17T10:52:47Z INFO  sequila_core::physical_planner::joins::interval_join] ThreadId(1) finished execution, total processed batches: 25, total join time: 21 ms
+----------+
| count(*) |
+----------+
| 321138   |
+----------+
1 row(s) fetched. 
Elapsed 0.114 seconds.

here it makes more sense: IT:80ms + join 21ms that makes ~0.1s which is ~= elapsed time

[mwiewior]

@pkhamutou Seems like the problem is when there is a great number of rows returned - maybe some unnecessary memory copy/allocation?

[mwiewior]

I ran coitrees only counting the intervals in a basic program and it takes <5s for the join itself and ~7s with reading parquet and building IT - to ~ 10x faster than in SeQuiLa at the moment.

time RUSTFLAGS="-C target-cpu=native" RUST_LOG=info cargo run --release

[2024-11-17T14:51:40Z INFO  join_test] Overlaps [Coitrees]: 3898481884
[2024-11-17T14:51:40Z INFO  join_test] Query time [Coitrees]: 4.742363292s
[2024-11-17T14:51:40Z INFO  join_test] ---------------------------------
RUSTFLAGS="-C target-cpu=native" RUST_LOG=info cargo run --release  6.88s user 0.15s system 97% cpu 7.232 total