Optimize range query with group by-CodePudding

Having trouble with a query. Here is the outline -

Table structure:

CREATE TABLE `world` (
  `placeRef` int NOT NULL,
  `forenameRef` int NOT NULL,
  `surnameRef` int NOT NULL,
  `incidence` int NOT NULL
) ENGINE=MyISAM DEFAULT CHARSET=utf8mb3;

ALTER TABLE `world`
  ADD KEY `surnameRef_forenameRef` (`surnameRef`,`forenameRef`),
  ADD KEY `forenameRef_surnameRef` (`forenameRef`,`surnameRef`),
  ADD KEY `forenameRef` (`forenameRef`,`placeRef`);
COMMIT;

This table contains data like and has over 600,000,000 rows:

placeRef    forenameRef    surnameRef    incidence
1           1              2             100
2           1              3             600

This represents the number of people with a given forename-surname combination in a place.

I would like to be able to query all the forenames that a surname is attached to; and then perform another search for where those forenames exist, with a count of the sum incidence. For Example: get all the forenames of people who have the surname "Smith"; then get a list of all those forenames, grouped by place and with the sum incidence. I can do this with the following query:

SELECT placeRef, SUM( incidence )
FROM world
WHERE forenameRef IN
(
    SELECT DISTINCT forenameRef
    FROM world
    WHERE surnameRef = 214488
)
GROUP BY world.placeRef

However, this query takes about a minute to execute and will take more time if the surname being searched for is common.

The root problem is: performing a range query with a group doesn't utilize the full index.

Any suggestions how the speed could be improved?

CodePudding user response：

In my experience, if your query has a range condition (i.e. any kind of predicate other than = or IS NULL), the column for that condition is the last column in your index that can be used to optimize search, sort, or grouping.

In other words, suppose you have an index on columns (a, b, c).

The following uses all three columns. It is able to optimize the ORDER BY c, because since all rows matching the specific values of a and b will by definition be tied, and then those matching rows will already be in order by c, so the ORDER BY is a no-op.

SELECT * FROM mytable WHERE a = 1 AND b = 2 ORDER BY c;

But the next example only uses columns a, b. The ORDER BY needs to do a filesort, because the index is not in order by c.

SELECT * FROM mytable WHERE a = 1 AND b > 2 ORDER BY c;

A similar effect is true for GROUP BY. The following uses a, b for row selection, and it can also optimize the GROUP BY using the index, because each group of values per distinct value of c is guaranteed to be grouped together in the index. So it can count the rows for each value of c, and when it's done with one group, it is assured there will be no more rows later with that value of c.

SELECT c, COUNT(*) FROM mytable WHERE a = 1 AND b = 2 GROUP BY c;

But the range condition spoils that. The rows for each value of c are not grouped together. It's assumed that the rows for each value of c may be scattered among each of the higher values of b.

SELECT c, COUNT(*) FROM mytable WHERE a = 1 AND b > 2 GROUP BY c;

In this case, MySQL can't optimize the GROUP BY in this query. It must use a temporary table to count the rows per distinct value of c.

MySQL 8.0.13 introduced a new type of optimizer behavior, the Skip Scan Range Access Method. But as far as I know, it only applies to range conditions, not ORDER BY or GROUP BY.

It's still true that if you have a range condition, this spoils the index optimization of ORDER BY and GROUP BY.

CodePudding user response：

Unless I don't understand the task, it seems like this works:

SELECT placeRef, SUM( incidence )
    FROM world
    WHERE surnameRef = 214488
    GROUP BY placeRef;

Give it a try.

It would benefit from a composite index in this order:

INDEX(surnameRef, placeRef, incidence)

Is incidence being updated a lot? If so, leave it off my Index.

You should consider moving from MyISAM to InnoDB. It will need a suitable PK, probably

PRIMARY KEY(placeRef, surnameRef, forenameRef)

and it will take 2x-3x the disk space.