Incorrect result HASH SEMI JOIN with UUID key

[sim1984]

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

[sim1984]

The error is not reproducible if the keys are integers

[sim1984]

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).

[EPluribusUnum]

Hi @sim1984!

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

Thank you!

[sim1984]

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!