Join algorithms for JavaScript Arrays using lodash
APACHE-2.0 License
A library providing join algorithms for JavaScript Arrays. LoDash is the only dependency and this library appends itself as an extension to that library.
Lodash already supports some standard SQL-like features:
Limit and offset can be accomplished using Array.slice
.
These functions only work on arrays of objects (comparable to database rows). Key comparisons are coercive, so Dates should work as well.
For merge-type joins, a merger function may be provided to customize the output array. By default, all joined rows are generated from
LoDash's assign
function:
_.assign({}, leftRow, rightRow);
A merger function takes both the left and right record and provides a new output record. The left or right record may be
null
in cases like outer joins which do not have matching row keys.
Order of the output is indeterminate.
<
, >
), and should expect keys of the same type (#43)Each join function accepts two arrays and two accessor functions for each array that will act as the pluck function for key comparison.
_.joinFunction(leftArray, leftKeyAccessor, rightArray, rightKeyAccessor, merger);
> var _ = require('lodash-joins');
> var left = [
... {id: 'c', left: 0},
... {id: 'c', left: 1},
... {id: 'e', left: 2},
... ],
... right = [
... {id: 'a', right: 0},
... {id: 'b', right: 1},
... {id: 'c', right: 2},
... {id: 'c', right: 3},
... {id: 'd', right: 4},
... {id: 'f', right: 5},
... {id: 'g', right: 6}
... ],
... accessor = function (obj) {
... return obj['id'];
... };
>
> var a = _.hashInnerJoin(left, accessor, right, accessor);
undefined
> a
[ { id: 'c', left: 0, right: 2 },
{ id: 'c', left: 1, right: 2 },
{ id: 'c', left: 0, right: 3 },
{ id: 'c', left: 1, right: 3 } ]
>
> var b = _.nestedLoopLeftOuterJoin(left, accessor, right, accessor);
undefined
> b
[ { id: 'c', left: 0, right: 2 },
{ id: 'c', left: 0, right: 3 },
{ id: 'c', left: 1, right: 2 },
{ id: 'c', left: 1, right: 3 },
{ id: 'e', left: 2 } ]
>
> var c = _.sortedMergeFullOuterJoin(left, accessor, right, accessor);
undefined
> c
[ { id: 'a', right: 0 },
{ id: 'b', right: 1 },
{ id: 'c', left: 0, right: 2 },
{ id: 'c', left: 0, right: 3 },
{ id: 'c', left: 1, right: 2 },
{ id: 'c', left: 1, right: 3 },
{ id: 'd', right: 4 },
{ id: 'e', left: 2 },
{ id: 'f', right: 5 },
{ id: 'g', right: 6 } ]
Tested using Jasmine and Karma. See the /spec
directory. There is also a browser test invoked through
Webpack and Mocha.
Typically for the Inner & Outer joins, with larger arrays stick with the Sorted Merge, then Hash, then Nested. With the Anti & Semi joins, Nested can outperform when there is a small cardinality of keys, but Hash may be more efficient since only one of the Arrays needs to be hashed.
Each suite performs three joins on randomly generated arrays with string keys. The sizes 'Large', 'Medium' and 'Small' correlate to the size of the join arrays being used, i.e. 1000, 100, 10 respectively.
Running suite Full Outer Joins Large...
Running suite Full Outer Joins Medium...
Running suite Full Outer Joins Small...
Running suite Inner Joins Large...
Running suite Inner Joins Medium...
Running suite Inner Joins Small...
Running suite Left Anti Joins Large...
Running suite Left Anti Joins Medium...
Running suite Left Anti Joins Small...
Running suite Left Outer Joins Large...
Running suite Left Outer Joins Medium...
Running suite Left Outer Joins Small...
Running suite Left Semi Joins Large...
Running suite Left Semi Joins Medium...
Running suite Left Semi Joins Small...