Accessing optimization with multiple indexes in TiDB

doi:10.11772/j.issn.1001-9081.2019081908

Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (2): 410-415.DOI: 10.11772/j.issn.1001-9081.2019081908

• CCF NDBC 2019 • Previous Articles Next Articles

Accessing optimization with multiple indexes in TiDB

Hai LAN¹, Ke HAN¹, Li SHEN², Qiu CUI², Yuwei PENG¹()

^1.School of Computer Science，Wuhan University，Wuhan Hubei 610072，China
^2.PingCAP，Beijing 100096，China

Received:2019-10-18 Revised:2019-11-20 Accepted:2019-11-22 Online:2019-12-04 Published:2020-02-10
Contact: Yuwei PENG
About author:LAN Hai， born in 1993， M. S. candidate. His research interests include database system， distributed system.
HAN Ke， born in 1995， M. S. candidate. His research interests include massive parallel processing database， genealogical data management.
SHEN Li， born in 1985， M. S. His research interests include database， distributed system.
CUI Qiu， born in 1986， M. S. His research interests include distributed database.
Supported by:
the National Key Research and Development Program of China(2016YFB1000701)

TiDB的多索引访问优化

兰海¹, 韩珂¹, 申砾², 崔秋², 彭煜玮¹()

^1.武汉大学计算机学院，武汉 610072
^2.北京平凯星辰科技发展有限公司，北京 100096

通讯作者: 彭煜玮
作者简介:兰海（1993—），男，四川成都人，硕士研究生，CCF会员，主要研究方向：数据库系统、分布式系统
韩珂（1995—），男，河南南阳人，硕士研究生，主要研究方向：大规模并行处理数据库、族谱数据管理
申砾（1985—），男，河北石家庄人，硕士研究生，主要研究方向：数据库、分布式系统
崔秋（1986—），男，天津人，硕士研究生，主要研究方向：分布式数据库；
基金资助:
国家重点研发计划项目(2016YFB1000701)

Abstract

Abstract:

When the query condition involves multiple indexed attributes， TiDB cannot effectively use multiple indexes to generate a more efficient execution plan. After studying the existing solutions of databases， such as PostgreSQL and MySQL， a new type of data access path using multiple indexes simultaneously was proposed in TiDB to solve the problem， namely MultiIndexPath. Firstly， a possible access path named MultiIndexPath for a certain query was generated and its physical plan named MultiIIndexPlan was created， then the cost of this plan was calculated. Secondly， the general execution framework of MultiIndexPath was proposed after combining the architecture and implementation of TiDB. Finally， the Pipeline execution plan was proposed with the condition of conjunctive normal form. The whole work was implemented based on TiDB 3.0 and several experiments were conducted. Experimental results show that the performance of the proposed scheme is improved by at least one order of magnitude compared with the original TiDB when the condition is the disjunctive normal form. With the condition of conjunctive normal form， the performance of the scheme is also better than that of the original TiDB.

Key words: distributed database, TiDB, optimizer, index

摘要：

当查询条件涉及多个已建立索引的属性时，TiDB不能利用多个索引产生更优的执行计划。为了解决此问题，在研究现有数据库解决方案（如PostgreSQL和MySQL等）后，在TiDB中提出一种同时利用多个索引的新类型数据访问路径，称为MultiIndexPath。首先，设计算法生成一个查询可能的MultiIndexPath，并产生该路径的物理计划MultiIIndexPlan，然后计算物理计划的代价；其次，结合TiDB的架构与实现，提出MultiIndexPlan的通用执行框架；最后，当条件为合取范式时，提出Pipeline执行方案。整个工作基于TiDB 3.0实现并进行若干实验，结果表明：当条件为析取范式时，所提方案的性能比原TiDB至少有一个数量级提升；当条件为合取范式时，性能也优于原TiDB。

关键词: 分布式数据库, TiDB, 优化器, 索引

CLC Number:

TP311.132

Hai LAN, Ke HAN, Li SHEN, Qiu CUI, Yuwei PENG. Accessing optimization with multiple indexes in TiDB[J]. Journal of Computer Applications, 2020, 40(2): 410-415.

兰海, 韩珂, 申砾, 崔秋, 彭煜玮. TiDB的多索引访问优化[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 410-415.

Figures/Tables 11

Tab. 1 Mode information

对象	创建语句
表	CREATE TABLE t1（a1 int， a2 int， a3 int）；
索引	CREATE INDEX i1 ON t1（a1）；
索引	CREATE INDEX i2 ON t1（a2）；

Fig. 1 MultiIndexPlan execution framework

Tab. 2 Symbol description of cost model

标识	简称	含义
IndexTupleCost	ITC	索引元组扫描代价
NetworkCost	NC	网络传输代价
TableScanCost	TSC	数据元组扫描代价
SelectionCost	SC	过滤条件执行代价
MergeCost	MC	集合交并代价
networkFactor	nF	网络传输代价因子
scanFactor	sF	元组扫描代价因子
selectionCPUFactor	selF	过滤条件代价因子
mergeFactor	mF	集合交并代价因子
indexRowCount	iRC	所有索引元组总个数
dataRowCount	dRC	最终结果元组总个数
afterSetOPRowCount	aSC	交并操作结束后总Rowid个数
TotalCost	TC	总代价

Fig. 2 Example of MultiIndexAnd execution

Tab. 3 Example of MultiIndexPlan execution process

新Rowid	set1	set2	TableWorker
$2 (i x 1)$	［2］	［］	［］
$1 (i x 2)$	［2］	［1］	［］
$5 (i x 1)$	［2，5］	［1］	［］
$5 (i x 2)$	［2］	［1］	［5］
$7 (i x 1)$	［2，7］	［1］	［］
$2 (i x 2)$	［7］	［1］	［2］

Tab. 3 Example of MultiIndexPlan execution process

新Rowid	set1	set2	TableWorker
$2 (i x 1)$	［2］	［］	［］
$1 (i x 2)$	［2］	［1］	［］
$5 (i x 1)$	［2，5］	［1］	［］
$5 (i x 2)$	［2］	［1］	［5］
$7 (i x 1)$	［2，7］	［1］	［］
$2 (i x 2)$	［7］	［1］	［2］

Tab. 4 Description of datasets

数据集	元组数量（万）	模式描述
T200	200	3列，每列为整型
T200M	200	8列，每列为整型

Tab. 5 Statement templates of SQL

模板	SQL
DNF	SELECT * FROM T200 WHERE C1<＄1 OR C2>＄2；
CNF-1	SELECT * FROM T200M WHERE C1<＄1 AND C2>＄2；
CNF-2	SELECT * FROM T200M WHERE C1<＄1 AND C2<＄2；

Fig. 3 Test of DNF

Fig. 4 Test of CNF

Fig. 5 Test of parallelism degree of DNF

Fig. 6 Test of parallelism degree of CNF

References 15

1	崔斌，高军，童咏昕，等. 新型数据管理系统研究进展与趋势［J］. 软件学报， 2019， 30（1）：164-193. 10.13328/j.cnki.jos.005646
	CUI B， GAO J， TONG Y X， et al. Progress and trend in novel data management system［J］. Journal of Software， 2019， 30（1）：164-193. 10.13328/j.cnki.jos.005646
2	SIVASUBRAMANIAN S. Amazon dynamoDB： a seamlessly scalable non-relational database service［C］// Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2012： 729-730. 10.1145/2213836.2213945
3	GEORGE L. HBase： the definitive guide： random access to your planet-size data［M］. Sebastopol， CA： O’Reilly Media， Inc.， 2011： 1-522.
4	KEMPER A， NEUMANN T. HyPer： a hybrid OLTP&OLAP main memory database system based on virtual memory snapshots［C］// Proceedings of the IEEE 27th International Conference on Data Engineering. Piscataway： IEEE， 2011： 195-206. 10.1109/icde.2011.5767867
5	FÄRBER F， CHA S K， PRIMSCH J， et al. SAP HANA database： data management for modern business applications［J］. ACM SIGMOD Record， 2012， 40（4）： 45-51. 10.1145/2094114.2094126
6	STONEBRAKER M， WEISBERG A. The VoltDB main memory DBMS［J］. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering， 2013， 36（2）： 21-27. 10.1109/icde.2014.6816685
7	TOSHNIWAL A， TANEJA S， SHUKLA A， et al. Storm@twitter［C］// Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2014： 147-156. 10.1145/2588555.2595641
8	NOGHABI S A， PARAMASIVAM K， PAN Y， et al. Samza： stateful scalable stream processing at LinkedIn［J］. Proceedings of the VLDB Endowment， 2017， 10（12）： 1634-1645. 10.14778/3137765.3137770
9	CARBONE P， EWEN S， HARIDI S， et al. Apache flink^TM： stream and batch processing in a single engine［J］. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering， 2015， 36（4）：28-38.
10	PingCAP. PingCAP首页［EB/OL］. ［2019-03-23］.［EB/OL］. ［2019-03-23］.）. 10.1109/procomm.2019.00054
11	SHUTE J， VINGRALEK R， SAMWEL B， et al. F1： a distributed SQL database that scales［J］. Proceedings of the VLDB Endowment， 2013， 6（11）： 1068-1079. 10.14778/2536222.2536232
12	CORBETT J C， DEAN J， EPSTEIN M， et al. Spanner： Google’s globally distributed database［J］. ACM Transactions on Computer Systems， 2013， 31（3）： Article No. 8. 10.1145/2491245
13	MySQL. Index merge optimization［EB/OL］. ［2019-03-23］.. 10.1007/978-1-4302-0729-0_7
14	PostgreSQL. Combining multiple indexes［EB/OL］. ［2019-03-23］. 10.1007/978-1-4302-0136-6_35
15	PingCAP. TiDB architecture ［EB/OL］. ［2019-03-23］. . 10.1109/procomm.2019.00054

[1]	WU Yue, LUO Jiangtao, LIU Rui, HU Zhongyin. Video similarity detection method based on perceptual hashing and dicing [J]. Journal of Computer Applications, 2021, 41(7): 2070-2075.
[2]	JIA Heming, JIANG Zichao, LI Yao, SUN Kangjian. Simultaneous feature selection optimization based on improved spotted hyena optimizer algorithm [J]. Journal of Computer Applications, 2021, 41(5): 1290-1298.
[3]	YAN Aijun, WEI Zhiyuan. Weight allocation and case base maintenance method of case-based reasoning classifier [J]. Journal of Computer Applications, 2021, 41(4): 1071-1077.
[4]	XU Feixue, LIU Qinming, OUYANG Hailing, YE Chunming. Optimization of maintenance strategy model for multi-component system based on performance-based contract [J]. Journal of Computer Applications, 2021, 41(4): 1184-1191.
[5]	CUI Shuangshuang, WANG Hongzhi. Implementation method of lightweight distributed index based on log structured merge-tree [J]. Journal of Computer Applications, 2021, 41(3): 630-635.
[6]	JIANG Kun, LIU Zheng, ZHU Lei, LI Xiaoxing. Fixed word-aligned partition compression algorithm of inverted list based on directed acyclic graph [J]. Journal of Computer Applications, 2021, 41(3): 727-732.
[7]	Yubin ZHOU, Hong XIAO, Tao WANG, Wenchao JIANG, Meng XIONG, Zhongtang HE. Health index construction and remaining useful life prediction of mechanical axis based on action cycle degradation similarity measurement [J]. Journal of Computer Applications, 2021, 41(11): 3192-3199.
[8]	Xiaoling SUN, Guang YANG, Yanping SHEN, Qiuge YANG, Tao CHEN. Searchable encryption scheme based on splittable inverted index [J]. Journal of Computer Applications, 2021, 41(11): 3288-3294.
[9]	HAO Pengfei, CHI Rui, QU Zhijian, TU Hongbin, CHI Xuexin, ZHANG Diyou. Improved grey wolf optimizer for location selection problem of railway logistics distribution center [J]. Journal of Computer Applications, 2021, 41(10): 2905-2911.
[10]	WEI Wei, LI Xiaojuan. Patent quality evaluation using deep learning with similar papers as augmented dataset [J]. Journal of Computer Applications, 2020, 40(4): 966-971.
[11]	Jiangfeng XU, Yulong TAN. Optimization of multidimensional index query mechanism based on HBase [J]. Journal of Computer Applications, 2020, 40(2): 571-577.
[12]	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.
[13]	Ming DU, Anping YANG, Junfeng ZHOU, Ziyang CHEN, Yun YANG. Optimized algorithm for k-step reachability queries on directed acyclic graphs [J]. Journal of Computer Applications, 2020, 40(2): 426-433.
[14]	MEI Wei, ZHAO Yuntao, MAO Xuesong, LI Weigang. Path planning method for spraying robot based on discrete grey wolf optimizer algorithm [J]. Journal of Computer Applications, 2020, 40(11): 3379-3384.
[15]	YANG Cheng, LU Jiamin, FENG Jun. Survey of large-scale resource description framework data partitioning methods in distributed environment [J]. Journal of Computer Applications, 2020, 40(11): 3184-3191.

Accessing optimization with multiple indexes in TiDB

TiDB的多索引访问优化

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 15

Related Articles 15

Recommended Articles

Metrics