search

FirebirdSQL / firebird

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

FB5 slower execution by List Scan vs Bitmap Or #7922

Open livius2 opened 11 months ago

livius2 commented 11 months ago

FB5 slower execution by List Scan vs Bitmap Or

Compare result between FB3 vs FB5 RC2 recent snapshot.

use scripts and data generator from https://github.com/FirebirdSQL/firebird/issues/7904

and add this:

CREATE TABLE DYREKCJA
(
DYR_ID SMALLINT NOT NULL,
CONSTRAINT PK_DYREKCJA PRIMARY KEY(DYR_ID)
);
commit;
INSERT INTO DYREKCJA
SELECT DISTINCT DYR_ID FROM ROZLICZENIE;
commit;

ALTER TABLE ROZLICZENIE ADD CONSTRAINT FK_ROZLICZENIE__DYREKCJA  FOREIGN KEY (DYR_ID) REFERENCES DYREKCJA (DYR_ID);

ALTER TABLE ROZLICZENIE
ADD  ROZLICZ_PROGRAM CHAR(1),
ADD  ROZLICZ_PROGRAM_OKRES CHAR(7);

UPDATE ROZLICZENIE RL SET RL.ROZLICZ_PROGRAM='T', RL.ROZLICZ_PROGRAM_OKRES=RL.OKRES_NUMER WHERE RL.ROZLICZ_NR_POZ BETWEEN 3 AND 8;
commit;

CREATE INDEX IXA_ROZLICZENIE__PROGRAM_OKRES ON ROZLICZENIE (ROZLICZ_PROGRAM_OKRES,DYR_ID);
CREATE INDEX IXA_ROZLICZENIE__RODZ_DZIAL ON ROZLICZENIE (ROZLICZ_RODZ_DZIAL_ID);

SET STATISTICS INDEX PK_DOK_ROZLICZENIOWY;
SET STATISTICS INDEX PK_DYREKCJA;
SET STATISTICS INDEX PK_RODZAJ_UMOWY;
SET STATISTICS INDEX FK_ROZLICZENIE__DYREKCJA;
SET STATISTICS INDEX FK_ROZLICZENIE__UMOWA;
SET STATISTICS INDEX IXA_ROZLICZENIE__PROGRAM_OKRES;
SET STATISTICS INDEX PK_ROZLICZENIE;
SET STATISTICS INDEX ROZLICZENIE_FK4;
SET STATISTICS INDEX FK_UMOWA__RODZAJ_UMOWY;
SET STATISTICS INDEX PK_UMOWA;

set cache buffers to 131072;

and then run query twice, ignore first cold run


SELECT
    RL.DYR_ID
    , RL.ROZLICZ_RODZ_DZIAL_ID
    , SUM(RL.ROZLICZ_KWOTA_ROZLICZONA)
FROM
    ROZLICZENIE RL
    INNER JOIN DOK_ROZLICZENIOWY DK ON DK.DOK_ROZLICZENIOWY_ID = RL.DOK_ROZLICZENIOWY_ID
WHERE
    RL.OKRES_NUMER BETWEEN '15'
    AND '18'
    AND RL.ROZLICZ_RODZ_DZIAL_ID IN('1', '5', '7', '9')
    AND DK.DOK_ROZLICZENIOWY_INKASO = '1'
    AND RL.ROZLICZ_PROGRAM='T'
    AND RL.ROZLICZ_PROGRAM_OKRES <= '19'
GROUP BY
    RL.DYR_ID
    , RL.ROZLICZ_RODZ_DZIAL_ID

Result on FB3:

525959 fetches, 0 marks, 0 reads, 0 writes.
0 inserts, 0 updates, 0 deletes, 410321 index, 40 seq.
Delta memory: 0 bytes.
RDB$FIELDS: 13 reads index. 
RDB$INDICES: 36 reads index. 
RDB$RELATION_FIELDS: 26 reads index. 
RDB$RELATIONS: 14 reads index. 
DOK_ROZLICZENIOWY: 40 reads sequence. 
ROZLICZENIE: 410232 reads index. 
Total execution time: 3.510s
Select Expression
    -> Aggregate
        -> Sort (record length: 100, key length: 16)
            -> Nested Loop Join (inner)
                -> Filter
                    -> Table "DOK_ROZLICZENIOWY" as "DK" Full Scan
                -> Filter
                    -> Table "ROZLICZENIE" as "RL" Access By ID
                        -> Bitmap And
                            -> Bitmap And
                                -> Bitmap
                                    -> Index "ROZLICZENIE_FK4" Range Scan (full match)
                                -> Bitmap
                                    -> Index "IXA_ROZLICZENIE__PROGRAM_OKRES" Range Scan (upper bound: 1/2)
                            -> Bitmap Or
                                -> Bitmap Or
                                    -> Bitmap Or
                                        -> Bitmap
                                            -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match)
                                        -> Bitmap
                                            -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match)
                                    -> Bitmap
                                        -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match)
                                -> Bitmap
                                    -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match)

Result on FB5

514802 fetches, 0 marks, 0 reads, 0 writes.
0 inserts, 0 updates, 0 deletes, 410250 index, 40 seq.
Delta memory: 0 bytes.
RDB$INDICES: 18 reads index. 
DOK_ROZLICZENIOWY: 40 reads sequence. 
ROZLICZENIE: 410232 reads index. 
Total execution time: 5.441s
Select Expression
    -> Aggregate
        -> Sort (record length: 100, key length: 16)
            -> Nested Loop Join (inner)
                -> Filter
                    -> Table "DOK_ROZLICZENIOWY" as "DK" Full Scan
                -> Filter
                    -> Table "ROZLICZENIE" as "RL" Access By ID
                        -> Bitmap And
                            -> Bitmap And
                                -> Bitmap
                                    -> Index "ROZLICZENIE_FK4" Range Scan (full match)
                                -> Bitmap
                                    -> Index "IXA_ROZLICZENIE__PROGRAM_OKRES" Range Scan (upper bound: 1/2)
                            -> Bitmap
                                -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" List Scan (full match)
dyemanov commented 11 months ago

I reduced this test case to queries:

SELECT count(*)
FROM ROZLICZENIE RL
WHERE RL.OKRES_NUMER BETWEEN '15' AND '18'
  AND RL.ROZLICZ_RODZ_DZIAL_ID IN ('1', '5', '7', '9')
  AND RL.ROZLICZ_PROGRAM = 'T'
  AND RL.ROZLICZ_PROGRAM_OKRES <= '19';

SELECT count(*)
FROM ROZLICZENIE RL
WHERE RL.OKRES_NUMER BETWEEN '15' AND '18'
  AND (RL.ROZLICZ_RODZ_DZIAL_ID = '1'
    OR RL.ROZLICZ_RODZ_DZIAL_ID = '5'
    OR RL.ROZLICZ_RODZ_DZIAL_ID = '7'
    OR RL.ROZLICZ_RODZ_DZIAL_ID = '9')
  AND RL.ROZLICZ_PROGRAM = 'T'
  AND RL.ROZLICZ_PROGRAM_OKRES <= '19';

and get the following output in ISQL (used latest v3 snapshot and v5.0 RC2, with cache buffers = 60000 to avoid the OS filesystem cache being disabled):

v3.0

SQL> SELECT count(*)
CON> FROM ROZLICZENIE RL
CON> WHERE RL.OKRES_NUMER BETWEEN '15' AND '18'
CON>   AND RL.ROZLICZ_RODZ_DZIAL_ID IN ('1', '5', '7', '9')
CON>   AND RL.ROZLICZ_PROGRAM = 'T'
CON>   AND RL.ROZLICZ_PROGRAM_OKRES <= '19';

Select Expression
    -> Aggregate
        -> Filter
            -> Table "ROZLICZENIE" as "RL" Access By ID
                -> Bitmap And
                    -> Bitmap
                        -> Index "IXA_ROZLICZENIE__PROGRAM_OKRES" Range Scan (upper bound: 1/2)
                    -> Bitmap Or
                        -> Bitmap Or
                            -> Bitmap Or
                                -> Bitmap
                                    -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match)
                                -> Bitmap
                                    -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match)
                            -> Bitmap
                                -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match)
                        -> Bitmap
                            -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match)

                COUNT 
===================== 
                66792 

Current memory = 533323472
Delta memory = -112
Max memory = 540647168
Elapsed time = 0.260 sec
Cpu = 0.260 sec
Buffers = 60000
Reads = 0
Writes = 0
Fetches = 460734
SQL> 
SQL> SELECT count(*)
CON> FROM ROZLICZENIE RL
CON> WHERE RL.OKRES_NUMER BETWEEN '15' AND '18'
CON>   AND (RL.ROZLICZ_RODZ_DZIAL_ID = '1'
CON>     OR RL.ROZLICZ_RODZ_DZIAL_ID = '5'
CON>     OR RL.ROZLICZ_RODZ_DZIAL_ID = '7'
CON>     OR RL.ROZLICZ_RODZ_DZIAL_ID = '9')
CON>   AND RL.ROZLICZ_PROGRAM = 'T'
CON>   AND RL.ROZLICZ_PROGRAM_OKRES <= '19';

Select Expression
    -> Aggregate
        -> Filter
            -> Table "ROZLICZENIE" as "RL" Access By ID
                -> Bitmap And
                    -> Bitmap
                        -> Index "IXA_ROZLICZENIE__PROGRAM_OKRES" Range Scan (upper bound: 1/2)
                    -> Bitmap Or
                        -> Bitmap Or
                            -> Bitmap Or
                                -> Bitmap
                                    -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match)
                                -> Bitmap
                                    -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match)
                            -> Bitmap
                                -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match)
                        -> Bitmap
                            -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match)

                COUNT 
===================== 
                66792 

Current memory = 533323584
Delta memory = 112
Max memory = 540647168
Elapsed time = 0.256 sec
Cpu = 0.260 sec
Buffers = 60000
Reads = 0
Writes = 0
Fetches = 460734

as expected, both plans and performance are the same.

v5.0

SQL> SELECT count(*)
CON> FROM ROZLICZENIE RL
CON> WHERE RL.OKRES_NUMER BETWEEN '15' AND '18'
CON>   AND RL.ROZLICZ_RODZ_DZIAL_ID IN ('1', '5', '7', '9')
CON>   AND RL.ROZLICZ_PROGRAM = 'T'
CON>   AND RL.ROZLICZ_PROGRAM_OKRES <= '19';

Select Expression
    -> Aggregate
        -> Filter
            -> Table "ROZLICZENIE" as "RL" Access By ID
                -> Bitmap And
                    -> Bitmap
                        -> Index "IXA_ROZLICZENIE__PROGRAM_OKRES" Range Scan (upper bound: 1/2)
                    -> Bitmap
                        -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" List Scan (full match)

                COUNT 
===================== 
                66792 

Current memory = 520738400
Delta memory = -12944
Max memory = 520787584
Elapsed time = 0.244 sec
Cpu = 0.240 sec
Buffers = 60000
Reads = 0
Writes = 0
Fetches = 447168
SQL> 
SQL> SELECT count(*)
CON> FROM ROZLICZENIE RL
CON> WHERE RL.OKRES_NUMER BETWEEN '15' AND '18'
CON>   AND (RL.ROZLICZ_RODZ_DZIAL_ID = '1'
CON>     OR RL.ROZLICZ_RODZ_DZIAL_ID = '5'
CON>     OR RL.ROZLICZ_RODZ_DZIAL_ID = '7'
CON>     OR RL.ROZLICZ_RODZ_DZIAL_ID = '9')
CON>   AND RL.ROZLICZ_PROGRAM = 'T'
CON>   AND RL.ROZLICZ_PROGRAM_OKRES <= '19';

Select Expression
    -> Aggregate
        -> Filter
            -> Table "ROZLICZENIE" as "RL" Access By ID
                -> Bitmap And
                    -> Bitmap
                        -> Index "IXA_ROZLICZENIE__PROGRAM_OKRES" Range Scan (upper bound: 1/2)
                    -> Bitmap Or
                        -> Bitmap Or
                            -> Bitmap Or
                                -> Bitmap
                                    -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match)
                                -> Bitmap
                                    -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match)
                            -> Bitmap
                                -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match)
                        -> Bitmap
                            -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match)

                COUNT 
===================== 
                66792 

Current memory = 520751344
Delta memory = 12944
Max memory = 520787584
Elapsed time = 0.248 sec
Cpu = 0.250 sec
Buffers = 60000
Reads = 0
Writes = 0
Fetches = 447192

As far as I see, there's no difference between Bitmap OR and List scans in v5 and there's no difference in performance between v3 and v5.

As for your original query, it executes 2.45s in v3 vs 2.55s in v5. A little bit slower, but not the amount worth worrying.

livius2 commented 11 months ago

Your query is even a little faster on FB5 for me

FB3

447860 fetches, 0 marks, 0 reads, 0 writes.
0 inserts, 0 updates, 0 deletes, 410262 index, 0 seq.
Delta memory: 0 bytes.
RDB$INDICES: 30 reads index. 
ROZLICZENIE: 410232 reads index. 
Total execution time: 0.378s

FB5

437439 fetches, 0 marks, 0 reads, 0 writes.
0 inserts, 0 updates, 0 deletes, 410232 index, 0 seq.
Delta memory: 0 bytes.
ROZLICZENIE: 410232 reads index. 
Total execution time: 0.357s

But my oryginal query is every times slower:

FB3

525848 fetches, 0 marks, 0 reads, 0 writes.
0 inserts, 0 updates, 0 deletes, 410268 index, 40 seq.
Delta memory: 0 bytes.
RDB$INDICES: 36 reads index. 
DOK_ROZLICZENIOWY: 40 reads sequence. 
ROZLICZENIE: 410232 reads index. 
Total execution time: 3.203s

FB5

514772 fetches, 0 marks, 0 reads, 0 writes.
0 inserts, 0 updates, 0 deletes, 410232 index, 40 seq.
Delta memory: 0 bytes.
DOK_ROZLICZENIOWY: 40 reads sequence. 
ROZLICZENIE: 410232 reads index. 
Total execution time: 5.107s

Maybe my diagnosis that the slowdown is caused by LIST SCAN was wrong, but the slowdown is there and it is significant 3.203s vs 5.107s.

to avoid the OS filesystem cache being disabled

Why do you concern about this when there is still free room in FB cache? I am really curious.

dyemanov commented 10 months ago

I played more with this test case and yes, v5 is constantly slower, although with a smaller degree than you see (2.5s vs 2.9s). This happens even with the IN optimization internally disabled, so it's really unrelated. Some other change(s) seem to affect the performance.

hvlad commented 9 months ago

I tried original query with

FB 3.0.12.33723

SELECT RL.DYR_ID , RL.ROZLICZ_RODZ_DZIAL_ID , SUM(RL.ROZLICZ_KWOTA_ROZLICZONA) FROM ROZLICZENIE RL INNER JOIN DOK_ROZLICZENIOWY DK ON DK.DOK_ROZLICZENIOWY_ID = RL.DOK_ROZLICZENIOWY_ID WHERE RL.OKRES_NUMER BETWEEN '15' AND '18' AND RL.ROZLICZ_RODZ_DZIAL_ID IN('1', '5', '7', '9') AND DK.DOK_ROZLICZENIOWY_INKASO = '1' AND RL.ROZLICZ_PROGRAM='T' AND RL.ROZLICZ_PROGRAM_OKRES <= '19' GROUP BY RL.DYR_ID, RL.ROZLICZ_RODZ_DZIAL_ID; Select Expression -> Aggregate -> Sort (record length: 100, key length: 16) -> Nested Loop Join (inner) -> Filter -> Table "DOK_ROZLICZENIOWY" as "DK" Full Scan -> Filter -> Table "ROZLICZENIE" as "RL" Access By ID -> Bitmap And -> Bitmap And -> Bitmap -> Index "ROZLICZENIE_FK4" Range Scan (full match) -> Bitmap -> Index "IXA_ROZLICZENIE__PROGRAM_OKRES" Range Scan (upper bound: 1/2) -> Bitmap Or -> Bitmap Or -> Bitmap Or -> Bitmap -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match) -> Bitmap -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match) -> Bitmap -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match) -> Bitmap -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" Range Scan (full match) Current memory = 1145086160 Delta memory = 0 Max memory = 1156064912 Elapsed time = 2.483 sec Buffers = 130000 Reads = 0 Writes = 0 Fetches = 563993

FB 5.0.1.1318

SELECT RL.DYR_ID , RL.ROZLICZ_RODZ_DZIAL_ID , SUM(RL.ROZLICZ_KWOTA_ROZLICZONA) FROM ROZLICZENIE RL INNER JOIN DOK_ROZLICZENIOWY DK ON DK.DOK_ROZLICZENIOWY_ID = RL.DOK_ROZLICZENIOWY_ID WHERE RL.OKRES_NUMER BETWEEN '15' AND '18' AND RL.ROZLICZ_RODZ_DZIAL_ID IN('1', '5', '7', '9') AND DK.DOK_ROZLICZENIOWY_INKASO = '1' AND RL.ROZLICZ_PROGRAM='T' AND RL.ROZLICZ_PROGRAM_OKRES <= '19' GROUP BY RL.DYR_ID, RL.ROZLICZ_RODZ_DZIAL_ID; Select Expression -> Aggregate -> Sort (record length: 92, key length: 16) -> Nested Loop Join (inner) -> Filter -> Table "DOK_ROZLICZENIOWY" as "DK" Full Scan -> Filter -> Table "ROZLICZENIE" as "RL" Access By ID -> Bitmap And -> Bitmap And -> Bitmap -> Index "ROZLICZENIE_FK4" Range Scan (full match) -> Bitmap -> Index "IXA_ROZLICZENIE__PROGRAM_OKRES" Range Scan (upper bound: 1/2) -> Bitmap -> Index "IXA_ROZLICZENIE__RODZ_DZIAL" List Scan (full match) Current memory = 1117343856 Delta memory = 0 Max memory = 1125586240 Elapsed time = 2.164 sec Buffers = 130000 Reads = 0 Writes = 0 Fetches = 548987

As you see, FB5 is faster for me: 2.483 sec vs 2.164 sec

livius2 commented 9 months ago

Hi @hvlad, on which OS? I have tested on Windows 10 and some Windows Server (i will send info which if it matters but must back to work).

hvlad commented 9 months ago

Win10, Intel, i7-12700