查找列值接近当前行之一的行
Find rows with a column value close to the one of the current row
我有一个 table 格式如下：
id
lon
lat
1
10.111
20.415
2
10.099
30.132
3
10.110
20.414
我想创建一个新列，其中 returns 所有 ID 使得 lon 和 lat 小于公差值，即 abs(lon_i - lon_j) < tol AND abs(lat_i-lat_j) < tol i != j.
我最初的想法是创建 table 的临时副本，然后加入 table 并给出列的名称 lon_2、lat_2 , 然后:
SELECT id
FROM TABLE_1
WHERE ABS(TABLE_1.lon - TABLE_1.lon_2) < tol
AND ABS(TABLE_1.lat - TABLE_1.lat_2) < tol
但必须有更好、更有效的方法来处理它。
暂时不需要table。
您可以进行自我加入：
SELECT t1.id, t2.id
FROM tablename t1 INNER JOIN tablename t2
ON t2.id <> t1.id AND ABS(t1.lon - t2.lon) < :tol AND ABS(t1.lat - t2.lat) < :tol;
这将为满足条件的每对 id 生成 return 1 行。
如果您想要每个 id 满足条件的所有 id 的逗号分隔列表，那么您可以聚合并使用 STRING_AGG():
SELECT t1.id, STRING_AGG(t2.id, ';' ORDER BY t2.id)
FROM tablename t1 INNER JOIN tablename t2
ON t2.id <> t1.id AND ABS(t1.lon - t2.lon) < :tol AND ABS(t1.lat - t2.lat) < :tol
GROUP BY t1.id;
all IDs such that lon and lat are less then a tolerance value away
一个简单的自连接就可以解决这个问题。
但是，简单查询必须在消除给定公差之外的对之前计算两行的每个 组合的增量。基本上是一个 Cartesian Product， 与 O(N²) 的关系非常大。如果您的 table 不小，请继续阅读。
目标是得到O(N)。我们将使用一些高级概念：
- 最近邻搜索
- GiST 表达式索引
LATERAL加入- 递归 CTE
最近邻查询
如果您不熟悉，这里是Nearest-Neighbour Searching with PostGis的介绍（您的地理编码可能正在使用它？）。
无论哪种方式，我们都可以对现有 Postgres 中的类型 point 执行相同的操作。我们需要一个GiST索引，同时坚持你原来的原始table，基于一个表达式：
CREATE INDEX tbl_point_gist_idx ON tbl USING GiST (point(lon, lat));
基本查询 - 快速但不完善
SELECT t.*, t1.id AS near_id, t1.lon AS near_lon, t1.lat AS near_lat
FROM tbl t
JOIN LATERAL (
SELECT *
FROM tbl t1
WHERE t1.id <> t.id
ORDER BY point(t.lon, t.lat) <-> point(t1.lon, t1.lat)
LIMIT 5 -- arbitrary
) t1 ON abs(t.lon - t1.lon) < 0.0011
AND abs(t.lat - t1.lat) < 0.0011;
id
lon
lat
near_id
near_lon
near_lat
1
10.111
20.415
3
10.110
20.414
3
10.110
20.414
1
10.111
20.415
db<>fiddle here
注意 LATERAL 连接：另一个高级概念。参见：
使用距离运算符<->计算点之间的几何距离。
一个简单的相关子查询是行不通的。我们需要在过滤距离之前得到最近的邻居。这可以非常有效地使用 GiST 索引。否则，如果一行有 no 符合条件的邻居，Postgres 必须在放弃之前搜索整个 table - 这违背了目的.
问题：我们被迫在例子中使用任意一个LIMIT，5。在容忍范围内的其他邻居将被冷落。我们需要使用最大数量的可能邻居，这是未知的。由于很少有大的异常值，其余部分的超调也是低效的。
此外，基本查询 returns 每个邻居一行。我们希望将所有邻居聚合到一行。
快速且几乎正确
将上面的内容与另一个高级概念结合起来：a recursive CTE:
WITH RECURSIVE d (tol) AS (SELECT float8 '0.001') -- input tolerance here
, cte AS (
SELECT t.id, t.lon, t.lat, d.tol
, 1 AS step, ARRAY [t1.id] AS neighbors
FROM tbl t
CROSS JOIN d
JOIN LATERAL (
SELECT *
FROM tbl t1
WHERE t1.id <> t.id
ORDER BY point(t.lon, t.lat) <-> point(t1.lon, t1.lat)
LIMIT 1
) t1 ON abs(t.lon - t1.lon) < d.tol
AND abs(t.lat - t1.lat) < d.tol
UNION ALL
SELECT t.id, t.lon, t.lat, t.tol
, t.step + 1, neighbors || t1.id
FROM cte t
JOIN LATERAL (
SELECT *
FROM tbl t1
WHERE t1.id <> t.id
ORDER BY point(t.lon, t.lat) <-> point(t1.lon, t1.lat) -- !
OFFSET t.step -- !
LIMIT 1 -- !
) t1 ON abs(t.lon - t1.lon) < t.tol -- !
AND abs(t.lat - t1.lat) < t.tol -- !
)
SELECT DISTINCT ON (id) id, lon, lat, neighbors
FROM cte
ORDER BY id, step DESC;
id
lon
lat
neighbours
1
10.111
20.415
{3}
3
10.110
20.414
{1}
db<>fiddle here
第一个（非递归）CTE d 只是为了方便，提供一次容差。如果您将查询包装在函数中或使用准备好的动态连接语句，则可以删除它并直接在多个位置传递值。
下一个 CTE cte 是 rCTE。非递归项只为每个点选择最近的邻居 (LIMIT 1)。如果它在公差范围内，请继续寻找，否则我们就完成了 - 立即消除所有没有邻居的行。
在递归项中，每个 step 增加 OFFSET 以检查下一个邻居，等等
在外部 SELECT 中，我们仅在每个 id 和 DISTINCT ON 中执行最后一步。参见：
- Select first row in each GROUP BY group?
剩下的 极端情况错误 是这样的：您检查 abs(lon_i - lon_j) < tol AND abs(lat_i-lat_j) < tol，它与几何距离的差异高达因子 sqrt(2)。所以查询可能会在一个超出容差的邻居处停止，而下一个更远的邻居仍然应该被包括在内。边界框与边界圆。
更快更正确
改为检查实际几何距离。通常从以下开始更有意义：
WITH RECURSIVE d(tol) AS (SELECT float8 '0.001415') -- input tolerance here
, cte AS (
SELECT t.id, t.lon, t.lat, d.tol
, 1 AS step, ARRAY [t1.id] AS neighbors
FROM tbl t
CROSS JOIN d
JOIN LATERAL (
SELECT *, point(t.lon, t.lat) <-> point(t1.lon, t1.lat) AS dist
FROM tbl t1
WHERE t1.id <> t.id
ORDER BY dist
LIMIT 1
) t1 ON dist < d.tol
UNION ALL
SELECT t.id, t.lon, t.lat, t.tol
, t.step + 1, neighbors || t1.id
FROM cte t
JOIN LATERAL (
SELECT *, point(t.lon, t.lat) <-> point(t1.lon, t1.lat) AS dist
FROM tbl t1
WHERE t1.id <> t.id
ORDER BY dist -- !
OFFSET t.step -- !
LIMIT 1 -- !
) t1 ON dist < t.tol -- !
)
SELECT DISTINCT ON (id) id, lon, lat, neighbors
FROM cte
ORDER BY id, step DESC;
同样的结果。
db<>fiddle here
更好的是：从 point 开始
改进了 table 定义：
CREATE TABLE tbl (id int PRIMARY KEY, lonlat point); -- !!
INSERT INTO tbl VALUES
(1, '10.111, 20.415')
, (2, '10.099, 30.132')
, (3, '10.110, 20.414')
;
一个point由两个float8组成，占用磁盘16个字节。
现在直接索引列（更便宜）：
CREATE INDEX tbl_lonlat_gist_idx ON tbl USING GiST (lonlat);
查询变得更简单，速度更快，但是：
WITH RECURSIVE d(tol) AS (SELECT float8 '0.001415') -- input tolerance here
, cte AS (
SELECT t.id, t.lonlat, d.tol, 1 AS step, ARRAY[t1.id] AS neighbours
FROM tbl t
CROSS JOIN d
JOIN LATERAL (
SELECT *, t.lonlat <-> t1.lonlat AS dist
FROM tbl t1
WHERE t1.id <> t.id
ORDER BY dist
LIMIT 1
) t1 ON dist < d.tol
UNION ALL
SELECT t.id, t.lonlat, t.tol, t.step + 1, neighbours || t1.id
FROM cte t
JOIN LATERAL (
SELECT *, t.lonlat <-> t1.lonlat AS dist
FROM tbl t1
WHERE t1.id <> t.id
ORDER BY dist -- !
OFFSET t.step -- !
LIMIT 1 -- !
) t1 ON dist < t.tol -- !
)
SELECT DISTINCT ON (id) id, lonlat, neighbours
FROM cte
ORDER BY id, step DESC;
id
lonlat
neighbours
1
(10.111,20.415)
{3}
3
(10.11,20.414)
{1}
db<>fiddle here
相关：
我有一个 table 格式如下：
| id | lon | lat |
|---|---|---|
| 1 | 10.111 | 20.415 |
| 2 | 10.099 | 30.132 |
| 3 | 10.110 | 20.414 |
我想创建一个新列，其中 returns 所有 ID 使得 lon 和 lat 小于公差值，即 abs(lon_i - lon_j) < tol AND abs(lat_i-lat_j) < tol i != j.
我最初的想法是创建 table 的临时副本，然后加入 table 并给出列的名称 lon_2、lat_2 , 然后:
SELECT id
FROM TABLE_1
WHERE ABS(TABLE_1.lon - TABLE_1.lon_2) < tol
AND ABS(TABLE_1.lat - TABLE_1.lat_2) < tol
但必须有更好、更有效的方法来处理它。
暂时不需要table。
您可以进行自我加入：
SELECT t1.id, t2.id
FROM tablename t1 INNER JOIN tablename t2
ON t2.id <> t1.id AND ABS(t1.lon - t2.lon) < :tol AND ABS(t1.lat - t2.lat) < :tol;
这将为满足条件的每对 id 生成 return 1 行。
如果您想要每个 id 满足条件的所有 id 的逗号分隔列表，那么您可以聚合并使用 STRING_AGG():
SELECT t1.id, STRING_AGG(t2.id, ';' ORDER BY t2.id)
FROM tablename t1 INNER JOIN tablename t2
ON t2.id <> t1.id AND ABS(t1.lon - t2.lon) < :tol AND ABS(t1.lat - t2.lat) < :tol
GROUP BY t1.id;
all IDs such that
lonandlatare less then a tolerance value away
一个简单的自连接
但是，简单查询必须在消除给定公差之外的对之前计算两行的每个 组合的增量。基本上是一个 Cartesian Product， 与 O(N²) 的关系非常大。如果您的 table 不小，请继续阅读。
目标是得到O(N)。我们将使用一些高级概念：
- 最近邻搜索
- GiST 表达式索引
LATERAL加入- 递归 CTE
最近邻查询
如果您不熟悉，这里是Nearest-Neighbour Searching with PostGis的介绍（您的地理编码可能正在使用它？）。
无论哪种方式，我们都可以对现有 Postgres 中的类型 point 执行相同的操作。我们需要一个GiST索引，同时坚持你原来的原始table，基于一个表达式：
CREATE INDEX tbl_point_gist_idx ON tbl USING GiST (point(lon, lat));
基本查询 - 快速但不完善
SELECT t.*, t1.id AS near_id, t1.lon AS near_lon, t1.lat AS near_lat
FROM tbl t
JOIN LATERAL (
SELECT *
FROM tbl t1
WHERE t1.id <> t.id
ORDER BY point(t.lon, t.lat) <-> point(t1.lon, t1.lat)
LIMIT 5 -- arbitrary
) t1 ON abs(t.lon - t1.lon) < 0.0011
AND abs(t.lat - t1.lat) < 0.0011;
| id | lon | lat | near_id | near_lon | near_lat |
|---|---|---|---|---|---|
| 1 | 10.111 | 20.415 | 3 | 10.110 | 20.414 |
| 3 | 10.110 | 20.414 | 1 | 10.111 | 20.415 |
db<>fiddle here
注意 LATERAL 连接：另一个高级概念。参见：
使用距离运算符<->计算点之间的几何距离。
一个简单的相关子查询是行不通的。我们需要在过滤距离之前得到最近的邻居。这可以非常有效地使用 GiST 索引。否则，如果一行有 no 符合条件的邻居，Postgres 必须在放弃之前搜索整个 table - 这违背了目的.
问题：我们被迫在例子中使用任意一个LIMIT，5。在容忍范围内的其他邻居将被冷落。我们需要使用最大数量的可能邻居，这是未知的。由于很少有大的异常值，其余部分的超调也是低效的。
此外，基本查询 returns 每个邻居一行。我们希望将所有邻居聚合到一行。
快速且几乎正确
将上面的内容与另一个高级概念结合起来：a recursive CTE:
WITH RECURSIVE d (tol) AS (SELECT float8 '0.001') -- input tolerance here
, cte AS (
SELECT t.id, t.lon, t.lat, d.tol
, 1 AS step, ARRAY [t1.id] AS neighbors
FROM tbl t
CROSS JOIN d
JOIN LATERAL (
SELECT *
FROM tbl t1
WHERE t1.id <> t.id
ORDER BY point(t.lon, t.lat) <-> point(t1.lon, t1.lat)
LIMIT 1
) t1 ON abs(t.lon - t1.lon) < d.tol
AND abs(t.lat - t1.lat) < d.tol
UNION ALL
SELECT t.id, t.lon, t.lat, t.tol
, t.step + 1, neighbors || t1.id
FROM cte t
JOIN LATERAL (
SELECT *
FROM tbl t1
WHERE t1.id <> t.id
ORDER BY point(t.lon, t.lat) <-> point(t1.lon, t1.lat) -- !
OFFSET t.step -- !
LIMIT 1 -- !
) t1 ON abs(t.lon - t1.lon) < t.tol -- !
AND abs(t.lat - t1.lat) < t.tol -- !
)
SELECT DISTINCT ON (id) id, lon, lat, neighbors
FROM cte
ORDER BY id, step DESC;
| id | lon | lat | neighbours |
|---|---|---|---|
| 1 | 10.111 | 20.415 | {3} |
| 3 | 10.110 | 20.414 | {1} |
db<>fiddle here
第一个（非递归）CTE d 只是为了方便，提供一次容差。如果您将查询包装在函数中或使用准备好的动态连接语句，则可以删除它并直接在多个位置传递值。
下一个 CTE cte 是 rCTE。非递归项只为每个点选择最近的邻居 (LIMIT 1)。如果它在公差范围内，请继续寻找，否则我们就完成了 - 立即消除所有没有邻居的行。
在递归项中，每个 step 增加 OFFSET 以检查下一个邻居，等等
在外部 SELECT 中，我们仅在每个 id 和 DISTINCT ON 中执行最后一步。参见：
- Select first row in each GROUP BY group?
剩下的 极端情况错误 是这样的：您检查 abs(lon_i - lon_j) < tol AND abs(lat_i-lat_j) < tol，它与几何距离的差异高达因子 sqrt(2)。所以查询可能会在一个超出容差的邻居处停止，而下一个更远的邻居仍然应该被包括在内。边界框与边界圆。
更快更正确
改为检查实际几何距离。通常从以下开始更有意义：
WITH RECURSIVE d(tol) AS (SELECT float8 '0.001415') -- input tolerance here
, cte AS (
SELECT t.id, t.lon, t.lat, d.tol
, 1 AS step, ARRAY [t1.id] AS neighbors
FROM tbl t
CROSS JOIN d
JOIN LATERAL (
SELECT *, point(t.lon, t.lat) <-> point(t1.lon, t1.lat) AS dist
FROM tbl t1
WHERE t1.id <> t.id
ORDER BY dist
LIMIT 1
) t1 ON dist < d.tol
UNION ALL
SELECT t.id, t.lon, t.lat, t.tol
, t.step + 1, neighbors || t1.id
FROM cte t
JOIN LATERAL (
SELECT *, point(t.lon, t.lat) <-> point(t1.lon, t1.lat) AS dist
FROM tbl t1
WHERE t1.id <> t.id
ORDER BY dist -- !
OFFSET t.step -- !
LIMIT 1 -- !
) t1 ON dist < t.tol -- !
)
SELECT DISTINCT ON (id) id, lon, lat, neighbors
FROM cte
ORDER BY id, step DESC;
同样的结果。
db<>fiddle here
更好的是：从 point 开始
改进了 table 定义：
CREATE TABLE tbl (id int PRIMARY KEY, lonlat point); -- !!
INSERT INTO tbl VALUES
(1, '10.111, 20.415')
, (2, '10.099, 30.132')
, (3, '10.110, 20.414')
;
一个point由两个float8组成，占用磁盘16个字节。
现在直接索引列（更便宜）：
CREATE INDEX tbl_lonlat_gist_idx ON tbl USING GiST (lonlat);
查询变得更简单，速度更快，但是：
WITH RECURSIVE d(tol) AS (SELECT float8 '0.001415') -- input tolerance here
, cte AS (
SELECT t.id, t.lonlat, d.tol, 1 AS step, ARRAY[t1.id] AS neighbours
FROM tbl t
CROSS JOIN d
JOIN LATERAL (
SELECT *, t.lonlat <-> t1.lonlat AS dist
FROM tbl t1
WHERE t1.id <> t.id
ORDER BY dist
LIMIT 1
) t1 ON dist < d.tol
UNION ALL
SELECT t.id, t.lonlat, t.tol, t.step + 1, neighbours || t1.id
FROM cte t
JOIN LATERAL (
SELECT *, t.lonlat <-> t1.lonlat AS dist
FROM tbl t1
WHERE t1.id <> t.id
ORDER BY dist -- !
OFFSET t.step -- !
LIMIT 1 -- !
) t1 ON dist < t.tol -- !
)
SELECT DISTINCT ON (id) id, lonlat, neighbours
FROM cte
ORDER BY id, step DESC;
| id | lonlat | neighbours |
|---|---|---|
| 1 | (10.111,20.415) | {3} |
| 3 | (10.11,20.414) | {1} |
db<>fiddle here
相关：