Given the following SQL Schema,

CREATE TABLE If Not Exists point_2d (x INT NOT NULL, y INT NOT NULL)
Truncate table point_2d
insert into point_2d (x, y) values ('-1', '-1')
insert into point_2d (x, y) values ('0', '0')
insert into point_2d (x, y) values ('-1', '-2')

Table point_2d holds the coordinates (x,y) of some unique points (more than two) in a plane.

Write a query to find the shortest distance between these points rounded to 2 decimals.

| x  | y  |
|----|----|
| -1 | -1 |
| 0  | 0  |
| -1 | -2 |

The shortest distance is 1.00 from point (-1,-1) to (-1,2). So the output should be:

| shortest |
|----------|
| 1.00     |

Note: The longest distance among all the points are less than 10000.

SQL to compute the shortest distance from array of points

We know the math formula to compute the distance between two points is: sqrt((a.x – b.x)^2 + (a.y – b.y)^2.

Given an array of points, we want to brute force every point except itself to compute the minimal distance. We can connect the table to itself, however need to exclude the computation of the same point to itself, which is zero obviously.

select 
  round(min(sqrt(pow(a.x - b.x,2) + pow(a.y - b.y,2))), 2) as 'shortest'
from 
  point_2d a, point_2d b
where
  a.x != b.x or a.y != b.y

We might put the min function first, i.e. sqrt(min(…)), which might slightly be faster as the sqrt (square root) is computed only once.

The above could be rewritten in the SQL inner join query:

select
  round(sqrt(min(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2)))), 2) as shortest
from
  point_2d p1
join
  point_2d p2 on p1.x != p2.x or p1.y != p2.y;

SQL Improvement by Avoiding Duplication

The above SQL query actually computes the same pair of points twice, namely, (A, B) and (B, A) should be only computed once as the distance is exactly the same.

We can always assume doing the computing with a bigger X value, thus:

select 
  round(min(sqrt(pow(a.x - b.x,2) + pow(a.y - b.y,2))), 2) as 'shortest'
from 
  point_2d a, point_2d b
where
  (a.x != b.x or a.y != b.y) and
  (a.x >= b.x)

Or, in the form of connecting two tables:

select 
  round(min(sqrt(pow(a.x - b.x,2) + pow(a.y - b.y,2))), 2) as 'shortest'
from 
  point_2d a, point_2d b
where
  (a.x != b.x or a.y != b.y) and
  (a.x >= b.x)

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
最大公约数和最小公倍数　 富兰克林的遗嘱　 听出言外之意——一道三年级的数学题　 中国剩余定理经典题目——韩信点兵　 《孙子算经》中的剩余定理题　 九头鸟问题　 一道相遇问题　 三女归家问题——出处《孙子算经》　 买车的分数问题　 数列求和之公式求和