Module Talon.Join

left |> Query.join ~on right pairs the rows of left and right that the condition on matches. A condition is a value, a conjunction of atoms built with (&&) inside Join.( … ), as in Join.(keys [ "ticker" ] && eq "day" "date"). An atom names a left column, then a right column. A kind says which rows are kept, and a count how many matches each row must have. Each condition runs as one algorithm (Algorithms).

Matching. A join keeps exactly the pairs of rows on which every atom holds. It is the join on all, restricted to those pairs. An equality atom holds by key identity (Type.compare_value), so null keys match. A comparison holds where Expr.(<) or its sibling is true on the two values, in talon's total order (NaN after every number and -0. equal to 0.), and never at a null. A value cannot fail a join, and a null or a period whose values come in either order (overlaps) changes only which pairs match.

Columns. A Semi or Anti join has the left columns. Another join has the left columns, then the right columns without those of equality atoms, in order, so the key of eq l r appears once, as l. In a Full join that key has the common type of l and r (Type.common), since an unmatched right row gives it r's value. Every other column keeps its type. Except in a Semi or Anti join, a name on both sides is a problem, and talon adds no suffixes. Rename one side first.

Order. A join's rows come in left's order, each left row followed by its matches in right's order, and a Full join then appends right's unmatched rows in order.

Conditions

Algorithms

• A condition of equality atoms alone (keys, eq) runs as an equality join, in O(n + m + matches) for sides of n and m rows.
• Equality atoms, if any, with at least one comparison (lt, le, gt, ge, inside) or overlaps run as a range join (Range joins).
• position takes no other atom and runs as its own algorithm.
• all, the condition with no atom, runs every pair, so all && c is c.

Range joins

A range join sorts one side's rows within their equality keys, the columns of its equality atoms, by the band column. Each row of the other side searches that order for its band, the rows the bounding atoms select. The band column is the column that comparisons name most, where a left and a right column of one name are two columns. On a tie between the sides it is the right column, and on a tie within a side the one written first. If the condition has an overlaps, the first one bounds the band and each side is sorted by its periods' starts. Otherwise the comparisons that name the band column bound the band, when they meet that column at the type of the first such comparison. Every other comparison or overlaps is tested on each pair the bands read.

Cost of a range join

A side needs no sort when its rows come grouped by their equality keys, each group ascending in the band column, which the join checks by reading them. The right side of an overlaps needs none when its rows come grouped that way by their periods' starts. A range join whose bands read p pairs, on a side of s rows searched from a side of o rows, costs O(s log s + o log s + p), less the sort when the side needs none. Matches out of the join's order are reordered once. An overlaps join sorts and searches each side. When every atom but the equality atoms bounds the band, a Semi or Anti join costs O(s log s + o log s), and the checks of each_left and each_right add no p term.

Kinds and counts