InnoDB's records_in_range estimates seem to be capped at ~50% of the table. (We used to observe this on various occasions before but I haven't been able to find an MDEV for this).
If I pass a range that contains a bigger fraction of the table, the estimated number of rows is still around 50% of the total rows in the table.
Test dataset:
create table ten(a int);
|
insert into ten values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
|
|
create table one_k(a int);
|
insert into one_k select A.a + B.a* 10 + C.a * 100 from ten A, ten B, ten C;
|
|
create table t1 (
|
a int,
|
b varchar(32),
|
c int,
|
key(a),
|
key(b)
|
) engine=innodb;
|
# 100K NULLs
|
insert into t1 select
|
null,
|
null,
|
A.a + 1000*B.a
|
from
|
one_k A,
|
one_k B
|
where
|
B.a<100;
|
|
# 900 K non-NULLs
|
insert into t1 select
|
A.a + 1000*B.a,
|
A.a + 1000*B.a,
|
A.a + 1000*B.a
|
from
|
one_k A,
|
one_k B
|
where
|
B.a>=100;
|
Now, both a IS NOT NULL or b IS NOT NULL match 900K rows (90% of the table).
But EXPLAIN will show the estimates of about 500K rows, which is 50% of the table:
explain select * from t1 force index (a) where a is not null ;
|
+------+-------------+-------+-------+---------------+------+---------+------+--------+-----------------------+
|
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
|
+------+-------------+-------+-------+---------------+------+---------+------+--------+-----------------------+
|
| 1 | SIMPLE | t1 | range | a | a | 5 | NULL | 494308 | Using index condition |
|
+------+-------------+-------+-------+---------------+------+---------+------+--------+-----------------------+
|
explain select * from t1 force index (b) where b is not null ;
|
+------+-------------+-------+-------+---------------+------+---------+------+--------+-----------------------+
|
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
|
+------+-------------+-------+-------+---------------+------+---------+------+--------+-----------------------+
|
| 1 | SIMPLE | t1 | range | b | b | 35 | NULL | 494308 | Using index condition |
|
+------+-------------+-------+-------+---------------+------+---------+------+--------+-----------------------+
|
When the optimizer was simple, this property was not a problem.
A simple optimizer would only use range estimates to construct range access. Range access is cheaper than full table if it covers about 30% of the table. Returning 50% of the table instead of 90% was not an issue.
A more advanced optimizer also attempts to use range estimates for condition selectivity, etc. Here, returning 50% selectivity instead of 90% is a problem. (One must take into account that selectivity is computed for multiple indexes. For example, for 5 indexes 0.5^2= 1/32 . 32x under-estimation of selectivity)
{"report":{"fcp":1245.3000001907349,"ttfb":280.8999996185303,"pageVisibility":"visible","entityId":75930,"key":"jira.project.issue.view-issue","isInitial":true,"threshold":1000,"elementTimings":{},"userDeviceMemory":8,"userDeviceProcessors":32,"apdex":0.5,"journeyId":"3450aed2-cfb8-4f1b-8893-28f5046bdc84","navigationType":0,"readyForUser":1350.3000001907349,"redirectCount":0,"resourceLoadedEnd":1865,"resourceLoadedStart":286.5999994277954,"resourceTiming":[{"duration":418.70000076293945,"initiatorType":"link","name":"https://jira.mariadb.org/s/2c21342762a6a02add1c328bed317ffd-CDN/lu2cib/820016/12ta74/0a8bac35585be7fc6c9cc5a0464cd4cf/_/download/contextbatch/css/_super/batch.css","startTime":286.5999994277954,"connectEnd":0,"connectStart":0,"domainLookupEnd":0,"domainLookupStart":0,"fetchStart":286.5999994277954,"redirectEnd":0,"redirectStart":0,"requestStart":0,"responseEnd":705.3000001907349,"responseStart":0,"secureConnectionStart":0},{"duration":418.80000019073486,"initiatorType":"link","name":"https://jira.mariadb.org/s/7ebd35e77e471bc30ff0eba799ebc151-CDN/lu2cib/820016/12ta74/494e4c556ecbb29f90a3d3b4f09cb99c/_/download/contextbatch/css/jira.browse.project,project.issue.navigator,jira.view.issue,jira.general,jira.global,atl.general,-_super/batch.css?agile_global_admin_condition=true&jag=true&jira.create.linked.issue=true&slack-enabled=true&whisper-enabled=true","startTime":286.8999996185303,"connectEnd":0,"connectStart":0,"domainLookupEnd":0,"domainLookupStart":0,"fetchStart":286.8999996185303,"redirectEnd":0,"redirectStart":0,"requestStart":0,"responseEnd":705.6999998092651,"responseStart":0,"secureConnectionStart":0},{"duration":439.6000003814697,"initiatorType":"script","name":"https://jira.mariadb.org/s/0917945aaa57108d00c5076fea35e069-CDN/lu2cib/820016/12ta74/0a8bac35585be7fc6c9cc5a0464cd4cf/_/download/contextbatch/js/_super/batch.js?locale=en","startTime":287.0999994277954,"connectEnd":287.0999994277954,"connectStart":287.0999994277954,"domainLookupEnd":287.0999994277954,"domainLookupStart":287.0999994277954,"fetchStart":287.0999994277954,"redirectEnd":0,"redirectStart":0,"requestStart":287.0999994277954,"responseEnd":726.6999998092651,"responseStart":726.6999998092651,"secureConnectionStart":287.0999994277954},{"duration":487.5,"initiatorType":"script","name":"https://jira.mariadb.org/s/2d8175ec2fa4c816e8023260bd8c1786-CDN/lu2cib/820016/12ta74/494e4c556ecbb29f90a3d3b4f09cb99c/_/download/contextbatch/js/jira.browse.project,project.issue.navigator,jira.view.issue,jira.general,jira.global,atl.general,-_super/batch.js?agile_global_admin_condition=true&jag=true&jira.create.linked.issue=true&locale=en&slack-enabled=true&whisper-enabled=true","startTime":287.19999980926514,"connectEnd":287.19999980926514,"connectStart":287.19999980926514,"domainLookupEnd":287.19999980926514,"domainLookupStart":287.19999980926514,"fetchStart":287.19999980926514,"redirectEnd":0,"redirectStart":0,"requestStart":287.19999980926514,"responseEnd":774.6999998092651,"responseStart":774.6999998092651,"secureConnectionStart":287.19999980926514},{"duration":490.4000005722046,"initiatorType":"script","name":"https://jira.mariadb.org/s/a9324d6758d385eb45c462685ad88f1d-CDN/lu2cib/820016/12ta74/c92c0caa9a024ae85b0ebdbed7fb4bd7/_/download/contextbatch/js/atl.global,-_super/batch.js?locale=en","startTime":287.3999996185303,"connectEnd":287.3999996185303,"connectStart":287.3999996185303,"domainLookupEnd":287.3999996185303,"domainLookupStart":287.3999996185303,"fetchStart":287.3999996185303,"redirectEnd":0,"redirectStart":0,"requestStart":287.3999996185303,"responseEnd":777.8000001907349,"responseStart":777.8000001907349,"secureConnectionStart":287.3999996185303},{"duration":490.70000076293945,"initiatorType":"script","name":"https://jira.mariadb.org/s/d41d8cd98f00b204e9800998ecf8427e-CDN/lu2cib/820016/12ta74/1.0/_/download/batch/jira.webresources:calendar-en/jira.webresources:calendar-en.js","startTime":287.5999994277954,"connectEnd":287.5999994277954,"connectStart":287.5999994277954,"domainLookupEnd":287.5999994277954,"domainLookupStart":287.5999994277954,"fetchStart":287.5999994277954,"redirectEnd":0,"redirectStart":0,"requestStart":287.5999994277954,"responseEnd":778.3000001907349,"responseStart":778.3000001907349,"secureConnectionStart":287.5999994277954},{"duration":491,"initiatorType":"script","name":"https://jira.mariadb.org/s/d41d8cd98f00b204e9800998ecf8427e-CDN/lu2cib/820016/12ta74/1.0/_/download/batch/jira.webresources:calendar-localisation-moment/jira.webresources:calendar-localisation-moment.js","startTime":287.8999996185303,"connectEnd":287.8999996185303,"connectStart":287.8999996185303,"domainLookupEnd":287.8999996185303,"domainLookupStart":287.8999996185303,"fetchStart":287.8999996185303,"redirectEnd":0,"redirectStart":0,"requestStart":287.8999996185303,"responseEnd":778.8999996185303,"responseStart":778.8999996185303,"secureConnectionStart":287.8999996185303},{"duration":591.5,"initiatorType":"link","name":"https://jira.mariadb.org/s/b04b06a02d1959df322d9cded3aeecc1-CDN/lu2cib/820016/12ta74/a2ff6aa845ffc9a1d22fe23d9ee791fc/_/download/contextbatch/css/jira.global.look-and-feel,-_super/batch.css","startTime":288,"connectEnd":0,"connectStart":0,"domainLookupEnd":0,"domainLookupStart":0,"fetchStart":288,"redirectEnd":0,"redirectStart":0,"requestStart":0,"responseEnd":879.5,"responseStart":0,"secureConnectionStart":0},{"duration":491.4000005722046,"initiatorType":"script","name":"https://jira.mariadb.org/rest/api/1.0/shortcuts/820016/47140b6e0a9bc2e4913da06536125810/shortcuts.js?context=issuenavigation&context=issueaction","startTime":288.0999994277954,"connectEnd":288.0999994277954,"connectStart":288.0999994277954,"domainLookupEnd":288.0999994277954,"domainLookupStart":288.0999994277954,"fetchStart":288.0999994277954,"redirectEnd":0,"redirectStart":0,"requestStart":288.0999994277954,"responseEnd":779.5,"responseStart":779.5,"secureConnectionStart":288.0999994277954},{"duration":591.6999998092651,"initiatorType":"link","name":"https://jira.mariadb.org/s/3ac36323ba5e4eb0af2aa7ac7211b4bb-CDN/lu2cib/820016/12ta74/d176f0986478cc64f24226b3d20c140d/_/download/contextbatch/css/com.atlassian.jira.projects.sidebar.init,-_super,-project.issue.navigator,-jira.view.issue/batch.css?jira.create.linked.issue=true","startTime":288.19999980926514,"connectEnd":0,"connectStart":0,"domainLookupEnd":0,"domainLookupStart":0,"fetchStart":288.19999980926514,"redirectEnd":0,"redirectStart":0,"requestStart":0,"responseEnd":879.8999996185303,"responseStart":0,"secureConnectionStart":0},{"duration":492,"initiatorType":"script","name":"https://jira.mariadb.org/s/5d5e8fe91fbc506585e83ea3b62ccc4b-CDN/lu2cib/820016/12ta74/d176f0986478cc64f24226b3d20c140d/_/download/contextbatch/js/com.atlassian.jira.projects.sidebar.init,-_super,-project.issue.navigator,-jira.view.issue/batch.js?jira.create.linked.issue=true&locale=en","startTime":288.3999996185303,"connectEnd":288.3999996185303,"connectStart":288.3999996185303,"domainLookupEnd":288.3999996185303,"domainLookupStart":288.3999996185303,"fetchStart":288.3999996185303,"redirectEnd":0,"redirectStart":0,"requestStart":288.3999996185303,"responseEnd":780.3999996185303,"responseStart":780.3999996185303,"secureConnectionStart":288.3999996185303},{"duration":807.6999998092651,"initiatorType":"script","name":"https://jira.mariadb.org/s/d41d8cd98f00b204e9800998ecf8427e-CDN/lu2cib/820016/12ta74/1.0/_/download/batch/jira.webresources:bigpipe-js/jira.webresources:bigpipe-js.js","startTime":297.19999980926514,"connectEnd":297.19999980926514,"connectStart":297.19999980926514,"domainLookupEnd":297.19999980926514,"domainLookupStart":297.19999980926514,"fetchStart":297.19999980926514,"redirectEnd":0,"redirectStart":0,"requestStart":297.19999980926514,"responseEnd":1104.8999996185303,"responseStart":1104.8999996185303,"secureConnectionStart":297.19999980926514},{"duration":1567.8000001907349,"initiatorType":"script","name":"https://jira.mariadb.org/s/d41d8cd98f00b204e9800998ecf8427e-CDN/lu2cib/820016/12ta74/1.0/_/download/batch/jira.webresources:bigpipe-init/jira.webresources:bigpipe-init.js","startTime":297.19999980926514,"connectEnd":297.19999980926514,"connectStart":297.19999980926514,"domainLookupEnd":297.19999980926514,"domainLookupStart":297.19999980926514,"fetchStart":297.19999980926514,"redirectEnd":0,"redirectStart":0,"requestStart":297.19999980926514,"responseEnd":1865,"responseStart":1865,"secureConnectionStart":297.19999980926514},{"duration":262.6000003814697,"initiatorType":"xmlhttprequest","name":"https://jira.mariadb.org/rest/webResources/1.0/resources","startTime":922.8999996185303,"connectEnd":922.8999996185303,"connectStart":922.8999996185303,"domainLookupEnd":922.8999996185303,"domainLookupStart":922.8999996185303,"fetchStart":922.8999996185303,"redirectEnd":0,"redirectStart":0,"requestStart":922.8999996185303,"responseEnd":1185.5,"responseStart":1185.5,"secureConnectionStart":922.8999996185303}],"fetchStart":0,"domainLookupStart":0,"domainLookupEnd":0,"connectStart":0,"connectEnd":0,"requestStart":108,"responseStart":281,"responseEnd":291,"domLoading":285,"domInteractive":1889,"domContentLoadedEventStart":1889,"domContentLoadedEventEnd":1936,"domComplete":2641,"loadEventStart":2641,"loadEventEnd":2642,"userAgent":"Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)","marks":[{"name":"bigPipe.sidebar-id.start","time":1866.8000001907349},{"name":"bigPipe.sidebar-id.end","time":1867.8000001907349},{"name":"bigPipe.activity-panel-pipe-id.start","time":1867.8999996185303},{"name":"bigPipe.activity-panel-pipe-id.end","time":1869.8000001907349},{"name":"activityTabFullyLoaded","time":1953.5999994277954}],"measures":[],"correlationId":"728d2093ccdad4","effectiveType":"4g","downlink":9,"rtt":0,"serverDuration":108,"dbReadsTimeInMs":16,"dbConnsTimeInMs":24,"applicationHash":"9d11dbea5f4be3d4cc21f03a88dd11d8c8687422","experiments":[]}}
This one:
commit b66cdbd1eaeed7e96317a03a190c496fd062ec71
Author: Monty <monty@mariadb.org>
Date: Thu Aug 11 13:05:23 2022 +0300
Changing all cost calculation to be given in milliseconds
https://github.com/mariadb/server/commit/b66cdbd1eaeed7e96317a03a190c496fd062ec71
Specifically, the part in btr0cur.cc where the piece of logic with
is ifdef-ed away.