An interesting case with key_column=rare_value

I’ve got a complaint about a very basic query that works poorly and I’m not sure how to handle it. The case is MDEV-25707. The query is very simple:

create table t (
  key_col int,
  INDEX idx1(key_col)

select *
from t
  key_col=const1 or
  key_col=const2 or
  -- and so forth, about 5K constants

In MariaDB 10.3, this query used a range scan. The EXPLAIN looked like so:

| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows   | Extra                 |
|    1 | SIMPLE      | t     | range | idx1          | idx1 | 3       | NULL | 101358 | Using index condition |

In MariaDB 10.5, it uses a full table scan, which is a surprise:

| id   | select_type | table | type | possible_keys | key  | key_len | ref  | rows    | Extra       |
|    1 | SIMPLE      | t     | ALL  | idx1          | NULL | NULL    | NULL | 1761063 | Using where |

and the query is slow. Why?

A bit of background: Normally, MySQL/MariaDB optimizer uses index dives to estimate how many rows will match each key_col=const range. This produces fairly precise estimates, but it does index dives (in this case, 5K index dives) which can be relatively expensive.

To combat this, MySQL and then MariaDB have introduced @@eq_range_index_dive_limit feature (MySQL docs, MariaDB docs). The idea is, when the query has many equality ranges, the optimizer will not do index dives but will use index cardinality statistics instead.

In this dataset, index statistics says there are about 70 rows with each key value. This gives an estimate of 70*5k = 350K rows in total. However, the query uses constants that either occur rarely or are not present in the dataset at all, so the query produces only 120 rows. Because of that, range scan is much cheaper than a full table scan.

It is obvious to suggest to set eq_range_index_dive_limit higher (or to 0 which means “never use index statistics”), but the users would like the optimizer to make the right choice automatically, without any tuning.

Certain kinds of Histograms, e.g. Most-Common-Value lists allow one to detect that the constants used by the query are very common. But is there any statistics to detect the opposite – that the used values are uncommon?

Optimizations for MIN/MAX with implicit and explicit grouping

Varun Gupta has pushed a fix for MDEV-24353. I was the reviewer. While investigating and fixing the issue, we had to revisit optimizations for MIN/MAX and different kinds of grouping.

SQL language has two kinds of grouping. “Explicit grouping” is done when the select has a GROUP BY clause. “Implicit grouping” happens when the query has aggregate function(s) but doesn’t have a GROUP BY clause, like

select count(*) from tbl

Here, there is only one group that contains the entire select output.

MIN/MAX Optimizations

Let’s start from implicit grouping and a basic query:

select min(col) from tbl

If there is an (ordered) index over col, one can resolve the query by making one index lookup: look into the index to find the first (smallest) value (If column col is NULLable, find the first non-NULL value). If the WHERE condition has a range:

select min(col) from tbl where col >= 10 and col <20

one can make a lookup to find the first value of col that’s greater-or-equal than 10. The range can be on a non-first key part, as long as all key parts before it have equalities:

select min(keypart2) from tbl where keypart1='foo' and keypart2>3

But that’s all that allowed. If the WHERE clause has something else, the optimizer will need to scan the index until it finds the value that matches the WHERE. It is also apparent that this works for MIN and MAX and won’t work for any other aggregate like COUNT or SUM.

This optimization doesn’t have a name. It is used whenever it is applicable (that is, it is not cost-based) because making one index lookup is as cheap as one can get.

MIN/MAX and explicit grouping

With explicit grouping, one can use the same approach. The difference is that there are potentially many groups. This means one needs groups to be separate (not interleaved) and a way to jump from one group to the next. Both are achieved by having GROUP BY columns at the start of the group:

select min(keypart2) from tbl group by keypart1 where keypart2>10

Each group is processed by two lookups:

  1. An index navigation command to “find the next different value of keypart1”
  2. An index navigation command to “find the first value with keypart2>10”

However, these “jumps” only make sense if the groups are large enough. So, the choice of whether to use this optimization is cost-based. The jumps gave name to the optimization – it is called Loose Index Scan.

The problem in MDEV-24353

The testcase had this :

-- The table has PRIMARY KEY (p,a);

-- Query with implicit grouping (fast)
select MIN(a) from t1 where p = 2;

-- Query with explicit grouping (slow)
select MIN(a) from t1 where p = 2 group by p;

The query with implicit grouping used the optimization and was instant. The query with explicit grouping wasn’t using Loose Scan and was optimization for implicit grouping worked, while one for explicit grouping didn’t.

Eventually, we’ve figured out the cause – there was an old heuristic rule “ref access is better than range access on the same index using same #key parts”. This is true, but not for Loose Scan (which is range-like access internally). The fix was to adjust the heuristic.

A side note: surprisingly, PostgreSQL is exhibiting similar behavior: it used an efficient query plan for the query with explicit grouping and an inefficient query plan for the query with implicit grouping: paste. Does it have an optimization that’s similar to MySQL/MariaDB’s Loose Scan?

Replication at cluster edge

I had to do some work fixing replication and wanted to share the experiences.


  • MariaDB is getting new storage engines that share the data between MariaDB
  • There is a demand to run these “shared-disk” engines alongside regular
    engines and replication. Like so:
  • Replication breaks when some tables have changes from the primary (aka master) “automagically” appear on the replica (aka slave).
  • MariaDB is getting support for running “shared disk” engines alongside with replication. The user experience is not entirely seamless yet, but it’s getting better.


MariaDB is getting new storage engines:

The first one is S3 Storage Engine, available in MariaDB 10.5. It’s basically a read-only Aria table that is stored in Amazon S3 or a compatible service. Its target use case is archive data that doesn’t get read much, and cloud environment where local storage is pay-per-gigabyte. In this setting, it pays off to put the archive into an S3 bucket and then share it between all MariaDB instances you have. Note that only the archive is shared, for non-archive data you’ll still want replication.

The second new engine is the Xpand Storage Engine. It is only available in MariaDB Enterprise. It connects to Xpand cluster (formerly known as Clustrix). Xpand cluster is a clustered database targeting mostly OLTP workloads. Think NDB Cluster which can also speak SQL.

If you’re just using Xpand, you don’t need replication:

  • All MariaDB nodes in the cluster immediately see all data
  • As for table definitions, Table Discovery feature allows one MariaDB instance to learn about the tables created through other MariaDB instances.

But it turns out there’s a demand to still have replication enabled. It’s used for hybrid Xpand-and- InnoDB setups, for propagating MariaDB-level entities like VIEWs, etc.

The problem

The base problem: when the replica (slave) starts to apply changes to the shared table, the data is already there. Moreover, if the replica has a delay, then the primary (master) might have already made further updates to it. Applying older updates from binlog will undo them and/or cause errors.

Also, we cannot binlog any statements that read the shared tables, as the data might be no longer there when the replica will be applying the statement. This includes e.g. statements like “ALTER TABLE xpand_table ENGINE=InnoDB”.

The solution

I think, the ideal would be to have a primary-only solution where the binlog is not allowed to have any references to the shared tables. But this wasn’t the choice made. As far as I understand, Monty wanted the binlog to be also usable as a self-contained backup. As a consequence, one needs to have special behavior both on the primary and on the replica.

Settings on the primary (master). Settings for S3 are on the left, Xpand settings are on the right:


Settings for the replica (slave):


Unfortunately, the solution is not complete. One needs to be careful when creating table in one engine and then changing it to another. This can confuse a delayed replica: MDEV-24351, MDEV-24367.

But if one is careful, things seem to work. As it usually is with replication :-).

On JSON Path in MariaDB

Short version:

  • JSON Path in MariaDB is now documented:
  • It supports a subset of JSON Path from SQL:2016. The subset is close to what MySQL supports.
  • It does have an extension to do recursive searches.
  • The search for matches is done “on the fly”, without constructing the document tree.

Longer version:

I got interested in JSON Path for two reasons: first, I was using it to extract portions of Optimizer Trace. Second, I am reviewing the patch for JSON_TABLE.

Unfortunately there wasn’t a description of MariaDB’s JSON Path dialect anywhere. Did everybody think paths are too obvious and something like is too trivial to document?

Well, it’s is not that simple. The definition of JSON Path in SQL:2016 standard takes 23 pages. Path expression can include filters, functions and arithmetic expressions (MariaDB doesn’t support any of those). One thing that the standard does NOT include is a capability to do recursive searches. You can ask for all members of an object or an array:


and you can find bar in the grand-children of foo:


but there’s no way to search for bar everywhere in the tree. MariaDB, MySQL and PostgreSQL have extensions for recursive searches:


will search for bar everywhere in the document. (In PostgreSQL, the syntax is slightly different: $.**.bar). This is very useful for querying the Optimizer Trace:

json_extract(trace, '$**.analyzing_range_alternatives'))


Some notes about the implementation

MariaDB doesn’t support filter conditions or [last] as array index. Which means we can walk through JSON document, and as soon as we see a node, we can tell whether it is a match or not. There is no need to build the parse tree or perform some kind of look-ahead.

As far as I understand, MySQL may or may not build the parse (DOM) tree, depending on the properties of the search path.

Slides and video: ANALYZE for statements: MariaDB’s hidden gem

My second talk at the MariaDB Fest was ANALYZE for statements: MariaDB’s hidden gem (slides, video). It also has a comparison with MySQL, with its EXPLAIN ANALYZE feature. MariaDB’s ANALYZE supports more kinds of statements, and a basic test has shown it has a lower CPU overhead for workloads with tight loops. I believe this is caused by MariaDB making fewer gettimeofday() calls. It might show fewer details about the query plan, though.

My experience with ANALYZE FORMAT=JSON was that it is immensely useful for troubleshooting query optimizer support issues.

Slides and video: Optimizer Trace walkthrough

It’s time to resume blogging. Starting with a bit of stale news: yours truly had two talks at MariaDB Fest . The first one was the Optimizer Trace Walkthrough (video, slides). The talk covers Optimizer Trace in MariaDB and it has a comparison with MySQL’s Optimizer Trace.

One interesting thing I’ve learned while presenting was that Øystein Grovlen has made a tool to summarize information from the trace –
Its main use case is analyze the join optimizer’s actions: it prints a condensed summary about what join order prefixes were considered and the reason they were discarded.

The tool doesn’t work with MariaDB, because MariaDB’s trace is slightly different. If I get a support escalation about a join optimization problem, I might try to get opttrace to work with MariaDB’s traces.

My proposals for Percona Live: Window Functions and ANALYZE for statements

I’ve made two session proposals for Percona Live conference:

if you feel these talks are worth it, please vote!

MariaDB 10.1: Better query optimization for ORDER BY … LIMIT

For some reason, we’ve been getting a lot of issues with ORDER BY optimization recently. The fixes have passed Elena Stepanova’s scrutiny and I’ve pushed them to MariaDB 10.1. Now, MariaDB’s ORDER BY ... LIMIT optimizer:

  • Doesn’t make stupid choices when several multi-part keys and potential range accesses are present (MDEV-6402)
  • Always uses “range” and (not full “index” scan) when it switches to an index to satisfy ORDER BY … LIMIT (MDEV-6657)
  • Tries hard to be smart and use cost/number of records estimates from other parts of the optimizer (MDEV-6384, MDEV-465, MySQL Bug#36817)
  • Takes full advantage of InnoDB’s Extended Keys feature when checking if filesort() can be skipped (MDEV-6796)

so, if you are struggling with poor optimization of ORDER BY ... LIMIT queries, help might be underway.

I have to admit that optimizations for ORDER BY... LIMIT are still far from perfect (both in MySQL and in MariaDB). The code is old and ugly and having spent some time debugging it, I can easily believe that it still does a poor job in some cases. The good part is that now we have some fresh knowledge of the ORDER BY … LIMIT optimization code, as well as RQG scripts for testing ORDER BY .. LIMIT queries. If you have any issues with ORDER BY LIMIT optimization, we will appreciate to see bugs filed for them.