WL#2985 "Partition Pruning"

sql/ha_ndbcluster.cc:
  WL#2985 "Partition Pruning": added part_info->used_partitions initialization
sql/ha_partition.cc:
  WL#2985 "Partition Pruning": added part_info->used_partitions initialization
sql/handler.h:
  WL#2985 "Partition Pruning": 
  Added function prototypes
  in partition_info:
   - Added 'used_partitions' bitmap
   - Added comments
sql/item.h:
  WL#2985 "Partition Pruning": 
  - added enum monotonicity_info
  - added virtual Item::get_monotonicity_info()
sql/item_timefunc.cc:
  WL#2985 "Partition Pruning": 
  - added Item_func_to_days::get_monotonicity_info()
  - added Item_func_year::get_monotonicity_info()
sql/item_timefunc.h:
  WL#2985 "Partition Pruning": 
  - added Item_func_to_days::get_monotonicity_info()
  - added Item_func_year::get_monotonicity_info()
sql/opt_range.cc:
  WL#2985 "Partition Pruning":
  - Split out PARAM structure into PARAM and RANGE_OPT_PARAM part.
  - Added partition pruning module code.
sql/opt_range.h:
  WL#2985 "Partition Pruning": 
  Added prune_partitions() function declaration. This is the entry point for partition pruning 
  module
sql/sql_class.cc:
  WL#2985 "Partition Pruning": added support for "EXPLAIN PARTITIONS SELECT ..."
sql/sql_lex.h:
  WL#2985 "Partition Pruning": added support for "EXPLAIN PARTITIONS SELECT ..."
sql/sql_partition.cc:
  WL#2985 "Partition Pruning": 
   - Added get_list_array_idx_for_endpoint and get_range_... functions to support partition 
     pruning on "partition_field < const"-like intervals.
   - Added partition_info::used_partitions bitmap.
   - Added make_used_partitions_str function
   - Fixed BUG#15819
sql/sql_select.cc:
  WL#2985 "Partition Pruning": 
  - Added prune_partitions() invocation right before the range analysis
  - Added code to handle return value from prune_partitions()
  - Added support for "EXPLAIN PARTITIONS SELECT ..."
sql/sql_yacc.yy:
  #2985 "Partition Pruning": added support for "EXPLAIN PARTITIONS SELECT ..."

2 files changed, 410 insertions, 0 deletions

diff --git a/mysql-test/r/partition_pruning.result b/mysql-test/r/partition_pruning.result
new file mode 100644
index 00000000000..63a727acb8c
--- /dev/null
+++ b/mysql-test/r/partition_pruning.result
@@ -0,0 +1,215 @@
+drop table if exists t1,t2,t3,t4,t5,t6,t7,t8,t9;
+create table t1 ( a int not null) partition by hash(a) partitions 2;
+insert into t1 values (1),(2),(3);
+explain select * from t1 where a=5 and a=6;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
+drop table t1;
+create table t1 (
+a int(11) not null
+) partition by hash (a) partitions 2;
+insert into t1 values (1),(2),(3);
+explain partitions select * from t1 where a=1;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	p1	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t1 where a=2;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	p0	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t1 where a=1 or a=2;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	p0,p1	ALL	NULL	NULL	NULL	NULL	3	Using where
+create table t2 (
+a int not null,
+b int not null
+) partition by key(a,b) partitions 2;
+insert into t2 values (1,1),(2,2),(3,3);
+explain partitions select * from t2 where a=1;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	p0,p1	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t2 where b=1;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	p0,p1	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t2 where a=1 and b=1;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	p0	ALL	NULL	NULL	NULL	NULL	3	Using where
+create table t3 (
+a int
+)
+partition by range (a*1) ( 
+partition p0 values less than (10),
+partition p1 values less than (20)
+);
+insert into t3 values (5),(15);
+explain partitions select * from t3 where a=11;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t3	p1	ALL	NULL	NULL	NULL	NULL	2	Using where
+explain partitions select * from t3 where a=10;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t3	p1	ALL	NULL	NULL	NULL	NULL	2	Using where
+explain partitions select * from t3 where a=20;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
+explain partitions select * from t3 where a=30;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
+create table t4 (a int not null, b int not null) partition by LIST (a+b) (
+partition p0 values in (12),
+partition p1 values in (14)
+);
+insert into t4 values (10,2), (10,4);
+explain partitions select * from t4 where (a=10 and b=1) or (a=10 and b=2);
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t4	p0	ALL	NULL	NULL	NULL	NULL	2	Using where
+explain partitions select * from t4 
+where (a=10 and b=1) or (a=10 and b=2) or (a=10 and b = 3);
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t4	p0	ALL	NULL	NULL	NULL	NULL	2	Using where
+explain partitions select * from t4 where (a=10 and b=2) or (a=10 and b=3)
+or (a=10 and b = 4);
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t4	p0,p1	ALL	NULL	NULL	NULL	NULL	2	Using where
+explain partitions select * from t4 where (a=10 and b=1) or a=11;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t4	p0,p1	ALL	NULL	NULL	NULL	NULL	2	Using where
+explain partitions select * from t4 where (a=10 and b=2) or a=11;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t4	p0,p1	ALL	NULL	NULL	NULL	NULL	2	Using where
+drop table t1, t2, t3, t4;
+create table t5 (a int not null, b int not null, 
+c int not null, d int not null) 
+partition by LIST(a+b) subpartition by HASH (c+d) subpartitions 2
+(
+partition p0 values in (12),
+partition p1 values in (14)
+);
+insert into t5 values (10,2,0,0), (10,4,0,0), (10,2,0,1), (10,4,0,1);
+explain partitions select * from t5;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t5	p0_sp0,p0_sp1,p1_sp0,p1_sp1	ALL	NULL	NULL	NULL	NULL	4	
+explain partitions select * from t5
+where (a=10 and b=1) or (a=10 and b=2) or (a=10 and b = 3);
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t5	p0_sp0,p0_sp1	ALL	NULL	NULL	NULL	NULL	4	Using where
+explain partitions select * from t5 where (a=10 and b=2) or (a=10 and b=3)
+or (a=10 and b = 4);
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t5	p0_sp0,p0_sp1,p1_sp0,p1_sp1	ALL	NULL	NULL	NULL	NULL	4	Using where
+explain partitions select * from t5 where (c=1 and d=1);
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t5	p0_sp0,p1_sp0	ALL	NULL	NULL	NULL	NULL	4	Using where
+explain partitions select * from t5 where (c=2 and d=1);
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t5	p0_sp1,p1_sp1	ALL	NULL	NULL	NULL	NULL	4	Using where
+explain partitions select * from t5 where (a=10 and b=2 and c=1 and d=1) or 
+(c=2 and d=1);
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t5	p0_sp0,p0_sp1,p1_sp1	ALL	NULL	NULL	NULL	NULL	4	Using where
+explain partitions select * from t5 where (a=10 and b=2 and c=1 and d=1) or 
+(b=2 and c=2 and d=1);
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t5	p0_sp0,p0_sp1,p1_sp1	ALL	NULL	NULL	NULL	NULL	4	Using where
+create table t6 (a int not null) partition by LIST(a) (
+partition p1 values in (1),
+partition p3 values in (3),
+partition p5 values in (5),
+partition p7 values in (7),
+partition p9 values in (9)
+);
+insert into t6 values (1),(3),(5);
+explain partitions select * from t6 where a <  1;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
+explain partitions select * from t6 where a <= 1;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t6	p1	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t6 where a >  9;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
+explain partitions select * from t6 where a >= 9;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t6	p9	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t6 where a > 0 and a < 5;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t6	p1,p3	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t6 where a > 5 and a < 12;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t6	p7,p9	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t6 where a > 3 and a < 8 ;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t6	p5,p7	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t6 where a >= 0 and a <= 5;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t6	p1,p3,p5	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t6 where a >= 5 and a <= 12;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t6	p5,p7,p9	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t6 where a >= 3 and a <= 8;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t6	p3,p5,p7	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t6 where a > 3 and a < 5;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
+create table t7 (a int not null) partition by RANGE(a) (
+partition p10 values less than (10),
+partition p30 values less than (30),
+partition p50 values less than (50),
+partition p70 values less than (70),
+partition p90 values less than (90)
+);
+insert into t7 values (10),(30),(50);
+explain partitions select * from t7 where a < 5;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t7	p10	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t7 where a < 10;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t7	p10	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t7 where a <= 10;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t7	p10,p30	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t7 where a = 10;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t7	p30	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t7 where a < 90;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t7	p10,p30,p50,p70,p90	ALL	NULL	NULL	NULL	NULL	3	Using where
+explain partitions select * from t7 where a = 90;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
+explain partitions select * from t7 where a > 90;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
+explain partitions select * from t7 where a >= 90;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
+explain partitions select * from t7 where a > 11 and a < 29;
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t7	p30	ALL	NULL	NULL	NULL	NULL	3	Using where
+create table t8 (a date not null) partition by RANGE(YEAR(a)) (
+partition p0 values less than (1980),
+partition p1 values less than (1990),
+partition p2 values less than (2000)
+);
+insert into t8 values ('1985-05-05'),('1995-05-05');
+explain partitions select * from t8 where a < '1980-02-02';
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t8	p0,p1	ALL	NULL	NULL	NULL	NULL	2	Using where
+create table t9 (a date not null) partition by RANGE(TO_DAYS(a)) (
+partition p0 values less than (732299), -- 2004-12-19
+partition p1 values less than (732468), -- 2005-06-06
+partition p2 values less than (732664)  -- 2005-12-19
+);
+insert into t9 values ('2005-05-05'), ('2005-04-04');
+explain partitions select * from t9 where a <  '2004-12-19';
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t9	p0	ALL	NULL	NULL	NULL	NULL	2	Using where
+explain partitions select * from t9 where a <= '2004-12-19';
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t9	p0,p1	ALL	NULL	NULL	NULL	NULL	2	Using where
+drop table t5,t6,t7,t8,t9;
+create table t1 (a enum('a','b','c','d') default 'a') 
+partition by hash (ascii(a)) partitions 2;
+insert into t1 values ('a'),('b'),('c');
+explain partitions select * from t1 where a='b';
+id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	p0,p1	ALL	NULL	NULL	NULL	NULL	3	Using where
+drop table t1;
diff --git a/mysql-test/t/partition_pruning.test b/mysql-test/t/partition_pruning.test
new file mode 100644
index 00000000000..e496a1b8e12
--- /dev/null
+++ b/mysql-test/t/partition_pruning.test
@@ -0,0 +1,195 @@
+#
+# Partition pruning tests. Currently we only detect which partitions to
+# prune, so the test is EXPLAINs.
+#
+-- source include/have_partition.inc
+
+--disable_warnings
+drop table if exists t1,t2,t3,t4,t5,t6,t7,t8,t9;
+--enable_warnings
+
+
+# Check if we can infer from condition on partition fields that 
+# no records will match.
+create table t1 ( a int not null) partition by hash(a) partitions 2;
+insert into t1 values (1),(2),(3);
+explain select * from t1 where a=5 and a=6;
+drop table t1;
+
+# Simple HASH partitioning
+create table t1 (
+  a int(11) not null
+) partition by hash (a) partitions 2;
+insert into t1 values (1),(2),(3);
+
+explain partitions select * from t1 where a=1;
+explain partitions select * from t1 where a=2;
+explain partitions select * from t1 where a=1 or a=2;
+
+# Partitioning over several fields
+create table t2 (
+  a int not null,
+  b int not null
+) partition by key(a,b) partitions 2;
+insert into t2 values (1,1),(2,2),(3,3);
+
+explain partitions select * from t2 where a=1;
+explain partitions select * from t2 where b=1;
+
+explain partitions select * from t2 where a=1 and b=1;
+
+# RANGE(expr) partitioning 
+create table t3 (
+  a int
+)
+partition by range (a*1) ( 
+  partition p0 values less than (10),
+  partition p1 values less than (20)
+);
+insert into t3 values (5),(15);
+
+explain partitions select * from t3 where a=11;
+explain partitions select * from t3 where a=10;
+explain partitions select * from t3 where a=20;
+
+explain partitions select * from t3 where a=30;
+
+# LIST(expr) partitioning
+create table t4 (a int not null, b int not null) partition by LIST (a+b) (
+  partition p0 values in (12),
+  partition p1 values in (14)
+);
+insert into t4 values (10,2), (10,4);
+
+# empty OR one
+explain partitions select * from t4 where (a=10 and b=1) or (a=10 and b=2);
+
+# empty OR one OR empty
+explain partitions select * from t4 
+  where (a=10 and b=1) or (a=10 and b=2) or (a=10 and b = 3);
+
+# one OR empty OR one
+explain partitions select * from t4 where (a=10 and b=2) or (a=10 and b=3)
+  or (a=10 and b = 4);
+
+# empty OR full
+explain partitions select * from t4 where (a=10 and b=1) or a=11;
+
+# one OR full
+explain partitions select * from t4 where (a=10 and b=2) or a=11;
+
+drop table t1, t2, t3, t4;
+
+# LIST(expr)/HASH subpartitioning.
+create table t5 (a int not null, b int not null, 
+                 c int not null, d int not null) 
+partition by LIST(a+b) subpartition by HASH (c+d) subpartitions 2
+(
+  partition p0 values in (12),
+  partition p1 values in (14)
+);
+ 
+insert into t5 values (10,2,0,0), (10,4,0,0), (10,2,0,1), (10,4,0,1);
+explain partitions select * from t5;
+
+# empty OR one OR empty
+explain partitions select * from t5
+  where (a=10 and b=1) or (a=10 and b=2) or (a=10 and b = 3);
+
+# one OR empty OR one
+explain partitions select * from t5 where (a=10 and b=2) or (a=10 and b=3)
+  or (a=10 and b = 4);
+
+# conditions on subpartitions only
+explain partitions select * from t5 where (c=1 and d=1);
+explain partitions select * from t5 where (c=2 and d=1);
+
+# mixed partition/subpartitions.
+explain partitions select * from t5 where (a=10 and b=2 and c=1 and d=1) or 
+(c=2 and d=1);
+
+# same as above
+explain partitions select * from t5 where (a=10 and b=2 and c=1 and d=1) or 
+(b=2 and c=2 and d=1);
+
+# LIST(field) partitioning, interval analysis.
+create table t6 (a int not null) partition by LIST(a) (
+  partition p1 values in (1),
+  partition p3 values in (3),
+  partition p5 values in (5),
+  partition p7 values in (7),
+  partition p9 values in (9)
+);
+insert into t6 values (1),(3),(5);
+
+explain partitions select * from t6 where a <  1;
+explain partitions select * from t6 where a <= 1;
+explain partitions select * from t6 where a >  9;
+explain partitions select * from t6 where a >= 9;
+
+explain partitions select * from t6 where a > 0 and a < 5;
+explain partitions select * from t6 where a > 5 and a < 12;
+explain partitions select * from t6 where a > 3 and a < 8 ;
+
+explain partitions select * from t6 where a >= 0 and a <= 5;
+explain partitions select * from t6 where a >= 5 and a <= 12;
+explain partitions select * from t6 where a >= 3 and a <= 8;
+
+explain partitions select * from t6 where a > 3 and a < 5;
+
+# RANGE(field) partitioning, interval analysis.
+create table t7 (a int not null) partition by RANGE(a) (
+  partition p10 values less than (10),
+  partition p30 values less than (30),
+  partition p50 values less than (50),
+  partition p70 values less than (70),
+  partition p90 values less than (90)
+);
+insert into t7 values (10),(30),(50);
+
+# leftmost intervals
+explain partitions select * from t7 where a < 5;
+explain partitions select * from t7 where a < 10;
+explain partitions select * from t7 where a <= 10;
+explain partitions select * from t7 where a = 10;
+
+#rightmost intervals
+explain partitions select * from t7 where a < 90;
+explain partitions select * from t7 where a = 90;
+explain partitions select * from t7 where a > 90;
+explain partitions select * from t7 where a >= 90;
+
+# misc intervals
+explain partitions select * from t7 where a > 11 and a < 29;
+
+# LIST(monontonic_func) partitioning
+create table t8 (a date not null) partition by RANGE(YEAR(a)) (
+  partition p0 values less than (1980),
+  partition p1 values less than (1990),
+  partition p2 values less than (2000)
+);
+insert into t8 values ('1985-05-05'),('1995-05-05');
+
+explain partitions select * from t8 where a < '1980-02-02';
+
+# LIST(strict_monotonic_func) partitioning
+create table t9 (a date not null) partition by RANGE(TO_DAYS(a)) (
+  partition p0 values less than (732299), -- 2004-12-19
+  partition p1 values less than (732468), -- 2005-06-06
+  partition p2 values less than (732664)  -- 2005-12-19
+);
+insert into t9 values ('2005-05-05'), ('2005-04-04');
+
+explain partitions select * from t9 where a <  '2004-12-19';
+explain partitions select * from t9 where a <= '2004-12-19';
+
+drop table t5,t6,t7,t8,t9;
+
+# Test the case where we can't create partitioning 'index'
+create table t1 (a enum('a','b','c','d') default 'a') 
+  partition by hash (ascii(a)) partitions 2;
+insert into t1 values ('a'),('b'),('c');
+explain partitions select * from t1 where a='b';
+drop table t1;
+
+