PostgreSQL: Running SELECT DISTINCT ON ~700m rows - how to optimize?
Thanks to ypercube's tip in the comments above, I was able to keep the time per chunk of the query constant, and so good enough for my one-off purposes. I'm now running:

SELECT DISTINCT ON (id) id, data
FROM table
WHERE id &gt; @last_max_id
ORDER BY id
LIMIT 250000


Takes about 1 minute per query. My whole process will take about 48 hours, but that's good enough.

Could definitely optimize further with multithreading if better performance were needed.

I also noticed that using a cursor would have probably worked similarly well:

BEGIN TRANSACTION;
DECLARE my_cursor CURSOR
FOR SELECT DISTINCT ON (id)
      id, raw_data
FROM table
ORDER BY id;

FETCH 100000 FROM my_cursor;
FETCH 100000 FROM my_cursor;
FETCH 100000 FROM my_cursor;


The FETCH's ran for about 100s, 110s, and 90s respectively so I imagine that scales linearly as well.