从Tournament Sort到MySQL深翻页与ByteSlice：数据库性能优化主线

DARTS#01这期我把三个看起来很散的词凑到了一起Tournament Sort算法、MySQL深度翻页优化、字节切片编码论文ByteSlice。如果你只是被其中一个词吸引点进来我也建议把另外几节扫完因为它们其实是同一根技术主线上的三段基础算法决定你对排序的直觉SQL改写解决你手头的线上问题论文则给你往后看两三年的视野。这是DARTS系列的第一篇后面会沿用这种“一道算法、一个工程优化、一篇论文速读”的格式。1. 为什么把排序算法、翻页优化和一篇论文放在同一期1.1 DARTS的定位和选题逻辑做这个系列的初衷很简单我发现很多做后端开发和数据库维护的人知识结构往往是“点状”的——懂索引、懂EXPLAIN、懂几条优化SQL但碰上复杂问题还是很难串成一条线。今天这条线是“数据如何被排序、如何被翻页、如何被压缩存储”。三个看似无关的话题其实都指向数据库吃不消时的典型场景。排序算法是数据库执行计划的地基MySQL的filesort和外部归并都建立在树形比较结构上深度翻页是OLTP系统最常见的性能杀手一条只取20行的查询能把机器拖到IO瓶颈ByteSlice则是OLAP列式存储里的编码思路让你理解列存为什么能在海量数据上跑得比行存快一个数量级。1.2 三个关键词之间的隐藏主线我先说一个自己的体会调优MySQL查询从来不是背几条SQL写法就能解决的。你得先弄清楚数据库在执行这条SQL时把数据从磁盘搬进内存后做了什么。Tournament Sort是“怎么用最少的比较找出最小值”的算法答案深度翻页优化是“怎么让数据库少做无用功”的工程答案ByteSlice是“怎么让数据在磁盘上占更少空间、扫描时读更少字节”的存储答案。三条答案放在一起才是一份完整的性能优化认知框架。1.3 适合谁来读这篇文章如果你是后端开发建议重点看第3章和第4章里面是可落地的SQL改写方案如果你是准备面试的候选人第2章的算法推导和第5章的论文拆解可以给你提供不错的谈资如果你已经在维护千万级数据表那第3章的量化分析可能能解释你上周遇到的那次慢查询。整体阅读大概需要15分钟代码可以直接抄。2. Tournament Sort树形选择排序如何点亮外部归并2.1 从简单选择排序到锦标赛为什么要两两对战先回忆一下最简单的选择排序每次线性扫描整个数组找到最小值把它放到结果数组里下次再扫描剩余部分。这个算法的问题很明显——找第k个最小值时前面比较过的信息全部丢弃下次又要从头比一遍。n个元素找最小平均要比较n/2次找n个最小值总比较量就变成O(n²)。Tournament Sort的思路是既然要反复找最小值那把每一轮比较的“胜者”记录下来避免重复劳动。这就像世界杯淘汰赛32支球队决出冠军不是让每支球队和其他31支都打一场而是两两分组、胜者晋级最后只需要31场比赛就能知道谁是冠军。选出冠军后如果想让亚军的产生也高效只需要重新比较冠军所在那条晋级路径上的球队即可。放到数组里先让所有元素两两比较产生一组胜者胜者再两两比较依次向上形成一棵完全二叉树。树的根节点就是全局最小值。取出根节点后把对应叶子节点置为正无穷再沿着这条路径重新比较一次新的根节点就是第二小的值。这个过程保证每次取出一个有序值只需进行log₂n次比较。2.2 时间复杂度与堆排序、归并排序的对比建树阶段需要n-1次比较之后每次选出一个最小元素需要约log₂n次比较整体时间复杂度和堆排序一样是O(n log n)。但空间上锦标赛排序需要额外的一棵二叉树属于非原地算法这是它不如堆排序普及的主要原因。不过在工程上锦标赛思想有一个堆排序替代不了的变体多路归并。外部排序把大文件拆成多个有序段后需要把k个有序段合并成一个有序段。每次从k个段的头部选最小值如果用线性扫描是O(k)但如果用败者树胜者树的对称版本只需要O(log k)。MySQL filesort产生临时文件后的归并阶段以及各种数据库的external merge sort底层都是这个套路。这也是为什么我始终觉得Tournament Sort不是一道孤立的算法题。它表面上是一棵二叉树实际上是连接选择排序、堆排序、归并排序三者的桥梁。理解了它你对“排序”这两个字的理解就不再是调用一个sort函数而是明白在内存放不下时算法如何被迫改变形态。2.3 MySQL ORDER BY里的树形排序影子MySQL执行ORDER BY时会先看排序字段能不能直接走索引。能走索引B树本身维护了有序性直接顺序扫描返回即可。不能走索引就需要filesort。filesort不是真的“文件排序”它优先使用内存中的sort buffer默认sort_buffer_size通常为256KB或更大。当sort buffer放不下全部数据时MySQL会把数据分成多个块每块内部排序后写成临时文件最后对这些有序临时文件做多路归并。多路归并的每一步就是从每个有序块中取当前最小再比较选出全局最小这正是锦标赛思想的经典应用。还有一个容易被忽略的细节当查询带ORDER BY和LIMIT时MySQL 8.0会尝试用优先队列堆来优化排序只维护LIMIT大小的堆而不是把所有行都排好序。这种做法的时间复杂度是O(n log m)m是LIMIT大小n是参与排序的行数。如果你只需要前20条它绝不会傻到把100万行全部排完再截断。理解这一点对后面深度翻页优化很有帮助。2.4 一个最小的锦标赛排序演示我用Python写了一个最直白的演示版本只为展示算法骨架生产代码不建议这么写。def tournament_sort(arr): n len(arr) size 1 while size n: size 1 tree [float(inf)] * (2 * size) tree[size:size n] arr # 自底向上建树比较得到冠军 for i in range(size - 1, 0, -1): tree[i] min(tree[2 * i], tree[2 * i 1]) res [] for _ in range(n): v tree[1] res.append(v) # 定位冠军对应的叶子置为无穷大后重新向上比较 pos next(i for i in range(size, 2 * size) if tree[i] v) tree[pos] float(inf) pos // 2 while pos: tree[pos] min(tree[2 * pos], tree[2 * pos 1]) pos // 2 return res注意这个实现用next线性查找冠军叶子所以实际复杂度不够严谨只适合演示原理。工程实现需要用一个left/right数组记录每轮比赛赢家来自哪个分支或者用败者树降低更新代价。演示代码的核心意图是让你看到“每次只更新冠军路径”这件事——这是整个算法最精华的部分。3. MySQL深度翻页的真实成本从回表到临时文件3.1 一条LIMIT 1000000, 20背后的物理操作先给一个具体的慢查询现场还原。假设我在维护一张订单表orders已经积累到200万行业务端做了一个分页列表页用户翻到第5万页时前端发起的就是这种请求SELECT id, user_id, amount, created_at FROM orders WHERE status 1 ORDER BY created_at DESC LIMIT 1000000, 20;这条SQL的意图是跳过前100万行取接下来的20行。但数据库的执行计划不会聪明到“直接从某个位置开始读”它必须老老实实扫描到第1000020行再丢弃前面的1000000行。等于你点了一个20行的外卖厨师把前面100万份菜全部炒了一遍然后倒掉。如果ORDER BY的字段没有索引MySQL还会先把所有满足status1的行读出来做filesort。更坏的情况是排序的列不在索引里需要回表读取完整数据行再把数据放进sort buffer排序完成后再次回表取列。光是回表这一步就可能触发几十万次随机IO。3.2 用EXPLAIN和实测数据还原慢查询现场在我本机测试环境里MySQL 8.0orders表约200万行innodb_buffer_pool_size设了1GB执行上面的SQLEXPLAIN结果大致是这样的EXPLAIN SELECT id, user_id, amount, created_at FROM orders WHERE status 1 ORDER BY created_at DESC LIMIT 1000000, 20;列值typerefrows约1850000filtered100.00ExtraUsing index condition; Using filesortrows估算185万这还只是估算值。实际执行时由于需要把185万行读进sort buffer并做外部排序耗时轻松超过900ms。随着offset继续增大扫描范围还会线性增长。如果把offset换成2000000这条查询可能直接变成秒级。EXPLAIN里出现Using filesort意味着排序过程没有索引可用。即使有二级索引支撑回表的次数也会被放大到“offsetlimit”的规模。这就是为什么很多报表接口翻到后面会越来越慢不是数据库变卡了而是每次翻页都在重复做同样的超大排序和超大跳跃。3.3 翻页越深越慢的三个放大因素第一个是回表放大。InnoDB的二级索引只存索引列和主键要取其他字段必须回到聚簇索引。深翻页时回表次数接近offset这些回表操作对散落的随机主键发起读取在没有被缓存的情况下每次都可能是物理IO。第二个是排序放大。如果排序字段没有索引参与排序的是全部满足条件的行而不是从第1000000行开始的20行。这意味着一半以上的数据被读进sort buffer又被写出临时文件做了大量无意义的排序工作。第三个是重复计算。分页接口每次翻页都是独立SQL上一页产生的排序结果和扫描位置完全不被重用。用户连续翻10页数据库就做10次几乎一样的全量排序。页数越深这个重复成本越离谱。想解决深翻页就得从这三个放大因素下手减少回表、减少排序规模、消灭大offset。4. 针对深度翻页的SQL改写方案与适用边界4.1 延迟关联用覆盖索引先缩小回表范围延迟关联的核心思路是先用最小代价查出这一页需要的20个主键再用主键回表取完整数据。最小代价怎么实现让子查询的WHERE、排序字段、主键都在同一个覆盖索引里。对上面的例子先建一个联合索引(status, created_at, id)或者(created_at, id)然后改写SQLSELECT o.* FROM ( SELECT id, created_at FROM orders WHERE status 1 ORDER BY created_at DESC LIMIT 1000000, 20 ) AS t JOIN orders o ON o.id t.id ORDER BY t.created_at DESC;子查询只扫描覆盖索引不需要回表取出所有列索引天然有序Using filesort会消失LIMIT阶段处理的都是索引页的小记录占用sort buffer非常少。拿到20个主键后再JOIN原表只做20次聚簇索引查询。我实测这条改写语句耗时降到约55ms和之前的900ms相比几乎不是一个量级。注意外层又加了一个ORDER BY t.created_at DESC因为JOIN是乱序匹配的如果业务要求保持分页顺序需要在外层重新排序。子查询里同时select id和created_at是为了外层能够稳定排序。4.2 游标分页让offset从SQL里消失延迟关联依然要扫描offset之前的100万个索引项虽然比回表全行快但offset继续增大到百万、千万时还是会感觉到压力。真正让深翻页成本恒定的是游标分页也叫keyset分页。思路很简单客户端记住上一页最后一条记录的排序字段和主键下一页从这条记录后面接着取。SQL写成这样SELECT id, user_id, amount, created_at FROM orders WHERE status 1 AND (created_at, id) (:last_created_at, :last_id) ORDER BY created_at DESC, id DESC LIMIT 20;联合索引(status, created_at, id)可以直接支撑这个查询。数据库通过索引定位到游标位置然后顺序向后扫描20行整个过程与offset完全没有关系。不管当前在第几页查询时间都稳定在个位数毫秒级别。这个方案最痛的点在于不支持常见的页码跳转。产品要做“跳到第100000页”这种需求游标分页就无能为力了。所以它更适合信息流、下拉加载、按时间线浏览这类“只关心下一页”的场景。我的建议是新项目优先按游标分页设计接口老项目如果需要兼容页码至少把延迟关联用起来。4.3 覆盖索引与稳定排序的细节还有一个常见陷阱如果排序字段不是唯一列比如排created_at时同一秒有几十条记录那么分页结果可能在不同页之间出现重复或遗漏。解决方案也很简单排序条件里同时带上主键让排序组合(created_at, id)成为唯一序。前面游标分页的SQL已经通过(id :last_id)体现了这一约束延迟关联的SQL也要确保子查询里按created_at, id并列排序。如果你只需要返回排序字段本身和主键不想接业务字段覆盖索引查询就够了SELECT id, created_at FROM orders WHERE status 1 ORDER BY created_at DESC, id DESC LIMIT 1000000, 20;这种方式几乎没有回表成本可以当成一个轻量的数据导出查询。但实际业务列表几乎总是要展示多个字段所以延迟关联仍然是更通用的做法。4.4 不同深翻页场景的选型对照我整理了一个决策表按业务场景直接选即可场景首选方案原因备选方案用户点页码可跳转延迟关联兼容任意页实现成本低缓存热点页信息流/瀑布流加载游标分页成本恒定体验最顺滑延迟关联兜底数据导出/后台任务覆盖索引避免回表速度最快游标分页排序字段非唯一游标分页主键竞态保证稳定不重不漏延迟关联复合排序字段一句话总结只要有办法绕过offset就别用offset如果必须支持跳页那就把扫描成本从全行回表降为覆盖索引扫描这是性价比最高的折中。5. ByteSlice论文精读字节切片编码的设计与收益5.1 论文在解决什么问题如果说前面两章是在“减少数据库做的无用功”ByteSlice思考的是更底层的事数据以什么形态放在磁盘上才能让扫描更快。传统行式存储按行存数据读一行就要把整行的所有字段读出来即使你只需要其中两列。列式存储则把同一列的数据连续存放扫描时只需要读取目标列天然节省大量IO。但连续存放只是第一步。分析型查询往往要扫描几亿行数值数据即使只读一列数据量依然巨大。ByteSlice就是针对这类定长数值列提出的一种编码与其把每个整数看成一个整体去压缩不如把每个整数的字节拆开按字节位置分组成连续切片再对每个切片做更有效的压缩。这套思路之所以有效是因为数值数据存在天然的字节分布规律。举个例子int32正数的高位两个字节通常全是0int64负数的最高位字节又往往是0xFF。把这些高位字节放在一起你会发现它们的形式非常单一非常容易被压缩。5.2 编码过程拆解从列数据到字节切片我用一组具体数字演示ByteSlice的处理过程。假设一列int32数据为[1024, 1025, 4096, 4097]小端序下每个数占4字节1024 - 00 04 00 001025 - 01 04 00 004096 - 00 10 00 004097 - 01 10 00 00ByteSlice不是按行存这4个整数而是按字节偏移重新组织切片内容特点第0字节切片00 01 00 01低位字节变化较随机第1字节切片04 04 10 10基数低适合bit-packing第2字节切片00 00 00 00全零直接标记跳过即可第3字节切片00 00 00 00全零直接标记跳过即可第2、第3字节切片全是0根本不需要存储第1字节切片只有两个不同取值可以用很小的bit宽度做位打包第0字节切片数值分布相对分散但也可以配合Delta编码或Varint压缩。查询时也不需要解码全部切片。比如你要过滤 x 3000可以先看高字节切片如果高字节部分已经说明该值大于或小于阈值就不用继续处理低位切片。这种按切片级别的Skip逻辑配合SIMD能够在扫描初期就排除大量不满足条件的行。5.3 与RLE、字典、Delta编码的横向对比ByteSlice不是唯一的选择。数据库列存中常见的编码还有几种编码适合的数据特征优点缺点RLE行程编码连续重复值压缩率极高数据乱序时失效Dictionary基数低的字符串/枚举查询友好高基数场景开销大Delta单调递增的时间戳/ID差值小存储紧凑对波动大的数据效果差ByteSlice数值分布集中、高位重复压缩率高且支持随机过滤只适用于定长数值实现复杂ByteSlice最大优势在于它不依赖数据的排列顺序不需要相邻值相同或递增只要数值在字节层面有模式就能获得压缩收益。这在真实业务里是很常见的价格、年龄、数量、状态码这些字段往往数值范围不大但行与行之间未必有规律。5.4 代价与适用边界ByteSlice不是没有成本。它要求列是定长数值类型对VARCHAR/字符串类型基本无能为力随机写入场景字节切片后会破坏一行数据的连续性更新一小块数据可能涉及多个切片的修改代价很大实现层面编码器和解码器都要处理位偏移、切片切分、bit-packing对齐等细节没有成熟的库支持时开发成本不低。所以ByteSlice更适合OLAP系统里的只读或追加写表而不是高并发OLTP。很多列式存储引擎之所以选择它是因为分析型查询注重扫描吞吐而OLTP的点查和更新场景完全用不上这种编码。理解这个边界比记住编码本身更重要。这类“字节切片”思想给我的启发是数据的物理布局直接影响查询性能。你在设计MySQL表时如果能把高频查询的少量字段放在一个宽表里减少无谓的大字段读入本质上也是在用更窄的数据布局换取更快的扫描速度。6. 三个主题连起来看一条数据库性能优化主线6.1 算法阶段排序的优化空间在哪里回到Tournament Sort。它告诉我们的第一件事是排序不是一件一锤子买卖的事信息可以复用。数据库index有序扫描、filesort的优先队列优化、外部归并的败者树全部建立在这个认知之上。日常写SQL时如果你发现ORDER BY在慢查询里出现先别急着加缓存。问自己三个问题排序字段能不能命中索引LIMIT能不能和ORDER BY一起告诉优化器让它使用堆排序而不是全量排序排序字段是不是唯一的能不能加上主键保证稳定大多数排序慢的问题问完这三个问题就解决了七成。6.2 工程阶段把查询改成可预期的低成本路径深度翻页优化给我们的工程启发是查询性能应该可预期而不是依赖数据量碰运气。用游标分页后不管第100页还是第10000000页查询时间都维持在几毫秒用延迟关联后回表次数从offsetlimit降为limit。这些手段的核心都是把“不确定的全表扫描”改成“确定的索引定位”。我见过不少团队花大价钱加缓存、上搜索引擎却忽略了把深翻页SQL改成游标分页这种只需要半天就能完成的改造。优化是有顺序的先改SQL和索引再考虑架构层缓存。前者往往是性价比最高的。6.3 进阶阶段用存储编码反向影响查询设计ByteSlice让我意识到数据库性能优化不仅有“查询层”和“索引层”还有“存储层”。同样的数据以行存、列存、字节切片、字典压缩等不同形式存放查询性能可能差出两个数量级。作为应用开发者虽然很难直接去改InnoDB的存储格式但在做表结构设计时可以借鉴这种思想尽量让行窄一些、让热点列集中一些、避免无意义的宽表和大字段查询。在线业务如果确实需要大范围报表查询该考虑把数据同步到分析型引擎时也可以优先选择支持列存和字节级编码的方案。这不是让你抛弃MySQL而是知道在什么场景下什么样的存储形态更适合。6.4 一点个人实操体会这三个主题我是在一次线上事故里串起来的。当时业务报表接口在深翻页后频繁超时我第一反应是加索引加了还是慢才开始研究EXPLAIN、回表、覆盖索引最后用延迟关联把耗时降了下来。后来去读列存编码相关的论文才意识到自己过去对“数据如何存放”的理解一直停留在表结构层面对物理布局和编码收益几乎没有概念。这段经历让我形成了一个固定习惯每遇到一个性能问题先想清楚它属于算法问题、执行计划问题还是存储表示问题再决定怎么下手。这个习惯比任何具体SQL技巧都管用。DARTS系列后续也会继续沿着“算法基础、工程优化、论文精读”这个三明治结构来写下一期打算聊聊Hash Join的底层设计以及在真实业务里如何选择Join策略。