MySQL Bugs: #109173: Contribution: Offset pushdown to InnoDB and removal of redundant conditions

Bug #109173	Contribution: Offset pushdown to InnoDB and removal of redundant conditions
Submitted:	23 Nov 2022 7:51	Modified:	24 Nov 2022 11:41
Reporter:	Maxime Conjard (OCA)	Email Updates:
Status:	Verified	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S5 (Performance)
Version:	.31, 8.0.31	OS:	Any
Assigned to:		CPU Architecture:	Any
Tags:	Contribution

Description:
Problem 1: 

Push the processing of the offset down to InnoDB

Why: 

By Skipping rows down in the storage engine, we do not have to return to the sql layer rows that are not going to be returned anyways

It is especially relevant for non-covering index because then the rows are skipped without ever having to be read from the base table 

Problem 2: 

Some conditions in index range scans are redundant in the sense that the storage engine already enforces that conditions but they are checked again in the sql layer  

Fix: Assess if the condition is redundant, and remove it. Side benefit: because pushing down the offset is only going to be possible when the sql does not have to carry out any checks on the rows that are returned, this would broaden the scope of the queries for which the offset can be pushed down. 

How to repeat:
Problem 1: 
CREATE TABLE t1 (a INT , b INT , INDEX(b));
INSERT INTO t1 VALUES (1, 2), (2, 3), (3, 3), (4, 3);

explain format=tree SELECT * FROM t1 LIMIT 1 OFFSET 100;

In this case, we could simply skip all the rows in the storage engine without ever having to return them to the sql layer

Problem 2: 

mysql> CREATE TABLE t3 (a INT , b INT , INDEX(a,b));
RT INTO t3 VALUES (1, 2),(2, 3),(3, 3),(4, 3);Query OK, 0 rows affected (0.04 sec)

mysql> INSERT INTO t3 VALUES (1, 2),(2, 3),(3, 3),(4, 3);
Query OK, 4 rows affected (0.02 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> explain format=tree SELECT a,b FROM t3 WHERE a = 2 AND b < 2;
+-----------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                               |
+-----------------------------------------------------------------------------------------------------------------------+
| -> Filter: ((t3.a = 2) and (t3.b < 2))  (cost=0.46 rows=1)
    -> Index range scan on t3 using a  (cost=0.46 rows=1)
 |
+-----------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

The Filter checks are redundant as they are already enforced by InnoDB, these checks could be removed

Suggested fix:
I am going to propose a feature "solving" this problem.

na

patch for the feature (*) I confirm the code being submitted is offered under the terms of the OCA, and that I am authorized to contribute it.

Contribution: my_patch.txt (text/plain), 922.50 KiB.

Hello Maxime Conjard,

Thank you for the report and contribution.

Sincerely,
Umesh

Hello,

our team observes this with MySQL 8.4 where pagination is used and hundreds of thousands of records are present.

Are there any plans to incorporate this fix?

For example such a query:

SELECT *
FROM `accounts`
WHERE `accounts`.`provider_account_id` = 5
AND `accounts`.`id` != 5
ORDER BY `accounts`.`created_at`, `id` ASC
LIMIT 1 OFFSET 355000;

It is like 10 times slower than an equivalent query like:

WITH paginated_ids AS (
SELECT id as account_id
FROM accounts
WHERE accounts.provider_account_id = 5 AND accounts.id != 5
ORDER BY accounts.created_at ASC, accounts.id ASC
LIMIT 1 OFFSET 355000)
SELECT accounts.*
FROM accounts
INNER JOIN paginated_ids ON paginated_ids.account_id = accounts.id
ORDER BY
	accounts.created_at ASC,
	accounts.id ASC;

In one deployment where we have just implemented this workaround, overall MySQL CPU load fell from 60%-80% to 20%-30%. Basically it poses a huge performance penalty.

So I think it makes sense for this fix to be prioritized.

fwiw my testing showed that other RDBMS already optimize such queries out of the box and don't require additional tuning or workarounds, i.e. pgsql and oracle, so for products supporting multiple backend database servers, it is rather tricky to apply such kind of vendor specific optimizations. 

Thank you!