PG Bug reporting form <noreply(at)postgresql(dot)org> writes:
> Expected Result: All records that meet the criteria should be updated
> regardless of using index scan or seq scan.
> Actual Result: When PostgreSQL 16 uses index scan, it fails to find and
> update all records. By changing random_page_cost to a value that forces the
> use of seq scan, all records are updated correctly.
I see that the problematic plan involves a Merge Right Anti Join step,
which makes me guess that this is the same bug recently reported in
https://www.postgresql.org/message-id/flat/18522-c7a8956126afdfd0%40postgresql.org
Are you in a position to try the patch posted in that thread?
regards, tom lane