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.boguk@gmail.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/