Adaptive SQL Join Algorithms for Skewed Data

ISEF Category: Systems Software

Subcategory: Algorithms  ·  Difficulty: Advanced  ·  Setup: University Lab  ·  Time: Full Year

The Hook

A bad join choice can turn a fast SQL query into a slog. On skewed data, one table value can appear far more often than the others, and that can break simple rules of thumb. You can build an algorithm that spots that pattern early and switches plans before the query slows down.

What Is It?

An SQL join combines rows from two tables when they match on a key. Think of it like pairing students from two class lists by ID. A hash join and a sort-merge join both solve that matching problem, but they work better under different data shapes. Your project studies when to pick each one during the query, not just before it starts.

The key idea is skew. Skewed data means some values show up much more often than others. That can overload one part of a hash table or make a merge step easier, depending on the pattern. Your algorithm watches the data as it runs, builds online histograms, which are running counts of value frequencies, and uses that signal to switch between join strategies. Reinforcement learning means the program learns which choice pays off over time, based on past query results.

Why This Is a Good Topic

This is a strong science fair topic because you can test it with real query workloads, clear metrics, and repeatable data changes. You are not guessing about success, you are measuring query time, memory use, and plan quality under different levels of skew. The topic connects to database systems used in analytics, finance, and search, so the real-world value is easy to explain. You can also learn how query optimizers make decisions, how data distribution changes performance, and how to compare algorithms with fair experiments.

Research Questions

• How does data skew affect the runtime of a top-k join under hash join and sort-merge join plans?
• What is the effect of online histogram accuracy on the join strategy selected during execution?
• Does a reinforcement-learning policy choose a better join switch point than a fixed heuristic on skewed SQL benchmarks?
• To what extent does the adaptive join reduce peak memory use compared with DuckDB defaults on skewed TPC-H variants?
• Which histogram binning strategy produces the most reliable join plan choice for heavy-tailed key distributions?
• How does the fraction of rare versus common keys change the benefit of mid-query strategy switching?

Basic Materials

• Laptop or desktop computer with at least 16 GB RAM.
• DuckDB installed locally.
• Python 3 with pandas and numpy.
• Jupyter Notebook or another notebook environment.
• Synthetic data generator for skewed tables.
• TPC-H benchmark data generator or publicly available sample datasets.
• Git for version control.
• Spreadsheet software for plotting results.

Advanced Materials

• University or lab workstation with higher RAM and multi-core CPU.
• PostgreSQL or another reference database system for comparison.
• SQL query profiler or execution-plan viewer.
• Python packages for reinforcement learning experiments.
• Apache Arrow or Parquet tools for faster data handling.
• Benchmark harness for repeated query runs.
• Logging framework for per-query statistics.
• Optional access to a CPU performance monitor for cache and branch metrics.

Software & Tools

• DuckDB: Runs analytical SQL queries locally and gives a baseline for comparing join plans.
• Python: Generates skewed datasets, controls experiments, and analyzes results.
• Jupyter Notebook: Helps you document experiments, plots, and notes in one place.
• pandas: Organizes benchmark outputs and makes runtime comparisons easier.
• ImageJ: Not needed here, so skip visual tools and focus on query logs and timing data.

Experiment Steps

1. Define the join task you will study, including the exact top-k query shape and the skew pattern you want to test.
2. Choose one outcome metric first, then decide whether runtime, memory use, or plan stability will be your main score.
3. Design a baseline plan set, such as fixed hash join and fixed sort-merge join, so you have something honest to compare against.
4. Build a data-generation scheme that creates several levels of skew and preserves the same table sizes across runs.
5. Plan the adaptive logic, including what signal the online histogram gives you and when the algorithm is allowed to switch strategies.
6. Set up repeated trials, then compare your adaptive method against the baseline across all skew levels with the same hardware and query settings.

Common Pitfalls

• Testing only one skew level, which can make the adaptive method look better than it really is.
• Letting query warm-up effects mix with real measurements, which hides the true runtime change.
• Comparing different query outputs without checking that every version returns the same top-k rows.
• Training the reinforcement policy on the same data used for final evaluation, which inflates the result.
• Ignoring memory pressure, which can make a fast-looking join fail when the data gets larger.

What Makes This Competitive

A stronger project goes beyond one speed comparison. You can study when the adaptive switch helps, when it hurts, and why, then back that up with clean measurements across many skew patterns. A competitive version also uses a fair baseline, careful repeated trials, and a clear analysis of false switches, overhead, and memory use. If you find a new threshold rule or a better reward signal, that gives your project real research value.

Project Variations

• Test the same adaptive join idea on star-schema warehouse queries instead of TPC-H joins.
• Replace reinforcement learning with a lightweight bandit rule and compare whether it adapts faster on changing skew.
• Study whether the method still works when the top-k result comes from approximate ranking rather than exact join output.

Learn More

• DuckDB Documentation: Read about query execution, join types, and profiling in the official DuckDB docs and source notes.
• MIT OpenCourseWare Database Systems: Search for lectures on query processing, join algorithms, and optimizer design.
• CMU Database Group course materials: Look for lecture slides and readings on physical operators, cost models, and skew handling.
• TPC-H Benchmark Specification: Find the official benchmark docs to understand query shapes and scaling behavior.
• NIH PubMed: Search for review articles on database query optimization and adaptive execution if you want background reading.