为何该SQL语句必须用ORDER BY？LeetCode 613问题解惑

题目描述 #

编写SQL查询，找出Point表中任意两点之间的最短距离。表结构如下：

Point
+-------------+------+
| Column Name | Type |
+-------------+------+
| x           | int  |
+-------------+------+

x是该表的主键，每行代表X轴上一个点的位置。

我的错误解法 #

一开始我认为这是LEAD函数（偏移量为1）的直接应用，写出了如下解法：

SELECT MIN(dist) as shortest
FROM    (SELECT ABS(x - LEAD(x, 1, NULL) OVER () ) AS dist
        FROM POINT) AS dist_table;

我原以为OVER ()会让LEAD函数遍历所有行（排除重复行），但这个解法得到了错误结果。正确解法仅将OVER ()改为OVER(ORDER BY X)，这让我无法理解——我认为两种方式都会计算所有行的距离（排除相同行），恳请有人解释其中原因，我查阅多篇文章仍无收获。

问题原因解析 #

核心问题出在OVER()的行为上：

• 当使用OVER()时，窗口函数没有指定排序规则，数据库会按照数据存储的物理顺序或默认的无序逻辑处理行。这意味着LEAD(x,1)取的是当前行在无序结果集中的下一行，而非X轴上相邻的点。比如点的存储顺序是5,1,3，计算出的差值是|5-1|=4、|1-3|=2、|3-NULL|=NULL，但X轴上真正相邻的点对是1和3、3和5，最短距离是2；如果存储顺序混乱，甚至会漏掉关键的相邻点对，导致计算结果错误。
• 而OVER(ORDER BY X)会先将所有点按X值从小到大排序，此时LEAD(x,1)取的是当前点在X轴上的下一个相邻点。由于X轴上的最短距离必然出现在相邻点之间（比如三个点a<b<c，|a-c|肯定大于等于|a-b|或|b-c|），所以计算排序后相邻点的距离，再取最小值就是正确的最短距离。

简单来说，不排序时LEAD拿到的是随机的下一行，不是X轴上的相邻点，自然算不出正确结果；排序后相邻行对应X轴上的相邻点，此时计算的差值才是候选的最短距离。

内容的提问来源于stack exchange，提问作者FafaDog