《大规模分布式计算深入解析》6.2 TopN 下推与局部 TopN

局部 TopN 的安全性来自同一比较器下的排名支配关系。带 OFFSET 或 WITH TIES 时,候选边界需要扩展。

6.2 TopN 下推与局部 TopN

局部 TopN 的安全性来自同一比较器下的排名支配关系。带 OFFSET 或 WITH TIES 时,候选边界需要扩展。

保留足够的候选

flowchart TB
  Q["分析 ORDER BY、OFFSET、LIMIT、WITH TIES"] --> T{"能证明局部候选覆盖全局结果?"}
  T -->|"按同一比较器,普通 LIMIT"| L["每个任务保留 OFFSET + LIMIT"]
  T -->|"存在边界并列"| W["保留并列或按全局边界补取"]
  T -->|"不能证明覆盖"| S["做全局排序或完整归并"]
  L --> M["归并局部有序候选"]
  W --> M
  M --> O["应用全局 OFFSET 和输出规则"]
  S --> O

在统一全序下,局部排在第 K 名之后的行,在本分区已有至少 K 条行领先,因此不能进入全局前 K。普通 LIMIT 100 可每个任务保留 100 条,16 个任务至多合成 1600 条。对 OFFSET 2 LIMIT 1,局部应取 3 条,再执行全局切片。实验中局部只取 1 条会使最终结果为空。WITH TIES 按声明的排序键判断同名次,需要保留边界并列或在确定边界后补取,不能增加改变 SQL ties 语义的隐式键。

区分估算与测量

每个任务处理 625 万行,取 n × ceil(log2(100)) 的教学比较模型,约 4375 万次/任务。对 1600 候选跑 16 路平衡二路完整归并,模型约 6400 次,是单个任务局部模型的 0.0146%。实际的堆算法会先与堆顶比较,多路归并还可以提前停止。测量时核对每个 Task 候选数、是否避免外排、全局输出和实际比较成本代理指标。

实验与资料

下载卷六实验包 ,参照包内 README。src/ 下的 Java 8 教学模型 · sql-counterexamples.py 的语义对照。

Trino SELECT 的 ORDER BY、OFFSET 与 FETCH · Trino Connector 下推

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图