• Tom Lane's avatar
    Avoid O(N^2) cost in ExecFindRowMark(). · f9eb7c14
    Tom Lane authored
    If there are many ExecRowMark structs, we spent O(N^2) time in
    ExecFindRowMark during executor startup.  Once upon a time this was
    not of great concern, but the addition of native partitioning has
    squeezed out enough other costs that this can become the dominant
    overhead in some use-cases for tables with many partitions.
    
    To fix, simply replace that List data structure with an array.
    
    This adds a little bit of cost to execCurrentOf(), but not much,
    and anyway that code path is neither of large importance nor very
    efficient now.  If we ever decide it is a bottleneck, constructing a
    hash table for lookup-by-tableoid would likely be the thing to do.
    
    Per complaint from Amit Langote, though this is different from
    his fix proposal.
    
    Discussion: https://postgr.es/m/468c85d9-540e-66a2-1dde-fec2b741e688@lab.ntt.co.jp
    f9eb7c14
execnodes.h 81.2 KB