原文是Stackoverflow上的一个问答，解释stackoverflow在如此大数据量的情况下，如何在关系型数据库上做到如此快的翻页查询的。个人觉得能对我们日常开发工作带来一些思考，在这里将大意转译出来（非原文翻译）。

问

stack overflow有上千万的问题，在翻页的时候，讲道理翻到后面时查询速度应该很慢才对。但stack overflow却很快。stack overflow是怎么做到分页查询这么快的？是缓存了所有热门问题并在应用层代码里排序吗？还是用了什么数据库黑魔法？

答

【答者是Haney，Stackoverflow核心团队的一个工程经理】
整个过程是比较复杂的，我会在这里尝试回答清楚避免写一篇长到跟权利的游戏最后一次游戏一样长的博客【恕我直言，您这里的回答已经可以当作一篇博客了】。

假设条件

为了方便讨论，我们假定翻页是基于pageNumber * pageSize这个公式来做的。那么，“拿到当前的一组问题”就是一个对n个问题进行排序的问题了，也就可以通过偏移pageNumber * pageSize然后从这个位置拿pageSize个问题就是当前翻页的问题了。在我们的事例里，偏移量是(pageNumber - 1) * pageSize，因为第一页的index是0。

在排序上，你永远也不需要对这个数据集进行排序。实际上，你只需要对前面pageNumber * pageSize的数据进行完全排序，而对剩下的数据进行部分排序（例如3路快排）就可以拿到当前页的问题了。

还有比较重要的一点：开销最大是查询中间的页。拿到最前的n页和拿到最后的n页代价是一样的，因为只需要把排序条件调转就可以了。大部分的排序引擎（数据库、搜索引擎等）都支持了这种排序优化，包括我们的系统。

为了方便这里的讨论，下文中有些地方会用Post这个概念来代替问题。

步骤一：标签引擎（Tag Engine）

我们有个用.NET写的Tag Engine用来保存post的id和相关的元信息。你可以把它理解为倒排索引，你可以通过诸如创建时间、标签、来源等信息查到相应的post id。

这个Tag Engine基于图论的谓词（Predicate）逻辑。它通过在内存中对post id做集合操作（交集、并集等）来得到最后的结果。

我们向Tag Engine传递page number、page size和限定数据集大小的谓词逻辑进行查询。它会在内存里进行集合操作，然后对结果进行排序，最后返回满足条件的post id子集。

Tag Engine会缓存结果（大的集合，不仅仅缓存请求的那一页），并且基于查询条件（页码、每页大小、排序方式等）的hash值来快速在缓存中快速获得查询的结果。这大大提高了查询性能。

步骤二：数据库

Tag Engine并不缓存实际的问题数据，只存了id和元数据。我们通过类似如下的sql用ids来查询SQL数据库来拿回需要的数据。

1
2
3
4
5
Select p.*, pm.ViewCount, u.Id, u.ProfileImageUrl, ...
From Posts p
    Join PostMetadata pm On p.Id = pm.PostId
    Left Join Users u On p.LastActivityUserId = u.Id
Where p.Id In @Ids";

这里的@ids是从上一步Tag Engine里获得的id列表。这样的查询拿回了用于展示的数据，但还没完。

步骤三：半冗余内存内排序（Semi-Redundant In-Memory Sort）【翻译出来怪怪的】

如上面讨论的，Tag Engine可能返回了缓存的数据。缓存数据是无法保证精确的，这是缓存的天性（缓存是事物过去某一状态的快照）。相对的，数据库永远是保存最新的、最权威的数据。所以有时两者会产生冲突。

为了解决这个问题，我们会对结果页的post再排序一次。这一步解决了这样一个问题，即结果页的post的元数据实际上已经更新到数据库而Tag Engine还没缓存到。

这一部分没有什么让人兴奋的内容，就是根据你浏览的tab页面来传不同的比较函数给List<T>.Sort。看Newesttab就比较post的创建时间，浏览Votes就比较score和答案votes数，等等。

如果不做这最后一步，post展现在页面上是可能不是有序的。因为Tag Engine用于排序的字段的值和当前数据库的值可能不一样。

最后，我们才把问题列表展示给你看。

原文中的问题和答案下面都有一些讨论，可以到原文中看看，这里就不译了。