EUVIMEDEUVIMED entdecken
Crossref

Cardinality Estimation Graphs

Semih Salihoğlu, Jeremy Chen, Yuqing Huang, Mushi Wang, Ken Salem

Communications of the ACM · 2026-02 · 69 (2) · 99-109

DOI: 10.1145/3780104 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Communications of the ACM, online erschienen am 29.01.2026. Verfasst von Semih Salihoğlu und 4 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 25 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study two classes of summary-based cardinality estimators that use statistics about input relations and joins of a small number of input relations: (i) optimistic estimators, which were defined in the context of graph database management systems, that make uniformity and conditional independence assumptions; and (ii) the recent pessimistic estimators that use information theoretic linear programs (LPs). We show that optimistic estimators can be modeled as picking bottom-to-top paths in a cardinality estimation graph (CEG), which contains sub-queries as nodes and edges whose weights are average degree statistics. We show that existing optimistic estimators have either undefined or fixed choices for picking CEG paths as their estimates and ignore alternative choices. Instead, we outline a space of optimistic estimators to make an estimate on CEGs, which subsumes existing estimators. We show, using an extensive empirical analysis, that effective paths depend on the structure of the queries. We next show that optimistic estimators and seemingly disparate LP-based pessimistic estimators are in fact connected. Specifically, we show that CEGs can also model some recent pessimistic estimators. This connection allows us to provide insights into the pessimistic estimators, such as showing that they have combinatorial solutions.

Zitieren

APA

Salihoğlu, S., Chen, J., Huang, Y., Wang, M., & Salem, K. (2026). Cardinality Estimation Graphs. Communications of the ACM, 69(2), 99-109. https://doi.org/10.1145/3780104

Vancouver

Salihoğlu S, Chen J, Huang Y, Wang M, Salem K. Cardinality Estimation Graphs. Communications of the ACM. 2026;69(2):99-109. doi:10.1145/3780104

BibTeX
@article{Saliholu2026,
  author = {Salihoğlu, Semih and Chen, Jeremy and Huang, Yuqing and Wang, Mushi and Salem, Ken},
  title = {Cardinality Estimation Graphs},
  journal = {Communications of the ACM},
  year = {2026},
  volume = {69},
  number = {2},
  pages = {99--109},
  doi = {10.1145/3780104}
}
Kostenlos starten →