search

apache / arrow

Apache Arrow is a multi-language toolbox for accelerated data interchange and in-memory processing
https://arrow.apache.org/
Apache License 2.0
14.31k stars 3.48k forks source link

[C++] Improve future as-of-join algorithmic complexity #36144

Open rtpsw opened 1 year ago

rtpsw commented 1 year ago

Describe the enhancement requested

Currently, the algorithmic complexity of future as-of-join is super-linear in the input size because the MemoStore is scanning all keys when cleaning up entries by-time.; this is due to the current entry data structures used in MemoStore. The algorithmic complexity should be improved to be linear.

Component(s)

C++

rtpsw commented 1 year ago

take