[C++] Naive spillover implementation for join

[asfimport]

A join is a pipeline breaker. I believe the proposed join operators assume that the data can fit into memory and queue all incoming batches. For example, if I understand correctly, #11150 queues the right side until the left side had finished.

There are many clever and interesting ways that this can be optimized (divide & conquer, recursive query, prioritize reading the left side and pause the right side read). This issue is intentionally not clever or interesting.

Instead, I think it would be good to take advantage of this opportunity to start fleshing out our spillover capabilities. A very simplistic implementation could be a standalone node which has 2 inputs and 2 outputs. The node queues up all incoming data on the "right" input and lets the "left" input pass through. Then, when the left input has finished the node will release the right input.

This node could then implement a basic spillover mechanism (e.g. IPC to disk) and start to flesh out the abstractions that we will eventually want to handle different spillover strategies (abort on spill, spill to disk, and spill to s3 are all I can think of at the moment).

Reporter: Weston Pace / @westonpace
Assignee: Sasha Krassovsky / @save-buffer

Related issues:

• [C++] Support hash-join on larger than memory datasets (is superceded by)

_{Note: This issue was originally created as ARROW-14163. Please see the migration documentation for further details.}

[asfimport]

Weston Pace / @westonpace:
It appears this will be addressed by ARROW-16389