3 ms·

15 years ago I was working on a similar distributed DB product. At the time, the idea was to send the query execution plan to each node to execute any filterin

by ww520 10y ago

15 years ago I was working on a similar distributed DB product. At the time, the idea was to send the query execution plan to each node to execute any filtering criteria to trim down the candidate row set. Then compute a Bloom Filter on the joining keys on the node with the largest candidate set (using some heuristic statistics), ship the Bloom Filter to other nodes with smaller data set to greatly reduce the non-matching rows. The rows survived the Bloom Filter are highly likely joinable and are shipped back to the main joining node to perform the final join. Bloom Filter is the perfect compromise between size and speed. I'd imagine CockroachDB is doing something similar for distributed join.

irfansharif 10y ago
haven't come across this idea before, interesting - will definitely have to give it some more thought. our 'distributed joins', so to speak, run through our distributed query execution model (distsql) setting up incremental 'stages' of computation with the results pipelined and plumbed through individual computes. viewing it through this model our implementation more closely resembles the Grace Hash Join[1] algorithm. you might be interested in the PR[2] that landed this changeset, there's a cool visualization in one of the comments[3] showing the query execution plan. [1]: https://en.wikipedia.org/wiki/Hash_join#Grace_hash_join https://en.wikipedia.org/wiki/Hash_join#Grace_hash_join [2]: https://github.com/cockroachdb/cockroach/pull/12221 https://github.com/cockroachdb/cockroach/pull/12221 [3]: https://github.com/cockroachdb/cockroach/pull/12221#issuecomment-267084941 https://github.com/cockroachdb/cockroach/pull/12221#issuecom...
- ww520 10y ago
  The Grace Hash Join approach ships the entire joining key set across network. Even if each node just get one partition of it, the aggregate network traffic is the entire set. For small table, it's fine. Large table is going to really tax the network.
sixdimensional 10y ago
I've heard of pushdown techniques including function, predicate and aggregate pushdown in distributed relational engines before. Another interesting idea I read about (I can't find it anywhere online) was called "join zippering". Basically you first request the cluster to solve a join by querying and streaming the key columns from a join predicate back into the cluster itself to identify which nodes have matches and then streaming the results from each node in parallel, and doing the join in the stream. This is hard stuff but so cool too :)
- irfansharif 10y ago
  > This is hard stuff but so cool too I agree! we have some semblances of pushdown filtering across aggregations and some other interesting techniques as documented in the RFC[1] that first proposed the distributed execution model. [1]: https://github.com/cockroachdb/cockroach/blob/master/docs/RFCS/distributed_sql.md https://github.com/cockroachdb/cockroach/blob/master/docs/RF...

by ww520 10y ago

irfansharif 10y ago

haven't come across this idea before, interesting - will definitely have to give it some more thought. our 'distributed joins', so to speak, run through our distributed query execution model (distsql) setting up incremental 'stages' of computation with the results pipelined and plumbed through individual computes. viewing it through this model our implementation more closely resembles the Grace Hash Join[1] algorithm. you might be interested in the PR[2] that landed this changeset, there's a cool visualization in one of the comments[3] showing the query execution plan. [1]: https://en.wikipedia.org/wiki/Hash_join#Grace_hash_join https://en.wikipedia.org/wiki/Hash_join#Grace_hash_join [2]: https://github.com/cockroachdb/cockroach/pull/12221 https://github.com/cockroachdb/cockroach/pull/12221 [3]: https://github.com/cockroachdb/cockroach/pull/12221#issuecomment-267084941 https://github.com/cockroachdb/cockroach/pull/12221#issuecom...

ww520 10y ago
The Grace Hash Join approach ships the entire joining key set across network. Even if each node just get one partition of it, the aggregate network traffic is the entire set. For small table, it's fine. Large table is going to really tax the network.

sixdimensional 10y ago

I've heard of pushdown techniques including function, predicate and aggregate pushdown in distributed relational engines before. Another interesting idea I read about (I can't find it anywhere online) was called "join zippering". Basically you first request the cluster to solve a join by querying and streaming the key columns from a join predicate back into the cluster itself to identify which nodes have matches and then streaming the results from each node in parallel, and doing the join in the stream. This is hard stuff but so cool too :)

irfansharif 10y ago
> This is hard stuff but so cool too I agree! we have some semblances of pushdown filtering across aggregations and some other interesting techniques as documented in the RFC[1] that first proposed the distributed execution model. [1]: https://github.com/cockroachdb/cockroach/blob/master/docs/RFCS/distributed_sql.md https://github.com/cockroachdb/cockroach/blob/master/docs/RF...