ARROW-11806: [Rust][DataFusion] Optimize join / inner join creation of indices

This PR implements two optimizations

* Change the way we create an array of indices for an inner join to avoid generating a null bit map. It seems currently not really ergonomic to do this with Arrow without resorting to an iterator (which would be hard to do here). This is around 3% difference
* Allow to reuse allocations in `create_hashes` when possible. This is around 2% faster.

In total this gives a small (5%) speedup to query 5:

This PR:
```
Query 5 iteration 0 took 169.3 ms
Query 5 iteration 1 took 156.0 ms
Query 5 iteration 2 took 157.5 ms
Query 5 iteration 3 took 158.0 ms
Query 5 iteration 4 took 157.3 ms
Query 5 iteration 5 took 163.4 ms
Query 5 iteration 6 took 167.6 ms
Query 5 iteration 7 took 171.5 ms
Query 5 iteration 8 took 167.4 ms
Query 5 iteration 9 took 164.5 ms
Query 5 avg time: 163.26 ms
```

Master:
```
Query 5 iteration 0 took 177.6 ms
Query 5 iteration 1 took 169.6 ms
Query 5 iteration 2 took 171.8 ms
Query 5 iteration 3 took 175.1 ms
Query 5 iteration 4 took 167.2 ms
Query 5 iteration 5 took 171.1 ms
Query 5 iteration 6 took 174.2 ms
Query 5 iteration 7 took 178.1 ms
Query 5 iteration 8 took 167.9 ms
Query 5 iteration 9 took 172.0 ms
Query 5 avg time: 172.46 ms
```

Closes #9595 from Dandandan/opt_hash_join

Authored-by: Heres, Daniel <danielheres@gmail.com>
Signed-off-by: Andrew Lamb <andrew@nerdnetworks.org>
2 files changed
tree: 76dcafeee1195a7ce5b58b3c73fe0c0769124e38
  1. .asf.yaml
  2. .clang-format
  3. .clang-tidy
  4. .clang-tidy-ignore
  5. .dir-locals.el
  6. .dockerignore
  7. .env
  8. .gitattributes
  9. .github/
  10. .gitignore
  11. .gitmodules
  12. .hadolint.yaml
  13. .pre-commit-config.yaml
  14. .readthedocs.yml
  15. .travis.yml
  16. CHANGELOG.md
  17. CODE_OF_CONDUCT.md
  18. CONTRIBUTING.md
  19. LICENSE.txt
  20. NOTICE.txt
  21. README.md
  22. appveyor.yml
  23. c_glib/
  24. ci/
  25. cmake-format.py
  26. cpp/
  27. csharp/
  28. dev/
  29. docker-compose.yml
  30. docs/
  31. format/
  32. go/
  33. header
  34. java/
  35. js/
  36. julia/
  37. matlab/
  38. python/
  39. r/
  40. ruby/
  41. run-cmake-format.py
  42. rust/
README.md

Apache Arrow

Build Status Coverage Status Fuzzing Status License Twitter Follow

Powering In-Memory Analytics

Apache Arrow is a development platform for in-memory analytics. It contains a set of technologies that enable big data systems to process and move data fast.

Major components of the project include:

Arrow is an Apache Software Foundation project. Learn more at arrow.apache.org.

What's in the Arrow libraries?

The reference Arrow libraries contain many distinct software components:

  • Columnar vector and table-like containers (similar to data frames) supporting flat or nested types
  • Fast, language agnostic metadata messaging layer (using Google's Flatbuffers library)
  • Reference-counted off-heap buffer memory management, for zero-copy memory sharing and handling memory-mapped files
  • IO interfaces to local and remote filesystems
  • Self-describing binary wire formats (streaming and batch/file-like) for remote procedure calls (RPC) and interprocess communication (IPC)
  • Integration tests for verifying binary compatibility between the implementations (e.g. sending data from Java to C++)
  • Conversions to and from other in-memory data structures
  • Readers and writers for various widely-used file formats (such as Parquet, CSV)

Implementation status

The official Arrow libraries in this repository are in different stages of implementing the Arrow format and related features. See our current feature matrix on git master.

How to Contribute

Please read our latest project contribution guide.

Getting involved

Even if you do not plan to contribute to Apache Arrow itself or Arrow integrations in other projects, we'd be happy to have you involved: