• Tomas Vondra's avatar
    Track unowned relations in doubly-linked list · 6ca015f9
    Tomas Vondra authored
    Relations dropped in a single transaction are tracked in a list of
    unowned relations.  With large number of dropped relations this resulted
    in poor performance at the end of a transaction, when the relations are
    removed from the singly linked list one by one.
    
    Commit b4166911 attempted to address this issue (particularly when it
    happens during recovery) by removing the relations in a reverse order,
    resulting in O(1) lookups in the list of unowned relations.  This did
    not work reliably, though, and it was possible to trigger the O(N^2)
    behavior in various ways.
    
    Instead of trying to remove the relations in a specific order with
    respect to the linked list, which seems rather fragile, switch to a
    regular doubly linked.  That allows us to remove relations cheaply no
    matter where in the list they are.
    
    As b4166911 was a bugfix, backpatched to all supported versions, do the
    same thing here.
    
    Reviewed-by: Alvaro Herrera
    Discussion: https://www.postgresql.org/message-id/flat/80c27103-99e4-1d0c-642c-d9f3b94aaa0a%402ndquadrant.com
    Backpatch-through: 9.4
    6ca015f9
smgr.h 5.98 KB