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