深入理解select count(*)底层究竟做了什么数据库

来源:互联网 / 作者:SKY / 2019-06-12 15:00 / 点击:
SELECT COUNT( * ) FROM t是个再常见不过的 SQL 需求了。在 MySQL 的使用规范中,我们一般使用事务引擎 InnoDB 作为(一般业务)表的存储引擎,在此前提下,COUNT(

SELECT COUNT( * ) FROM t是个再常见不过的 SQL 需求了。在 MySQL 的使用规范中,我们一般使用事务引擎 InnoDB 作为(一般业务)表的存储引擎,在此前提下,COUNT( * )操作的时间复杂度为 O(N),其中 N 为表的行数。

而 MyISAM 表中可以快速取到表的行数。这些实践经验的背后是怎样的机制,以及为什么需要/可以是这样,就是此文想要探讨的。

先来看一下概况: MySQL COUNT( * ) 在 2 种存储引擎中的部分问题:

深入理解select count(*)底层究竟做了什么

下面就带着这些问题,以 InnoDB 存储引擎为主来进行讨论。

一、InnoDB 全表 COUNT( * )

主要问题:

执行过程是怎样的?

如何计算 count?影响 count 结果的因素有哪些?

count 值存在哪里?涉及的数据结构是怎样的?

为什么 InnoDB 只能通过扫表来实现 count( * )?(见本文最后的问题)

全表COUNT( * )作为 table scan 类型操作的一个 case,有什么风险?

COUNT(* )操作是否会像SELECT *一样可能读取大字段涉及的溢出页?

1. 执行框架 – 循环: 读取 + 计数

1.1 基本结论

全表扫描,一个循环解决问题。

循环内: 先读取一行,再决定该行是否计入 count。

循环内是一行一行进行计数处理的。

1.2 说明

简单 SELELCT-SQL 的执行框架,类比 INSERT INTO … SELECT 是同样的过程。

深入理解select count(*)底层究竟做了什么

下面会逐步细化如何读取与计数 ( count++ ) 。

2. 执行过程

引述: 执行过程部分,分为 4 个部分:

COUNT( * )前置流程: 从 Client 端发 SQL 语句,到 MySQL-Server端执行 SELECT 之前,为后面的一些阐述做一铺垫。

COUNT( * ) 流程: 简要给出代码层面的流程框架及 2 个核心步骤的重点调用栈部分。

读取一行: 可见性及 row_search_mvcc函数,介绍可见性如何影响 COUNT( * ) 结果。

计数一行: Evaluate_join_record与列是否为空,介绍计数过程如何影响 COUNT( * )结果。

如果读者希望直接看如何进行 COUNT( * ),那么也可以忽略 (1),而直接跳到 (2) 开始看。

2.1 COUNT( * ) 前置流程回忆 – 从 Client 端发 SQL 到 sub_select 函数

为了使看到的调用过程不太突兀,我们还是先回忆一下如何执行到 sub_select函数这来的:

深入理解select count(*)底层究竟做了什么

1.MySQL-Client 端发送 SQL 语句,根据 MySQL 通信协议封包发送。

2.Mysql-Server端接收数据包,由协议解析出 command 类型 ( QUERY ) 及 SQL 语句 ( 字符串 ) 。

3.SQL 语句经过解析器解析输出为 JOIN类的对象,用于结构化地表达该 SQL 语句。

PS: 这里的 JOIN 结构,不仅仅是纯语法结构,而是已经进行了语义处理,粗略地说,汇总了表的列表 (table_list )、目标列的列表 (target_list )、WHERE 条件、子查询等语法结构。在全表 COUNT( * )-case 中,table_list = [表“t”(别名也是“t”)],target_list = [目标列对象(列名为“COUNT( * )”)],当然这里没有 WHERE 条件、子查询等结构。 

4.JOIN对象有 2 个重要的方法: JOIN::optimize(), JOIN::exec(),分别用于进行查询语句的优化 和 查询语句的执行。

join->optimize(),优化阶段 (稍后 myisam 下全表 count( * )操作会涉及这里的一点内容)。  

join->exec(),执行阶段 ( 重点 ),包含了 InnoDB 下全表count( * ) 操作的执行流程。  

5.join->exec() 经过若干调用,将调用到sub_select函数来执行简单 SQL,包括 COUNT( * ) 。

6.END of sub_select 。

2.2 COUNT( * ) 流程 ( 于 sub_select 函数中 )

上层的流程与代码是比较简单的,集中在 sub_select 函数中,其中 2 类函数分别对应于前面”执行框架”部分所述的 2 个步骤 – 读取、计数。先给出结论如下:

1.  读取一行:从相对顶层的 sub_select 函数经过一番调用,最终所有分支将调用到 row_search_mvcc 函数中,该函数就是用于从 InnoDB 存储引擎所存储的B+-tree结构中读取一行到内存中的一个 buf (uchar * ) 中,待后续处理使用。

2.  这里会涉及行锁的获取、MVCC 及行可见性的问题。当然对 于 SELECT COUNT( * ) 这类快照读而言,只会涉及 MVCC 及其可见性,而不涉及行锁。详情可跳至“可见性与 row_search_mvcc 函数”部分。

3.  计数一行: 代码层面,将会在 evaluate_join_record函数中对所读取的行进行评估,看其是否应当计入 count中 ( 即是否要count++ )。

简单来说,COUNT(arg) 本身为 MySQL 的函数操作,对于一行来说,若括号内的参数 arg ( 某列或整行 )的值若不是 NULL,则 count++,否则对该行不予计数。详情可跳至“ Evaluate_join_record 与列是否为空”部分。

这两个阶段对 COUNT( * )结果的影响如下: (两层过滤)

深入理解select count(*)底层究竟做了什么

SQL 层流程框架相关代码摘要如下:

深入理解select count(*)底层究竟做了什么

Q: 代码层面,第一步骤(读取一行)有 2 个分支,为什么?

A:从 InnoDB 接口层面考虑,分为 “读第一行” 和 “读下一行”,是 2 个不同的执行过程,读第一行需要找到一个 ( cursor ) 位置并做一些初始化工作让后续的过程可递归。

正如我们如果用脚本/程序来进行逐行的扫表操作,实现上就会涉及下面 2 个 SQL:

阅读延展

1
3