Thread: BUG #15518: intarray index crashes hard

The following bug has been logged on the website:

Bug reference:      15518
Logged by:          Andrew Gierth
Email address:      andrew@tao11.riddles.org.uk
PostgreSQL version: 11.1
Operating system:   any
Description:

Based on a report from IRC:

create extension intarray;
create table ibreak (id integer, a integer[]);
create index on ibreak using gist (a);
insert into ibreak
  select i, array(select hashint4(i*j) from generate_series(1,100) j)
    from generate_series(1,20) i;
-- segfault

This happens because the default "small" intarray opclass, gist__int_ops,
has wholly inadequate sanity checks on the data; while it will reject
individual rows with too many distinct values, it will happily construct
compressed non-leaf keys that will crash the decompression code due to
overflowing an "int", or produce an unhelpful memory allocation error, or
consume vast amounts of CPU time without checking for interrupts.

This isn't new; it looks like this issue has existed as long as intarray
has.

Obviously it's not intended that gist__int_ops should actually work with
data of this kind - that's what gist__intbig_ops is for. But it's not
reasonable for it to crash rather than returning an error.

I'm working on a patch.

>>>>> "PG" == PG Bug reporting form <noreply@postgresql.org> writes:

 PG> Obviously it's not intended that gist__int_ops should actually work
 PG> with data of this kind - that's what gist__intbig_ops is for. But
 PG> it's not reasonable for it to crash rather than returning an error.

 PG> I'm working on a patch.

And here it is.

This version doesn't restrict the sparseness of keys any more than it
needs to for safety. This necessitates improving the O(N^2) compression
algorithm to O(N), because otherwise it's possible to create datasets
that cause a single compression call to run for months (with no check
for interrupts, either).

There are essentially 4 specific issues addressed:

1. Integer overflow in internal_size could result in memory corruption
   in decompression since a zero-length array would be allocated and
   then written to.

2. Integer overflow in g_int_compress could cause pessimal merge
   choices, resulting in unnecessarily large ranges (which would in turn
   trigger issue 1 above)

3. Even without overflow, array sizes could become large enough to cause
   unexplained memory allocation errors, so cap the sizes and report
   actual errors pointing at gist__intbig_ops as needed.

4. Large inputs to the compression function always consist of large runs
   of consecutive integers, and the compression loop was processing
   these one at a time in an O(N^2) manner with a lot of overhead. The
   expected runtime of this function could easily exceed 6 months as a
   result. Performing a linear-time first pass reduces the worst case
   to something on the order of seconds.

-- 
Andrew (irc:RhodiumToad)