> We lock the table as a precaution, with the understanding that we are > undergoing a "small" downtime to finish replacing the int id by the new > bigint
Ah, sorry I overlooked that most row updates are done pre-transaction in a preliminary step: /* in batches, we update all the rows to new_id = id */
No worries. I suppose the answer to the original question, which is how to avoid a table scan when adding a primary key constraint to a newly backfilled column is "there is no way"? Downtime might be at least as long as the table scan.