Adaptive Query Processing (AQP)

Mid-query reoptimization is a dynamic AQP technique where the execution engine pauses a running query, collects actual runtime statistics (like true cardinalities of intermediate results), and then generates a new, more efficient execution plan for the remainder of the query. This is a corrective action triggered when the observed data flow deviates significantly from the optimizer's initial estimates.

• Use Case: Correcting a severely underestimated join cardinality in a multi-hop graph traversal.
• Mechanism: A checkpoint operator is inserted into the initial plan. If the number of rows processed passes a threshold, execution halts, statistics are fed back to the optimizer, and a new plan is compiled.

Adaptive join operators dynamically switch their internal algorithm at runtime based on the true size of inputs as they become available. This eliminates the risk of a static, poor algorithm choice made during optimization.

Key operators include:

• Hash Join → Nested Loop: If one input is much smaller than predicted, the operator can switch to a more efficient nested loop join.
• Adaptive Broadcast Join: In distributed systems, the decision to broadcast a small table is made dynamically after sampling.
• Graceful Degradation: For graph queries, this can mean switching from an indexed lookup to a scan-based strategy if an index is underperforming.

The statistics feedback loop (or plan feedback) is a continuous learning system where cardinality and selectivity misestimates observed during query execution are captured and used to permanently update the database's internal statistical models. This improves future optimizations for similar queries.

• Process: Actual result counts from executed query operators are compared to pre-execution estimates. Significant discrepancies are stored in a feedback repository.
• Integration: Before optimizing a new query, the optimizer consults this repository to adjust its base table or predicate selectivity estimates, leading to better plan choices over time. This is foundational for self-tuning databases.

An Eddy is a pioneering AQP operator that continuously reorders the sequence of query operations (like filters and joins) for each individual tuple as it flows through the pipeline. It uses a routing policy to adaptively decide the next operation for a tuple based on runtime selectivity.

• Tuple Routing: Instead of a fixed plan, tuples are dynamically routed through a set of operators.
• SteMs (Steering Modules): Modern extensions of the Eddy concept that apply adaptive routing decisions at a batching level for vectorized execution engines, making the technique practical for high-throughput systems.
• Graph Application: Useful for reordering a sequence of label filters and property predicates on graph nodes during a traversal.

Progressive query processing focuses on producing usable initial results as quickly as possible and then refining them over time. It is closely related to approximate query processing (AQP) but within an adaptive context.

• Online Aggregation: Delivers a running estimate and confidence interval for aggregation queries (e.g., COUNT, AVG) as data is sampled, allowing users to stop execution once precision is sufficient.
• Sort-Merge Trade-offs: For ORDER BY ... LIMIT queries, the engine can use an adaptive sort that quickly identifies top-K candidates before fully sorting the entire result set.
• Benefit: Provides early insights for exploratory graph analytics, where a user may modify a query after seeing preliminary patterns.

Runtime filtering uses dynamically created data structures to prune irrelevant rows early in the execution pipeline. The most common structure is the Bloom filter, a probabilistic set-membership filter.

• How it Works: During a join, a Bloom filter is built on the join keys from one side (the build side). This filter is then pushed ahead to scan operators on the other side (the probe side), discarding rows that cannot possibly join before they enter the expensive join operation.
• Adaptive Aspect: The decision to create and deploy a runtime filter can be made dynamically based on the observed size of the build-side input. Filters are especially powerful in multi-join graph queries to reduce intermediate result sizes early.

Cost-Based Optimization is the foundational strategy that AQP seeks to correct at runtime. CBO uses a cost model to estimate the resource consumption (I/O, CPU, memory) of multiple potential query plans, selecting the one with the lowest estimated cost. Its effectiveness is entirely dependent on the accuracy of its cardinality estimates. AQP intervenes when these runtime estimates prove to be incorrect.

• Core Dependency: AQP relies on CBO to generate the initial execution plan it will later adapt.
• Static vs. Dynamic: CBO is a static, compile-time optimization, while AQP introduces dynamic, runtime correction.

Cardinality Estimation is the process of predicting the number of rows or graph elements (nodes, edges) that will result from a query operation (e.g., a filter or a join). It is the single most critical input to a cost model in Cost-Based Optimization. Inaccurate estimates are the primary cause of poor plan selection, which AQP is designed to mitigate.

• The Root Cause: Poor cardinality estimates lead to suboptimal join orders and access methods.
• AQP's Role: AQP monitors actual cardinalities during execution and can re-optimize the plan if estimates are off by a significant margin.

Approximate Query Processing (often sharing the AQP acronym) is a distinct but related paradigm. It focuses on returning statistically sound, approximate answers to analytical queries over massive datasets in exchange for drastically reduced latency. It uses samples, sketches, and synopses instead of scanning full datasets.

• Different Goal: While Adaptive QP seeks the correct answer via a better plan, Approximate QP trades exact precision for speed.
• Common Techniques: Both may use runtime sampling, but for different purposes: one for re-optimization, the other for final answer generation.

A Materialized View is a precomputed result set of a query, stored as a physical table or graph. It is a static optimization technique that accelerates queries by answering them from the precomputed cache, avoiding expensive joins and aggregations at runtime. AQP can be seen as a dynamic complement.

• Static Pre-computation: Materialized views are optimized during design or refresh cycles.
• AQP Synergy: An adaptive optimizer might dynamically decide to use a materialized view if runtime statistics show it is beneficial, even if the initial plan did not select it.

Vectorized Execution is a low-level query processing paradigm that improves performance by operating on batches of data (vectors) instead of row-by-row (the tuple-at-a-time model). It maximizes CPU cache utilization and leverages SIMD (Single Instruction, Multiple Data) instructions. This is an execution mechanism, while AQP is a planning strategy.

• Execution Engine: Vectorization is how the CPU processes the data once a plan (static or adapted) is chosen.
• Performance Foundation: The efficiency gains from vectorized execution provide more headroom for AQP's runtime planning overhead.

An Explain Plan is the human-readable output of a query optimizer, detailing the sequence of operations (scans, joins, filters) it intends to perform. It is the static blueprint of the query's execution. AQP makes this plan mutable during execution.

• Before vs. During: An Explain Plan shows the intent before execution. AQP monitors the execution against this plan and may change it.
• Debugging Tool: Explain plans are essential for diagnosing the poor plan choices that AQP systems are built to automatically correct.