SQL查询从二维数据表中获取邻居

Question

我有一个表，其中包含世界地图的分区。分区是通过将所有区域分割成矩形（称为“平铺”）来完成的。像往常一样，矩形有左下角和右上角，两者都由浮点坐标引用。

任务是这样的：

对于每个图块，获取其右侧的邻居和顶部的邻居，就像一组{tile_id, id_of_top_neighbour, id_of_right_n}。

瓦片 A 的右邻居意味着瓦片 B 的 min_x 坐标与 A 的 max_x 坐标最接近，而 y 相同。

表说明：

integer tile_id; --Tile id. PK.
real    min_x;  --X coordinate of bottom-left point
real    min_y;  --Y coordinate of bottom-left point
real    max_x;  --X coordinate of upper-right point
real    max_y;  --Y coordinate of upper-right point

失败的解决方案：

首先，我尝试按一个坐标排序，在java端迭代此结果集，然后对每一行执行额外的选择。表现不够充分。

现在我想知道纯 SQL 解决方案是否可能并且在运行时更快...

提前感谢任何帮助或想法。

编辑： 两个图块之间可能存在间隙，因此（例如，对于右邻居）B.min_x - A.max_x 可能> 0. 然而，两个图块的相交不能超过边界。

我们正在使用 Postgres 8.3

Answer 1

窗口函数和 CTE 将使这变得非常容易。我认为两者都在 8.4 及更高版本中可用。我强烈建议你升级。我在9.0上测试了这个解决方案：

with tile_data as
(
    select
        tile_id,
        min_x,
        min_x + 0.9 as max_x,
        min_y,
        min_y + 0.9 as max_y
    from
    (
     select 1 as tile_id, 0.0 as min_x, 0.0 as min_y union all
     select 2, 1.0, 0.0 union all
     select 3, 2.0, 0.0 union all
     select 4, 0.0, 1.0 union all
     select 5, 1.0, 1.0 union all
     select 6, 2.0, 1.0 union all
     select 7, 0.0, 2.0 union all
     select 8, 1.0, 2.0 union all
     select 9, 2.0, 2.0 
    ) a
),
right_neighbor_tiles as
(
    select
        tile_id,
        other_tile_id as right_neighbor_tile_id
    from
    (
        select
             a.tile_id,
             b.tile_id as other_tile_id,
             row_number() over(partition by a.tile_id order by b.min_x - a.min_x) as distance_rank
        from 
            tile_data a
        inner join
            tile_data b
        on
            a.min_x < b.min_x 
            and a.min_y = b.min_y
    ) ranked_tiles_right
    where
        distance_rank = 1
),
up_neighbor_tiles as
(
    select
        tile_id,
        other_tile_id as up_neighbor_tile_id
    from
    (
        select
            a.tile_id,
            b.tile_id as other_tile_id,
            row_number() over(partition by a.tile_id order by a.min_y - b.min_y) as distance_rank
        from 
            tile_data a
        inner join
            tile_data b
        on
            a.min_y > b.min_y 
            and a.min_x = b.min_x
    ) ranked_tiles_up
    where
        distance_rank = 1
)
select 
    a.*,
    b.right_neighbor_tile_id,
    c.up_neighbor_tile_id
from
    tile_data a
left join
    right_neighbor_tiles b
on
    a.tile_id = b.tile_id
left join
    up_neighbor_tiles c
on
    a.tile_id = c.tile_id

结果：

tile_id  min_x  max_x  min_y  max_y  right_neighbor_tile_id   up_neighbor_tile_id
1        0      0.9    0      0.9    2
2        1      1.9    0      0.9    3
3        2      2.9    0      0.9
4        0      0.9    1      1.9    5                        1
5        1      1.9    1      1.9    6                        2
6        2      2.9    1      1.9                             3
7        0      0.9    2      2.9    8                        4
8        1      1.9    2      2.9    9                        5
9        2      2.9    2      2.9                             6

Answer 2

更改您的数据以使用 Box 类型。

create temp table test (
    nick    char,
    tile    box
);


/*
.........
aa..bbcc.
aa..bbcc.
*/

insert into test values ('a',  box(point(0,1),point(1,0)));
insert into test values ('b',  box(point(4,0),point(5,1)));
insert into test values ('c',  box(point(7,0),point(8,1)));

select
    distinct on (test.nick)

    test.nick,
    r.nick as right,
    least((r.tile[0])[0], (r.tile[1])[0]) as least_x -- gets the lowest x cord

from test
    join test as r
        on  test.tile << r.tile -- strictly left of operator

    group by test.nick, right, least_x

输出：

 nick | right   | least_x
 ------+---------+---------
 a    | b       |       4
 b    | c       |       7
 (2 rows)