  Joining records with all other records that meet a linkage condition can
result in an astronomically large number of combinations due to many-to-many
relationships. For such challenging (acyclic) joins, a random sample over the
join result is a practical alternative to working with the oversized join
result. Whereas prior works are limited to uniform join sampling where each
join row is assigned the same probability, the scope is extended in this work
to weighted sampling to support emerging applications such as scientific
discovery in observational data and privacy-preserving query answering.
Notwithstanding some naive methods, this work presents the first approach for
weighted random sampling from join results. Due to a lack of baselines,
experiments over various join types and real-world data sets are conducted to
show substantial memory savings and competitive performance with main-memory
index-based approaches in the equal-probability setting. In contrast to
existing uniform sampling approaches that require prepared structures that
occupy contested resources to squeeze out slightly faster query-times, the
proposed approaches exhibit qualities that are urgently needed in practice,
namely reduced memory footprint, streaming operation, support for selections,
outer joins, semi joins and anti joins and unequal-probability sampling. All
pertinent code and data can be found at:
https://github.com/shekelyan/weightedjoinsampling
