Optimise the Performance of an As-of Join

Question

How can the performance of an aj between a trades table and a quotes table be optimised?

Solution

• For in-memory joins: ensure the table is sorted by time within each symbol group.
• Apply a grouped (`g#) or parted (`p#) attribute to the column being matched on (sym).
• For on-disk tables: apply the parted attribute to the keyed column (typically sym), and again ensure time is sorted within each sym group.

Explanation

aj relies on a binary search through each match group's time values, so the requirement that makes the join correct — time sorted within each sym — is also what makes it fast: a binary search needs only a handful of comparisons per lookup instead of a scan.

Attributes speed up the other half of the lookup — finding which rows belong to a given sym group in the first place. The grouped attribute (`g#) builds a hash index for fast lookup regardless of physical row order; the parted attribute (`p#) is even more effective when the data is also physically sorted by that column, since it lets q jump directly to a contiguous block of rows for a symbol instead of scanning.

For on-disk (splayed or partitioned) tables, the same logic carries over to the file system: data is naturally append-ordered by time as it arrives, so applying the parted attribute to the symbol column — and keeping time sorted within each symbol's block — lets aj skip straight to the relevant disk blocks instead of reading the whole table into memory first.