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