[MDEV-26090] where CONCAT(column) = 'xxx' is much faster than without concat condition Created: 2021-07-04  Updated: 2023-11-28

Status: Stalled
Project: MariaDB Server
Component/s: Optimizer
Affects Version/s: 10.5.9, 10.2, 10.3, 10.4, 10.5
Fix Version/s: 10.11

Type: Bug Priority: Minor
Reporter: Allen Lee (Inactive) Assignee: Sergei Petrunia
Resolution: Unresolved Votes: 2
Labels: optimizer

Attachments: Zip Archive dump.zip    

 Description   

Customer shared the interesting test result and was wondering why where CONCAT(col) is faster without CONCAT. I've attached test schema and data.

  • this is the initial table schema and query.

CREATE TABLE F (
 
id INTEGER NOT NULL,
 
dept CHAR(4),
 
dest CHAR(4),
 
t TIMESTAMP NOT NULL,
 
 
 
PRIMARY KEY (id),
 
KEY t (t)
 
);
 
 
 
CREATE TABLE M (
 
station CHAR(4) NOT NULL,
 
t_start DATETIME NOT NULL,
 
t_end DATETIME DEFAULT NULL,
 
windspeed INTEGER unsigned DEFAULT NULL,
 
winddir INTEGER unsigned DEFAULT NULL,
 
PRIMARY KEY (station,t_start)
 
);


SELECT SQL_NO_CACHE F.id, F.t, M.t_start, M.t_end, M.winddir 
FROM F JOIN M ON (M.t_start BETWEEN F.t - INTERVAL 1 HOUR AND F.t AND M.t_end >= F.t)
 
WHERE F.t BETWEEN '2021-01-01' AND '2021-01-03' 
AND M.station = 'LFBO';


+------+-------------+-------+-------+---------------+---------+---------+-------+-------+--------------------------+
 
| id   | select_type | table | type  | possible_keys | key     | key_len | ref   | rows  | Extra                    |
 
+------+-------------+-------+-------+---------------+---------+---------+-------+-------+--------------------------+
 
|    1 | SIMPLE      | F     | range | t             | t       | 4       | NULL  | 266   | Using where; Using index |
 
|    1 | SIMPLE      | M     | ref   | PRIMARY       | PRIMARY | 12      | const | 42462 | Using where              |
 
+------+-------------+-------+-------+---------------+---------+---------+-------+-------+--------------------------+

  • analyze output 

    | {
    		 
      "query_block": {
    		 
        "select_id": 1,
    		 
        "r_loops": 1,
    		 
        "r_total_time_ms": 40612.55196,
    		 
        "table": {
    		 
          "table_name": "F",
    		 
          "access_type": "range",
    		 
          "possible_keys": ["t"],
    		 
          "key": "t",
    		 
          "key_length": "4",
    		 
          "used_key_parts": ["t"],
    		 
          "r_loops": 1,
    		 
          "rows": 266,
    		 
          "r_rows": 266,
    		 
          "r_table_time_ms": 1.012544094,
    		 
          "r_other_time_ms": 1.524286562,
    		 
          "filtered": 100,
    		 
          "r_filtered": 100,
    		 
          "attached_condition": "f.t between '2021-01-01 00:00:00.000000' and '2021-01-03 00:00:00.000000'",
    		 
          "using_index": true
    		 
        },
    		 
        "table": {
    		 
          "table_name": "M",
    		 
          "access_type": "ref",
    		 
          "possible_keys": ["PRIMARY"],
    		 
          "key": "PRIMARY",
    		 
          "key_length": "12",
    		 
          "used_key_parts": ["station"],
    		 
          "ref": ["const"],
    		 
          "r_loops": 266,
    		 
          "rows": 42462,
    		 
          "r_rows": 21285,
    		 
          "r_table_time_ms": 18581.56254,
    		 
          "r_other_time_ms": 22028.44358,
    		 
          "filtered": 100,
    		 
          "r_filtered": 0.004698144,
    		 
          "attached_condition": "m.station = 'LFBO' and m.t_start between f.t - interval 1 hour and f.t and m.t_end >= f.t"
    		 
        }
    		 
      }
    		 
    } |

With initial query and index, it was extremely slow. So, I proposed change index of `m` table to use primary key

MariaDB [raymond]> alter table m drop primary key, add primary key(t_start, station);
 
Query OK, 0 rows affected (0.415 sec)               
Records: 0  Duplicates: 0  Warnings: 0


+------+-------------+-------+-------+---------------+------+---------+------+--------+-------------------------------------------------+
 
| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows   | Extra                                           |
 
+------+-------------+-------+-------+---------------+------+---------+------+--------+-------------------------------------------------+
 
|    1 | SIMPLE      | F     | range | t             | t    | 4       | NULL | 266    | Using where; Using index                        |
 
|    1 | SIMPLE      | M     | ALL   | PRIMARY       | NULL | NULL    | NULL | 249541 | Using where; Using join buffer (flat, BNL join) |
 
+------+-------------+-------+-------+---------------+------+---------+------+--------+-------------------------------------------------+

  • analyze output

  • | {
    		 
      "query_block": {
    		 
        "select_id": 1,
    		 
        "r_loops": 1,
    		 
        "r_total_time_ms": 4726.954647,
    		 
        "table": {
    		 
          "table_name": "F",
    		 
          "access_type": "range",
    		 
          "possible_keys": ["t"],
    		 
          "key": "t",
    		 
          "key_length": "4",
    		 
          "used_key_parts": ["t"],
    		 
          "r_loops": 1,
    		 
          "rows": 266,
    		 
          "r_rows": 266,
    		 
          "r_table_time_ms": 0.802683315,
    		 
          "r_other_time_ms": 0.913815331,
    		 
          "filtered": 100,
    		 
          "r_filtered": 100,
    		 
          "attached_condition": "f.t between '2021-01-01 00:00:00.000000' and '2021-01-03 00:00:00.000000'",
    		 
          "using_index": true
    		 
        },
    		 
        "block-nl-join": {
    		 
          "table": {
    		 
            "table_name": "M",
    		 
            "access_type": "ALL",
    		 
            "possible_keys": ["PRIMARY"],
    		 
            "r_loops": 1,
    		 
            "rows": 249541,
    		 
            "r_rows": 250119,
    		 
            "r_table_time_ms": 753.0043604,
    		 
            "r_other_time_ms": 3972.225239,
    		 
            "filtered": 100,
    		 
            "r_filtered": 8.509949264,
    		 
            "attached_condition": "m.station = 'LFBO'"
    		 
          },
    		 
          "buffer_type": "flat",
    		 
          "buffer_size": "2Kb",
    		 
          "join_type": "BNL",
    		 
          "attached_condition": "m.t_start between f.t - interval 1 hour and f.t and m.t_end >= f.t",
    		 
          "r_filtered": 0.004698144
    		 
        }
    		 
      }
    		 
    } |

Then, it got much faster compared to 1st one. However, customer noted that query got even faster with concat on where clause.

+------+-------------+-------+-------+---------------+------+---------+------+--------+------------------------------------------------+
 
| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows   | Extra                                          |
 
+------+-------------+-------+-------+---------------+------+---------+------+--------+------------------------------------------------+
 
|    1 | SIMPLE      | F     | range | t             | t    | 4       | NULL | 266    | Using where; Using index                       |
 
|    1 | SIMPLE      | M     | ALL   | PRIMARY       | NULL | NULL    | NULL | 249541 | Range checked for each record (index map: 0x1) |
 
+------+-------------+-------+-------+---------------+------+---------+------+--------+------------------------------------------------+

  • analyze output 

    | {
    		 
      "query_block": {
    		 
        "select_id": 1,
    		 
        "r_loops": 1,
    		 
        "r_total_time_ms": 67.0752722,
    		 
        "table": {
    		 
          "table_name": "F",
    		 
          "access_type": "range",
    		 
          "possible_keys": ["t"],
    		 
          "key": "t",
    		 
          "key_length": "4",
    		 
          "used_key_parts": ["t"],
    		 
          "r_loops": 1,
    		 
          "rows": 266,
    		 
          "r_rows": 266,
    		 
          "r_table_time_ms": 0.802407781,
    		 
          "r_other_time_ms": 2.921898929,
    		 
          "filtered": 100,
    		 
          "r_filtered": 100,
    		 
          "attached_condition": "f.t between '2021-01-01 00:00:00.000000' and '2021-01-03 00:00:00.000000'",
    		 
          "using_index": true
    		 
        },
    		 
        "range-checked-for-each-record": {
    		 
          "keys": ["PRIMARY"],
    		 
          "r_keys": {
    		 
            "full_scan": 0,
    		 
            "index_merge": 0,
    		 
            "range": {
    		 
              "PRIMARY": 266
    		 
            }
    		 
          },
    		 
          "table": {
    		 
            "table_name": "M",
    		 
            "access_type": "ALL",
    		 
            "possible_keys": ["PRIMARY"],
    		 
            "r_loops": 266,
    		 
            "rows": 249541,
    		 
            "r_rows": 37.36842105,
    		 
            "r_table_time_ms": 31.15710876,
    		 
            "r_other_time_ms": 32.18475629,
    		 
            "filtered": 100,
    		 
            "r_filtered": 2.676056338
    		 
          }
    		 
        }
    		 
      }
    		 
    } |

what would be the logical explanation on this dramatic query performance improvement?

 Comments   
Comment by Sergei Petrunia [ 2021-08-10 ]

Examining the dataset and the query:

The table F has 100K rows. It has a restriction

  F.t BETWEEN '2021-01-01' AND '2021-01-03'

which has a good index and it matches ~250 rows.

The table M has 250K rows. It has a restriction:

  M.station = 'LFBO'

which has a suitable index and it matches 21K rows.

The join condition is a non-equality one:

M.t_start BETWEEN F.t - INTERVAL 1 HOUR AND F.t AND 
M.t_end >= F.t

which prevents use of ref access.

There is an index on M.t_start. This looks suitable for construction of Range-Checked-for-each-record plans.

Comment by Sergei Petrunia [ 2021-08-10 ]

The first query plan:

+------+-------------+-------+-------+-----------------+---------+---------+-------+-------+--------------------------+
 
| id   | select_type | table | type  | possible_keys   | key     | key_len | ref   | rows  | Extra                    |
 
+------+-------------+-------+-------+-----------------+---------+---------+-------+-------+--------------------------+
 
|    1 | SIMPLE      | F     | range | t               | t       | 4       | NULL  | 254   | Using where; Using index |
 
|    1 | SIMPLE      | M     | ref   | PRIMARY,t_start | PRIMARY | 12      | const | 42534 | Using where              |
 
+------+-------------+-------+-------+-----------------+---------+---------+-------+-------+--------------------------+

Just takes the best ways to read the tables individually and then computes a cross-join between the result using a nested-loops join algorithm. Takes 27 sec for me.

An interesting thing to observe: use of ref access prevents use of Join buffering (Enabling MRR and setting join_cache_level=6 will not cause BKA to be used).

One can force join buffering to be used by changing ref into "range" . In order to do this, I replace M.station = 'LFBO' with (M.station='NO-STATION' or M.station = 'LFBO').

+------+-------------+-------+-------+-----------------+---------+---------+------+-------+-------------------------------------------------+
 
| id   | select_type | table | type  | possible_keys   | key     | key_len | ref  | rows  | Extra                                           |
 
+------+-------------+-------+-------+-----------------+---------+---------+------+-------+-------------------------------------------------+
 
|    1 | SIMPLE      | F     | range | t               | t       | 4       | NULL | 254   | Using where; Using index                        |
 
|    1 | SIMPLE      | M     | range | PRIMARY,t_start | PRIMARY | 12      | NULL | 42535 | Using where; Using join buffer (flat, BNL join) |
 
+------+-------------+-------+-------+-----------------+---------+---------+------+-------+-------------------------------------------------+

7.3 seconds.

Comment by Sergei Petrunia [ 2021-08-10 ]

The second query plan:

 alter table M drop primary key, add primary key(t_start, station);


+------+-------------+-------+-------+-----------------+------+---------+------+--------+-------------------------------------------------+
 
| id   | select_type | table | type  | possible_keys   | key  | key_len | ref  | rows   | Extra                                           |
 
+------+-------------+-------+-------+-----------------+------+---------+------+--------+-------------------------------------------------+
 
|    1 | SIMPLE      | F     | range | t               | t    | 4       | NULL | 254    | Using where; Using index                        |
 
|    1 | SIMPLE      | M     | ALL   | PRIMARY,t_start | NULL | NULL    | NULL | 249541 | Using where; Using join buffer (flat, BNL join) |
 
+------+-------------+-------+-------+-----------------+------+---------+------+--------+-------------------------------------------------+

This basically achieves a similar thing to what I have achieved with adding "M.station='NO-STATION'": it enables the use of join buffering.

Takes 6.2 seconds for me

Comment by Sergei Petrunia [ 2021-08-10 ]

The 3rd query plan:

replace M.station='LFBO' with CONCAT(M.station)='LFBO' and we get:

+------+-------------+-------+-------+-----------------+------+---------+------+--------+------------------------------------------------+
 
| id   | select_type | table | type  | possible_keys   | key  | key_len | ref  | rows   | Extra                                          |
 
+------+-------------+-------+-------+-----------------+------+---------+------+--------+------------------------------------------------+
 
|    1 | SIMPLE      | F     | range | t               | t    | 4       | NULL | 254    | Using where; Using index                       |
 
|    1 | SIMPLE      | M     | ALL   | PRIMARY,t_start | NULL | NULL    | NULL | 249541 | Range checked for each record (index map: 0x3) |
 
+------+-------------+-------+-------+-----------------+------+---------+------+--------+------------------------------------------------+

The idea is: the optimizer does NOT recognize concat(M.station)='LFBO' as a possible usable expression.
Without that, the only option to read table M is to do a full table scan.
When that is the case, the optimizer starts to consider "last resort" family of query plans: Range-Checked-for-each-record (lets call it RC-FER).

As explain shows, the optimizer constructs RC-FER query plan.
Running ANALYZE:

{
 
  "query_block": {
 
    "select_id": 1,
 
    "r_loops": 1,
 
    "r_total_time_ms": 82.1091927,
 
    "table": {
 
      "table_name": "F",
 
      "access_type": "range",
 
      "possible_keys": ["t"],
 
      "key": "t",
 
      "key_length": "4",
 
      "used_key_parts": ["t"],
 
      "r_loops": 1,
 
      "rows": 254,
 
      "r_rows": 254,
 
      "r_table_time_ms": 0.827620911,
 
      "r_other_time_ms": 29.79661383,
 
      "filtered": 100,
 
      "r_filtered": 100,
 
      "attached_condition": "F.t between '2021-01-01 00:00:00.000000' and '2021-01-03 00:00:00.000000'",
 
      "using_index": true
 
    },
 
    "range-checked-for-each-record": {
 
      "keys": ["PRIMARY", "t_start"],
 
      "r_keys": {
 
        "full_scan": 0,
 
        "index_merge": 0,
 
        "range": {
 
          "PRIMARY": 254,
 
          "t_start": 0
 
        }
 
      },
 
      "table": {
 
        "table_name": "M",
 
        "access_type": "ALL",
 
        "possible_keys": ["PRIMARY", "t_start"],
 
        "r_loops": 254,
 
        "rows": 249541,
 
        "r_rows": 37.93700787,
 
        "r_table_time_ms": 42.4408665,
 
        "r_other_time_ms": 9.013576013,
 
        "filtered": 100,
 
        "r_filtered": 2.635948526
 
      }
 
    }
 
  }
 
}

The query took 82 milliseconds.

The execution is basically: 

for each row in index F.t such that (BETWEEN '2021-01-01' AND '2021-01-03')  {
 
    Take expression 
     (M.t_start BETWEEN F.t - INTERVAL 1 HOUR AND F.t AND M.t_end >= F.t)
 
      put the values from table F in place, so it becomes
 
       (M.t_start BETWEEN $VALUE1 HOUR AND $VALUE2 AND M.t_end >= $VALUE2)
 
      check if this allows to use a range access to read table M
 
      read rows from table M and join with current row of F
 
   }

and ANALYZE output shows the index "PRIMARY" was good for use every single time:

      "r_keys": {
 
        "full_scan": 0,
 
        "index_merge": 0,
 
        "range": {
 
          "PRIMARY": 254,
 
          "t_start": 0
 
        }

Comment by Sergei Petrunia [ 2021-08-11 ]

Can the optimizer be fixed to handle this?

The problem is that in general case it is very hard to predict the performance of Range-Checked-For-Each-Record plan. Consider a basic case:

select * from t1, t2 where t2.key<t1.col

It is hard to tell whether "t2.key<t1.col" will be selective condition or not.

One can observe that a BETWEEN condition in form like this query uses:

M.t_start BETWEEN F.t - INTERVAL 1 HOUR AND F.t

is a quite common special case. It can be proven selective if a [certain kind of?] histogram is available (like one we'll get when MDEV-21130 is done?) : walk through all histogram buckets and see how much 1-hour interval can occupy) . This requires a new optimizer feature though.

Comment by Sergei Petrunia [ 2021-08-11 ]

allen.lee@mariadb.com , here are the takeaways:

Please find detailed explanations about each query performance above.

In particular, using CONCAT(column) makes the optimizer unable to use a certain query plan, after which it tries a "last resort" query plan of Range-Checked-For-Each-Record which turns out to be very good for this dataset and query.

I see a way to fix this, but it will only be possible after MariaDB 10.7 and will be a new optimizer feature (NRE anyone?)

At the moment, we can only suggest to use the CONCAT(column) or similar workarounds.

Generated at Thu Feb 08 09:42:40 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.