来源书籍

TiDB源码阅读系列文章

Skill 版本:v23 工程实践(高信息浓度、低稳定性) 153 张卡片

全文解释优化器的属性与统计推导、算子并发和恢复边界,信息浓度高;具体接口、约束与源码路径依赖早期实现,因此稳定性评为低。

申砾 · 2019-03-13

全书导读

这组文章以早期 tidb-server 为观察对象,解释一条 SQL 如何从客户端请求变成数据库操作。这里的 TiDB 有时指完整集群,有时专指 SQL 服务进程;系列主要追踪后者,不能当成 TiKV 的完整实现教材。EPUB 的 OPF 日期为 2019-03-13,未标明统一源码提交,因此本文所述路径、接口与限制均属于书中版本。原理可以迁移,代码定位和产品能力必须另按目标版本核对。

全书主线

SQL 描述“要什么”,数据库需要补出“怎样取得”。协议层先识别客户端命令,语法分析把文本变成树,计划层绑定对象并选算法,执行层按算子协作获取数据。数据实际分布在不同 Region 上,因此路由、网络重试、结果顺序和事务状态也会影响 SQL 层设计。

理解这些层次后,再看统计估计与代价选择、Join 与聚合、在线 DDL 和 Binlog。它们分别回答计划为何这样选、数据怎样处理、结构如何安全演进以及变更怎样传播,不能拼成每条语句都会走过的一条固定流程。

第01章 TiDB 源码阅读系列文章(一)序

序篇说明学习范围与方法:读者要把数据库原理放到成熟实现里检验,而不是只记文章中的结论。这里主要讲 tidb-server,即接收 SQL 并协调执行的服务。TiKV 存储和 PD 调度属于完整集群的其他组成,不能因为本系列提到它们就认为已经覆盖其全部实现。

阅读顺序从协议和 SQL 主流程进入优化器、执行器等模块。先追一条主路径,才能知道局部代码在解决哪个问题。原文中的活动时间、产品开源状态和人员安排属于历史背景,不作为当前事实。

源码阅读的验证闭环:源码导读提供问题和路线,真正理解还要对照实现,解释代码如何影响系统行为。先认清总体结构,再跟踪一个实际功能,最后用修改或测试检查理解;只读讲解容易把简化模型误当完整实现。

SQL服务的阅读边界:完整 TiDB 集群包括 SQL 服务、调度和 KV 存储。该系列主要围绕 tidb-server;书中 Mock-TiKV 用于本地模拟和理解计算下推。读完 SQL 服务的路径,不能据此声称掌握 TiKV 的全部存储实现。

原书依据 · 2 处

第02章 TiDB 源码阅读系列文章(二)初识 TiDB 源码

TiDB 的 SQL 服务可分成三个职责层。协议层管理连接并解释 MySQL 命令;SQL 层解析、检查和规划语句,再生成执行器;KV 接口层负责用事务存储能力完成读写,并允许把计算交给存储侧。三层通过接口协作,所以“兼容 MySQL 协议”与“使用哪一种存储引擎”是两个不同问题。

包名地图用于定位职责。ast 保存语法对象,plan 处理计划,executor 完成执行;infoschema 是元信息的运行时视图,meta 负责持久化元信息,model 保存这些信息的数据结构。阅读时要按目的进入模块,而不是平均阅读所有包。

SQL引擎的三层职责:协议层把客户端命令交给 SQL 层;SQL 层决定要怎样操作数据;KV 层提供事务读写及可选的计算下推。协议兼容并不决定底层存储类型,存储实现只要满足约定接口就能接入书中设计。

按问题选择源码入口:只追某项功能时,从对应模块及接口入手;要理解全局时,从 main 的启动、请求接收和 SQL 执行路径逐步展开。先建立主路径,再补辅助模块,能避免把包数量当作学习进度。

事务KV与计算下推:事务 KV 接口足以表达 SQL 数据的读取和修改;分布式计算接口进一步允许发送计算请求,在数据所在处处理后返回结果。二者分别解决功能完整性和执行效率,不应把计算下推视为任何 KV 驱动天然具备的能力。

元信息的分层存放:model 定义数据库、表、列、索引等元信息对象;meta 在底层结构化 KV 上保存和修改元信息;infoschema 提供 SQL 层使用的元信息管理视图。把表示、持久化和访问分开,便于定位“定义错、存储错、视图错”的不同问题。

共享上下文与域:Context 把大量模块共同需要的能力抽成接口以缓和包依赖。Domain 是存储空间的抽象,并持有 Schema、统计等实例级信息;它不等同于一个客户端 Session。书中通常一个 TiDB 实例创建一个 Domain。

关系数据的KV编码:tablecodec 负责把 SQL 行和索引对象映射成 KV,codec 负责具体数据类型的编码。structure 则在事务 KV 上提供 List、Queue、HashMap。它们处在不同抽象层,排查编码或元信息问题时不能混为一个存储模块。

集群任务的唯一执行者:某些集群任务只能由一个 tidb-server 执行,例如异步 Schema 变更。owner 模块协调出执行者,每类任务可有自己的 Owner;这是一种任务级职责,不意味着整个集群只有一个工作节点。

全局标识区分元数据对象:数据库、表与自增行标识需要在相应命名范围内保持唯一。书中 meta/autoid 除了生成表自增 ID,也生成全局 Database ID 与 Table ID;这些内部身份与用户可见名称是不同东西。

表达式与类型分工:expression 承担运算符和内建函数,types 承担类型表示与操作,聚合表达式另有对应模块。识别这三个职责,才能把值转换问题与普通求值、分组累计问题分别定位,而非把所有计算都归为执行器。

原书依据 · 23 处

第03章 TiDB 源码阅读系列文章(三)SQL 的一生

一条 SQL 先以 MySQL 命令包进入连接处理循环。普通查询走 COM_QUERY,把文本交给 Session;Session 带着时区、自动提交等环境调用解析和编译。解析产生抽象语法树,预处理检查对象与名字,优化生成执行计划,再由计划构造执行器。

计划描述怎样做,执行器负责实际做。结果集提供读取数据的接口,协议层持续拉取结果并编码给客户端,因此构造结果集不等于已经算完查询。无返回列的写语句也需要被驱动执行,只是执行点与查询不同。

命令分发到会话执行:连接循环读出网络包,dispatch 按首字节识别命令,COM_QUERY 交给 handleQuery,再经 TiDBContext 进入 Session.Execute。Session 会考虑会话变量,因此同一 SQL 文本的行为还受时区、自动提交等环境影响。

声明式SQL需要补算法:SQL 表达需要哪些数据,没有指定怎样取得。数据库要把语义变成计划,并考虑数据分片和网络异常;复杂性来自语言组合、算法选择和分布式条件,不能只把数据库视为 SQL 字符串翻译器。

AST与计划的区别:AST 表达语句的语法结构,例如表、过滤条件和输出列;计划进一步表达如何实现语义。预处理做合法性检查和名字绑定,优化器负责生成并优化计划,执行器才把计划转成实际运算。

结果集是惰性读取接口:结果集描述列信息并提供 Next 或 NextChunk 逐行、逐批取数。生成结果集只建立读取入口;客户端取结果时才持续驱动执行。关闭接口负责释放执行链资源,不能把结果对象创建成功当成计算全部结束。

火山模型的拉取驱动:执行器组成树,父算子调用子算子的 Next/NextChunk 取得输入,再计算自身结果。顶层结果读取驱动整棵树推进;写语句虽然不返回数据,也要调用执行入口完成副作用。

查询与写语句驱动时机:查询要把数据送回客户端,由返回结果的循环驱动结果集读取;不返回列的 Insert 等语句则在构造结果集前立即执行。二者共享执行框架,但没有相同的延迟执行时机。

原书依据 · 20 处

第04章 TiDB 源码阅读系列文章(四)Insert 语句概览

简单 INSERT 展示一次写入如何沿统一框架落到事务 KV。语法节点保存目标表和值列表,建计划时补全数据库、表和列信息,并将值转换成表达式。执行器求出每行数据后,把行和各索引编码为 KV 写入事务缓存;事务提交时才交给存储引擎。

本章刻意限定为普通 VALUES 写入。其计划不走逻辑计划的通用优化路径,不能由此推出 INSERT SELECT 或所有写语句都没有优化空间。原书示例建表代码的花括号属于展示文本,不作为可直接执行的标准 SQL。

插入计划补全写入语义:简单 INSERT 的 AST 保存目标表和二维值列表,计划构建补齐库表列信息,并把 AST 表达式转成执行框架可求值的表达式。没指定列名时使用全部列,不能只按文本中的值直接构造存储记录。

简单插入绕过逻辑优化:书中普通 VALUES 插入转为 plan.Insert,它只实现 Plan,不属于 LogicalPlan,因此不进入 doOptimize。这个判断受计划类型限制,不能推广成所有写入来源和所有版本都不需要优化。

写入缓存与提交分离:Insert 执行求值后同时构造行和索引 KV,调用 txn.Set 写进当前事务缓存;真正提交存储发生在事务提交过程。单次 AddRecord 或 Set 成功只说明该层已接收变更,不等于分布式事务已经持久提交。

索引KV的定位作用:非唯一索引允许相同列值出现多次,因此书中编码把行 Handle 追加到索引键以区分记录,值可只存占位字节。唯一索引在需要唯一约束的情形把 Handle 放在值里。读索引后能否直接得到行数据,还取决于投影列是否在索引里。

原书依据 · 12 处

第05章 TiDB 源码阅读系列文章(五)TiDB SQL Parser 的实现

Parser 把文本变成语法树,它由词法和语法分析配合完成。词法分析识别关键字、变量、字面量等 token;语法分析按产生式和优先级组合 token,归约时构造 AST 节点。词法规则关心字符怎样分段,语法规则关心片段怎样组成合法结构。

TiDB 在书中使用手写 Scanner 和由 goyacc 生成的语法分析器。parser.y 的声明区定义符号、语义值、优先级与结合性,规则区描述 SQL 结构并附构造节点的动作。后续合法性检查和名字绑定通过 Visitor 遍历 AST,属于解析结果的使用,不应混同于词法扫描。原文在乘法归约示例的说明里误写“两表达式相加”,应以其乘法产生式和动作代码为准。

词法与语法分析分工:词法分析将字符流识别成 token;语法分析把 token 按产生式组合成树。前者解决“这是一段什么词”,后者解决“这些词怎样组成语句”。语法树保留语义处理需要的结构,不必像表达式计算器那样立即求值。

移进归约的工作方式:移进把新 token 连同状态压栈,归约把匹配某条产生式右侧的内容替换为左侧非终结符。重复这两个动作,最终把完整输入归约为起始结构;运算符优先级和结合性影响何时归约。

产生式动作构建AST:产生式动作可以直接计算值,也可以构造 AST 节点。$1、$2 等引用右侧符号的语义值,$$ 保存归约结果。SQL Parser 选择构造节点,让后续预处理、优化和执行各自承担职责。

语义值承载解析结果:parser.y 的 union 描述 token 和非终结符可携带的值,goyacc 据此生成 yySymType。关键字、字面量、表达式和语句节点按声明存取不同字段;读规则动作要同时核对符号声明,不能只看 token 名。

Scanner满足词法接口:goyacc 通过 yyLexer.Lex 获取 token,通过 Error 报告词法相关错误。书中 Scanner 手写实现该接口;Lex 的语义值参数带回位置和值,返回整数标记 token 类型,0 与 invalid 分别有终止和非法字符含义。

Visitor分离遍历处理:AST 节点通过 Accept 接收 Visitor,Visitor 用 Enter 和 Leave 在进入、离开节点时处理内容,还能跳过子树或返回变换后的节点。这样名字绑定等处理复用树遍历结构;它不是 Go 继承关系。

语法规则与语义处理分界:SELECT 产生式构造 SelectStmt,并保存 FROM、WHERE、GROUP BY 等语法成分。能生成 AST 不代表名字存在或计划已选好;增加语法时要同时检查节点表示和后续使用者,不能只修改生成后的 parser.go。

终结符与非终结符:BNF 用产生式描述语法。终结符是词法分析输出的 token,非终结符表示可继续由规则展开的语法对象;解析反过来把具体输入归约成非终结结构。产生式描述允许的组合,动作决定怎样构建语义值。

原书依据 · 29 处

第06章 TiDB 源码阅读系列文章(六)Select 语句概览

SELECT 的难点在于计划选择和分布式执行。语法树先转成逻辑算子树,例如扫描、过滤和投影;规则优化改写树,物理优化再按统计和属性要求选具体算法。相同的过滤语义可能由不同扫描方式完成,不应只按 SQL 表面顺序理解执行。

能在存储侧完成的扫描、过滤和部分聚合可打包为 CopTask,TiDB 自身保留的计算称 RootTask。Coprocessor 按 Region 处理键范围,DistSQL 隔开结果读取与分布式请求的复杂性。最终结果通过迭代接口返回,表扫描和过滤仍可能在同一存储侧任务中执行。

逻辑与物理优化分工:逻辑优化按规则改写关系运算,物理优化为逻辑节点选择扫描和计算算法。统计信息决定过滤后剩多少数据,因而影响 TableScan 与 IndexScan 等选择;一个语义正确的逻辑树还没有给出最终访问路径。

按属性搜索物理计划:物理优化递归要求子节点满足所需属性,为候选算子计算子任务,再比较组合代价。相同属性下已求得的任务可缓存以避免重复搜索;“选局部最小”必须限定在相同输出要求下。

根任务与下推任务:CopTask 表示存储节点上的计算片段,RootTask 表示 TiDB 内的片段。任务把物理计划和代价封装到相应执行位置,支持评估分布式计划;这不是说每个 SQL 只能有一个计算节点。

表达式下推有能力边界:只有存储侧支持的表达式才能编码并下推。书中先把可下推条件放进 DataSource,再将扫描和相应 Selection 纳入 CopTask;不能下推的部分仍须在上层计算,不能静默丢弃。

Region级分布式查询:SQL 层先确定查询 Key Range,再按 Region 边界拆分并发送。各 Region 计算本地数据,TiDB 汇总后继续处理剩余算子;一次逻辑扫描因此可能对应多次远程请求。

DistSQL隔离分布式细节:DistSQL 为 SQL 执行器提供统一查询结果入口,把路由、重试、并发控制和结果顺序隔离在分布式查询抽象内。执行器反复取 Chunk 直至空批次,而不需要自行维护每个 Region 的请求状态。

原书依据 · 16 处

第07章 TiDB 源码阅读系列文章(七)基于规则的优化

关系算子把 SQL 拆成数据源、选择、投影、连接、排序和聚合等运算。规则优化利用等价关系减少无用数据,但每条规则都要保留查询语义:列裁剪必须保留过滤和连接依赖的列,谓词下推不能随意越过 LIMIT,外连接只有在补出的 NULL 行一定会被过滤时才可改成内连接。

MIN/MAX 重写借助有序访问只读取极值附近的数据,同时需要保留空输入和 NULL 的聚合语义。原书用降序例子解释 MIN 的段落有误:MIN 对应升序、MAX 对应降序;其“!= null”示例也不应照抄为 SQL 的非空判断。MaxOneRow 属性表示最多一行的信息,不能把校验多行的断言算子简单当作 LIMIT 1。

关系算子的基本职责:DataSource 提供数据,Selection 按条件筛行,Projection 选择列或表达式,Join 按连接关系组合两侧行;Sort 排序,Aggregation 按键分组计算。算子树描述这些职责的组合,语法里的同一段并不总是单独保留成物理节点。

列裁剪保留隐含依赖:列裁剪自顶向下传播“上层需要的列”,并加上本节点计算要用的列。输出只要 a,但 WHERE 依赖 b 时,扫描仍需 a、b;聚合键、排序键和 Join 条件用列同样不能因最终不输出而被裁掉。

极值改写依赖有序访问:MIN/MAX 可借助相应方向的有序扫描和只取首个非空值,减少全量聚合读取。必须处理 NULL 与空输入的聚合语义;MIN 对应升序、MAX 对应降序,原书先前用降序说明 MIN 的示例不能直接作为等价 SQL。

冗余投影可以消除:若投影输出和子节点输出完全相同,它没有增量作用;连续投影也可能由上层投影吸收。能否消除取决于表达式和上层上下文,不能见到两个相邻 Projection 就无条件删掉其中一个。

谓词下推保留剩余条件:把条件推到靠近数据源处,可先减少 Join 或后续算子的输入。下推接口返回无法下推的条件及新计划,剩余条件要留作上层 Selection;优化的责任是重排计算位置,不是删除不方便执行的条件。

空值拒绝约束外连接改写:左外连接会为未匹配右行补 NULL。只有后续过滤必然排除这些补空行时,才可改写为内连接。要按 SQL 三值逻辑检查整个谓词,非空判断使用 IS NOT NULL;原书的“!= null”示例不应当作推荐写法。

过滤不能任意跨越限额:LIMIT 先截断再过滤,与过滤后再取 LIMIT 的结果通常不同。优化必须保护这种顺序依赖;MaxOneRow 的基数信息与限制或校验算子的语义也要区分,不能为了下推而改变多行错误行为。

唯一键属性辅助优化:唯一性和最多一行等属性从叶子向上推导,为后续改写提供依据。唯一索引含可空列时要额外注意 NULL;投影丢失关键列也会丢失相应唯一性,不能把底层的唯一约束无条件带到所有上层节点。

原书依据 · 31 处

第08章 TiDB 源码阅读系列文章(八)基于代价的优化

代价优化在满足相同要求的可行计划之间做比较。“要求”不仅是返回什么数据,还包括是否按某列排序、在哪一层执行以及预计读取多少行。Stream 聚合依赖分组键有序,Hash 聚合不要求同样的输入顺序,因此会把不同属性需求传给下层。

统计信息提供行数和不同值数等估计,算子逐层推导中间结果规模,再把计算、内存和网络等成本纳入任务代价。记忆化减少相同节点、相同属性的重复搜索,属性剪枝则尽早排除不可能或无需枚举的要求。优化器比较的是模型下的估计,不是实际运行后保证最快。

所需属性约束候选计划:required property 描述上层对输出的要求,例如按分组键有序。Stream Agg 会向子节点请求相应顺序,Hash Agg 可以没有该要求;只有满足同样属性的计划才属于可替代候选。

按属性记忆化搜索:自顶向下把要求传给子节点,并缓存某个逻辑节点在特定属性下的最优任务。再次遇到相同问题时复用结果;属性不同便不能仅因节点相同就复用,否则会混淆有序与无序等不同语义。

统计信息估算输出规模:统计估计既包括行数,也包括每列不同值数。数据源根据过滤选择率调整输出规模,Join 用两侧规模和连接键不同值数估计匹配量。模型依赖分布假设与统计新鲜度,估计值不是实际行数证明。

期望行数影响提前停止:上层 LIMIT 所需行数会向下传递,但底层还需按过滤选择率放大读取量。若要 3 行、选择率约 0.1,理想估计需扫描约 30 行;若必须先排序全部候选,LIMIT 本身不能令扫描提前结束。

双读成本不能过早裁掉:覆盖索引单读只需索引访问,非覆盖索引双读还要按 Handle 取行。只比底层 IndexScan 可能误判优劣;分成 cop single 和 cop double 后,要在完整读取与过滤边界比较总成本。

属性剪枝减少排列爆炸:多个等值连接键可能产生阶乘数量的排序属性排列。先从数据源的真实主键和索引得到可提供属性,再限制候选组合,能排掉大量无用搜索;剪枝不是任意省略仍可能更好的执行路径。

连接基数估计依赖分布假设:书中内连接估算把两侧行数乘积除以连接键不同值数的较大者,可由其给出的公式约简而得。这相当于按键值分布近似匹配;键倾斜、取值不重合或相关性都会让真实结果偏离,不能当成恒等式。

原书依据 · 23 处

第09章 TiDB 源码阅读系列文章(九)Hash Join

Hash Join 先把 Inner 侧按连接键放进哈希表,再用 Outer 侧的每行探测匹配。Inner/Outer 表示构建和驱动职责,不能一概换成小表/大表;外连接的保留侧会约束方向。

实现把读取 Outer、并行探测、向调用方返回结果分开,并通过通道循环复用 Chunk。哈希键找到候选后,还需检查两表非等值条件,并按连接类型生成结果;普通等值连接的 NULL 键也有专门处理。不同结果生成语义决定未匹配行如何输出。

哈希连接的构建与探测:Build 阶段按 Inner 的连接键建立哈希索引,Probe 阶段用 Outer 行查找候选。内连接可倾向让估计较小的一侧构建,但书中外连接的保留侧限制方向,因此不能把 Inner 永远解释成小表。

重复连接键需要多值映射:同一连接键可能对应多行 Inner 数据,所以哈希表必须保存一个键的多个行位置。探测命中要遍历这些候选,不能把普通 map 的后写覆盖前写语义带入 Join,否则会丢结果。

探测任务与Chunk回收:Outer Fetcher 从可复用资源池取得 Chunk,拉取数据后按资源记录的目的通道发给空闲 Worker。Worker 用完后归还资源;数据流同时携带可回收对象和接收方,使任务供给与内存复用协同。

结果传递交换复用内存:Worker 把结果 Chunk 及归还通道传给主线程;主线程与调用方的 Chunk 交换数据,再把资源交回原 Worker。调用者获得结果而缓冲区循环复用,减少每批结果重新分配的开销。

连接条件分层计算:Inner 单侧过滤可提前下推;Outer 单侧过滤在探测前判断;双侧等值条件构成哈希键;双侧非等值条件在候选匹配后再算。哈希键命中只是候选成立,不能替代完整 ON 条件。

普通等值连接不匹配空键:普通 SQL 等值比较不会让 NULL 与 NULL 成为真。书中构建时跳过含 NULL 的键,Outer 含 NULL 时也不查哈希表。外连接是否仍输出补空行,属于连接结果语义,不应与探测匹配混淆。

连接类型决定输出形态:内连接只输出匹配组合,外连接还保留指定侧未匹配行并补空;Semi Join 只判断是否存在匹配并输出驱动行,Anti Semi 则保留无匹配行。Outer Semi 变体把存在性编码成布尔列,不能把这些结果都当成普通两表拼行。

原书依据 · 35 处

第10章 TiDB 源码阅读系列文章(十)Chunk 和执行框架简介

Chunk 是按列连续存放的一批内存数据。定长列按固定宽度定位,变长列用 offsets 找边界,NULL 位图独立记录是否为空。Row 则是跨列访问某个行号的逻辑视图,不意味着把该行所有字段重新复制到连续内存。

执行框架从每次取一行改为一次取一批,减少函数调用、对象分配和垃圾回收,也改善列访问的局部性。批次大有吞吐收益,却可能为小请求预留过多内存,因此书中的批量默认值与性能对比都需要留在当时版本和测试条件下理解。

列式Chunk压缩对象开销:Chunk 把同列数据连续组织,用一批数据替代逐行 Datum 对象流转。它支持追加而非任意随机写;收益包括减少对象开销、便于复用和统计内存,而不只是把若干行装进一个容器。

定长与变长列的定位:定长值按宽度排列,变长值连续写入 data 并在 offsets 记录边界。NULL 用位图表示:书中 0 表示空,1 表示非空;定长空值仍占位,变长空值沿用当前偏移。值域和空值标记不能混为一体。

行视图无需复制整行:列存中同一行各字段分散在不同 Column。Row 只提供按行号访问列值的逻辑视图,不需要把整行复制成连续对象;算子仍可按行处理,物理布局和访问接口不必一致。

批处理的收益与代价:每次 NextChunk 返回多行,可摊薄函数调用、复用内存并改善缓存局部性。但给小请求直接分配最大批次不一定合算;批次大小应结合行宽、实际请求规模和延迟目标评估,不能照抄历史默认值。

原书依据 · 23 处

第11章 TiDB 源码阅读系列文章(十一)Index Lookup Join

Index Lookup Join 用 Outer 侧一批连接键去限定 Inner 侧索引范围,避免对每条驱动行都扫描全表。它结合批量取数和批内哈希匹配:Outer Worker 生成任务,Inner Worker 并行读限定范围,主线程按 Outer 任务次序探测并返回结果。

保序来自按任务次序消费,而不是所有后台任务按序完成;因此当前任务未结束时主线程可能等待。批次用动态增长平衡小输入负载和大输入吞吐,重复连接键会在查询 Inner 前去重,但不能因此删除原始 Outer 行的结果。

嵌套循环到索引连接:普通嵌套循环为每个 Outer 行扫描 Inner;分块版本用一批 Outer 行摊薄重复扫描。索引连接进一步由这一批连接键构建 Inner 的取值范围,只读相关记录,适合有可用索引且范围选择性合算的场景。

并行取数按任务保序:Outer Worker 同时把任务交给 Inner Worker 和主线程。Inner 并行完成取数,主线程按原任务次序等待 doneCh 后探测,从而保留 Outer 顺序;代价是慢任务可能挡住后面已完成任务。

自适应批次平衡开销:批次太大时小输入容易让 Worker 分工不均;太小时大输入会增加调度与重复网络读取。书中采用指数增长直到上限,使早期较小任务与后期吞吐兼顾;历史上限值不是通用最佳设置。

过滤位图避免复制行:批量过滤可用与原 Chunk 行数相同的布尔数组记录各行是否通过,而不重建合格行对象。后续算子按标记读取原批次,节省提取和复制成本;原 Chunk 的生命周期必须覆盖这些引用。

查询键去重保留结果重数:同批 Outer 的重复 Join Key 可先排序去重,只查一次对应 Inner 范围。读取后按连接键建立映射,再逐原始 Outer 行探测,因此去重的是访问请求,而非 SQL 结果中的行重复。

原书依据 · 21 处

第12章 TiDB 源码阅读系列文章(十二)统计信息(上)

统计信息是数据分布的摘要,供优化器在不实际执行所有候选计划的前提下估算代价。直方图适合范围查询,Sketch 用小空间近似频次;它们精度与分布假设不同,不能把估计值当真实结果。

列统计先抽样再排序建桶,索引数据已有序,可边扫描边合并桶。查询反馈用实际范围计数调整桶高和边界。多列条件优先用覆盖多个条件的索引统计,减少列独立性假设;仍未覆盖的相关性会带来误差。

统计摘要替代穷举执行:优化器要区分计划成本,不能为了选计划先把所有计划实际执行一遍。表行数、不同值数、NULL 数、平均长度和分布摘要提供便宜的估计输入;即便估计不精确,也可能足以排除代价差距大的方案。

等深直方图描述分布:等深直方图让每个桶包含的记录数尽量相近,而非让取值跨度相同。完整覆盖的桶可直接累加,部分覆盖通常按桶内连续均匀假设估计;热点或稀疏间隔会使该假设失准。

最小计数Sketch估频:Count-Min Sketch 用多行独立哈希把同一值计入多个桶,查询取这些计数最小值。非负插入且未作额外校正时,碰撞只增加计数,得到不低于真实频次的估计;它节省空间,但不能当精确计数表。

去噪Sketch改变误差界:Count-Mean-Min 在每行计数中减去估计噪声,再取各行估计的中位数。它与原始 Count-Min 更新结构相同,查询规则却不同,因此不能把原始取最小值的单侧高估保证直接套到去噪估计上。

蓄水池均匀抽样:容量 S 的样本池先收下前 S 个元素,随后第 n 个元素以 S/n 概率入池,并随机替换旧样本。这样在读完整个流后各元素有同样的入选概率;样本排序成本较低,但抽样本身仍要遍历输入。

重复值不跨直方桶:列样本排序后依次装桶,即使桶已满,与上一值相同的新值也放在同一桶。牺牲严格等深以避免同一值横跨桶,便于等值边界和范围估计;因此等深应理解为尽量均衡。

有序索引在线建桶:索引流天然有序,初始桶深很小,桶数超限后把相邻桶两两合并并扩大深度。Region 结果合并时先处理交界处相同值,防止一个值分散在多个桶,再控制总桶数。

反馈按桶定位误差:将查询范围按直方图边界切开,让执行侧返回每段真实计数,可知道各桶贡献的误差,而不是把总误差平均分摊给所有桶。后续调整桶高和边界仍受反馈覆盖与桶数预算约束。

桶边界随查询热点调整:查询边界在桶内造成估计误差时,可按反馈点分配拆分预算并选新边界;为限制桶数,再优先合并误差较小的旧相邻桶。目标是把有限分辨率用在常被查询、误差显著的位置。

多列估计减少独立假设:分别计算列条件再相乘,假定列之间独立。联合索引统计可直接估算一组前缀条件;Selectivity 用条件集合覆盖选择少量统计对象,再组合剩余估计,以减少而非消除独立性假设。

查询反馈校正频次与桶高:范围反馈可用实际计数与估计计数之比修正桶高;等值反馈则调整 Sketch 中相关计数,使该查询的估计贴近观察。更新是在已有摘要上校正,仍受哈希碰撞、反馈范围和新旧数据差异约束。

原书依据 · 29 处

第13章 TiDB 源码阅读系列文章(十三)索引范围计算简介

索引范围计算分两步:从完整过滤条件中抽出可用于索引的部分,再把这些表达式转成可扫描区间。AND 可留下有关索引的必要条件,OR 则要求每个分支都能被扫描范围覆盖,避免漏行;被抽掉的残余过滤仍必须执行。

组合索引按列的字典序排列,书中实现只有前面的列都是点查时才继续收紧后列。区间计算用端点表示开闭边界,AND 取交、OR 取并,再转成物理键范围。本章若干例子只为展示形状:出现了未定义的 d 列,且一处把 OR 误写成 AND,不把这些当可执行示例。

访问条件与残余过滤:可用来构造扫描范围的条件只负责缩小候选集合。AND 中不相关条件可以暂不参与范围计算,但仍须作为残余过滤;“从范围表达式删去”不等于“从查询语义删去”。

或条件范围必须覆盖分支:对于 a 索引,a=1 OR b=2 不能仅扫描 a=1,否则会漏掉靠 b 命中的行。只有每个 OR 分支都能提供安全的 a 范围时才能合并为并集;原文一处将应保留的 OR 写成 AND,不能照搬。

组合索引按前缀收紧:书中 ranger 沿组合索引逐列处理:前缀列必须是等值或 IN 点集,才继续用下一列缩小范围。a>1 与 b=1 不能按同样方式收紧后列,而 a IN 点集加 b>1 可以展开多个前缀区间。

表达式形状影响范围识别:语义相近的 OR、IN 和元组 IN 在书中实现可能走不同识别路径。部分点集 OR 未被识别为点查,会阻断后列条件使用;改写要先证明等价,再在目标版本验证范围和计划,不能当永久 SQL 规则。

端点扫描计算区间交并:区间端点包含值、左右端和开闭标记。对内部无重叠的已规范化区间序列,按端点扫描维护覆盖次数:求并保留被任一序列覆盖部分,求交保留两者同时覆盖部分;边界包含性仍须参与比较。

组合范围的字典序展开:先把前缀点值依次写入范围的低高值向量,再按最后一列的范围数复制并扩展。OR 分支的范围合并按左端排序并维护最右界;这利用的是组合键字典序,不是各列独立区间的任意笛卡尔盒。

函数包列限制索引提取:书中简单条件识别限定 Column op Constant,函数包住列时可能无法构造索引范围。考虑改写到原列时要检查函数逆变换、时区和边界语义;原文提出的方向不证明所有函数都有安全逆变换。

原书依据 · 21 处

第14章 TiDB 源码阅读系列文章(十四)统计信息(下)

本篇把前章统计原理映射到源码。Histogram 记录桶边界,Column/Index 各自组合直方图和 Sketch;analyze 把不同列与索引拆成任务下推。列样本、索引有序流和跨 Region 合并使用不同构建入口,但共同保护重复值边界和桶数预算。

反馈先按桶上界拆查询范围,实际发送时又按 Region 划分。QueryFeedback 利用起始键和连续计数对应回逻辑范围,再进行桶分裂、估计修正与低误差合并。这里是把执行观察送回模型,不是每次增删都精确重建全表统计。

统计表示复用列式存储:直方图的上下界用 Chunk 保存,减少大量 Datum 的分配开销。Column 和 Index 再把直方图与 CM Sketch 组合成不同统计对象;数据结构选择不仅影响估计算法,也影响统计元数据本身的内存成本。

反馈范围映射跨越Region:查询范围先按桶上界拆分,发送时再按 Region 分割。返回的计数按连续范围排列,配合扫描 start key 定位到 QueryFeedback 的逻辑区间;缺少这层映射就可能把真实计数归到错误桶。

分裂预算与低误差合并:反馈按桶归组,按信息量分配分裂预算,选查询边界并修正桶深;太小的桶不继续分。控制总桶数时,优先合并预计误差较低的旧桶,避免刚为热点细化的桶立即被吞回。

条件覆盖优先选择索引:Selectivity 把每个统计对象能解释的条件编码成 bitset,贪心选择覆盖未处理条件最多的对象。覆盖数相同时书中优先主键或索引统计,再组合各组结果;此策略减少相关性丢失,但仍不能代替完整多列统计。

平均分摊误差会失真:把总估计误差按均匀比例分配给涉及桶,可能把新增越界值的误差摊给原本准确的旧区间。反馈应尽量定位到具体范围;动态修正的依据、覆盖盲点与分布变化必须一起检查。

原书依据 · 25 处

第15章 TiDB 源码阅读系列文章(十五)Sort Merge Join

Sort Merge Join 要求两侧按连接键有序,比较当前键组后推进较小的一侧,键相等时组合两组匹配行。若索引已提供正确顺序,可省去额外排序;否则排序成本可能成为主要开销。

顺序扫描不代表内存恒定。旧版把同键组整体缓存,严重倾斜会放大内存;书中提出逐行推进 Outer 并跟踪 Inner 内存的改进。外连接不能简单丢弃未匹配行,最终是否补 NULL 要交给连接语义处理。

归并连接利用有序输入:两侧按连接键排序后,比较当前键:较小的一侧向前推进,相等时组合两组行。索引若已提供相同顺序,可免额外排序;有序条件不满足时,不能只看到线性归并就忽略前置排序成本。

同键组必须保留全部组合:相同连接键可能在两侧重复,归并应遍历两组的行组合,而不是只把当前位置配一对后同时前移。外侧未匹配行及未通过 ON 单侧条件的行,是否输出仍由连接类型决定。

有序连接也会因倾斜耗尽内存:一次性读入完整同键组,在重复键很多时会放大中间内存。逐行推进 Outer 可减少一侧缓存,但 Inner 大组仍需内存追踪和超限策略;书中日志或终止措施不等于已具备自动落盘。

原书依据 · 15 处

第16章 TiDB 源码阅读系列文章(十六)INSERT 语句详解

不同写入语句共享数据准备与执行框架,却有不同冲突语义。普通 INSERT 冲突报错,IGNORE 把相应冲突变成跳过和警告,ON DUPLICATE KEY UPDATE 更新冲突行,REPLACE 则删除冲突记录后插入。这里的“更新”不是更新后再追加一条新行。

书中普通 INSERT 可把唯一性检测推迟到提交,IGNORE 与冲突更新却要及时知道哪些行冲突。batchChecker 批量读唯一键和旧行以减少 RPC,同时在本地回填每行处理后的键状态,否则同一批的后行会看不见前行刚产生的冲突。所有时机均限定于书中版本,不能推广到不同事务模式。

插入变体选择冲突语义:普通 INSERT 遇唯一冲突报错;IGNORE 跳过相应行并给警告;ON DUPLICATE KEY UPDATE 更新冲突行,更新本身也可能引发新冲突;REPLACE 删除冲突行再插入。它们不是可随意替换的性能开关。

延迟唯一检查改变报错时点:书中普通 INSERT 先在本地缓存写入,未发现本地冲突便暂定键不存在,提交时批量检查。因而语句返回成功仍可能在 COMMIT 报唯一冲突;客户端必须理解事务结果,不能只凭 INSERT 返回作业务完成判断。

忽略冲突要求及时检测:IGNORE 要立刻报告未插入行的 warning,不能等到提交阶段再让事务层区分逐行策略。batchChecker 把唯一约束编码成键并批量读取,按查得结果逐行决定跳过或写入,避免每行一次远程检查。

冲突更新先取旧行:ON DUPLICATE KEY UPDATE 不仅需要知道哪个唯一键冲突,还需取得相应旧行来计算更新表达式。书中先批量取键再取旧记录,更新引发新唯一冲突时根据是否带 IGNORE 选择错误或警告。

批内冲突检查要回填状态:批量预读只是开始时的快照,同一批后行可能与前行刚插入或更新的键冲突。每处理一行后要删除旧键、回填新键到本地检查映射,使后续检测看到批内变化;仅做一次远程 BatchGet 会漏掉这类冲突。

替换语句可能删除多行:一条待插入记录可能分别与多条旧记录的不同唯一索引冲突。REPLACE 会删除所有这些冲突行再写新行,所以一次输入并不只影响一个旧对象;例如原文四个冲突旧行加一次插入共影响五行。

原书依据 · 25 处

第17章 TiDB 源码阅读系列文章(十七)DDL 源码解析

在线 DDL 处理的是 Schema 演进:客户端请求先封成持久 Job,Owner 的 Worker 推进状态并同步版本。这里的 Job 状态和索引、列、表的 Schema 状态是不同维度;多次状态过渡使新旧视图的节点逐步兼容,而不是一个元信息开关立即覆盖所有进程。

建索引还要回填历史行,并持久保存进度。删列可只改元信息让解码忽略旧字段;删表则先使表不可见,再交给 GC 清理数据。书中并行 DDL 把耗时建索引拆队列,但同表任务仍要维护依赖,不能因分队列而改变先后语义。

DDL请求持久化为任务:DDL API 检查并封装 Job 写入持久队列,Owner Worker 取任务执行,完成后转入历史队列,提交端据历史结果返回。请求节点和执行节点可以不同;队列与历史保存在存储层,不能只靠某进程的内存完成状态。

DDL所有权带租约切换:各节点有 Worker,但只有当选 Owner 的节点能推进任务。Owner 续约维持身份,宕机后可重新选出执行者。唯一执行权和持久进度共同支撑接续执行,不能把选主本身当成任务无需恢复的保证。

在线建索引分阶段发布:建索引先增加元信息,再经过 delete only、write only、reorganization 到 public。回填范围覆盖已有行,多个 Worker 分段处理,并定期保存进度;索引不能在历史数据尚未补齐时直接按完整索引供查询使用。

逻辑删除与物理回收分离:删列可修改表元信息,解码时忽略原行里的字段,不立即重写所有行。删表先移除元信息,再把键范围交给 GC;SQL 层对象不可见与底层字节已回收是两个完成时点。

并行DDL仍需同表依赖:把慢建索引分到独立队列可减少对其他 DDL 的阻塞,但同表操作必须按依赖顺序。先加列再建该列索引时,后者要等待前者,即使分处不同队列;并行调度不取消数据对象的顺序约束。

原书依据 · 23 处

第18章 TiDB 源码阅读系列文章(十八)tikv-client(上)

TiKV 客户端把事务存储接口映射成远程请求。先按键找到 Region,再找到可处理该 Region 的节点;RegionCache 用键区间和 ID 两种索引缓存元信息,减少每次请求都访问 PD 的成本。缓存可能过时,所以服务端仍要校验请求中的 Region 信息。

错误要区分 Leader 改变、Region 分裂、服务繁忙和网络失败。它们分别要求更新目标、重分任务、退避或失效缓存。Backoffer 的时间预算还要覆盖整个查询的多个子请求,不能让每个 RPC 各自重试到上层早已超时。

Region缓存按两种方式查找:Region 覆盖左闭右开的键区间。RegionCache 用 map 按 Region ID 查找,用 B-tree 按键定位区间;缺失时询问 PD。范围定位从当前 Region 的 EndKey 继续,直到覆盖请求范围。

路由缓存必须由服务端校验:PD 信息也来自 TiKV 上报,并非客户端随时取得的绝对最新状态。请求到达后由 TiKV 校验 Region 信息,过期时拒绝;客户端失效或刷新缓存再重试,避免把旧范围直接用于已分裂的数据。

多路复用仍可能需要连接池:gRPC 可在一条 TCP 连接承载并发请求,但并不保证单连接吞吐无限。书中测试促使每个目标地址维护多条连接并轮转选择;池大小应由实际并发、流控和资源代价验证,不能直接沿用旧默认值。

存储接口隔离真实RPC:tikvStore 对外实现事务存储能力,内部经 Client 抽象发请求。真实实现使用 gRPC,本地 mock 实现可以直接调用模拟逻辑。上层依赖存储行为而非连接细节,使功能测试不必启动完整远程集群。

路由错误与过载区别重试:NotLeader 要调整目标 Leader;StaleEpoch 表示范围元信息过时,需要重新定位;ServerIsBusy 是主动过载保护,要等待后再试。网络错误与响应中的 Region 错误也不同,不能用同一种无限快速重试处理。

子请求共享总退避预算:指数退避平衡重试压力与延迟。查询可能顺序或并发发出多个 RPC,子 Backoffer 继承父级已等待时间,避免各自预算叠加突破查询期限;还需按错误类别选择等待策略。

原书依据 · 22 处

第19章 TiDB 源码阅读系列文章(十九)tikv-client(下)

copIterator 把一个分布式查询拆成 Region 任务,再用后台 Worker 预取和并发执行。无序请求从全局结果通道消费,有序请求从每任务的通道按顺序消费;Region 分裂重建子任务时,仍需把结果放回旧任务对应的位置。

事务提交部分只覆盖 TiDB 客户端协调逻辑。它收集 mutation、选事务 Primary、计算大小和锁 TTL,再 prewrite、取提交时间戳并验证、提交。提交网络超时可能意味着结果未知,不能当作确定回滚并盲目清锁;书中断开连接处理这种不确定性,并未承诺调用方可直接安全重试业务。

查询拆成Region任务:一个 SQL 可以产生多个 DistSQL 请求,每个又拆成多个 Coprocessor 任务。每个任务键范围不得越过对应 Region;下推可能减少网络返回和序列化开销,但不自动减少底层扫描量。

预取与并发解决不同等待:后台预取把 RPC 等待提前到调用 Next 之前,多个 Worker 则让不同任务并行。前者只隐藏部分等待,后者增加并发吞吐;通道关闭表示结果流结束,不能用暂时无数据误判完成。

保序结果按任务通道消费:共享结果通道按完成先后产生乱序;每任务单独通道让 Next 按任务次序读取,保留逻辑顺序。Region 分裂时子任务结果仍回到旧任务通道,且可能一任务对应多个响应。

事务Primary不是表主键:提交器从本地缓存收集 PUT、DELETE 和 LOCK mutation,并在书中选择首个键作为事务 Primary。它是事务协议的协调键,不能与 SQL 表的 PRIMARY KEY 混同;大小限制则约束整批事务资源。

锁TTL权衡恢复与执行时间:prewrite 后协调进程若宕机,其他请求可能被残留锁阻塞。TTL 给恢复提供时间边界;太短会打断正常大事务,太长会延长故障影响。书中按事务大小平方根并加上下界估算,不能当所有版本的固定公式。

提交前验证时间与Schema:书中先完成 prewrite,再取得 commitTS,检查它大于 startTS、Schema 仍有效且事务未超时,然后执行 commit。准备阶段成功不等于事务已提交,检查失败与提交结果未知也不能混为一类。

提交超时意味着结果未知:commit RPC 网络超时后,服务端可能已提交,只是响应丢失。此时执行失败清锁可能破坏一致性;书中返回特殊 undetermined error 并断开连接。上层须区分失败与未知,后续动作要依据可核查的事务或业务状态。

不同提交阶段的并行边界:prewrite 的多批次需要并行完成后再前进;commit 先处理首批成功后再异步处理其他批;cleanup 可异步分批。Region 变化要重新拆批,错误会取消相关并发上下文;不能把三个阶段套同一并行模板。

事务状态分散到键上:书中用 Percolator 解释事务模型:把协议状态保存在键上,减轻集中事务管理器的单点负担。它仍依赖时间戳服务和存储侧协议,去掉一个协调热点不等于不再需要全局协调或故障恢复。

原书依据 · 39 处

第20章 TiDB 源码阅读系列文章(二十)Table Partition

分区表对用户是一张逻辑表,底层却按分区 ID 存成多个物理表。分区规则决定新行去向,查询可合并多个分区,也可利用条件裁掉不相关分区;按生命周期删除分区与逐行 DELETE 是不同管理方式。

本篇实现主要按 release-2.1 的 Range 分区讲解。创建和增加分区要核验名称、边界递增及表达式合法性,元信息附在 TableInfo。删除分区改变可存放的数据范围并删除对应数据,不能当成只改名称。书中关于唯一键包含关系、键编码次序和示意查询的表达有含混或笔误,不据此给出生产建表规范;一般分区类型的介绍也不代表当时 TiDB 全部支持。

逻辑分区与物理表区分:用户仍操作一个逻辑表,底层由多个按规则分配数据的物理分区组成。查询裁剪可减少扫描,分区增删可服务生命周期管理;分区规则若未打散递增写入,不能仅凭“分区”两字保证热点消失。

分区类型对应不同映射:Range 按边界分段,List 按枚举集合分组,Hash 由整数表达式取模,Key 使用系统定义的键计算。它们解决的访问和分布问题不同;本章真正追踪的 TiDB 实现仅限书中 Range 版本。

分区元信息附属逻辑表:创建时先把分区语法转换成 PartitionInfo,检查名称、边界和表达式等约束,再附在 TableInfo 中保存。每个新增分区分配独立 ID;它不是一个与逻辑表无关、可独立命名查询的普通业务表。

分区裁剪排除无关扫描:书中计划把逻辑数据源展开成分区 Reader 的 Union All,再根据条件排掉不可能命中的分区。分区键范围提供排除依据,索引选择继续作用于保留分区;逻辑分区也不等同于 TiKV Region。

分区ID承担物理命名:普通表用 Table ID 区分物理记录,分区表各分区使用自身 Partition ID 编码行与索引。逻辑名称不变,物理键空间却不同;确定写入或删除范围应核对实际编码实现,不能照抄本篇简化字符串拼接。

分区写入先计算归属:locatePartition 根据分区表达式结果定位分区,再调用相应 AddRecord。若没有分区覆盖该值则报错;书中 Range 的 NULL 归入最小分区。边界、NULL 和删分区后的可覆盖范围都必须纳入数据接入检查。

删分区会移除数据范围:删分区既移除逻辑表中的相应元信息,也处理该 Partition ID 下的数据。书中不允许删尽所有分区;删后若数据值不再被规则覆盖,写入会报错,故删除不能只按当前行数判断后续影响。

原书依据 · 33 处

第21章 TiDB 源码阅读系列文章(二十一)基于规则的优化 II

规则优化第二篇借助唯一性消除不必要的聚合与连接。若每组本来最多一行,聚合可改写成投影表达式,但仍须保持 COUNT 的 NULL 语义和返回类型。若上层只用外侧列,且内侧不会扩增行数或上层会去重,外连接可整个移除;这与转成内连接是不同优化。

相关子查询每次依赖外行,需要 Apply 执行。去相关把可提升的算子和条件挪到连接层,使内侧不再逐行依赖。它必须保护外侧行身份、空输入聚合和标量子查询多行报错;COUNT 空集为 0,不能照抄原文“所有聚合空集都 NULL”的概括。

唯一分组可消除聚合:若 GROUP BY 的列在下层输出中唯一,每组只有一行,MAX(a) 可化为该行 a,COUNT(a) 要化为非空时 1、空时 0。返回类型也须保持必要转换;不能简单把所有聚合函数都替换成参数。

外连接消除要保护重数:只有上层只需 Outer 列,且 Inner 连接键唯一,或上层会把重复行去重,才可消掉整个外连接。否则一条 Outer 行可能匹配多个 Inner 行,删连接就改变输出重数。

非相关子查询有两种路线:可提前求值得到标量的子查询可展开成常量;IN 子查询也可转为 Join,但须控制 Inner 重复造成的重数变化。小 Outer 按键查 Inner 可能省数据,反过来的分布可能更适合展开,因此改写不是恒优。

去相关释放连接算法选择:Apply 为每个 Outer 行把相关列值传入 Inner 后执行,物理选择受逐行依赖限制。把相关过滤提升为连接条件等改写若能移除 Inner 的外部引用,就可改为普通 Join,再由代价选择 Hash、Merge 或索引连接。

标量子查询限制不是截断:LogicalMaxOneRow 要在子查询返回多行时报错,不能当成 LIMIT 1 偷偷取第一行。只有下层属性已证明最多一行时,该校验才冗余可删;这是优化保留错误语义的例子。

投影提升保留输出依赖:去相关时可先从 Inner 移走 Projection,再按 Join 类型决定是否把该投影保留在 Apply 之上。普通连接仍输出 Inner 列,Semi 类连接不输出它们,因此是否重建投影取决于结果列语义。

聚合提升需外行身份唯一:把相关聚合移到 Join 后,需要按 Outer 唯一标识分组。若两条外行共享同一相关值,错误地合成一个组会把两次独立结果相加;唯一性前提和分组列共同保护每条外行身份。

空集语义限制聚合提升:SUM 等聚合的空输入结果与 COUNT 不同。把相关聚合提升到左连接之后,要核对补空行上的结果能否与原空集结果一致;COUNT 不能套用 NULL 传播的直接提升规则,须采用其他等价改写。

原书依据 · 31 处

第22章 TiDB 源码阅读系列文章(二十二)Hash Aggregation

Hash 聚合按分组键维护中间状态,Stream 聚合利用同组连续的输入,只保存当前组并在组结束时输出。AVG 要维护 sum 和 count,不能把各批平均值简单平均;这也解释了为什么分布式聚合必须约定中间结果形态。

计算模式说明输入是原始数据还是中间状态,输出是中间状态还是最终值。存储侧可先 Partial,再由 TiDB 合并;TiDB 自身还可把合并过程并行拆成 Partial Worker 与 Final Worker,按 Group Key shuffle 汇集同组结果。并行度、DISTINCT 支持和性能收益都按原文版本限定。

哈希聚合保存每组状态:哈希表以 GROUP BY 值为键,保存各聚合函数中间状态。例如 AVG 用 sum 与 count,所有输入读完后再除。原文两组状态 (6,3)、(3,3) 得到均值 2、1;组数增大会增加哈希状态内存。

流式聚合可以按组返回:输入必须按分组键有序,使同组行连续。读到下一组时即可结束并返回上一组;上层 LIMIT 若只需若干组,可避免继续读取,但若先要全量排序,则排序成本仍不可免。

聚合模式描述状态流转:Complete 从原始数据算最终值,Partial1 从原始数据产中间状态,Partial2 继续合并中间状态,Final 产最终值,Dedup 产去重原始值。跨阶段必须一致解释状态,AVG 应合并和与计数,而非平均各批均值。

下推聚合要重写输入类型:物理计划若允许聚合下推,要确认函数可被存储侧表达。TiKV Partial 返回中间结果后,TiDB 的 Final 模式和参数必须改成接收这些状态;不能只把原函数挪位置而仍按原始行解释输入。

并行聚合按组洗牌:Fetcher 分批给 Partial Worker,先各自做局部聚合,再按 Group Key 把同组状态送到同一 Final Worker 合并。只有把同一组收齐到正确位置,局部结果才能成为全局结果;并行不是把最终值随意拼接。

聚合并行能力有版本限制:书中含 DISTINCT 的 HashAgg 尚不能并行,因为未支持对应 DedupMode;部分与最终并发都为 1 时也走单线程。这是当时的实现边界,不能据此断言当前版本限制,更不能从一条 TPC-H 测试外推所有负载同倍提速。

原书依据 · 34 处

第23章 TiDB 源码阅读系列文章(二十三)Prepare/Execute 请求处理

Prepared Statement 把参数化 SQL 的准备和执行分开。Prepare 生成 AST、提取占位符、记录 Schema 与列信息,并在当前会话里分配 stmtID;Execute 找回语句并绑定本次参数。二进制命令与文本 PREPARE/EXECUTE 是两条入口,最后可共享执行机制。

AST 复用和物理计划缓存是不同层的节省。缓存还必须保护会话环境与 Schema 一致性,并在命中后按新参数重建范围。游标让客户端控制分批拉取,长参数可分段追加,Close/Reset 则有各自资源语义。书中安全收益限于参数被当值绑定,不能推出动态标识符拼接也安全。

准备一次解析多次绑定:Prepare 把带占位符 SQL 解析为 AST,并返回会话内 stmtID;Execute 携带该 ID 和本次参数,复用准备信息。省去反复解析与省去反复优化是两回事,后者还需计划缓存命中。

参数按文本位置建立映射:Prepare 遍历 AST 收集参数标记,按 offset 排序,后续绑定可定位每个问号。还要检查协议参数数量限制,保存 Schema 版本和返回列信息;stmtID 的身份限定于当前 Session,不能当全局语句 ID。

Schema变化触发重新预处理:Execute 按 stmtID 取出准备对象并填参数,再比较 Schema 版本。发生变更时重做预处理;缓存未开或未命中仍要正常优化。因此 Prepared 不能保证表结构变化后永远复用旧计划。

延迟释放兼顾事务重试:Close 先清理协议层语句映射,书中会话 Prepared 信息却延迟到事务结束再删。原因是事务重试可能只保留 Execute 与 Deallocate,需要旧 stmtID 找回准备对象;资源释放要服从真实生命周期。

长参数追加与重置分离:SEND_LONG_DATA 可按参数 ID 多次追加大参数,Execute 将预绑定数据和本次参数共同使用,完成后重置。RESET 则允许在执行前主动放弃已追加数据,不能把每次发送都误解为覆盖原内容。

游标把结果拉取权交给客户端:启用游标时,Execute 先保留结果集并返回列信息;FETCH 指定数量才驱动取数,超过本次数量的部分留待下次。末批标志告知结束,游标分批与执行器内部 Chunk 大小不是同一控制层。

计划缓存键保护执行环境:书中计划缓存按当前库、连接、语句、Schema、快照、SQL Mode、时区等环境组成键,并限制可缓存语句形状。命中必须维持相关环境假设,不能仅用 SQL 文本相同就认定旧物理计划可复用。

命中计划仍要重建范围:可缓存参数表达式延迟从当前执行上下文取值,避免把首轮参数固化进计划。命中后还要按新参数 rebuildRange;复用的是可参数化结构,不是上一次扫描的键边界。

原书依据 · 32 处

第24章 TiDB 源码阅读系列文章(二十四)TiDB Binlog 源码解析

本篇讲 TiDB 端如何把变更写给 Pump,并非 Binlog 整个集群的源码导读。DML 执行先在事务上下文按表累积行变更和顺序,再把这些数据绑定到事务提交。Prewrite Binlog 必须确认写入后才能继续提交,以保证成功事务有可追踪的准备记录。

提交完成标记异步输出,Pump 缺少标记时可向 TiKV 查询事务状态;不能把异步通知丢失直接判为回滚。DDL 还要区分 Job 状态与内部 Schema 状态,只在最终处理相关的事务输出记录;同一 Job 可能重试产生多条日志,因此 Job ID 与事务结果要一起看。

行变更按事务累积顺序:DML 执行时按表维护 TableMutation,记录插入行、修改前后行和删除行,并用 sequence 保存变更次序。事务未提交时这些只是待发布变化;日志不能脱离事务结果直接作为已生效事实。

预写日志确认是提交前置:提交时把所有行变化编码为 PrewriteValue 并绑定事务选项。数据 prewrite 与 Binlog prewrite 可并行,但继续提交前必须等待日志写入确认,保证成功提交的事务有对应准备记录。

异步完成标记需要反查状态:事务提交或回滚后异步写 Finish Binlog,避免再增加提交等待。Pump 若没收到完成标记,可依据 Prewrite 记录查询 TiKV 状态;这是以可核查状态补偿通知丢失,不能解释为可以省掉预写记录。

DDL两层状态:Job Running 期间可多次推进 Schema 状态,Job 状态不必每步改变。Done 表示本节点完成状态变更,Synced 表示等待其他节点同步后结束;取消则经历 Cancelling、Rollingback 与 RollbackDone。

DDL日志对应最终状态事务:DDL 内部状态变更各自以事务提交,但不会为每个中间状态输出同样的 DDL Binlog。书中在 Done/RollbackDone 的最终处理处写入原查询和 Job ID;内部事务回滚不等于用户 DDL 已完成回滚。

同一DDL任务可有多次日志:最终 Job 状态提交若失败,Owner 会继续重试,因而同一 DdlJobId 可能出现多次 Prewrite 与完成记录。消费时必须区分任务身份、内部事务结果及终态,不能把一次 Rollback 日志等同整个 DDL 最终失败。

原书依据 · 33 处

跨章综合

解析正确只说明文本能构成语法树,不能保证执行计划好。第七、八、二十一章说明等价变换、属性要求和代价选择如何共同补出物理算法;第十二、十四章的统计估计给它提供输入。估计出错会传导到访问路径、Join 顺序和并行程度,因此定位慢查询要区分语义重写、估计、执行三类问题。

执行器的批处理、Join 的并行、聚合的局部合并都在减少每行处理成本,但分别受内存、数据分布、顺序需求和阻塞边界约束。第十八、十九章进一步说明,逻辑上的一个范围扫描,在分布式环境里会拆成多个 Region 任务,并经历重试和结果合并;本地算子不能直接替代这层恢复责任。

写入、DDL 和 Binlog 共享事务背景,却处理不同对象:写入把行和索引变成 KV 变更;DDL 用状态机协调新旧 Schema;Binlog 记录变更并服务下游。识别各层完成语义,比把某次 RPC 成功等同于整个操作完成更重要。书中演进中的实现限制应保留在历史语境中。

发散与实践

读者延伸:沿着“一条语句的路径”核对旧版实现,再把原文中的限制转换为目标版本的检查问题。实践计划见概览中的 ideas 链接;源码首轮映射是本次准备材料,不代表已运行数据库或测得性能结果。

生成进度与管理记录

《TiDB源码阅读系列文章》概览

Skill 版本:v23

执行模式:light

建档进度:done

作者:申砾(OPF);各篇可能另署投稿作者。

信息浓度:高。SQL 解析、代价推导、并发算子、统计维护及 DDL 状态转换均给出机制和设计原因。

稳定性/时效性:低。可迁移的关系运算和统计原理很多,但主线依赖早期源码路径、执行接口和功能限制,需按目标版本核对。

四象限结论:工程实践(高信息浓度、低稳定性)

主题:数据库/存储;总表优先级:P6。

整书笔记:_book_note.md(schema 1)。

理由:全文解释优化器的属性与统计推导、算子并发和恢复边界,信息浓度高;具体接口、约束与源码路径依赖早期实现,因此稳定性评为低。

章节进度追踪表

章节号 章节标题 状态(pending/done) 卡片数
01 TiDB 源码阅读系列文章(一)序 done 2
02 TiDB 源码阅读系列文章(二)初识 TiDB 源码 done 9
03 TiDB 源码阅读系列文章(三)SQL 的一生 done 6
04 TiDB 源码阅读系列文章(四)Insert 语句概览 done 4
05 TiDB 源码阅读系列文章(五)TiDB SQL Parser 的实现 done 8
06 TiDB 源码阅读系列文章(六)Select 语句概览 done 6
07 TiDB 源码阅读系列文章(七)基于规则的优化 done 8
08 TiDB 源码阅读系列文章(八)基于代价的优化 done 7
09 TiDB 源码阅读系列文章(九)Hash Join done 7
10 TiDB 源码阅读系列文章(十)Chunk 和执行框架简介 done 4
11 TiDB 源码阅读系列文章(十一)Index Lookup Join done 5
12 TiDB 源码阅读系列文章(十二)统计信息(上) done 11
13 TiDB 源码阅读系列文章(十三)索引范围计算简介 done 7
14 TiDB 源码阅读系列文章(十四)统计信息(下) done 5
15 TiDB 源码阅读系列文章(十五)Sort Merge Join done 3
16 TiDB 源码阅读系列文章(十六)INSERT 语句详解 done 6
17 TiDB 源码阅读系列文章(十七)DDL 源码解析 done 5
18 TiDB 源码阅读系列文章(十八)tikv-client(上) done 6
19 TiDB 源码阅读系列文章(十九)tikv-client(下) done 9
20 TiDB 源码阅读系列文章(二十)Table Partition done 7
21 TiDB 源码阅读系列文章(二十一)基于规则的优化 II done 8
22 TiDB 源码阅读系列文章(二十二)Hash Aggregation done 6
23 TiDB 源码阅读系列文章(二十三)Prepare/Execute 请求处理 done 8
24 TiDB 源码阅读系列文章(二十四)TiDB Binlog 源码解析 done 6

非正文排除

spine项 类型 排除理由
1 cover.xhtml 封面 仅书名,无实质讲解
2 Section0001.xhtml 空白页 仅空白实体,无正文

待关联术语

术语名 出现章节 一句话语境
Goroutine/Channel/Sync 01 先修 Go 并发知识,序篇未展开
RPC 01 先修后端通信知识
TSO 02 模块表仅指向时间戳服务接口与客户端
Performance Schema 02 仅列模块用途
X-Protocol 02 仅列协议实现模块
字典树 05 仅指出 lexer 的 token 识别使用此结构
CNF/DNF 07 在条件组合和 NULL 过滤分析中出现,本文仅保留组合语境
Apply 07 仅指出承接子查询,后章详解
多路归并/外存中间结果 15 仅列后续优化方向,未展开实现
LOAD DATA 16 本篇说明数据源不同并明确不展开实现
聚合下推/TopN下推/Join Reorder 21 结尾仅预告其他规则,未在此篇展开
SQL注入 23 仅保留参数值绑定的作用范围,未展开完整安全防护
protobuf 24 只说明 Binlog 编码格式,未展开序列化协议

| F1/Spanner | 01 | 仅作分布式数据库背景提名,未指定论文 | | Google F1 在线Schema变更 | 17 | 说明算法来源,未展开完整证明 |

引用文献

标题 类型(书/论文/框架/源码项目) 出现章节 一句话语境
MySQL 源码项目 01 举作可研究的单机数据库
PostgreSQL 源码项目 01 举作可研究的单机数据库
FoundationDB 源码项目 01 书中历史背景,开源状态不作当前结论
ANTLR 4 框架 05 与 Lex/Yacc 对照提名,未展开实现
MySQL参考手册 SQL Statement Syntax 书 05 用于对照 SELECT 语法
HBase Coprocessor 框架 06 仅说明名称借鉴来源
Apache Arrow 框架 10 作为列存实现参考,未展开协议或完整格式
Accurate estimation of the number of tuples satisfying a condition 论文 12 等深直方图来源
An improved data stream summary: The count-min sketch and its applications 论文 12 Count-Min Sketch 来源
New estimation algorithms for streaming data: Count-min can do more 论文 12 去噪估计参考
Synopses for Massive Data: Samples, Histograms, Wavelets, Sketches 书 12 数据摘要的延伸阅读
TiDB 的异步 schema 变更实现 文章 17 原文延伸文章,类型栏沿用文献登记类别
TiDB 的异步 schema 变更优化 文章 17 原文延伸文章
Google Percolator 论文 19 文中说明事务状态分布在键上以弱化集中事务管理器;完整协议未展开

资金安全问题案例

问题标题 问题卡 解决方案卡(如有) 出现章节 一句话说明

无:本书未展开资金、余额、库存的具体正确性事故,不把一般 DDL/事务机制改造成资金案例。

实践卡进度

序号 实践标题 实践方式 状态(pending/done) 关联章节 产出
1 优化器到执行器深读 实现深读 done 06、08、09、22 idea-001-优化器到执行器深读.md;首轮源码映射已备
2 Region任务与保序深读 实现深读 done 18、19 idea-002-Region任务与保序深读.md;首轮源码映射已备
3 提交未知结果深读 实现深读 done 16、19、24 idea-003-提交未知结果深读.md;首轮源码映射已备

实践候选筛选:done

采用三个互补方向:计划与执行、Region 任务、事务提交。未另建从零实现、泛化性能实验及当前生产调参卡:成熟实现已经提供可读入口,尚无必须执行实验才能回答的具体问题。实践仅交付计划和首轮资料,未执行完整实践。

生成状态

已完成 24⁄24 正文项,知识卡 153 张。轻量模式:未执行笔记复核、独立审查及审查结果优化。

来源限制与版本

全文 24 篇已读,两个非正文页排除;图片资源错配与笔误处理见 _source_limits.md。保留 P2 后续:必要时用正确原版恢复缺失插图。

整书笔记 schema:1;字节 SHA-256:ca79da1afecb6ca95af639d1136c076f7cbf73de71370db62e453b6bf2ce73db。来源版本见 _source_manifest.json。

相关主题

从本书的主题进入跨书阅读,对照其他书籍的讲解。下方数量包含主题关联的全部卡片与书籍。

暂无公开主题。