Skip to main content

uqa_engine/session/
analyze.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Column-statistics collection, persistence, and lazy refresh.
8
9mod automatic;
10#[cfg(test)]
11mod tests;
12
13use super::analyze_helpers::ColumnAnalyzeValues;
14use super::{
15    build_histogram, build_mcv, collect_analyze_values, distinct_count, Arc, BTreeMap,
16    CatalogFacade, ColumnStatsInput, Engine, Ordering, StorageBackendError, StorageBackendResult,
17    TableState, Value,
18};
19
20struct HierarchyAnalyzeInputs {
21    row_count: u64,
22    values: BTreeMap<String, ColumnAnalyzeValues>,
23    null_counts: BTreeMap<String, u64>,
24}
25
26fn build_analyze_stats(
27    columns: &[String],
28    inputs: HierarchyAnalyzeInputs,
29) -> StorageBackendResult<BTreeMap<String, uqa_planner::ColumnStats>> {
30    let HierarchyAnalyzeInputs {
31        row_count,
32        values: mut column_values,
33        null_counts: mut column_nulls,
34    } = inputs;
35    let mut stats = BTreeMap::new();
36    for column in columns {
37        let values = column_values.remove(column).ok_or_else(|| {
38            StorageBackendError::Other(format!(
39                "ANALYZE lost the value buffer for column `{column}`"
40            ))
41        })?;
42        let null_count = column_nulls.remove(column).ok_or_else(|| {
43            StorageBackendError::Other(format!(
44                "ANALYZE lost the null counter for column `{column}`"
45            ))
46        })?;
47        // Omitted wide values contribute non-null, conservatively distinct
48        // observations. They are not truncated into false equality/range keys.
49        let distinct = distinct_count(&values.retained)?
50            .checked_add(values.omitted)
51            .ok_or_else(|| StorageBackendError::Other("ANALYZE distinct count overflow".into()))?;
52        let values = values.retained;
53        let comparable = values
54            .iter()
55            .filter(|value| {
56                matches!(
57                    value,
58                    Value::Int(_) | Value::Float(_) | Value::Str(_) | Value::Bool(_)
59                )
60            })
61            .collect::<Vec<_>>();
62        let (mcv_values, mcv_frequencies) = build_mcv(&values, row_count, distinct);
63        stats.insert(
64            column.clone(),
65            uqa_planner::ColumnStats {
66                distinct_count: distinct,
67                null_count,
68                min_value: comparable.iter().min().map(|value| (*value).clone()),
69                max_value: comparable.iter().max().map(|value| (*value).clone()),
70                row_count,
71                histogram: build_histogram(&comparable),
72                mcv_values,
73                mcv_frequencies,
74            },
75        );
76    }
77    Ok(stats)
78}
79
80/// When the lazy statistics of a memory-only table are collected again after writes.
81#[derive(Clone, Copy, Debug, PartialEq, Eq)]
82pub(crate) enum StatisticsRefresh {
83    /// An explicit statistics request reports the current rows.
84    Current,
85    /// Planning keeps its estimates until enough rows changed, as autovacuum decides for `PostgreSQL`, so a write is not followed by a full ANALYZE of its table.
86    Maintained,
87}
88
89impl Engine {
90    /// Refresh per-column statistics for one table, or every table when
91    /// `table` is `None`. The analysis scans each document and collects per-
92    /// column distinct count / null count / min / max / equi-depth
93    /// histogram (100 buckets) / MCV list (top 10 above-average
94    /// frequency), and stores the result on the per-table state so the
95    /// cardinality estimator can read it on subsequent queries.
96    pub fn run_analyze(&self, table: Option<&str>) -> StorageBackendResult<()> {
97        self.analyze_targets(table, None, true, false)
98    }
99
100    pub(crate) fn run_analyze_target(
101        &self,
102        table: &str,
103        columns: &[String],
104        include_descendants: bool,
105    ) -> StorageBackendResult<()> {
106        self.analyze_targets(
107            Some(table),
108            (!columns.is_empty()).then_some(columns),
109            include_descendants,
110            true,
111        )
112    }
113
114    fn analyze_targets(
115        &self,
116        table: Option<&str>,
117        columns: Option<&[String]>,
118        include_descendants: bool,
119        check_privileges: bool,
120    ) -> StorageBackendResult<()> {
121        self.with_storage_maintenance_scope(|engine| {
122            let targets = uqa_execution::maintenance::analyze::prepare_targets(
123                &engine.analyze_execution_context(check_privileges),
124                table,
125                include_descendants,
126            )
127            .map_err(|error| StorageBackendError::backend("ANALYZE locking", error))?;
128            if targets.is_empty() {
129                return Ok(());
130            }
131            engine.prepare_storage_maintenance_writer()?;
132            uqa_execution::maintenance::analyze::run_locked_targets(&targets, |name| {
133                engine.analyze_locked_table(name, columns, include_descendants)
134            })
135        })
136    }
137
138    fn analyze_locked_table(
139        &self,
140        name: &str,
141        columns: Option<&[String]>,
142        include_descendants: bool,
143    ) -> StorageBackendResult<()> {
144        let table = self.try_table(name)?.ok_or_else(|| {
145            StorageBackendError::Other(format!("locked ANALYZE target `{name}` does not exist"))
146        })?;
147        self.analyze_table(name, &table, true, columns, include_descendants)?;
148        self.note_table_data_changed();
149        Ok(())
150    }
151
152    /// Record a change whose effect on the stored documents its caller does not know, such as a schema rewrite or a truncation.
153    pub(crate) fn mark_column_stats_dirty(
154        &self,
155        canonical_table_name: &str,
156        table: &Arc<TableState>,
157    ) -> StorageBackendResult<()> {
158        self.mark_column_stats_dirty_by_count(canonical_table_name, table, 1)
159    }
160
161    pub(crate) fn mark_column_stats_dirty_by_count(
162        &self,
163        canonical_table_name: &str,
164        table: &Arc<TableState>,
165        count: u64,
166    ) -> StorageBackendResult<()> {
167        self.record_table_change(canonical_table_name, table, count, None)
168    }
169
170    /// Record one row write, which changes the stored documents of its own table alone and by a known amount.
171    pub(crate) fn mark_row_write(
172        &self,
173        canonical_table_name: &str,
174        table: &Arc<TableState>,
175        documents: crate::table_storage::DocumentCountChange,
176    ) -> StorageBackendResult<()> {
177        self.record_table_change(canonical_table_name, table, 1, Some(documents))
178    }
179
180    fn record_table_change(
181        &self,
182        canonical_table_name: &str,
183        table: &Arc<TableState>,
184        count: u64,
185        documents: Option<crate::table_storage::DocumentCountChange>,
186    ) -> StorageBackendResult<()> {
187        let ancestors = self
188            .hierarchy_ancestor_tables(canonical_table_name)
189            .map_err(|error| StorageBackendError::Other(error.to_string()))?;
190        for name in ancestors {
191            let written = name == canonical_table_name;
192            let state = if written {
193                Arc::clone(table)
194            } else {
195                self.try_table(&name)?.ok_or_else(|| {
196                    StorageBackendError::Other(format!(
197                        "statistics ancestor table `{name}` does not exist"
198                    ))
199                })?
200            };
201            // Estimates remain useful while a replacement is pending. Track
202            // changes transactionally instead of deleting durable statistics.
203            self.record_statistics_change(&name, &state, count)?;
204            match documents {
205                Some(change) if written => state.apply_document_count_change(change),
206                // An ancestor stores its own documents, which a row write below it leaves alone.
207                Some(_) => {}
208                None => state.discard_document_count(),
209            }
210            state.column_stats_dirty.store(true, Ordering::Release);
211        }
212        self.note_table_data_changed();
213        Ok(())
214    }
215
216    fn analyze_table(
217        &self,
218        canonical_table_name: &str,
219        t: &Arc<TableState>,
220        persist: bool,
221        requested_columns: Option<&[String]>,
222        include_descendants: bool,
223    ) -> StorageBackendResult<()> {
224        let available_columns: Vec<String> = t
225            .columns
226            .read()
227            .iter()
228            .filter(|column| {
229                !column.generated.as_ref().is_some_and(|generated| {
230                    generated.kind == uqa_sql::ast::GeneratedColumnKind::Virtual
231                })
232            })
233            .map(|column| column.name.clone())
234            .collect();
235        let columns =
236            requested_columns.map_or_else(|| available_columns.clone(), <[String]>::to_vec);
237        if let Some(column) = columns
238            .iter()
239            .find(|column| !available_columns.contains(column))
240        {
241            return Err(StorageBackendError::Other(format!(
242                "column `{column}` of relation `{canonical_table_name}` does not exist"
243            )));
244        }
245        let sampled_generations =
246            if persist && t.persistence != uqa_sql::ast::RelationPersistence::Temporary {
247                self.sampled_data_generations(canonical_table_name, include_descendants)?
248            } else {
249                None
250            };
251        // Read before the sample, which reads at this sequence or a later one.
252        let sampled_at = self.statistics_sample_sequence();
253        let (stats_out, row_count) = self.collect_hierarchy_analyze_statistics(
254            canonical_table_name,
255            &columns,
256            include_descendants,
257        )?;
258
259        let stats_out = if requested_columns.is_some() {
260            let mut combined = t.column_stats.read().clone();
261            combined.extend(stats_out);
262            combined
263        } else {
264            stats_out
265        };
266        if persist && t.persistence != uqa_sql::ast::RelationPersistence::Temporary {
267            if let Some(catalog) = self.storage.catalog.as_ref() {
268                Self::persist_column_stats(
269                    catalog.as_ref(),
270                    canonical_table_name,
271                    &stats_out,
272                    t.object_id(),
273                    row_count,
274                    sampled_at,
275                )?;
276            }
277        }
278        *t.column_stats.write() = stats_out;
279        t.column_stats_loaded.store(true, Ordering::Release);
280        t.column_stats_dirty.store(false, Ordering::Release);
281        t.statistics_maintenance.lock().analyzed(
282            t.object_id(),
283            row_count,
284            crate::statistics::value_size::FORMAT_VERSION,
285            None,
286        )?;
287        self.clear_pending_statistics_changes(canonical_table_name, t.object_id());
288        self.retain_statistics_sample(canonical_table_name, t.object_id(), sampled_generations);
289        Ok(())
290    }
291
292    fn collect_hierarchy_analyze_statistics(
293        &self,
294        canonical_table_name: &str,
295        columns: &[String],
296        include_descendants: bool,
297    ) -> StorageBackendResult<(crate::ColumnStatsMap, u64)> {
298        let members = self
299            .hierarchy_scan_tables(canonical_table_name, include_descendants)
300            .map_err(|error| StorageBackendError::Other(error.to_string()))?;
301        let snapshots = members.iter().map(|member_name| {
302            let member = self.try_table(member_name)?.ok_or_else(|| {
303                StorageBackendError::Other(format!(
304                    "ANALYZE hierarchy member `{member_name}` does not exist"
305                ))
306            })?;
307            let snapshot = member.document_store.read().snapshot()?;
308            Ok(snapshot)
309        });
310        let workspace = self
311            .work_mem_bytes()
312            .map_err(|error| StorageBackendError::backend("ANALYZE workspace", error))?;
313        let inputs = uqa_execution::maintenance::analyze::values::collect_values(
314            snapshots,
315            columns,
316            workspace,
317            &self.runtime.cancellation,
318            crate::statistics::value_size::accepts,
319        )
320        .map_err(|error| StorageBackendError::backend("ANALYZE value collection", error))?;
321        let counts = inputs
322            .counts
323            .iter()
324            .map(
325                |count| uqa_planner::cardinality::analyze::ColumnObservationCounts {
326                    nulls: count.nulls,
327                    omitted: count.omitted,
328                    comparable: count.comparable,
329                },
330            )
331            .collect::<Vec<_>>();
332        let stats = uqa_planner::cardinality::analyze::collect_statistics(
333            inputs.row_count,
334            &counts,
335            inputs.values,
336            crate::statistics::value_size::HISTOGRAM_VALUES,
337            crate::statistics::value_size::MCV_VALUES,
338        )
339        .map_err(|error| StorageBackendError::backend("ANALYZE distributions", error))?;
340        Ok((
341            columns.iter().cloned().zip(stats).collect(),
342            inputs.row_count,
343        ))
344    }
345
346    /// `sampled_at` is the commit sequence the statistics were sampled at, or `None` when it is not known.
347    pub(crate) fn persist_column_stats(
348        catalog: &dyn CatalogFacade,
349        table_name: &str,
350        stats: &BTreeMap<String, uqa_planner::ColumnStats>,
351        object_id: [u8; 16],
352        row_count: u64,
353        sampled_at: Option<u64>,
354    ) -> StorageBackendResult<()> {
355        Self::persist_column_stats_rows(catalog, table_name, stats)?;
356        crate::statistics::MaintenanceState::analyzed_for(
357            catalog,
358            table_name,
359            object_id,
360            row_count,
361            crate::statistics::value_size::FORMAT_VERSION,
362            sampled_at,
363        )
364    }
365
366    fn persist_column_stats_rows(
367        catalog: &dyn CatalogFacade,
368        table_name: &str,
369        stats: &BTreeMap<String, uqa_planner::ColumnStats>,
370    ) -> StorageBackendResult<()> {
371        struct EncodedColumnStats {
372            column_name: String,
373            distinct_count: i64,
374            null_count: i64,
375            min_json: Option<String>,
376            max_json: Option<String>,
377            row_count: i64,
378            histogram_json: String,
379            mcv_values_json: String,
380            mcv_frequencies_json: String,
381        }
382
383        let mut encoded = Vec::with_capacity(stats.len());
384        for (col_name, cs) in stats {
385            let min_json = cs
386                .min_value
387                .as_ref()
388                .map(serde_json::to_string)
389                .transpose()?;
390            let max_json = cs
391                .max_value
392                .as_ref()
393                .map(serde_json::to_string)
394                .transpose()?;
395            let histogram_json = serde_json::to_string(&cs.histogram)?;
396            let mcv_values_json = serde_json::to_string(&cs.mcv_values)?;
397            let mcv_frequencies_json = serde_json::to_string(&cs.mcv_frequencies)?;
398            encoded.push(EncodedColumnStats {
399                column_name: col_name.clone(),
400                distinct_count: Self::u64_to_i64("distinct count", cs.distinct_count)?,
401                null_count: Self::u64_to_i64("null count", cs.null_count)?,
402                min_json,
403                max_json,
404                row_count: Self::u64_to_i64("row count", cs.row_count)?,
405                histogram_json,
406                mcv_values_json,
407                mcv_frequencies_json,
408            });
409        }
410        let rows = encoded
411            .iter()
412            .map(|stats| ColumnStatsInput {
413                table_name,
414                column_name: &stats.column_name,
415                distinct_count: stats.distinct_count,
416                null_count: stats.null_count,
417                min_value: stats.min_json.as_deref(),
418                max_value: stats.max_json.as_deref(),
419                row_count: stats.row_count,
420                histogram_json: &stats.histogram_json,
421                mcv_values_json: &stats.mcv_values_json,
422                mcv_frequencies_json: &stats.mcv_frequencies_json,
423            })
424            .collect::<Vec<_>>();
425        catalog.replace_column_stats(table_name, &rows)
426    }
427
428    pub(super) fn u64_to_i64(kind: &str, value: u64) -> StorageBackendResult<i64> {
429        i64::try_from(value).map_err(|_| {
430            StorageBackendError::Other(format!(
431                "ANALYZE {kind} {value} exceeds the persistent i64 range"
432            ))
433        })
434    }
435
436    /// Snapshot of the cardinality estimator's per-column statistics
437    /// for `table`. Clean statistics are reused, including sampled scalar
438    /// statistics from automatic maintenance. Dirty stats are recomputed
439    /// through the same durable transaction boundary as `ANALYZE`. Use
440    /// `run_analyze` to force full collection regardless of cached statistics.
441    /// Persistent query planning only consumes already-collected statistics.
442    pub fn column_stats(
443        &self,
444        table: &str,
445    ) -> StorageBackendResult<BTreeMap<String, uqa_planner::ColumnStats>> {
446        self.try_column_stats(table)
447    }
448
449    pub fn try_column_stats(
450        &self,
451        table: &str,
452    ) -> StorageBackendResult<BTreeMap<String, uqa_planner::ColumnStats>> {
453        self.with_direct_query_snapshot(
454            false,
455            |engine| engine.column_stats_in_execution(table, StatisticsRefresh::Current),
456            |error| StorageBackendError::backend("column statistics query", error),
457        )
458    }
459
460    pub(crate) fn column_stats_in_execution(
461        &self,
462        table: &str,
463        refresh: StatisticsRefresh,
464    ) -> StorageBackendResult<BTreeMap<String, uqa_planner::ColumnStats>> {
465        self.synchronize_table_data()?;
466        let canonical_name = self
467            .try_resolve_table_name(table)?
468            .ok_or_else(|| StorageBackendError::Other(format!("table `{table}` does not exist")))?;
469        let t = self
470            .try_table(&canonical_name)?
471            .ok_or_else(|| StorageBackendError::Other(format!("table `{table}` does not exist")))?;
472        if t.column_stats_dirty.load(Ordering::Acquire) {
473            if self.storage.catalog.is_none() {
474                // Memory-only lazy collection has no durable publication and
475                // must not invalidate the statement currently being planned.
476                let due = match refresh {
477                    StatisticsRefresh::Current => true,
478                    StatisticsRefresh::Maintained => {
479                        let maintenance = t.statistics_maintenance.lock();
480                        maintenance.due(
481                            maintenance.missing(t.column_stats.read().is_empty()),
482                            crate::statistics::now_ms(),
483                            crate::statistics::value_size::FORMAT_VERSION,
484                        )
485                    }
486                };
487                if due {
488                    self.analyze_table(&canonical_name, &t, false, None, true)?;
489                }
490                return Ok(t.column_stats.read().clone());
491            }
492            self.run_analyze(Some(&canonical_name))?;
493            // Starting maintenance can refresh session-local table bindings.
494            let refreshed = self.try_table(&canonical_name)?.ok_or_else(|| {
495                StorageBackendError::Other(format!("table `{canonical_name}` does not exist"))
496            })?;
497            return Ok(refreshed.column_stats.read().clone());
498        }
499        let stats = t.column_stats.read().clone();
500        Ok(stats)
501    }
502
503    pub(crate) fn try_query_column_stats(
504        &self,
505        table: &str,
506    ) -> StorageBackendResult<BTreeMap<String, uqa_planner::ColumnStats>> {
507        // Memory-only engines have no durable independent sessions or blob
508        // I/O. Retain their automatic lazy refresh at this boundary.
509        if self.storage.provider.is_none() && self.query_table_snapshots.is_none() {
510            return self.column_stats_in_execution(table, StatisticsRefresh::Maintained);
511        }
512        let table = self
513            .try_query_table(table)?
514            .ok_or_else(|| StorageBackendError::Other(format!("table `{table}` does not exist")))?;
515        // Cardinality estimates must never turn a projection or EXPLAIN into
516        // a synchronous full-table ANALYZE (including unrelated BLOB fields).
517        // Keep using the last collected estimate while the database worker
518        // refreshes it. A genuinely new table uses ordinary planner estimates.
519        let stats = table.column_stats.read().clone();
520        Ok(stats)
521    }
522}