Biblioteca

Detailed New Features of Firebird 5. Part 1: Improvements in Optimizer

This material is sponsored and created with the sponsorship and support of IBSurgeon, vendor of HQbird (advanced distribution of Firebird) and supplier of performance optimization, migration and technical support services

The material is licenses under Public Documentation License https://www.firebirdsql.org/file/documentation/html/en/licenses/pdl/public-documentation-license.html

Preface

Recently Firebird Project has released Release Candidate СУБД Firebird 5.0, it means that Firebird 5.0 final release is very, very close, and now it is a good time to learn about new features of Firebird 5. Firebird 5 is the 8^th major release of Firebird, and it seems like it will be one of the best releases so far.

In Firebird 5.0 Firebird Project had focus on performance improvements in various areas:

Optimizer improvements – SQLs runs faster due to better execution plans
Scalability in multi-user environments – Firebird can serve more concurrent connections and queries in highly concurrent environments
Parallel backup, restore, sweep, index creation – up to 6-10x faster (depends on hardware)
Cache of compiled prepared statements – up to 25% of improvement for frequent queries
Improved compression of records – Firebird 5.0 works faster with large VARCHARs
Profiling plugin – identify bottlenecks and slow code inside complex stored procedures and triggers

Due to the large amount of the material, we will split it to several parts, and we start with the improvements in the optimizer of Firebird.

It is the most practical part which directly improves the performance of SQLs for databases of any size, from 1Gb to 1Tb.

1. Improvements in Optimizer

The optimizer is a part of Firebird database engine which is responsible for decision: how to execute the SQL on the specific database in the fastest way. In v5.0 Firebird optimizer has received the biggest amount of changes since version 2.0. Let’s see in details what was improved, with examples and performance comparisons.

1.1. Cost estimation of HASH vs NESTED LOOP JOIN

HASH JOIN appeared in Firebird 3.0.

The [simplified] idea of HASH JOIN is to cache the small dataset (e.g., a small table) into the memory, calculate hashes of keys, and use the hash of the key to join with larger dataset (e.g., a large table). If there will be the same hash for the several records, they will be processed one by one, to find the exactly the same key. HASH JOIN works only with strict key equality (i.e., =), and allows expressions with keys.

Until version 5.0, Firebird optimizer uses HASH JOIN only in a case of absence of indices for the join condition. If there is index, optimizer of pre-v5 version will use NESTED LOOP JOIN (usually it is INNER JOIN) with index. However, it is not always the fastest way: for example, if very large table is joined with small table using the primary key using INNER JOIN, each record of small table will be read multiple times (data pages and appropriate index pages). With HASH JOIN, the small table will be read once, cached, and calculated hashes will be used to join with very large table.

The obvious question is when to use HASH JOIN and when NESTED LOOP JOIN (INNER JOIN in majority cases)? It is relatively easy to decide to use HASH when small table like CLIENT_COUNTRY is joining with large table like INVOICES, but not all situations are clear. Until Firebird 5, the decision was the sole responsibility of the developer, since it required change of the text of SQL query, now it is done by Firebird optimizer using cost estimation algorithm.

To better understand the effect of HASH JOIN, let’s consider how the same query will be executed in Firebird 4.0 and in Firebird 5.0. To analyze the difference, we have EXPLAIN PLAN, query execution statistics and extended statistics from the trace.

In the example below, we the large table named HORSE, where we have list of horses, and small tables with a few records: SEX, COLOR, BREED, FARM. The query selects all records from the large table.

We use COUNT(*) to read all records, and to exclude time to transfer records from the server to the client.

SELECT
  COUNT(*)
FROM
  HORSE
  JOIN SEX ON SEX.CODE_SEX = HORSE.CODE_SEX
  JOIN COLOR ON COLOR.CODE_COLOR = HORSE.CODE_COLOR
  JOIN BREED ON BREED.CODE_BREED = HORSE.CODE_BREED
  JOIN FARM ON FARM.CODE_FARM = HORSE.CODE_FARM

In Firebird 4.0:

Select Expression
    -> Aggregate
        -> Nested Loop Join (inner)
            -> Table "COLOR" Full Scan
            -> Filter
                -> Table "HORSE" Access By ID
                    -> Bitmap
                        -> Index "FK_HORSE_COLOR" Range Scan (full match)
            -> Filter
                -> Table "SEX" Access By ID
                    -> Bitmap
                        -> Index "PK_SEX" Unique Scan
            -> Filter
                -> Table "BREED" Access By ID
                    -> Bitmap
                        -> Index "PK_BREED" Unique Scan
            -> Filter
                -> Table "FARM" Access By ID
                    -> Bitmap
                        -> Index "PK_FARM" Unique Scan

                COUNT
=====================
               519623

Current memory = 2614108752
Delta memory = 438016
Max memory = 2614392048
Elapsed time = 2.642 sec
Buffers = 153600
Reads = 0
Writes = 0
Fetches = 5857109
Per table statistics:
--------------------------------+---------+---------+---------+---------+---------+
 Table name                     | Natural | Index   | Insert  | Update  | Delete  |
--------------------------------+---------+---------+---------+---------+---------+
BREED                           |         |   519623|         |         |         |
COLOR                           |      239|         |         |         |         |
FARM                            |         |   519623|         |         |         |
HORSE                           |         |   519623|         |         |         |
SEX                             |         |   519623|         |         |         |
--------------------------------+---------+---------+---------+---------+---------+

And in Firebird 5.0. The optimizer of v5 uses cardinality of table to decide when to use HASH JOIN.

Select Expression
    -> Aggregate
        -> Filter
            -> Hash Join (inner)
                -> Hash Join (inner)
                    -> Hash Join (inner)
                        -> Nested Loop Join (inner)
                            -> Table "COLOR" Full Scan
                            -> Filter
                                -> Table "HORSE" Access By ID
                                    -> Bitmap
                                        -> Index "FK_HORSE_COLOR" Range Scan (full match)
                        -> Record Buffer (record length: 25)
                            -> Table "SEX" Full Scan
                    -> Record Buffer (record length: 25)
                        -> Table "BREED" Full Scan
                -> Record Buffer (record length: 33)
                    -> Table "FARM" Full Scan

                COUNT
=====================
               519623

Current memory = 2579749376
Delta memory = 352
Max memory = 2582802608
Elapsed time = 0.702 sec
Buffers = 153600
Reads = 0
Writes = 0
Fetches = 645256
Per table statistics:
--------------------------------+---------+---------+---------+---------+---------+
 Table name                     | Natural | Index   | Insert  | Update  | Delete  |
--------------------------------+---------+---------+---------+---------+---------+
BREED                           |      282|         |         |         |         |
COLOR                           |      239|         |         |         |         |
FARM                            |    36805|         |         |         |         |
HORSE                           |         |   519623|         |         |         |
SEX                             |        4|         |         |         |         |
--------------------------------+---------+---------+---------+---------+---------+

As you can see, HASH JOIN in this situation is 3.5 times faster!

1.2. Cost estimation of HASH vs MERGE JOIN

In Firebird 3.0 the algorithm MERGE JOIN was temporary disabled in favor of HASH JOIN. Usually it was used when NESTED LOOP JOIN was non-optimal (when there were no indices for join condition, or when joining datasets were not related).

And, in the majority of situations, HASH JOIN is more effective than MERGE JOIN, due to the fact that it does not require to sort joining datasets with keys before the merge, however, there are a few cases when MERGE JOIN is better than HASH JOIN:

Merged datasets are already sorted with the join key, for example, merge of 2 subselects with keys specfied in GROUP BY:
```
select count(*)
from
(
    select code_father+0 as code_father, count(*) as cnt
    from horse group by 1
) h
join (
    select code_father+0 as code_father, count(*) as cnt
    from cover group by 1
) c on h.code_father = c.code_father
```
In this example, merged datasets are already sorted by the key code_father, and we don’t need to sort them again, in this case MERGE JOIN will be the most effective.

Unfortunately, Firebird 5.0 cannot recognize this situation, hopefully it will appear in the next version.
Merged datasets are very large. In this case hash-table will become very large and will not fit into memory. The optimizer of Firebird v5 checks cardinalities of merged datasest (tables, for exemple), and if the smallest is more than 1009000 records, v5 will choose MERGE JOIN instead of HASH JOIN. In the explain plan we will see it in the following manner:

SELECT
  *
FROM
  BIG_1
  JOIN BIG_2 ON BIG_2.F_2 = BIG_1.F_1
Select Expression
    -> Filter
        -> Merge Join (inner)
            -> Sort (record length: 44, key length: 12)
                -> Table "BIG_2" Full Scan
            -> Sort (record length: 44, key length: 12)
                -> Table "BIG_1" Full Scan