TopK算子技术背景

业务系统中普遍存在这样一种场景：根据给定条件筛选一批记录，这些记录按用户指定的条件排序，以分页的方式展示。例如，筛选出某个商家在售的商品，按商品销量排序，以分页的方式展示。上述场景在数据库中，通常以ORDER BY column LIMIT n, m这样的查询语句实现。

假设业务系统中每页展示100条记录：

• 通过ORDER BY column LIMIT 0, 100可以展示第1页的数据；
• 通过ORDER BY column LIMIT 1000000, 100可以展示第10001页的数据。

在没有索引的情况下，此类查询在数据库中是通过基于堆的经典TopK算法来实现的，逻辑如下：在内存中维护一个大小为K的堆，堆顶元素是最小的元素，将遍历到的数据与堆顶元素比较，如果比堆顶元素大，替换堆顶元素，并重建堆。遍历完数据后，堆中的元素即为前K个最大的元素。当翻页较浅时（如上文中展示第1页），K较小，基于堆的TopK算法非常高效。

然而，业务场景中也存在翻页较深的场景（下文中简称“深翻页”），例如上文中展示第10001页。该场景下的K非常大，内存中可能无法缓存大小为K的堆，也就无法使用上述方式获得查询结果。即便内存充足，由于维护堆的操作访问内存是乱序的，当堆非常大时，TopK算法的访存效率较差，最终的性能表现也差强人意。

PolarDB MySQL版IMCI最初也采用了上述方式来实现分页查询，并在内存不足以缓存大小为K的堆时，采用了全表排序后取相应的位置记录的方式，所以在深翻页时的性能表现也不是非常理想。为此，在分析了深翻页场景的特点和传统方案存在的问题，并调研了相关研究和工业界现有方案后，PolarDB MySQL版重新设计了IMCI的Sort/TopK算子。在测试场景中，重新设计的Sort/TopK算子显著提升了IMCI在深翻页场景的性能表现。