Re: Is array_append O(n)?

On 2019-Jun-18, Rob Nikander wrote:

> Does `array_append(arr, elt)` create a new array and copy everything?
> In other words, is it O(n) or O(1)? I’m trying to use plpgsql and
> realizing I don’t really have my usual data structures for basic
> algorithms the way I’d normally write them. I probably shouldn’t be
> treating arrays like Java ArrayList or C++ vector, where you can
> add/remove on the end with little cost (O(1), almost.)

Starting with 9.5, there's an optimization that I think is supposed to
make it O(1):

commit 1dc5ebc9077ab742079ce5dac9a6664248d42916
Author: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
AuthorDate: Thu May 14 12:08:40 2015 -0400
CommitDate: Thu May 14 12:08:49 2015 -0400

Support "expanded" objects, particularly arrays, for better performance.

This patch introduces the ability for complex datatypes to have an
in-memory representation that is different from their on-disk format.
On-disk formats are typically optimized for minimal size, and in any case
they can't contain pointers, so they are often not well-suited for
computation. Now a datatype can invent an "expanded" in-memory format
that is better suited for its operations, and then pass that around among
the C functions that operate on the datatype. There are also provisions
(rudimentary as yet) to allow an expanded object to be modified in-place
under suitable conditions, so that operations like assignment to an element
of an array need not involve copying the entire array.

The initial application for this feature is arrays, but it is not hard
to foresee using it for other container types like JSON, XML and hstore.
I have hopes that it will be useful to PostGIS as well.

In this initial implementation, a few heuristics have been hard-wired
into plpgsql to improve performance for arrays that are stored in
plpgsql variables. We would like to generalize those hacks so that
other datatypes can obtain similar improvements, but figuring out some
appropriate APIs is left as a task for future work. (The heuristics
themselves are probably not optimal yet, either, as they sometimes
force expansion of arrays that would be better left alone.)

Preliminary performance testing shows impressive speed gains for plpgsql
functions that do element-by-element access or update of large arrays.
There are other cases that get a little slower, as a result of added array
format conversions; but we can hope to improve anything that's annoyingly
bad. In any case most applications should see a net win.

Tom Lane, reviewed by Andres Freund

--
Álvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services