论文导读机器学习在数据库基数估计中的应用

有时候我们也需要对不止一个表的复杂查询(包含多表连接(join)、范围查询(rangequery)等)估计基数,这些都是数据库基数估计的研究内容。

基数估计的作用主要可概括成如下两个方面:

(2)基数估计可以帮助回答一些只需要知道结果数量的查询。例如某个用户可能想知道全中国有多少大学生学习计算机专业,这个查询只关心结果的数目而不需要知道每条结果的具体值。对这样的查询我们可以通过基数估计的方法快速返回结果大小的近似值。

目前方法的分类

基数估计是一个重要且较为困难的问题,几十年来一直有研究者尝试用各种方法和技巧提升估计的准确性和稳健性,现有的方法可以分为如下几类:

传统型基数估计方法

传统型基数估计方法大体上可以分为基于概要(synopsis-based)和采样(sampling)的两大类方法。

基于概要的基数估计方法会预先收集数据库的一些统计信息,并基于独立性等简单假设,能够方便快速地求解查询基数。

例如基于直方图(histogram)的方法,其对数据表中每一列总结成一张等宽(equalwidth)或等深(equaldepth)的直方图,最后根据查询条件,基于列与列之间相互独立的假设,估计出查询结果的大小。当然有时这样的独立性假设效果不好,便可根据多维直方图(multi-dimensionalhistogram)的方法求解。

数据画像(sketching)也属于基于概要的基数估计方法,其使用bitmap或哈希的方法,估计数据库中互不相同的元素个数,比较适合流式数据的场景。更新的一类数据画像的方法如loglog、hyperloglog等,更加注重节约内存和提升估计的稳健性。

基于采样的方法会从原始数据表中随机抽取一定比例或者一定数量的元组,最终根据在采样集上执行查询后的结果大小除以相应的缩放比例便可得到查询在原数据库的基数估计。基于采样的方法在采样策略较好、能反映大部分数据分布的情况下效果较好,但也很容易由于采样的随机性无法产生采样集上匹配结果的情况,便有研究者提出了一种基于索引的采样方法(index-basedsampling)[1],其在多表连接时,会根据查询的连接条件选择要采样的范围,能减少采样出现零结果的情况,具体图示如下:

查询驱动的学习型基数估计方法

由于基数估计可以视为“查询”到”基数值”的回归问题(当数据库没有更新时),故我们可以将监督学习的技巧迁移到本问题上,直接学习查询到基数的对应关系。一般的查询驱动方法的工作流程如下所示:

其难点主要在于训练数据的获取和查询语句的表示两方面。

通常而言,当数据库给定时,我们可以假设查询框架(schema)是已知的(例如,某两个表会根据哪些列做连接等),由此我们可以随机产生一些查询语句,将这些语句真实运行之后,我们便得到了这些查询的真实基数,这就构成了训练模型需要的训练数据。当然也可以根据数据库的查询日志直接获取查询。需要注意的是,训练数据一定要有代表性,否则模型不能学习到工作环境中常见的查询模式到基数的对应,会影响到预测的准确性。

查询语句的表示主要由查询表、谓词条件、连接条件等决定,更复杂的情况包括含正则表示式之类的“like”查询。

工作[4]中,作者将基数估计和查询计划的代价估计结合在同一个端到端的学习型估计模型里。其依赖于数据库系统的优化器对于输入查询产生一个物理计划,训练数据则由(查询计划,准确基数,准确计划代价)三元组的形式构成。由于查询计划为树状结构,故其模型使用树形LSTM。简而言之,计划树中的每个节点都接收来自子节点的信息,并和自己的信息综合,最终将查询数根节点的输出送入预测基数和预测代价的两个模型得到想要的估计。本篇工作中还提出了根据谓词条件的联系(AND、OR等),分别使用MIN、MAX池化,具体细节可以参照其论文。下图展示了其模型的工作流程:

数据驱动的学习型基数估计方法

与查询驱动类的方法不同,数据驱动的基数估计方法为无监督的一类方法,直接从数据表中学习数据的分布,因此训练较为简单。

在工作[5]中,作者使用核密度估计(kerneldensityestimation,KDE)的方法估计查询基数。其想法为在数据表中随机抽取若干元组,这样查询点和采样元组越靠近,那该查询有结果的可能性就会较大。作者使用了高斯核,并用可学习的参数控制概率密度的分散程度。对于数据库更新场景,作者使用蓄水池抽样(reservoirsampling)应对数据插入;通过监测去除某个采样元组对估计效果的影响应对数据删除(即如果删去某个元组能提升估计效果,则将其删去)。由于计算只需要对每个采样元组计算概率再相加,故可以通过GPU加速计算。作者也在之后的研究中,将核密度估计的方法拓展到多表连接的基数估计[6]。下图展示了核密度估计的主要思想:

还有一类使用自回归模型估计基数的方法。在工作[7]中,作者提出了Naru模型,在训练过程中还融合了采样和Mask技巧,能够提升模型的准确性。作者其后也将该方法拓展到多表连接的情形[8]。

目前的困难和未来研究方向

第二点,大部分的模型都很难适应更新环境。当有大量数据插入或删除是,这些模型很难追踪这些改动,因此需要重新训练,这在OLTP环境中是需要改进的。

第三点,这些模型在多表连接的场景下估计效果仍然很差。多表连接时,不同表之间的依赖性难以捕捉,给基数估计带来了较大的困难。这在2021年实验论文[11]中也有介绍。

[1]ViktorLeis,BernhardRadke,AndreyGubichev,AlfonsKemper,andThomasNeumann.2017.CardinalityEstimationDoneRight:Index-BasedJoinSampling.InCIDR.

[2]TanuMalik,RandalCBurns,andNiteshVChawla.2007.ABlack-BoxApproachtoQueryCardinalityEstimation..InCIDR.Citeseer,56–67.

[3]AndreasKipf,ThomasKipf,BernhardRadke,ViktorLeis,PeterA.Boncz,andAlfonsKemper.2019.LearnedCardinalities:EstimatingCorrelatedJoinswithDeepLearning.In9thBiennialConferenceonInnovativeDataSystemsResearch,CIDR2019,Asilomar,CA,USA,January13-16,2019,OnlineProceedings.www.cidrdb.org.

[4]JiSunandGuoliangLi.2019.Anend-to-endlearning-basedcostestimator.ProceedingsoftheVLDBEndowment13,3(2019),307–319.

[5]MaxHeimel,MartinKiefer,andVolkerMarkl.2015.Self-tuning,GPU-acceleratedkerneldensitymodelsformultidimensionalselectivityestimation.InProceedingsofthe2015ACMSIGMODInternationalConferenceonManagementofData.1477–1492.

[6]MartinKiefer,MaxHeimel,SebastianBre,andVolkerMarkl.2017.Estimatingjoinselectivitiesusingbandwidth-optimizedkerneldensitymodels.ProceedingsoftheVLDBEndowment10,13(2017),2085–2096

[7]ZonghengYang,EricLiang,AmogKamsetty,ChenggangWu,YanDuan,XiChen,PieterAbbeel,JosephMHellerstein,SanjayKrishnan,andIonStoica.2019.Deepunsupervisedcardinalityestimation.ProceedingsoftheVLDBEndowment13,3(2019),279–292.

[8]ZonghengYang,AmogKamsetty,SifeiLuan,EricLiang,YanDuan,XiChen,andIonStoica.2020.NeuroCard:onecardinalityestimatorforalltables.ProceedingsoftheVLDBEndowment14,1(2020),61–73.

[9]BenjaminHilprecht,AndreasSchmidt,MoritzKulessa,AlejandroMolina,KristianKersting,andCarstenBinnig.2020.DeepDB:learnfromdata,notfromqueries!ProceedingsoftheVLDBEndowment13,7(2020),992–1005.

[10]RongZhu,ZiniuWu,YuxingHan,KaiZeng,AndreasPfadler,ZhengpingQian,JingrenZhou,andBinCui.2021.FLAT:fast,lightweightandaccuratemethodforcardinalityestimation.ProceedingsoftheVLDBEndowment14,9(2021),1489–1502.

[11]Wang,Xiaoying,etal."Arewereadyforlearnedcardinalityestimation."ProceedingsoftheVLDBEndowment14.9(2021):1640-1654.

THE END
1.机器学习:开启智能未来的钥匙腾讯云开发者社区一、机器学习概述 机器学习作为人工智能的核心方法,通过分析数据中的隐藏规律,让计算机从中获取新的经验和知识,不断提升和改善自身性能,从而像人一样根据所学知识做出决策。 机器学习涉及概率论、统计学、微积分、代数学、算法复杂度理论等多门学科,是一门多领域交叉学科。其应用范围极为广泛,涵盖自然语言处理、图像识https://cloud.tencent.com/developer/article/2478495
2.机器学习中的在线学习与离线学习离线训练是什么意思离线学习:一个batch训练完才更新权重,这样的话要求所有的数据必须在每一个训练操作中(batch中)都是可用的,个人理解,这样不会因为偶然的错误把网络带向极端。 这种理解方式在国外论文中出现比较多,国外称为online and batch learning.离线就是对应batch learning.这两种方式各有优点,在线学习比较快,但是有比较高的残差https://blog.csdn.net/a493823882/article/details/83240496
3.在线学习(Onlinelearning)在线学习(Online learning) 在线学习算法,获取连续的数据,当我们训练完后,便丢弃了,不再使用。 点击率CTR(Click through rate): 和随机梯度下降算法很像,只不过这里没有固定的训练集。https://www.jianshu.com/p/0e70dce74b39
4.在线深度学习mob64ca12d6c78e的技术博客在现代机器学习领域,深度学习作为一种强大的方法论,已经被广泛应用于计算机视觉、自然语言处理、语音识别等众多领域。而在线深度学习是一种新兴的研究方向,它使得模型可以在不断变换的数据环境中进行实时学习。本文将探讨在线深度学习的基本概念、应用场景以及提供一个简单的代码示例来展示如何实现在线深度学习。 https://blog.51cto.com/u_16213326/11689672
5.一步一步教你在线免费训练机器学习模型(启用GPU和TPU)关于Kgle、colab和机器学习的其他资源跟随Siraj Raval和Yufeng G. 由于我无法在这篇文章中涵盖所有在线训练机器学习模型的服务,因此本文将有第二部分。 所有需要学习和实践机器学习的资源都是开源的,可在线获取。从计算、数据集、算法以及免费在线提供的各种高质量教程,你只需要互联网连接和学习的热情。 https://blog.itpub.net/31545819/viewspace-2216969/
6.在文本分析中的应用01深度学习与传统机器学习的不同深度学习在这方面就做得特别好,它能够从原始的数据当中能够实现这种特征的各种结果,它通过pre-training就可以将数据里面的特征自动提取出来,再直接基于原始的数据,就能训练出一个模型,而且它的效果相比传统的机器学习甚至有显著的改善,这就是为什么说深度学习在这些年得到了这么火热的欢迎,以及在工业界得到了大量的使用https://www.ximalaya.com/sound/79094645
7.20232023-2024在线学习课堂网课《机器学习》单元测试考核答案.pdf 13页内容提供方:1sda321 大小:338.2 KB 字数:约9.61千字 发布时间:2023-06-10发布于贵州 浏览人气:242 下载次数:仅上传者可见 收藏次数:0 需要金币:*** 金币 (10金币=人民币1元)https://m.book118.com/html/2023/0608/6113132015005142.shtm
8.土木学院主办“机器学习与大数据在岩土力学与岩土工程中应用新?2022年1月8日,由重庆大学土木工程学院主办,山地城镇建设与新技术教育部重点实验室、国际土力学及岩土工程协会(ISSMGE)TC303、TC309专委会以及中国土木工程学会土力学及岩土工程学会承办的“机器学习与大数据在岩土力学与岩土工程中的新进展”学术研讨会于线上顺利开展。 https://news.cqu.edu.cn/archives/news2/content/2022/01/10/83dad05ffb4d8d8d812965dde7b0c74c5350c09a.html
9.机器学习初步南京大学?机器学习(Machine Learning)是人工智能的核心研究领域之一,并取得了广泛的应用效果,是引领这一轮“人工智能热潮”的关键技术支撑。《机器学习初步》课程覆盖机器学习的入门基石内容,课程主讲人周志华教授是领域内学者,所著《机器学习》(网友昵称为“西瓜书”)正是本课程的教材。本课程的教学目标是使学生对机器学习有https://www.xuetangx.com/course/nju0802bt/14363483&wd=&eqid=e751ab060004056400000003647fed08
10.教程:在PowerBI中生成机器学习模型按照本教程操作,可以了解如何在 Power BI 中生成和使用机器学习模型。https://docs.microsoft.com/zh-cn/power-bi/service-tutorial-build-machine-learning-model
11.机器学习方法在数字芯片设计中的应用电子创新网Imgtec社区随着深度学习的概念深入人心,相比于传统方法,机器学习(ML, Machine learning)的方法对于处理NP-complete问题提供了一整套新的解决方案。芯片设计过程可以看成不断的伴随着从一个step到另外一个step的抽象化任务模型建模的过程,其方法论在半导体发展的过程中不断的完善,汇集了种类繁多的各种抽象化模型任务,几乎可以包含所https://imgtec.eetrend.com/blog/2022/100565005.html
12.机器学习在肉类微生物安全中的应用研究进展机器学习方法可以从海量、复杂的数据中提取关键信息,学习数据集中各变量间的隐藏关系,现已逐渐成为食品安全领域数据密集型分析任务的强有力工具。 本文通过归纳近年来国内外相关研究,总结了机器学习方法在肉品中有害微生物的检测和预测建模中所起到的关键作用,分析了该法在实际应用时的不足之处,并展望了该法在肉类https://www.rlyj.net.cn/fileup/HTML/2022-36-11-006.shtml
13.「机器学习」机器学习在计量经济学中的运用「机器学习」机器学习在计量经济学中的运用,伴随着电子信息技术的发展趋势,机器学习技术性广泛运用于工业领域各行各业。传统计量经济学与机器学习拥有 一同的理论基础和同样的研究思路,另外从科学研究方法与目地,对模型的规定、模型检测方法都拥有 显著的差别。针对传统计量经济学存有众多不够,比如基础理论假定过强、样https://www.dtstack.com/news/7620
14.七月在线具身智能机器人复现实战营 [复现实战UMI/DexCap] 免费试听 录播 实训 答疑结合,且每天答疑 机器学习集训营19 [双11期间2799¥秒杀,24年最新一期新增大模型] 免费试听 随到随学,项目代码课件答疑一应俱全 CV高级小班 第12期 [最好CV课程,一次报名 服务三年] http://julyedu.com/
15.文本分析及机器学习在影视传媒中的应用——以电视剧《狂飙》为例可见,将《狂飙》作为研究对象,可以很好的探究“顶流热剧”何以生成与建构,溯源其“走红”内在肌理、必备要素与发生机制,为今后的影视剧创作具有重要的借鉴意义。本文以豆瓣网为数据库,通过Python工具对《狂飙》豆瓣网长评进行数据抓取,利用文本分析与机器学习的技术,从观众回馈角度使用定量方法对《狂飙》http://ex.chinadaily.com.cn/exchange/partners/82/rss/channel/cn/columns/snl9a7/stories/WS64be1db0a3109d7585e4635f.html
16.谭庆收(博士)1.国家自然科学基金面上项目,噪声环境中机器学习辅助的量子计量学 研究,批准号:12275077,2023年1月至2026年12月。 2.国家自然科学基金青年项目,超冷原子腔光机械系统中的量子效应及 应用,批准号:11805047,2019年1月至2021年12月。 3.国家自然科学基金地区项目,玻色-爱因斯坦凝聚体中偶极-偶极与三 https://wdxy.hnist.cn/info/1102/4517.htm