有时候我们也需要对不止一个表的复杂查询（包含多表连接（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.