A HOT-update chain looks something like this:

      A               B *           C *
      o #             o #           o  
      |               |             |
      |               |             |
      |               |             |
      v               v             v
  +--------+     +--------+     +--------+
  |   X    |---->|    Y   |---->|   Z    |
  +--------+     +--------+     +--------+

In the illustration above,
   
    # indicates that the tuple is HOT-updated
    * indicates that the tuple is heap-only


There are three tuples X, Y and Z in the tuple chain and the
chain is rooted at X. The item-ids (or line-pointers) A, B, C
point to the tuples X, Y and Z respectively.

Now, say X and Y become DEAD and are not visible to any backend.
We prune the chain in this case. As a first step, X is made point
to Z by changing its t_ctid and isolating Y. The item-id B is set
LP_DELETE so that the tuple can be reused for subsequent UPDATE
in this page.


      A               B *           C *
      o #             o ^           o
      |               |             |
      |               |             |
      |               |             |
      v               v             v
  +--------+     +--------+     +--------+
  |   X    |--   |    Y   |  -->|   Z    |
  +--------+ |   +--------+  |  +--------+
             |               |
             +---------------+

    ^ indicates LP_DELETEd item-id and tuple

Tuple X is also dead, but we can not remove A because there might be
index entries pointing to A and thats the only access to Z from
the indexes. So we redirect A to C by storing C in the lp_off
field of A. We also set A->lp_len to a special value of
ITEMID_REDIRECTED which is defined to 1. Here we are assuming that
there can not be a tuple (heap or index) with length 1 and so we
can safely use this value to identify redirected item-ids.

      A %                           C *
      o---------------------------->o
                                    |
                      B *           |  
                      o ^           |
                      |             |
                      |             |
                      |             |
                      v             v
  +--------+     +--------+     +--------+
  |   X    |     |    Y   |     |   Z    |
  +--------+     +--------+     +--------+
                              

   % indicates that the item-id is redirected                           


As a last step, we try to insert a new item-id to track the
released tuple X. This is very useful for cases where the tuple
size does not change (or very marginally change) with UPDATEs.
If we track X and reuse it, then we can completely avoid vacuuming
these tables, as long as there are no long running transactions
and enough free space in the block to start with.


      A %                           C *
      o---------------------------->o
                                    |
      D               B *           |  
      o ^             o ^           |
      |               |             |
      |               |             |
      |               |             |
      v               v             v
  +--------+     +--------+     +--------+
  |   X    |     |    Y   |     |   Z    |
  +--------+     +--------+     +--------+
                              

In this case, both X and Y are available for reuse and there is a
4 byte overhead for the tuple live tuple Z.

If Z is now updated to P, assuming that the tuple size does not
grow and the page has no free space, Y will be reused.


      A %                           C *
      o---------------------------->o #
                                    |
      D               B *           |  
      o ^             o             |
      |               |             |
      |               |             |
      |               |             |
      v               v             v
  +--------+     +--------+     +--------+
  |   X    |     |    P   |<----|   Z    |
  +--------+     +--------+     +--------+


Finally, when P is either COLD-updated or is deleted, thus making the
entire HOT-chain DEAD, the chain is broken, item-ids are marked
LP_DELETEd and A is redirected to itself. VACUUM can them remove A
and the associated index entries.


      A %
      o $  
         
      D               B *           C *
      o ^             o ^           o ^
      |               |             |
      |               |             |
      |               |             |
      v               v             v
  +--------+     +--------+     +--------+
  |   X    |     |    P   |     |   Z    |
  +--------+     +--------+     +--------+

     $ indicates redirect-dead (i.e. redirected to itself)


Thus line-pointer redirection gives us a great opportunity to
reuse the dead tuples in a page without cleaning up the index entries.
There is a 4 byte overhead per HOT-update chain, but to my mind
its still reasonable given that it helps us avoid heap and index
bloats and allows us to run VACUUM less frequently (or even completely
avoid it for best-case scenarios).