Expand description

Remove semijoins that are applied multiple times to no further effect.

Mechanically, this transform looks for instances of A join B and replaces B with a simpler C. It does this in the restricted setting that each join would be a “semijoin”: a multiplicity preserving restriction.

The approach we use here is to restrict our attention to cases where

  1. A is a potentially filtered instance of some Get{id},
  2. A join B equate columns of A to all columns of B,
  3. The multiplicity of any record in B is at most one.
  4. The values in these records are exactly Get{id} join C.

We find a candidate C by descending B looking for another semijoin between Get{id} and some other collection D on the same columns as A means to join B. Should we find such, allowing arbitrary filters of Get{id} on the equated columns, which we will transfer to the columns of D thereby forming C.


A restricted form of a semijoin idempotence information.
Remove redundant semijoin operators




Attempts to interpret expr as filters applied to a Get.
Attempt to simplify the join using local information and let bindings.
True iff some unique key of input is contained in the keys of map.
Return a list of potential semijoin replacements for expr.
Return a list of potential semijoin replacements for expr.
Determines bijection between equated columns of a binary join.
Evaluates the viability of a candidate to drive the replacement at semijoin.