Poisson Sampling over Acyclic Joins

This paper introduces a nearly instance-optimal algorithm for Poisson sampling over acyclic joins that utilizes a random-access index to efficiently generate samples without fully materializing the join result, demonstrating superior performance over existing methods while also serving as a competitive foundation for classical join processing.

The Gist

Imagine you are a chef trying to make a giant pot of soup for a festival. The recipe (your database query) requires you to mix ingredients from three different warehouses: Vegetables, Spices, and Broth.

If you want to know exactly what the final soup tastes like, you have to combine every single vegetable with every single spice and every single broth packet. In the world of databases, this is called a Join.

The Problem: The "Giant Soup" Trap

The problem is that if you have 1 million vegetables and 1 million spices, combining them all creates a theoretical pot with 1 trillion possible soup combinations.

• The Naive Approach: Most database systems would try to cook all 1 trillion combinations first, put them in a massive pot, and then try to scoop out a small cup for you to taste. This takes forever and wastes huge amounts of energy (and computer memory) on soup you'll never eat.
• The Goal: You want a small, representative cup of soup (a sample) without ever cooking the trillion-pot.

The New Idea: "Poisson Sampling"

The authors of this paper introduce a smarter way to get your sample. They call it Poisson Sampling.

Think of it like this: Instead of cooking the whole pot, you look at every potential soup combination in your head. For each one, you flip a special coin.

• If the coin says "Yes," you write down that recipe.
• If it says "No," you ignore it.

The tricky part is that these aren't fair coins. Some combinations are more likely to be chosen than others based on specific rules (e.g., "If the vegetable is a carrot, there's a 90% chance we keep it; if it's a turnip, only a 1% chance"). This is non-uniform sampling.

Doing this for 1 trillion potential combinations one by one is still too slow. So, the authors built a Magic Index.

The Solution: The "Library Card Catalog" (Index-and-Probe)

The paper proposes a two-step strategy called Index-and-Probe.

Step 1: Build the Map (The Index)

Instead of cooking the soup, you build a highly organized library card catalog.

• The Old Way (Chained): Imagine a library where books are chained together. To find the 500th book, you might have to walk down a long row of linked books. It's fast to build the library, but finding a specific book deep in the chain takes a bit of walking.
• The New Way (Unchained): Imagine a library where every book has a direct GPS coordinate. You can jump straight to the 500th book instantly. This is theoretically faster for finding things, but it takes a lot of extra work and space to build the library in the first place.

The authors tested both. Surprisingly, they found that the "Chained" library (CSR) was actually faster in the real world. Why? Because the "walking" was so short and the library was built so quickly that it beat the "GPS jump" method, which spent too much time setting up the coordinates.

Step 2: The Smart Scoop (Probing)

Once the map is built, you don't walk through the whole library. You use a Smart Scoop algorithm:

1. The "Geo" Strategy: If you only need a few books (low probability), you skip huge chunks of the library at once, like skipping stones across a pond.
2. The "Bern" Strategy: If you need almost all the books (high probability), it's faster to just walk down the aisle and pick them up one by one.
3. The Hybrid: The authors created a smart system that switches between these two strategies automatically, depending on how many books you need.

The Real-World Test: The Disease Simulator

To prove this works, the authors used a real-world scenario: Simulating a disease outbreak (like the flu or COVID).

• They had to simulate millions of people meeting each other in schools, homes, and workplaces.
• The "Join" (all possible meetings) was massive (10 trillion combinations).
• The "Sample" (actual infections) was much smaller.

Using their new method, they could simulate the spread of disease up to 6 times faster than the old methods. They didn't have to calculate every single possible handshake; they just calculated the ones that were likely to happen.

The Big Takeaway

The paper teaches us a valuable lesson about computer engineering: Theoretically perfect isn't always practically best.

• The "Unchained" method (GPS coordinates) looked perfect on paper (faster access time).
• The "Chained" method (linked lists) looked slightly slower on paper.
• But in the real world, the Chained method won because it was easier to build and played better with the computer's memory (CPU cache).

In summary: The authors built a system that lets you grab a random handful of results from a massive database join without ever having to compute the entire result. It's like tasting a spoonful of soup without having to cook the whole ocean. They found that the "messy" but quick-to-build approach works better than the "perfect" but slow-to-build approach.

Technical Summary

Here is a detailed technical summary of the paper "Poisson Sampling over Acyclic Joins" by Bekkers et al.

1. Problem Statement

The paper addresses the problem of Poisson sampling over acyclic join queries.

• Context: Traditional sampling often involves drawing a fixed-size uniform sample from a query result. However, many applications (e.g., epidemiological simulations in the EpiQL language) require Poisson sampling, where each tuple in the join result has a specific, potentially non-uniform probability $p \in [0, 1]$ of being included in the sample.
• The Challenge: A naive approach involves materializing the full join result $Q(db)$ and then performing a Bernoulli trial for every tuple. This is inefficient because the full join result can be orders of magnitude larger than the input database or the desired sample size (e.g., $10^{10}$tuples vs.$10^8$ samples).
• Goal: Develop an algorithm that computes a Poisson sample without materializing the full join result, achieving near instance-optimality in terms of asymptotic complexity.

2. Methodology

The authors propose an Index-and-Probe (I&P) strategy consisting of three main steps:

1. Index Construction: Build a random-access index for the join query that allows retrieving the $i$-th tuple of the join result without materializing the entire result.
2. Position Sampling: Determine the sequence of tuple positions (offsets) in the virtual join result that should be included in the sample based on their specific probabilities.
3. Probing: Use the index to retrieve only the tuples at the sampled positions.

A. Random-Access Indexing (Shredded Representations)

The paper leverages the Nested Semijoin Algebra (NSA) and the Shredded Yannakakis (SYA) framework to represent nested relations as collections of flat physical relations (columnar storage). Two specific implementations are compared:

1. Chained Shredded Representation (CSR):

   • Based on linked lists (nxt pointers) to chain tuples sharing the same join key.
   • Access Time: $O(\log |db| + d)$, where $d$ is the maximum join degree. It uses linear traversal for linked lists.
   • Construction: Linear time $O(|db|)$, requiring only one pass over the data for grouping.
   • Key Insight: Despite having worse asymptotic access time than USR, CSR is often faster in practice due to better cache locality and lower construction overhead.

2. Unchained Shredded Representation (USR):

   • Based on the theoretical random-access index by Carmeli et al. [6].
   • Access Time: $O(\log |db|)$, achieved by storing tuples consecutively and using binary search (via start, len, and pref columns).
   • Construction: Requires two hashing passes over the data, making it slower to build than CSR.
   • Trade-off: Theoretically optimal access time, but higher constant factors in construction and probing for low-degree joins.

B. Position Sampling

The algorithm must generate the sequence of offsets to probe.

• Uniform Case: Compares three strategies:
  • Bern: Perform a Bernoulli trial for every tuple ($O(n)$). Slow for small $p$.
  • Geo: Sample gaps using a geometric distribution ($O(k)$). Fast for small $p$, but slow for large $p$ due to overhead.
  • Hybrid: Dynamically switches between Geo and Bern based on a threshold (experimentally determined as $p=0.5$).
• Non-Uniform Case: The problem is reduced to a series of uniform sampling steps. The algorithm iterates over nested tuples, grouping them by their sampling probability, and applies the Hybrid method to each group.

3. Key Contributions

1. Problem Definition: Formalized Poisson sampling over joins, generalizing fixed-size uniform sampling.
2. Algorithm Design: Proposed an Index-and-Probe algorithm for acyclic joins with data complexity $O(|db| + k \log |db|)$, where $k$ is the sample size. This is nearly instance-optimal.
3. Engineering Trade-offs:
   • Demonstrated that CSR (with linear access) outperforms USR (with logarithmic access) in end-to-end runtime for most real-world scenarios due to faster index construction and better cache performance.
   • Designed a Hybrid position sampling method that adapts to the sampling probability distribution.
4. Unified Engine Design: Showed that CSR can serve as a single, robust basis for both classical acyclic join processing (Yannakakis algorithm) and Poisson sampling, eliminating the need for separate, complex sampling-specific engine internals.

4. Experimental Results

The methods were implemented in Apache DataFusion (Rust-based columnar engine) and tested on:

• Benchmarks: JOB (Join Order Benchmark) and STATS-CEB.
• Real-world Use Case: EpiQL (Infectious disease simulation with $10^7$ individuals).

Key Findings:

• Performance vs. Baseline: The proposed I&P method (specifically CSR + Hybrid) is up to 6.08x faster than the naive "Materialize-and-Scan" (M&S) approach.
• CSR vs. USR:
  • CSR consistently outperformed USR in end-to-end sampling time across all benchmarks, despite USR's theoretical $O(\log |db|)$ access advantage.
  • Reason: CSR's faster construction time and the fact that linked-list traversal is often faster than binary search for the low join degrees typical in these datasets.
  • Full Joins: CSR and USR were competitive for computing full joins, validating CSR as a universal choice.
• Sampling Probability: The Hybrid method successfully adapted to varying probabilities, outperforming pure Geo or Bern strategies in different regimes.
• Scalability: In the EpiQL scenario (11M people), the method avoided memory exhaustion (which occurred with binary joins) and provided significant speedups (5.3x over M-CSYA).

5. Significance

• Theoretical Impact: Proves that Poisson sampling over acyclic joins can be solved with the same asymptotic complexity as fixed-size sampling, bridging a gap between theoretical database theory and practical simulation needs.
• Practical Impact: Provides a concrete, high-performance implementation strategy for column stores. It demonstrates that "theoretically optimal" structures (like USR) are not always practically superior due to constant factors and hardware characteristics (caching).
• Engine Design: Offers a compelling argument for database engine designers to adopt a single, unified strategy (CSR-based SYA) for both standard join processing and advanced sampling, simplifying engine architecture while maintaining high performance for both tasks.
• Application: Directly enables efficient execution of complex epidemiological and agent-based simulations (like EpiQL) that rely on probabilistic join operations, which were previously intractable due to the massive size of intermediate join results.