PostgreSQL中&&运算符的时间复杂度

html5 • • 问答

给定一个程序，例如

SELECT (regexp_split_to_array(...)) && SELECT (regexp_split_to_array(...))

我试图检查两个集合是否至少产生一个共同的元素，我想知道这有多昂贵，以及担心布尔可满足性问题是否有意义。

更完整的视图：

CREATE POLICY mytable_policy
ON mytable
USING (
        CASE WHEN ... THEN TRUE
             ELSE (SELECT (regexp_split_to_array((SELECT current_setting('my.stuff')), ':')))
                                                &&
                  (SELECT (regexp_split_to_array(mystuff, ':')))
        END
      )
WITH CHECK (true);

感谢您的关注。

回答

快速查看array1 && array2的源代码，说复杂度是 O(L1*L2)，L1 和 L2 是 array1 和 array2 的长度。它遍历array1，然后对于每个元素遍历array2，直到找到匹配项。

如果数组很短，这很可能不是问题，如果它们很长，则可能会很慢。由于循环在找到的第一个匹配项处停止，因此将最频繁的元素放在数组中是有意义的。

请注意，您可以将数组存储在表中。无需将它们存储为以“:”分隔的字符串并每次都重新构建它们。这是一个包含 1000 行的表格，其中文本列“t”的值为 'A:B:C:D:E:F:G:H:I:J:K:L:M:N:O:P： Q:R:S:T:U:V:W:X:Y:Z'，以及包含数组 {A,B,C,D,E,F,G,H,I, J、K、L、M、N、O、P、Q、R、S、T、U、V、W、X、Y、Z}。

test=> EXPLAIN ANALYZE SELECT string_to_array(t,':') FROM foo;
 Execution time: 5.334 ms

test=> EXPLAIN ANALYZE SELECT regexp_split_to_array(t,':') FROM foo;
 Execution time: 40.640 ms

test=> EXPLAIN ANALYZE SELECT a FROM foo;
 Execution time: 0.488 ms

如您所见，将其存储为文本是一个非常糟糕的主意，使用 regexp 函数更糟糕。只需使用数组列，它会快得多......现在，&& 运算符需要多长时间？

test=> EXPLAIN ANALYZE SELECT regexp_split_to_array(t,':') && '{M,N,Z}'::TEXT[] FROM foo;
 Execution time: 42.055 ms

test=> EXPLAIN ANALYZE SELECT a && '{M,N,Z}'::TEXT[] FROM foo;
 Execution time: 1.944 ms

在 1.9 毫秒内处理了 1000 行，因此运行 && 运算符不到 2µs。所以，是的，除非数组很大，否则没问题。

如果你想过度使用它，你可以使用 jsonb 类型。这个包含一个关联数组，如 {'A':1, 'B':2 ... etc ... }

test=> EXPLAIN ANALYZE SELECT j ?| '{M,N,Z}'::TEXT[] FROM foo;
 Execution time: 1.041 ms

快一点，但我不确定这是否具有更好的复杂性。这取决于 jsonb 代码如何以及是否对键进行哈希处理。如果对 jsonb 对象的键查找是 O(1)，那么整个操作将是 O(L1)，如果 array2 很大，这比 O(L1*L2) 好。

编辑：源代码说它使用线性搜索并且不散列键，所以 jsonb 不会有更好的复杂性。

如果你想过度使用它，你也可以使用位图或位串，对于存在的属性，位设置为 1。这使得重叠操作 O(1)，但当然每个属性都在位串中分配了一个固定的位位置，这很麻烦。

以上是PostgreSQL中&&运算符的时间复杂度的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>