Avoid index lookup for a NULL key if the condition is known to always be FALSE in this case

[AnatolyLoy]

The case contains three linked tables (see script below). The simple Query No1 and tricked Query No2 produced the same result, but Query No1 slowed it.

It looks like Firebird compares the NULL value of T1.T1_ID with every index value and spend resources...

CREATE TABLE T1 (T1_ID INTEGER NOT NULL, PRIMARY KEY (T1_ID)); CREATE TABLE T2 (T2_ID INTEGER NOT NULL, T1_ID INTEGER, PRIMARY KEY (T2_ID)); ALTER TABLE T2 ADD FOREIGN KEY (T1_ID) REFERENCES T1 (T1_ID); CREATE TABLE T3 (T3_ID INTEGER NOT NULL, T1_ID INTEGER, PRIMARY KEY (T3_ID)); ALTER TABLE T3 ADD FOREIGN KEY (T1_ID) REFERENCES T1 (T1_ID); -- Fill data: -- T1 - 1 000 recorsa -- T2 - 10 000 records, 1 000 of them referred to T1 -- T3 - 1 000 000 records, 1 000 of them referred to T1 EXECUTE BLOCK AS DECLARE VARIABLE L_T1_ID INTEGER; DECLARE VARIABLE L_T2_ID INTEGER; DECLARE VARIABLE L_T3_ID INTEGER; BEGIN L_T3_ID = 1; WHILE (L_T3_ID <= 1000000) DO BEGIN L_T1_ID = IIF(MOD(L_T3_ID, 1000) = 0, TRUNC(L_T3_ID/1000), NULL); L_T2_ID = IIF(MOD(L_T3_ID, 100) = 0, TRUNC(L_T3_ID/100), NULL); IF (L_T1_ID IS NOT NULL) THEN INSERT INTO T1 (T1_ID) VALUES (:L_T1_ID); INSERT INTO T3 (T3_ID, T1_ID) VALUES (:L_T3_ID, :L_T1_ID); IF (L_T2_ID IS NOT NULL) THEN INSERT INTO T2 (T2_ID, T1_ID) VALUES (:L_T2_ID, :L_T1_ID); L_T3_ID = L_T3_ID + 1; END END;

-- Query No1: Simple query and bad performance SELECT count(*) FROM t2 LEFT OUTER JOIN T1 ON T1.T1_ID = T2.T1_ID LEFT OUTER JOIN T3 ON T3.T1_ID = T1.T1_ID

Plan PLAN JOIN (JOIN (T2 NATURAL, T1 INDEX (RDB$PRIMARY294)), T3 INDEX (RDB$FOREIGN298))

Adapted Plan PLAN JOIN (JOIN (T2 NATURAL, T1 INDEX (INTEG_2830)), T3 INDEX (INTEG_2836))

------ Performance info ------ Prepare time = 0ms Execute time = 44s 797ms Avg fetch time = 44,797.00 ms Current memory = 40,174,016 Max memory = 74,196,768 Memory buffers = 2,048 Reads from disk to cache = 1,251 Writes from cache to disk = 0 Fetches from cache = 4,059,140

-- Query No2: Trick query and expected performance SELECT count(*) FROM T2 LEFT OUTER JOIN T1 on T1.T1_ID = T2.T1_ID LEFT OUTER JOIN T3 on T3.T1_ID = COALESCE(T1.T1_ID, -1)

Plan PLAN JOIN (JOIN (T2 NATURAL, T1 INDEX (RDB$PRIMARY294)), T3 INDEX (RDB$FOREIGN298))

Adapted Plan PLAN JOIN (JOIN (T2 NATURAL, T1 INDEX (INTEG_2830)), T3 INDEX (INTEG_2836))

------ Performance info ------ Prepare time = 0ms Execute time = 31ms Avg fetch time = 31.00 ms Current memory = 37,804,784 Max memory = 38,739,168 Memory buffers = 2,048 Reads from disk to cache = 1,042 Writes from cache to disk = 0 Fetches from cache = 63,145

[livius2]

This is a typical case, and I suppose the NULL comparison should be removed by the engine here, as this is a simple scenario. In more complex cases, however, it might be harder to detect such situations. Comparisons with NULL should be skipped, as they cannot return any rows. As a result, scanning the index for a NULL value is unnecessary.

[AnatolyLoy]

This is a typical case, and I suppose the NULL comparison should be removed by the engine here, as this is a simple scenario. In more complex cases, however, it might be harder to detect such situations. Comparisons with NULL should be skipped, as they cannot return any rows. As a result, scanning the index for a NULL value is unnecessary.

Exactly. It's unfortunate. The simple query for the case mentioned above produces the same result - The OUTER JOIN compares NULLs 9,000 times with all 1,000,000 index values... So, it's a spend server resource whenever you try to left-join the non-mandatory column with many NULL values, Just a full index scan... Every comparison. Brrrrrrr.....

SELECT COUNT() FROM T2 -- 10 000 records LEFT OUTER JOIN T3 ON T3.T1_ID = NULL -- 1 000 000 index scans

Plan

PLAN JOIN (T2 NATURAL, T3 INDEX (RDB$FOREIGN300))

Adapted Plan

PLAN JOIN (T2 NATURAL, T3 INDEX (INTEG_2846))

------ Performance info ------ Prepare time = 15ms Execute time = 49s 625ms Avg fetch time = 49,625.00 ms Current memory = 56,801,616 Max memory = 57,807,920 Memory buffers = 3,000 Reads from disk to cache = 0 Writes from cache to disk = 0 Fetches from cache = 4,480,148

[AnatolyLoy]

The Firebird 2.5 makes the same result. The INNER JOIN makes the same result. SELECT COUNT() FROM T2 -- 10 000 records JOIN T3 ON T3.T1_ID = NULL -- 1 000 000 index scans

Even do not try to run

SELECT COUNT() FROM T2 -- 10 000 index scans JOIN T3 ON T3.T1_ID = T2.T1_ID -- 1 000 000 records

The server has chosen the T3 -> T2 plan. and we will have about 1 000 000 attempts to make scans for 1000 index values :(

So, it looks like a non-optimal execution in IndexTableScan...