MySQL Bugs: #26511: A composite index prefix is used when all of the key

Bug #26511	A composite index prefix is used when all of the key_len could be used.
Submitted:	20 Feb 2007 22:47	Modified:	17 Aug 2007 20:05
Reporter:	Sean Pringle	Email Updates:
Status:	Verified	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S4 (Feature request)
Version:	4.0, 4.1, 5.0, 5.1	OS:	Any
Assigned to:		CPU Architecture:	Any

Description:
A prefix of a composite index is used when all of the index could be used for a query.  In some cases, this optimizer choice is not desirable.

How to repeat:
-- Below is an example;  while in explain 3 the range examines more
-- rows than the equivalent ref in explain 2 in this case, this merely
-- demonstrates the full key_len in use.

create table t1 (i int primary key, o int);

create table t2 (j int, d Date);
create index x2 on t2(j, d);

insert into t1 values (1,1), (2,2), (3,3), (4,4);
insert into t2 values (1, '2007-01-01');
insert into t2 values (2, '2007-01-02');
insert into t2 values (3, '2007-01-03');
insert into t2 values (4, '2007-01-04');
insert into t2 select * from t2;
insert into t2 select * from t2;
insert into t2 select * from t2;
insert into t2 select * from t2;
insert into t2 select * from t2;
insert into t2 select * from t2;
insert into t2 select * from t2;
insert into t2 select * from t2;

analyze table t1;
analyze table t2;

-- Query uses single column index. This query is only done to show that
-- key_len=5 when the predicate uses a single column index.

explain select t2.j from t1, t2
where
t1.i = t2.j and
t1.o = 3 ;

> table type possible_keys key key_len ref rows Extra
> t1 ALL PRIMARY NULL NULL NULL 4 Using where
> t2 ref x1,x2 x1 5 t1.i 256 Using where; Using index

-- This is the problem query.  Note key_len for t2, only the prefix of
-- the index is used.  The predicate on t2.d is not used for the index
-- access.  In our usage, many rows can be filtered were the predicate
-- on t2.d used to access the index.

explain select t2.j from t1, t2
where
t1.i = t2.j and
t1.o = 3 and
t2.d > '2007-01-01' and t2.d < '2007-01-10';

> table type possible_keys key key_len ref rows Extra
> t1 ALL PRIMARY NULL NULL NULL 4 Using where
> t2 ref x1,x2 x2 5 t1.i 256 Using where; Using index

-- This query is done to demonstrate that MySQL can use an index
-- an equality predicate on the first indexed column and a range
-- predicate on the second indexed column.

explain select * from t2 where j = 3 and d > '2007-01-01' and d < '2007-01-10';

> table type possible_keys key key_len ref rows Extra
> t2 range x1,x2 x2 9 NULL 287 Using where; Using index

- This is feature request.
- Serious development is needed for this optimization (~ 4 man-months)

By the above reasons I move the bug to 'To be fixed later'.
Product management will decide in what version this optimization appears.

-- SUMMARY
Main point of this post is to show that FULL index *IS* used
when "equal" is used instead of range on the second column of the
composite index.

-- OTHER NOTES/FEEDBACK: 
a) Number of rows on joined tables does not affect the result.
   On production server there is 8k x 500K rows and the following
   example has only 2 x 6 rows: Result is the same.
b) Happens with other data types (integer, timestamp);
   it is not related to datetime.
c) Problem appears even if the composite index is UNIQUE.
d) Behaviour makes the composite index useless and has same result
   as a single column index.

-- SERVER INFO:
5.0.45-community-nt-log MySQL Community Edition (GPL)

-- TABLES (2)
create table test_rel(
  lhs_id int unsigned not null
, rhs_id int unsigned not null
, primary key (lhs_id,rhs_id)
);

create table test_item(
  id int unsigned not null auto_increment
, regtime datetime not null
, rel_id int unsigned not null
, primary key (id)
, index rel_regtime(rel_id,regtime)
);

-- SAMPLE DATA
insert into test_rel(lhs_id,rhs_id) values (1,2), (1,3);
insert into test_item(rel_id,regtime) 
values (2,'2007-05-01'),(2,'2007-05-02'),(2,'2007-05-03'),(3,'2007-05-01'),(3,'2007-05-02'),(3,'2007-05-03');

analyze table test_rel;
analyze table test_item;

-- RESULTS  ---

-- Optimizer works well and uses full index (key_len=12) 
-- when query is non-joined:

EXPLAIN SELECT i.* from test_item i where i.rel_id=2 AND i.regtime>='2007-05-02';

id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE i range rel_regtime rel_regtime 12 NULL 1 Using where

-- Optimizer fails to use full index when query 
-- is joined and range (key_len=4):

EXPLAIN SELECT i.* from test_rel r inner join test_item i on (i.rel_id=r.rhs_id AND i.regtime>='2007-05-02') WHERE r.lhs_id=1;

id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE r ref PRIMARY PRIMARY 4 const 1 Using index
1 SIMPLE i ref rel_regtime rel_regtime 4 icl.r.rhs_id 1 Using where

-- Optimizer works well when query is joined and 
-- equal is used instead of range (key_len=12):

EXPLAIN SELECT i.* from test_rel r inner join test_item i on (i.rel_id=r.rhs_id AND i.regtime='2007-05-02') WHERE r.lhs_id=1;

id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE r ref PRIMARY PRIMARY 4 const 1 Using index
1 SIMPLE i ref rel_regtime rel_regtime 12 icl.r.rhs_id,const 2