毕加索数据库最优化查询观察系统.doc

毕加索数据库最优化查询观察系统
1. 介绍
现在数据库系统采用最优化查询模型去自动识别最有效的策略来执行由用户提交的申明的SQL查询语句。这种有效的策略称为‘计划’，估测了关于查询回应的次数的‘消耗’。最优化是一种在不同的最优的执行计划的花费和一个随即选择中强制运行，可能是根据重要性的排序来运行。最优化查询的作用已成为尤其的重要在当今因为高密度的处理性高复杂有特征的现代数据库和挖掘运用，就像TPC-H和TPC-DS决定支持基准[20,21]。

通过过去5年的课程，我们已开发一款可视化工具，称为毕加索[22]，可以通过图表描述分析数据库最优化查询的运转状态。此工具是运行在一个巨型工业强度的最优化设置上，包括IBM DB2[15],Microsoft SQL Server[16], Oracal[17]，Sybase ASE[18]和PostgreSQL[19]。当今可免费下载的毕加索被全球的领先工业和学术研究所所用。它被用来作为
·优化查询分析、查错和重新设计辅助可以被系统开发者来使用；
·开发的优化查询测试床可以被数据库研究者来使用；
·优化查询教育学支持可以被指导者和学生来使用；

科学支持的毕加索工具早期已出现在一系列最近的VLDB论文中[12,7,8,6,1]。在样本中，
我们将第一次呈现初排的毕加索工具，和解释它怎么提供强有力的可视的界面去详细地探究优化查询现代数据库中有趣的世界。我们还会展示此工具怎么有效的决定在最优化计划选择上的改进--例如去确定‘健全计划’，这个计划是限制选择性的评估错误在查询库的关系上。
最后我们将说明这些概念是怎样有重要的作用为下一代的优化查询设计。

允许个人或班级利用此作品的部分或全部的打印件或多媒体但是保证没有任何付费，附件不能用来商业或盈利。这段文字和引用在第一页。以其他方式复制或再版,发表收费或重新分发目录或收费。这卷的文章由在大型数据库第36国际会议，2010年9月13-17日在新加坡发表。
由VLDB Endowment发行第3卷NO2
2010 VLDB Endowment版权

毕加索图表
给一个被参数化的SQL查询样式其中定义了一个可以选择的空间，和一个数据库引擎的选择，毕加索工具自动生成多样化的以通过这空间描述引擎最优化的行为的图表。例如：被称作“计划图表”[12]，表现计划选择的多彩的以图画表示的列举由通过选择的空间的优化器。
特别地，计划图表可视地捕捉POSP最优性地域，计划的参数最优设置。

为了是这些概念，QT8作为考虑的范围，参数2D查询样式展示在图表2中，以TPCH的查询8为标准。在这里，在SUPPLIER和LINEITEM联系上的可查询性的多样性通过S_acctbal是特别的：各自的多样性和L_拓展价格：不同的谓语。

select o year, sum(case when nation = ’BRAZIL’ then volume else 0
end) / sum(volume) as mkt share
from (select YEAR(o orderdate) as o year, l extendedprice * (1 -
l discount) as volume, n2.n name as nation
from part, supplier, lineitem, orders, customer,
nation n1, nation n2, region
where p partkey = l partkey and s suppkey = l suppkey
and l orderkey = o orderkey and o custkey = c custkey
and c nationkey = n1.n nationkey and n1.n regionkey =
r regionkey and s nationkey = n2.n nationkey and r name
= ’AMERICA’ and p type = ’ECONOMY ANODIZED
STEEL’ and
s acctbal :varies and l extendedprice :varies
) as all nations
group by o year
order by o year

图表1 查询样式列子（QT8）

QT8相联系的计划图表被展示在图表2中，由毕加索系统在一个流行商业数据库引擎绘制出。在这个图画中，每个颜色的区域代表一个特别的计划，和89种不同最优化设置，P1到P89，
涵盖了可查询空间。在图列中每个计划相联系的价值代表在图表中被那计划所覆盖的百分比区域。例如，在P1最大的区域覆盖了22%，但是最小的P89只占了0.001%。

汇编——时间 图表

全套的图表被毕加索工具所制作被列举在图表1中。它包括几个汇编-时间被优化器选择计划质的和量的图表计划。例如，关于量的价格图表表述了查询进度花费的估计被展示在相关联的计划图表中，基数性图表展示了基数定性的结果。这个图表可以被快速的移动到个人的方位下去决定在这些位置下执行树的计划（计划的执行树图表），附有选择的被注释的代价和基数性树节点(编译的计划树图表)。结构性在被给计划不同之间可以被定义通过计划不同图表，与最显著不同点在颜色代码结构中。

毕加索也支持与那些其他引擎在同一位置最优计划选择的比较，或者由同一引擎不同最优化级别的比较（外键计划树图表）。就像IBM开发器注重在一个特别的查询例子上，可以可视地确定和比较与那些如SQLSERVER或ORACLE其他引擎DB2对于查询的计划选择。最终，最新版本的几个优化器在它们的API中都包含了一个外键树代价计算（FPC）特性，代价计算计划是不同于本生的优化地域的（就像在DB2中的优化文件夹，在SQLSEVERE中的XML 计划和在SYBASE ASE中的抽象计划。这FPC特征被毕加索所用在整个可查询的空间去可视表现出代价行为的指定的计划的特征（抽象计划图表）。

代替计划图表：也许是毕加索最吸引人的方面，它支持计划代替图表的构建。这里查询样式的起初计划/代价图表被输入资料所取代，新的计划图表被构建，在其中最优化的起初选择的子集被从POSP集可代替计划所代替。此代替被得出在预料中，这些预料将执行更好比起原始的选择（减少图表和健全计划图表）。对于这些替代图表执行，和他们的构建技术将被详细地讨论在第五部分。

运行时图表：最终除了上述的编译时间图表，毕加索也生成运行时图表，此表可视地描述真实的查询执行行为，关于执行时间和基数性结果，在现在的数据库平台上（执行代价和执行基数性表）。与预期的和现在的图表相比较帮助理解和勾画立体感质量的优化器。

汇编——时间图表
计划图表
以图例表示的枚举的优化器的执行计划选择在可查询的空间中。
代价图表
可视的相关联的估计计划执行代价在可查询的控件
基数性图表
可视的相关联的估计查询结果基数性在可查询的控件
图解计划树图表
在计划图表中树状可视的选择计划
不同计划图表
出现在计划图表中一个可查询部分的计划之中的图解的不同的显著点
编译计划树图表
在计划图表中特别位置可视树的选择计划，对代价和基数性信息做注释
外键计划树图表
由数据库引擎制造在一个计划图表中被给的区域，在这区域被另一个引擎生成可视树的计划（或同一个数据库不同的最优化等级）。
抽象计划图表
在计划图表中一可视的估计的行为的可查询的计划，此特殊计划被用通过可查询空间。

计划代替图表
减少计划图表
展示了原始图表可能被简化的程度（通过代替一些在计划图表中同族的计划）不增加个人查询的花费通过多个特别用户端口值。
健全计划图表
展示了原始图表可能被简化的程度被相比健全计划不增加个人查询的花费通过多个特别用户端口值。

运行时图表
执行代价图表
可视的运行时查询回应次数通过可查询空间。
执行基数性图表
可视的运行时查询得出基数性结果通过可查询空间。

（a）计划图表

（B）降低图表 (Threshold  = 10%)

Figure 3 毕加索结构
3. 图表制作
图解布局的毕加索系统由图表3展示。计划图表的制作策略采纳是遵循：毕加索工具通过d-维的查询样式和r图解析生成rd查询，此查询通过可查询空间根据用户的需求可以采用统一或幂数分配。然后，基于相联系的可查询的价值，对于这些每个查询的位置，一个查询伴随着实例化地适当的恒量--这个恒量从优化器在统计中可得的同数据库被决定，一般以柱状图的形式呈现。这个查询然后被提交到查询优化器去被“解释”，用最理想的计划去计算和返回值。
相对应的所有查询点的计划被得到后，每个唯一的计划与不同的颜色相关联。然后，其余的图表由颜色相对应的计划的每个点周围的带色的区域的上色。例如：在一个带有一个唯一10格子的决策的2D计划图表中，有100个真正的查询点，在每个点周围有10*10维平方被计划颜色相联系的点着色。
计划图表被构建的同时，通过由“解释计划”输出定量信息（估计）花费和基数性图表也被创建。这些图表与POSP相对应的执行树一直存储在数据库便利了图表的再用。另外，统计的估计器已被配置去提供给使用者附有图表制作次数的预测。
毕加索工具被完全地写在Java和 现在的运行时中带有100多个类 5K行代码。JAVA3D,VISAD,SWING和JGRAPH库被用作可视化目的，通过JDBC数据连接。第一代的数据库被发放在2007年，随后2009发行了2代。通过2代，用户可以通过限制图表的制作去请求第二可查询空间区域--例如：起初，高易变性在优化器计划的选择上以被基本克服。
另一个2代特征是近似计划图表的引进。此行为是在上面所表述的所有图表的制作方法是部分地只有为那些低维查询样式（1D和2D）和略劣决策（最多每维100点）的图表。然而，它成为出奇的耗资源对那些高维的高密度的决策由于在传输过程中的幂数的增长。举个例子，一个带有每维1000决策的2D计划图表，或带有每维100决策的3D计划图表都需要优化器执行1百万次。即使一个保守估计每0.5秒优化总共的时间制作这个全部的图表需要1周！
计算的消耗的问题在毕加索中被关注通过合作的强大的样本和互相作用库近似技术[6]。 这技术发送的图表接近90%的正确性，只有大约10%消耗由无规则排序方法产生。

4.计划图表的运用
从图表2可以证明，计划图表可以把在一个空间的许多计划被惊人地混合和加密——几个例子在现代的优化器作为一个可用的代表性的参考标注的查询样式[22]。实际上，毕加索工具的名字起源于计划图表相似于“立体作图”。
我们与产业发展团队的交互说明毕加索计划图表已证明了流行的保守智慧是相反的。原因是在个体查询上优化器行为已被开发者很大程度地分析了，计划图表提供了在整个空间上完全的不同的观测行为，生动的捕捉了计划传输的障碍和可视化几何学。因此，在刻板的环境下，他们传送了一个生动图片。
计划图表现在被运用在各个行业和学术领域为了让驱动程序的运用包括分析现在的优化器设计，可视地得出优化器的复原测试，找出新查询进程特征的错误，比较各代优化器的行为；分析相邻计划空间的结构的不同点；选取最优的由比较优化器计划选择中的不同性等等。由于整个特性，在商务的优化器中可视例子的无单一计消耗行为，模型错误的表现是亮点[12]。
除了帮助优化器的设计，计划图表也可以被用作执行设置。尤其，当它们确立了在编译时间中对于整个相关的可查询空间中最优化设置计划，它们可以被用在运行时中去立即确定最好的计划对现在的查询无需通过花费时间对最优化测试。而且，它们可以证明对适应计划查询有用的技术（查考[5]最近的调查）此技术是基于运行时的观察，可以动态地选择去重新优化查询和去开启计划中路通过处理。在此文中，计划图表可以帮助去减少重新优化的发生在决定替换计划选择前。
5.计划代替图表
正如早期提及的，除了可视地数据优化行为，毕加索也与机械装置合作为了改进优化器的计划通过“减少计划图表和”和“健全计划图表”，以下表述的。

5.1较少计划图表
考虑到高密度的原始计划图表和由用户指定的消耗增长线程。我们的减少规则系统重新在密度图表上了更简单的图片，只有对期初计划为特征——以至于一些期初的计划被完全的吞没掉被他们的子树。最重要地，重新上色进程保证了任何重新上色查询点的消耗不能被更多的く比例增加，有关于它的的期初消耗。
已被经验地展示在是否愿意忍受低消耗的最多く=20%增长，所有计划在最终的减少图表中经常被降低到或在10之内。简而简之，复杂的计划图表可能被制成‘患上厌食症的人’当维持查询的进程行为。举例，QT8计划图表（图表2（a））可以被减少在く=10%的图表被显示在2（b）,原始的89个计划只有7计划被维持下来。
厌食症计划图表减少由十分重要的实际利益，被消息表述在[7],包括大量的计划搜寻空间，加强参量查询优化器技术运用性[9,10]，确立了错误限制和最少预期消耗计划[3,4],使多计划的方法的消耗最小化[2，11]。
5.2健全计划图表
制成附有く保证减少计划图表的暗示是可查询空间中优化器的编译时间估计的查询位置在是精确的。然而，实际上，这些可查询的估计在查询执行期间关于遭遇运行时价值时发生的错误是严重的。这些可以在真实数据库环境中有级别次序的错误被引起由于各种各样的原因，包括过时的数据，没有以假定和粗率统计为依据的属性值。
由上结论可以得出，由减少计划图表和在く线程内的估计查询方位暗示的替代品可能是属性或好或坏的在出现可查询估计错误的替代品。因此，我们理想化地想只容许那些保证促进查询进程的程序或者没有任何负面影响的替代品，无论次替代品在运行时中实际的查询在哪里。使我们足够惊奇地是，有效识别那些优化器支持的外计划消耗特征（见[8]中描述）的替代品是有可能的。此被实施在毕加索中可以确信可改进的全球的安全的替代品，并且不会损害查询进程程序。更好地是，我们实验上的结果说明了巨大的进步是可得的，在健全计划中的有效结果。有趣的是，健全计划图表大体上维持了减少计划的厌食症特征。因此,表面上，我们的结论在工业为主的数据库设定档案计划的安全，健全，厌食症并存是确实有可能的。
最后一步，我们最近在[1]中的展示，在计划图表上那些已用的进程方法怎么可以被国际化到在线查询优化器进程中，导致从本质上改进分发计划选择优化器。这是十分值得的那些令人向往的结果被得到尽管在线进程缺少全球性可得线下运算法则行为信息。
6. 示范组织
在毕加索工具的示范中，我们将在表1中呈现完全的优化器图表配置，突出复杂的计划图表。然后我们将展示厌食症和健全计划替代图表是怎么从这些密集型图表中生成的。最终，我们将展示在查询优化器中心的对于国际化的概念结构。全部演示将被在流行的工业化优化器上展示，采用不同的基于TPC-H和TPC-DS的标准中的查询样式。

答谢
毕加索工具通过在毕加索网站上列出的学生的努力已被安装在印度科学装置上,Bangalore。这项工作被印度政府科技部门支持，研究资金从google ,IBM,Microsoft和Sybase得到。

7. 参考文献
[1] M. Abhirama, S. Bhaumik, A. Dey, H. Shrimal and
J. Haritsa, “On the Stability of Plan Costs and the Costs of
Plan Stability”, Proc. of 36th Intl. Conf. on Very Large Data
Bases (VLDB), September 2010.
[2] G. Antonshenkov, “Dynamic Query Optimization in
Rdb/VMS”, Proc. of 9th IEEE Intl. Conf. on Data
Engineering (ICDE), April 1993.
[3] F. Chu, J. Halpern and P. Seshadri, “Least Expected Cost
Query Optimization: An Exercise in Utility”, Proc. of ACM
Symp. on Principles of Database Systms (PODS), May 1999.
[4] F. Chu, J. Halpern and J. Gehrke, “Least Expected Cost
Query Optimization: What Can We Expect”, Proc. of ACM
Symp. on Principles of Database Systems (PODS), May
2002.
[5] A. Deshpande, Z. Ives and V. Raman, “Adaptive Query
Processing”, Foundations and Trends in Databases, Now
Publishers, 1(1), 2007.
[6] A. Dey, S. Bhaumik, Harish D. and J. Haritsa, “Efficient
Generation of Approximate Plan Diagrams”, Proc. of 34th
Intl. Conf. on Very Large Data Bases (VLDB), August 2008.
[7] Harish D., P. Darera and J. Haritsa, “On the Production of
Anorexic Plan Diagrams”, Proc. of 33th Intl. Conf. on Very
Large Data Bases (VLDB), September 2007.
[8] Harish D., P. Darera and J. Haritsa, “Robust Plans through
Plan Diagram Reduction”, Proc. of 34th Intl. Conf. on Very
Large Data Bases (VLDB), August 2008.
[9] A. Hulgeri and S. Sudarshan, “Parametric Query
Optimization for Linear and Piecewise Linear Cost
Functions”, Proc. of 28th Intl. Conf. on Very Large Data
Bases (VLDB), August 2002.
[10] A. Hulgeri and S. Sudarshan, “AniPQO: Almost
Non-intrusive Parametric Query Optimization for Nonlinear
Cost Functions”, Proc. of 29th Intl. Conf. on Very Large
Data Bases (VLDB), August 2003.
[11] N. Kabra and D. DeWitt, “Efficient Mid-Query
Re-Optimization of Sub-Optimal Query Execution Plans”,
Proc. of ACM SIGMOD Intl. Conf. on Management of Data,
May 1998.
[12] N. Reddy and J. Haritsa, “Analyzing Plan Diagrams of
Database Query Optimizers”, Proc. of 31st Intl. Conf. on
Very Large Data Bases (VLDB), August 2005.
[13] M. Stillger, G. Lohman, V. Markl and M. Kandil, “LEO,
DB2’s LEarning Optimizer”, Proc. of 27th Intl. Conf. on
Very Large Data Bases (VLDB), August 2001.
[14]
[15]
[16]
[17]
database/oracle11g/
[18]
[19] www.postgresql.org
[20] www.tpc.org/tpch
[21] www.tpc.org/tpcds
[22] dsl.serc.iisc.ernet.in/projects/PICASSO/