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

Question

给定一个过程，例如

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

当我试图检查两个集合是否至少产生一个共同元素时，我想知道这样做的成本有多大，以及担心 boolean satisfiability problem 是否有意义。 .

---

更完整的 View :

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

感谢您的关注。

Answer 1

快速浏览 source code对于 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 微秒。所以，是的，除非数组很大，否则没问题。

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

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) 更好。

编辑:source code说它使用线性搜索并且不会散列键，因此 jsonb 不会有更好的复杂性。

如果您想做得太过分，您还可以使用位图或位字符串，其中存在的属性的位设置为 1。这使得重叠操作为 O(1)，但当然每个属性都在位串中分配了固定的位位置，这很麻烦。