Re: BUG #15518: intarray index crashes hard

>>>>> "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)