Inefficient evaluation of expressions like rdb$db_key <= ? after mass delete

[hvlad]

Currently, engine evaluates expression with upper limit on DBKEY after some available record is found.
Here, available is: non-deleted and visible to the current transaction.

After mass DELETE there could be a lot of deleted records before one available will be found. I.e. engine could read many more records beyond of upper limit on DBKEY before check is made.

Thus it will be much more effective to check for DBKEY's upper limit more early, before check for record availability.

[hvlad]

Steps to reproduce.

create table t1
(
  id int not null,
  val varchar(256)
);
commit;

-- fill with some data
set term ^;

execute block as
declare n int = 0;
declare s varchar(36);
begin
  while (n < 1000000) do
  begin
    n = n + 1;
    s = UUID_TO_CHAR(GEN_UUID());
    insert into t1 (id, val) values (:n, lpad('', 256, :s));
  end
end
^
set term ;^

commit;

-- get relation ID and number of pointer pages
select p.rdb$relation_id, p.rdb$page_sequence
  from rdb$pages p join rdb$relations r on p.rdb$relation_id = r.rdb$relation_id
 where r.rdb$relation_name = 'T1'
   and p.rdb$page_type = 4
order by 2 desc rows 1;

RDB$RELATION_ID	RDB$PAGE_SEQUENCE
128	23

set stat;

-- read records from PP 20 only
select count(*), min(id), max(id) from t1
 where rdb$db_key >= make_dbkey(128, 0, 0, 20) and rdb$db_key < make_dbkey(128, 0, 0, 21);

...
Fetches = 48971

-- read records from PP 20 and up to the end
select count(*), min(id), max(id) from t1
 where rdb$db_key >= make_dbkey(128, 0, 0, 20);

Fetches = 174657

-- delete records from PP 20 and up to the end
delete from t1
 where rdb$db_key >= make_dbkey(128, 0, 0, 20);

-- read records from PP 20 only
select count(*), min(id), max(id) from t1
 where rdb$db_key >= make_dbkey(128, 0, 0, 20) and rdb$db_key < make_dbkey(128, 0, 0, 21);

Fetches = 174652

It shows that select after mass delete reads much more than necessary.

[aafemt]

Isn't it good for garbage collection?

[hvlad]

No. And it is very bad for parallel backup.