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.