Details
-
New Feature
-
Status: Open (View Workflow)
-
Major
-
Resolution: Unresolved
-
None
Description
(All file and line references below are with respect to git sha 38e420ba6e84ef6efc9c54b04ebd4dbc95dc3cae which was 11.4 at the time of writing.)
Range filtering is cost-based. The decision to filter is made exclusively on the cost by using selectivity and it's made during optimization, to choose the best join ordering. However, at this point in optimization, ICP is not taken into account. First, we choose some join order and then later we figure out if an index condition can be pushed. If yes, then we push it, but that is downstream of join ordering. At the same time, the selectivity of ICP can be large, so using the rowid range filters together with a large ICP selectivity might cause a slowdown: we spend time building the filter but we may not gain anything or just a little. The original approach was that if ICP is used, and although we decide we use a filter, we cancel this usage. So filtering can never be used together with ICP to access the table. Since the original implementation, other changes over time have now permitted this usage, which is not desirable. At the same time, we are not certain what is more optimal at this point: to cancel the ICP or to cancel the rowid filter.
Here is an example scenario in which rowid filtering and ICP both are used:
create table t1 (a int, b int);
|
insert into t1 (a, b) values
|
(1, 1000),
|
(2, 2000),
|
(3, 3000),
|
(4, 4000),
|
(5, 5000),
|
(6, 6000),
|
(7, 7000),
|
(8, 8000),
|
(9, 9000),
|
(10, 10000);
|
create index t1_a on t1 (a);
|
create index t1_b on t1 (b);
|
set session optimizer_where_cost=10;
|
analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G
|
If we place a breakpoint at handler.cc:7144, just before we check the pushed rowid filter, then we can see the following abriged stack trace (we can also see that h->pushed_idx_cond and h->pushed_rowid_filter both are set at this point):
(lldb) bt
|
* thread #8, stop reason = breakpoint 1.1
|
* frame #0: 0x0000000102ab3404 mariadbd`handler_rowid_filter_check(h_arg=0x0000000156139ca8) at handler.cc:7146:3
|
frame #1: 0x000000010382bcc4 mariadbd`row_search_idx_cond_check(mysql_rec="\xfb", prebuilt=0x000000015613d498, rec="\x80", offsets=0x000000016d9da3b0) at row0sel.cc:4104:34
|
frame #2: 0x00000001038296ac mariadbd`row_search_mvcc(buf="\xfb", mode=PAGE_CUR_GE, prebuilt=0x000000015613d498, match_mode=0, direction=0) at row0sel.cc:5493:10
|
frame #3: 0x000000010360aa5c mariadbd`ha_innobase::index_read(this=0x0000000156139ca8, buf="\xfb", key_ptr="", key_len=5, find_flag=HA_READ_KEY_OR_NEXT) at ha_innodb.cc:9121:3
|
frame #4: 0x000000010338dec4 mariadbd`handler::index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.h:4190:12
|
frame #5: 0x0000000102aa6230 mariadbd`handler::ha_index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.cc:3792:3
|
frame #6: 0x0000000102ab2c9c mariadbd`handler::read_range_first(this=0x0000000156139ca8, start_key=0x0000000156139df8, end_key=0x0000000156139e18, eq_range_arg=false, sorted=true) at handler.cc:6949:13
|
frame #7: 0x0000000103140a08 mariadbd`handler::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at multi_range_read.cc:590:15
|
frame #8: 0x0000000103140ba8 mariadbd`Mrr_simple_index_reader::get_next(this=0x000000015613a340, range_info=0x000000016d9dae48) at multi_range_read.cc:627:32
|
frame #9: 0x0000000103143f30 mariadbd`DsMrr_impl::dsmrr_next(this=0x000000015613a1f0, range_info=0x000000016d9dae48) at multi_range_read.cc:1731:26
|
frame #10: 0x00000001036242cc mariadbd`ha_innobase::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at ha_innodb.cc:20301:18
|
frame #11: 0x0000000102d0f4ec mariadbd`QUICK_RANGE_SELECT::get_next(this=0x0000000155e14760) at opt_range.cc:13276:5
|
frame #12: 0x0000000102d3cc64 mariadbd`rr_quick(info=0x000000015bcc4b10) at records.cc:402:34
|
frame #13: 0x0000000102d0e4c0 mariadbd`READ_RECORD::read_record(this=0x000000015bcc4b10) at records.h:81:30
|
frame #14: 0x0000000102f42398 mariadbd`join_init_read_record(tab=0x000000015bcc4a40) at sql_select.cc:25221:27
|
frame #15: 0x0000000102f1e2a0 mariadbd`sub_select(join=0x000000015bcc2278, join_tab=0x000000015bcc4a40, end_of_records=false) at sql_select.cc:24153:12
|
frame #16: 0x0000000102f45e28 mariadbd`do_select(join=0x000000015bcc2278, procedure=0x0000000000000000) at sql_select.cc:23667:14
|
And the corresponding analyze output to confirm:
MariaDB [test]> analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G
|
*************************** 1. row ***************************
|
ANALYZE: {
|
"query_optimization": {
|
"r_total_time_ms": 0.471028634
|
},
|
"query_block": {
|
"select_id": 1,
|
"cost": 0.012382207,
|
"r_loops": 1,
|
"r_total_time_ms": 0.194622362,
|
"nested_loop": [
|
{
|
"table": {
|
"table_name": "t1",
|
"access_type": "range",
|
"possible_keys": ["t1_a", "t1_b"],
|
"key": "t1_b",
|
"key_length": "5",
|
"used_key_parts": ["b"],
|
"rowid_filter": {
|
"range": {
|
"key": "t1_a",
|
"used_key_parts": ["a"]
|
},
|
"rows": 6,
|
"selectivity_pct": 60,
|
"r_rows": 6,
|
"r_lookups": 1,
|
"r_selectivity_pct": 100,
|
"r_buffer_size": 4,
|
"r_filling_time_ms": 0.082075697
|
},
|
"loops": 1,
|
"r_loops": 1,
|
"rows": 1,
|
"r_rows": 1,
|
"cost": 0.012005717,
|
"r_table_time_ms": 0.115547909,
|
"r_other_time_ms": 0.028011614,
|
"r_engine_stats": {
|
"pages_accessed": 3
|
},
|
"filtered": 60,
|
"r_filtered": 100,
|
"index_condition": "t1.b between 4000 and 4100",
|
"attached_condition": "t1.a between 3 and 8"
|
}
|
}
|
]
|
}
|
}
|
1 row in set (0.001 sec)
|
2. Objection
One can construct similar cases with e.g. join operation:
2.1 Example with JOIN
Consider this testcase (https://gist.github.com/spetrunia/a2f28cd0573afba20179c2a828ac8d49):
explain
|
select * from t1, t2 |
where
|
t1.b+1<10 and |
t2.key2=t1.a and |
t2.key1 between 100 and 200; |
*************************** 1. row ***************************
|
id: 1
|
select_type: SIMPLE
|
table: t1
|
type: ALL
|
possible_keys: NULL
|
key: NULL
|
key_len: NULL
|
ref: NULL
|
rows: 100
|
Extra: Using where
|
*************************** 2. row ***************************
|
id: 1
|
select_type: SIMPLE
|
table: t2
|
type: ref|filter
|
possible_keys: key1,key2
|
key: key2|key1
|
key_len: 5|5
|
ref: j1.t1.a
|
rows: 19 (1%)
|
Extra: Using where; Using rowid filter
|
|
|
|
Here, we build the rowid filter once per join execution, and then it is used during all index lookups to table t2. We expect 100 lookups, each scanning 19 rows.
Now, table t1 has "Using where", the condition t1.b+1<10. We don't know its selectivity. If this condition is selective, it will reduce the number of index lookups made to table t2, to the point where using Rowid Filter for table t2 will no longer bring benefit.
2.2 When not to use Rowid Filter - too many cases?
This MDEV requests that Rowid Filter is not used when selective ICP condition can make it not worth using.
Should Rowid Filter also not be used when join operation and "Using where" conditions can make it not worth using?
If the answer is Yes, then we would need to disable use of Rowid Filter in most of the cases where it is currently used...
Attachments
Activity
| Field | Original Value | New Value |
|---|---|---|
| Description |
(All file and line references below are with respect to git sha {{38e420ba6e84ef6efc9c54b04ebd4dbc95dc3cae}} which was 11.4 at the time of writing.)
Range filtering is cost-based. The decision to filter is made exclusively on the cost by using selectivity and it's made during optimization, to choose the best join ordering. However, at this point in optimization, ICP is not taken into account. First, we choose some join order and then later we figure out if an index condition can be pushed. If yes, then we push it, but that is downstream of join ordering. At the same time, the selectivity of ICP can be large, so using the rowid range filters together with a large ICP selectivity might cause a slowdown: we spend time building the filter but we may not gain anything or just a little. The original approach was that if ICP is used, and although we decide we use a filter, we cancel this usage. So filtering can never be used together with ICP to access the table. Since the original implementation, other changes over time have now permitted this usage, which is not desirable. At the same time, we are not certain what is more optimal at this point: to cancel the ICP or to cancel the rowid filter. Here is an example scenario in which rowid filtering and ICP both are used: {code} create table t1 (a int, b int); insert into t1 (a, b) values (1, 1000), (2, 2000), (3, 3000), (4, 4000), (5, 5000), (6, 6000), (7, 7000), (8, 8000), (9, 9000), (10, 10000); create index t1_a on t1 (a); create index t1_b on t1 (b); set session optimizer_where_cost=10; analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G {code} If we place a breakpoint at handler.cc:7144, just before we check the pushed rowid filter, then we can see the following abriged stack trace (we can also see that h->pushed_idx_cond and h->pushed_rowid_filter both are set at this point): {code} (lldb) bt * thread #8, stop reason = breakpoint 1.1 * frame #0: 0x0000000102ab3404 mariadbd`handler_rowid_filter_check(h_arg=0x0000000156139ca8) at handler.cc:7146:3 frame #1: 0x000000010382bcc4 mariadbd`row_search_idx_cond_check(mysql_rec="\xfb", prebuilt=0x000000015613d498, rec="\x80", offsets=0x000000016d9da3b0) at row0sel.cc:4104:34 frame #2: 0x00000001038296ac mariadbd`row_search_mvcc(buf="\xfb", mode=PAGE_CUR_GE, prebuilt=0x000000015613d498, match_mode=0, direction=0) at row0sel.cc:5493:10 frame #3: 0x000000010360aa5c mariadbd`ha_innobase::index_read(this=0x0000000156139ca8, buf="\xfb", key_ptr="", key_len=5, find_flag=HA_READ_KEY_OR_NEXT) at ha_innodb.cc:9121:3 frame #4: 0x000000010338dec4 mariadbd`handler::index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.h:4190:12 frame #5: 0x0000000102aa6230 mariadbd`handler::ha_index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.cc:3792:3 frame #6: 0x0000000102ab2c9c mariadbd`handler::read_range_first(this=0x0000000156139ca8, start_key=0x0000000156139df8, end_key=0x0000000156139e18, eq_range_arg=false, sorted=true) at handler.cc:6949:13 frame #7: 0x0000000103140a08 mariadbd`handler::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at multi_range_read.cc:590:15 frame #8: 0x0000000103140ba8 mariadbd`Mrr_simple_index_reader::get_next(this=0x000000015613a340, range_info=0x000000016d9dae48) at multi_range_read.cc:627:32 frame #9: 0x0000000103143f30 mariadbd`DsMrr_impl::dsmrr_next(this=0x000000015613a1f0, range_info=0x000000016d9dae48) at multi_range_read.cc:1731:26 frame #10: 0x00000001036242cc mariadbd`ha_innobase::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at ha_innodb.cc:20301:18 frame #11: 0x0000000102d0f4ec mariadbd`QUICK_RANGE_SELECT::get_next(this=0x0000000155e14760) at opt_range.cc:13276:5 frame #12: 0x0000000102d3cc64 mariadbd`rr_quick(info=0x000000015bcc4b10) at records.cc:402:34 frame #13: 0x0000000102d0e4c0 mariadbd`READ_RECORD::read_record(this=0x000000015bcc4b10) at records.h:81:30 frame #14: 0x0000000102f42398 mariadbd`join_init_read_record(tab=0x000000015bcc4a40) at sql_select.cc:25221:27 frame #15: 0x0000000102f1e2a0 mariadbd`sub_select(join=0x000000015bcc2278, join_tab=0x000000015bcc4a40, end_of_records=false) at sql_select.cc:24153:12 frame #16: 0x0000000102f45e28 mariadbd`do_select(join=0x000000015bcc2278, procedure=0x0000000000000000) at sql_select.cc:23667:14 {code} And the corresponding analyze output to confirm: {code} MariaDB [test]> analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G *************************** 1. row *************************** ANALYZE: { "query_optimization": { "r_total_time_ms": 0.471028634 }, "query_block": { "select_id": 1, "cost": 0.012382207, "r_loops": 1, "r_total_time_ms": 0.194622362, "nested_loop": [ { "table": { "table_name": "t1", "access_type": "range", "possible_keys": ["t1_a", "t1_b"], "key": "t1_b", "key_length": "5", "used_key_parts": ["b"], "rowid_filter": { "range": { "key": "t1_a", "used_key_parts": ["a"] }, "rows": 6, "selectivity_pct": 60, "r_rows": 6, "r_lookups": 1, "r_selectivity_pct": 100, "r_buffer_size": 4, "r_filling_time_ms": 0.082075697 }, "loops": 1, "r_loops": 1, "rows": 1, "r_rows": 1, "cost": 0.012005717, "r_table_time_ms": 0.115547909, "r_other_time_ms": 0.028011614, "r_engine_stats": { "pages_accessed": 3 }, "filtered": 60, "r_filtered": 100, "index_condition": "t1.b between 4000 and 4100", "attached_condition": "t1.a between 3 and 8" } } ] } } 1 row in set (0.001 sec) {code} |
(All file and line references below are with respect to git sha {{38e420ba6e84ef6efc9c54b04ebd4dbc95dc3cae}} which was 11.4 at the time of writing.)
We shouldn't allow rowid filtering to be used together with index condition pushdown, due to performance problems. Range filtering is cost-based. The decision to filter is made exclusively on the cost by using selectivity and it's made during optimization, when choosing the best join ordering. However, at this point in optimization, ICP performance is not taken into account. During optimization we first choose some join order and then later we figure out if an index condition can be pushed. If yes, then we push it, but that is downstream of join ordering. At the same time, the selectivity of ICP can be large, so using the rowid range filters together with a large ICP selectivity might cause a slowdown: we spend time building the filter but we may not gain anything or maybe will gain just a little. The original approach was that if ICP is used, and although we decide we use a filter, we cancel this usage. So filtering can never be used together with ICP to access the table. Since the original implementation, other changes over time have now permitted this usage, which is not desirable. However, we are not certain what is more optimal at this point: to cancel the ICP or to cancel the rowid filter. Here is an example scenario in which rowid filtering and ICP both are used: {code} create table t1 (a int, b int); insert into t1 (a, b) values (1, 1000), (2, 2000), (3, 3000), (4, 4000), (5, 5000), (6, 6000), (7, 7000), (8, 8000), (9, 9000), (10, 10000); create index t1_a on t1 (a); create index t1_b on t1 (b); set session optimizer_where_cost=10; analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G {code} If we place a breakpoint at handler.cc:7144, just before we check the pushed rowid filter, then we can see the following abriged stack trace (we can also see that h->pushed_idx_cond and h->pushed_rowid_filter both are set at this point): {code} (lldb) bt * thread #8, stop reason = breakpoint 1.1 * frame #0: 0x0000000102ab3404 mariadbd`handler_rowid_filter_check(h_arg=0x0000000156139ca8) at handler.cc:7146:3 frame #1: 0x000000010382bcc4 mariadbd`row_search_idx_cond_check(mysql_rec="\xfb", prebuilt=0x000000015613d498, rec="\x80", offsets=0x000000016d9da3b0) at row0sel.cc:4104:34 frame #2: 0x00000001038296ac mariadbd`row_search_mvcc(buf="\xfb", mode=PAGE_CUR_GE, prebuilt=0x000000015613d498, match_mode=0, direction=0) at row0sel.cc:5493:10 frame #3: 0x000000010360aa5c mariadbd`ha_innobase::index_read(this=0x0000000156139ca8, buf="\xfb", key_ptr="", key_len=5, find_flag=HA_READ_KEY_OR_NEXT) at ha_innodb.cc:9121:3 frame #4: 0x000000010338dec4 mariadbd`handler::index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.h:4190:12 frame #5: 0x0000000102aa6230 mariadbd`handler::ha_index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.cc:3792:3 frame #6: 0x0000000102ab2c9c mariadbd`handler::read_range_first(this=0x0000000156139ca8, start_key=0x0000000156139df8, end_key=0x0000000156139e18, eq_range_arg=false, sorted=true) at handler.cc:6949:13 frame #7: 0x0000000103140a08 mariadbd`handler::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at multi_range_read.cc:590:15 frame #8: 0x0000000103140ba8 mariadbd`Mrr_simple_index_reader::get_next(this=0x000000015613a340, range_info=0x000000016d9dae48) at multi_range_read.cc:627:32 frame #9: 0x0000000103143f30 mariadbd`DsMrr_impl::dsmrr_next(this=0x000000015613a1f0, range_info=0x000000016d9dae48) at multi_range_read.cc:1731:26 frame #10: 0x00000001036242cc mariadbd`ha_innobase::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at ha_innodb.cc:20301:18 frame #11: 0x0000000102d0f4ec mariadbd`QUICK_RANGE_SELECT::get_next(this=0x0000000155e14760) at opt_range.cc:13276:5 frame #12: 0x0000000102d3cc64 mariadbd`rr_quick(info=0x000000015bcc4b10) at records.cc:402:34 frame #13: 0x0000000102d0e4c0 mariadbd`READ_RECORD::read_record(this=0x000000015bcc4b10) at records.h:81:30 frame #14: 0x0000000102f42398 mariadbd`join_init_read_record(tab=0x000000015bcc4a40) at sql_select.cc:25221:27 frame #15: 0x0000000102f1e2a0 mariadbd`sub_select(join=0x000000015bcc2278, join_tab=0x000000015bcc4a40, end_of_records=false) at sql_select.cc:24153:12 frame #16: 0x0000000102f45e28 mariadbd`do_select(join=0x000000015bcc2278, procedure=0x0000000000000000) at sql_select.cc:23667:14 {code} And the corresponding analyze output to confirm: {code} MariaDB [test]> analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G *************************** 1. row *************************** ANALYZE: { "query_optimization": { "r_total_time_ms": 0.471028634 }, "query_block": { "select_id": 1, "cost": 0.012382207, "r_loops": 1, "r_total_time_ms": 0.194622362, "nested_loop": [ { "table": { "table_name": "t1", "access_type": "range", "possible_keys": ["t1_a", "t1_b"], "key": "t1_b", "key_length": "5", "used_key_parts": ["b"], "rowid_filter": { "range": { "key": "t1_a", "used_key_parts": ["a"] }, "rows": 6, "selectivity_pct": 60, "r_rows": 6, "r_lookups": 1, "r_selectivity_pct": 100, "r_buffer_size": 4, "r_filling_time_ms": 0.082075697 }, "loops": 1, "r_loops": 1, "rows": 1, "r_rows": 1, "cost": 0.012005717, "r_table_time_ms": 0.115547909, "r_other_time_ms": 0.028011614, "r_engine_stats": { "pages_accessed": 3 }, "filtered": 60, "r_filtered": 100, "index_condition": "t1.b between 4000 and 4100", "attached_condition": "t1.a between 3 and 8" } } ] } } 1 row in set (0.001 sec) {code} |
| Description |
(All file and line references below are with respect to git sha {{38e420ba6e84ef6efc9c54b04ebd4dbc95dc3cae}} which was 11.4 at the time of writing.)
We shouldn't allow rowid filtering to be used together with index condition pushdown, due to performance problems. Range filtering is cost-based. The decision to filter is made exclusively on the cost by using selectivity and it's made during optimization, when choosing the best join ordering. However, at this point in optimization, ICP performance is not taken into account. During optimization we first choose some join order and then later we figure out if an index condition can be pushed. If yes, then we push it, but that is downstream of join ordering. At the same time, the selectivity of ICP can be large, so using the rowid range filters together with a large ICP selectivity might cause a slowdown: we spend time building the filter but we may not gain anything or maybe will gain just a little. The original approach was that if ICP is used, and although we decide we use a filter, we cancel this usage. So filtering can never be used together with ICP to access the table. Since the original implementation, other changes over time have now permitted this usage, which is not desirable. However, we are not certain what is more optimal at this point: to cancel the ICP or to cancel the rowid filter. Here is an example scenario in which rowid filtering and ICP both are used: {code} create table t1 (a int, b int); insert into t1 (a, b) values (1, 1000), (2, 2000), (3, 3000), (4, 4000), (5, 5000), (6, 6000), (7, 7000), (8, 8000), (9, 9000), (10, 10000); create index t1_a on t1 (a); create index t1_b on t1 (b); set session optimizer_where_cost=10; analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G {code} If we place a breakpoint at handler.cc:7144, just before we check the pushed rowid filter, then we can see the following abriged stack trace (we can also see that h->pushed_idx_cond and h->pushed_rowid_filter both are set at this point): {code} (lldb) bt * thread #8, stop reason = breakpoint 1.1 * frame #0: 0x0000000102ab3404 mariadbd`handler_rowid_filter_check(h_arg=0x0000000156139ca8) at handler.cc:7146:3 frame #1: 0x000000010382bcc4 mariadbd`row_search_idx_cond_check(mysql_rec="\xfb", prebuilt=0x000000015613d498, rec="\x80", offsets=0x000000016d9da3b0) at row0sel.cc:4104:34 frame #2: 0x00000001038296ac mariadbd`row_search_mvcc(buf="\xfb", mode=PAGE_CUR_GE, prebuilt=0x000000015613d498, match_mode=0, direction=0) at row0sel.cc:5493:10 frame #3: 0x000000010360aa5c mariadbd`ha_innobase::index_read(this=0x0000000156139ca8, buf="\xfb", key_ptr="", key_len=5, find_flag=HA_READ_KEY_OR_NEXT) at ha_innodb.cc:9121:3 frame #4: 0x000000010338dec4 mariadbd`handler::index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.h:4190:12 frame #5: 0x0000000102aa6230 mariadbd`handler::ha_index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.cc:3792:3 frame #6: 0x0000000102ab2c9c mariadbd`handler::read_range_first(this=0x0000000156139ca8, start_key=0x0000000156139df8, end_key=0x0000000156139e18, eq_range_arg=false, sorted=true) at handler.cc:6949:13 frame #7: 0x0000000103140a08 mariadbd`handler::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at multi_range_read.cc:590:15 frame #8: 0x0000000103140ba8 mariadbd`Mrr_simple_index_reader::get_next(this=0x000000015613a340, range_info=0x000000016d9dae48) at multi_range_read.cc:627:32 frame #9: 0x0000000103143f30 mariadbd`DsMrr_impl::dsmrr_next(this=0x000000015613a1f0, range_info=0x000000016d9dae48) at multi_range_read.cc:1731:26 frame #10: 0x00000001036242cc mariadbd`ha_innobase::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at ha_innodb.cc:20301:18 frame #11: 0x0000000102d0f4ec mariadbd`QUICK_RANGE_SELECT::get_next(this=0x0000000155e14760) at opt_range.cc:13276:5 frame #12: 0x0000000102d3cc64 mariadbd`rr_quick(info=0x000000015bcc4b10) at records.cc:402:34 frame #13: 0x0000000102d0e4c0 mariadbd`READ_RECORD::read_record(this=0x000000015bcc4b10) at records.h:81:30 frame #14: 0x0000000102f42398 mariadbd`join_init_read_record(tab=0x000000015bcc4a40) at sql_select.cc:25221:27 frame #15: 0x0000000102f1e2a0 mariadbd`sub_select(join=0x000000015bcc2278, join_tab=0x000000015bcc4a40, end_of_records=false) at sql_select.cc:24153:12 frame #16: 0x0000000102f45e28 mariadbd`do_select(join=0x000000015bcc2278, procedure=0x0000000000000000) at sql_select.cc:23667:14 {code} And the corresponding analyze output to confirm: {code} MariaDB [test]> analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G *************************** 1. row *************************** ANALYZE: { "query_optimization": { "r_total_time_ms": 0.471028634 }, "query_block": { "select_id": 1, "cost": 0.012382207, "r_loops": 1, "r_total_time_ms": 0.194622362, "nested_loop": [ { "table": { "table_name": "t1", "access_type": "range", "possible_keys": ["t1_a", "t1_b"], "key": "t1_b", "key_length": "5", "used_key_parts": ["b"], "rowid_filter": { "range": { "key": "t1_a", "used_key_parts": ["a"] }, "rows": 6, "selectivity_pct": 60, "r_rows": 6, "r_lookups": 1, "r_selectivity_pct": 100, "r_buffer_size": 4, "r_filling_time_ms": 0.082075697 }, "loops": 1, "r_loops": 1, "rows": 1, "r_rows": 1, "cost": 0.012005717, "r_table_time_ms": 0.115547909, "r_other_time_ms": 0.028011614, "r_engine_stats": { "pages_accessed": 3 }, "filtered": 60, "r_filtered": 100, "index_condition": "t1.b between 4000 and 4100", "attached_condition": "t1.a between 3 and 8" } } ] } } 1 row in set (0.001 sec) {code} |
(All file and line references below are with respect to git sha {{38e420ba6e84ef6efc9c54b04ebd4dbc95dc3cae}} which was 11.4 at the time of writing.)
Range filtering is cost-based. The decision to filter is made exclusively on the cost by using selectivity and it's made during optimization, to choose the best join ordering. However, at this point in optimization, ICP is not taken into account. First, we choose some join order and then later we figure out if an index condition can be pushed. If yes, then we push it, but that is downstream of join ordering. At the same time, the selectivity of ICP can be large, so using the rowid range filters together with a large ICP selectivity might cause a slowdown: we spend time building the filter but we may not gain anything or just a little. The original approach was that if ICP is used, and although we decide we use a filter, we cancel this usage. So filtering can never be used together with ICP to access the table. Since the original implementation, other changes over time have now permitted this usage, which is not desirable. At the same time, we are not certain what is more optimal at this point: to cancel the ICP or to cancel the rowid filter. Here is an example scenario in which rowid filtering and ICP both are used: {code} create table t1 (a int, b int); insert into t1 (a, b) values (1, 1000), (2, 2000), (3, 3000), (4, 4000), (5, 5000), (6, 6000), (7, 7000), (8, 8000), (9, 9000), (10, 10000); create index t1_a on t1 (a); create index t1_b on t1 (b); set session optimizer_where_cost=10; analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G {code} If we place a breakpoint at handler.cc:7144, just before we check the pushed rowid filter, then we can see the following abriged stack trace (we can also see that h->pushed_idx_cond and h->pushed_rowid_filter both are set at this point): {code} (lldb) bt * thread #8, stop reason = breakpoint 1.1 * frame #0: 0x0000000102ab3404 mariadbd`handler_rowid_filter_check(h_arg=0x0000000156139ca8) at handler.cc:7146:3 frame #1: 0x000000010382bcc4 mariadbd`row_search_idx_cond_check(mysql_rec="\xfb", prebuilt=0x000000015613d498, rec="\x80", offsets=0x000000016d9da3b0) at row0sel.cc:4104:34 frame #2: 0x00000001038296ac mariadbd`row_search_mvcc(buf="\xfb", mode=PAGE_CUR_GE, prebuilt=0x000000015613d498, match_mode=0, direction=0) at row0sel.cc:5493:10 frame #3: 0x000000010360aa5c mariadbd`ha_innobase::index_read(this=0x0000000156139ca8, buf="\xfb", key_ptr="", key_len=5, find_flag=HA_READ_KEY_OR_NEXT) at ha_innodb.cc:9121:3 frame #4: 0x000000010338dec4 mariadbd`handler::index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.h:4190:12 frame #5: 0x0000000102aa6230 mariadbd`handler::ha_index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.cc:3792:3 frame #6: 0x0000000102ab2c9c mariadbd`handler::read_range_first(this=0x0000000156139ca8, start_key=0x0000000156139df8, end_key=0x0000000156139e18, eq_range_arg=false, sorted=true) at handler.cc:6949:13 frame #7: 0x0000000103140a08 mariadbd`handler::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at multi_range_read.cc:590:15 frame #8: 0x0000000103140ba8 mariadbd`Mrr_simple_index_reader::get_next(this=0x000000015613a340, range_info=0x000000016d9dae48) at multi_range_read.cc:627:32 frame #9: 0x0000000103143f30 mariadbd`DsMrr_impl::dsmrr_next(this=0x000000015613a1f0, range_info=0x000000016d9dae48) at multi_range_read.cc:1731:26 frame #10: 0x00000001036242cc mariadbd`ha_innobase::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at ha_innodb.cc:20301:18 frame #11: 0x0000000102d0f4ec mariadbd`QUICK_RANGE_SELECT::get_next(this=0x0000000155e14760) at opt_range.cc:13276:5 frame #12: 0x0000000102d3cc64 mariadbd`rr_quick(info=0x000000015bcc4b10) at records.cc:402:34 frame #13: 0x0000000102d0e4c0 mariadbd`READ_RECORD::read_record(this=0x000000015bcc4b10) at records.h:81:30 frame #14: 0x0000000102f42398 mariadbd`join_init_read_record(tab=0x000000015bcc4a40) at sql_select.cc:25221:27 frame #15: 0x0000000102f1e2a0 mariadbd`sub_select(join=0x000000015bcc2278, join_tab=0x000000015bcc4a40, end_of_records=false) at sql_select.cc:24153:12 frame #16: 0x0000000102f45e28 mariadbd`do_select(join=0x000000015bcc2278, procedure=0x0000000000000000) at sql_select.cc:23667:14 {code} And the corresponding analyze output to confirm: {code} MariaDB [test]> analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G *************************** 1. row *************************** ANALYZE: { "query_optimization": { "r_total_time_ms": 0.471028634 }, "query_block": { "select_id": 1, "cost": 0.012382207, "r_loops": 1, "r_total_time_ms": 0.194622362, "nested_loop": [ { "table": { "table_name": "t1", "access_type": "range", "possible_keys": ["t1_a", "t1_b"], "key": "t1_b", "key_length": "5", "used_key_parts": ["b"], "rowid_filter": { "range": { "key": "t1_a", "used_key_parts": ["a"] }, "rows": 6, "selectivity_pct": 60, "r_rows": 6, "r_lookups": 1, "r_selectivity_pct": 100, "r_buffer_size": 4, "r_filling_time_ms": 0.082075697 }, "loops": 1, "r_loops": 1, "rows": 1, "r_rows": 1, "cost": 0.012005717, "r_table_time_ms": 0.115547909, "r_other_time_ms": 0.028011614, "r_engine_stats": { "pages_accessed": 3 }, "filtered": 60, "r_filtered": 100, "index_condition": "t1.b between 4000 and 4100", "attached_condition": "t1.a between 3 and 8" } } ] } } 1 row in set (0.001 sec) {code} h2. Objection Consider a basic example with joon: {code:sql} explain select * from t1, t2 where t1.b+1<10 and t2.key2=t1.a and t2.key1 between 100 and 200; {code} {code} *************************** 1. row *************************** id: 1 select_type: SIMPLE table: t1 type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 100 Extra: Using where *************************** 2. row *************************** id: 1 select_type: SIMPLE table: t2 type: ref|filter possible_keys: key1,key2 key: key2|key1 key_len: 5|5 ref: j1.t1.a rows: 19 (1%) Extra: Using where; Using rowid filter {code} |
| Component/s | Optimizer [ 10200 ] |
| Fix Version/s | 12.1 [ 29992 ] |
| Affects Version/s | 11.4 [ 29301 ] | |
| Affects Version/s | 12.0 [ 29945 ] |
| Description |
(All file and line references below are with respect to git sha {{38e420ba6e84ef6efc9c54b04ebd4dbc95dc3cae}} which was 11.4 at the time of writing.)
Range filtering is cost-based. The decision to filter is made exclusively on the cost by using selectivity and it's made during optimization, to choose the best join ordering. However, at this point in optimization, ICP is not taken into account. First, we choose some join order and then later we figure out if an index condition can be pushed. If yes, then we push it, but that is downstream of join ordering. At the same time, the selectivity of ICP can be large, so using the rowid range filters together with a large ICP selectivity might cause a slowdown: we spend time building the filter but we may not gain anything or just a little. The original approach was that if ICP is used, and although we decide we use a filter, we cancel this usage. So filtering can never be used together with ICP to access the table. Since the original implementation, other changes over time have now permitted this usage, which is not desirable. At the same time, we are not certain what is more optimal at this point: to cancel the ICP or to cancel the rowid filter. Here is an example scenario in which rowid filtering and ICP both are used: {code} create table t1 (a int, b int); insert into t1 (a, b) values (1, 1000), (2, 2000), (3, 3000), (4, 4000), (5, 5000), (6, 6000), (7, 7000), (8, 8000), (9, 9000), (10, 10000); create index t1_a on t1 (a); create index t1_b on t1 (b); set session optimizer_where_cost=10; analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G {code} If we place a breakpoint at handler.cc:7144, just before we check the pushed rowid filter, then we can see the following abriged stack trace (we can also see that h->pushed_idx_cond and h->pushed_rowid_filter both are set at this point): {code} (lldb) bt * thread #8, stop reason = breakpoint 1.1 * frame #0: 0x0000000102ab3404 mariadbd`handler_rowid_filter_check(h_arg=0x0000000156139ca8) at handler.cc:7146:3 frame #1: 0x000000010382bcc4 mariadbd`row_search_idx_cond_check(mysql_rec="\xfb", prebuilt=0x000000015613d498, rec="\x80", offsets=0x000000016d9da3b0) at row0sel.cc:4104:34 frame #2: 0x00000001038296ac mariadbd`row_search_mvcc(buf="\xfb", mode=PAGE_CUR_GE, prebuilt=0x000000015613d498, match_mode=0, direction=0) at row0sel.cc:5493:10 frame #3: 0x000000010360aa5c mariadbd`ha_innobase::index_read(this=0x0000000156139ca8, buf="\xfb", key_ptr="", key_len=5, find_flag=HA_READ_KEY_OR_NEXT) at ha_innodb.cc:9121:3 frame #4: 0x000000010338dec4 mariadbd`handler::index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.h:4190:12 frame #5: 0x0000000102aa6230 mariadbd`handler::ha_index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.cc:3792:3 frame #6: 0x0000000102ab2c9c mariadbd`handler::read_range_first(this=0x0000000156139ca8, start_key=0x0000000156139df8, end_key=0x0000000156139e18, eq_range_arg=false, sorted=true) at handler.cc:6949:13 frame #7: 0x0000000103140a08 mariadbd`handler::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at multi_range_read.cc:590:15 frame #8: 0x0000000103140ba8 mariadbd`Mrr_simple_index_reader::get_next(this=0x000000015613a340, range_info=0x000000016d9dae48) at multi_range_read.cc:627:32 frame #9: 0x0000000103143f30 mariadbd`DsMrr_impl::dsmrr_next(this=0x000000015613a1f0, range_info=0x000000016d9dae48) at multi_range_read.cc:1731:26 frame #10: 0x00000001036242cc mariadbd`ha_innobase::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at ha_innodb.cc:20301:18 frame #11: 0x0000000102d0f4ec mariadbd`QUICK_RANGE_SELECT::get_next(this=0x0000000155e14760) at opt_range.cc:13276:5 frame #12: 0x0000000102d3cc64 mariadbd`rr_quick(info=0x000000015bcc4b10) at records.cc:402:34 frame #13: 0x0000000102d0e4c0 mariadbd`READ_RECORD::read_record(this=0x000000015bcc4b10) at records.h:81:30 frame #14: 0x0000000102f42398 mariadbd`join_init_read_record(tab=0x000000015bcc4a40) at sql_select.cc:25221:27 frame #15: 0x0000000102f1e2a0 mariadbd`sub_select(join=0x000000015bcc2278, join_tab=0x000000015bcc4a40, end_of_records=false) at sql_select.cc:24153:12 frame #16: 0x0000000102f45e28 mariadbd`do_select(join=0x000000015bcc2278, procedure=0x0000000000000000) at sql_select.cc:23667:14 {code} And the corresponding analyze output to confirm: {code} MariaDB [test]> analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G *************************** 1. row *************************** ANALYZE: { "query_optimization": { "r_total_time_ms": 0.471028634 }, "query_block": { "select_id": 1, "cost": 0.012382207, "r_loops": 1, "r_total_time_ms": 0.194622362, "nested_loop": [ { "table": { "table_name": "t1", "access_type": "range", "possible_keys": ["t1_a", "t1_b"], "key": "t1_b", "key_length": "5", "used_key_parts": ["b"], "rowid_filter": { "range": { "key": "t1_a", "used_key_parts": ["a"] }, "rows": 6, "selectivity_pct": 60, "r_rows": 6, "r_lookups": 1, "r_selectivity_pct": 100, "r_buffer_size": 4, "r_filling_time_ms": 0.082075697 }, "loops": 1, "r_loops": 1, "rows": 1, "r_rows": 1, "cost": 0.012005717, "r_table_time_ms": 0.115547909, "r_other_time_ms": 0.028011614, "r_engine_stats": { "pages_accessed": 3 }, "filtered": 60, "r_filtered": 100, "index_condition": "t1.b between 4000 and 4100", "attached_condition": "t1.a between 3 and 8" } } ] } } 1 row in set (0.001 sec) {code} h2. Objection Consider a basic example with joon: {code:sql} explain select * from t1, t2 where t1.b+1<10 and t2.key2=t1.a and t2.key1 between 100 and 200; {code} {code} *************************** 1. row *************************** id: 1 select_type: SIMPLE table: t1 type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 100 Extra: Using where *************************** 2. row *************************** id: 1 select_type: SIMPLE table: t2 type: ref|filter possible_keys: key1,key2 key: key2|key1 key_len: 5|5 ref: j1.t1.a rows: 19 (1%) Extra: Using where; Using rowid filter {code} |
(All file and line references below are with respect to git sha {{38e420ba6e84ef6efc9c54b04ebd4dbc95dc3cae}} which was 11.4 at the time of writing.)
Range filtering is cost-based. The decision to filter is made exclusively on the cost by using selectivity and it's made during optimization, to choose the best join ordering. However, at this point in optimization, ICP is not taken into account. First, we choose some join order and then later we figure out if an index condition can be pushed. If yes, then we push it, but that is downstream of join ordering. At the same time, the selectivity of ICP can be large, so using the rowid range filters together with a large ICP selectivity might cause a slowdown: we spend time building the filter but we may not gain anything or just a little. The original approach was that if ICP is used, and although we decide we use a filter, we cancel this usage. So filtering can never be used together with ICP to access the table. Since the original implementation, other changes over time have now permitted this usage, which is not desirable. At the same time, we are not certain what is more optimal at this point: to cancel the ICP or to cancel the rowid filter. Here is an example scenario in which rowid filtering and ICP both are used: {code} create table t1 (a int, b int); insert into t1 (a, b) values (1, 1000), (2, 2000), (3, 3000), (4, 4000), (5, 5000), (6, 6000), (7, 7000), (8, 8000), (9, 9000), (10, 10000); create index t1_a on t1 (a); create index t1_b on t1 (b); set session optimizer_where_cost=10; analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G {code} If we place a breakpoint at handler.cc:7144, just before we check the pushed rowid filter, then we can see the following abriged stack trace (we can also see that h->pushed_idx_cond and h->pushed_rowid_filter both are set at this point): {code} (lldb) bt * thread #8, stop reason = breakpoint 1.1 * frame #0: 0x0000000102ab3404 mariadbd`handler_rowid_filter_check(h_arg=0x0000000156139ca8) at handler.cc:7146:3 frame #1: 0x000000010382bcc4 mariadbd`row_search_idx_cond_check(mysql_rec="\xfb", prebuilt=0x000000015613d498, rec="\x80", offsets=0x000000016d9da3b0) at row0sel.cc:4104:34 frame #2: 0x00000001038296ac mariadbd`row_search_mvcc(buf="\xfb", mode=PAGE_CUR_GE, prebuilt=0x000000015613d498, match_mode=0, direction=0) at row0sel.cc:5493:10 frame #3: 0x000000010360aa5c mariadbd`ha_innobase::index_read(this=0x0000000156139ca8, buf="\xfb", key_ptr="", key_len=5, find_flag=HA_READ_KEY_OR_NEXT) at ha_innodb.cc:9121:3 frame #4: 0x000000010338dec4 mariadbd`handler::index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.h:4190:12 frame #5: 0x0000000102aa6230 mariadbd`handler::ha_index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.cc:3792:3 frame #6: 0x0000000102ab2c9c mariadbd`handler::read_range_first(this=0x0000000156139ca8, start_key=0x0000000156139df8, end_key=0x0000000156139e18, eq_range_arg=false, sorted=true) at handler.cc:6949:13 frame #7: 0x0000000103140a08 mariadbd`handler::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at multi_range_read.cc:590:15 frame #8: 0x0000000103140ba8 mariadbd`Mrr_simple_index_reader::get_next(this=0x000000015613a340, range_info=0x000000016d9dae48) at multi_range_read.cc:627:32 frame #9: 0x0000000103143f30 mariadbd`DsMrr_impl::dsmrr_next(this=0x000000015613a1f0, range_info=0x000000016d9dae48) at multi_range_read.cc:1731:26 frame #10: 0x00000001036242cc mariadbd`ha_innobase::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at ha_innodb.cc:20301:18 frame #11: 0x0000000102d0f4ec mariadbd`QUICK_RANGE_SELECT::get_next(this=0x0000000155e14760) at opt_range.cc:13276:5 frame #12: 0x0000000102d3cc64 mariadbd`rr_quick(info=0x000000015bcc4b10) at records.cc:402:34 frame #13: 0x0000000102d0e4c0 mariadbd`READ_RECORD::read_record(this=0x000000015bcc4b10) at records.h:81:30 frame #14: 0x0000000102f42398 mariadbd`join_init_read_record(tab=0x000000015bcc4a40) at sql_select.cc:25221:27 frame #15: 0x0000000102f1e2a0 mariadbd`sub_select(join=0x000000015bcc2278, join_tab=0x000000015bcc4a40, end_of_records=false) at sql_select.cc:24153:12 frame #16: 0x0000000102f45e28 mariadbd`do_select(join=0x000000015bcc2278, procedure=0x0000000000000000) at sql_select.cc:23667:14 {code} And the corresponding analyze output to confirm: {code} MariaDB [test]> analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G *************************** 1. row *************************** ANALYZE: { "query_optimization": { "r_total_time_ms": 0.471028634 }, "query_block": { "select_id": 1, "cost": 0.012382207, "r_loops": 1, "r_total_time_ms": 0.194622362, "nested_loop": [ { "table": { "table_name": "t1", "access_type": "range", "possible_keys": ["t1_a", "t1_b"], "key": "t1_b", "key_length": "5", "used_key_parts": ["b"], "rowid_filter": { "range": { "key": "t1_a", "used_key_parts": ["a"] }, "rows": 6, "selectivity_pct": 60, "r_rows": 6, "r_lookups": 1, "r_selectivity_pct": 100, "r_buffer_size": 4, "r_filling_time_ms": 0.082075697 }, "loops": 1, "r_loops": 1, "rows": 1, "r_rows": 1, "cost": 0.012005717, "r_table_time_ms": 0.115547909, "r_other_time_ms": 0.028011614, "r_engine_stats": { "pages_accessed": 3 }, "filtered": 60, "r_filtered": 100, "index_condition": "t1.b between 4000 and 4100", "attached_condition": "t1.a between 3 and 8" } } ] } } 1 row in set (0.001 sec) {code} h2. Objection Consider a basic example with joon: {code:sql} explain select * from t1, t2 where t1.b+1<10 and t2.key2=t1.a and t2.key1 between 100 and 200; {code} {code} *************************** 1. row *************************** id: 1 select_type: SIMPLE table: t1 type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 100 Extra: Using where *************************** 2. row *************************** id: 1 select_type: SIMPLE table: t2 type: ref|filter possible_keys: key1,key2 key: key2|key1 key_len: 5|5 ref: j1.t1.a rows: 19 (1%) Extra: Using where; Using rowid filter {code} Here, we build the rowid filter once per join execution, and then it is used during all index lookups to table t2. We expect 100 lookups, each scanning 19 rows). Now, table t1 has "Using where", the condition {{t1.b+1<10}}. We don't know its selectivity. If this condition is selective, it will reduce the number of index lookups made to table t2, to the point where using Rowid Filter for table t2 will no longer bring benefit. This MDEV requests that Rowid Filter is not used with Pushed Index condition. Should Rowid Filter also be not used when it is used with ref access and the join plan has "Using where" conditions which may reduce the number of times the Rowid Filter is used? |
| Description |
(All file and line references below are with respect to git sha {{38e420ba6e84ef6efc9c54b04ebd4dbc95dc3cae}} which was 11.4 at the time of writing.)
Range filtering is cost-based. The decision to filter is made exclusively on the cost by using selectivity and it's made during optimization, to choose the best join ordering. However, at this point in optimization, ICP is not taken into account. First, we choose some join order and then later we figure out if an index condition can be pushed. If yes, then we push it, but that is downstream of join ordering. At the same time, the selectivity of ICP can be large, so using the rowid range filters together with a large ICP selectivity might cause a slowdown: we spend time building the filter but we may not gain anything or just a little. The original approach was that if ICP is used, and although we decide we use a filter, we cancel this usage. So filtering can never be used together with ICP to access the table. Since the original implementation, other changes over time have now permitted this usage, which is not desirable. At the same time, we are not certain what is more optimal at this point: to cancel the ICP or to cancel the rowid filter. Here is an example scenario in which rowid filtering and ICP both are used: {code} create table t1 (a int, b int); insert into t1 (a, b) values (1, 1000), (2, 2000), (3, 3000), (4, 4000), (5, 5000), (6, 6000), (7, 7000), (8, 8000), (9, 9000), (10, 10000); create index t1_a on t1 (a); create index t1_b on t1 (b); set session optimizer_where_cost=10; analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G {code} If we place a breakpoint at handler.cc:7144, just before we check the pushed rowid filter, then we can see the following abriged stack trace (we can also see that h->pushed_idx_cond and h->pushed_rowid_filter both are set at this point): {code} (lldb) bt * thread #8, stop reason = breakpoint 1.1 * frame #0: 0x0000000102ab3404 mariadbd`handler_rowid_filter_check(h_arg=0x0000000156139ca8) at handler.cc:7146:3 frame #1: 0x000000010382bcc4 mariadbd`row_search_idx_cond_check(mysql_rec="\xfb", prebuilt=0x000000015613d498, rec="\x80", offsets=0x000000016d9da3b0) at row0sel.cc:4104:34 frame #2: 0x00000001038296ac mariadbd`row_search_mvcc(buf="\xfb", mode=PAGE_CUR_GE, prebuilt=0x000000015613d498, match_mode=0, direction=0) at row0sel.cc:5493:10 frame #3: 0x000000010360aa5c mariadbd`ha_innobase::index_read(this=0x0000000156139ca8, buf="\xfb", key_ptr="", key_len=5, find_flag=HA_READ_KEY_OR_NEXT) at ha_innodb.cc:9121:3 frame #4: 0x000000010338dec4 mariadbd`handler::index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.h:4190:12 frame #5: 0x0000000102aa6230 mariadbd`handler::ha_index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.cc:3792:3 frame #6: 0x0000000102ab2c9c mariadbd`handler::read_range_first(this=0x0000000156139ca8, start_key=0x0000000156139df8, end_key=0x0000000156139e18, eq_range_arg=false, sorted=true) at handler.cc:6949:13 frame #7: 0x0000000103140a08 mariadbd`handler::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at multi_range_read.cc:590:15 frame #8: 0x0000000103140ba8 mariadbd`Mrr_simple_index_reader::get_next(this=0x000000015613a340, range_info=0x000000016d9dae48) at multi_range_read.cc:627:32 frame #9: 0x0000000103143f30 mariadbd`DsMrr_impl::dsmrr_next(this=0x000000015613a1f0, range_info=0x000000016d9dae48) at multi_range_read.cc:1731:26 frame #10: 0x00000001036242cc mariadbd`ha_innobase::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at ha_innodb.cc:20301:18 frame #11: 0x0000000102d0f4ec mariadbd`QUICK_RANGE_SELECT::get_next(this=0x0000000155e14760) at opt_range.cc:13276:5 frame #12: 0x0000000102d3cc64 mariadbd`rr_quick(info=0x000000015bcc4b10) at records.cc:402:34 frame #13: 0x0000000102d0e4c0 mariadbd`READ_RECORD::read_record(this=0x000000015bcc4b10) at records.h:81:30 frame #14: 0x0000000102f42398 mariadbd`join_init_read_record(tab=0x000000015bcc4a40) at sql_select.cc:25221:27 frame #15: 0x0000000102f1e2a0 mariadbd`sub_select(join=0x000000015bcc2278, join_tab=0x000000015bcc4a40, end_of_records=false) at sql_select.cc:24153:12 frame #16: 0x0000000102f45e28 mariadbd`do_select(join=0x000000015bcc2278, procedure=0x0000000000000000) at sql_select.cc:23667:14 {code} And the corresponding analyze output to confirm: {code} MariaDB [test]> analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G *************************** 1. row *************************** ANALYZE: { "query_optimization": { "r_total_time_ms": 0.471028634 }, "query_block": { "select_id": 1, "cost": 0.012382207, "r_loops": 1, "r_total_time_ms": 0.194622362, "nested_loop": [ { "table": { "table_name": "t1", "access_type": "range", "possible_keys": ["t1_a", "t1_b"], "key": "t1_b", "key_length": "5", "used_key_parts": ["b"], "rowid_filter": { "range": { "key": "t1_a", "used_key_parts": ["a"] }, "rows": 6, "selectivity_pct": 60, "r_rows": 6, "r_lookups": 1, "r_selectivity_pct": 100, "r_buffer_size": 4, "r_filling_time_ms": 0.082075697 }, "loops": 1, "r_loops": 1, "rows": 1, "r_rows": 1, "cost": 0.012005717, "r_table_time_ms": 0.115547909, "r_other_time_ms": 0.028011614, "r_engine_stats": { "pages_accessed": 3 }, "filtered": 60, "r_filtered": 100, "index_condition": "t1.b between 4000 and 4100", "attached_condition": "t1.a between 3 and 8" } } ] } } 1 row in set (0.001 sec) {code} h2. Objection Consider a basic example with joon: {code:sql} explain select * from t1, t2 where t1.b+1<10 and t2.key2=t1.a and t2.key1 between 100 and 200; {code} {code} *************************** 1. row *************************** id: 1 select_type: SIMPLE table: t1 type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 100 Extra: Using where *************************** 2. row *************************** id: 1 select_type: SIMPLE table: t2 type: ref|filter possible_keys: key1,key2 key: key2|key1 key_len: 5|5 ref: j1.t1.a rows: 19 (1%) Extra: Using where; Using rowid filter {code} Here, we build the rowid filter once per join execution, and then it is used during all index lookups to table t2. We expect 100 lookups, each scanning 19 rows). Now, table t1 has "Using where", the condition {{t1.b+1<10}}. We don't know its selectivity. If this condition is selective, it will reduce the number of index lookups made to table t2, to the point where using Rowid Filter for table t2 will no longer bring benefit. This MDEV requests that Rowid Filter is not used with Pushed Index condition. Should Rowid Filter also be not used when it is used with ref access and the join plan has "Using where" conditions which may reduce the number of times the Rowid Filter is used? |
(All file and line references below are with respect to git sha {{38e420ba6e84ef6efc9c54b04ebd4dbc95dc3cae}} which was 11.4 at the time of writing.)
Range filtering is cost-based. The decision to filter is made exclusively on the cost by using selectivity and it's made during optimization, to choose the best join ordering. However, at this point in optimization, ICP is not taken into account. First, we choose some join order and then later we figure out if an index condition can be pushed. If yes, then we push it, but that is downstream of join ordering. At the same time, the selectivity of ICP can be large, so using the rowid range filters together with a large ICP selectivity might cause a slowdown: we spend time building the filter but we may not gain anything or just a little. The original approach was that if ICP is used, and although we decide we use a filter, we cancel this usage. So filtering can never be used together with ICP to access the table. Since the original implementation, other changes over time have now permitted this usage, which is not desirable. At the same time, we are not certain what is more optimal at this point: to cancel the ICP or to cancel the rowid filter. Here is an example scenario in which rowid filtering and ICP both are used: {code} create table t1 (a int, b int); insert into t1 (a, b) values (1, 1000), (2, 2000), (3, 3000), (4, 4000), (5, 5000), (6, 6000), (7, 7000), (8, 8000), (9, 9000), (10, 10000); create index t1_a on t1 (a); create index t1_b on t1 (b); set session optimizer_where_cost=10; analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G {code} If we place a breakpoint at handler.cc:7144, just before we check the pushed rowid filter, then we can see the following abriged stack trace (we can also see that h->pushed_idx_cond and h->pushed_rowid_filter both are set at this point): {code} (lldb) bt * thread #8, stop reason = breakpoint 1.1 * frame #0: 0x0000000102ab3404 mariadbd`handler_rowid_filter_check(h_arg=0x0000000156139ca8) at handler.cc:7146:3 frame #1: 0x000000010382bcc4 mariadbd`row_search_idx_cond_check(mysql_rec="\xfb", prebuilt=0x000000015613d498, rec="\x80", offsets=0x000000016d9da3b0) at row0sel.cc:4104:34 frame #2: 0x00000001038296ac mariadbd`row_search_mvcc(buf="\xfb", mode=PAGE_CUR_GE, prebuilt=0x000000015613d498, match_mode=0, direction=0) at row0sel.cc:5493:10 frame #3: 0x000000010360aa5c mariadbd`ha_innobase::index_read(this=0x0000000156139ca8, buf="\xfb", key_ptr="", key_len=5, find_flag=HA_READ_KEY_OR_NEXT) at ha_innodb.cc:9121:3 frame #4: 0x000000010338dec4 mariadbd`handler::index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.h:4190:12 frame #5: 0x0000000102aa6230 mariadbd`handler::ha_index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.cc:3792:3 frame #6: 0x0000000102ab2c9c mariadbd`handler::read_range_first(this=0x0000000156139ca8, start_key=0x0000000156139df8, end_key=0x0000000156139e18, eq_range_arg=false, sorted=true) at handler.cc:6949:13 frame #7: 0x0000000103140a08 mariadbd`handler::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at multi_range_read.cc:590:15 frame #8: 0x0000000103140ba8 mariadbd`Mrr_simple_index_reader::get_next(this=0x000000015613a340, range_info=0x000000016d9dae48) at multi_range_read.cc:627:32 frame #9: 0x0000000103143f30 mariadbd`DsMrr_impl::dsmrr_next(this=0x000000015613a1f0, range_info=0x000000016d9dae48) at multi_range_read.cc:1731:26 frame #10: 0x00000001036242cc mariadbd`ha_innobase::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at ha_innodb.cc:20301:18 frame #11: 0x0000000102d0f4ec mariadbd`QUICK_RANGE_SELECT::get_next(this=0x0000000155e14760) at opt_range.cc:13276:5 frame #12: 0x0000000102d3cc64 mariadbd`rr_quick(info=0x000000015bcc4b10) at records.cc:402:34 frame #13: 0x0000000102d0e4c0 mariadbd`READ_RECORD::read_record(this=0x000000015bcc4b10) at records.h:81:30 frame #14: 0x0000000102f42398 mariadbd`join_init_read_record(tab=0x000000015bcc4a40) at sql_select.cc:25221:27 frame #15: 0x0000000102f1e2a0 mariadbd`sub_select(join=0x000000015bcc2278, join_tab=0x000000015bcc4a40, end_of_records=false) at sql_select.cc:24153:12 frame #16: 0x0000000102f45e28 mariadbd`do_select(join=0x000000015bcc2278, procedure=0x0000000000000000) at sql_select.cc:23667:14 {code} And the corresponding analyze output to confirm: {code} MariaDB [test]> analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G *************************** 1. row *************************** ANALYZE: { "query_optimization": { "r_total_time_ms": 0.471028634 }, "query_block": { "select_id": 1, "cost": 0.012382207, "r_loops": 1, "r_total_time_ms": 0.194622362, "nested_loop": [ { "table": { "table_name": "t1", "access_type": "range", "possible_keys": ["t1_a", "t1_b"], "key": "t1_b", "key_length": "5", "used_key_parts": ["b"], "rowid_filter": { "range": { "key": "t1_a", "used_key_parts": ["a"] }, "rows": 6, "selectivity_pct": 60, "r_rows": 6, "r_lookups": 1, "r_selectivity_pct": 100, "r_buffer_size": 4, "r_filling_time_ms": 0.082075697 }, "loops": 1, "r_loops": 1, "rows": 1, "r_rows": 1, "cost": 0.012005717, "r_table_time_ms": 0.115547909, "r_other_time_ms": 0.028011614, "r_engine_stats": { "pages_accessed": 3 }, "filtered": 60, "r_filtered": 100, "index_condition": "t1.b between 4000 and 4100", "attached_condition": "t1.a between 3 and 8" } } ] } } 1 row in set (0.001 sec) {code} h2. Objection Consider a basic example with join (https://gist.github.com/spetrunia/a2f28cd0573afba20179c2a828ac8d49): {code:sql} explain select * from t1, t2 where t1.b+1<10 and t2.key2=t1.a and t2.key1 between 100 and 200; {code} {code} *************************** 1. row *************************** id: 1 select_type: SIMPLE table: t1 type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 100 Extra: Using where *************************** 2. row *************************** id: 1 select_type: SIMPLE table: t2 type: ref|filter possible_keys: key1,key2 key: key2|key1 key_len: 5|5 ref: j1.t1.a rows: 19 (1%) Extra: Using where; Using rowid filter {code} Here, we build the rowid filter once per join execution, and then it is used during all index lookups to table t2. We expect 100 lookups, each scanning 19 rows). Now, table t1 has "Using where", the condition {{t1.b+1<10}}. We don't know its selectivity. If this condition is selective, it will reduce the number of index lookups made to table t2, to the point where using Rowid Filter for table t2 will no longer bring benefit. This MDEV requests that Rowid Filter is not used with Pushed Index condition. Should Rowid Filter also be not used when it is used with ref access and the join plan has "Using where" conditions which may reduce the number of times the Rowid Filter is used? |
| Affects Version/s | 11.4 [ 29301 ] | |
| Affects Version/s | 12.0 [ 29945 ] | |
| Issue Type | Bug [ 1 ] | New Feature [ 2 ] |
| Description |
(All file and line references below are with respect to git sha {{38e420ba6e84ef6efc9c54b04ebd4dbc95dc3cae}} which was 11.4 at the time of writing.)
Range filtering is cost-based. The decision to filter is made exclusively on the cost by using selectivity and it's made during optimization, to choose the best join ordering. However, at this point in optimization, ICP is not taken into account. First, we choose some join order and then later we figure out if an index condition can be pushed. If yes, then we push it, but that is downstream of join ordering. At the same time, the selectivity of ICP can be large, so using the rowid range filters together with a large ICP selectivity might cause a slowdown: we spend time building the filter but we may not gain anything or just a little. The original approach was that if ICP is used, and although we decide we use a filter, we cancel this usage. So filtering can never be used together with ICP to access the table. Since the original implementation, other changes over time have now permitted this usage, which is not desirable. At the same time, we are not certain what is more optimal at this point: to cancel the ICP or to cancel the rowid filter. Here is an example scenario in which rowid filtering and ICP both are used: {code} create table t1 (a int, b int); insert into t1 (a, b) values (1, 1000), (2, 2000), (3, 3000), (4, 4000), (5, 5000), (6, 6000), (7, 7000), (8, 8000), (9, 9000), (10, 10000); create index t1_a on t1 (a); create index t1_b on t1 (b); set session optimizer_where_cost=10; analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G {code} If we place a breakpoint at handler.cc:7144, just before we check the pushed rowid filter, then we can see the following abriged stack trace (we can also see that h->pushed_idx_cond and h->pushed_rowid_filter both are set at this point): {code} (lldb) bt * thread #8, stop reason = breakpoint 1.1 * frame #0: 0x0000000102ab3404 mariadbd`handler_rowid_filter_check(h_arg=0x0000000156139ca8) at handler.cc:7146:3 frame #1: 0x000000010382bcc4 mariadbd`row_search_idx_cond_check(mysql_rec="\xfb", prebuilt=0x000000015613d498, rec="\x80", offsets=0x000000016d9da3b0) at row0sel.cc:4104:34 frame #2: 0x00000001038296ac mariadbd`row_search_mvcc(buf="\xfb", mode=PAGE_CUR_GE, prebuilt=0x000000015613d498, match_mode=0, direction=0) at row0sel.cc:5493:10 frame #3: 0x000000010360aa5c mariadbd`ha_innobase::index_read(this=0x0000000156139ca8, buf="\xfb", key_ptr="", key_len=5, find_flag=HA_READ_KEY_OR_NEXT) at ha_innodb.cc:9121:3 frame #4: 0x000000010338dec4 mariadbd`handler::index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.h:4190:12 frame #5: 0x0000000102aa6230 mariadbd`handler::ha_index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.cc:3792:3 frame #6: 0x0000000102ab2c9c mariadbd`handler::read_range_first(this=0x0000000156139ca8, start_key=0x0000000156139df8, end_key=0x0000000156139e18, eq_range_arg=false, sorted=true) at handler.cc:6949:13 frame #7: 0x0000000103140a08 mariadbd`handler::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at multi_range_read.cc:590:15 frame #8: 0x0000000103140ba8 mariadbd`Mrr_simple_index_reader::get_next(this=0x000000015613a340, range_info=0x000000016d9dae48) at multi_range_read.cc:627:32 frame #9: 0x0000000103143f30 mariadbd`DsMrr_impl::dsmrr_next(this=0x000000015613a1f0, range_info=0x000000016d9dae48) at multi_range_read.cc:1731:26 frame #10: 0x00000001036242cc mariadbd`ha_innobase::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at ha_innodb.cc:20301:18 frame #11: 0x0000000102d0f4ec mariadbd`QUICK_RANGE_SELECT::get_next(this=0x0000000155e14760) at opt_range.cc:13276:5 frame #12: 0x0000000102d3cc64 mariadbd`rr_quick(info=0x000000015bcc4b10) at records.cc:402:34 frame #13: 0x0000000102d0e4c0 mariadbd`READ_RECORD::read_record(this=0x000000015bcc4b10) at records.h:81:30 frame #14: 0x0000000102f42398 mariadbd`join_init_read_record(tab=0x000000015bcc4a40) at sql_select.cc:25221:27 frame #15: 0x0000000102f1e2a0 mariadbd`sub_select(join=0x000000015bcc2278, join_tab=0x000000015bcc4a40, end_of_records=false) at sql_select.cc:24153:12 frame #16: 0x0000000102f45e28 mariadbd`do_select(join=0x000000015bcc2278, procedure=0x0000000000000000) at sql_select.cc:23667:14 {code} And the corresponding analyze output to confirm: {code} MariaDB [test]> analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G *************************** 1. row *************************** ANALYZE: { "query_optimization": { "r_total_time_ms": 0.471028634 }, "query_block": { "select_id": 1, "cost": 0.012382207, "r_loops": 1, "r_total_time_ms": 0.194622362, "nested_loop": [ { "table": { "table_name": "t1", "access_type": "range", "possible_keys": ["t1_a", "t1_b"], "key": "t1_b", "key_length": "5", "used_key_parts": ["b"], "rowid_filter": { "range": { "key": "t1_a", "used_key_parts": ["a"] }, "rows": 6, "selectivity_pct": 60, "r_rows": 6, "r_lookups": 1, "r_selectivity_pct": 100, "r_buffer_size": 4, "r_filling_time_ms": 0.082075697 }, "loops": 1, "r_loops": 1, "rows": 1, "r_rows": 1, "cost": 0.012005717, "r_table_time_ms": 0.115547909, "r_other_time_ms": 0.028011614, "r_engine_stats": { "pages_accessed": 3 }, "filtered": 60, "r_filtered": 100, "index_condition": "t1.b between 4000 and 4100", "attached_condition": "t1.a between 3 and 8" } } ] } } 1 row in set (0.001 sec) {code} h2. Objection Consider a basic example with join (https://gist.github.com/spetrunia/a2f28cd0573afba20179c2a828ac8d49): {code:sql} explain select * from t1, t2 where t1.b+1<10 and t2.key2=t1.a and t2.key1 between 100 and 200; {code} {code} *************************** 1. row *************************** id: 1 select_type: SIMPLE table: t1 type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 100 Extra: Using where *************************** 2. row *************************** id: 1 select_type: SIMPLE table: t2 type: ref|filter possible_keys: key1,key2 key: key2|key1 key_len: 5|5 ref: j1.t1.a rows: 19 (1%) Extra: Using where; Using rowid filter {code} Here, we build the rowid filter once per join execution, and then it is used during all index lookups to table t2. We expect 100 lookups, each scanning 19 rows). Now, table t1 has "Using where", the condition {{t1.b+1<10}}. We don't know its selectivity. If this condition is selective, it will reduce the number of index lookups made to table t2, to the point where using Rowid Filter for table t2 will no longer bring benefit. This MDEV requests that Rowid Filter is not used with Pushed Index condition. Should Rowid Filter also be not used when it is used with ref access and the join plan has "Using where" conditions which may reduce the number of times the Rowid Filter is used? |
(All file and line references below are with respect to git sha {{38e420ba6e84ef6efc9c54b04ebd4dbc95dc3cae}} which was 11.4 at the time of writing.)
Range filtering is cost-based. The decision to filter is made exclusively on the cost by using selectivity and it's made during optimization, to choose the best join ordering. However, at this point in optimization, ICP is not taken into account. First, we choose some join order and then later we figure out if an index condition can be pushed. If yes, then we push it, but that is downstream of join ordering. At the same time, the selectivity of ICP can be large, so using the rowid range filters together with a large ICP selectivity might cause a slowdown: we spend time building the filter but we may not gain anything or just a little. The original approach was that if ICP is used, and although we decide we use a filter, we cancel this usage. So filtering can never be used together with ICP to access the table. Since the original implementation, other changes over time have now permitted this usage, which is not desirable. At the same time, we are not certain what is more optimal at this point: to cancel the ICP or to cancel the rowid filter. Here is an example scenario in which rowid filtering and ICP both are used: {code} create table t1 (a int, b int); insert into t1 (a, b) values (1, 1000), (2, 2000), (3, 3000), (4, 4000), (5, 5000), (6, 6000), (7, 7000), (8, 8000), (9, 9000), (10, 10000); create index t1_a on t1 (a); create index t1_b on t1 (b); set session optimizer_where_cost=10; analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G {code} If we place a breakpoint at handler.cc:7144, just before we check the pushed rowid filter, then we can see the following abriged stack trace (we can also see that h->pushed_idx_cond and h->pushed_rowid_filter both are set at this point): {code} (lldb) bt * thread #8, stop reason = breakpoint 1.1 * frame #0: 0x0000000102ab3404 mariadbd`handler_rowid_filter_check(h_arg=0x0000000156139ca8) at handler.cc:7146:3 frame #1: 0x000000010382bcc4 mariadbd`row_search_idx_cond_check(mysql_rec="\xfb", prebuilt=0x000000015613d498, rec="\x80", offsets=0x000000016d9da3b0) at row0sel.cc:4104:34 frame #2: 0x00000001038296ac mariadbd`row_search_mvcc(buf="\xfb", mode=PAGE_CUR_GE, prebuilt=0x000000015613d498, match_mode=0, direction=0) at row0sel.cc:5493:10 frame #3: 0x000000010360aa5c mariadbd`ha_innobase::index_read(this=0x0000000156139ca8, buf="\xfb", key_ptr="", key_len=5, find_flag=HA_READ_KEY_OR_NEXT) at ha_innodb.cc:9121:3 frame #4: 0x000000010338dec4 mariadbd`handler::index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.h:4190:12 frame #5: 0x0000000102aa6230 mariadbd`handler::ha_index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.cc:3792:3 frame #6: 0x0000000102ab2c9c mariadbd`handler::read_range_first(this=0x0000000156139ca8, start_key=0x0000000156139df8, end_key=0x0000000156139e18, eq_range_arg=false, sorted=true) at handler.cc:6949:13 frame #7: 0x0000000103140a08 mariadbd`handler::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at multi_range_read.cc:590:15 frame #8: 0x0000000103140ba8 mariadbd`Mrr_simple_index_reader::get_next(this=0x000000015613a340, range_info=0x000000016d9dae48) at multi_range_read.cc:627:32 frame #9: 0x0000000103143f30 mariadbd`DsMrr_impl::dsmrr_next(this=0x000000015613a1f0, range_info=0x000000016d9dae48) at multi_range_read.cc:1731:26 frame #10: 0x00000001036242cc mariadbd`ha_innobase::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at ha_innodb.cc:20301:18 frame #11: 0x0000000102d0f4ec mariadbd`QUICK_RANGE_SELECT::get_next(this=0x0000000155e14760) at opt_range.cc:13276:5 frame #12: 0x0000000102d3cc64 mariadbd`rr_quick(info=0x000000015bcc4b10) at records.cc:402:34 frame #13: 0x0000000102d0e4c0 mariadbd`READ_RECORD::read_record(this=0x000000015bcc4b10) at records.h:81:30 frame #14: 0x0000000102f42398 mariadbd`join_init_read_record(tab=0x000000015bcc4a40) at sql_select.cc:25221:27 frame #15: 0x0000000102f1e2a0 mariadbd`sub_select(join=0x000000015bcc2278, join_tab=0x000000015bcc4a40, end_of_records=false) at sql_select.cc:24153:12 frame #16: 0x0000000102f45e28 mariadbd`do_select(join=0x000000015bcc2278, procedure=0x0000000000000000) at sql_select.cc:23667:14 {code} And the corresponding analyze output to confirm: {code} MariaDB [test]> analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G *************************** 1. row *************************** ANALYZE: { "query_optimization": { "r_total_time_ms": 0.471028634 }, "query_block": { "select_id": 1, "cost": 0.012382207, "r_loops": 1, "r_total_time_ms": 0.194622362, "nested_loop": [ { "table": { "table_name": "t1", "access_type": "range", "possible_keys": ["t1_a", "t1_b"], "key": "t1_b", "key_length": "5", "used_key_parts": ["b"], "rowid_filter": { "range": { "key": "t1_a", "used_key_parts": ["a"] }, "rows": 6, "selectivity_pct": 60, "r_rows": 6, "r_lookups": 1, "r_selectivity_pct": 100, "r_buffer_size": 4, "r_filling_time_ms": 0.082075697 }, "loops": 1, "r_loops": 1, "rows": 1, "r_rows": 1, "cost": 0.012005717, "r_table_time_ms": 0.115547909, "r_other_time_ms": 0.028011614, "r_engine_stats": { "pages_accessed": 3 }, "filtered": 60, "r_filtered": 100, "index_condition": "t1.b between 4000 and 4100", "attached_condition": "t1.a between 3 and 8" } } ] } } 1 row in set (0.001 sec) {code} h2. 2. Objection Let's construct a similar example without ICP. h3. 2.1 Example with JOIN Consider this testcase (https://gist.github.com/spetrunia/a2f28cd0573afba20179c2a828ac8d49): {code:sql} explain select * from t1, t2 where t1.b+1<10 and t2.key2=t1.a and t2.key1 between 100 and 200; {code} {code} *************************** 1. row *************************** id: 1 select_type: SIMPLE table: t1 type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 100 Extra: Using where *************************** 2. row *************************** id: 1 select_type: SIMPLE table: t2 type: ref|filter possible_keys: key1,key2 key: key2|key1 key_len: 5|5 ref: j1.t1.a rows: 19 (1%) Extra: Using where; Using rowid filter {code} Here, we build the rowid filter once per join execution, and then it is used during all index lookups to table t2. We expect 100 lookups, each scanning 19 rows. Now, table t1 has "Using where", the condition {{t1.b+1<10}}. We don't know its selectivity. If this condition is selective, it will reduce the number of index lookups made to table t2, to the point where using Rowid Filter for table t2 will no longer bring benefit. h3. 2.2 When not to use Rowid Filter This MDEV requests that Rowid Filter is not used when selective ICP condition can make it not worth using. Should Rowid Filter also not be used when join operation and "Using where" conditions can make it not worth using? |
| Description |
(All file and line references below are with respect to git sha {{38e420ba6e84ef6efc9c54b04ebd4dbc95dc3cae}} which was 11.4 at the time of writing.)
Range filtering is cost-based. The decision to filter is made exclusively on the cost by using selectivity and it's made during optimization, to choose the best join ordering. However, at this point in optimization, ICP is not taken into account. First, we choose some join order and then later we figure out if an index condition can be pushed. If yes, then we push it, but that is downstream of join ordering. At the same time, the selectivity of ICP can be large, so using the rowid range filters together with a large ICP selectivity might cause a slowdown: we spend time building the filter but we may not gain anything or just a little. The original approach was that if ICP is used, and although we decide we use a filter, we cancel this usage. So filtering can never be used together with ICP to access the table. Since the original implementation, other changes over time have now permitted this usage, which is not desirable. At the same time, we are not certain what is more optimal at this point: to cancel the ICP or to cancel the rowid filter. Here is an example scenario in which rowid filtering and ICP both are used: {code} create table t1 (a int, b int); insert into t1 (a, b) values (1, 1000), (2, 2000), (3, 3000), (4, 4000), (5, 5000), (6, 6000), (7, 7000), (8, 8000), (9, 9000), (10, 10000); create index t1_a on t1 (a); create index t1_b on t1 (b); set session optimizer_where_cost=10; analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G {code} If we place a breakpoint at handler.cc:7144, just before we check the pushed rowid filter, then we can see the following abriged stack trace (we can also see that h->pushed_idx_cond and h->pushed_rowid_filter both are set at this point): {code} (lldb) bt * thread #8, stop reason = breakpoint 1.1 * frame #0: 0x0000000102ab3404 mariadbd`handler_rowid_filter_check(h_arg=0x0000000156139ca8) at handler.cc:7146:3 frame #1: 0x000000010382bcc4 mariadbd`row_search_idx_cond_check(mysql_rec="\xfb", prebuilt=0x000000015613d498, rec="\x80", offsets=0x000000016d9da3b0) at row0sel.cc:4104:34 frame #2: 0x00000001038296ac mariadbd`row_search_mvcc(buf="\xfb", mode=PAGE_CUR_GE, prebuilt=0x000000015613d498, match_mode=0, direction=0) at row0sel.cc:5493:10 frame #3: 0x000000010360aa5c mariadbd`ha_innobase::index_read(this=0x0000000156139ca8, buf="\xfb", key_ptr="", key_len=5, find_flag=HA_READ_KEY_OR_NEXT) at ha_innodb.cc:9121:3 frame #4: 0x000000010338dec4 mariadbd`handler::index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.h:4190:12 frame #5: 0x0000000102aa6230 mariadbd`handler::ha_index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.cc:3792:3 frame #6: 0x0000000102ab2c9c mariadbd`handler::read_range_first(this=0x0000000156139ca8, start_key=0x0000000156139df8, end_key=0x0000000156139e18, eq_range_arg=false, sorted=true) at handler.cc:6949:13 frame #7: 0x0000000103140a08 mariadbd`handler::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at multi_range_read.cc:590:15 frame #8: 0x0000000103140ba8 mariadbd`Mrr_simple_index_reader::get_next(this=0x000000015613a340, range_info=0x000000016d9dae48) at multi_range_read.cc:627:32 frame #9: 0x0000000103143f30 mariadbd`DsMrr_impl::dsmrr_next(this=0x000000015613a1f0, range_info=0x000000016d9dae48) at multi_range_read.cc:1731:26 frame #10: 0x00000001036242cc mariadbd`ha_innobase::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at ha_innodb.cc:20301:18 frame #11: 0x0000000102d0f4ec mariadbd`QUICK_RANGE_SELECT::get_next(this=0x0000000155e14760) at opt_range.cc:13276:5 frame #12: 0x0000000102d3cc64 mariadbd`rr_quick(info=0x000000015bcc4b10) at records.cc:402:34 frame #13: 0x0000000102d0e4c0 mariadbd`READ_RECORD::read_record(this=0x000000015bcc4b10) at records.h:81:30 frame #14: 0x0000000102f42398 mariadbd`join_init_read_record(tab=0x000000015bcc4a40) at sql_select.cc:25221:27 frame #15: 0x0000000102f1e2a0 mariadbd`sub_select(join=0x000000015bcc2278, join_tab=0x000000015bcc4a40, end_of_records=false) at sql_select.cc:24153:12 frame #16: 0x0000000102f45e28 mariadbd`do_select(join=0x000000015bcc2278, procedure=0x0000000000000000) at sql_select.cc:23667:14 {code} And the corresponding analyze output to confirm: {code} MariaDB [test]> analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G *************************** 1. row *************************** ANALYZE: { "query_optimization": { "r_total_time_ms": 0.471028634 }, "query_block": { "select_id": 1, "cost": 0.012382207, "r_loops": 1, "r_total_time_ms": 0.194622362, "nested_loop": [ { "table": { "table_name": "t1", "access_type": "range", "possible_keys": ["t1_a", "t1_b"], "key": "t1_b", "key_length": "5", "used_key_parts": ["b"], "rowid_filter": { "range": { "key": "t1_a", "used_key_parts": ["a"] }, "rows": 6, "selectivity_pct": 60, "r_rows": 6, "r_lookups": 1, "r_selectivity_pct": 100, "r_buffer_size": 4, "r_filling_time_ms": 0.082075697 }, "loops": 1, "r_loops": 1, "rows": 1, "r_rows": 1, "cost": 0.012005717, "r_table_time_ms": 0.115547909, "r_other_time_ms": 0.028011614, "r_engine_stats": { "pages_accessed": 3 }, "filtered": 60, "r_filtered": 100, "index_condition": "t1.b between 4000 and 4100", "attached_condition": "t1.a between 3 and 8" } } ] } } 1 row in set (0.001 sec) {code} h2. 2. Objection Let's construct a similar example without ICP. h3. 2.1 Example with JOIN Consider this testcase (https://gist.github.com/spetrunia/a2f28cd0573afba20179c2a828ac8d49): {code:sql} explain select * from t1, t2 where t1.b+1<10 and t2.key2=t1.a and t2.key1 between 100 and 200; {code} {code} *************************** 1. row *************************** id: 1 select_type: SIMPLE table: t1 type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 100 Extra: Using where *************************** 2. row *************************** id: 1 select_type: SIMPLE table: t2 type: ref|filter possible_keys: key1,key2 key: key2|key1 key_len: 5|5 ref: j1.t1.a rows: 19 (1%) Extra: Using where; Using rowid filter {code} Here, we build the rowid filter once per join execution, and then it is used during all index lookups to table t2. We expect 100 lookups, each scanning 19 rows. Now, table t1 has "Using where", the condition {{t1.b+1<10}}. We don't know its selectivity. If this condition is selective, it will reduce the number of index lookups made to table t2, to the point where using Rowid Filter for table t2 will no longer bring benefit. h3. 2.2 When not to use Rowid Filter This MDEV requests that Rowid Filter is not used when selective ICP condition can make it not worth using. Should Rowid Filter also not be used when join operation and "Using where" conditions can make it not worth using? |
(All file and line references below are with respect to git sha {{38e420ba6e84ef6efc9c54b04ebd4dbc95dc3cae}} which was 11.4 at the time of writing.)
Range filtering is cost-based. The decision to filter is made exclusively on the cost by using selectivity and it's made during optimization, to choose the best join ordering. However, at this point in optimization, ICP is not taken into account. First, we choose some join order and then later we figure out if an index condition can be pushed. If yes, then we push it, but that is downstream of join ordering. At the same time, the selectivity of ICP can be large, so using the rowid range filters together with a large ICP selectivity might cause a slowdown: we spend time building the filter but we may not gain anything or just a little. The original approach was that if ICP is used, and although we decide we use a filter, we cancel this usage. So filtering can never be used together with ICP to access the table. Since the original implementation, other changes over time have now permitted this usage, which is not desirable. At the same time, we are not certain what is more optimal at this point: to cancel the ICP or to cancel the rowid filter. Here is an example scenario in which rowid filtering and ICP both are used: {code} create table t1 (a int, b int); insert into t1 (a, b) values (1, 1000), (2, 2000), (3, 3000), (4, 4000), (5, 5000), (6, 6000), (7, 7000), (8, 8000), (9, 9000), (10, 10000); create index t1_a on t1 (a); create index t1_b on t1 (b); set session optimizer_where_cost=10; analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G {code} If we place a breakpoint at handler.cc:7144, just before we check the pushed rowid filter, then we can see the following abriged stack trace (we can also see that h->pushed_idx_cond and h->pushed_rowid_filter both are set at this point): {code} (lldb) bt * thread #8, stop reason = breakpoint 1.1 * frame #0: 0x0000000102ab3404 mariadbd`handler_rowid_filter_check(h_arg=0x0000000156139ca8) at handler.cc:7146:3 frame #1: 0x000000010382bcc4 mariadbd`row_search_idx_cond_check(mysql_rec="\xfb", prebuilt=0x000000015613d498, rec="\x80", offsets=0x000000016d9da3b0) at row0sel.cc:4104:34 frame #2: 0x00000001038296ac mariadbd`row_search_mvcc(buf="\xfb", mode=PAGE_CUR_GE, prebuilt=0x000000015613d498, match_mode=0, direction=0) at row0sel.cc:5493:10 frame #3: 0x000000010360aa5c mariadbd`ha_innobase::index_read(this=0x0000000156139ca8, buf="\xfb", key_ptr="", key_len=5, find_flag=HA_READ_KEY_OR_NEXT) at ha_innodb.cc:9121:3 frame #4: 0x000000010338dec4 mariadbd`handler::index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.h:4190:12 frame #5: 0x0000000102aa6230 mariadbd`handler::ha_index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.cc:3792:3 frame #6: 0x0000000102ab2c9c mariadbd`handler::read_range_first(this=0x0000000156139ca8, start_key=0x0000000156139df8, end_key=0x0000000156139e18, eq_range_arg=false, sorted=true) at handler.cc:6949:13 frame #7: 0x0000000103140a08 mariadbd`handler::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at multi_range_read.cc:590:15 frame #8: 0x0000000103140ba8 mariadbd`Mrr_simple_index_reader::get_next(this=0x000000015613a340, range_info=0x000000016d9dae48) at multi_range_read.cc:627:32 frame #9: 0x0000000103143f30 mariadbd`DsMrr_impl::dsmrr_next(this=0x000000015613a1f0, range_info=0x000000016d9dae48) at multi_range_read.cc:1731:26 frame #10: 0x00000001036242cc mariadbd`ha_innobase::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at ha_innodb.cc:20301:18 frame #11: 0x0000000102d0f4ec mariadbd`QUICK_RANGE_SELECT::get_next(this=0x0000000155e14760) at opt_range.cc:13276:5 frame #12: 0x0000000102d3cc64 mariadbd`rr_quick(info=0x000000015bcc4b10) at records.cc:402:34 frame #13: 0x0000000102d0e4c0 mariadbd`READ_RECORD::read_record(this=0x000000015bcc4b10) at records.h:81:30 frame #14: 0x0000000102f42398 mariadbd`join_init_read_record(tab=0x000000015bcc4a40) at sql_select.cc:25221:27 frame #15: 0x0000000102f1e2a0 mariadbd`sub_select(join=0x000000015bcc2278, join_tab=0x000000015bcc4a40, end_of_records=false) at sql_select.cc:24153:12 frame #16: 0x0000000102f45e28 mariadbd`do_select(join=0x000000015bcc2278, procedure=0x0000000000000000) at sql_select.cc:23667:14 {code} And the corresponding analyze output to confirm: {code} MariaDB [test]> analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G *************************** 1. row *************************** ANALYZE: { "query_optimization": { "r_total_time_ms": 0.471028634 }, "query_block": { "select_id": 1, "cost": 0.012382207, "r_loops": 1, "r_total_time_ms": 0.194622362, "nested_loop": [ { "table": { "table_name": "t1", "access_type": "range", "possible_keys": ["t1_a", "t1_b"], "key": "t1_b", "key_length": "5", "used_key_parts": ["b"], "rowid_filter": { "range": { "key": "t1_a", "used_key_parts": ["a"] }, "rows": 6, "selectivity_pct": 60, "r_rows": 6, "r_lookups": 1, "r_selectivity_pct": 100, "r_buffer_size": 4, "r_filling_time_ms": 0.082075697 }, "loops": 1, "r_loops": 1, "rows": 1, "r_rows": 1, "cost": 0.012005717, "r_table_time_ms": 0.115547909, "r_other_time_ms": 0.028011614, "r_engine_stats": { "pages_accessed": 3 }, "filtered": 60, "r_filtered": 100, "index_condition": "t1.b between 4000 and 4100", "attached_condition": "t1.a between 3 and 8" } } ] } } 1 row in set (0.001 sec) {code} h2. 2. Objection Let's construct a similar example without ICP. h3. 2.1 Example with JOIN Consider this testcase (https://gist.github.com/spetrunia/a2f28cd0573afba20179c2a828ac8d49): {code:sql} explain select * from t1, t2 where t1.b+1<10 and t2.key2=t1.a and t2.key1 between 100 and 200; {code} {code} *************************** 1. row *************************** id: 1 select_type: SIMPLE table: t1 type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 100 Extra: Using where *************************** 2. row *************************** id: 1 select_type: SIMPLE table: t2 type: ref|filter possible_keys: key1,key2 key: key2|key1 key_len: 5|5 ref: j1.t1.a rows: 19 (1%) Extra: Using where; Using rowid filter {code} Here, we build the rowid filter once per join execution, and then it is used during all index lookups to table t2. We expect 100 lookups, each scanning 19 rows. Now, table t1 has "Using where", the condition {{t1.b+1<10}}. We don't know its selectivity. If this condition is selective, it will reduce the number of index lookups made to table t2, to the point where using Rowid Filter for table t2 will no longer bring benefit. h3. 2.2 When not to use Rowid Filter This MDEV requests that Rowid Filter is not used when selective ICP condition can make it not worth using. Should Rowid Filter also not be used when join operation and "Using where" conditions can make it not worth using? If the answer is Yes, then we would need to disable use of Rowid Filter in most of the cases where it is currently used... |
| Description |
(All file and line references below are with respect to git sha {{38e420ba6e84ef6efc9c54b04ebd4dbc95dc3cae}} which was 11.4 at the time of writing.)
Range filtering is cost-based. The decision to filter is made exclusively on the cost by using selectivity and it's made during optimization, to choose the best join ordering. However, at this point in optimization, ICP is not taken into account. First, we choose some join order and then later we figure out if an index condition can be pushed. If yes, then we push it, but that is downstream of join ordering. At the same time, the selectivity of ICP can be large, so using the rowid range filters together with a large ICP selectivity might cause a slowdown: we spend time building the filter but we may not gain anything or just a little. The original approach was that if ICP is used, and although we decide we use a filter, we cancel this usage. So filtering can never be used together with ICP to access the table. Since the original implementation, other changes over time have now permitted this usage, which is not desirable. At the same time, we are not certain what is more optimal at this point: to cancel the ICP or to cancel the rowid filter. Here is an example scenario in which rowid filtering and ICP both are used: {code} create table t1 (a int, b int); insert into t1 (a, b) values (1, 1000), (2, 2000), (3, 3000), (4, 4000), (5, 5000), (6, 6000), (7, 7000), (8, 8000), (9, 9000), (10, 10000); create index t1_a on t1 (a); create index t1_b on t1 (b); set session optimizer_where_cost=10; analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G {code} If we place a breakpoint at handler.cc:7144, just before we check the pushed rowid filter, then we can see the following abriged stack trace (we can also see that h->pushed_idx_cond and h->pushed_rowid_filter both are set at this point): {code} (lldb) bt * thread #8, stop reason = breakpoint 1.1 * frame #0: 0x0000000102ab3404 mariadbd`handler_rowid_filter_check(h_arg=0x0000000156139ca8) at handler.cc:7146:3 frame #1: 0x000000010382bcc4 mariadbd`row_search_idx_cond_check(mysql_rec="\xfb", prebuilt=0x000000015613d498, rec="\x80", offsets=0x000000016d9da3b0) at row0sel.cc:4104:34 frame #2: 0x00000001038296ac mariadbd`row_search_mvcc(buf="\xfb", mode=PAGE_CUR_GE, prebuilt=0x000000015613d498, match_mode=0, direction=0) at row0sel.cc:5493:10 frame #3: 0x000000010360aa5c mariadbd`ha_innobase::index_read(this=0x0000000156139ca8, buf="\xfb", key_ptr="", key_len=5, find_flag=HA_READ_KEY_OR_NEXT) at ha_innodb.cc:9121:3 frame #4: 0x000000010338dec4 mariadbd`handler::index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.h:4190:12 frame #5: 0x0000000102aa6230 mariadbd`handler::ha_index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.cc:3792:3 frame #6: 0x0000000102ab2c9c mariadbd`handler::read_range_first(this=0x0000000156139ca8, start_key=0x0000000156139df8, end_key=0x0000000156139e18, eq_range_arg=false, sorted=true) at handler.cc:6949:13 frame #7: 0x0000000103140a08 mariadbd`handler::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at multi_range_read.cc:590:15 frame #8: 0x0000000103140ba8 mariadbd`Mrr_simple_index_reader::get_next(this=0x000000015613a340, range_info=0x000000016d9dae48) at multi_range_read.cc:627:32 frame #9: 0x0000000103143f30 mariadbd`DsMrr_impl::dsmrr_next(this=0x000000015613a1f0, range_info=0x000000016d9dae48) at multi_range_read.cc:1731:26 frame #10: 0x00000001036242cc mariadbd`ha_innobase::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at ha_innodb.cc:20301:18 frame #11: 0x0000000102d0f4ec mariadbd`QUICK_RANGE_SELECT::get_next(this=0x0000000155e14760) at opt_range.cc:13276:5 frame #12: 0x0000000102d3cc64 mariadbd`rr_quick(info=0x000000015bcc4b10) at records.cc:402:34 frame #13: 0x0000000102d0e4c0 mariadbd`READ_RECORD::read_record(this=0x000000015bcc4b10) at records.h:81:30 frame #14: 0x0000000102f42398 mariadbd`join_init_read_record(tab=0x000000015bcc4a40) at sql_select.cc:25221:27 frame #15: 0x0000000102f1e2a0 mariadbd`sub_select(join=0x000000015bcc2278, join_tab=0x000000015bcc4a40, end_of_records=false) at sql_select.cc:24153:12 frame #16: 0x0000000102f45e28 mariadbd`do_select(join=0x000000015bcc2278, procedure=0x0000000000000000) at sql_select.cc:23667:14 {code} And the corresponding analyze output to confirm: {code} MariaDB [test]> analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G *************************** 1. row *************************** ANALYZE: { "query_optimization": { "r_total_time_ms": 0.471028634 }, "query_block": { "select_id": 1, "cost": 0.012382207, "r_loops": 1, "r_total_time_ms": 0.194622362, "nested_loop": [ { "table": { "table_name": "t1", "access_type": "range", "possible_keys": ["t1_a", "t1_b"], "key": "t1_b", "key_length": "5", "used_key_parts": ["b"], "rowid_filter": { "range": { "key": "t1_a", "used_key_parts": ["a"] }, "rows": 6, "selectivity_pct": 60, "r_rows": 6, "r_lookups": 1, "r_selectivity_pct": 100, "r_buffer_size": 4, "r_filling_time_ms": 0.082075697 }, "loops": 1, "r_loops": 1, "rows": 1, "r_rows": 1, "cost": 0.012005717, "r_table_time_ms": 0.115547909, "r_other_time_ms": 0.028011614, "r_engine_stats": { "pages_accessed": 3 }, "filtered": 60, "r_filtered": 100, "index_condition": "t1.b between 4000 and 4100", "attached_condition": "t1.a between 3 and 8" } } ] } } 1 row in set (0.001 sec) {code} h2. 2. Objection Let's construct a similar example without ICP. h3. 2.1 Example with JOIN Consider this testcase (https://gist.github.com/spetrunia/a2f28cd0573afba20179c2a828ac8d49): {code:sql} explain select * from t1, t2 where t1.b+1<10 and t2.key2=t1.a and t2.key1 between 100 and 200; {code} {code} *************************** 1. row *************************** id: 1 select_type: SIMPLE table: t1 type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 100 Extra: Using where *************************** 2. row *************************** id: 1 select_type: SIMPLE table: t2 type: ref|filter possible_keys: key1,key2 key: key2|key1 key_len: 5|5 ref: j1.t1.a rows: 19 (1%) Extra: Using where; Using rowid filter {code} Here, we build the rowid filter once per join execution, and then it is used during all index lookups to table t2. We expect 100 lookups, each scanning 19 rows. Now, table t1 has "Using where", the condition {{t1.b+1<10}}. We don't know its selectivity. If this condition is selective, it will reduce the number of index lookups made to table t2, to the point where using Rowid Filter for table t2 will no longer bring benefit. h3. 2.2 When not to use Rowid Filter This MDEV requests that Rowid Filter is not used when selective ICP condition can make it not worth using. Should Rowid Filter also not be used when join operation and "Using where" conditions can make it not worth using? If the answer is Yes, then we would need to disable use of Rowid Filter in most of the cases where it is currently used... |
(All file and line references below are with respect to git sha {{38e420ba6e84ef6efc9c54b04ebd4dbc95dc3cae}} which was 11.4 at the time of writing.)
Range filtering is cost-based. The decision to filter is made exclusively on the cost by using selectivity and it's made during optimization, to choose the best join ordering. However, at this point in optimization, ICP is not taken into account. First, we choose some join order and then later we figure out if an index condition can be pushed. If yes, then we push it, but that is downstream of join ordering. At the same time, the selectivity of ICP can be large, so using the rowid range filters together with a large ICP selectivity might cause a slowdown: we spend time building the filter but we may not gain anything or just a little. The original approach was that if ICP is used, and although we decide we use a filter, we cancel this usage. So filtering can never be used together with ICP to access the table. Since the original implementation, other changes over time have now permitted this usage, which is not desirable. At the same time, we are not certain what is more optimal at this point: to cancel the ICP or to cancel the rowid filter. Here is an example scenario in which rowid filtering and ICP both are used: {code} create table t1 (a int, b int); insert into t1 (a, b) values (1, 1000), (2, 2000), (3, 3000), (4, 4000), (5, 5000), (6, 6000), (7, 7000), (8, 8000), (9, 9000), (10, 10000); create index t1_a on t1 (a); create index t1_b on t1 (b); set session optimizer_where_cost=10; analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G {code} If we place a breakpoint at handler.cc:7144, just before we check the pushed rowid filter, then we can see the following abriged stack trace (we can also see that h->pushed_idx_cond and h->pushed_rowid_filter both are set at this point): {code} (lldb) bt * thread #8, stop reason = breakpoint 1.1 * frame #0: 0x0000000102ab3404 mariadbd`handler_rowid_filter_check(h_arg=0x0000000156139ca8) at handler.cc:7146:3 frame #1: 0x000000010382bcc4 mariadbd`row_search_idx_cond_check(mysql_rec="\xfb", prebuilt=0x000000015613d498, rec="\x80", offsets=0x000000016d9da3b0) at row0sel.cc:4104:34 frame #2: 0x00000001038296ac mariadbd`row_search_mvcc(buf="\xfb", mode=PAGE_CUR_GE, prebuilt=0x000000015613d498, match_mode=0, direction=0) at row0sel.cc:5493:10 frame #3: 0x000000010360aa5c mariadbd`ha_innobase::index_read(this=0x0000000156139ca8, buf="\xfb", key_ptr="", key_len=5, find_flag=HA_READ_KEY_OR_NEXT) at ha_innodb.cc:9121:3 frame #4: 0x000000010338dec4 mariadbd`handler::index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.h:4190:12 frame #5: 0x0000000102aa6230 mariadbd`handler::ha_index_read_map(this=0x0000000156139ca8, buf="\xfb", key="", keypart_map=1, find_flag=HA_READ_KEY_OR_NEXT) at handler.cc:3792:3 frame #6: 0x0000000102ab2c9c mariadbd`handler::read_range_first(this=0x0000000156139ca8, start_key=0x0000000156139df8, end_key=0x0000000156139e18, eq_range_arg=false, sorted=true) at handler.cc:6949:13 frame #7: 0x0000000103140a08 mariadbd`handler::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at multi_range_read.cc:590:15 frame #8: 0x0000000103140ba8 mariadbd`Mrr_simple_index_reader::get_next(this=0x000000015613a340, range_info=0x000000016d9dae48) at multi_range_read.cc:627:32 frame #9: 0x0000000103143f30 mariadbd`DsMrr_impl::dsmrr_next(this=0x000000015613a1f0, range_info=0x000000016d9dae48) at multi_range_read.cc:1731:26 frame #10: 0x00000001036242cc mariadbd`ha_innobase::multi_range_read_next(this=0x0000000156139ca8, range_info=0x000000016d9dae48) at ha_innodb.cc:20301:18 frame #11: 0x0000000102d0f4ec mariadbd`QUICK_RANGE_SELECT::get_next(this=0x0000000155e14760) at opt_range.cc:13276:5 frame #12: 0x0000000102d3cc64 mariadbd`rr_quick(info=0x000000015bcc4b10) at records.cc:402:34 frame #13: 0x0000000102d0e4c0 mariadbd`READ_RECORD::read_record(this=0x000000015bcc4b10) at records.h:81:30 frame #14: 0x0000000102f42398 mariadbd`join_init_read_record(tab=0x000000015bcc4a40) at sql_select.cc:25221:27 frame #15: 0x0000000102f1e2a0 mariadbd`sub_select(join=0x000000015bcc2278, join_tab=0x000000015bcc4a40, end_of_records=false) at sql_select.cc:24153:12 frame #16: 0x0000000102f45e28 mariadbd`do_select(join=0x000000015bcc2278, procedure=0x0000000000000000) at sql_select.cc:23667:14 {code} And the corresponding analyze output to confirm: {code} MariaDB [test]> analyze format=json select * from t1 where t1.a between 3 and 8 and t1.b between 4000 and 4100 order by t1.b\G *************************** 1. row *************************** ANALYZE: { "query_optimization": { "r_total_time_ms": 0.471028634 }, "query_block": { "select_id": 1, "cost": 0.012382207, "r_loops": 1, "r_total_time_ms": 0.194622362, "nested_loop": [ { "table": { "table_name": "t1", "access_type": "range", "possible_keys": ["t1_a", "t1_b"], "key": "t1_b", "key_length": "5", "used_key_parts": ["b"], "rowid_filter": { "range": { "key": "t1_a", "used_key_parts": ["a"] }, "rows": 6, "selectivity_pct": 60, "r_rows": 6, "r_lookups": 1, "r_selectivity_pct": 100, "r_buffer_size": 4, "r_filling_time_ms": 0.082075697 }, "loops": 1, "r_loops": 1, "rows": 1, "r_rows": 1, "cost": 0.012005717, "r_table_time_ms": 0.115547909, "r_other_time_ms": 0.028011614, "r_engine_stats": { "pages_accessed": 3 }, "filtered": 60, "r_filtered": 100, "index_condition": "t1.b between 4000 and 4100", "attached_condition": "t1.a between 3 and 8" } } ] } } 1 row in set (0.001 sec) {code} h2. 2. Objection One can construct similar cases with e.g. join operation: h3. 2.1 Example with JOIN Consider this testcase (https://gist.github.com/spetrunia/a2f28cd0573afba20179c2a828ac8d49): {code:sql} explain select * from t1, t2 where t1.b+1<10 and t2.key2=t1.a and t2.key1 between 100 and 200; {code} {code} *************************** 1. row *************************** id: 1 select_type: SIMPLE table: t1 type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 100 Extra: Using where *************************** 2. row *************************** id: 1 select_type: SIMPLE table: t2 type: ref|filter possible_keys: key1,key2 key: key2|key1 key_len: 5|5 ref: j1.t1.a rows: 19 (1%) Extra: Using where; Using rowid filter {code} Here, we build the rowid filter once per join execution, and then it is used during all index lookups to table t2. We expect 100 lookups, each scanning 19 rows. Now, table t1 has "Using where", the condition {{t1.b+1<10}}. We don't know its selectivity. If this condition is selective, it will reduce the number of index lookups made to table t2, to the point where using Rowid Filter for table t2 will no longer bring benefit. h3. 2.2 When not to use Rowid Filter - too many cases? This MDEV requests that Rowid Filter is not used when selective ICP condition can make it not worth using. Should Rowid Filter also not be used when join operation and "Using where" conditions can make it not worth using? If the answer is Yes, then we would need to disable use of Rowid Filter in most of the cases where it is currently used... |
Relevant follow-up question from psergei: "I'm wondering if the logic that ICP should not work with rowid filter can be also extended that joins with "using where" should not work with rowid filter?"