给定一个像这样的表:
路径(l树) |
---|
ABC |
ab |
A |
德 |
F |
我将如何编写一个查询来返回给定输入的最长匹配 ltree 路径?
例如:
(input) => expected output
(a.b.c) => a.b.c
(d.e.f) => d.e
(f.g.h) => f
(a.b) => a.b
我希望能够使用它以一种高性能的方式将一个包含 ltree 路径的表与另一个表中的“最长匹配路径”连接起来。因此,给定一个包含上面示例中所有行的表inputs
,我如何将其连接到表中以获得具有“最长匹配”的行?
构建测试数据...
对于表“other”中的约 1000 行,将搜索表“tree”中包含 1M 行的最长匹配路径。
第一次尝试:窗口函数。140ms,无限制。它需要在输出中进行一些重复数据删除。
第二次尝试:可以使用 ltree 比较,如 '1.2.3'::ltree>'1.2'::ltree,因此使用 max() 只会返回最长的一个。不幸的是 max() 没有为 ltree 实现,但你可以添加它。但我们始终可以使用 LATERAL,它的优点是可以在需要时返回整行。
这个排序速度更快,为 80 毫秒,因为排序是在嵌套循环内移动的,而且它是 top-1 堆排序。因此每行需要 80μs 才能找到最长的路径。
第三个:设置返回功能。
结果:29ms,快得多。
然而,它依赖于这样一个事实:postgres 将按照函数返回的顺序使用 unnest_ltree() 中的行,但这是不能保证的。
第四次尝试:手动加入
结果:路径上有 gist 索引需要 35 毫秒,路径上有 btree 索引需要 16 毫秒。
然而,既然我在路径列上添加了 btree 索引,第一个查询就会反击。因为路径(o.path)的最长父项(t.path)必须满足 t.path <= o.path,并且由于路径的排序顺序,添加该条件意味着 btree 立即找到目标行,而 gist只是返回所有需要排序的祖先。所以这是最快的选择,但它需要额外的索引。
但是......如果表“其他”更大,会发生什么?让我们尝试一下 500k 行。
在这种情况下,上述所有方法都会受到影响,大约需要 3.5 秒,因为它们都仅限于嵌套循环计划类型。对于两个表中的大量行,合并联接将是一个更好的选择...不幸的是,postgres 不支持 ASOF JOIN,它会自动执行此操作,但我们总是可以排序!
由于这使得相关行非常接近(一个总是在另一个之上),因此窗口函数可以对此进行排序。
这不使用任何索引,应该适用于大型表,但在我的测试用例中,它花费的时间与之前的时间大约相同。