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 下推
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。