Skip to content

A join that returns a row selection instead of a materialised table #596

Description

@vbmithr

Summary

anti-join and the *-join family always materialise a result table. A
large share of our join calls immediately reduce that table to a boolean
mask, a row count, or a delete — the gathered columns are built and then
thrown away. There is no way to ask a join for the row selection alone.

Measurement

In a 30 s profile of a market-data service, gather_fn is 9.07% of samples
and the libc memcpy cluster is a further ~18%, all of it under the join
worker tasks — roughly a quarter of the process's CPU spent copying rows out
of joins. The three call sites responsible in our code are:

  • a mask for a delete: the join result is reduced to
    (> (fill 0 (get j 'n)) 0) and discarded;
  • anti-join used as "the rows of b not named by h", whose result
    immediately replaces b;
  • inner-join whose only consumer is (count …).

None of them needs the columns the join copies.

What we are asking for

A form of semi-join / anti-join that returns a row selection — a boolean
mask over the left side, or a row-id vector — rather than a table. Something
along the lines of:

(semi-mask [venue instrument] levels keys)   ; boolean vector, length (count levels)
(anti-mask [venue instrument] levels keys)   ; its complement

The executor already has the rowsel concept internally (the index routing
table describes filter sites "building the rowsel directly"), so this is
asking for an existing intermediate to be exposed rather than for new
machinery.

It composes with delete/select where: directly, which is where these
results are headed anyway, and it would let a caller count matches without
building them.

Why not just narrow the join

Selecting fewer columns first does not help: the cost is the gather over the
rows the join produces, and the key columns alone still get copied. What we
want is to not produce rows at all.


Measured on rayforce 2.6.2 (the build carrying bc350ddc).

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions