TiDB 源码阅读系列文章（五）TiDB SQL Parser 的实现

       本文是 TiDB 源码阅读系列文章的第五篇，主要内容围绕 SQL Parser 功能实现进行讲解。网课内容源自社区伙伴马震（GitHub ID：mz）的源码阅读投稿。系列文章的网课目的是与数据库研究者及爱好者深入交流，收到了社区的源码阅读积极反馈。后续，网课allcoin平台源码期待更多伙伴加入 TiDB 的源码阅读探讨与分享。

       TiDB 的网课源码阅读系列文章，帮助读者系统性地学习 TiDB 内部实现。源码阅读最近的网课《SQL 的一生》一文，全面阐述了 SQL 语句处理流程，源码阅读从接收网络数据、网课MySQL 协议解析、源码阅读SQL 语法解析、网课查询计划制定与优化、源码阅读执行直至返回结果。

       其中，SQL Parser 的功能是将 SQL 语句按照 SQL 语法规则进行解析，将文本转换为抽象语法树（AST）。此功能需要一定背景知识，下文将尝试介绍相关知识，以帮助理解这部分代码。

       TiDB 使用 goyacc 根据预定义的 SQL 语法规则文件 parser.y 生成 SQL 语法解析器。这一过程可在 TiDB 的 Makefile 文件中看到，通过构建 goyacc 工具，使用 goyacc 依据 parser.y 生成解析器 parser.go。

       goyacc 是 yacc 的 Golang 版本，因此理解语法规则定义文件 parser.y 及解析器工作原理之前，需要对 Lex & Yacc 有所了解。Lex & Yacc 是用于生成词法分析器和语法分析器的工具，它们简化了编译器的编写。

       下文将详细介绍 Lex & Yacc 的工作流程，以及生成解析器的过程。我们将从 Lex 根据用户定义的 patterns 生成词法分析器，词法分析器读取源代码并转换为 tokens 输出，以及 Yacc 根据用户定义的语法规则生成语法分析器等角度进行阐述。

       生成词法分析器和语法分析器的网页建设源码过程，用户需为 Lex 提供 patterns 的定义，为 Yacc 提供语法规则文件。这两种配置都是文本文件，结构相同，分为三个部分。我们将关注中间规则定义部分，并通过一个简单的例子来解释。

       Lex 的输入文件中，规则定义部分使用正则表达式定义了变量、整数和操作符等 token 类型。例如整数 token 的定义，当输入字符串匹配正则表达式时，大括号内的动作会被执行，将整数值存储在变量yylval 中，并返回 token 类型 INTEGER 给 Yacc。

       而 Yacc 的语法规则定义文件中，第一部分定义了 token 类型和运算符的结合性。四种运算符都是左结合，同一行的运算符优先级相同，不同行的运算符，后定义的行具有更高的优先级。语法规则使用 BNF 表达，大部分现代编程语言都可以使用 BNF 表示。

       表达式解析是生成表达式的逆向操作，需要将语法树归约到一个非终结符。Yacc 生成的语法分析器使用自底向上的归约方式进行语法解析，同时使用堆栈保存中间状态。通过一个表达式 x + y * z 的解析过程，我们可以理解这一过程。

       在这一过程中，读取的 token 压入堆栈，当发现堆栈中的内容匹配了某个产生式的右侧，则将匹配的项从堆栈中弹出，将该产生式左侧的非终结符压入堆栈。这个过程持续进行，直到读取完所有的同花顺源码上传 tokens，并且只有启始非终结符保留在堆栈中。

       产生式右侧的大括号中定义了该规则关联的动作，例如将三项从堆栈中弹出，两个表达式相加，结果再压回堆栈顶。这里可以使用 $position 的形式访问堆栈中的项，$1 引用第一项，$2 引用第二项，以此类推。$$ 代表归约操作执行后的堆栈顶。本例的动作是将三项从堆栈中弹出，两个表达式相加，结果再压回堆栈顶。

       在上述例子中，动作不仅完成了语法解析，还完成了表达式求值。一般希望语法解析的结果是一颗抽象语法树（AST），可以定义语法规则关联的动作。这样，解析完成时，我们就能得到由 nodeType 构成的抽象语法树，对这个语法树进行遍历访问，可以生成机器代码或解释执行。

       至此，我们对 Lex & Yacc 的原理有了大致了解，虽然还有许多细节，如如何消除语法的歧义，但这些概念对于理解 TiDB 的代码已经足够。

       下一部分，我们介绍 TiDB SQL Parser 的实现。有了前面的背景知识，对 TiDB 的 SQL Parser 模块的理解会更易上手。TiDB 使用手写的词法解析器（出于性能考虑），语法解析采用 goyacc。我们先来看 SQL 语法规则文件 parser.y，这是封装时钟源码生成 SQL 语法解析器的基础。

       parser.y 文件包含 多行代码，初看可能令人感到复杂，但该文件仍然遵循我们之前介绍的结构。我们只需要关注第一部分 definitions 和第二部分 rules。

       第一部分定义了 token 类型、优先级、结合性等。注意 union 结构体，它定义了在语法解析过程中被压入堆栈的项的属性和类型。压入堆栈的项可能是终结符，也就是 token，它的类型可以是 item 或 ident；也可能是非终结符，即产生式的左侧，它的类型可以是 expr、statement、item 或 ident。

       goyacc 根据这个 union 在解析器中生成对应的 struct。在语法解析过程中，非终结符会被构造成抽象语法树（AST）的节点 ast.ExprNode 或 ast.StmtNode。抽象语法树相关的数据结构定义在 ast 包中，它们大都实现了 ast.Node 接口。

       ast.Node 接口有一个 Accept 方法，接受 Visitor 参数，后续对 AST 的处理主要依赖这个 Accept 方法，以 Visitor 模式遍历所有的节点以及对 AST 做结构转换。例如 plan.preprocess 是对 AST 做预处理，包括合法性检查以及名字绑定。

       union 后面是对 token 和非终结符按照类型分别定义。第一部分的最后是对优先级和结合性的定义。文件的第二部分是 SQL 语法的产生式和每个规则对应的 aciton。SQL 语法非常复杂，大部分内容都是产生式的定义。例如 SELECT 语法的定义，我们可以在 parser.y 中找到 SELECT 语句的产生式。

       完成语法规则文件 parser.y 的定义后，使用 goyacc 生成语法解析器。iapp源码主页TiDB 对 lexer 和 parser.go 进行封装，对外提供 parser.yy_parser 进行 SQL 语句的解析。

       最后，我们通过一个简单的例子，使用 TiDB 的 SQL Parser 进行 SQL 语法解析，构建出抽象语法树，并通过 visitor 遍历 AST。我实现的 visitor 只输出节点的类型，运行结果依次输出遍历过程中遇到的节点类型。

       了解 TiDB SQL Parser 的实现后，我们有可能实现当前不支持的语法，如添加内置函数。这为我们学习查询计划以及优化打下了基础。希望这篇文章对读者有所帮助。

       作者介绍：马震，金蝶天燕架构师，负责中间件、大数据平台的研发，今年转向 NewSQL 领域，关注 OLTP/AP 融合，目前在推动金蝶下一代 ERP 引入 TiDB 作为数据库存储服务。

源码阅读忆丛（）Minigui

       探索GUI的历史与实现

       对于GUI的细节仍然存在一些困惑，似乎总是有新的东西需要学习。年轻时，对《Windows程序设计》、MFC等书籍充满热情，那些API的神奇之处让人着迷。然而，花费大量时间深入学习，却似乎事倍功半，微软似乎更倾向于教人如何使用，而非深入解释实现原理。尽管如此，还是尝试实现过文字版的GUI，涉及基本的按钮、滚动条、菜单等元素。但一些细节仍不清楚。

       通过网络搜索，了解到魏永明的Minigui项目是对Windows GUI和GDI的模仿。通过下载vc6版本的MinGUI，能够进行调试。在分析代码时，发现事件回调、消息链等常见功能并无特别之处。而DefaultMainWinProc、InvalidateRect、PopupMenuTrackProc等函数则更具实际意义。GUI就像是在显存沙漠中绘画，有其既定规则。DefaultMainWinProc负责实现画最大、最小按钮、窗口方框等常规操作，而绘制的动作有其先后顺序，即消息的先后处理。

       GDI部分则展示了如何在显存中书写文字，包括粗体、斜体等效果；如何绘制图标和位图；关键的rgn裁剪矩形技术，用于加速绘制，矩形外的绘制不会进行。rgn裁剪矩形的运算包括加、减、合、并等，对应着窗口的各种移动和形状改变。不同线程之间的窗口管理由HWND_DESKTOP统一处理，desktop-common.c相当于窗口管理器，不同程序无法直接获取其他窗口的位置和大小，由其进行统一管理。desktop包含三个线程，分别负责捕捉键盘、鼠标消息，以及实际消息的处理，以及窗口给desktop的消息交由DesktopWinProc统一处理。

       MinGUI的模拟版本在调试方面虽能使用，但功能实现上有缺失。相比之下，libminigui-1.0.提供了完整的gui、gdi、kernel代码，定义了大部分的画窗套路和动作，只需要关注关键部分和自己定义的动作即可。

       Linux的GUI采用了xwindows，通过socket将xclient进程中的窗口绘制信息传输到xserver，由xserver统一处理。xclient之间互相不知道窗口的位置和大小，因此都通过xserver进行绘制，xserver还包含了窗口管理器。而MinGUI在一个进程的多个线程中实现，不存在窗口管理器与进程间位置信息传递的问题。

       Windows使用wink.sys作为窗口管理器，作为内核态程序，用户态的动态链接库在不同进程间数据段不同，但内核态的数据段统一，因此实现了窗口管理。Windows显示流畅的原因之一在于窗口管理机制与MinGUI的desktop类似，但实现机制有所不同。

       工作繁忙，业余时间进行学习。尽管以前对GUI有过大量无用功，但这次的探索仅用几天时间便有所收获。

vnpy源码阅读学习(3)：学习vnpy界面的实现

       在深入学习vnpy界面实现的过程中，我们首先了解了PyQt5的基础并进入vnpy的UI部分。从run.py文件中的UI部分开始，我们注意到关键代码如create_qapp()，该方法在/vnpy/trader/ui/init.py中定义，用于创建QApplication并处理全局异常。init.py的作用是封装文件夹为包，便于引入和管理，其内的方法在引入时会自动执行。

       在主窗体生成部分，我们重点研究了mainwindow.py的代码。__init__()方法中主要是初始化窗口的属性，而真正吸引眼球的是initUI()函数，它包含了init_dock和init_toolbar等组件的创建。init_dock通过create_dock创建自定义Widget并放入浮动窗口（QDockWidget）中，可以参考PyQt5高级教程中的相关内容。init_toolbar则负责初始化工具栏，而init_menu()则用于生成菜单并将其与相应的槽函数关联起来，确保菜单操作的响应。

       在打开功能窗口时，vnpy会先检查该窗口是否已在widgets列表中，如果没有，会新建实例并添加，然后调用show()或exec_()方法来显示或运行窗口。这样，vnpy的界面布局管理相当细致，确保了窗口的有序和一致性。通过这些代码，我们可以逐步理解vnpy界面是如何构建和管理的。

TiFlash 源码阅读（一） TiFlash 存储层概览

       本系列文章聚焦于 TiFlash，读者需具备基本的 TiDB 知识。TiFlash 是 TiDB HTAP 模式的关键组件，作为 TiKV 的列存扩展，通过 Raft Learner 协议实现异步复制，并提供与 TiKV 相同的快照隔离支持。自 5.0 引入 MPP 后，TiDB 的实时分析场景下计算加速能力得到了增强。

       TiFlash 整体逻辑模块划分如下：通过 Raft Learner Proxy 接入多 Raft 体系，计算层 MPP 在 TiFlash 间进行数据交换，提供更强的分析计算能力。Schema 模块与 TiDB 表结构同步，将 TiKV 同步数据转换为列形式，并写入列存引擎。底层为 DeltaTree 引擎。

       TiFlash 基于 ClickHouse fork，沿用了 ClickHouse 的向量化执行引擎，并加入针对 TiDB 的对接、MySQL 兼容、Raft 协议、集群模式、实时更新列存引擎、MPP 架构等特性。DeltaTree 引擎解决了高频率数据写入、实时更新读性能优化、符合 TiDB 事务模型、支持 MVCC 过滤、数据分片便于分析场景等需求。

       DeltaTree 引擎不同于 MergeTree，具备原生支持高频率写入、列存实时更新下读性能优化、支持 TiDB 事务模型、数据分片便于提供分析特性等优势。MergeTree 引擎存在写入碎片、Scan 时 CPU cache miss 严重、清理过期数据时 compaction 导致性能波动等问题，而 DeltaTree 通过横向分割数据管理、delta-stable 数据组织、PageStorage 存储等设计优化了性能。

       DeltaTree 引擎通过在表内按 handle 列分段管理数据，采用 delta-stable 数据组织，PageStorage 存储小数据块，构建 DeltaIndex 和 Rough Set Index 等组件优化读性能。DeltaIndex 帮助减少 CPU bound 的 merge 操作，Rough Set Index 用于过滤数据块，减少不必要的 IO 操作。

       TiFlash 存储层 DeltaTree 引擎在不同数据量和更新 TPS 下读性能表现优于基于 MergeTree 的实现，提供更稳定、高效的读、写性能。TiFlash 中的 PageStorage、DeltaIndex、Rough Set Index 等组件协同作用，优化数据管理和查询性能。

       DeltaTree 引擎在 TiFlash 内部实现中，通过 PageStorage 存储数据，DeltaIndex 提高读性能，Rough Set Index 优化查询效率，提供了对 HTAP 场景的优化和支持。TiFlash 存储层 DeltaTree 引擎的设计和实现细节将在后续章节中详细展开。

有人用过sourcetrail这个代码阅读工具吗,体验怎么样?

       尝试使用 CODEMAP源代码阅读器进行代码阅读体验如何？答案是：极佳。

       在阅读他人代码时，我们常常需要在不同文件间频繁跳转，同时记忆函数名称、所在行数及文件名。对于复杂的项目，还需要记住不同文件夹路径，这给学习带来巨大负担。常规方法是在本地环境中切换到早期版本，通过设置断点或命令行打印来追踪逻辑流程。然而，在复杂项目中，逻辑结构复杂，调用层次过深，多次文件间跳转和调用会令人感到疲惫。

       CODEMAP源代码阅读器解决了上述问题，它通过代码编辑器平铺布局，自动连接跳转结构，手动添加高亮和标注，使代码结构清晰易懂。以下是演示相关视频链接：

       bilibili.com/video/BV1V...