Approximate query processing approach based on deep autoregressive model

doi:10.11772/j.issn.1001-9081.2022071128

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (7): 2034-2039.DOI: 10.11772/j.issn.1001-9081.2022071128

• The 39th CCF National Database Conference (NDBC 2022) • Previous Articles

Approximate query processing approach based on deep autoregressive model

Libin CEN¹, Jingdong LI¹, Chunbo LIN², Xiaoling WANG¹()

^1.School of Computer Science and Technology，East China Normal University，Shanghai 200062，China
^2.Gauss Database Labs，Huawei Technologies Company Limited，Shanghai 201206，China

Received:2022-07-12 Revised:2022-08-25 Accepted:2022-08-29 Online:2023-07-20 Published:2023-07-10
Contact: Xiaoling WANG
About author:CEN Libin， born in 1999， M. S. candidate. His research interests include query optimization， approximate query processing.
LI Jingdong， born in 1996， Ph. D. candidate. His research interests include graph data mining， database theory.
LIN Chunbo， born in 1995， M. S. His research interests include database theory， approximate query processing.
WANG Xiaoling， born in 1975， Ph. D.， professor. Her research interests include distributed graph data processing， knowledge graph， sequence recommendation and sequence data analysis.
Supported by:
Key Project of National Natural Science Foundation of China(62136002);Key Project of Science and Technology Commission of Shanghai Municipality(20DZ1100300)

基于深度自回归模型的近似查询处理方法

岑黎彬¹, 李靖东¹, 林淳波², 王晓玲¹()

^1.华东师范大学计算机科学与技术学院，上海 200062
^2.华为技术有限公司高斯实验室，上海 201206

通讯作者: 王晓玲
作者简介:岑黎彬（1999—），男，广西梧州人，硕士研究生，CCF学生会员，主要研究方向：查询优化、近似查询处理；
李靖东（1996—），男，江西景德镇人，博士研究生，CCF学生会员，主要研究方向：图数据挖掘、数据库理论；
林淳波（1995—），男，浙江绍兴人，硕士，CCF会员，主要研究方向：数据库理论、近似查询处理；
王晓玲（1975—），女，山东烟台人，教授，博士，CCF会员，主要研究方向：分布式图数据处理、知识图谱、序列推荐与序列数据分析。
基金资助:
国家自然科学基金重点项目(62136002);上海市科委重点项目(20DZ1100300)

Abstract

Abstract:

Recently， Approximate Query Processing （AQP） of aggregate functions is a research hotspot in the database field. Existing approximate query techniques have problems such as high query response time cost， high storage overhead， and no support for multi-predicate queries. Thus， a deep autoregressive model-based AQP approach DeepAQP （Deep Approximate Query Processing） was proposed. DeepAQP leveraged deep autoregressive model to learn the joint probability distribution of multi-column data in the table in order to estimate the selectivity and the target column’s probability distribution of the given query， enhancing the ability to handle the approximate query requests of aggregation functions with multiple predicates in a single table. Experiments were conducted on TPC-H and TPC-DS datasets. The results show that compared with VerdictDB， which is a sample-based method， DeepAQP has the query response time reduced by 2 to 3 orders of magnitude， and the storage space reduced by 3 orders of magnitude； compared with DBEst++， which is a machine learning-based method， DeepAQP has the query response time reduced by 1 order of magnitude and the model training time reduced significantly. Besides， DeepAQP can handle with multi-predicate query requests， for which DBEst++ does not support. It can be seen that DeepAQP achieves good accuracy and speed at the same time and reduces the training and storage overhead of algorithm significantly.

Key words: Approximate Query Processing (AQP), autoregressive model, multi-predicate query, deep learning, aggregate function

摘要：

聚合函数的近似查询处理（AQP）是近年来数据库领域的研究热点。针对现有的近似查询技术存在查询响应时间长、存储开销大、不支持多谓词查询等问题，提出一种基于深度自回归模型的AQP方法DeepAQP （Deep Approximate Query Processing），利用深度自回归模型对表中多列数据的联合概率分布进行学习和建模，以估计给定查询的谓词选择度和目标列概率分布，以促进单表下多谓词聚合函数近似查询请求的有效处理。在TPC-H和TPC-DS数据集上进行实验，结果表明，与基于采样的VerdictDB方法相比，DeepAQP在查询响应时间和存储空间开销上均降低了2到3个数量级；与基于传统机器学习模型的DBEst++方法相比，DeepAQP的查询响应时间降低了1个数量级，显著降低了模型训练耗时，并且可以处理DBEst++所不支持的多谓词查询请求。可见，DeepAQP兼顾了查询精度和速度，并显著降低了算法在训练和存储上的开销。

关键词: 近似查询处理, 自回归模型, 多谓词查询, 深度学习, 聚合函数

CLC Number:

TP391

Libin CEN, Jingdong LI, Chunbo LIN, Xiaoling WANG. Approximate query processing approach based on deep autoregressive model[J]. Journal of Computer Applications, 2023, 43(7): 2034-2039.

岑黎彬, 李靖东, 林淳波, 王晓玲. 基于深度自回归模型的近似查询处理方法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2034-2039.

Figures/Tables 8

Tab. 1 Example data

Age	City	Salary/$
26	London	1 200
30	London	3 000
40	Paris	4 500
40	London	5 000

Fig. 1 Structure and characteristics of MADE

Fig. 2 DeepAQP framework

Fig. 3 Query response time

Fig. 4 Average relative error of AVG

Fig. 5 Average relative error of COUNT

Tab. 2 Storage overhead

数据集	DBEst++/KB	VerdictDB/GB	DeepAQP/MB
TPC-H	49	2.39	8.4
TPC-DS	39	0.57	8.7

Tab. 3 Sampling and training time

数据集	DBEst++	VerdictDB	DeepAQP
TPC-H	899	938	121
TPC-DS	151	763	78

References 16

1	PARK Y， MOZAFARI B， SORENSON J， et al. VerdictDB： universalizing approximate query processing ［C］// Proceedings of the 2018 International Conference on Management of Data. New York： ACM， 2018： 1461-1476. 10.1145/3183713.3196905
2	AGARWAL S， MOZAFARI B， PANDA A， et al. BlinkDB： queries with bounded errors and bounded response times on very large data ［C］// Proceedings of the 8th ACM European Conference on Computer Systems. New York： ACM， 2013： 29-42. 10.1145/2465351.2465355
3	MA Q Z， TRIANTAFILLOU P. DBEst： revisiting approximate query processing engines with machine learning models ［C］// Proceedings of the 2019 International Conference on Management of Data. New York： ACM， 2019： 1553-1570. 10.1145/3299869.3324958
4	MA Q Z， SHANGHOOSHABAD A M， ALMASI M， et al. Learned approximate query processing： make it light， accurate and fast［C/OL］// Proceedings of the 11th Annual Conference on Innovative Data Systems Research ［2022-05-11］. .
5	SALIMANS T， KARPATHY A， CHEN X， et al. PixelCNN++： improving the PixelCNN with discretized logistic mixture likelihood and other modifications［EB/OL］. （2017-01-19）［2022-05-11］. .
6	VASWANI A， SHAZEER N， PARMAR N， et al. Attention is all you need ［C］// Proceedings of the 31st International Conference on Neural Information Processing Systems. Red Hook， NY： Curran Associates Inc.， 2017： 6000-6010.
7	YANG Z H， LIANG E， KAMSETTY A， et al. Deep unsupervised cardinality estimation［J］. Proceedings of the VLDB Endowment， 2019， 13 （3）： 279-292. 10.14778/3368289.3368294
8	HASAN S， THIRUMURUGANATHAN S， AUGUSTINE J， et al. Deep learning models for selectivity estimation of multi-attribute queries ［C］// Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York： AMC， 2020： 1035-1050. 10.1145/3318464.3389741
9	GERMAIN M， GREGOR K， MURRAY I， et al. MADE： masked autoencoder for distribution estimation ［C］// Proceedings of the 32nd International Conference on Machine Learning. New York： JMLR.org， 2015： 881-889.
10	LI K Y， LI G L. Approximate query processing： what is new and where to go？［J］. Data Science and Engineering， 2018， 3 （4）： 379-397. 10.1007/s41019-018-0074-4
11	HELLERSTEIN J M， HAAS P J， WANG H J. Online aggregation ［C］// Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data. Ney York： ACM 1997： 171-182. 10.1145/253260.253291
12	LI F F， WU B， YI K， et al. Wander join： online aggregation via random walks ［C］// Proceedings of the 2016 International Conference on Management of Data. New York： ACM， 2016： 615-629. 10.1145/2882903.2915235
13	LOHR S. Sampling： Design and Analysis［M］. 2nd ed. Boca Raton， FL： Chapman & Hall， 2019： 73.
14	LI G L， ZHOU X H， CAO L. AI meets database： AI4DB and DB4AI ［C］// Proceedings of the 2021 International Conference on Management of Data. New York： ACM， 2021： 2859-2866. 10.1145/3448016.3457542
15	HINTON G E， SALAKHUTDINOV R R. Reducing the dimensionality of data with neural networks［J］. Science， 2006， 313 （5786）： 504-507. 10.1126/science.1127647
16	NASH C， DURKAN C. Autoregressive energy machines ［C］// Proceedings of the 36th International Conference on Machine Learning. New York： JMLR.org， 2019： 1735-1744.

[1]	Yichi CHEN, Bin CHEN. Review of lifelong learning in computer vision [J]. Journal of Computer Applications, 2023, 43(6): 1785-1795.
[2]	Xin JIN, Yangchuan LIU, Yechen ZHU, Zijian ZHANG, Xin GAO. Sinogram inpainting for sparse-view cone-beam computed tomography image reconstruction based on residual encoder-decoder generative adversarial network [J]. Journal of Computer Applications, 2023, 43(6): 1950-1957.
[3]	Runting DONG, Li WU, Xiaoying WANG, Tengfei CAO, Jianqiang HUANG, Qin GUAN, Jiexia WU. Review of application analysis and research progress of deep learning in weather forecasting [J]. Journal of Computer Applications, 2023, 43(6): 1958-1968.
[4]	Jing QIN, Xueqian MA, Fujie GAO, Changqing JI, Zumin WANG. Survey of Parkinson’s disease auxiliary diagnosis methods based on gait analysis [J]. Journal of Computer Applications, 2023, 43(6): 1687-1695.
[5]	Yang LIU, Zhiyang LU, Jun WANG, Jun SHI. Gibbs artifact removal algorithm for magnetic resonance imaging based on self-attention connection UNet [J]. Journal of Computer Applications, 2023, 43(5): 1606-1611.
[6]	Liyao FU, Mengxiao YIN, Feng YANG. Transformer based U-shaped medical image segmentation network： a survey [J]. Journal of Computer Applications, 2023, 43(5): 1584-1595.
[7]	Xianlan WANG, Jinkun ZHOU, Nan MU, Chen WANG. Cross-view geo-localization method based on multi-task joint learning [J]. Journal of Computer Applications, 2023, 43(5): 1625-1635.
[8]	Qinghai XU, Shifei DING, Tongfeng SUN, Jian ZHANG, Lili GUO. Improved capsule network based on multipath feature [J]. Journal of Computer Applications, 2023, 43(5): 1330-1335.
[9]	Xu ZHANG, Long SHENG, Haifang ZHANG, Feng TIAN, Wei WANG. Pre-hospital emergency text classification model based on label confusion [J]. Journal of Computer Applications, 2023, 43(4): 1050-1055.
[10]	Xiaoyu FAN, Suzhen LIN, Yanbo WANG, Feng LIU, Dawei LI. Reconstruction algorithm for highly undersampled magnetic resonance images based on residual graph convolutional neural network [J]. Journal of Computer Applications, 2023, 43(4): 1261-1268.
[11]	Haiyu YANG, Wenpu GUO, Kai KANG. Signal modulation recognition method based on convolutional long short-term deep neural network [J]. Journal of Computer Applications, 2023, 43(4): 1318-1322.
[12]	Zhoubo XU, Puqing CHEN, Huadong LIU, Xin YANG. Deep graph matching model based on self-attention network [J]. Journal of Computer Applications, 2023, 43(4): 1005-1012.
[13]	Cheng FANG, Bei LI, Ping HAN, Qiong WU. Fine-grained emotion classification of Chinese microblog based on syntactic dependency graph [J]. Journal of Computer Applications, 2023, 43(4): 1056-1061.
[14]	Guangyi DOU, Fanan WEI, Chuangyi QIU, Jianshu CHAO. Tracking appearance features based on attention self-correlation mechanism [J]. Journal of Computer Applications, 2023, 43(4): 1248-1254.
[15]	Jianqing GAO, Yanhui TU, Feng MA, Zhonghua FU. Progressive ratio mask-based adaptive noise estimation method [J]. Journal of Computer Applications, 2023, 43(4): 1303-1308.

Approximate query processing approach based on deep autoregressive model

基于深度自回归模型的近似查询处理方法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 16

Related Articles 15

Recommended Articles

Metrics