在 PostgreSQL 中使用 int4range 类型进行快速最近邻匹配

Question

我有两个范围为 t1 和 t2 的表，我正在尝试为 t1 中的每个条目在 t2 中找到最接近的匹配项。

我定义距离如下：

-- distance function
CREATE OR REPLACE FUNCTION distance(
    pos1 int4range,
    pos2 int4range)
    RETURNS integer
    LANGUAGE 'sql'
AS $BODY$SELECT CASE
WHEN pos1 && pos2 THEN 0
WHEN pos1 >> pos2 THEN lower(pos1) - upper(pos2)
WHEN pos1 << pos2 THEN lower(pos2) - upper(pos1)
ELSE NULL
END AS distance$BODY$;

让我们定义 t1 和 t2 如下：

SELECT setseed(0.20191109);

DROP TABLE IF EXISTS t1;
DROP TABLE IF EXISTS t2;

WITH
t1n AS
(
    SELECT generate_series (1,500) AS id1, floor(random()*1e7)::integer AS n 
)
SELECT id1, int4range(n, n + ceil(random()*10)::integer) AS range1
INTO t1
FROM t1n;

WITH
t2n AS
(
    SELECT generate_series (1,10000) AS id2, floor(random()*1e7)::integer AS n 
)
SELECT id2, int4range(n, n + ceil(random()*100)::integer) AS range2
INTO t2
FROM t2n;

我认为使用连接和标量子查询的两个直接解决方案都非常低效，因为它们 (1) 计算所有可能的距离并聚合或 (2) 对每个 t2 的整体进行排序t1 中的值：

-- method one
SELECT id1,min(distance(range1,range2)) AS dist
FROM t1
CROSS JOIN t2
GROUP BY 1
ORDER BY 1;

-- method two
SELECT id1,(SELECT distance(t2.range2, t1.range1) FROM t2 ORDER BY distance(t2.range2, t1.range1) LIMIT 1) AS dist
FROM t1
ORDER BY 1;

这是一个 rextester link：https://rextester.com/AIYEQ97536

我想知道是否有我缺少的更有效的解决方案？

更新：我尝试在范围类型上使用 GiST、SP-GiST、B-tree/GiST 索引，但其中 none 似乎天真地支持在范围类型上使用 <-> 距离运算符int4range？至少在 PostgreSQL 10.5 中没有？有没有办法将我在此 post 顶部定义的距离函数与这些索引类型之一一起使用？

Answer 1

but none of these seem to naively support using the <-> distance operator on int4range?

他们不仅不支持该运算符，而且该运算符甚至不存在于开箱即用的 int4range 上。您可以在 SQL:

中简单地创建这样的运算符

create operator <-> ( function = distance, leftarg=int4range, rightarg=int4range);

但是将它连接到索引需要大量的 C 编程。

如果不使用 C 编程，您可以通过结合 3 个查询、重叠、最靠近左侧和最接近右侧，然后取它们的最小值来找到最接近的事物。最右边的一个很容易，它必须是第一个 > 询问者，所以应该很容易索引。但是，这不适用于最靠近左侧的位置。您可以使用功能索引来解决这个问题。合并后的结果并不漂亮，但通常很快（一旦对表进行了 VACUUM ANALYZEd）。

create index on t2 using gist (range2 );
create index on t2 (range2 );
create index on t2 (int4range(-upper(range2),-lower(range2),'[]'));


select id1, distance(range1,range2) AS dist from t1 cross join lateral 
(
    select * from (
       (select * from t2 where t2.range2 && t1.range1 limit 1) union all 
       (select * from t2 where t2.range2 > t1.range1 order by t2.range2 limit 1) union all 
       (select * from t2 where int4range(-upper(range2),-lower(range2),'[]') > int4range(-upper(range1),-lower(range1),'[]') order by int4range(-upper(range2),-lower(range2),'[]') limit 1)
    ) foobar order by distance(range1,range2) limit 1
) foo;

我不确定“[]”是对端点的正确处理，但此查询确实给出了与您的方法 1 相同的结果。

在 PostgreSQL 中使用 int4range 类型进行快速最近邻匹配

Fast nearest neighbor matching in using int4range type in PostgreSQL

postgresql

nearest-neighbor