BUG #18526: 'UPDATE' inconsistency using index scan with 'NOT EXIST' after upgrading to PostgreSQL 16

The following bug has been logged on the website:

Bug reference: 18526
Logged by: Feliphe Pozzer
Email address: feliphepozzer(at)gmail(dot)com
PostgreSQL version: 16.3
Operating system: Ubuntu
Description:

After upgrading from PostgreSQL 15 to PostgreSQL 16, an UPDATE on our data
structure stopped functioning correctly. The data structure is randomly
generated, resulting in a variable number of updates.

Steps to Reproduce:
1 - Create the tables and indexes as per the provided script.
2 - Populate the tables with random data using the provided PL/pgSQL
blocks.
3 - Execute the following query to update the financial table

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.

Environment:
PostgreSQL Version: 16
Operating System: Ubuntu

Logs and Error Messages:
There are no specific error messages, but the unexpected behavior is
observed in the query execution plan.

Structure:

-- Creation of the financial table
CREATE TABLE financial (
id SERIAL PRIMARY KEY,
canceled BPCHAR(1),
settlement BPCHAR(1),
type VARCHAR(50),
description VARCHAR(50)
);

-- Creation of the account_movement table
CREATE TABLE account_movement (
id SERIAL PRIMARY KEY,
credit_invoice_id INT,
FOREIGN KEY (credit_invoice_id) REFERENCES financial(id)
);

-- Creation of the indexes
CREATE INDEX idx_financial_settlement ON financial USING btree
(settlement);
CREATE INDEX idx_account_movement_credit_invoice_id ON account_movement
USING btree (credit_invoice_id);

-- Populating random data for the financial table
DO
$$
BEGIN
FOR i IN 1..2500 LOOP
INSERT INTO financial (canceled, settlement, type)
VALUES (
(ARRAY['0', '1'])[floor(random() * 2 + 1)],
(ARRAY[NULL, 1])[floor(random() * 2 + 1)],
(ARRAY['type1', 'type2', 'type3', 'type4',
'type5'])[floor(random() * 5 + 1)]
);
END LOOP;
END
$$;

-- Populating random data for the account_movement table
DO
$$
BEGIN
FOR i IN 1..1000 LOOP
INSERT INTO account_movement (credit_invoice_id)
VALUES (
(ARRAY[NULL, (SELECT id FROM financial ORDER BY random() LIMIT
1)])[floor(random() * 2 + 1)]
);
END LOOP;
END
$$;

VACUUM ANALYZE financial, account_movement;

SET random_page_cost = 4;

UPDATE financial F SET description = '1'
WHERE canceled = '0' AND
settlement IS NULL AND
type = 'type5' AND
NOT EXISTS (SELECT 1 FROM account_movement AM WHERE AM.credit_invoice_id =
F.id);

SET random_page_cost = 1.1;

UPDATE financial F SET description = '1'
WHERE canceled = '0' AND
settlement IS NULL AND
type = 'type5' AND
NOT EXISTS (SELECT 1 FROM account_movement AM WHERE AM.credit_invoice_id =
F.id);

Additional Description:
I am unsure if this is a bug or incorrect usage of random_page_cost. This
same query worked perfectly in PostgreSQL 15, regardless of the execution
plan (using seq scan or index scan). To work around this issue, we had to
modify the query to correctly update the records.