Data access methods used in Firebird

This method is also known as Full Scan, Natural Scan, Sequential Scan.

In this access method, the server performs a sequential reading of all pages allocated for a given table, in the order of their physical location on the disk. Obviously, this method provides the highest performance in terms of throughput, i.e. the number of records fetched per unit of time. It is also quite obvious that all records of a given table will be read, regardless of whether we need them or not.

Since the expected data volume is quite large, there is a problem of the read pages displacing other pages that are potentially needed by competing sessions during the process of reading the table pages from disk. For this purpose, the logic of the page cache operation changes — the current scan page is located in the MRU (most recently used) position during the reading of all records from this page. As soon as there is no more data on the page and the next one needs to be fetched, the current page is released with the LRU (least recently used) flag, going to the "tail" of the queue and thus being the first candidate for removal from the cache.

The records are read from the table one by one, immediately issued to the output. It should be noted that there is no pre-fetch of records (at least within the page) with their buffering in the server. That is, a full selection from a table with 100K records occupying 1000 pages will lead to 100K page fetches, and not to 1000, as one might expect. There is also no batch reading (multi-block reads), in which adjacent pages could be allocated into groups and read from the disk "in batches" of several pieces, thereby reducing the number of physical I/O operations.

The optimizer uses a rule-based strategy when choosing this access method — a full scan is performed only if there are no indexes applicable to the query predicate. The cost of this access method is equal to the number of records in the table (estimated approximately by the number of table pages, the record size, and the average compression ratio of records on data pages). Theoretically, this is incorrect and the choice of access method should always be based on cost, but in practice this turns out to be unnecessary in the vast majority of cases. The reasons for this will be explained below when describing index access.

Here and below, when mentioning the optimizer behavior, the following will be given: an example of a SELECT query, its execution plan in Legacy and Explain forms. In the Legacy execution plan, a full table scan is designated by the word “NATURAL”. In the Explain form — Table "<table name>" Full Scan. Currently, what is specified in square brackets (cardinality and cost) is not displayed in the explain plan, it is given as an example of calculating these values.

In the query execution statistics, records read by a full scan are reported as non indexed reads.

If you use table aliases, the plan will also show the aliases.

In this case, the execution engine obtains the identifier (physical number) of the record to be read. This record number can be obtained from various sources, each of which is described below.

In simplified terms, the physical record number contains information about the page on which the record is located and the offset within that page. This information is therefore sufficient to fetch the required page and find the desired record on it.

This access method is low-level and is used only as an implementation of bitmap-based fetching (both index scan and RDB$DB_KEY access) and index navigation. More details on these access methods will be given later.

The cost of this type of access is always equal to one. Reads of records are reflected in statistics as indexed.

Here we are talking about positioned statements UPDATE and DELETE (syntax WHERE CURRENT OF). There is a misconception that this access method is syntactically analogous to fetching via RDB$DB_KEY, but this is not true. Positioned data access works only for the active cursor, i.e. for the already fetched record (using FOR SELECT or FETCH statements). Otherwise, the error isc_no_cur_rec (“no current record for fetch operation”) will be thrown. Thus, this is simply a way to refer to the active record of the cursor, which does not require any read operations at all. Whereas fetching via RDB$DB_KEY involves access via the record identifier and, therefore, always results in fetching one page.

The main parameter that influences index access optimization is the index selectivity. This is the reciprocal of the number of unique key values. Cardinality and cost calculations assume a uniform distribution of key values ​​in the index.

The selectivity of an index can be found using the following query

For composite indexes, in addition to the index selectivity, Firebird also stores the selectivity of the set of its segments, starting from the first to the given one. The selectivity of the set of segments can be found using a query to the RDB$INDEX_SEGMENTS table.

The index selectivity is calculated when it is built (CREATE INDEX, ALTER INDEX …​ ACTIVE) and may become outdated later. To update the index statistics, use the following SQL query

Currently, Firebird does not update index statistics automatically. In addition, the stored statistics contain very little information for optimizing access using the index. In fact, only the selectivity of the index and its segments is stored. But such important index characteristics as NULL value selectivity, index depth, average index key length, histograms of value distribution, and clustering factor are not stored.

In addition to simple and composite indexes, Firebird allows you to create indexes by expression. In this case, instead of table field values, the index keys are the values of an expression that returns a scalar value. To use such indexes, the optimizer must use the same expression in the query filter condition as was specified when creating the index. Indexes by expression cannot be composite, but the expression can contain several table fields. The selectivity of such an index is calculated in the same way as for regular indexes.

Starting with Firebird 5.0, when creating an index, it is possible to specify an optional WHERE clause that defines a search condition that limits the subset of table records to be indexed. Such indexes are called partial indexes. The search condition must contain one or more table columns.

The optimizer can use a partial index only in the following cases:

I will demonstrate the last point with an example. Suppose you have created the following partial index:

Now the optimizer can use this index not only for the IS NOT NULL predicate, but also for the =, <, >, BETWEEN and other predicates, if they do not return TRUE when compared with NULL. For the IS NULL and IS NOT DISTINCT FROM predicates, the index cannot be used.

If a regular index and a partial index exist on the same set of fields, the optimizer will choose the regular index in most cases, even if the WHERE clause includes the same expression as defined in the partial index. The reason for this behavior is that the selectivity of a regular index is known "exactly" (calculated as the inverse of the number of unique keys). But fewer keys are included in a partial index due to the additional filtering condition, so the stored selectivity of the index will be worse. The calculated selectivity of a partial index is estimated as the stored selectivity multiplied by the proportion of records included in the index. This proportion is currently not stored in statistics ("exactly" is not known), but is estimated based on the selectivity of the filter expression specified when creating the index (see Predicate checking). However, the actual selectivity may be lower, and therefore a regular index (with an exactly calculated selectivity value) may win.

The main standard problem with index access is random I/O to data pages. Indeed, the order of keys in the index very rarely coincides with the order of the corresponding records in the table. Thus, selecting a significant number of records through the index will most likely lead to multiple fetching of each corresponding data page. This problem is solved in other DBMSs using clustered indexes (MSSQL term) or index-ordered tables (Oracle term), in which the data is located directly in the index in ascending order of the cluster key.

Firebird solves this problem in a different way. Index scanning is not a pipeline operation, but is performed for the entire search range, including the obtained record numbers in a special bitmap. This map is a sparse bit array, where each bit corresponds to a specific record, and the presence of one in it is an indication for selecting this record. The peculiarity of this solution is that the bitmap is sorted by record numbers by definition. After the scan is complete, this array serves as the basis for sequential access via the record identifier. The advantage is obvious - reading from the table is done in the physical order of the pages, as with a full scan, i.e. each page will be read no more than once. Thus, the simplicity of the index implementation is combined with the most efficient access to records. The price is a slight increase in response time for queries with the FIRST ROWS strategy, when you need to get the first records very quickly.

Bitmaps allow intersection (bit and) and union (bit or) operations, so the server can use multiple indexes on a single table.

The search under the index is performed using the upper and lower bounds. That is, if the lower scan bound is specified, the corresponding key is found first and only then the sequential search of keys begins with the entry numbers in the bitmap. If the upper bound is specified, each key is compared with it and when it is reached, the scan stops. This mechanism is called range scan. In the case where the lower bound key is equal to the upper bound key, we speak of an equality scan. If the equality scan is performed for a unique index, this is called a unique scan. This type of scan is of particular importance, since it can return no more than one entry and, therefore, is by definition the cheapest. If none of the bounds are specified, we are dealing with a full scan. This method is used exclusively for index navigation, described below.

When possible, the server skips NULL values ​​when scanning a range, if it is acceptable to do so. In most cases, this results in improved performance due to a smaller bitmap size and, therefore, fewer indexed reads. This option is not used only for indexed predicates such as IS NULL and IS NOT DISTINCT FROM, which are NULL aware.

When choosing indexes to scan, the optimizer uses a cost-based strategy. The cost of a range scan is estimated based on the index selectivity, the number of records in the table, the average number of keys per index page, and the height of the B+ tree.

In a Legacy execution plan, an index range scan is denoted by the word “INDEX” followed in parentheses by the names of all the indexes that make up the resulting bitmap.

In the Explain plan, the display of the range scan is somewhat more complex. In general, it looks like this:

Where index_name is the name of the index to use, scan_type is the scan type, table_name is the table name.

As mentioned above, bitmaps can be bit ANDed and bit ORed, so the server can use multiple indexes for a single table. Bitmap intersections do not increase the resulting cardinality. For example, for the expression F = 0 and ? = 0, the second part is not indexed and is therefore checked after the index fetching, without affecting the final result. But bitmap merging increases the resulting cardinality, so only parts of a fully indexed predicate can be merged. That is, when moving the second part of the expression F = 0 or ? = 0 to a higher level, it may turn out that all records had to be scanned. Therefore, the index for the F field will not be used in such an expression.

The selectivity of the intersection of two bitmaps is calculated using the formula:

The selectivity of combining two bitmaps is calculated using the formula:

Since the cost of access via a record identifier is one, the total cost of access via a bitmap is equal to the total cost of the index lookup (for all indexes that form the bitmap) plus the resulting cardinality of the bitmap.

Let’s look at examples using multiple indexes.

Index navigation is nothing more than sequential scanning of index keys. And since for each record the server needs to fetch the record and check its visibility for our transaction, this operation is quite expensive. That is why this access method is not used for regular selections (unlike Oracle, for example), but is used only in cases where it is justified.

There are two such cases today. The first is the calculation of aggregate functions MIN/MAX. Obviously, to calculate MIN it is enough to take the first key in the ASC index, and to calculate MAX — the first key in the DESC index. If after fetching a record it turns out that it is not visible to us, then we take the next key, and so on. The second is sorting or grouping records. This is indicated by the ORDER BY or GROUP BY clauses in the user’s query. In this situation, we simply go through the index, selecting records as we scan. In both cases, fetching records is performed based on access via its identifier.

There are several features that optimize this process. First, if there are restrictive predicates on the sort field, they create upper and/or lower scan bounds. That is, in the case of the query (WHERE A > 0 ORDER BY A), a partial index scan will be performed instead of a full one. This way, we reduce the cost of the scan itself. Second, if there are other restrictive predicates (not on the sort field), but optimized through the index, a complex mode of operation is enabled, where index scanning is combined with the use of a bitmap. Let’s consider how this works. Let us assume that we have a query of the form (WHERE A > 0 AND B > 0 ORDER BY A). In this case, first a range scan is performed for the index by field B and a bitmap is created. Then the value 0 is set as the lower bound of the index scan by field A. Then we scan this index starting from the lower bound and for each record number extracted from the index we check its inclusion in the bitmap. And only in case of entry we perform fetch of records. This way we reduce expenses on fetch of data pages.

The main difference between index navigation and scanning (described in Range Scan) is the absence of a bitmap between index scanning and record access via its identifier. The reason is clear — sorting records by physical numbers is contraindicated in this case. From this we can conclude that the index is scanned as it is fetched from the client, and not "all at once" (as in the case of using a bitmap).

The cost of navigation is quite difficult to estimate. To calculate MIN/MAX in the vast majority of cases it will be equal to the height of the B+ tree (search for the first key) plus one (page fetch). The cost of such access is considered to be a negligible value, since in practice the described calculation of MIN/MAX will always be faster than alternative options. To estimate the cost of index navigation, one must take into account both the number and average width of index keys and the cardinality of the bitmap (if any), and also have an idea of the clustering factor of the index — the coefficient of correspondence between the location of keys and physical numbers of records. At the moment, the server does not calculate the cost of navigation, i.e. the rule-based strategy is used again. In the future, it is planned to use this approach only for MIN/MAX and FIRST, and rely on the cost in other cases.

In the Legacy plan, index navigation is indicated by the word “ORDER” followed by the name of the index (without parentheses, since there can only be one such index). The server also reports the indices that form the bitmap used for filtering. In this case, both words are present in the execution plan: first “ORDER”, then “INDEX”.

A predicate is invariant if its value does not depend on the fields of the filtered streams. The simplest example of invariant predicates are conditions like 1=0 and 1=1. Invariant predicates can also contain parameter markers, for example ? = 1.

Starting with Firebird 5.0, invariant and at the same time deterministic predicates are recognized by the optimizer and are evaluated once. Unlike regular filtering predicates, invariant predicates are evaluated as early as possible, their check is always placed as “higher” in the query execution tree as possible. If an invariant filtering predicate evaluates to FALSE, then retrieval of records from the underlying data sources is immediately stopped.

Unlike regular filtering predicates, filtering with an invariant predicate does not change the cardinality of the output stream.

In the Legacy plan, checking of invariant predicates is not displayed. In the Explain plan, the check for invariant predicates is displayed using the word “Filter (preliminary)”, but the predicate itself is not displayed.

Starting with Firebird 4.0, there is a sorting optimization for wide data sets, which is displayed in the Explain plan as Refetch. A ``wide data set’ is a data set in which the total length of the record fields is large.

When performing an external sort, Firebird writes both key fields (those specified in the ORDER BY or GROUP BY clause) and non-key fields (all other fields referenced within the query) to sort blocks, which are either stored in memory or in temporary files. After the sort is complete, these fields are read back from the sort blocks. This approach is generally considered faster because records are read from the temporary files in the order corresponding to the sorted records, rather than being selected randomly from the data page. However, if the non-key fields are large (e.g., using long VARCHARs), this increases the size of the sort blocks and thus results in more I/O to the temporary files.

An alternative approach (Refetch) is that only key fields and DBKEY of records of all participating tables are stored inside sort blocks, and non-key fields are extracted from data pages after sorting. This improves sort performance in case of long non-key fields. It is clear from the description of Refetch that it can be used only in case of normal sort mode, Refetch is not applicable for truncated mode, since DBKEY does not get into sort blocks in this mode.

For external sorting using Refetch, the cost is not calculated. The optimizer uses the InlineSortThreshold parameter to select the method by which the data will be sorted. The value specified for InlineSortThreshold determines the maximum size of a sort record (in bytes) that can be stored inline, i.e. inside the sort block. Zero means that records are always re-fetched (Refetch). The optimal value for this parameter should be selected experimentally. The default value is 1000 bytes.

In the Legacy execution plan, Refetch and external sorting are displayed the same way, as SORT.

In the Explain execution plan, sorting using Refetch is displayed as a tree, where the root is “Refetch”, at the bottom level is “Sort” . Then in brackets are the length of the keys to be sorted + DBKEY of the tables used (record length) and the length of the sort key (key length).

From the Explain plan it is clear that first sorting by sort keys occurs, the keys themselves + DBKEY of the table get into the sort blocks, and then full records are extracted from the table in sorted order by DBKEY using the Refetch method.

Now let’s try to use Refetch for truncating sort mode.

Here, although wide records need to be sorted, Refetch cannot be used, and so the usual external sorting is used.

Predicates in the HAVING clause may contain aggregate functions or fields and grouping expressions. If the predicate is applied to an aggregate function, filtering occurs after grouping and aggregate calculation. If the predicate is applied to fields and grouping expressions, the predicate is pushed inward so that it is evaluated before grouping and aggregation.

In the last example, the filtering predicate was "pushed down", but after the aggregates were calculated, the filtering was applied again. Note that the re-filtering performed cardinality normalization (in theory, aggregate functions with or without grouping can never return less than one record).

This method is the most common in Firebird. In other DBMSs, this algorithm is also called nested loops join.

Its essence is simple. One of the input streams (outer) is opened and one record is read from it. After that, the second stream (inner) is opened and one record is also read from it. Then the join condition is checked. If the condition is met, these two records are merged into one and output. Then the second record is read from the inner stream and the process is repeated until EOF is output from it. If the inner stream does not contain any records corresponding to the outer stream, then two scenarios are possible. In the case of an inner join, the record is not returned to the output. In the case of an outer join, we join the record from the outer stream with the required number of NULL values and output it. Next, regardless of the type of join, we read the second record from the outer stream and begin the iteration process over the inner stream again. It is obvious that this algorithm works on a pipeline principle and the join of streams is performed directly in the process of the client fetch.

The key feature of this join method is the "nested" selection from the inner stream. It is obvious that reading the entire inner stream for each record of the outer stream is very expensive. Therefore, nested loop join works efficiently only if there is an index applicable to the join condition. In this case, at each iteration, a subset of records that satisfy the current record of the outer stream will be selected from the inner stream. It is worth noting that not every index is suitable for efficient execution of this algorithm, but only the one that corresponds to the join condition. For example, with a join of the form (ON SLAVE.F = 0), even if an index is used on the F field of the inner table, the same records will still be read from it at each iteration, which is a waste of resources. In this situation, a MERGE/HASH join would be more efficient (see below).

We can introduce the definition of "stream dependency" as the presence of fields of both streams in the join condition and conclude that joining with nested loops is effective only when streams depend on each other.

If we recall the description of "Predicate checking", where the principle of maximally “deep” placement of predicative filters by the optimizer is described, then one point becomes clear: individual table filters will push “down” the join methods. Accordingly, in the case of a predicate of the type (WHERE MASTER.F = 0) and the absence of records in the MASTER table with the F field equal to zero, there will be no calls to the inner join stream at all, since in this case there is no iteration over the outer stream (there are no records in it).

Since the logical AND and OR connections are optimized via bitmaps, the nested loop join can be used for all kinds of join conditions, and is usually quite efficient.

For outer joins, the nested loop join is always selected because there are currently no alternatives. For inner joins, the optimizer selects the nested loop join if its cost is cheaper than the alternatives (Hash Join). If there are no suitable indices for the link fields of inner joins, then alternative join algorithms are almost always selected if they are possible. In addition, for inner joins, the optimizer selects the most efficient order of streams. The main selection criteria are the cardinalities of both streams and the selectivity of the link condition. The following formulas are used to estimate the cost of a certain join order:

The last part of the formula defines the cost of selection from the inner stream at each iteration. Multiplying it by the number of iterations yields the total cost of selection from the inner stream. The total cost is obtained by adding the cost of selection from the outer stream. Of all possible permutations, the one with the lowest cost is selected. In the process of enumerating the options, the obviously worst ones are discarded (based on the already available cost information). Permutations involve not only streams joined by nested loops, but also other join algorithms (Hash Join), the cost of which is calculated according to other rules.

In the Legacy execution plan, nested loops are joined by the word "JOIN", followed by parentheses and commas that describe the input streams.

In the Explain execution plan, nested loops are displayed as a tree, the root of which is labeled “Nested Loop Join” followed by the type of join in parentheses. The streams being joined are described at the level below.

Hash join is an alternative algorithm for performing a join. Joining streams using the HASH JOIN algorithm has been available since Firebird 3.0.

When joining by the hashing method, the input streams are always divided into a master and a slave, and the slave is usually the stream with the lowest cardinality. First, the smaller (slave) stream is read entirely into an internal buffer. During reading, a hash function is applied to each link key and the pair {hash, pointer in buffer} is written to the hash table. Then the master stream is read and its link key is tried in the hash table. If a match is found, the records of both streams are joined and output. In the case of several duplicates of a given key in the slave table, several records will be output. If the key does not appear in the hash table, we move on to the next record of the master stream, and so on.

Obviously, replacing key comparison with hash comparison is possible only when comparing for strict equality of keys. Thus, a join with a connection condition of the form (ON MASTER.F > SLAVE.F) cannot be performed by the Hash Join algorithm.

However, this method has one advantage over nested loop joins — it allows expression-based hash joins. For example, a join with a link condition like (ON MASTER.F + 1 = SLAVE.F + 2) is easily implemented using hash joins. The reason is obvious: there is no dependency between streams and, therefore, no requirement to use indexes.

Collisions may occur during the construction of a hash table. A collision is a situation where the same hash function value is obtained for different key values. Therefore, after the hash function value matches, the connection predicate is always recalculated. Collisions are saved as a list sorted by keys, which makes it possible to perform a binary search along the collision chain.

In the current implementation, the hash table has a fixed size of 1009 slots, it does not change depending on the cardinality of the hashed stream. Also, the hash table size does not increase and rehashing does not occur when the length of collision chains is exceeded. This means that hashing join is effective only with a relatively small cardinality of the slave stream. If the cardinality of the hashed stream exceeds 1009000 records, then other join algorithms are selected (in the presence of indexes, NESTED LOOP JOIN; in the absence, MERGE JOIN).

The hash join algorithm can handle multiple AND join conditions. In this case, the hash function is calculated for multiple fields included in the join condition (or multiple links if more than one stream is joined). However, in the case of OR join conditions, the hash join method cannot be applied. It should be noted here that the hash function is not always calculated for all fields included in the join condition, it can be calculated only for some of them. This happens if the number of link keys exceeds 8. In this case, if the hash function value matches, more records than necessary will be returned from the hash table. The extra records will be filtered out after all predicates in the join condition have been calculated. In this case, the efficiency of hash join decreases. The Explain plan does not display the number of keys involved in the hash function (this information was added in Firebird 6.0).

Another feature of hash join is that it can be performed when comparing keys for strict equality taking into account NULL values. That is, both = and IS NOT DISTINCT FROM are allowed. At the same time, no difference is made between these predicates when constructing a hash table, although it is obvious that if the = predicate is used, then records with the NULL key can be omitted from the hash table. This leads to increased memory consumption and decreased performance of hash join if there are many keys with the NULL value. This drawback is planned to be fixed in future versions of Firebird (see CORE-7769).

Before Firebird 5.0, the HASH JOIN join method was used only when there were no indexes by the join condition or they were not applicable, otherwise the optimizer chose the NESTED LOOP join algorithm using indexes. In fact, this is not always optimal. If a large stream joins a small table by the primary key, then each record of such a table will be read many times, and the index pages, if used, will also be read many times. When using a HASH JOIN join, the smaller table will be read exactly once. Naturally, the cost of hashing and probing is not free, so the choice of which algorithm to use is based on cost.

The cost of joining using the HASH JOIN method consists of the following parts:

The following formulas are used to estimate cardinality and cost (see InnerJoin.cpp):

Where

В Legacy плане выполнения соединение хешированием отображается словом "HASH", за которым в скобках через запятую описываются входные потоки.

In the Explain of the execution plan, the hash join is shown as a tree with the root labeled “Hash Join” followed by the join type in parentheses. The joinable streams are described at the level below. The slave table hash is shown as “Record Buffer” followed by the record length in parentheses as (record length: <length>) (see Record Buffer).

Merge is an alternative algorithm for implementing a join. In this case, the input streams are completely independent. For the operation to be performed correctly, the streams must be pre-ordered by the join key, after which a binary merge tree is built. Then, during fetch, records are read from both streams and their link keys are compared for equality. If the keys match, the record is returned to the output. Then new records are read from the input streams and the process is repeated. Merge is always performed in one pass, i.e. each input stream is read only once. This is possible due to the ordered arrangement of the link keys in the input streams.

However, this algorithm cannot be used for all types of joins. As noted above, a strict equality comparison of keys is required. Thus, a join with a join condition of the form (ON MASTER.F > SLAVE.F) cannot be performed using a one-pass merge. To be fair, it should be noted that joins of this type cannot be efficiently performed in any way, since even in the case of using the nested loop join algorithm, there will be repeated reads from the internal stream at each iteration.

However, this method has one advantage over the nested loop join algorithm — it allows expression-based merging. For example, a join with a link condition like (ON MASTER.F + 1 = SLAVE.F + 2) is easily performed by the merge method. The reason is clear: there is no dependency between threads and, therefore, no requirement to use indexes.

An attentive reader might have noticed that the description of the merge algorithm does not specify the mode of operation of the method in the case of flow dependencies (one-way outer join). The answer is simple: this algorithm is not supported for such joins. In addition, it is also not supported for full outer joins, semi-joins, and anti-joins.

This algorithm can handle multiple link conditions combined via AND. In this case, the input streams are simply sorted by several fields. However, in the case of combining link conditions via OR, the merge method cannot be applied.

The main disadvantage of this algorithm is the requirement to sort both streams by join keys. If the streams are already sorted, then this join algorithm is the cheapest among others (NESTED LOOP, HASH JOIN). However, usually the streams to be joined are not sorted by join keys, and therefore they have to be sorted, which dramatically increases the cost of performing the join by this method. Unfortunately, at the moment the optimizer cannot determine that the streams are already sorted by join keys, and therefore this algorithm may not be used in cases where it would really be cheaper.

Before Firebird 3.0, merge joins were used only when the nested loop join algorithm was impossible or suboptimal, i.e. primarily when there were no indexes by the link condition or they were not applicable, and when there was no dependency between the input streams. Starting with Firebird 3.0, the merge join algorithm was disabled, and hash join was always used instead. Starting with Firebird 5.0, merge join became available again. It is used only when the streams being joined are too large and hash join becomes ineffective (the cardinality of all streams being joined is greater than 1009000 records, see Hash join), and also when there are no indexes by the link condition, which makes the nested loop join algorithm suboptimal.

The following formulas are used to estimate the cost and cardinality of a join:

Where cost_1, cost_2 is the cost of extracting data from sorted input streams. And since the cost of external sorting is not calculated, the cost of merge join cannot be estimated correctly.

In a Legacy execution plan, a merge join is represented by the word "MERGE" followed by parentheses and a comma-separated list of input streams.

In the Explain execution plan, the merge join is displayed as a tree, the root of which is labeled “Merge Join” followed by the join type in parentheses. The level below describes the streams being joined, which are sorted by the outer sort.

Table expressions in Firebird have one nasty feature, namely when accessing table expression columns that reference expressions, these expressions are evaluated each time the table expression column is mentioned. This is easily demonstrated when using non-deterministic functions.

Try running the following query:

The result will be something like

Although you expected the values ​​in the columns to be the same.

This also occurs when sorting by column reference. For example:

The sequence will increase not by 1, as you expected, but by 2.

There is one trick that allows you to “materialize” the results of expression calculations in table expressions. To do this, it is enough to make a UNION with a query returning 0 records, naturally the total number of columns of both queries must be the same. Let’s try to rewrite the first query as follows:

Now the values ​​of ID1 and ID2 will be the same.

What happens if a subquery is used as a column in a table expression? A subquery can be quite heavy to execute repeatedly. Fortunately, in this case, the optimizer does all the work for us. Try executing the following query:

Despite the repeated mention of T.CNT, the subquery will be executed once for each record in RDB$RELATIONS.

In the Explain plan you will see the following:

Here “Materialize” means materialization of the subquery results for each record from RDB$RELATIONS. This is not a separate access method, but an inner union (UNION) inside a table expression with an empty set. That is, the same thing happened as described above about the materialization of non-deterministic expressions.