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?