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, DocId, Engine, Ordering, StorageBackendError,
17    StorageBackendResult, 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        // Read before the sample, which reads at this sequence or a later one.
246        let sampled_at = self.statistics_sample_sequence();
247        let inputs = self.collect_hierarchy_analyze_inputs(
248            canonical_table_name,
249            &columns,
250            include_descendants,
251        )?;
252        let row_count = inputs.row_count;
253        let stats_out = build_analyze_stats(&columns, inputs)?;
254
255        let stats_out = if requested_columns.is_some() {
256            let mut combined = t.column_stats.read().clone();
257            combined.extend(stats_out);
258            combined
259        } else {
260            stats_out
261        };
262        if persist && t.persistence != uqa_sql::ast::RelationPersistence::Temporary {
263            if let Some(catalog) = self.storage.catalog.as_ref() {
264                Self::persist_column_stats(
265                    catalog.as_ref(),
266                    canonical_table_name,
267                    &stats_out,
268                    t.object_id(),
269                    row_count,
270                    sampled_at,
271                )?;
272            }
273        }
274        *t.column_stats.write() = stats_out;
275        t.column_stats_loaded.store(true, Ordering::Release);
276        t.column_stats_dirty.store(false, Ordering::Release);
277        t.statistics_maintenance.lock().analyzed(
278            t.object_id(),
279            row_count,
280            crate::statistics::value_size::FORMAT_VERSION,
281            None,
282        )?;
283        self.clear_pending_statistics_changes(canonical_table_name, t.object_id());
284        Ok(())
285    }
286
287    fn collect_hierarchy_analyze_inputs(
288        &self,
289        canonical_table_name: &str,
290        columns: &[String],
291        include_descendants: bool,
292    ) -> StorageBackendResult<HierarchyAnalyzeInputs> {
293        let mut col_values = columns
294            .iter()
295            .map(|column| (column.clone(), ColumnAnalyzeValues::default()))
296            .collect::<BTreeMap<_, _>>();
297        let mut col_nulls = columns
298            .iter()
299            .map(|column| (column.clone(), 0_u64))
300            .collect::<BTreeMap<_, _>>();
301        let members = self
302            .hierarchy_scan_tables(canonical_table_name, include_descendants)
303            .map_err(|error| StorageBackendError::Other(error.to_string()))?;
304        let mut n = 0_u64;
305        for member_name in members {
306            let member = self.try_table(&member_name)?.ok_or_else(|| {
307                StorageBackendError::Other(format!(
308                    "ANALYZE hierarchy member `{member_name}` does not exist"
309                ))
310            })?;
311            let snapshot = member.document_store.read().snapshot()?;
312            let mut doc_ids: Vec<DocId> = snapshot.doc_ids()?;
313            doc_ids.sort_unstable();
314            n = n
315                .checked_add(u64::try_from(doc_ids.len()).map_err(|_| {
316                    StorageBackendError::Other("ANALYZE document count exceeds u64".into())
317                })?)
318                .ok_or_else(|| {
319                    StorageBackendError::Other("ANALYZE hierarchy row count overflow".into())
320                })?;
321            let (mut member_values, member_nulls) =
322                collect_analyze_values(snapshot.as_ref(), &doc_ids, columns)?;
323            for column in columns {
324                col_values
325                    .get_mut(column)
326                    .ok_or_else(|| {
327                        StorageBackendError::Other(format!(
328                            "ANALYZE lost the value buffer for column `{column}`"
329                        ))
330                    })?
331                    .extend(member_values.remove(column).unwrap_or_default());
332                let null_count = member_nulls.get(column).copied().ok_or_else(|| {
333                    StorageBackendError::Other(format!(
334                        "ANALYZE lost the null counter for column `{column}`"
335                    ))
336                })?;
337                let total = col_nulls.get_mut(column).ok_or_else(|| {
338                    StorageBackendError::Other(format!(
339                        "ANALYZE lost the null counter for column `{column}`"
340                    ))
341                })?;
342                *total = total.checked_add(null_count).ok_or_else(|| {
343                    StorageBackendError::Other("ANALYZE null count overflow".into())
344                })?;
345            }
346        }
347        Ok(HierarchyAnalyzeInputs {
348            row_count: n,
349            values: col_values,
350            null_counts: col_nulls,
351        })
352    }
353
354    /// `sampled_at` is the commit sequence the statistics were sampled at, or `None` when it is not known.
355    pub(crate) fn persist_column_stats(
356        catalog: &dyn CatalogFacade,
357        table_name: &str,
358        stats: &BTreeMap<String, uqa_planner::ColumnStats>,
359        object_id: [u8; 16],
360        row_count: u64,
361        sampled_at: Option<u64>,
362    ) -> StorageBackendResult<()> {
363        Self::persist_column_stats_rows(catalog, table_name, stats)?;
364        crate::statistics::MaintenanceState::analyzed_for(
365            catalog,
366            table_name,
367            object_id,
368            row_count,
369            crate::statistics::value_size::FORMAT_VERSION,
370            sampled_at,
371        )
372    }
373
374    fn persist_column_stats_rows(
375        catalog: &dyn CatalogFacade,
376        table_name: &str,
377        stats: &BTreeMap<String, uqa_planner::ColumnStats>,
378    ) -> StorageBackendResult<()> {
379        struct EncodedColumnStats {
380            column_name: String,
381            distinct_count: i64,
382            null_count: i64,
383            min_json: Option<String>,
384            max_json: Option<String>,
385            row_count: i64,
386            histogram_json: String,
387            mcv_values_json: String,
388            mcv_frequencies_json: String,
389        }
390
391        let mut encoded = Vec::with_capacity(stats.len());
392        for (col_name, cs) in stats {
393            let min_json = cs
394                .min_value
395                .as_ref()
396                .map(serde_json::to_string)
397                .transpose()?;
398            let max_json = cs
399                .max_value
400                .as_ref()
401                .map(serde_json::to_string)
402                .transpose()?;
403            let histogram_json = serde_json::to_string(&cs.histogram)?;
404            let mcv_values_json = serde_json::to_string(&cs.mcv_values)?;
405            let mcv_frequencies_json = serde_json::to_string(&cs.mcv_frequencies)?;
406            encoded.push(EncodedColumnStats {
407                column_name: col_name.clone(),
408                distinct_count: Self::u64_to_i64("distinct count", cs.distinct_count)?,
409                null_count: Self::u64_to_i64("null count", cs.null_count)?,
410                min_json,
411                max_json,
412                row_count: Self::u64_to_i64("row count", cs.row_count)?,
413                histogram_json,
414                mcv_values_json,
415                mcv_frequencies_json,
416            });
417        }
418        let rows = encoded
419            .iter()
420            .map(|stats| ColumnStatsInput {
421                table_name,
422                column_name: &stats.column_name,
423                distinct_count: stats.distinct_count,
424                null_count: stats.null_count,
425                min_value: stats.min_json.as_deref(),
426                max_value: stats.max_json.as_deref(),
427                row_count: stats.row_count,
428                histogram_json: &stats.histogram_json,
429                mcv_values_json: &stats.mcv_values_json,
430                mcv_frequencies_json: &stats.mcv_frequencies_json,
431            })
432            .collect::<Vec<_>>();
433        catalog.replace_column_stats(table_name, &rows)
434    }
435
436    pub(super) fn u64_to_i64(kind: &str, value: u64) -> StorageBackendResult<i64> {
437        i64::try_from(value).map_err(|_| {
438            StorageBackendError::Other(format!(
439                "ANALYZE {kind} {value} exceeds the persistent i64 range"
440            ))
441        })
442    }
443
444    /// Snapshot of the cardinality estimator's per-column statistics
445    /// for `table`. Clean statistics are reused, including sampled scalar
446    /// statistics from automatic maintenance. Dirty stats are recomputed
447    /// through the same durable transaction boundary as `ANALYZE`. Use
448    /// `run_analyze` to force full collection regardless of cached statistics.
449    /// Persistent query planning only consumes already-collected statistics.
450    pub fn column_stats(
451        &self,
452        table: &str,
453    ) -> StorageBackendResult<BTreeMap<String, uqa_planner::ColumnStats>> {
454        self.try_column_stats(table)
455    }
456
457    pub fn try_column_stats(
458        &self,
459        table: &str,
460    ) -> StorageBackendResult<BTreeMap<String, uqa_planner::ColumnStats>> {
461        self.with_direct_query_snapshot(
462            false,
463            |engine| engine.column_stats_in_execution(table, StatisticsRefresh::Current),
464            |error| StorageBackendError::backend("column statistics query", error),
465        )
466    }
467
468    pub(crate) fn column_stats_in_execution(
469        &self,
470        table: &str,
471        refresh: StatisticsRefresh,
472    ) -> StorageBackendResult<BTreeMap<String, uqa_planner::ColumnStats>> {
473        self.synchronize_table_data()?;
474        let canonical_name = self
475            .try_resolve_table_name(table)?
476            .ok_or_else(|| StorageBackendError::Other(format!("table `{table}` does not exist")))?;
477        let t = self
478            .try_table(&canonical_name)?
479            .ok_or_else(|| StorageBackendError::Other(format!("table `{table}` does not exist")))?;
480        if t.column_stats_dirty.load(Ordering::Acquire) {
481            if self.storage.catalog.is_none() {
482                // Memory-only lazy collection has no durable publication and
483                // must not invalidate the statement currently being planned.
484                let due = match refresh {
485                    StatisticsRefresh::Current => true,
486                    StatisticsRefresh::Maintained => {
487                        let maintenance = t.statistics_maintenance.lock();
488                        maintenance.due(
489                            maintenance.missing(t.column_stats.read().is_empty()),
490                            crate::statistics::now_ms(),
491                            crate::statistics::value_size::FORMAT_VERSION,
492                        )
493                    }
494                };
495                if due {
496                    self.analyze_table(&canonical_name, &t, false, None, true)?;
497                }
498                return Ok(t.column_stats.read().clone());
499            }
500            self.run_analyze(Some(&canonical_name))?;
501            // Starting maintenance can refresh session-local table bindings.
502            let refreshed = self.try_table(&canonical_name)?.ok_or_else(|| {
503                StorageBackendError::Other(format!("table `{canonical_name}` does not exist"))
504            })?;
505            return Ok(refreshed.column_stats.read().clone());
506        }
507        let stats = t.column_stats.read().clone();
508        Ok(stats)
509    }
510
511    pub(crate) fn try_query_column_stats(
512        &self,
513        table: &str,
514    ) -> StorageBackendResult<BTreeMap<String, uqa_planner::ColumnStats>> {
515        // Memory-only engines have no durable independent sessions or blob
516        // I/O. Retain their automatic lazy refresh at this boundary.
517        if self.storage.provider.is_none() && self.query_table_snapshots.is_none() {
518            return self.column_stats_in_execution(table, StatisticsRefresh::Maintained);
519        }
520        let table = self
521            .try_query_table(table)?
522            .ok_or_else(|| StorageBackendError::Other(format!("table `{table}` does not exist")))?;
523        // Cardinality estimates must never turn a projection or EXPLAIN into
524        // a synchronous full-table ANALYZE (including unrelated BLOB fields).
525        // Keep using the last collected estimate while the database worker
526        // refreshes it. A genuinely new table uses ordinary planner estimates.
527        let stats = table.column_stats.read().clone();
528        Ok(stats)
529    }
530}