Time Constraints

Here's a paradox at the heart of query optimization: the more time you spend optimizing, the less time you have for executing—but the better your plan, the faster execution will be.

For a query that will run for hours, spending 30 seconds finding an optimal plan is an excellent investment. But for a query that should complete in 10 milliseconds, spending 30 seconds optimizing is absurd—you've delayed the result by 3000×.

The optimizer must navigate this trade-off dynamically, adapting its effort to the expected query complexity. Too little optimization → poor plan quality. Too much optimization → wasted time. Getting this balance right is a crucial but often overlooked aspect of query processing.

Optimization time and plan quality are fundamentally linked. More time allows more thorough search, better cost estimation, and consideration of more alternatives. But optimization has diminishing returns:

1.1 The Law of Diminishing Returns

• First 10ms of optimization: Prune obviously bad plans (Cartesian products, missing predicates)
• Next 100ms: Find the optimal join order via DP for moderate queries
• Next 1s: Consider additional access paths, parallel alternatives
• Beyond 1s: Marginal improvements, exploring rare edge cases

For most practical queries, 95% of the benefit comes from the first 100ms of optimization. Spending more time produces incrementally smaller improvements.

1.2 Characterizing Total Query Cost

Total response time = Optimization time + Execution time

$$T_{total} = T_{opt} + T_{exec}(plan)$$

Where T_exec depends on the plan chosen. The optimizer seeks to minimize T_total, not just T_exec.

Optimal Optimization Time: In principle, we want to optimize until: $$\frac{dT_{exec}}{dT_{opt}} = -1$$

That is, until each additional optimization second saves less than one execution second. In practice, this is impossible to measure in advance.

Optimizers use various mechanisms to prevent optimization from taking too long:

2.1 Static Thresholds

The simplest approach: switch strategies based on query characteristics.

if (num_tables <= 5):
    use full_dp_optimization()
elif (num_tables <= 12):
    use left_deep_dp_optimization()
else:
    use genetic_optimization()  # or heuristic

PostgreSQL Example:

• geqo_threshold = 12: Switch to genetic optimizer above 12 tables
• from_collapse_limit = 8: Stop collapsing subqueries above 8 tables

2.2 Time Budgets

Allocate a maximum optimization time:

budget = estimate_execution_time(query) * 0.01  # 1% of expected
start_time = now()

while (has_more_plans() and elapsed() < budget):
    evaluate_next_plan()

return best_plan_so_far()

Challenge: Estimating expected execution time before optimization completes—a chicken-and-egg problem. Systems often use query complexity heuristics (number of tables, presence of aggregations) instead.

2.3 Plan Count Limits

Limit the number of plans evaluated:

max_plans = 10000
plans_evaluated = 0

while (has_more_plans() and plans_evaluated < max_plans):
    evaluate_next_plan()
    plans_evaluated++

Advantage: Predictable bound on optimization time. Disadvantage: Doesn't adapt to plan evaluation speed or query importance.

2.4 Pruning Escalation

Start with light pruning, escalate if optimization is taking too long:

pruning_level = 1  # 1=light, 2=medium, 3=aggressive

while (has_more_plans()):
    if (elapsed() > phase_budget[pruning_level]):
        pruning_level++
        apply_stricter_pruning(pruning_level)
        if (pruning_level > 3):
            break
    evaluate_next_plan()

This adaptively increases aggressiveness as time pressure mounts.

2.5 Timeout with Best-Effort

Hard timeout after maximum allowed time:

timeout = 30 seconds  # Configurable

try:
    with_timeout(timeout):
        plan = full_optimization(query)
except TimeoutError:
    plan = best_plan_so_far or heuristic_plan(query)

return plan

This guarantees bounded optimization time but may return suboptimal plans.

Rather than a single optimization pass, many systems use multi-phase approaches that progressively improve plan quality:

3.1 Quick Phase → Thorough Phase

Phase 1: Quick Optimization (Low Cost)

• Apply heuristic transformations (push selections, eliminate redundant operations)
• Use simplified cost model
• Consider only common access paths
• Find a "good enough" plan quickly

Phase 2: Thorough Optimization (If Time Permits)

• Full DP enumeration
• Detailed cost model with accurate statistics
• Consider all access paths and algorithms
• Refine or replace Phase 1 plan

Decision Point: Proceed to Phase 2 only if:

• Phase 1 plan has high estimated cost (optimization is worth it)
• Time budget allows
• Query is not trivial (e.g., single table, simple filter)

3.2 The SQL Server Approach

SQL Server uses three optimization phases:

Each phase has increasing sophistication and cost. The optimizer escalates only when the previous phase's best plan exceeds a cost threshold.

The most sophisticated systems adapt their optimization approach based on query characteristics and system state:

4.1 Query Complexity Metrics

Systems compute complexity scores to guide optimization effort:

• Join count: More joins = more complex
• Predicate complexity: OR conditions, functions, subqueries
• Aggregation presence: GROUP BY, DISTINCT, window functions
• Data volume: Estimated rows touched
• Index availability: More indexes = more options = more search

$$complexity = \alpha \cdot joins + \beta \cdot predicates + \gamma \cdot aggregates + ...$$

Optimization time budget scales with complexity score.

4.2 System Load Adaptation

When the system is under heavy load, optimize less aggressively:

load_factor = current_cpu_usage / max_cpu_capacity

if load_factor > 0.8:
    optimization_budget *= 0.5  # Cut optimization time in half
    use_cached_plans_more_aggressively()

Rationale: During high load, faster optimization (even with worse plans) reduces queueing delays and helps overall throughput.

4.3 Query Priority / Importance

Allocate more optimization resources to important queries:

Priority Indicators:

• User-specified hints (HIGH_PRIORITY, OPTIMIZE_FOR_AD_HOC)
• Query frequency (optimize more for frequently repeated queries)
• Resource governor classifications
• Service tier (premium users get more optimization)

4.4 Feedback-Driven Adaptation

Learn from past queries to adjust optimization:

Successful Patterns:

• Queries that completed quickly after optimization
• Plans that matched cardinality estimates

Failed Patterns:

• Queries where actual time >> estimated time
• Plans with large cardinality estimation errors

Adaptive systems might:

• Spend more time on query patterns that previously had poor plans
• Reuse plans that worked well on similar queries
• Flag queries that frequently have estimation problems

4.5 Incremental Improvement

For repeated queries or prepared statements:

if (same_query_executed_before):
    previous_plan = get_cached_plan(query)
    previous_actual_cost = get_actual_cost(previous_plan)
    
    if (previous_actual_cost was_acceptable):
        return previous_plan  # Don't re-optimize
    else:
        re_optimize with (higher_budget, updated_statistics)

This amortizes optimization cost over multiple executions while adapting to change.

The best way to reduce optimization time is to avoid optimization altogether by reusing previously computed plans:

5.1 Plan Cache Architecture

Query String → Hash → Cache Lookup
                        ↓
              Hit: Return cached plan
                        ↓ (Miss)
              Optimize → Store in cache → Return plan

Cache Key Components:

• Query text (normalized: whitespace, case)
• Parameter values (for some systems) or parameter types
• Session settings (ANSI nulls, date format, etc.)
• Schema version (invalidate on DDL changes)

5.2 Prepared Statements

Prepared statements explicitly separate parsing/optimization from execution:

-- Prepare once (optimization happens here)
PREPARE order_lookup AS 
    SELECT * FROM orders WHERE customer_id = $1;

-- Execute many times (no re-optimization)
EXECUTE order_lookup(12345);
EXECUTE order_lookup(67890);
EXECUTE order_lookup(11111);

Benefits:

• Optimization cost amortized over many executions
• Reduced SQL injection risk
• Reduced parsing overhead
• Stable plans across executions

5.3 Cache Invalidation

Cached plans must be invalidated when they become stale:

Invalidation Triggers:

• Schema changes (DDL on involved tables)
• Statistics updates (ANALYZE)
• Index creation/deletion
• Configuration changes affecting optimization
• Explicit cache flush commands

Lazy Recompilation: Some systems recompile lazily:

• Mark plan as "needs recompile"
• Recompile on next execution (not immediately)
• Avoids thundering herd of simultaneous recompilations

5.4 Cache Management

Memory Pressure:

• Plans consume memory from a shared cache
• Eviction policies (LRU, cost-weighted) manage cache size
• Rarely-used plans evicted first

Plan Cache Bloat:

• Auto-parameterization helps: WHERE id = 5 → WHERE id = @p1
• Non-parameterized literals create unique cache entries
• Ad-hoc workloads can flood the cache with single-use plans

-- SQL Server: Check plan cache efficiency
SELECT 
    objtype,
    COUNT(*) as plan_count,
    SUM(size_in_bytes) / 1024 / 1024 as size_mb
FROM sys.dm_exec_cached_plans
GROUP BY objtype;

When optimization exceeds time limits, the system must have fallback strategies:

6.1 Graceful Degradation

Attempt full optimization
    ↓ (timeout)
Use best plan found so far
    ↓ (no complete plan)
Fall back to heuristic plan
    ↓ (heuristics fail)
Fall back to left-to-right join order
    ↓ (catastrophic failure)
Report error and abort

Each fallback level produces a valid (if potentially suboptimal) plan.

6.2 Partial Results Usage

Modern optimizers track partial results during enumeration:

• Best complete plan so far: Even if search is incomplete
• Best partial plans per subset: Can be assembled into complete plan
• Cost bounds discovered: Enable early termination with confidence

6.3 Parallel Optimization

Some systems parallelize optimization itself:

• Multiple threads explore different regions of search space
• First thread to find a "good enough" plan terminates others
• Especially useful for very large queries

6.4 User-Facing Implications

Timeout During Optimization:

• Query may still execute (with suboptimal plan)
• User sees slower-than-expected performance, not error
• May return results but log a warning

Complete Optimization Failure:

• Return error to user
• Suggest query simplification
• Recommend explicit hints or query decomposition

Understanding time constraints has practical implications for application development:

7.1 Query Design for Optimal Optimization

Keep Joins Manageable:

• Try to keep queries under 10-12 table joins
• Break complex queries into CTEs or subqueries (may parallelize optimization)
• Use views or materialized views for common join patterns

Simplify Predicates:

• Avoid overly complex WHERE clauses
• Minimize OR conditions that multiply search space
• Use helper columns instead of expression-heavy predicates

Use Explicit Hints When Needed:

-- When you know optimizer time is wasted
SELECT /*+ NO_REORDER */ * FROM ...

-- When you know the optimal join
SELECT /*+ LEADING(a b) */ * FROM a JOIN b ON ...

7.2 Prepared Statements Strategy

Use Prepared Statements For:

• Frequently executed queries (OLTP patterns)
• Queries with varying parameters but stable structure
• Security-sensitive queries (SQL injection prevention)

Consider Ad-hoc For:

• One-time analytical queries
• Queries with extreme parameter variability requiring different plans
• Exploratory queries during development

7.3 Monitoring Optimization Performance

Key Metrics to Track:

• Compilation/optimization time per query
• Cache hit ratio for plan cache
• Number of plans in cache
• Frequency of optimization timeout/fallback

-- PostgreSQL: Check planning time
EXPLAIN (ANALYZE, COSTS) SELECT ...;
-- Look for "Planning Time: X ms"

-- SQL Server: Check compilation time
SET STATISTICS TIME ON;
-- Look for "SQL Server parse and compile time"

7.4 Configuration Tuning

For Complex OLAP Workloads:

• Increase optimization time budgets
• Raise table join thresholds
• Consider query hints for repeatably complex queries

For High-Volume OLTP:

• Aggressive plan caching
• Lower optimization thresholds
• Focus on prepared statement reuse