`EXISTS` query over a fan-out index may incorrectly return the parent record multiple times

[RobertBrunel]

An EXISTS subquery over an ARRAY that is matched to a fan-out index can return the same parent record multiple times instead of just once. This happens when the semi-join predicate can have multiple matches for a given parent row; for example, when it is an inequality comparison.

Example

CREATE TABLE vendors (id BIGINT, fruits STRING ARRAY, PRIMARY KEY (id))

CREATE INDEX fruits_idx AS
  SELECT fs.f FROM vendors, (SELECT f FROM vendors.fruits AS f) AS fs
  ORDER BY fs.f

INSERT INTO vendors VALUES
  (1, ['apple', 'apricot', 'banana']),
  (2, ['cherry', 'date']),
  (3, ['avocado']);

-- Vendor 1 has 2 elements less than 'b'.
SELECT id FROM vendors WHERE EXISTS (SELECT f FROM vendors.fruits AS f WHERE f < 'b');

Expected result:

{ID: 1}, {ID: 3}

Actual result:

{ID: 1}, {ID: 1}, {ID: 3}

Query plan:

COVERING(FRUITS_IDX [[LESS_THAN @c18]] -> [ID: KEY:[2]]) | MAP (_.ID AS ID)

Note that the query plan does not perform any kind of deduplication on the parent key ID.

Notes

• Equality predicates such as f = 'apple' do not have this problem, since fan-out indexes perform an implicit duplication of the ARRAY elements when they are populated. So such semi-join conditions can have at most one match per parent row.

[RobertBrunel]

Tangentially related issue: #3896