Meanwhile, I started experimenting with partitioning the table into smaller tables, each holding rows with ID spanning 1 million values and using this approach, the UPDATE takes 300ms. I have to check if all the SELECTs I am issuing against the original table keep their performance, but so far it seems they do, if the appropriate indexes are present on the child tables. I was worried about the overhead of each query having to go through all (currently) 58 partition tables, but it seems like it's not that big of a deal.