先问一个问题。五年前在tx的时候，发现分页场景下mysql的请求速度很慢。在数据量只有10w的时候，单机selectxx大概需要2、3秒。我问导师为什么，他反问：“在索引场景下，mysql中获取第n大数的时间复杂度是多少？”对答案的追求证实了场景假设状态有一个索引。select*fromtablewherestatus=xxlimit10offset10000.会很慢。如果数据量不大，会有几秒的延迟。小白猜答案中的log(N)，认为找到一个节点会是log(N)。很自然地，导师让我自己做研究。这个阶段用了10分钟。继续认真回答分析，你会发现通过索引查找很别扭。因为不知道左子树和右子树前100个数的分布，所以无法利用二叉树的查找特性。通过学习了解到mysql的索引是b+树。看到这张图，我顿时豁然开朗。通过叶子节点组成的链表可以直接找到复杂度为O(n)的第100大树。但即使它是O(n)，它也不是非常慢，这是有原因的。这个阶段主要是上网查资料，断断续续用了10天。这里推荐两本书系统学习，一本《MySQL技术内幕 InnoDB存储引擎》，通过它可以更深入的了解InnoDB的实现机制，比如mvcc、索引实现、文件存储等。第二本书是《高性能MySQL》。本书从使用层面入手，但更深入，提到了很多设计思路。结合两本书，反复理解，mysql勉强可以入室。这里有两个关键概念：聚簇索引：包含主键索引和对应的实际数据，索引的叶子节点是数据节点的辅助索引：可以理解为二级节点，它的叶子节点也是一个索引节点，其中包含主键id。即使前10000条会被扔掉，mysql也会通过二级索引上的主键id来检查聚簇索引上的数据。这是10000个随机ios，自然比哈士奇慢。这里可能会有疑问，为什么会出现这样的行为，这跟mysql的分层有关，limitoffset只能应用于引擎层返回的结果集。也就是说，引擎层也很无辜，他不知道这一万要扔掉。下面是mysql分层的示意图。可以看到引擎层和服务器层其实是分开的。直到这个时候，我大概明白了慢的原因。这个阶段用了一年。以此类推，此时我工作了3年，也开始看一些源码。看完etcd，又看了一些tidb的源码。不管是哪种数据库，其实一条语句的查询都是由逻辑运算符组成的。逻辑运算符介绍在编写具体的优化规则之前，我们先简单介绍一下查询计划中的一些逻辑运算符。DataSource这个是数据源，也就是表，select*fromt中的t。Selection选择，比如selectxxxfromtwherexx=5中的where过滤条件。Projection投影，selectcfromt选择c列是一个投影操作。joinconnection,selectxxfromt1,t2wheret1.c=t2.c是joint1和t2的两张表。Selection,projection,join（简称SPJ）是最基本的算子。其中Join有内连接、左外右外连接等多种连接方式。selectbfromt1,t2wheret1.c=t2.candt1.a>5成为逻辑查询计划后，由t1和t2对应的DataSource负责取数据。上面连接一个Join算子，根据t1.c=t2.c连接两个表的结果，然后根据t1.a>5进行Selection过滤，最后投影b列。下图是一个未优化的表现：不是mysql不想把limit和offset传递给引擎层，而是因为逻辑运算符的划分，无法确定具体的运算符包含多少符合条件的数据。如何解决《高性能MySQL》提到了两种解决方法。一是看下一页和上一页的功能是否可以根据业务的实际需要进行替换。尤其是ios和android端，以往完全分页的情况并不常见。这里是说，用>辅助索引（即搜索条件）id替换limit，offset。再次调用该id时，需要返回给前端。选项二是肯定的。这里有一个概念：索引覆盖：当辅助索引查询到的数据只有id和辅助索引本身时，那么就不需要再去查找聚簇索引了。思路如下：selectxxx,xxxfromin(selectidfromtablewheresecond_index=xxxlimit10offset10000)`这句话的意思是首先从条件查询中，找到数据对应的数据库的唯一id值，因为主键在辅助索引上面，所以不需要回到聚集索引的磁盘上去拉。然后使用已经限定的10个主键id查询聚簇索引。这样，只会进行十次随机io。在业务确实需要使用分页的情况下，使用这种方案可以大大提高性能。通常满足性能要求。来源|https://juejin.cn/post/684490...
