Module semijoin_idempotence

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.

Structs

• Replacement 🔒
  A restricted form of a semijoin idempotence information.
• SemijoinIdempotence
  Remove redundant semijoin operators

Functions

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