BUG #16964: Quadratic performance degradation of INSERT and ADD CONSTRAINT for intarray/GIST EXCLUDE CONSTRAINT

The following bug has been logged on the website:

Bug reference: 16964
Logged by: Maxim Boguk
Email address: maxim(dot)boguk(at)gmail(dot)com
PostgreSQL version: 13.2
Operating system: Linux
Description:

I found that combination of EXCLUDE CONSTRAINT with intarray GIST have
quadratic degradation with relation size.
Making it completely useless with tables starting from few thousand rows.

Test dataset can be provided by request (100kb sql file).
Confirmed for 13.2 and 12.* versions.

create extension intarray;
create extension btree_gist;
\i /tmp/2.sql
CREATE TABLE
COPY 4000

structure of
test=# \d+ test
Table "public.test"
Column | Type | Collation | Nullable | Default | Storage | Stats
target | Description
----------+-----------+-----------+----------+---------+----------+--------------+-------------
team_id | integer | | | | plain |
|
user_ids | integer[] | | | | extended |
|

1 or 2 user_id per array.

Performance results:
ALTER TABLE test
ADD CONSTRAINT unique_user_parties_on_team
EXCLUDE USING gist (
team_id WITH =,
user_ids WITH &&
);
ALTER TABLE
Time: 911198.957 ms (15:11.199)

(with 2k rows Time: 217885.618 ms (03:37.886))

performance of insert (on 4k rows set):
insert into test values (10, array[1,2]);
INSERT 0 1
Time: 1204.211 ms (00:01.204)

perf record/report for ADD CONSTRAINT:
39.65% postgres postgres [.] pg_qsort
35.60% postgres _int.so [.] compASC
3.68% postgres postgres [.] swapfunc
3.26% postgres _int.so [.] _int_unique
3.15% postgres _int.so [.] g_int_decompress
2.69% postgres libc-2.31.so [.] 0x000000000018ead1
1.65% postgres _int.so [.] inner_int_union

perf record/report for INSERT:
39.32% postgres postgres [.] pg_qsort
36.08% postgres _int.so [.] compASC
3.18% postgres postgres [.] swapfunc

It look like somewhat broken for me (especially for so simple use
case/common scenario).

--
Maxim Boguk
Senior Postgresql DBA
https://dataegret.com/