PaperlayerView exact revision on arXiv

Source-linked AI summary

FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation

Rong Zhu, Ziniu Wu, Yuxing Han, Kai Zeng, Andreas Pfadler, Zhengping Qian, Jingren Zhou, Bin Cui

arXiv:2011.09022v5cs.DBcs.AI

TL;DR

CardEst must model attribute distributions accurately and compactly, but existing approaches trade off accuracy against computation speed. FLAT uses FSPN to adaptively combine conditional and independent factorization. It reports gains across accuracy, speed, and storage on single-table benchmarks, as well as improved end-to-end query time in Postgres.

  • Problem

    Existing data-driven CardEst methods struggle to model complex attribute correlations while balancing estimation accuracy, probability-computation speed, and storage.

    Source: §1 · p. 1, §2 · p. 3

  • Method

    FLAT uses FSPN, an unsupervised graphical model that adaptively combines conditional and independent factorization to model different levels of attribute correlation.

    Source: §1 · p. 2

  • Results

    On single-table benchmarks, FLAT achieves up to 1–5 orders of magnitude better accuracy, 1–3 orders faster probability computation, and 1–2 orders lower storage cost than existing methods.

    Source: §1 · p. 2

  • Takeaways & Limitations

    In Postgres, FLAT improves average end-to-end query time by 12.9%, close to the 14.2% optimal result using true cardinalities.

    Source: §1 · p. 2

Abstract

from arXiv · show

Query optimizers rely on accurate cardinality estimation (CardEst) to produce good execution plans. The core problem of CardEst is how to model the rich joint distribution of attributes in an accurate and compact manner. Despite decades of research, existing methods either over simplify the models only using independent factorization which leads to inaccurate estimates, or over complicate them by lossless conditional factorization without any independent assumption which results in slow probability computation. In this paper, we propose FLAT, a CardEst method that is simultaneously fast in probability computation, lightweight in model size and accurate in estimation quality. The key idea of FLAT is a novel unsupervised graphical model, called FSPN. It utilizes both independent and conditional factorization to adaptively model different levels of attributes correlations, and thus dovetails their advantages. FLAT supports efficient online probability computation in near liner time on the underlying FSPN model, provides effective offline model construction and enables incremental model updates. It can estimate cardinality for both single table queries and multi table join queries. Extensive experimental study demonstrates the superiority of FLAT over existing CardEst methods on well known IMDB benchmarks: FLAT achieves 1 to 5 orders of magnitude better accuracy, 1 to 3 orders of magnitude faster probability computation speed and 1 to 2 orders of magnitude lower storage cost. We also integrate FLAT into Postgres to perform an end to end test. It improves the query execution time by 12.9% on the benchmark workload, which is very close to the optimal result 14.2% using the true cardinality.

1 INTRODUCTION

CardEst must estimate query result sizes while balancing accuracy, inference speed, and storage. FLAT uses FSPN to adaptively combine conditional and independent factorization, and is evaluated on single-table and multi-table queries as well as in Postgres.

1 INTRODUCTION

  • Existing CardEst methods struggle to balance accuracy, inference speed, and storage when modeling complex real-world data.Conditional factorization can be slow, while independence assumptions can yield inaccurate estimates.Source: §1 · pp. 1–2
  • FSPN adaptively models attribute dependence, using conditional factorization for highly and weakly correlated attributes and independent factorization within suitable regions.It combines conditional and independent factorization to adapt to different levels of correlation.Source: §1 · p. 2
  • For multi-table queries, FLAT clusters tables offline, builds an FSPN for each group, and combines subquery probabilities online.The framework is described as more general and applicable than existing work.Source: §1 · p. 2
  • On single-table benchmarks, FLAT achieves up to 1–5 orders of magnitude better accuracy, 1–3 orders faster probability computation, and 1–2 orders lower storage cost.Probability computation is near 0.2 ms, with storage of only tens of KB.Source: §1 · p. 2
  • On JOB-light and a crafted multi-table workload, FLAT attains the highest accuracy, near 5 ms computation, and 3.3 MB storage.The computation time is an order of magnitude faster than existing methods.Source: §1 · p. 2
  • In Postgres, FLAT improves average end-to-end query time by 12.9%, close to the 14.2% optimal result using true cardinalities.The authors state this addresses whether and how much more accurate CardEst can improve query-plan quality.Source: §1 · p. 2

2 PROBLEM DEFINITION AND BACKGROUND

CardEst estimates how many records satisfy a query without executing it, by estimating the probability of the query under a model of the table’s joint distribution. Existing data-driven approaches trade off model accuracy, probability-computation speed, and storage.

CardEst Problem

  • The problem covers single or joined tables whose attributes may be categorical or continuous, with selection predicates represented by intervals.The paper does not consider LIKE queries on strings.Source: §2 · p. 2
  • CardEst estimates the number of records satisfying a query without executing it, equivalently estimating the query probability and scaling it by table size.The table is modeled as records sampled from the joint PDF of its attributes.Source: §2 · p. 2

Data-Driven CardEst Methods Analysis

  • FullStore has intractable storage, while sampling and kernel methods can be inaccurate or inefficient on high-dimensional data.These approaches either store compressed joint distributions or fetch samples on the fly.Source: §2 · p. 2
  • Factorization methods reduce joint distributions to low-dimensional PDFs, but independent factorization can be inaccurate when correlations violate its assumptions.One-dimensional histograms can compute probabilities in O(|A|) time while ignoring attribute correlations.Source: §2 · pp. 2–3
  • Multidimensional histograms model dependencies within attribute subsets and assume independence across subsets, improving accuracy at the cost of space.Their decomposition remains lossy.Source: §2 · p. 3
  • Conditional factorization can preserve the joint distribution but slow probability computation; SPNs can become large when local independence fails.Strong correlations may lead SPNs to repeatedly split records into very small subsets.Source: §2 · p. 3

3 THE FSPN MODEL

FSPN is a tree-structured model that adapts its factorization to attribute dependence: conditional factorization separates correlated groups, while independent factorization models weakly correlated attributes in suitable contexts. Its node operations support these different modeling choices and distinguish it from SPN.

Key Ideas of FSPN

  • FSPN adaptively uses conditional factorization to separate highly and weakly correlated attributes, then models highly correlated groups together and weakly correlated attributes recursively.The paper’s ocean-observation example applies this approach to water turbidity, temperature, wave height, and wind force.Source: §3 · p. 3

Formulation of FSPN

  • Each FSPN node records its attribute scope, condition attributes, record context, and the operation used to generate children.An empty condition represents a joint PDF; otherwise the node represents a conditional PDF.Source: §3 · p. 4

FSPN Operations

  • Factorize nodes separate highly correlated attributes from the remaining attributes through conditional factorization.The factorization is Pr(A_n) = Pr(A_n − H) · Pr(H|A_n − H).Source: §3 · p. 4
  • Sum nodes partition records into weighted subsets, while Product nodes split attributes only when contextual independence holds.Sum-node weights are each subset’s proportion of the records at that node.Source: §3 · p. 4
  • Split nodes partition records by condition-attribute values, whereas Uni-leaves store univariate PDFs and Multi-leaves store multivariate PDFs under stated independence conditions.Split partitions are disjoint; a Multi-leaf is used when its scope is independent of the condition attributes.Source: §3 · p. 4

Differences with SPN

  • Unlike SPN, FSPN adapts modeling to dependence levels and uses split and Multi-leaf nodes for highly correlated attributes.SPN uses sum and product operations across attributes, which can create a large structure when local independence does not hold.Source: §3 · p. 4

Generality of FSPN

  • FSPN generalizes 1-D histograms, SPNs, and Bayesian Networks, and is no worse than SPN or BN in expressive efficiency.The paper states that disabling factorize yields SPN, while independent attributes yield a 1-D histogram.Source: §3 · pp. 4–5

4 SINGLE TABLE CardEst METHOD

For single-table cardinality estimation, FLAT builds an FSPN that adapts its factorization to attribute dependencies and computes query probabilities recursively. It also supports offline construction and incremental model updates.

4.1 Online Probability Computation

  • FLAT-Online splits query ranges at factorize-node partitions, evaluates conditional and marginal probabilities recursively, then sums their products.Sum and product nodes combine child probabilities by weighted summation and multiplication, respectively.Source: §4.1 · p. 5
  • 1–3 orders of magnitude faster than other methods, FLAT-Online runs near histogram speed in testing.The reported comparison concerns probability-computation speed.Source: §4.1 · p. 6

4.2 Offline Structure Construction

  • FLAT-Offline separates highly correlated attributes conditionally, factors independent subsets, and clusters records when local independence is absent.For conditional attributes, it uses multi-leaf PDFs when independent and otherwise partitions their domain into grid regions.Source: §4.2 · p. 6
  • Univariate leaves use histograms or Gaussian mixtures, while conditional multivariate leaves use piecewise regression.Source: §4.2 · p. 6

4.3 Incremental Updates

  • Updates preserve the FSPN structure where possible, propagate changes through nodes, and recheck independence, rebuilding local structure when needed.Multi-leaf and product nodes are rechecked after data changes; failed independence checks trigger further splitting or reconstruction.Source: §4.3 · p. 7

5 MULTI-TABLE CardEst METHOD

FLAT models groups of joined tables with local FSPNs and corrects their probabilities using scattering coefficients. Its framework supports multiple join types and incremental updates, with stated exclusions for self-joins and circular joins.

5 MULTI-TABLE CardEst METHOD

  • FLAT extends local-model join estimation to inner, outer, and many-to-many joins, whereas the cited earlier approach supports only primary-foreign-key joins.The paper describes many-to-many joins as common in query optimization.Source: §5 · p. 7
  • The offline phase groups highly correlated tables into join-tree nodes, adds scattering-coefficient columns, and builds an FSPN for each node.The method does not consider self-joins or circular joins.Source: §5 · p. 7
  • Scattering coefficients track join multiplicities on both sides, allowing local probabilities to be corrected for down-scale and up-scale effects.For each record, the correction factor is e/s, with zero values treated as 1.Source: §5 · p. 8
  • FLAT computes each corrected sub-query probability with one traversal of its FSPN, then multiplies probabilities across touched nodes.The attribute-query probability is computed on the factorize node's left child; expected scattering values are precomputed on leaves.Source: §5 · pp. 8–9
  • For record insertions and deletions, FLAT updates affected local and neighboring models; creating or deleting tables requires offline retraining.Source: §5 · p. 9

6 EVALUATION RESULTS

Across single-table and join workloads, FLAT delivers high estimation accuracy with low query latency, and its incremental updates trade some accuracy for much less update time than retraining. In Postgres, FLAT improves end-to-end query time by 12.9%.

6.1 Single Table Evaluation Results

  • Median q-error is 1.001 on GAS and 1.002 on DMV; FLAT leads on GAS, while Naru and SPN-Multi are comparable and marginally better on DMV.The optimal q-error is 1.Source: §6.1 · p. 10, Table 1 · p. 10
  • FLAT’s latency is around 0.2 ms on DMV and 0.5 ms on GAS, close to Histogram and faster than other methods.FSPN uses 210 nodes on GAS and 20 on DMV, compared with 873 and 823 nodes for DeepDB.Source: §6.1 · pp. 10–11, Figure 5 · p. 10

6.2 Multi-Table Evaluation Results

  • At the 95% quantile on JOB-light, FLAT outperforms NeuroCard by 2.6×, BN by 33×, DeepDB by 1.7×, and MSCN by 43×.NeuroCard is slightly better on maximum q-error, which reflects only one query in the workload.Source: §6.2 · p. 11, Table 2 · p. 11
  • At the 95% quantile on JOB-ours, FLAT outperforms NeuroCard, DeepDB, and MSCN by 1.4×, 4.3×, and 7.8×, respectively.The performance of other algorithms drops significantly on this more complex workload.Source: §6.2 · p. 11, Table 3 · p. 12
  • On harder JOB-ours, FLAT’s q-error is relatively larger than on JOB-light, but its median is only 1.2, although true cardinalities for the tail 5% of queries are often below 100.Source: §6.2 · p. 11
  • FLAT requires around 5 ms per multi-table query, outperforming BN by 5×, Sample by 12.4×, KDE by 4.8×, and DeepDB by 5.2×.Its accuracy is also more stable with the number of joins and predicates.Source: §6.2 · p. 11, Figure 7 · p. 12

6.3 Effects of Updates

  • FLAT’s incremental update accuracy is close to retraining while its time cost is much lower, for both insertion and deletion.The non-updated model has the lowest accuracy as the data distribution changes; retraining has the highest accuracy and update time.Source: §6.3 · p. 11, Table 4 · p. 12

6.4 End-to-End Evaluation on Postgres

  • FLAT improves end-to-end Postgres query time by 12.9%, compared with 4.6% for NeuroCard.Without accounting for CardEst latency, both methods improve query time by near 13%, close to the 14.2% improvement using true cardinality.Source: §6.4 · p. 12

7 RELATED WORK

The section reviews query-driven cardinality estimation and machine learning in databases, while noting possible uses of FSPN beyond CardEst. It also describes efforts to integrate FLAT with learned query optimizers.

7 RELATED WORK

  • Query-driven CardEst moved from query-feedback corrections to learned mappings from query features to cardinalities,, [24].The section also notes that learned query optimizers have used query embeddings [38] and reinforcement learning for join ordering [27].Source: §7 · p. 12
  • Query-driven methods require many executed queries and work well only when future queries resemble training samples, limiting their flexibility and generalizability.The section also identifies dependence on how input queries are featurized as a drawback.Source: §7 · p. 12
  • The authors are trying to integrate FLAT with learned query-plan generation and join-order optimization approaches.They describe this as work toward an end-to-end database query-optimization solution.Source: §7 · p. 12
  • FSPN is presented as a general unsupervised model that may also apply to approximate group-by processing, hashing, and multidimensional indexing.The authors say they are trying to apply it in these database scenarios, which also require modeling high-dimensional joint PDFs.Source: §7 · p. 12

8 CONCLUSIONS

The conclusion presents FLAT as an unsupervised CardEst method built on FSPN for single- and multi-table queries. The appendix describes how FSPN can represent SPNs and discrete Bayesian networks equivalently.

8 CONCLUSIONS

  • FLAT uses FSPN, a new graphical model that adaptively models attribute joint PDFs, for single- and multi-table cardinality estimation.The conclusion characterizes FLAT as simultaneously fast in probability computation, lightweight in storage, and accurate in estimation.Source: §8 · p. 12
  • The authors report that benchmark experiments and an end-to-end Postgres evaluation demonstrate the superiority of their proposed methods.They identify integration into an end-to-end learned query optimizer and broader database applications for FSPN as future directions.Source: §8 · p. 13

A RELATIONS BETWEEN FSPN AND OTHER MODELS

A.1 Transforming to FSPN

  • An SPN can be represented by an equivalent FSPN by disabling factorization with an infinite threshold and following the SPN construction steps.For a discrete BN, the conversion recursively uses product nodes for independent components, uni-leaves for root variables, and factorize and split nodes for conditional distributions.Source: §A.1 · p. 16

A.2 Proof of Lemma 1

The appendix establishes a space bound for equivalent FSPN representations and provides pseudocode for incremental updates to single-table and multi-table models.

A.2 Proof of Lemma 1

  • An equivalent FSPN uses no more than O(M) space when the represented joint PDF has an SPN or BN representation with O(M) space.Source: §A.2 · p. 16

B DETAILED UPDATING ALGORITHM

B.1 FLAT-Update Algorithm

  • FLAT-Update traverses a single-table FSPN top-down, preserving its structure as much as possible while fine-tuning parameters to fit updated data.Source: §B.1 · p. 16

B.2 FLAT-Update-Multi Algorithm

  • FLAT-Update-Multi identifies the impact of a table change, then updates FSPNs for attribute columns and scattering-coefficient columns.The pseudocode handles inserted or removed records and periodically recomputes scattering columns.Source: §B.2 · pp. 16–17

C PROOF OF LEMMA 2

The proof obtains cardinality on a join from probabilities over touched tables and adjusts for scattering from untouched tables. It then expresses the calculation using local join-node models.

C PROOF OF LEMMA 2

  • For query-touched join nodes, the lemma defines scattering columns for distinct joins to unqueried tables and assignments to those columns.Source: C PROOF OF LEMMA 2 · p. 17
  • The proof converts query probability on the touched tables Z to cardinality by multiplying by |Z|.It uses independence across join-tree nodes and computes local terms from each node's PDF and scattering columns.Source: C PROOF OF LEMMA 2 · p. 17
  • To remove the effects of untouched tables, the proof divides by their scattering multiplicity, treating a zero scattering coefficient as one.It describes scaling from a touched table's query probability to the full outer join over touched nodes.Source: C PROOF OF LEMMA 2 · pp. 17–18

D SENSITIVITY ANALYSIS OF HYPER-PARAMETERS

FLAT’s hyperparameters trade estimation accuracy against model size, learning time, and inference efficiency. The paper describes how each setting affects these trade-offs, giving users a basis for choosing settings suited to their data and resources.

D SENSITIVITY ANALYSIS OF HYPER-PARAMETERS

  • Smaller τ_l can improve accuracy but creates more sum and split nodes, increasing model size and reducing learning or inference efficiency.τ_l is the RDC threshold for deciding whether two attributes are independent.Source: D SENSITIVITY ANALYSIS OF… · p. 18
  • Larger τ_h can compact factorize nodes for highly correlated attributes, but undiscovered correlated attributes may leave a less compact left branch.τ_h is the RDC threshold for deciding whether attributes are highly correlated.Source: D SENSITIVITY ANALYSIS OF… · p. 18
  • Larger d may improve compactness and accuracy but lengthens split-node training, while larger c speeds inference and compacts the model but may reduce accuracy.A larger c can stop further splitting sooner, even when attributes in a uni-leaf node are not independent.Source: D SENSITIVITY ANALYSIS OF… · p. 18
  • More histogram bins b and regression pieces p can improve distribution modeling but require more time and storage.b controls histogram bins, while p controls pieces for piecewise regression in multi-leaf nodes.Source: D SENSITIVITY ANALYSIS OF… · p. 18
  • A larger sample n can improve estimation by representing the table more closely and preventing overfitting, but collecting it may cost time and memory.The sample is drawn from the full outer-join table for training.Source: D SENSITIVITY ANALYSIS OF… · p. 18
  • Each FLAT hyperparameter represents a trade-off between estimation accuracy and learning or inference efficiency, and its influence is predictable enough for users to choose settings suited to their data and resources.The analysis covers the RDC thresholds τ_l and τ_h, partitioning intervals d, stopping threshold c, histogram bins b, regression pieces p, and sample count n.Source: D SENSITIVITY ANALYSIS OF… · p. 18

E ADDITIONAL EVALUATION RESULTS

This section presents additional evaluation results.

E ADDITIONAL EVALUATION RESULTS

E.1 Estimation Latency on GPUs

On the examined GPU benchmarks, FLAT running on CPUs is faster than Naru running on GPUs. The multi-table comparison does not include NeuroCard’s GPU implementation because the required CUDA version is unsupported on the test machine.

E.1 Estimation Latency on GPUs

  • GPU acceleration substantially speeds up the DNN computations of both MSCN and Naru.Source: §E.1 · p. 18
  • 19× and 58× faster than GPU-based Naru on GAS and DMV, respectively, FLAT runs on CPUs.Source: §E.1 · pp. 18–19
  • NeuroCard’s GPU implementation is excluded from the multi-table comparison because its required CUDA version is unsupported on the test machine.Source: §E.1 · p. 19

E.2 Performance Stability

On JOB-ours, FLAT’s end-to-end query-time improvement is more significant than NeuroCard’s, while their query-time improvements excluding CardEst latency are close to using true cardinality. The additional evaluations report FLAT’s stability across synthetic data variations and its performance as join and predicate counts change.

E.2 Performance Stability

  • Varied attribute correlation has mild impact on FLAT, while increasing correlation severely degrades Histogram and DeepDB performance.The authors attribute FLAT’s behavior to modeling the joint PDF without an independence assumption.Source: §E.2 · p. 19
  • Increasing Pareto skewness has slight impact on FLAT but severely degrades Naru and Sample performance.The authors attribute FLAT’s robustness to using multi-histograms to represent distributions.Source: §E.2 · p. 19
  • Increasing domain size degrades FLAT’s performance, but it remains within a reasonable range; increasing attribute count also degrades performance, though it remains reasonable with tens of attributes.The paper summarizes FLAT as sensitive to attribute count and relatively robust to domain size.Source: §E.2 · p. 19

E.3 Performance with Varied Number of Joins and Predicates

  • As join size and predicate count increase, DeepDB’s q-error rises substantially, while NeuroCard’s and FLAT’s change little.Figure 9 reports q-error across different numbers of joins and predicates; the authors attribute FLAT’s stability to FSPN modeling attributes at different dependency levels.Source: Figure 9 · p. 19, §E.3 · p. 19

E.4 End-to-End Test on JOB-ours Workload

  • On JOB-ours, FLAT’s end-to-end query-time improvement is more significant than NeuroCard’s, while excluding CardEst latency, both are close to the true-cardinality method.Source: Table 8 · p. 20, §E.4 · p. 20

Related papers

Loading 2011.09022v5…