How do distributed joins work in a distributed relational database system?

Question

I have been looking around for a few days trying to find a clear and concise description of how, at a technical/implementation level, how distributed joins work, but haven't found much. The best so far is in Track Join: Distributed Joins with Minimal Network Traffic. In this though they seem to suggest that every joined attribute is sent over the network to every other node, sort of like this (from another presentation):

Is that really how distributed joins generally work? Say I have 100 billion records per "table" (type), and two tables/types, and want to join on them to find some resulting set of records (along with a filtering condition). "Find all employees where e.department_id = department.id and department.category is 'design'" sort of thing. If there are billions of both types of records, scattered randomly (through hash-based partitioning) across 100 servers/nodes, how would the join typically work? Would you literally have to send all billions of nodes to every node in the network? That just seems like an enormous waste. What am I not interpreting correctly? Is there no other way to do it?

Answer 1

To make effective joins you would need indexes. Indexes could be either local the the data (index is on the same node as data) or global - index is partitioned independently of data.

In a local index case, the coordinator node would send requests to every other node, as the coordinator can not do any better decisions.

In a global index case, the coordinator would first deduct which nodes may have the information and go just there.

At the end of the day, the data needs to be collected at some node to be pre-processed before getting back to the client.

I recommend to dive on this topic: how does ElasticSearch (distributed cluster) executes a query: find all docs with words Alpha and Beta in it. And find top 10, then next 10 etc.