Skip to content

Do not write data to hash table or do not sort (merge join) if join keys are NULL #7769

Open
@sim1984

Description

@sim1984

I wrote a simple test to test the speed of MERGE JOIN.

RECREATE TABLE BIG_1 (
  ID_1    BIGINT NOT NULL,
  F_1     BIGINT,
  CONSTRAINT PK_BIG_1 PRIMARY KEY(ID_1)
);

RECREATE TABLE BIG_2 (
  ID_2    BIGINT NOT NULL,
  F_2     BIGINT,
  CONSTRAINT PK_BIG_2 PRIMARY KEY(ID_2)
);

SET TERM ^;

EXECUTE BLOCK
AS
DECLARE I BIGINT;
DECLARE A BIGINT;
BEGIN
  I = 0;
  WHILE (I < 2000000) DO
  BEGIN
    I = I + 1;
    A = NULL;
    IF(MOD(I, 19) = 0)
      THEN A = I;
    INSERT INTO BIG_1(ID_1, F_1)
    VALUES (:I, :A);
  END

  I = 0;
  WHILE (I < 1500000) DO
  BEGIN
    I = I + 1;
    A = NULL;
    IF(MOD(I, 13) = 0)
      THEN A = I;
    INSERT INTO BIG_2(ID_2, F_2)
    VALUES (:I, :A);
  END
END^

SET TERM ;^

COMMIT;

As you can see, most of the field values by which tables are joined are NULL.

And execute simple query. I didn't wait for the result.

SELECT COUNT(*)
FROM
  BIG_1
  JOIN BIG_2 ON BIG_2.F_2 = BIG_1.F_1

Now we rewrite it in an equivalent form:

SELECT COUNT(*)
FROM
  BIG_1
  JOIN BIG_2 ON BIG_2.F_2 = BIG_1.F_1
WHERE BIG_2.F_2 IS NOT NULL
Select Expression
    -> Aggregate
        -> Filter
            -> Hash Join (inner)
                -> Table "BIG_1" Full Scan
                -> Record Buffer (record length: 33)
                    -> Filter
                        -> Table "BIG_2" Full Scan

                COUNT
=====================
                 6072

Current memory = 1806305664
Delta memory = 0
Max memory = 1811848224
Elapsed time = 0.944 sec
Buffers = 204800
Reads = 0
Writes = 0
Fetches = 3596854

This is understandable: in a hash table, many entries with the value NULL fall into one bucket.

Why does the optimizer add records with NULL values into a hash table? Why isn't the filter applied implicitly? After all, for an internal join of tables using HASH/MERGE JOIN, it is a priori clear that the condition will be false.

Tried it in 4.0 and 5.0. No difference. although I don't understand why MERGE JOIN is so slow in this case.

Activity

dyemanov

dyemanov commented on Sep 28, 2023

@dyemanov
Member

The algorithm does not check whether equality or IS NOT DISTINCT FROM is used as a join condition (both options are possible), and preserve NULLs to handle both cases. I agree such a check could be added to improve the performance.

sim1984

sim1984 commented on Sep 28, 2023

@sim1984
Author

Still, more often the join is made using equality, and NULL is not such a rare value. Therefore, it would be nice to add such a check. Of course, already in 6.0.

self-assigned this
on Sep 28, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

    Development

    Participants

    @dyemanov@sim1984

    Issue actions

      Do not write data to hash table or do not sort (merge join) if join keys are NULL · Issue #7769 · FirebirdSQL/firebird