MySQL Bugs: #120574: Range optimizer exceeds memory limit and chooses bad range plan for large IN lists

Bug #120574	Range optimizer exceeds memory limit and chooses bad range plan for large IN lists
Submitted:	29 May 14:05	Modified:	4 Aug 13:50
Reporter:	Qingping Zhu	Email Updates:
Status:	Duplicate	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	8.0.41	OS:	Any
Assigned to:		CPU Architecture:	Any
Tags:	Memory, Optimizer, performance, range_optimizer_max_mem_size, range-optimizer

Description:
A single EXPLAIN SELECT with large literal IN (...) lists can cause the range optimizer to allocate several GB of memory while constructing range scan candidates.

The server variable range_optimizer_max_mem_size is set to the default value 8388608 bytes, but the optimizer still builds a very large number of QUICK_RANGE objects before falling back or choosing the final access path. In the reproduced case, mysqld RSS grows to about 7-10GB during optimization of one SQL statement.

The query shape is:
- equality predicates on the first key parts
- large IN (...) predicates on following key parts
- ORDER BY matching the index order
- SELECT *, so the index is not covering

The problematic plan chooses type=range on the ordering index, with a row estimate much larger than the actual table size. In the local reduced repro, the table has about 405k rows, while the range plan estimates 134217728 rows. In the original case, the estimate was hundreds of millions of rows for a table of about 400k rows.

This causes two issues:
1. range_optimizer_max_mem_size does not effectively prevent large memory allocation in this path.
2. The optimizer may still choose range even though the estimated range scan is much more expensive than a full table/index scan or another access path.

How to repeat:
Use the attached reduced repro script:
mysql -uroot -h127.0.0.1 < single_sql_range_mem_repro.sql

The script creates a small synthetic schema with generic object names:
CREATE DATABASE r1;
CREATE TABLE r1.t (
  id int NOT NULL,
  c1 varchar(32) NOT NULL,
  c2 int NOT NULL,
  c3 varchar(32) NOT NULL,
  c4 varchar(32) NOT NULL,
  c5 varchar(32) NOT NULL,
  c6 varchar(32) NOT NULL,
  PRIMARY KEY (id),
  KEY k1 (c1, c2, c3 DESC, c4 DESC, c5 DESC)
);

It inserts about 405k deterministic rows, then runs:
CALL run_case(8192, 2048);

The procedure builds and executes one statement equivalent to:
EXPLAIN SELECT *
FROM t FORCE INDEX(k1)
WHERE c1 = 'x'
  AND c2 = 1
  AND c3 IN (...8192 literals...)
  AND c4 IN (...2048 literals...)
ORDER BY c3 DESC, c4 DESC, c5 DESC;

The generated SQL has about 92KB of text and creates 8192 * 2048 = 16777216 range combinations.

Observed on unpatched MySQL 8.0.41:
type: range
key:  k1
rows: 134217728
Extra: Using index condition
During optimization of this single statement, mysqld RSS peaked at about 7.79GB.

With the proposed guard patch applied, the same statement produced:
type: index
key:  k1
rows: 385189
Extra: Using where
Peak mysqld RSS was about 0.29GB.

Expected behavior
When range_optimizer_max_mem_size is exceeded, the range access path being evaluated should be abandoned or marked as unusable/too expensive. The optimizer should then choose another valid access path, such as full table/index scan or ref access, without allocating memory far beyond the configured range optimizer memory limit.

Actual behavior
The range optimizer may continue far enough to allocate several GB of memory for range construction, despite range_optimizer_max_mem_size=8388608. The final plan may still choose range, even when the estimated rows are much larger than the table size and another access path would be cheaper.

Suggested fix:
When the range optimizer detects EE_CAPACITY_EXCEEDED for range_optimizer_max_mem_size, propagate this state to the caller and prevent the current range candidate from being selected.

In particular:
- expose whether the range optimizer memory limit was exceeded
- after check_quick_select() reports the memory error, reject the candidate range scan
- before materializing QUICK_RANGE objects into the return mem_root, guard against a known excessive quick_n_ranges count
- fall back to another access path instead of returning a huge range scan candidate

A local prototype applies this behavior in:
sql/range_optimizer/internal.h
sql/range_optimizer/index_range_scan_plan.cc

The saved prototype patch is:
0001-range-optimizer-mem-guard-v1.patch
With this patch, the reduced test case no longer causes multi-GB memory growth and no longer chooses the pathological range plan.

Self-contained reduced repro script.

Attachment: single_sql_range_mem_repro.sql (application/octet-stream, text), 2.77 KiB.

Prototype patch for this issue

Attachment: 0001-range-optimizer-mem-guard-v1.patch (application/octet-stream, text), 3.13 KiB.

Hi Qingping Zhu,

Thank you for the test case. We have verified the issue. We think this is duplicate of an old report Bug#100595. As you have observed,  range_optimizer_max_mem_size limit does not apply in this case. This is because that setting limits memory used during range analysis. The large memory allocation in this case occurs later, when the selected range access is materialized into execution-time QUICK_RANGE objects; that allocation is not controlled by this setting. It is the same underlying issue as that of Bug#100595.
We are therefore marking this report as a duplicate. The required fix is to restrict the execution-time range representation and fall back to another applicable access path when that limit is reached.

We see that you have contributed a patch to handle this. Thank you very much, we appreciate it!  In order for us to continue the process of reviewing your contribution to MySQL, please send us a signed copy of the Oracle Contributor Agreement (OCA) as outlined in https://oca.opensource.oracle.com
Signing an OCA needs to be done only once and it's valid for all other Oracle governed Open Source projects as well. Getting a signed/approved OCA on file will help us facilitate your contribution - this one, and others in the future. 

Please let me know, if you have any questions.

Thank you for your interest in MySQL.

--Chaithra