select count(*)底层究竟做了什么?

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> select count(*)底层究竟做了什么?

select count(*)底层究竟做了什么?
作者:贾春生 blog.didiyun.com/index.php/2019/01/08/mysql-count/

blog.didiyun.com/index.php/2019/01/08/mysql-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(*)底层究竟做了什么?
  • `MySQL-Client` 端发送 SQL 语句,根据 MySQL 通信协议封包发送。
  • `Mysql-Server`端接收数据包,由协议解析出 `command` 类型 ( `QUERY` ) 及 SQL 语句 ( 字符串 ) 。
  • SQL 语句经过解析器解析输出为 `JOIN`类的对象,用于结构化地表达该 SQL 语句。
  • PS: 这里的  JOIN 结构,不仅仅是纯语法结构,而是已经进行了语义处理,粗略地说,汇总了表的列表 ( table_list )、目标列的列表 ( target_list )、 WHERE 条件、子查询等语法结构。
    在全表  COUNT( * )-case 中, table_list = [表“t”(别名也是“t”)] target_list = [目标列对象(列名为“COUNT( * )”)],当然这里没有  WHERE 条件、子查询等结构。

    在全表  COUNT( * )-case 中, table_list = [表“t”(别名也是“t”)] target_list = [目标列对象(列名为“COUNT( * )”)],当然这里没有  WHERE 条件、子查询等结构。

  • `JOIN`对象有 2 个重要的方法: `JOIN::optimize()`, `JOIN::exec()`,分别用于进行查询语句的优化 和 查询语句的执行。
  • join-optimize(),优化阶段 (稍后 `myisam` 下全表 `count( * )`操作会涉及这里的一点内容)。 join-exec(),执行阶段 ( 重点 ),包含了 `InnoDB` 下全表`count( * )` 操作的执行流程。

  • join-exec() 经过若干调用,将调用到`sub_select`函数来执行简单 SQL,包括 `COUNT( * )` 。
  • `END of sub_select` 。
  • 2.2 COUNT( * ) 流程 ( 于 sub_select 函数中 )

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

  • 读取一行:从相对顶层的 `sub_select` 函数经过一番调用,最终所有分支将调用到 `row_search_mvcc` 函数中,该函数就是用于从 `InnoDB` 存储引擎所存储的`B+-tree`结构中读取一行到内存中的一个 `buf (uchar * )` 中,待后续处理使用。 这里会涉及行锁的获取、MVCC 及行可见性的问题。当然对 于 `SELECT COUNT( * )` 这类快照读而言,只会涉及 MVCC 及其可见性,而不涉及行锁。详情可跳至“可见性与 `row_search_mvcc` 函数”部分。

  • 计数一行: 代码层面,将会在 `evaluate_join_record`函数中对所读取的行进行评估,看其是否应当计入 `count`中 ( 即是否要`count++` )。
  • 简单来说, COUNT(arg) 本身为 MySQL 的函数操作,对于一行来说,若括号内的参数  arg ( 某列或整行 )的值若不是 NULL,则  count++,否则对该行不予计数。详情可跳至“ Evaluate_join_record 与列是否为空”部分。

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

    select count(*)底层究竟做了什么?

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

    
    1210 enum_nested_loop_state
    
    1211 sub_select(JOIN *join, QEP_TAB *const qep_tab,bool end_of_records)
    1212 {
    1213   DBUG_ENTER("sub_select");
    
    ... ... // 此处省略1000字
    
    1265   while (rc == NESTED_LOOP_OK && join-return_tab = qep_tab_idx)
    1266   {
    1267     int error;
    // 第一步,从存储引擎中获取一行;
    1268     if (in_first_read)
    1269     {
    1270       in_first_read= false;
    // 第一步,首次读取,扫描第一个满足条件的记录;
    // 初始化cursor,从”头”扫描到某个位置
    // 类似: SELECT id FROM t LIMIT 1;
    1271       error= (*qep_tab-read_first_record)(qep_tab);
    1272     }
    1273     else
    // 第一步,后续读取,在前次扫描的位置上继续遍历,找到一个满足条件的记录;
    // 类似: SELECT id FROM t WHERE id  $last_id LIMIT 1;
    1274       error= info-read_record(info);
    
    ... ... // 此处省略1000字
    
    // 第二步,处理刚刚取出的一行
    1291       rc= evaluate_join_record(join, qep_tab);
    ... ... // 此处省略1000字
    1303   DBUG_RETURN(rc);
    1304 }
    

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

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

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

    
    // SELECT id FROM t LIMIT 1; OR SELECT MIN(id)-1 FROM t; - $last_id
    
    // SELECT id FROM t WHERE id  $last_id LIMIT 1;
    

    具体涉及到此例的代码,SQL 层到存储引擎层的调用关系,读取阶段的调用栈如下:(供参考)

    
    sub_select 函数中从 SQL 层到 InnoDB 层的函数调用关系:(同颜色、同缩进 表示同一层)
    
    Ø  (*qep_tab-read_first_record) ()
    
    | --  join_read_first(tab)
        | --  tab-read_record.read_record=join_read_next;
        | --  table-file-ha_index_init()
            | --  handler::ha_index_init(uint idx, bool sorted)
                | --  ha_innobase::index_init()
        | --  table-file-ha_index_first()
            | --  handler::ha_index_first(uint idx, bool sorted)
                | --  ha_innobase::index_first()
                    | --  ha_innobase::index_read()
                        | --  row_search_mvcc()
                        初始化cursor并将其放到一个有效的初始位置上;
    
    Ø  info-read_record (info)
    
    | --  join_read_next(info)
        | --  info-table-file-ha_index_next(info-record))
            | --  handler::ha_index_next(uchar * buf)
                | --  ha_innobase::index_next(uchar * buf)
                    | --  general_fetch(buf, ROW_SEL_NEXT, 0)
                        | --  row_search_mvcc()
                            “向前”移动一次cursor;
    

    我们可以看到,无论是哪一个分支的读取,最终都殊途同归于  row_search_mvcc函数。

    以上是对 LOOP 中的代码做一些简要的说明,下面来看  row_search_mvcc与  evaluate_join_record 如何输出最终的  count 结果。

    2.3 行可见性及 row_search_mvcc 函数

    这里我们主要通过一组 case 和几个问题来看行可见性对 COUNT( * ) 的影响。

    select count(*)底层究竟做了什么?

    Q:对于 SELECT COUNT( * ) FROM t或者 SELECT MIN(id) FROM t操作,第一次的读行操作读到的是表 t 中 ( B+ 树最左叶节点 page 内 ) 的最小记录吗?(  ha_index_first 为何也调用  row_search_mvcc 来获取最小 key 值?)

    A:不一定。即使是 MIN ( id ) 也不一定就读取的是 id 最小的那一行,因为也同样有行可见性的问题,实际上  index_read 取到的是 当前事务内语句可见的最小 index 记录。这也反映了前面提到的  join_read_first 与  join_read_next “殊途同归”到  row_search_mvcc 是理所应当的。

    Q:针对图中最后一问,如果事务 X 是  RU ( Read-Uncommitted ) 隔离级别,且  C-Insert ( 100 ) 的完成是在  X-count( * )执行过程中 ( 仅扫描到 5 或 10 这条记录 ) 完成的,那么  X-count( * ) 在事务  C-Insert ( 100 ) 完成后,能否在之后的读取过程中看到 100 这条记录呢?

    A:MySQL 采取”读到什么就是什么”的策略,即 X-count( * )在后面可以读到 100 这条记录。

    2.4 evaluate_join_record 与列是否为空

    Q:某一行如何计入 count?

    A:两种情况会将所读的行计入 count:

    1、如果 COUNT 函数中的参数是某列,则会判断所读行中该列定义是否  Nullable以及该列的值是否为  NULL;若两者均为是,则不会计入 count,否则将计入 count。

  • e.g. `SELECT COUNT(col_name) FROM t`
  • `col_name`可以是主键、唯一键、非唯一键、非索引字段
  • 2、如果 COUNT 中带有 * ,则会判断这部分的整行是否为 NULL,如果判断参数为 NULL,则忽略该行,否则  count++

  • e.g-1. `SELECT COUNT(*) FROM t`
  • e.g-2. `SELECT COUNT(B.*) FROM A LEFT JOIN B ON A.id = B.id`
  • Q: 特别地,对于  SELECT COUNT(id) FROM t,其中 id 字段是表 t 的主键,则如何?

    A:效果上等价于  COUNT( * )。因为无论是  COUNT( * ),还是  COUNT ( pk_col ) 都是因为有主键从而充分断定索取数据不为  NULL,这类 COUNT 表达式可以用于获取当前可见的表行数。

    Q: 用户层面对  InnoDB COUNT( * ) 的优化操作问题

    A:这个问题是业界熟悉的一个问题,扫描非空唯一键可得到表行数,但所涉及的字节数可能会少很多(在表的行长与主键、唯一键的长度相差较多时),相对的 IO 代价小很多。

    相关调用栈参考如下:

    
    参考一:
    
    evaluate_join_record()
    
    | --  rc= (*qep_tab-next_select)(join, qep_tab+1, 0);
        | --  end_send_group(...)
            | --  init_sum_functions(join-sum_funcs, join-sum_funcs_end[idx+1]))
                | --  (*func_ptr)-reset_and_add()
                    | --  Item_sum::aggregator_clear()
                    | --  Item_sum::aggregator_add()
            | --  update_sum_func(Item_sum **func_ptr)
                | --  (*func_ptr)-add()
                    | --  Item_sum::aggregator_add()
    
    参考二: (Item_sum::aggregator_add)
    
    ((Item_sum *) (*func_ptr))-aggregator_add()
    
    | --  (Item_sum *)this-aggr-add()
        | --  ((Aggregator_simple *) aggr)-item_sum-add()
            | --  if (! aggr-arg_is_null(false))
            | ------  ((Item_sum_count *)aggr-item_sum)-count++;
    

    二、数据结构:

    Q:count 值存储在哪个内存变量里?

    A:SQL 解析后,存储于表达  COUNT( * ) 这一项中, ((Item_sum_count*)item_sum)-count

    如下图所示回顾我们之前“ COUNT( * )前置流程”部分提到的 JOIN 结构。

    select count(*)底层究竟做了什么?

    即 SQL 解析器为每个 SQL 语句进行结构化,将其放在一个  JOIN 对象 ( join ) 中来表达。在该对象中创建并填充了一个列表  result_field_list 用于存放结果列,列表中每个元素则是一个结果列的 (  Item_result_field*) 对象 ( 指针 ) 。

    在  COUNT( * )-case 中,结果列列表只包含一个元素,(  Item_sum_count: public Item_result_field ) 类型对象 (  name = “COUNT( * )”),其中该类所特有的成员变量 count即为所求。

    三、MyISAM 全表 COUNT( * )

    由于  MyISAM引擎并不常用于实际业务中,仅做简要描述如下:

  • `MyISAM-COUNT( * )` 操作是 `O(1)` 时间复杂度的操作。
  • 每张`MyISAM`表中存放了一个 `meta` 信息-count 值,在内存中与文件中各有一份,内存中的 count 变量值通过读取文件中的 count 值来进行初始化。
  • `SELECT COUNT( * ) FROM t` 会直接读取内存中的表 t 对应的 count 变量值。
  • 内存中的 count 值与文件中的 count 值由写操作来进行更新,其一致性由表级锁来保证。
  • 表级锁保证的写入串行化使得,同一时刻所有用户线程的读操作要么被锁,要么只会看到一种数据状态。
  • 四、几个问题

    Q: MyISAM 与  InnoDB 在 COUNT( * ) 操作的执行过程在哪里开始分道扬镳?

  • 共性:共性存在于 SQL 层,即 SQL 解析之后的数据结构是一致的,count 变量都是存在于作为结果列的 `Item_sum_count` 类型对象中;返回给客户端的过程也类似 – 对该 count 变量进行赋值并经由 MySQL 通信协议返回给客户端。
  • 区别:`InnoDB` 的 count 值计算是在 SQL 执行阶段进行的;而 `MyISAM`表本身在内存中有一份包含了表 `row_count` 值的 `meta` 信息,在 SQL 优化阶段通过存储引擎的标记给优化器一个 `hint`,表明该表所用的存储引擎保存了精确行数,可以直接获取到,无需再进入执行器。
  • select count(*)底层究竟做了什么?

    Q:InnoDB 中为何无法向 MyISAM 一样维护住一个 row_count 变量?

    A:从 MVCC 机制与行可见性问题中可得到原因,每个事务所看到的行可能是不一样的,其  count( * )结果也可能是不同的;反过来看,则是  MySQL-Server 端无法在同一时刻对所有用户线程提供一个统一的读视图,也就无法提供一个统一的  count 值。

    PS: 对于多个访问 MySQL 的用户线程  ( COUNT( * ) ) 而言,决定它们各自的结果的因素有几个:

  • 一组事务执行前的数据状态(初始数据状态)。
  • 有时间重叠的事务们的执行序列 (操作时序,事务理论表明 并发事务操作的可串行化是正确性的必要条件)。
  • 事务们各自的隔离级别(每个操作的输入)。
  • 其中 1、2 对于 Server 而言都是全局或者说可控的,只有 3 是每个用户线程中事务所独有的属性,这是 Server 端不可控的因素,因此 Server 端也就对每个  COUNT( * ) 结果不可控了。

    Q: InnoDB-COUNT( * ) 属  table scan 操作,是否会将现有  Buffer Pool 中其它用户线程所需热点页从  LRU-list 中挤占掉,从而其它用户线程还需从磁盘  load一次,突然加重 IO 消耗,可能对现有请求造成阻塞?

    A:MySQL 有这样的优化策略,将扫表操作所  load的  page 放在  LRU-list 的  oung/old 的交界处 ( LRU 尾部约 3/8 处 )。这样用户线程所需的热点页仍然在  LRU-list-young 区域,而扫表操作不断 load 的页则会不断冲刷 old区域的页,这部分的页本身就是被认为非热点的页,因此也相对符合逻辑。

    PS: 个人认为还有一种类似的优化思路,是限定扫描操作所使用的  Buffer Pool 的大小为 O(1) 级别,但这样做需要付出额外的内存管理成本。

    Q: InnoDB-COUNT( * ) 是否会像  SELECT * FROM t 那样读取存储大字段的溢出页(如果存在)?

    A:否。因为  InnoDB-COUNT( * ) 只需要数行数,而每一行的主键肯定不是  NULL,因此只需要读主键索引页内的行数据,而无需读取额外的溢出页。

    据说,帅的人已经将这个公众号设为星标

    select count(*)底层究竟做了什么?select count(*)底层究竟做了什么?

    原文始发于微信公众号(后端技术精选):

    本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

    转载声明:转载请注明出处,本技术博客是本人原创文章

    本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

    原文链接:blog.ouyangsihai.cn >> select count(*)底层究竟做了什么?


     上一篇
    MySQL的使用及优化 MySQL的使用及优化
    前言最近听了公司里的同事做的技术分享,然后觉得对自己还是挺有帮助的。都是一些日常需要注意的地方,我们目前在开发过程中,其实用不到MySQL太深的内容的。只是能适用我们日常开发的知识就可以了。所以我将自己的理解和学习总结也写出来,供大家一起分
    下一篇 
    Mysql高性能优化规范建议 Mysql高性能优化规范建议
    点击上方“Java知音”,选择“置顶公众号” 技术文章第一时间送达! 作者:听风 cnblogs.com/huchong/p/10219318.html cnblogs.com/huchong/p/10219318.html