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]	Xiaoling SUN, Danhui WANG, Shanshan LI. Dynamic ciphertext sorting and retrieval scheme based on blockchain [J]. Journal of Computer Applications, 2024, 44(8): 2500-2505.
[2]	Yuan LI, Qiulan LIN, Anzhi CHEN, Guoli YANG, Wei SONG, Guoren WANG. Temporal shortest path counting query algorithm based on tree decomposition [J]. Journal of Computer Applications, 2024, 44(8): 2446-2454.
[3]	Fanjun MENG, Bin HAN, Shucheng HUANG, Xiangdong MEI. Distributed temporal index for temporal aggregation range query [J]. Journal of Computer Applications, 2024, 44(6): 1848-1854.
[4]	Shuai REN, Yuanfa JI, Xiyan SUN, Zhaochuan WEI, Zian LIN. Prediction of landslide displacement based on improved grey wolf optimizer and support vector regression [J]. Journal of Computer Applications, 2024, 44(3): 972-982.
[5]	Kedi NIU, Min LI, Zhongyuan YAO, Xueming SI. Review of blockchain consensus algorithms for internet of things [J]. Journal of Computer Applications, 2024, 44(12): 3678-3687.
[6]	Chuanyu ZONG, Chunhe ZHANG, Xiufeng XIA. Maximum cycle truss community search based on hierarchical tree index on directed graphs [J]. Journal of Computer Applications, 2024, 44(1): 190-198.
[7]	Yun OU, Kaiqing ZHOU, Pengfei YIN, Xuewei LIU. Improved grey wolf optimizer algorithm based on dual convergence factor strategy [J]. Journal of Computer Applications, 2023, 43(9): 2679-2685.
[8]	Ting YANG, Ruoyu MO, Xiujuan ZHANG, Zhousen ZHU. Enhancement and expansion of full-text search in relational databases based on lightweight caching strategy [J]. Journal of Computer Applications, 2023, 43(8): 2431-2438.
[9]	Xiaoyu ZHANG, Ziqiang YU, Chengdong LIU, Bohan LI, Changfeng JING. Spatial-temporal co-occurrence pattern mining algorithm for video data [J]. Journal of Computer Applications, 2023, 43(8): 2330-2337.
[10]	Fangshu CHEN, Wei ZHANG, Xiaoming HU, Yufei ZHANG, Xiankai MENG, Linxiang SHI. Dynamic aggregate nearest neighbor query algorithm in weighted road network space [J]. Journal of Computer Applications, 2023, 43(7): 2026-2033.
[11]	Hua JIANG, Xing LI, Huijiao WANG, Jinghai WEI. Cross-level high utility itemsets mining algorithm based on data index structure [J]. Journal of Computer Applications, 2023, 43(7): 2200-2208.
[12]	Jun LIANG, Zehong HONG, Songsen YU. Image segmentation model based on improved particle swarm optimization algorithm and genetic mutation [J]. Journal of Computer Applications, 2023, 43(6): 1743-1749.
[13]	Xiaoyan ZHANG, Jiayi WANG. Comparison of three-way concepts under attribute clustering [J]. Journal of Computer Applications, 2023, 43(5): 1336-1341.
[14]	Chenghao YU, Runhe QIU. Performance analysis of bit error rate on RIS assisted index modulation cooperative system [J]. Journal of Computer Applications, 2023, 43(11): 3559-3567.
[15]	Erchao LI, Shenghui ZHANG. Dynamic multi-objective optimization algorithm based on adaptive prediction of new evaluation index [J]. Journal of Computer Applications, 2023, 43(10): 3178-3187.

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