在PostgreSQL中使用int4range类型的最接近的邻居匹配

Question

我有两个表，它们的范围分别为t1和t2，并试图为t2中的每个条目查找t1中最接近的匹配项。

我将距离定义如下：

-- 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);

WITH
t1n AS
(
    SELECT generate_series (1,500) AS id1, floor(random()*1e7)::integer AS n 
),
t1 AS
(
    SELECT id1, int4range(n, n + ceil(random()*10)::integer) AS range1
    FROM t1n
),
t2n AS
(
    SELECT generate_series (1,10000) AS id2, floor(random()*1e7)::integer AS n 
),
t2 AS
(
    SELECT id2, int4range(n, n + ceil(random()*100)::integer) AS range2
    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;

这里是一个右月链接：https://rextester.com/MMCL97337

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

更新：我已经尝试在范围类型上使用GiST，SP-GiST，B树/ GiST索引，但是似乎没有一个天真的支持在<->上使用int4range距离运算符吗？至少不是在PostgreSQL 10.5中吗？有没有一种方法可以将我在本文顶部定义的距离函数与这些索引类型之一一起使用？

Answer 1

但是这些似乎都没有天真的支持在int4range上使用距离运算符？

他们不仅不支持该运算符，而且开箱即用的int4range甚至都不存在该运算符。您可以在SQL中轻松创建这样的运算符：

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

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

没有C语言编程，您可以通过对3个查询进行合并，重叠，向左最靠近，向右靠近，然后取其最小值，来找到最接近的东西。最右边的一个很容易，它必须是第一个> querent，因此应该易于索引。但是，这对于最靠近左侧的位置无效。您可以使用功能索引来解决此问题。合并的结果不太好，但是通常很快（一旦对表进行了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提供了相同的结果。