FirebirdSQL / firebird

Firebird server, client and tools
https://firebirdsql.org
1.26k stars 217 forks source link

NULLs should be skipped during index navigation when there's no lower bound and matched conditions are known to ignore NULLs #8291

Closed dyemanov closed 4 weeks ago

dyemanov commented 4 weeks ago

Since v2.0 we have an optimization that skips NULL keys in the beginning of the ASC index if the retrieval is known to ignore NULL values, i.e. it does not involve IS [NOT] NULL and IS [NOT] DISTINCT FROM conditions matched with an index. However, it was disabled for index navigation (i.e. ORDER BY mapped to an index). This is correct for a full index scan (no conditions matched), but it should be enabled if the navigational retrieval has also upper bound key(s) defined and these matches are known to treat NULLs as FALSE. Currently it returns every NULL key found inside the index to be evaluated at the record level and then ignored, just wasting CPU cycles.

Example:

create table t (id int);

insert into t
select case when mod(val, 2) = 0 then null else val end from (
  select row_number() over() as val
  from rdb$types, rdb$types, rdb$types
  rows 1000000
);

commit;
create index it on t(id);

set stat on;
set explain on;

SELECT count(*) FROM T WHERE ID < 3;

Select Expression
    -> Aggregate
        -> Filter
            -> Table "T" Access By ID
                -> Bitmap
                    -> Index "IT" Range Scan (upper bound: 1/1)

                COUNT 
===================== 
                    1 

-- Fetches = 4

SELECT count(*) from (SELECT ID FROM T WHERE ID < 3 ORDER BY ID);

Select Expression
    -> Aggregate
        -> Filter
            -> Table "T" Access By ID
                -> Index "IT" Range Scan (upper bound: 1/1)

                COUNT 
===================== 
                    1 

-- Fetches = 1007094 (1775 when NULLs are skipped)
dyemanov commented 4 weeks ago

The current NULLs skipping code is still sub-optimal, number of page fetches shows that (still more than expected). But this is to be addressed separately and only in the master branch.