David Blasby <dblasby@refractions.net> writes:
> I just did another vacuum analyse on the table:

Ah, here we go:

> INFO:  "csn_edges": found 0 removable, 16289929 nonremovable row 
> versions in 2783986 pages

That works out to just under 6 rows per 8K page, which wouldn't be too
bad if the rows are 1K wide on average, but are they?  (You might want
to run contrib/pgstattuple to get some exact information about average
tuple size.)

> INFO:  analyzing "public.csn_edges"
> INFO:  "csn_edges": 2783986 pages, 3000 rows sampled, 6724 estimated 
> total rows

This looks like a smoking gun to me.  The huge underestimate of number
of rows from ANALYZE is a known failure mode of the existing sampling
method when the early pages of the table are thinly populated.  (Manfred
just fixed that for 7.5, btw.)

I think you want to VACUUM FULL or CLUSTER the table, and then take a
look at your FSM settings and routine vacuuming frequency to see if
you need to adjust them to keep this from happening again.
        regards, tom lane