A Tree-Structure Enhanced Transformer for Cardinality Estimation

Hu Mingjie, Zhang Qihang, Ren Jing, Liu Hengzhu
Proceedings of 2024 International Conference on Machine Learning and Intelligent Computing, PMLR 245:225-237, 2024.

Abstract

Accurate cardinality estimation is crucial for query optimization by guiding plan selection. Traditional cardinality estimation approaches often fail to provide precise estimates, leading to suboptimal query plans. In recent years, learning-based methods have emerged as a promising alternative. For tree-based learning methods, a conventional way to simply encode nearby parent-child pairs and learn by iteratively training hampers the performance. But it leads to a significant loss of structural information and incurs substantial computational overhead by the iterative training process. In this paper, we proposed a tree-structure positional encoding scheme. It can not only extract effective features for each node, but also capture the inherent structural characteristics of the tree. Based on the tree-based feature, we designed a novel transformer-based cardinality estimation model, which enhances the parallelism of the model training process and reduces the overhead caused by iterative training. On real-world datasets, our method beats the current state-of-the-art techniques, QF, by 25% in terms of mean qerror.

Cite this Paper

BibTeX
@InProceedings{pmlr-v245-mingjie24a, title = {A Tree-Structure Enhanced Transformer for Cardinality Estimation}, author = {Mingjie, Hu and Qihang, Zhang and Jing, Ren and Hengzhu, Liu}, booktitle = {Proceedings of 2024 International Conference on Machine Learning and Intelligent Computing}, pages = {225--237}, year = {2024}, editor = {Nianyin, Zeng and Pachori, Ram Bilas}, volume = {245}, series = {Proceedings of Machine Learning Research}, month = {26--28 Apr}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v245/main/assets/mingjie24a/mingjie24a.pdf}, url = {https://proceedings.mlr.press/v245/mingjie24a.html}, abstract = {Accurate cardinality estimation is crucial for query optimization by guiding plan selection. Traditional cardinality estimation approaches often fail to provide precise estimates, leading to suboptimal query plans. In recent years, learning-based methods have emerged as a promising alternative. For tree-based learning methods, a conventional way to simply encode nearby parent-child pairs and learn by iteratively training hampers the performance. But it leads to a significant loss of structural information and incurs substantial computational overhead by the iterative training process. In this paper, we proposed a tree-structure positional encoding scheme. It can not only extract effective features for each node, but also capture the inherent structural characteristics of the tree. Based on the tree-based feature, we designed a novel transformer-based cardinality estimation model, which enhances the parallelism of the model training process and reduces the overhead caused by iterative training. On real-world datasets, our method beats the current state-of-the-art techniques, QF, by 25% in terms of mean qerror.} }
Endnote
%0 Conference Paper %T A Tree-Structure Enhanced Transformer for Cardinality Estimation %A Hu Mingjie %A Zhang Qihang %A Ren Jing %A Liu Hengzhu %B Proceedings of 2024 International Conference on Machine Learning and Intelligent Computing %C Proceedings of Machine Learning Research %D 2024 %E Zeng Nianyin %E Ram Bilas Pachori %F pmlr-v245-mingjie24a %I PMLR %P 225--237 %U https://proceedings.mlr.press/v245/mingjie24a.html %V 245 %X Accurate cardinality estimation is crucial for query optimization by guiding plan selection. Traditional cardinality estimation approaches often fail to provide precise estimates, leading to suboptimal query plans. In recent years, learning-based methods have emerged as a promising alternative. For tree-based learning methods, a conventional way to simply encode nearby parent-child pairs and learn by iteratively training hampers the performance. But it leads to a significant loss of structural information and incurs substantial computational overhead by the iterative training process. In this paper, we proposed a tree-structure positional encoding scheme. It can not only extract effective features for each node, but also capture the inherent structural characteristics of the tree. Based on the tree-based feature, we designed a novel transformer-based cardinality estimation model, which enhances the parallelism of the model training process and reduces the overhead caused by iterative training. On real-world datasets, our method beats the current state-of-the-art techniques, QF, by 25% in terms of mean qerror.
APA
Mingjie, H., Qihang, Z., Jing, R. & Hengzhu, L.. (2024). A Tree-Structure Enhanced Transformer for Cardinality Estimation. Proceedings of 2024 International Conference on Machine Learning and Intelligent Computing, in Proceedings of Machine Learning Research 245:225-237 Available from https://proceedings.mlr.press/v245/mingjie24a.html.

Related Material