Time complexity of && operator in PostgreSQL

user_4828060 0
Viewed 232

Given a procedure such as

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

where I'm trying to check if two collections yield at least one element in common, I was wondering how costly is this and whether it makes sense to worry about the boolean satisfiability problem.

A more complete 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);

Thank you for your attention.

postgresql
1 Answers

A quick look at the source code for array1 && array2 says complexity is O(L1*L2) with L1 and L2 being the lengths of array1 and array2. It iterates through array1, then for each element it iterates through array2 until it finds a match.

This will most likely not be a problem if the arrays are short, could be slow if they are long. Since the loop stops at the first match found, it makes sense to put the most frequent elements first in the array.

Note that you can store arrays in tables. There is no need to store them as strings separated with ":" and rebuild them every time. Here is a table that contains 1000 lines with a text column "t" with value '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', and a TEXT[] column which contains the array {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

As you can see, it is a very bad idea to store it as text, and even worse to use the regexp function. Just use an array column, it'll be much faster... now, how long does the && operator take?

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

1000 lines processed in 1.9ms, so that's less than 2µs to run the && operator. So, yeah, unless the arrays are huge, no problem.

If you want to overdo it, you could use a jsonb type. This one contains an associative array like {'A':1, 'B':2 ... etc ... }

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

A bit faster, but I'm not sure this has better complexity. That depends on how and if the jsonb code hashes keys. If key lookup into a jsonb object is O(1) then the whole operation will be O(L1) which is better than O(L1*L2) if array2 is large.

EDIT: source code says it uses linear search and doesn't hash the keys, so jsonb won't have better complexity.

If you want to overdo it, you could also use a bitmap or bitstring, with bits set to 1 for attributes that are present. This makes overlap operation O(1), but of course each attribute is assigned a fixed bit position in the bitstring, which is cumbersome.

user_1444500
Related