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@sss.pgh.pa.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