pingcap / pingcap/tidb

Non optimal behavior of composite index first column range query

Open
#39,021 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

type/feature-request
Dominant language
Go
Stars
40.6k
Forks
6.2k
PR merge metrics
PR metrics pending

Description

Feature Request

Is your feature request related to a problem? Please describe:

Describe the feature you'd like:

When using the composite index, the range condition on the first column and the equal condition on the second column, we can filter more rows through the second column on the index range scan

tidb:
1.index range scan: id range[1,3]
2.filter:id2=2


create table test7(id int,id2 int,id3 int,key ind_test7(id,id2));
insert into test7 values(1,1,1),(1,2,1),(1,3,1),(1,4,1),(2,1,1),(2,2,1),(2,3,1),(2,4,1),(3,1,1),(3,2,1),(3,3,1),(3,4,1),(4,1,1),(4,2,1),(4,3,1),(4,4,1);
analyze table test7;
select * from test7 order by id,id2;
+------+------+------+
| id   | id2  | id3  |
+------+------+------+
|    1 |    1 |    1 |
|    1 |    2 |    1 |
|    1 |    3 |    1 |
|    1 |    4 |    1 |
|    2 |    1 |    1 |
|    2 |    2 |    1 |
|    2 |    3 |    1 |
|    2 |    4 |    1 |
|    3 |    1 |    1 |
|    3 |    2 |    1 |
|    3 |    3 |    1 |
|    3 |    4 |    1 |
|    4 |    1 |    1 |
|    4 |    2 |    1 |
|    4 |    3 |    1 |
|    4 |    4 |    1 |
+------+------+------+
16 rows in set (0.00 sec)

explain analyze select * from test7 where id between 1 and 3 and id2=2;
+-------------------------------+---------+---------+-----------+---------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------+---------+------+
| id                            | estRows | actRows | task      | access object                         | execution info                                                                                                                                                                                                                                                                                                                                                                                              | operator info                 | memory  | disk |
+-------------------------------+---------+---------+-----------+---------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------+---------+------+
| IndexLookUp_11                | 0.01    | 3       | root      |                                       | time:3.66ms, loops:2, index_task: {total_time: 2.24ms, fetch_handle: 2.23ms, build: 1.43µs, wait: 11.6µs}, table_task: {total_time: 1.22ms, num: 1, concurrency: 5}                                                                                                                                                                                                                                         |                               | 9.16 KB | N/A  |
| ├─Selection_10(Build)         | 0.01    | 3       | cop[tikv] |                                       | time:2.22ms, loops:3, cop_task: {num: 1, max: 2.08ms, proc_keys: 12, tot_proc: 1ms, tot_wait: 1ms, rpc_num: 1, rpc_time: 2.05ms, copr_cache_hit_ratio: 0.00}, tikv_task:{time:1ms, loops:1}, scan_detail: {total_process_keys: 12, total_process_keys_size: 660, total_keys: 13, rocksdb: {delete_skipped_count: 0, key_skipped_count: 12, block: {cache_hit_count: 1, read_count: 0, read_byte: 0 Bytes}}} | eq(test.test7.id2, 2)         | N/A     | N/A  |
| │ └─IndexRangeScan_8          | 12.00   | 12      | cop[tikv] | table:test7, index:ind_test7(id, id2) | tikv_task:{time:1ms, loops:1}                                                                                                                                                                                                                                                                                                                                                                               | range:[1,3], keep order:false | N/A     | N/A  |
| └─TableRowIDScan_9(Probe)     | 0.01    | 3       | cop[tikv] | table:test7                           | time:1.08ms, loops:2, cop_task: {num: 1, max: 1.01ms, proc_keys: 3, rpc_num: 1, rpc_time: 996.5µs, copr_cache_hit_ratio: 0.00}, tikv_task:{time:0s, loops:1}, scan_detail: {total_process_keys: 3, total_process_keys_size: 135, total_keys: 3, rocksdb: {delete_skipped_count: 0, key_skipped_count: 0, block: {cache_hit_count: 4, read_count: 0, read_byte: 0 Bytes}}}                                   | keep order:false              | N/A     | N/A  |
+-------------------------------+---------+---------+-----------+---------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------+---------+------+
4 rows in set (0.01 sec)

oracle(db2、ob、etc):
1.index range scan: id,id2 range[(1,2),(3,2)]
2.filter:id2=2

create table test7(id number,id2 number,id3 number);
create index ind_test7 on test7(id,id2);
insert into test7 values(1,1,1);(1,2,1)
insert all 
into test7 values (1,1,1)
into test7 values (1,2,1)
into test7 values (1,3,1)
into test7 values (1,4,1)
into test7 values (2,1,1)
into test7 values (2,2,1)
into test7 values (2,3,1)
into test7 values (2,4,1)
into test7 values (3,1,1)
into test7 values (3,2,1)
into test7 values (3,3,1)
into test7 values (3,4,1)
into test7 values (4,1,1)
into test7 values (4,2,1)
into test7 values (4,3,1)
into test7 values (4,4,1)
select 1 from dual;
commit;
exec dbms_stats.gather_table_stats('TEST','TEST7');
alter session set statistics_level=all;

select * from test7 where id between 1 and 3 and id2=2;

	ID	  ID2	     ID3
---------- ---------- ----------
	 1	    2	       1
	 2	    2	       1
	 3	    2	       1

select * from table(dbms_xplan.display_cursor(null,null,'ALLSTATS LAST'));

PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
SQL_ID	dr53yqrfd37y7, child number 0
-------------------------------------
select * from test7 where id between 1 and 3 and id2=2

Plan hash value: 1962590959

-----------------------------------------------------------------------------------------------------------
| Id  | Operation			    | Name	| Starts | E-Rows | A-Rows |   A-Time	| Buffers |
-----------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT		    |		|      1 |	  |	 3 |00:00:00.01 |	4 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| TEST7	|      1 |	4 |	 3 |00:00:00.01 |	4 |
|*  2 |   INDEX RANGE SCAN		    | IND_TEST7 |      1 |	4 |	 3 |00:00:00.01 |	2 |
-----------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("ID">=1 AND "ID2"=2 AND "ID"<=3)
       filter("ID2"=2)

Describe alternatives you've considered:

Teachability, Documentation, Adoption, Migration Strategy:
In the production environment, it is sometimes necessary to query on the first column range condition and second column equal condition.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

The issue names no source files, tests, or entry points. Start by reproducing the SQL example and comparing TiDB's EXPLAIN ANALYZE output with the stated Oracle behavior. Done should mean the composite index range uses both the first-column range and second-column equality predicate, with regression coverage for the example.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
databases
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.