RB-Tree indexes support in HEAP tables

Renamed _hp_func  ->  hp_func
mi_key_cmp moved to /mysys/my_handler.c
New tests for HEAP tables


heap/_check.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/_rectest.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/heapdef.h:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_block.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_clear.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_close.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_create.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_delete.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_hash.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_open.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_panic.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_rename.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_rfirst.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_rkey.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_rlast.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_rnext.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_rprev.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_rrnd.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_rsame.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_scan.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_test1.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_test2.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_update.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_write.c:
  RB-tree index
  Renamed _hp_func -> hp_func
include/Makefile.am:
  New include
include/heap.h:
  RB-Tree index
include/my_tree.h:
  new search functions
  new custom_arg argument
include/myisam.h:
  Removed MI_KEYSEG
isam/isamlog.c:
  Add custom_arg
isam/pack_isam.c:
  Add custom_arg
myisam/ft_nlq_search.c:
  Add custom_arg
myisam/ft_parser.c:
  Add custom_arg
myisam/ft_stopwords.c:
  Add custom_arg
myisam/mi_search.c:
  Remove mi_key_cmp
myisam/mi_write.c:
  Add custom_arg
myisam/myisamdef.h:
  Remove mi_key_cmp
myisam/myisamlog.c:
  Add custom_arg
myisam/myisampack.c:
  Add custom_arg
mysys/Makefile.am:
  New file my_handler.c
mysys/tree.c:
  custom_arg
  new search functions
sql/ha_heap.cc:
  RBTree
sql/ha_myisam.cc:
  RBTree
sql/item_sum.cc:
  custom_arg
sql/sql_analyse.cc:
  custom_arg
sql/sql_class.h:
  custom_arg
sql/sql_table.cc:
  Remove duplicate code
sql/sql_yacc.yy:
  UNDEF by default
sql/table.cc:
  Remove dirty hack

2 files changed, 410 insertions, 0 deletions

diff --git a/mysql-test/r/heap_btree.result b/mysql-test/r/heap_btree.result
new file mode 100644
index 00000000000..14c5f6d56f4
--- /dev/null
+++ b/mysql-test/r/heap_btree.result
@@ -0,0 +1,205 @@
+drop table if exists t1;
+create table t1 (a int not null,b int not null, primary key using BTREE (a)) type=heap comment="testing heaps" avg_row_length=100 min_rows=1 max_rows=100;
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+delete from t1 where a=1 or a=0;
+show keys from t1;
+Table	Non_unique	Key_name	Seq_in_index	Column_name	Collation	Cardinality	Sub_part	Packed	Null	Index_type	Comment
+t1	0	PRIMARY	1	a	A	NULL	NULL	NULL		BTREE	
+select * from t1;
+a	b
+2	2
+3	3
+4	4
+select * from t1 where a=4;
+a	b
+4	4
+update t1 set b=5 where a=4;
+update t1 set b=b+1 where a>=3;
+replace t1 values (3,3);
+select * from t1;
+a	b
+2	2
+3	3
+4	6
+alter table t1 add c int not null, add key using BTREE (c,a);
+drop table t1;
+create table t1 (a int not null,b int not null, primary key using BTREE (a)) type=heap comment="testing heaps";
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+delete from t1 where a > 0;
+select * from t1;
+a	b
+drop table t1;
+create table t1 (a int not null,b int not null, primary key using BTREE (a)) type=heap comment="testing heaps";
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+alter table t1 modify a int not null auto_increment, type=myisam, comment="new myisam table";
+select * from t1;
+a	b
+1	1
+2	2
+3	3
+4	4
+drop table t1;
+create table t1 (a int not null) type=heap;
+insert into t1 values (869751),(736494),(226312),(802616);
+select * from t1 where a > 736494;
+a
+869751
+802616
+alter table t1 add unique uniq_id using BTREE (a);
+select * from t1 where a > 736494;
+a
+802616
+869751
+select * from t1 where a = 736494;
+a
+736494
+select * from t1 where a=869751 or a=736494;
+a
+736494
+869751
+select * from t1 where a in (869751,736494,226312,802616);
+a
+226312
+736494
+802616
+869751
+alter table t1 type=myisam;
+explain select * from t1 where a in (869751,736494,226312,802616);
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	range	uniq_id	uniq_id	4	NULL	4	where used; Using index
+drop table t1;
+create table t1 (x int not null, y int not null, key x  using BTREE (x), unique y  using BTREE (y))
+type=heap;
+insert into t1 values (1,1),(2,2),(1,3),(2,4),(2,5),(2,6);
+select * from t1 where x=1;
+x	y
+1	1
+1	3
+select * from t1,t1 as t2 where t1.x=t2.y;
+x	y	x	y
+1	1	1	1
+2	2	2	2
+1	3	1	1
+2	4	2	2
+2	5	2	2
+2	6	2	2
+explain select * from t1,t1 as t2 where t1.x=t2.y;
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ALL	x	NULL	NULL	NULL	6	
+t2	eq_ref	y	y	4	t1.x	1	
+drop table t1;
+create table t1 (a int) type=heap;
+insert into t1 values(1);
+select max(a) from t1;
+max(a)
+1
+drop table t1;
+CREATE TABLE t1 ( a int not null default 0, b int not null default 0,  key  using BTREE (a),  key  using BTREE (b)  ) TYPE=HEAP;
+insert into t1 values(1,1),(1,2),(2,3),(1,3),(1,4),(1,5),(1,6);
+select * from t1 where a=1;
+a	b
+1	1
+1	2
+1	3
+1	4
+1	5
+1	6
+insert into t1 values(1,1),(1,2),(2,3),(1,3),(1,4),(1,5),(1,6);
+select * from t1 where a=1;
+a	b
+1	1
+1	2
+1	3
+1	4
+1	5
+1	6
+1	1
+1	2
+1	3
+1	4
+1	5
+1	6
+drop table t1;
+create table t1 (id int unsigned not null, primary key  using BTREE (id)) type=HEAP;
+insert into t1 values(1);
+select max(id) from t1;
+max(id)
+NULL
+insert into t1 values(2);
+select max(id) from t1;
+max(id)
+NULL
+replace into t1 values(1);
+drop table t1;
+create table t1 (n int) type=heap;
+drop table t1;
+create table t1 (n int) type=heap;
+drop table if exists t1;
+CREATE table t1(f1 int not null,f2 char(20) not 
+null,index(f2)) type=heap;
+INSERT into t1 set f1=12,f2="bill";
+INSERT into t1 set f1=13,f2="bill";
+INSERT into t1 set f1=14,f2="bill";
+INSERT into t1 set f1=15,f2="bill";
+INSERT into t1 set f1=16,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+delete from t1 where f2="bill";
+select * from t1;
+f1	f2
+16	ted
+12	ted
+12	ted
+12	ted
+12	ted
+drop table t1;
+create table t1 (btn char(10) not null, key using BTREE (btn)) type=heap;
+insert into t1 values ("hello"),("hello"),("hello"),("hello"),("hello"),("a"),("b"),("c"),("d"),("e"),("f"),("g"),("h"),("i");
+explain select * from t1 where btn like "q%";
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ALL	btn	NULL	NULL	NULL	14	where used
+select * from t1 where btn like "q%";
+btn
+alter table t1 add column new_col char(1) not null, add key using BTREE (btn,new_col), drop key btn;
+update t1 set new_col=btn;
+explain select * from t1 where btn="a";
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ref	btn	btn	10	const	1	where used
+explain select * from t1 where btn="a" and new_col="a";
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ref	btn	btn	11	const,const	1	where used
+drop table t1;
+CREATE TABLE t1 (
+a int default NULL,
+b int default NULL,
+KEY a using BTREE (a),
+UNIQUE b using BTREE (b)
+) type=heap;
+INSERT INTO t1 VALUES (NULL,99),(99,NULL),(1,1),(2,2),(1,3);
+SELECT * FROM t1 WHERE a=NULL;
+a	b
+explain SELECT * FROM t1 WHERE a IS NULL;
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ref	a	a	5	const	1	where used
+SELECT * FROM t1 WHERE a<=>NULL;
+a	b
+NULL	99
+SELECT * FROM t1 WHERE b=NULL;
+a	b
+explain SELECT * FROM t1 WHERE b IS NULL;
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ref	b	b	5	const	1	where used
+SELECT * FROM t1 WHERE b<=>NULL;
+a	b
+99	NULL
+INSERT INTO t1 VALUES (1,3);
+Duplicate entry '3' for key 1
+DROP TABLE t1;
+CREATE TABLE t1 (a int not null, primary key using BTREE (a)) type=heap;
+INSERT into t1 values (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11);
+DELETE from t1 where a < 100;
+SELECT * from t1;
+a
+DROP TABLE t1;
diff --git a/mysql-test/r/heap_hash.result b/mysql-test/r/heap_hash.result
new file mode 100644
index 00000000000..9b7f2cca6bc
--- /dev/null
+++ b/mysql-test/r/heap_hash.result
@@ -0,0 +1,205 @@
+drop table if exists t1;
+create table t1 (a int not null,b int not null, primary key using HASH (a)) type=heap comment="testing heaps" avg_row_length=100 min_rows=1 max_rows=100;
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+delete from t1 where a=1 or a=0;
+show keys from t1;
+Table	Non_unique	Key_name	Seq_in_index	Column_name	Collation	Cardinality	Sub_part	Packed	Null	Index_type	Comment
+t1	0	PRIMARY	1	a	NULL	NULL	NULL	NULL		HASH	
+select * from t1;
+a	b
+2	2
+3	3
+4	4
+select * from t1 where a=4;
+a	b
+4	4
+update t1 set b=5 where a=4;
+update t1 set b=b+1 where a>=3;
+replace t1 values (3,3);
+select * from t1;
+a	b
+2	2
+3	3
+4	6
+alter table t1 add c int not null, add key using HASH (c,a);
+drop table t1;
+create table t1 (a int not null,b int not null, primary key using HASH (a)) type=heap comment="testing heaps";
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+delete from t1 where a > 0;
+select * from t1;
+a	b
+drop table t1;
+create table t1 (a int not null,b int not null, primary key using HASH (a)) type=heap comment="testing heaps";
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+alter table t1 modify a int not null auto_increment, type=myisam, comment="new myisam table";
+select * from t1;
+a	b
+1	1
+2	2
+3	3
+4	4
+drop table t1;
+create table t1 (a int not null) type=heap;
+insert into t1 values (869751),(736494),(226312),(802616);
+select * from t1 where a > 736494;
+a
+869751
+802616
+alter table t1 add unique uniq_id using HASH (a);
+select * from t1 where a > 736494;
+a
+869751
+802616
+select * from t1 where a = 736494;
+a
+736494
+select * from t1 where a=869751 or a=736494;
+a
+736494
+869751
+select * from t1 where a in (869751,736494,226312,802616);
+a
+226312
+736494
+802616
+869751
+alter table t1 type=myisam;
+explain select * from t1 where a in (869751,736494,226312,802616);
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	range	uniq_id	uniq_id	4	NULL	4	where used; Using index
+drop table t1;
+create table t1 (x int not null, y int not null, key x  using HASH (x), unique y  using HASH (y))
+type=heap;
+insert into t1 values (1,1),(2,2),(1,3),(2,4),(2,5),(2,6);
+select * from t1 where x=1;
+x	y
+1	3
+1	1
+select * from t1,t1 as t2 where t1.x=t2.y;
+x	y	x	y
+1	1	1	1
+2	2	2	2
+1	3	1	1
+2	4	2	2
+2	5	2	2
+2	6	2	2
+explain select * from t1,t1 as t2 where t1.x=t2.y;
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ALL	x	NULL	NULL	NULL	6	
+t2	eq_ref	y	y	4	t1.x	1	
+drop table t1;
+create table t1 (a int) type=heap;
+insert into t1 values(1);
+select max(a) from t1;
+max(a)
+1
+drop table t1;
+CREATE TABLE t1 ( a int not null default 0, b int not null default 0,  key  using HASH (a),  key  using HASH (b)  ) TYPE=HEAP;
+insert into t1 values(1,1),(1,2),(2,3),(1,3),(1,4),(1,5),(1,6);
+select * from t1 where a=1;
+a	b
+1	6
+1	5
+1	4
+1	3
+1	2
+1	1
+insert into t1 values(1,1),(1,2),(2,3),(1,3),(1,4),(1,5),(1,6);
+select * from t1 where a=1;
+a	b
+1	6
+1	5
+1	4
+1	3
+1	2
+1	1
+1	6
+1	5
+1	4
+1	3
+1	2
+1	1
+drop table t1;
+create table t1 (id int unsigned not null, primary key  using HASH (id)) type=HEAP;
+insert into t1 values(1);
+select max(id) from t1;
+max(id)
+1
+insert into t1 values(2);
+select max(id) from t1;
+max(id)
+2
+replace into t1 values(1);
+drop table t1;
+create table t1 (n int) type=heap;
+drop table t1;
+create table t1 (n int) type=heap;
+drop table if exists t1;
+CREATE table t1(f1 int not null,f2 char(20) not 
+null,index(f2)) type=heap;
+INSERT into t1 set f1=12,f2="bill";
+INSERT into t1 set f1=13,f2="bill";
+INSERT into t1 set f1=14,f2="bill";
+INSERT into t1 set f1=15,f2="bill";
+INSERT into t1 set f1=16,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+delete from t1 where f2="bill";
+select * from t1;
+f1	f2
+16	ted
+12	ted
+12	ted
+12	ted
+12	ted
+drop table t1;
+create table t1 (btn char(10) not null, key using HASH (btn)) type=heap;
+insert into t1 values ("hello"),("hello"),("hello"),("hello"),("hello"),("a"),("b"),("c"),("d"),("e"),("f"),("g"),("h"),("i");
+explain select * from t1 where btn like "q%";
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ALL	btn	NULL	NULL	NULL	14	where used
+select * from t1 where btn like "q%";
+btn
+alter table t1 add column new_col char(1) not null, add key using HASH (btn,new_col), drop key btn;
+update t1 set new_col=btn;
+explain select * from t1 where btn="a";
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ALL	btn	NULL	NULL	NULL	14	where used
+explain select * from t1 where btn="a" and new_col="a";
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ref	btn	btn	11	const,const	10	where used
+drop table t1;
+CREATE TABLE t1 (
+a int default NULL,
+b int default NULL,
+KEY a using HASH (a),
+UNIQUE b using HASH (b)
+) type=heap;
+INSERT INTO t1 VALUES (NULL,99),(99,NULL),(1,1),(2,2),(1,3);
+SELECT * FROM t1 WHERE a=NULL;
+a	b
+explain SELECT * FROM t1 WHERE a IS NULL;
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ref	a	a	5	const	10	where used
+SELECT * FROM t1 WHERE a<=>NULL;
+a	b
+NULL	99
+SELECT * FROM t1 WHERE b=NULL;
+a	b
+explain SELECT * FROM t1 WHERE b IS NULL;
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ref	b	b	5	const	1	where used
+SELECT * FROM t1 WHERE b<=>NULL;
+a	b
+99	NULL
+INSERT INTO t1 VALUES (1,3);
+Duplicate entry '3' for key 1
+DROP TABLE t1;
+CREATE TABLE t1 (a int not null, primary key using HASH (a)) type=heap;
+INSERT into t1 values (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11);
+DELETE from t1 where a < 100;
+SELECT * from t1;
+a
+DROP TABLE t1;