1、分布式数据库与存储专场分布式数据库与存储专场张建 2021 年 08 月 01 日张建 2021 年 08 月 01 日本期议题：A History of TiDB Query Optimizer张建，开源爱好者，TiDB MaintainerTiDB SQL 团队负责人兼 TiKV 产品负责人PingCAP前 MaxCompute 执行引擎研发Alibaba关注数据库、分布式系统、开源软件与社区等领域Email:About MeAgenda01Whats TiDB02The History of TiDB Optimizer03Future WorkWhats TiDBWhats TiDBT

2、iDB：全新一栈式实时 HTAP 数据库一键水平扩容或者缩容金融级高可用实时 HTAP云原生的分布式数据库兼容 MySQL 5.7 协议和 MySQL 生态TiDB-ServerTiFlash NodeTiFlash NodeTiFlash NodeTiKV NodeMPP EngineTiKV NodeTiKV NodeTiKV ClusterOLTP ApplicationsOLAP Applications助推全球助推全球 1500+企企业业互互联联网化和数字化网化和数字化10+银银行与行与头头部金融企部金融企业业网联交易、网贷核算互联网业务中台实时风控、反欺诈三大运三大运营营商商支付与

3、风控征信与账单系统精准营销覆盖中国互覆盖中国互联联网网独角独角兽兽企企业业的的 80%万亿量级数据毫秒响应支付、秒杀等场景单个集群1000+节点物流与零售物流与零售实时统计报表数据中台交易与报表业务隔离美国、日本、美国、日本、东东南南亚头亚头部支部支付企付企业业与与电电商商在线支付用户与订单管理风控与营销OLTP 规规模化的模化的头头部用部用户户支撑平安人寿“金管家”单日交易额破1000 亿亿，超，超 1 亿亿用用户户高可靠、低延高可靠、低延迟迟、可快速、可快速扩扩展展大大降低敏大大降低敏态应态应用开用开发发复复杂杂度度，加快应用上线速度在在线弹线弹性性扩缩扩缩容容满足不确定业务需求在线支付联

4、机交易，钱包等高增高增长长交易支撑，交易支撑，3000 万用万用户户水平水平弹弹性性扩扩展展和几乎线性的扩展能力友好的开友好的开发发界面界面，应用几乎无需改动实时实时高并高并发发，高效支撑短时高峰交易及数据访问，1.5 亿亿用用户户弹弹性高性高扩扩展，展，TiDB on K8s 随时随地在线扩展安全高可用，安全高可用，可靠放心的高可用容灾保障能力面向零售高增面向零售高增长长交易交易场场景景在在线线核心核心联联机支付交易平台机支付交易平台面向金融敏面向金融敏态态交易交易场场景景全球全球领领先餐先餐饮饮巨巨头头 日本日本头头部金融支付企部金融支付企业业 平安人寿在平安人寿在线线金融金融联联机服机服

5、务务TiDB HTAP：一：一栈栈式数据服式数据服务务生生态态存储节点存储节点数据中枢场景交易交易处处理和在理和在线线分析同步分析同步规规模化模化报报表表业务业务不影响在不影响在线线交易交易流式计算场景混合负载场景实时实时到到账账、实时统计实时统计缩缩短短业务业务等待周期，提升用等待周期，提升用户户体体验验多源多源汇汇聚，聚，统统一数据服一数据服务务节节省系省系统统和数据聚合代和数据聚合代码码开开发时间发时间写写 SQL 就行了就行了一个TiDB 系统，一个访问入口，一份数据The History of TiDB OptimizerWhats Query Optimizer目目标标：做一个：做

6、一个执执行行计计划划输入 AST输出物理执行计划物理物理执执行行计计划需要考划需要考虑虑什么内容：什么内容：选哪个索引子查询如何执行用什么 Join 算法和 Join 顺序.SortHashJoinTableScant1TableScant2MergeJoinIndexJoinIndexScant1IndexScant2select t1.afrom t1join t2on t1.col1=t2.col1order by t1.col1NominalSort采用 1979 年由 Selinger 在 System R 中使用的经典优化器模型TiDB 优优化器框架化器框架简简介介TiDBTiKV

7、ParserPhysicalOptimizerRootExecutorSQLASTLogicalPlanPhysicalPlanFeedbackLogicalOptimizerDistSQLStatisticsCardinalityEstimationCopExecutorTiKVCopExecutorTiKVCopExecutorCop TaskCop TaskCop TaskResult优化器的关键要素：搜索空间搜索算法代价估算统计信息能帮我们做什么有多少数据满足条件：id between 10129 and 23819按照索引 date 去读取到第一个 id 10129 的数据要扫多少数

8、据：where id 10129 order by date limit 1有多少数据满足条件：s join t on s.id=t.id统计统计信息信息简简介介TiDB 1.0 中的统计信息简介：初始初始阶阶段：段：拥拥有基本的有基本的统计统计信息和信息和 CBO 能力能力Count-Min Sketchwhere date=2021-08-01where status in(Desiging,testing)TiDB 1.0 中的统计信息简介：初始初始阶阶段：段：拥拥有基本的有基本的统计统计信息和信息和 CBO 能力能力Equal-Depth Histogramwhere date bet

9、ween 2021-07-31 and 2021-08-01where age 20;在线业务忽然卡了集群中出现了好多慢查询TiDB OOM 了.遇到的遇到的问题问题先看先看执执行行计计划划根据 parent 和 children 来判断数据在计算过程中的流向提升提升执执行行计计划可划可读读性性使数据依赖关系一目了然：树形结构：上层的节点依赖下层的节点数据作为输入Build 和 Probe 两个关键：Probe 依赖 Build 作为输入丰富各种情况下丰富各种情况下问题问题排排查查的方式的方式希望知道实际运行时哪里慢了，优化器估算值和实际值的差距：explain analyze一个 SQL 长

10、时间运行不结束，希望知道它的执行计划是什么，卡在哪里：explain for connection希望知道慢查询日志中的 SQL 为什么慢：从记录 explain 结果到记录记录 explain analyze 结结果果希望知道这个 SQL 历史上的执行计划是什么，执行时间分别什么样：statement summary 系列的内部表系列的内部表希望一眼看出哪个 SQL 慢，慢在哪里：TiDB Dashboard趋势趋势：信息越来越丰富，工具越来越易用：信息越来越丰富，工具越来越易用TiDB Dashboard什么是优化器 Hint：告诉优化器选哪个具体的索引告诉优化器用什么 Join 算法告诉

11、优化器用什么聚合算法先加先加 Hint，提供，提供 workaround 方法方法SELECT/*+USE_INDEX(t1,idx1),HASH_AGG(),HASH_JOIN(t1)*/count(*)FROM t t1,t t2 WHERE t1.a=t2.b;给 SQL 加 Hint 需要改业务 SQL：SQL 散落在各个地方不好改改 SQL 涉及到应用代码的修改，需要完整走一遍应用程序的发布流程有些 SQL 是应用程序引用的第三方库发的，没法改Hint 有哪些有哪些问题问题SQL Binding：不用修改 Hint需要 super 权限从从 Hint 到到 SQL BindingCR

12、EATE BINDING FORSELECT count(*)from t t1,t t2 WHERE t1.a=t2.a;USINGSELECT/*+USE_INDEX(t1,idx1),HASH_AGG(),HASH_JOIN(t1)*/count(*)FROM t t1,t t2 WHERE t1.a=t2.b;“我有很多 SQL，成千上万，一个个加 Binding 太累了！”“万一 SQL 参数的值变化了，原先的执行计划不够好怎么办？”select*from twhere date between?and?;SQL Binding 有哪些有哪些问题问题？从从 SQL Binding 到

13、到 SPMSQLCost-based Plan GenBaselineExists?Execute PlanIs Plan in Baseline?Execute PlanQueue New Plan for verificationExecute Known PlanNoNoYesYesSPM 两大特性：自动捕获自动演进于此同于此同时时，我，我们们也在完善也在完善优优化化规则规则和和统计统计信息信息缩小搜索空间，降低犯错的概率：引入 Skyline Pruning 裁剪一定不优索引引入更多一定优的启发式规则CREATE TABLE t(id INT,date DATETIME,INDEX i

14、dx1(id),INDEX idx2(id,date);SELECT*FROM tWHERE id=10291 AND date=2021-08-01;于此同于此同时时，我，我们们也在完善也在完善优优化化规则规则和和统计统计信息信息降低基数估算误差，提升选对执行计划的能力：引入 TopN 的统计信息引入相关系数的统计信息去除 CM-Sketch 的统计信息xhash collision从从 OLTP 优优化器成化器成长为长为 HTAP 优优化器化器TiDB-ServerTiFlash NodeTiFlash NodeTiFlash NodeTiKV NodeMPP EngineTiKV Nod

15、eTiKV NodeTiKV ClusterOLTP ApplicationsOLAP ApplicationsHTAP 的的优优化器架构化器架构TiFlash Node 1MPP WorkerOptimizerTiFlash Node 2TiFlash Node 3TiDB-ServerMPP WorkerMPP WorkerPlan SegmentParserUserQueryTiKV Node 1TP Queryread KV directlyTiFlash iscomputing/storage combined for now.It forms MPP cluster in AP w

16、orkload.In MPP mode,TiDB-Server becomes the coordinator.Making HTAP real by MPP first release复复杂杂的的优优化器系化器系统统，需要有科学的，需要有科学的测试测试体系体系Optimizer Effectiveness含义：优化器选中的执行计划不差于多少比例的执行计划参考：OptMark:A Toolkit for Benchmarking Query Optimizersand,oris covered by an indexpredicae on the attribute:col,=,=,in co

17、nsis the last attributeyesnonoget a new attributeget a record from the tableconstruct filters based on the record复复杂杂的的优优化器系化器系统统，需要有科学的，需要有科学的测试测试体系体系用 q-error 来衡量优化器的估算误差，降低它：含义：max(est/act,act/est)参考：Preventing Bad Plans by Bounding the Impact of Cardinality Estimation ErrorsTiDB 优化器架构故障诊断和恢复统计信息优化做分布式并行执行计划建立科学的测试体系总结总结Future Work提高可提高可预测预测性：性：添加更多启发式规则为什么没有选这个索引？提高可提高可观测观测性：性：Optimizer Trace为什么选了这个索引？提高可提高可扩扩展性：展性：Cascades PlannerFuture WorkTHANKSTHANKS