I believe that PG back-end does not version index rows the way it does the data rows. Assume that the app updates a row frequently (several times in a second). For each update, PG will create a new version. However I believe the primary key index pointing to that row will point to only the first row and the back end has to work its way traversing the list until it finds the appropriate row matching the xmin/xmax. Does frequent vaccum take care of this by removing the dead rows and hence reducing the commute.