Re: BUG #15518: intarray index crashes hard

From: Andrew Gierth <andrew(at)tao11(dot)riddles(dot)org(dot)uk>
To: pgsql-bugs(at)lists(dot)postgresql(dot)org
Subject: Re: BUG #15518: intarray index crashes hard
Date: 2018-11-23 21:49:22
Message-ID: 878t1jsczr.fsf@news-spur.riddles.org.uk
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-bugs

>>>>> "PG" == PG Bug reporting form <noreply(at)postgresql(dot)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)

Attachment Content-Type Size
iafix.patch text/x-patch 4.3 KB

In response to

Browse pgsql-bugs by date

  From Date Subject
Next Message Tom Lane 2018-11-23 21:57:18 Re: BUG #15517: JSONB_BUILD_ARRAY and JSON_BUILD_ARRAY omit XML Declaration (if present) from XML colums
Previous Message Tom Lane 2018-11-23 17:17:34 Re: BUG #15160: planner overestimates number of rows in join when there are more than 200 rows coming from CTE