mcollina/node-levelgraph — pull request #11 by mcollina (2013-05-01 20:10:26+00:00)
Title: Hash join

I have built a benchmark unoptimizable with `getApproximateSize`: https://github.com/mcollina/node-levelgraph/blob/master/benchmarks/joinStream.js.

On my MBA I get around 2000 result/s.
Which is more than an order of magnitude lower that I get from `getStream`, which stays at around 30000 triples/s. Plain old LevelUp is at 40000 pair/s.

This is something an hash-join algorithm can fix, and I implemented it. As a key, something like: var1::var2, but only for common variables between streams: this can be done :tada:!

The hashJoin algorithm ticks around 9000 result/s. However memory explodes.

Things that are missing:
* [ ] abstract test for join algorithms
* [ ] separate test for the naive and hash algorithms
* [ ] create a mixes join-naive algorithms, to join as much as possible