并行查询下查询执行计划的选择

doi:10.11772/j.issn.1001-9081.2019101762

《计算机应用》唯一官方网站 ›› 2020, Vol. 40 ›› Issue (2): 420-425.DOI: 10.11772/j.issn.1001-9081.2019101762

• 第36届CCF中国数据库学术会议(NDBC 2019) • 上一篇下一篇

并行查询下查询执行计划的选择

裴泽锋, 牛保宁(), 张锦文, Muhammad Amjad

太原理工大学信息与计算机学院，太原 030024

收稿日期:2019-09-18 修回日期:2019-10-03 接受日期:2019-10-24 发布日期:2019-10-31 出版日期:2020-02-10
通讯作者: 牛保宁
作者简介:裴泽锋（1995—），男，山西兴县人，硕士研究生，CCF会员，主要研究方向：数据库管理及优化
张锦文（1988—），男，山西阳泉人，博士，CCF会员，主要研究方向：数据库系统的性能管理
Amjad Muhammad（1978—），男，巴基斯坦人，博士，CCF会员，主要研究方向：数据库查询性能预测。
基金资助:
国家自然科学基金资助项目(61572345)

Query execution plan selection under concurrent query

Zefeng PEI, Baoning NIU(), Jinwen ZHANG, Muhammad AMJAD

College of Information and Computer，Taiyuan University of Technology，Taiyuan Shanxi 030024，China

Received:2019-09-18 Revised:2019-10-03 Accepted:2019-10-24 Online:2019-10-31 Published:2020-02-10
Contact: Baoning NIU
About author:PEI Zefeng， born in 1995， M. S. candidate. His research interests include database management and optimization.
ZHANG Jinwen， born in 1988， Ph. D. His research interests include database system performance management.
AMJAD Muhammad， born in 1978， Ph. D. His research interests include database query performance prediction.
Supported by:
the National Natural Science Foundation of China(61572345)

摘要/Abstract

摘要：

查询是数据库系统的主要负载，其效率决定了数据库性能的好坏。一个查询存在多种执行计划，当前，查询优化器只能按照数据库系统的配置参数，静态地为查询选择一个较优的执行计划。并行查询间存在复杂多变的资源争用，很难通过配置参数准确反映，而且同一执行计划在不同情景下的效率并不一致。并行查询下执行计划的选择需考虑查询间的相互影响——查询交互。基于此，提出了一种在并行查询下度量查询受查询交互影响大小的标准QIs。针对并行查询下查询执行计划的选择，还提出了一种动态地为查询选择执行计划的方法TRating，该方法通过比较查询组合中按不同执行计划执行的查询受查询交互影响的大小，选择受查询交互影响较小的执行计划作为该查询的较优执行计划。实验结果表明，TRating方法为查询选择较优执行计划的准确率达61%，相比查询优化器提高了25%；而且在为查询选择次优执行计划时，其准确率也高达69%。

关键词: 并行查询, 查询交互, 查询优化器, 查询执行计划, 较优执行计划

Abstract:

Query is the main workload of a database system， and its efficiency determines the performance of the database system. There are multiple execution plans for a query， and the existing query optimizers can only statically select a better execution plan for a query according to the configuration parameters of the database system. There are complex and variable resource contentions between concurrent queries， and such contentions are difficult to be reflected accurately through configuration parameters； besides， the efficiency of the same execution plan is not consistent in different scenarios. The selection of the execution plans for concurrent queries needs to consider the influence between queries — query interaction. Based on the above， a metric for measuring the influence of query interaction on the query under concurrent query called QIs （Query Interactions） was proposed. For the selection of query execution plan under concurrent query， a method called TRating （Time Rating） was proposed to dynamically select the execution plan for the query. In the method， the influence of query interaction on the queries executed with different plans in the query combination was measured， and the plan with small influence of query interaction was selected as the better execution plan for the query. Experimental results show that TRating can select a better execution plan for the query with an accuracy of 61%， which is 25% higher than that of the query optimizer； and the accuracy of the proposed method is as high as 69% when selecting suboptimal execution plan for the query.

Key words: concurrent query, query interaction, query optimizer, query execution plan, better execution plan

中图分类号:

TP392

裴泽锋, 牛保宁, 张锦文, Muhammad Amjad. 并行查询下查询执行计划的选择[J]. 计算机应用, 2020, 40(2): 420-425.

Zefeng PEI, Baoning NIU, Jinwen ZHANG, Muhammad AMJAD. Query execution plan selection under concurrent query[J]. Journal of Computer Applications, 2020, 40(2): 420-425.

图/表 9

表1 相关符号定义

Tab. 1 Definition of related symbols

符号	释义
$q i$	查询 $q i$ ，编号i
$q i_j$	查询 $q i$ 的执行计划 $q i_j$ ，编号j
$D = q i_j / q n_m i ≠ n$	按特定执行计划 $q i_j$ 执行的查询 $q i$ 和按特定执行计划 $q n_m$ 执行的查询 $q n$ 并行查询组合
$f q i_j / q n_m$	$q i_j / n_m$ 查询组合的编号f
$A = q i i = 1,2, …, n$	数据库中的所有查询的集合，共n个查询
$B = q i_j j = 1,2, …, m$	查询 $q i$ 的执行计划的集合，共m个
$C = q i_j / q n_m q i, q j ∈ A, q i_j, q n_m ∈ B, i ≠ n$	查询组合的集合
$γ q i_j / q n_m$	按特定执行计划 $q i_j$ 执行的查询 $q i$ 和按特定执行计划 $q n_m$ 执行的查询 $q n$ 并行时查询 $q i$ 的QueryRating值
$k γ q i_j / q n_m$	$γ q i_j / q n_m$ 的编号k

表1 相关符号定义

Tab. 1 Definition of related symbols

符号	释义
$q i$	查询 $q i$ ，编号i
$q i_j$	查询 $q i$ 的执行计划 $q i_j$ ，编号j
$D = q i_j / q n_m i ≠ n$	按特定执行计划 $q i_j$ 执行的查询 $q i$ 和按特定执行计划 $q n_m$ 执行的查询 $q n$ 并行查询组合
$f q i_j / q n_m$	$q i_j / n_m$ 查询组合的编号f
$A = q i i = 1,2, …, n$	数据库中的所有查询的集合，共n个查询
$B = q i_j j = 1,2, …, m$	查询 $q i$ 的执行计划的集合，共m个
$C = q i_j / q n_m q i, q j ∈ A, q i_j, q n_m ∈ B, i ≠ n$	查询组合的集合
$γ q i_j / q n_m$	按特定执行计划 $q i_j$ 执行的查询 $q i$ 和按特定执行计划 $q n_m$ 执行的查询 $q n$ 并行时查询 $q i$ 的QueryRating值
$k γ q i_j / q n_m$	$γ q i_j / q n_m$ 的编号k

表2 索引表IT1

Tab. 2 Index table IT1

查询编号	执行计划编号
i	j

表3 索引表IT2

Tab. 3 Index table IT2

查询组合编号	$γ q i_j / q n_m$ 编号	$γ q n_m / q i_j$ 编号
f	k₁	k₂

表3 索引表IT2

Tab. 3 Index table IT2

查询组合编号	$γ q i_j / q n_m$ 编号	$γ q n_m / q i_j$ 编号
f	k₁	k₂

表4 实验环境配置

Tab. 4 Experimental environment configuration

实验配置	参数说明
硬件环境	Server1： CPU：Inter Xeon CPU E3-1225 V2 @3.2 GHz RAM：8 GB Server2： CPU： Intel Xeon CPU E5-2609 v4 @1.70 GHz Mem：16 GB
操作系统	Windows 2008 Server CentOS Linux release 7.4.1708 （Core）
数据库	PostgreSQL（缓冲池配置：2 000 MB）
编程语言	Java
测试基准	TPC-H（10 GB）

图1 默认执行计划

Fig. 1 Default execution plan

图2 关闭MergeJoin后的执行计划

Fig. 2 Excution plan after closing MergeJoin

图3 关闭nestloop后MPL=4时，同一查询加入不同的查询组合时的较优执行计划抽样

Fig. 3 Sampling of better execution plan of one query adding to different query combinations with nestloop closed and MPL=4

表5 TRating和查询优化器准确率对比

Tab. 5 Accuracy comparison between TRating and query optimizer

MPL	选择准确率		变化幅度
MPL	优化器	TRating	变化幅度
2	0.64	0.92	0.28
4	0.36	0.67	0.31
6	0.27	0.48	0.21
8	0.16	0.36	0.20

表6 TRating选择次优执行计划准确率

Tab. 6 TRating accuracy for suboptimal execution plan selection

MPL	TRating选择准确率	MPL	TRating选择准确率
2	0.97	6	0.61
4	0.73	8	0.46

参考文献 17

1	孙振兴，向阳，刘增宝. PostgreSQL 查询优化器分析研究［J］. 计算机技术与发展， 2011， 21（8）： 141-144. 10.3969/j.issn.1673-629X.2011.08.036
	SUN Z X， XIANG Y， LIU Z B， Analysis and research on optimizer of PostgreSQL［J］. Computer Technology and Development， 2011， 21（8）： 141-144. 10.3969/j.issn.1673-629X.2011.08.036
2	谷伟，陈莲君.基于MySql的查询优化技术研究［J］.微型电脑应用，2013，30（7）：48-50. 10.3969/j.issn.1007-757X.2013.07.015
	GU W， CHEN L J. Research on the query optimize technology of MySql［J］. Microcomputer Applications， 2013， 30（7）： 48-50. 10.3969/j.issn.1007-757X.2013.07.015
3	刘维学.SQL Server 查询优化器原理与优化实例分析［J］.计算机技术与发展，2013，23（11）： 108-111. 10.3969/j.issn.1673-629X.2013.11.027
	LIU W X. Query optimization principle and optimized instance analysis of SQL Server［J］. Computer Technology and Development， 2013， 23（11）： 108-111. 10.3969/j.issn.1673-629X.2013.11.027
4	LI J， NEHME R V， NAUGHTON J. GSLPI： a cost-based query progress indicator［C］// Proceedings of the IEEE 28th International Conference on Data Engineering. Piscataway： IEEE， 2012： 678-689. 10.1109/icde.2012.74
5	宋晓眉，叶晓俊，曾小青，等.PostgreSQL查询优化中的等价类研究与改进［J］.计算机工程与应用，2014，50（14）：31-38. 10.3778/j.issn.1002-8331.1310-0286
	SONG X M， YE X J， ZENG X Q， et al. Study and improvement on equivalence classes of PostgreSQL query optimization［J］. Computer Engineering and Applications， 2014， 50（14）： 31-38. 10.3778/j.issn.1002-8331.1310-0286
6	CHAUDHURI S， KAUSHIK R， RAMAMURTHY R. When can we trust progress estimators for SQL queries？［C］// Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2005： 575-586. 10.1145/1066157.1066223
7	MARKL V G， HAAS P J， ABOULNAGA A I， et al. System and method for updating database statistics according to query feedback： US7831592B2［P］. 2010-11-09. 10.1016/b978-012088469-8/50142-x
8	AHMAD M， ABOULNAGA A， BABU S， et al. Modeling and exploiting query interactions in database systems［C］// Proceedings of the 17th ACM Conference on Information and Knowledge Management. New York： ACM， 2008： 183-192. 10.1145/1458082.1458109
9	WEISSMAN C， MOELLENHOFF D， WONG S， et al. Query optimization in a multi-tenant database system： US7529728B2［P］. 2009-05-05.
10	EWEN S E， KACHE H， MARKL V G， et al. Progressive refinement of a federated query plan during query execution： US7877381B2［P］. 2011-01-25. 10.1007/11687238_50
11	SIMON E， LLIRBAT F， FABRET F， et al. Query plan reformulation： US 8688683B2［P］. 2014-04-01. 10.1145/253262.253357
12	WU W， WU X， HACIGÜMÜŞ H， et al. Uncertainty aware query execution time prediction［J］. Proceedings of the VLDB Endowment， 2014， 7（14）： 1857-1868. 10.14778/2733085.2733092
13	AHMAD M， ABOULNAGA A， BABU S， et al. Interaction-aware scheduling of report-generation workloads［J］. The VLDB Journal， 2011， 20（4）： 589-615. 10.1007/s00778-011-0217-y
14	DUGGAN J， CETINTEMEL U， PAPAEMMANOUIL O， et al. Performance prediction for concurrent database workloads［C］// Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. New York： ACM， 2011： 337-348. 10.1145/1989323.1989359
15	ZHANG J， NIU B. A clustering-based sampling method for building query response time models［J］. Computer Systems Science and Engineering， 2017， 32（4）： 319-331.
16	张锦文，牛保宁，李爱萍.查询交互响应时间预测模型的采样优化［J］.小型微型计算机系统，2015，36（10）： 2240-2244. 10.3969/j.issn.1000-1220.2015.10.012
	ZHANG J W， NIU B N， LI A P. An optimized sampling method for query interaction aware respond time modeling［J］. Journal of Chinese Computer Systems， 2015， 36（10）： 2240-2244. 10.3969/j.issn.1000-1220.2015.10.012
17	Wiki PostgreSQL. TP-C［EB/OL］. ［2018-09-20］..

[1]	林基明, 班文娇, 王俊义, 童记超. 基于并行遗传最大最小蚁群算法的分布式数据库查询优化[J]. 计算机应用, 2016, 36(3): 675-680.
[2]	魏莉杨科华. 基于语义分解的联机分析处理查询并行优化方案[J]. 计算机应用, 2010, 30(07): 1956-1958.

并行查询下查询执行计划的选择

Query execution plan selection under concurrent query

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 17

相关文章 2

编辑推荐

Metrics