TiDB 源码阅读系列文章(二十一)基于规则的优化 II
在TiDB源码阅读系列文章(七)基于规则的优化一文中,我们介绍了几种TiDB中的逻辑优化规则,包括列剪裁,最大最小消除,投影消除,谓词下推和构建节点属性,本篇将继续介绍更多的优化规则:聚合消除、外连接消除和子查询优化。聚合消除聚合消除会检查SQL查询中GroupBy语句所使用的列是否具有唯一性属性,
TiDB 源码阅读系列文章(二十)Table Partition
TablePartition什么是TablePartitionTablePartition是指根据一定规则,将数据库中的一张表分解成多个更小的容易管理的部分。从逻辑上看只有一张表,但是底层却是由多个物理分区组成。相信对有关系型数据库使用背景的用户来说可能并不陌生。TiDB正在支持分区表这一特性。在T
TiDB 源码阅读系列文章(十九)tikv-client(下)
TiDB源码阅读系列文章(十八)中,我们介绍了数据读写过程中tikv-client需要解决的几个具体问题,本文将继续介绍tikv-client里的两个主要的模块——负责处理分布式计算的copIterator和执行二阶段提交的twoPhaseCommitter。copIteratorcopIterat
TiDB 源码阅读系列文章(十八)tikv-client(上)
在整个SQL执行过程中,需要经过Parser,Optimizer,Executor,DistSQL这几个主要的步骤,最终数据的读写是通过tikv-client与TiKV集群通讯来完成的。为了完成数据读写的任务,tikv-client需要解决以下几个具体问题:如何定位到某一个key或keyrange所
TiDB 源码阅读系列文章(十七)DDL 源码解析
DDL是数据库非常核心的组件,其正确性和稳定性是整个SQL引擎的基石,在分布式数据库中,如何在保证数据一致性的前提下实现无锁的DDL操作是一件有挑战的事情。本文首先会介绍TiDBDDL组件的总体设计,介绍如何在分布式场景下支持无锁schema变更,描述这套算法的大致流程,然后详细介绍一些常见的DDL
TiDB 源码阅读系列文章(十六)INSERT 语句详解
在之前的一篇文章《TiDB源码阅读系列文章(四)INSERT语句概览》中,我们已经介绍了INSERT语句的大体流程。为什么需要为INSERT单独再写一篇?因为在TiDB中,单纯插入一条数据是最简单的情况,也是最常用的情况;更为复杂的是在INSERT语句中设定各种行为,比如,对于UniqueKey冲突
TiDB 源码阅读系列文章(十五)Sort Merge Join
什么是SortMergeJoin在开始阅读源码之前,我们来看看什么是SortMergeJoin(SMJ),定义可以看wikipedia。简单说来就是将Join的两个表,首先根据连接属性进行排序,然后进行一次扫描归并,进而就可以得出最后的结果。这个算法最大的消耗在于对内外表数据进行排序,而当连接列为索
TiDB 源码阅读系列文章(十四)统计信息(下)
在统计信息(上)中,我们介绍了统计信息基本概念、TiDB的统计信息收集/更新机制以及如何用统计信息来估计算子代价,本篇将会结合原理介绍TiDB的源码实现。文内会先介绍直方图和Count-Min(CM)Sketch的数据结构,然后介绍TiDB是如何实现统计信息的查询、收集以及更新的。数据结构定义直方图
TiDB 源码阅读系列文章(十三)索引范围计算简介
简述在数据库中处理查询请求时,如果可以尽早的将无关数据过滤掉,那么后续的算子就可以少做无用功,提升整个SQL的执行效率。过滤数据最常用的手段是使用索引,TiDB的优化器也会尽量采用索引过滤的方式处理请求,利用索引有序的特点来提升查询效率。比如当查询条件为a=1时,如果a这一列上有索引,我们就可以利用
TiDB 源码阅读系列文章(十二)统计信息(上)
在TiDB里,SQL优化的过程可以分为逻辑优化和物理优化两个部分,在物理优化阶段需要为逻辑查询计划中的算子估算运行代价,并选择其中代价最低的一条查询路径作为最终的查询计划。这里非常关键的一点是如何估算查询代价,本文所介绍的统计信息是这个估算过程的核心模块。这部分内容非常复杂,所以会分成两篇文章来介绍
TiDB 源码阅读系列文章(十一)Index Lookup Join
什么是IndexLookupJoinNestedLoopJoin在介绍IndexLookupJoin之前,我们首先看一下什么是NestedLoopJoin(NLJ)。NLJ的具体定义可以参考Wikipedia。NLJ是最为简单暴力的Join算法,其执行过程简述如下:遍历Outer表,取一条数据r;遍
TiDB 源码阅读系列文章(十)Chunk 和执行框架简介
什么是ChunkTiDB2.0中,我们引入了一个叫Chunk的数据结构用来在内存中存储内部数据,用于减小内存分配开销、降低内存占用以及实现内存使用量统计/控制,其特点如下:只读不支持随机写只支持追加写列存,同一列的数据连续的在内存中存放Chunk本质上是Column的集合,它负责连续的在内存中存储同
TiDB 源码阅读系列文章(九)Hash Join
什么是HashJoinHashJoin的基本定义可以参考维基百科:Hashjoin。简单来说,A表和B表的HashJoin需要我们选择一个Inner表来构造哈希表,然后对Outer表的每一行数据都去这个哈希表中查找是否有匹配的数据。我们不用“小表”和“大表”这两个术语是因为:对于类似LeftOute
TiDB 源码阅读系列文章(八)基于代价的优化
概述本文是TiDB源码阅读系列文章的第八篇。内文会先简单介绍制定查询计划以及优化的过程,然后用较大篇幅详述在得到逻辑计划后,如何基于统计信息和不同的属性选择等生成各种不同代价的物理计划,通过比较物理计划的代价,最后选择一个代价最小的物理计划,即Cost-BasedOptimization(CBO)的
TiDB 源码阅读系列文章(七)基于规则的优化
在TiDB里面,SQL优化的过程可以分为逻辑优化和物理优化两个部分。逻辑优化主要是基于规则的优化,简称RBO(rulebasedoptimization)。物理优化会为逻辑查询计划中的算子选择某个具体的实现,需要用到一些统计信息,决定哪一种方式代价最低,所以是基于代价的优化CBO(costbased
TiDB 源码阅读系列文章(六)Select 语句概览
在先前的TiDB源码阅读系列文章(四)中,我们介绍了Insert语句,想必大家已经了解了TiDB是如何写入数据,本篇文章介绍一下Select语句是如何执行。相比Insert,Select语句的执行流程会更复杂,本篇文章会第一次进入优化器、Coprocessor模块进行介绍。表结构和语句表结构沿用上篇
TiDB 源码阅读系列文章(五)TiDB SQL Parser 的实现
本文为TiDB源码阅读系列文章的第五篇,主要对SQLParser功能的实现进行了讲解,内容来自社区小伙伴——马震(GitHubID:mz1999)的投稿。TiDB源码阅读系列文章的撰写初衷,就是希望能与数据库研究者、爱好者进行深入交流,我们欣喜于如此短的时间内就收到了来自社区的反馈。后续,也希望有更
TiDB 源码阅读系列文章(四)Insert 语句概览
本文为TiDB源码阅读系列文章的第四篇。上一篇文章简单介绍了整体流程,无论什么语句,大体上是在这个框架下运行,DDL语句也不例外。本篇文章会以Insert语句为例进行讲解,帮助读者理解前一篇文章,下一篇文章会介绍Select语句的执行流程。这两条是最常用的读、写语句,其他的语句相信读者能触类旁通,可
TiDB 源码阅读系列文章(三)SQL 的一生
概述上一篇文章讲解了TiDB项目的结构以及三个核心部分,本篇文章从SQL处理流程出发,介绍哪里是入口,对SQL需要做哪些操作,知道一个SQL是从哪里进来的,在哪里处理,并从哪里返回。SQL有很多种,比如读、写、修改、删除以及管理类的SQL,每种SQL有自己的执行逻辑,不过大体上的流程是类似的,都在一
TiDB 源码阅读系列文章(二)初识 TiDB 源码
本文为TiDB源码阅读系列文章的第二篇,第一篇文章介绍了TiDB整体的架构,知道TiDB有哪些模块,分别是做什么的,从哪里入手比较好,哪些可以忽略,哪些需要仔细阅读。这篇文章是一篇入门文档,难度系数比较低,其中部分内容可能大家在其他渠道已经看过,不过为了内容完整性,我们还是会放在这里。TiDB架构T