Incorrect result HASH SEMI JOIN with UUID key

WI-V5.0.5.1816 Firebird 5.0 2f91fa0
SubQueryConversion = true

recreate table uuid_1M_a(id binary(16) not null);
recreate table uuid_1M_b(id binary(16) not null);

create index idx_uuid_1M_b_id on uuid_1M_b(id);

set term ^;

execute block
as
  declare variable i int = 0;
begin
  while (i < 1000000) do
  begin
    insert into uuid_1M_a(id) values (gen_uuid());
    i = i + 1;
  end
end^

set term ;^

insert into uuid_1M_b(id)
select a.id from uuid_1M_a a;

commit;

select count(distinct id) from uuid_1M_a;

                COUNT
=====================
              1000000

select count(distinct id) from uuid_1M_b;

                COUNT
=====================
              1000000

set explain on;

select count(*)
from uuid_1M_a a
join uuid_1M_b b on a.id = b.id;

Select Expression
    -> Aggregate
        -> Filter
            -> Hash Join (inner)
                -> Table "UUID_1M_A" as "A" Full Scan
                -> Record Buffer (record length: 41)
                    -> Table "UUID_1M_B" as "B" Full Scan

                COUNT
=====================
              1000000

select count(*)
from uuid_1M_a a
where exists (select * from uuid_1M_b b where a.id = b.id);

Select Expression
    -> Aggregate
        -> Filter
            -> Hash Join (semi)
                -> Table "UUID_1M_A" as "A" Full Scan
                -> Record Buffer (record length: 41)
                    -> Table "UUID_1M_B" as "B" Full Scan

                COUNT
=====================
               999883                                            <----- What ????????????????????

But:

select count(*)
from uuid_1M_a a
where exists (select * from uuid_1M_b b where a.id = b.id and nullif(a.id, b.id) is null);

Sub-query
    -> Filter
        -> Table "UUID_1M_B" as "B" Access By ID
            -> Bitmap
                -> Index "IDX_UUID_1M_B_ID" Range Scan (full match)
Select Expression
    -> Aggregate
        -> Filter
            -> Table "UUID_1M_A" as "A" Full Scan

                COUNT
=====================
              1000000

The issue is reproducible in both version 5.0.5 and version 6.0.

The value 999883 can vary significantly if the test is rerun from scratch. It all depends on the generated UUID. Sometimes, everything works fine.

If SubQueryConversion = false result:

select count(*)
from uuid_1M_a a
where exists (select * from uuid_1M_b b where a.id = b.id);

Sub-query
    -> Filter
        -> Table "UUID_1M_B" as "B" Access By ID
            -> Bitmap
                -> Index "IDX_UUID_1M_B_ID" Range Scan (full match)
Select Expression
    -> Aggregate
        -> Filter
            -> Table "UUID_1M_A" as "A" Full Scan

                COUNT
=====================
              1000000

The error is not reproducible if the keys are integers

Root cause analysis of the SEMI JOIN bug

I believe I've identified the root cause. It is not in the hash table implementation itself (which is why INNER JOIN produces correct results), but in the way the SEMI JOIN path interacts with the bucket iteration logic.

The problem

When a hash collision occurs, multiple distinct join keys share the same 32-bit hash and therefore end up in the same bucket. Within the bucket, entries are ordered by hash, but entries with equal hashes may appear in any order relative to each other.

For SEMI JOIN, the current code stops after finding the first entry in the bucket whose hash matches the leader's hash:

// in HashJoin::fetchRecord()
if (hashTable->iterate(stream, impure->irsb_leader_hash, position))
{
    arg->locate(tdbb, position);
    if (arg->getRecord(tdbb))
        return true;   // <-- returns on the first hash match
}
if (m_joinType == JoinType::SEMI || m_joinType == JoinType::ANTI)
    return false;

If the first entry with the matching hash happens to have a different join key (a false positive due to a hash collision), the EXISTS predicate above the join rejects it, but the join node has already marked the leading row as processed:

// in HashJoin::internalGetRecord()
if (m_joinType == JoinType::SEMI || m_joinType == JoinType::ANTI)
{
    impure->irsb_flags |= irsb_mustread;   // <-- row considered done
    if (m_joinType == JoinType::ANTI)
        continue;
}

On the next call, a new leading row is fetched, and the row that actually had a match later in the same bucket is never re-examined. The result is a missing row in the output.

Why INNER JOIN is not affected

For INNER JOIN, irsb_mustread is not set on success. On subsequent calls, control flows into the else branch, which calls fetchRecord() again. The iterator inside the bucket advances, and eventually the correct entry is found. INNER JOIN effectively scans all entries with the same hash; SEMI JOIN does not.

Verification

This explains the observed behaviour:

INNER JOIN = correct count (all matches are eventually found).
SEMI JOIN = count decreases as the number of rows grows (more rows → more hash collisions → more false positives that mask the real match).
The same UUIDs are lost every time (the order of entries with equal hashes in a bucket is deterministic for a given dataset).

@sim1984

Hi @sim1984!

This sounds scary.
Every HASH JOIN affected? Every 5.x version affected?

Thank you!

Hi @sim1984!

This sounds scary. Every HASH JOIN affected? Every 5.x version affected?

No. Only if SubQueryConversion = true (disabled by default) and if the EXISTS clause is converted into a semi-join executed via hashing.

Note that reproducing this with integer keys is very difficult (though easy with UUIDs), but it is theoretically possible. The larger the table being hashed, the higher the likelihood of reproducing the issue.

An INNER JOIN executed via hashing always produces the correct result.

Thank you!

Fix #9158: Incorrect result HASH SEMI JOIN with UUID key. More comple…

A deterministic, two-row reproduction of the same SEMI-join defect, on plain INTEGER keys and with default settings on Firebird 6.0. It's caused by a second, non-random key collision: a NULL key and a 0 key always hash to the same value.

Environment: Firebird 6.0.0 (LI-T6.0.0.2179, source master @ 84f30a54c6), default firebird.conf. In this 6.0 source I can't find a SubQueryConversion setting: RseNode::processPossibleJoins converts IN/EXISTS without a config check, so on 6.0 this is reachable out of the box.

CREATE TABLE T (ID INTEGER, N INTEGER);
COMMIT;
INSERT INTO T VALUES (1, NULL);   -- the NULL must come first
INSERT INTO T VALUES (2, 0);
COMMIT;

SET PLAN ON;
SELECT ID FROM T WHERE N IN (SELECT N FROM T);
-- PLAN HASH ("PUBLIC"."T" NATURAL, "PUBLIC"."T" NATURAL)
-- expected: 2    actual: no rows

SELECT ID FROM T WHERE EXISTS (SELECT 1 FROM T T2 WHERE T2.N = T.N);
-- PLAN HASH ("PUBLIC"."T" NATURAL, "T2" NATURAL)
-- expected: 2    actual: no rows

The engine gives the right answer for the same predicate any other way:

SELECT ID, IIF(N IN (SELECT N FROM T), 'TRUE', 'NOT TRUE') FROM T → row 2 is TRUE
... WHERE N IN (SELECT N FROM T) OR 1 = 0 (no semi-join) → 2
... WHERE N IN (SELECT N FROM T ORDER BY N DESC) (the 0 streamed before the NULL) → 2
... WHERE N IN (SELECT COALESCE(N, -1) FROM T) (no NULL) → 2
with row 2 holding 5 instead of 0 → 2 (only 0 collides with NULL)

It also reproduces on NUMERIC and DOUBLE PRECISION columns and with = ANY (...).

Why NULL and 0 collide: HashJoin::computeHash() starts with memset(keyBuffer, 0, sub.totalKeyLength). When a key expression evaluates to NULL (EVL_expr() returns nullptr), nothing is written, so the key stays all-zero bytes. That's identical to a numeric 0, whose key is also all-zero (and floating-point zero is explicitly normalised to +0). The NULL row and the 0 row therefore always share a hash. The semi-join's first-candidate-only iteration, analysed above, then offers only the NULL row to the residual N = N, which is not TRUE, and the matching 0 behind it is never examined.

The SEMI iteration fix discussed here should cover this case too. Separately, encoding NULL distinctly in the key (or keeping NULL keys out of the hash table for equality joins, cf. #7769) would remove this collision at the source.

Found with the fire-crab differential test suite, which runs the same statements against a live Firebird 6 server and a re-implementation and flags any difference.

Report the semi-join NULL/0 bug upstream on FirebirdSQL/firebird#9158

Bump fire-crab: report the semi-join NULL/0 bug on FirebirdSQL/firebi…

Navigation Menu

Repository navigation

Incorrect result HASH SEMI JOIN with UUID key #9158

Root cause analysis of the SEMI JOIN bug

The problem

Why INNER JOIN is not affected

Verification

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Incorrect result HASH SEMI JOIN with UUID key #9158

Description

Activity

sim1984 commented on Sep 19, 2026

sim1984 commented on Sep 21, 2026

Root cause analysis of the SEMI JOIN bug

The problem

Why INNER JOIN is not affected

Verification

EPluribusUnum commented on Sep 22, 2026

sim1984 commented on Sep 22, 2026

mariuz commented on Oct 3, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions