Efficient Query Rewrite Rule Discovery via Standardized Enumeration and Learning-to-Rank(extend)

This paper presents SLER, a scalable system that combines standardized template enumeration with a learning-to-rank model to overcome the exponential search space and redundancy challenges of existing methods, successfully discovering over one million high-quality query rewrite rules for complex query plans.

The Gist

Imagine you are a chef running a very busy restaurant. Your goal is to serve delicious meals (queries) to customers as fast as possible. However, the recipes (SQL queries) your sous-chefs write are often messy, redundant, and inefficient. They might chop the same onion three times, boil water twice, or use a giant pot to cook a single egg.

In the world of databases, this is called Query Rewriting. The database needs a smart "Head Chef" (an optimizer) to look at these messy recipes and rewrite them into something faster and cleaner before cooking them.

For a long time, this Head Chef relied on a Rule Book. But the old Rule Books were tiny. They only had rules for simple dishes (like a salad with 4 ingredients). If a customer ordered a complex banquet (a query with 5, 6, or 10+ steps), the Head Chef had no idea what to do.

Enter SLER (the new system proposed in this paper). Think of SLER as a revolutionary new kitchen management system that uses three main tricks to build a massive, super-smart Rule Book.

1. The Problem: The "Brute Force" Kitchen Disaster

The previous best system (called WeTune) tried to find new rules by checking every single possible combination of ingredients.

• The Analogy: Imagine trying to find the best way to arrange a 5-ingredient salad by testing every single permutation. For a 4-ingredient salad, it takes a few days. For a 5-ingredient salad, it would take six months. For a 6-ingredient salad, it would take ten years.
• The Result: The old system gave up on anything complex. It also found thousands of "rules" that were useless (like "don't boil water if you're just making tea"), clogging up the kitchen.

2. The Solution: SLER's Three Magic Tricks

SLER fixes this with a three-step process: Standardization, Deduplication, and Ranking.

Trick #1: Standardized Templates (The "Uniform" Uniform)

Instead of looking at every messy recipe, SLER first forces every recipe into a standard uniform.

• The Analogy: Imagine if every chef had to wear a specific uniform and arrange their ingredients in a specific order before the Head Chef even looked at them.
• How it helps: If two recipes look different but are actually the same dish (just with the salt and pepper swapped), SLER realizes they are identical immediately. It throws away the duplicates before doing the hard math. This turns a task that would take exponential time (forever) into polynomial time (a manageable amount of time).

Trick #2: The "RTP" Deduplicator (The Trash Can)

Even with uniforms, you might still generate some trash. SLER uses a special algorithm called RTP (Reduce by Template Pair).

• The Analogy: As the chefs write down new rules, a smart robot (the RTP) stands next to them. If a chef writes, "If you have a red apple, cut it," and the robot already has a rule "If you have a fruit, cut it," the robot says, "Stop! That's redundant. We already have the bigger rule."
• The Result: It stops the system from wasting time checking rules that are already known to be useless. It prunes the garden so only the healthy plants grow.

Trick #3: Learning-to-Rank (The "Smart Sous-Chef")

This is the most exciting part. SLER doesn't just guess; it learns.

• The Analogy: Imagine a senior Sous-Chef who has tasted thousands of dishes. Before the Head Chef tries to verify a new, complex rule, the Sous-Chef takes a quick look and says, "I bet this rule will make the soup 20% faster. Let's test it first." Or, "This rule looks like nonsense; skip it."
• How it works: SLER uses a machine learning model (LambdaMART) trained on over 11,000 real-world queries. It learns to predict which rules are "stars" and which are "duds."
• The Benefit: Instead of checking 1 million rules blindly, SLER checks the top 100 most promising ones first. This allows it to tackle massive, complex queries (with 7, 8, or even 10+ steps) that the old system couldn't even touch.

3. The Results: A Massive Library of Super-Rules

By using these tricks, SLER achieved something incredible:

• Scale: It built a library of over 1 million rules. The old system only had rules for tiny queries. SLER has rules for the "banquet" level queries.
• Speed: It found these rules in a fraction of the time. Where the old system would take years to find rules for 6-step queries, SLER did it in months (and can do 7+ steps by using the "Smart Sous-Chef" to filter them).
• Quality: It found rules that actually make databases run faster. In tests, SLER could simplify complex queries that the old system couldn't touch at all, turning a 10-second wait into a 1-second wait.

Summary

Think of SLER as a database optimizer that stopped trying to read every book in the library to find a good story. Instead, it:

1. Organized the books into neat, standard shelves (Standardization).
2. Threw away the duplicate copies immediately (Deduplication).
3. Hired a librarian who knows exactly which books are bestsellers and only recommends those first (Learning-to-Rank).

The result? A database that is faster, smarter, and capable of handling the most complex data requests we throw at it today.

Technical Summary

Here is a detailed technical summary of the paper "Efficient Query Rewrite Rule Discovery via Standardized Enumeration and Learning-to-Rank (SLER)".

1. Problem Statement

Query rewriting is a critical technique for optimizing database performance, yet current automated methods face severe limitations in efficiency and effectiveness:

• Exponential Search Space: Existing state-of-the-art (SOTA) systems like WeTune rely on brute-force enumeration of query plan templates. This results in prohibitive computational complexity. For example, enumerating rules for 4-node plans takes ~9 days, while 5-node plans would take ~6 months, and 6-node plans could take a decade.
• Severe Redundancy: Brute-force methods generate massive amounts of redundant rules (over 90% in WeTune) and trivial rules that offer minimal optimization value.
• Scalability Barrier: Real-world queries often involve 5 to 10+ operators (nodes). Existing tools are limited to 4-node patterns, failing to optimize complex, nested queries common in production environments (e.g., ORM-generated SQL).
• Verification Bottleneck: Validating rule equivalence using SMT solvers (e.g., Z3) is computationally expensive and theoretically unreliable for large templates due to unresolved complexity issues (NP=coNP).

2. Methodology: The SLER Framework

The authors propose SLER (Scalable Learning-to-Rank for Efficient Rewrite), a system designed to discover effective rewrite rules through three core components:

A. Standardized Rule Enumeration (Efficiency)

Instead of brute-force enumeration, SLER employs standardized templates to structurally normalize query plans.

• Standardization: The system enforces a canonical structure by defining operator priorities (e.g., Project > Distinct > Filter). It generates rules that swap or remove operators to achieve this standard form.
• Redundancy Elimination: By proving that non-standardized rules are redundant if a standardized equivalent exists, SLER reduces the verification complexity from exponential to polynomial time for specific redundant cases.
• RTP Algorithm: A Reduce by Template Pair (RTP) algorithm is introduced to prune redundant rules during the enumeration phase. It checks if a new rule is redundant relative to the current rule base before full verification, significantly cutting down Z3 solver calls.

B. Learning-to-Rank (Effectiveness & Scalability)

To handle templates with 7+ nodes where full enumeration is infeasible, SLER integrates a LambdaMART (Learning-to-Rank) model.

• Feature Extraction: The model encodes query plan templates (Source and Destination) using a Tree Convolutional Neural Network (TCNN) to capture structural relationships. Features include L2 distance, cosine similarity, and expression complexity metrics (e.g., operator counts, bracket depth).
• Ranking Mechanism: The model predicts the "effectiveness score" of a rule pair. It is trained on over 11,000 real-world SQL queries (from open-source and commercial workloads) where rules are labeled based on actual execution time reduction.
• Pre-filtering: During enumeration, the ranker filters template pairs, selecting only the top-k most promising pairs for full rule generation and verification. This allows the system to scale to large-node templates (n ≥ 7) by trading off completeness for high-value discovery.

C. System Workflow

1. Enumerator: Generates candidate rules using standardized templates.
2. Ranker (Optional): Pre-filters template pairs to prioritize high-potential candidates for large-scale enumeration.
3. Deduplicator (RTP): Prunes redundant rules dynamically during generation.
4. Verifier: Validates semantic equivalence using Z3 only for non-redundant candidates.

3. Key Contributions

1. Refutation of "Small-to-Large" Hypothesis: The paper empirically demonstrates that complex rules cannot be reliably composed from simpler ones (only ~9% of 4→2 rules can be composed from 4→3 and 3→2 rules), necessitating direct enumeration of complex patterns.
2. Standardized Enumeration Algorithm: A novel approach that reduces enumeration overhead and verification complexity by enforcing canonical structures, enabling the discovery of rules for templates with up to 6 nodes and beyond.
3. Learning-to-Rank for Rule Discovery: The first application of a LambdaMART model to prioritize query rewrite rules based on intrinsic structural features and real-world performance data, enabling scalable discovery of high-node rules.
4. RTP Deduplication: An algorithm that performs redundancy elimination during enumeration rather than post-hoc, drastically reducing the candidate set size.

4. Experimental Results

The system was evaluated on 11,518 real-world SQL queries (8,518 open-source + 3,000 commercial).

• Rule Repository Scale: SLER automatically constructed a repository of >1 million rules, the largest empirically validated library to date. This is 98.25x larger than WeTune's 4-node rule set.
• Efficiency Gains:
  • Enumeration Time: SLER is significantly faster. For 4-node templates, it takes ~23 hours compared to WeTune's ~67 hours.
  • Scalability: SLER successfully enumerated 5-node rules in ~30 days and 6-node rules in ~395 days (tasks where WeTune times out). With the ranker's pre-filtering, it can explore 10-node templates in minutes.
  • Redundancy Reduction: The RTP algorithm reduced de-redundancy time for 4-node templates from 20+ days (WeTune) to under 10 minutes.
• Effectiveness:
  • Coverage: SLER discovered effective rules for complex patterns (5–10 nodes) that WeTune could not find.
  • Performance Impact: Top-ranked rules achieved an average 98.6% performance improvement, vastly outperforming random selection.
  • Query Optimization: In end-to-end tests, SLER achieved faster convergence (fewer rewrite steps) and higher optimization ratios for complex queries compared to WeTune.

5. Significance

• Breaking the 4-Node Barrier: SLER is the first system capable of systematically discovering and validating rewrite rules for complex queries involving 5 to 10+ operators, addressing a critical gap in modern database optimization.
• Practical Scalability: By combining structural standardization with machine learning, SLER makes the discovery of massive rule sets computationally feasible, moving from "brute-force" to "intelligent search."
• Future-Proofing: The framework is extensible. While currently focused on SPJ (Select-Project-Join) operators, the methodology provides a path to incorporate aggregates, window functions, and other complex operators, paving the way for next-generation, adaptive database optimizers.
• Real-World Impact: The ability to automatically discover rules for ORM-generated and deeply nested queries directly addresses the inefficiencies found in modern application development, offering immediate performance gains for production databases.