突破性能瓶颈：深度解析PolarDB-X列存分页查询原理（一）

分页查询介绍

在数据处理系统中，Top-K查询（分页查询）是一种常见且重要的操作，用于从大量数据中筛选出最具代表性或最重要的 K个结果。具体来说，Top-K查询 是指从一个数据集（例如一张数据库表）中按照某个特定的标准（如数值大小、时间戳、相关性评分等）进行排序，并返回排序后前K个记录。这类查询非常适用于以下场景：

• 排行榜（如分数排名、销售排名）
• 推荐系统（如推荐前K个相关的物品）
• 实时查询（如最新的K条新闻、最近的K个交易记录）

这些数据从数据源（一般是表文件）中读取，经过多轮复杂运算（如过滤、连接、投影），最后再对计算结果进行最大或最小K个值的筛选。

当数据源由大量文件组成时，传统的Top-K查询方法通常需要对所有文件进行全量扫描和筛选，再进行耗时的复杂计算，导致大量I/O和计算开销，尤其在分页查询（即用户需要逐页查看Top-K结果的不同部分）场景中，这种问题更加明显。

现有技术通常依赖于单线程逐个处理文件，缺乏并行处理能力，导致Top-K阈值形成较慢。此外，缺乏动态阈值更新机制，使得无法及时排除不在最终Top-K结果中的数据，进一步增加了I/O和计算负担。PolarDB-X通过多线程协同、动态阈值更新、优化文件扫描策略，达到提前终止读取与计算的效果，克服了现有技术的不足，显著提升对复杂查询进行分页的效率。

Top-K查询的语法

在SQL中，Top-K查询通常通过 ORDER BY 和 LIMIT 关键字实现。任何查询都可以在SQL语句的末尾添加如下子句：

ORDER BY col1 ASC|DESC, col2 ASC|DESC, ...
LIMIT offset, len

这是为了进行Top-K查询。其含义是先按照列 col1, col2, ..., colx 进行排序（ASC 表示升序，DESC表示降序），然后输出排序结果中从 offset 位置开始的 len 行数据。

又比如，下列SQL对R, S, T 表分别进行过滤，然后连接，最终按照R.col1 asc , R.col2 desc的顺序进行分页。

select * from R inner join S on S.A = R.A inner join T on T.B = R.B
where R.condition_1 and S.condition_2 and T.condition_3
order by R.col1 asc , R.col2 desc limit offset, len;

Part1. 并行Top-K实现

经典Top-K算法实现

下面是一种经典的Top-K算法实现，适用于单线程、小规模数据场景。

基于小顶堆的top-k算法

小顶堆是一种二叉堆树数据结构，其中每个节点的值都不大于其子节点的值。堆的堆顶，即根节点，始终是堆中的最小值。

利用堆（Heap）结构实现一个简单的Top-K算法，步骤如下：

1. 初始化一个大小为K的小顶堆H。
2. 对于数据集A，遍历输入每个元素A[i]到堆中，直到写满K个元素。此时堆顶元素为H[0]
3. 继续遍历输入数据集，此时，将每个元素与堆顶元素进行比较和替换：

• 如果当前元素大于堆顶元素，则将堆顶元素出堆，并将当前元素插入堆中。此时堆进行自动调整，选出新的堆顶元素。
• 否则，继续遍历下一个元素。

4. 遍历完成后，小顶堆中的K个元素即为数据集中最大（Top-K）元素。

比较与替换

上述算法的关键原理，也是第3步中“比较和替换”的基本思想是：

如果要求解一个集合中的Top-K元素集合，那么对于任意一个大小>=K的子集，如果元素小于该子集的第K大元素，则该元素必然不属于最终的Top-K元素集合。

在上述简单top-k算法实现中，大小为K的堆元素集合 $H=\{h_1,h_2,...h_k\},h_k<h_{k-1}<...<h_1$

那么集合H中的第K大元素，就是 $K_{th}\left(H\right)=h_k$

现在遍历数据集A中的元素A_i，和原本的堆元素集合组成一个新集合： $S=\{A_i,h_1,h_2,...h_k\}$

进行比较和替换，如果 $h_k<A_i$ ，并且结合前面所说的 $h_k<h_{k-1}<...<h_1$ ，那么必然有大小为K的新集合H'，且h_k小于新集合H'的第K大元素： $H^{{}^{\prime }}=\{A_i,h_1,h_2...h_{k-1}\},h_k<K_{th}\left(H^{{}^{\prime }}\right)$ ，此时h_k必然不属于最终的Top-K元素集合。

应用到Top-K查询

数据库如果要处理SQL中的Top-K子句： ORDER BY col1 ASC|DESC, col2 ASC|DESC,... LIMIT offset, len，最基本的办法是：

1. 求解Top-K问题，K=offset+len，构造一个大小为K的最小堆。
2. 构造一个比较器 comparator 用于包括堆排序内的所有比较操作。如果使用小顶堆数据结构，对于 SQL 中的 ORDER BY ... LIMIT offset, len 语义，若排序列为升序（ASC），则小顶堆的比较器需要使用反序；若为降序（DESC），则直接使用正序。

整体比较器实现的伪代码如下：

comparator(a, b) =
    (s1 * cmp(a.col1, b.col1) != 0) ? s1 * cmp(a.col1, b.col1) :
    (s2 * cmp(a.col2, b.col2) != 0) ? s2 * cmp(a.col2, b.col2) :
    ...
    (sN * cmp(a.colN, b.colN))

其中：

• cmp(x, y) 是基础比较函数（例如 x < y 则返回 -1，x > y 则返回 1，x = y 则返回 0）。
• si = -1 如果第 i 列是 ASC 排序。
• si = 1 如果第 i 列是 DESC 排序。

下文中所有的大小比较，都是通过上述比较器来实现的。

3. 在通过基于小顶堆的算法得到 Top-K 结果后，从中选择第 offset 行起的 len 条数据，作为最终的 SQL 结果输出。