korowa commented on PR #8658:
URL:
https://github.com/apache/arrow-datafusion/pull/8658#issuecomment-1871434363
@metesynnada thank you!
Regarding explanations -- I've added extended explanation of how build phase
works in `HashJoinExec` docstring -- hope with this description of "the whole
picture", the other modified / added comments will make more sense.
Regarding performance -- benchmark results are
```
--------------------
Benchmark tpch_mem.json
--------------------
┏━━━━━━━━━━━━━━┳━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
┃ Query ┃ master ┃ hash_join_build_order ┃ Change ┃
┡━━━━━━━━━━━━━━╇━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
│ QQuery 1 │ 156.09ms │ 155.86ms │ no change │
│ QQuery 2 │ 36.49ms │ 36.30ms │ no change │
│ QQuery 3 │ 70.99ms │ 71.59ms │ no change │
│ QQuery 4 │ 61.01ms │ 58.94ms │ no change │
│ QQuery 5 │ 104.64ms │ 101.76ms │ no change │
│ QQuery 6 │ 16.71ms │ 16.67ms │ no change │
│ QQuery 7 │ 274.75ms │ 283.66ms │ no change │
│ QQuery 8 │ 65.54ms │ 65.67ms │ no change │
│ QQuery 9 │ 103.82ms │ 104.10ms │ no change │
│ QQuery 10 │ 123.52ms │ 123.01ms │ no change │
│ QQuery 11 │ 28.87ms │ 27.55ms │ no change │
│ QQuery 12 │ 50.39ms │ 52.08ms │ no change │
│ QQuery 13 │ 59.11ms │ 58.02ms │ no change │
│ QQuery 14 │ 21.04ms │ 18.94ms │ +1.11x faster │
│ QQuery 15 │ 47.09ms │ 46.57ms │ no change │
│ QQuery 16 │ 32.32ms │ 33.87ms │ no change │
│ QQuery 17 │ 150.53ms │ 140.37ms │ +1.07x faster │
│ QQuery 18 │ 324.83ms │ 322.20ms │ no change │
│ QQuery 19 │ 46.00ms │ 45.74ms │ no change │
│ QQuery 20 │ 83.35ms │ 83.45ms │ no change │
│ QQuery 21 │ 261.97ms │ 265.00ms │ no change │
│ QQuery 22 │ 28.01ms │ 25.16ms │ +1.11x faster │
└──────────────┴──────────┴───────────────────────┴───────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━┓
┃ Benchmark Summary ┃ ┃
┡━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━┩
│ Total Time (master) │ 2147.08ms │
│ Total Time (hash_join_build_order) │ 2136.50ms │
│ Average Time (master) │ 97.59ms │
│ Average Time (hash_join_build_order) │ 97.11ms │
│ Queries Faster │ 3 │
│ Queries Slower │ 0 │
│ Queries with No Change │ 19 │
└──────────────────────────────────────┴───────────┘
```
(faster queries probably are no more than outliers)
> I've noticed that with each new row addition, the previous row indices
need to be scanned, making the addition complexity linear instead of constant.
Could you, please, recheck or point the LOC where scanning takes place? If I
got it right -- the problem should be in `JoinHashMap::update_from_iter`, but
the worst case for insertion there seems to be
- obtain currently stored index index in hashmap for hash value
- place it at specific position in `next` vector
- update hashmap with a new index
which should not produce linear complexity :thinking: (at least it
definitely shouldn't perform worse than before)
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
