Add "leaves" algorithm to oqgraph.

This algorithm returns all reachable leaf nodes from a given origin,
or all root nodes that can reach a given destination.

4 files changed, 586 insertions, 0 deletions

diff --git a/storage/oqgraph/mysql-test/oqgraph/general-Aria.result b/storage/oqgraph/mysql-test/oqgraph/general-Aria.result
index e527705045f..bd0f7ed9ee8 100644
--- a/storage/oqgraph/mysql-test/oqgraph/general-Aria.result
+++ b/storage/oqgraph/mysql-test/oqgraph/general-Aria.result
@@ -195,6 +195,170 @@ from	to
 SELECT linkid as `from`, destid as `to` FROM graph where latch='0' and destid = 10;
 from	to
 12	10
+# Leaves search tests
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 1;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 2;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 3;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 4;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 5;
+latch	origid	destid	weight	seq	linkid
+leaves	5	NULL	1	1	7
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 6;
+latch	origid	destid	weight	seq	linkid
+leaves	6	NULL	2	1	7
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 7;
+latch	origid	destid	weight	seq	linkid
+leaves	7	NULL	0	1	7
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 8;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 9;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 1;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 2;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 3;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 4;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 5;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 6;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 7;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 8;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 9;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12;
+latch	origid	destid	weight	seq	linkid
+INSERT INTO graph_base(from_id, to_id) VALUES (10,13);
+INSERT INTO graph_base(from_id, to_id) VALUES (11,14);
+INSERT INTO graph_base(from_id, to_id) VALUES (12,15);
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10;
+latch	origid	destid	weight	seq	linkid
+leaves	10	NULL	3	3	15
+leaves	10	NULL	2	2	14
+leaves	10	NULL	1	1	13
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11;
+latch	origid	destid	weight	seq	linkid
+leaves	11	NULL	3	3	13
+leaves	11	NULL	2	2	15
+leaves	11	NULL	1	1	14
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12;
+latch	origid	destid	weight	seq	linkid
+leaves	12	NULL	3	3	14
+leaves	12	NULL	2	2	13
+leaves	12	NULL	1	1	15
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 13;
+latch	origid	destid	weight	seq	linkid
+leaves	13	NULL	0	1	13
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 14;
+latch	origid	destid	weight	seq	linkid
+leaves	14	NULL	0	1	14
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 15;
+latch	origid	destid	weight	seq	linkid
+leaves	15	NULL	0	1	15
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 13;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 14;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 15;
+latch	origid	destid	weight	seq	linkid
+DELETE FROM graph_base where from_id=10 and to_id=13;
+DELETE FROM graph_base where from_id=11 and to_id=14;
+DELETE FROM graph_base where from_id=12 and to_id=15;
+INSERT INTO graph_base(from_id, to_id) VALUES (13,10);
+INSERT INTO graph_base(from_id, to_id) VALUES (14,11);
+INSERT INTO graph_base(from_id, to_id) VALUES (15,12);
+INSERT INTO graph_base(from_id, to_id) VALUES (16,1);
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 13;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 14;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 15;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 16;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	10	3	3	14
+leaves	NULL	10	2	2	15
+leaves	NULL	10	1	1	13
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	11	3	3	15
+leaves	NULL	11	2	2	13
+leaves	NULL	11	1	1	14
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	12	3	3	13
+leaves	NULL	12	2	2	14
+leaves	NULL	12	1	1	15
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 13;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	13	0	1	13
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 14;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	14	0	1	14
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 15;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	15	0	1	15
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 1;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	1	1	1	16
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 2;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	2	2	1	16
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 3;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	3	2	1	16
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 4;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	4	3	1	16
+DELETE FROM graph_base where from_id=13 and to_id=10;
+DELETE FROM graph_base where from_id=14 and to_id=11;
+DELETE FROM graph_base where from_id=15 and to_id=12;
+DELETE FROM graph_base where from_id=16 and to_id=1;
+SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=2;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=3;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=4;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch='leaves' AND origid=6 AND destid=7;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch='leaves' AND origid=10 AND destid=11;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch='leaves' AND origid=10 AND destid=12;
+latch	origid	destid	weight	seq	linkid
 # Breadth-first search tests
 SELECT * FROM graph WHERE latch = 'breadth_first' AND origid = 1;
 latch	origid	destid	weight	seq	linkid
diff --git a/storage/oqgraph/mysql-test/oqgraph/general-MyISAM.result b/storage/oqgraph/mysql-test/oqgraph/general-MyISAM.result
index bbf660e7db4..e5b5e958fdf 100644
--- a/storage/oqgraph/mysql-test/oqgraph/general-MyISAM.result
+++ b/storage/oqgraph/mysql-test/oqgraph/general-MyISAM.result
@@ -195,6 +195,170 @@ from	to
 SELECT linkid as `from`, destid as `to` FROM graph where latch='0' and destid = 10;
 from	to
 12	10
+# Leaves search tests
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 1;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 2;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 3;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 4;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 5;
+latch	origid	destid	weight	seq	linkid
+leaves	5	NULL	1	1	7
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 6;
+latch	origid	destid	weight	seq	linkid
+leaves	6	NULL	2	1	7
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 7;
+latch	origid	destid	weight	seq	linkid
+leaves	7	NULL	0	1	7
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 8;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 9;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 1;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 2;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 3;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 4;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 5;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 6;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 7;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 8;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 9;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12;
+latch	origid	destid	weight	seq	linkid
+INSERT INTO graph_base(from_id, to_id) VALUES (10,13);
+INSERT INTO graph_base(from_id, to_id) VALUES (11,14);
+INSERT INTO graph_base(from_id, to_id) VALUES (12,15);
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10;
+latch	origid	destid	weight	seq	linkid
+leaves	10	NULL	3	3	15
+leaves	10	NULL	2	2	14
+leaves	10	NULL	1	1	13
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11;
+latch	origid	destid	weight	seq	linkid
+leaves	11	NULL	3	3	13
+leaves	11	NULL	2	2	15
+leaves	11	NULL	1	1	14
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12;
+latch	origid	destid	weight	seq	linkid
+leaves	12	NULL	3	3	14
+leaves	12	NULL	2	2	13
+leaves	12	NULL	1	1	15
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 13;
+latch	origid	destid	weight	seq	linkid
+leaves	13	NULL	0	1	13
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 14;
+latch	origid	destid	weight	seq	linkid
+leaves	14	NULL	0	1	14
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 15;
+latch	origid	destid	weight	seq	linkid
+leaves	15	NULL	0	1	15
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 13;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 14;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 15;
+latch	origid	destid	weight	seq	linkid
+DELETE FROM graph_base where from_id=10 and to_id=13;
+DELETE FROM graph_base where from_id=11 and to_id=14;
+DELETE FROM graph_base where from_id=12 and to_id=15;
+INSERT INTO graph_base(from_id, to_id) VALUES (13,10);
+INSERT INTO graph_base(from_id, to_id) VALUES (14,11);
+INSERT INTO graph_base(from_id, to_id) VALUES (15,12);
+INSERT INTO graph_base(from_id, to_id) VALUES (16,1);
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 13;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 14;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 15;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 16;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	10	3	3	14
+leaves	NULL	10	2	2	15
+leaves	NULL	10	1	1	13
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	11	3	3	15
+leaves	NULL	11	2	2	13
+leaves	NULL	11	1	1	14
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	12	3	3	13
+leaves	NULL	12	2	2	14
+leaves	NULL	12	1	1	15
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 13;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	13	0	1	13
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 14;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	14	0	1	14
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 15;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	15	0	1	15
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 1;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	1	1	1	16
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 2;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	2	2	1	16
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 3;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	3	2	1	16
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 4;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	4	3	1	16
+DELETE FROM graph_base where from_id=13 and to_id=10;
+DELETE FROM graph_base where from_id=14 and to_id=11;
+DELETE FROM graph_base where from_id=15 and to_id=12;
+DELETE FROM graph_base where from_id=16 and to_id=1;
+SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=2;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=3;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=4;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch='leaves' AND origid=6 AND destid=7;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch='leaves' AND origid=10 AND destid=11;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch='leaves' AND origid=10 AND destid=12;
+latch	origid	destid	weight	seq	linkid
 # Breadth-first search tests
 SELECT * FROM graph WHERE latch = 'breadth_first' AND origid = 1;
 latch	origid	destid	weight	seq	linkid
diff --git a/storage/oqgraph/mysql-test/oqgraph/general-innodb.result b/storage/oqgraph/mysql-test/oqgraph/general-innodb.result
index 927d856bc84..38e3e0a23b4 100644
--- a/storage/oqgraph/mysql-test/oqgraph/general-innodb.result
+++ b/storage/oqgraph/mysql-test/oqgraph/general-innodb.result
@@ -195,6 +195,170 @@ from	to
 SELECT linkid as `from`, destid as `to` FROM graph where latch='0' and destid = 10;
 from	to
 12	10
+# Leaves search tests
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 1;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 2;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 3;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 4;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 5;
+latch	origid	destid	weight	seq	linkid
+leaves	5	NULL	1	1	7
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 6;
+latch	origid	destid	weight	seq	linkid
+leaves	6	NULL	2	1	7
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 7;
+latch	origid	destid	weight	seq	linkid
+leaves	7	NULL	0	1	7
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 8;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 9;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 1;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 2;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 3;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 4;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 5;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 6;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 7;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 8;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 9;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12;
+latch	origid	destid	weight	seq	linkid
+INSERT INTO graph_base(from_id, to_id) VALUES (10,13);
+INSERT INTO graph_base(from_id, to_id) VALUES (11,14);
+INSERT INTO graph_base(from_id, to_id) VALUES (12,15);
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10;
+latch	origid	destid	weight	seq	linkid
+leaves	10	NULL	3	3	15
+leaves	10	NULL	2	2	14
+leaves	10	NULL	1	1	13
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11;
+latch	origid	destid	weight	seq	linkid
+leaves	11	NULL	3	3	13
+leaves	11	NULL	2	2	15
+leaves	11	NULL	1	1	14
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12;
+latch	origid	destid	weight	seq	linkid
+leaves	12	NULL	3	3	14
+leaves	12	NULL	2	2	13
+leaves	12	NULL	1	1	15
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 13;
+latch	origid	destid	weight	seq	linkid
+leaves	13	NULL	0	1	13
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 14;
+latch	origid	destid	weight	seq	linkid
+leaves	14	NULL	0	1	14
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 15;
+latch	origid	destid	weight	seq	linkid
+leaves	15	NULL	0	1	15
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 13;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 14;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 15;
+latch	origid	destid	weight	seq	linkid
+DELETE FROM graph_base where from_id=10 and to_id=13;
+DELETE FROM graph_base where from_id=11 and to_id=14;
+DELETE FROM graph_base where from_id=12 and to_id=15;
+INSERT INTO graph_base(from_id, to_id) VALUES (13,10);
+INSERT INTO graph_base(from_id, to_id) VALUES (14,11);
+INSERT INTO graph_base(from_id, to_id) VALUES (15,12);
+INSERT INTO graph_base(from_id, to_id) VALUES (16,1);
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 13;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 14;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 15;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 16;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	10	3	3	14
+leaves	NULL	10	2	2	15
+leaves	NULL	10	1	1	13
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	11	3	3	15
+leaves	NULL	11	2	2	13
+leaves	NULL	11	1	1	14
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	12	3	3	13
+leaves	NULL	12	2	2	14
+leaves	NULL	12	1	1	15
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 13;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	13	0	1	13
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 14;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	14	0	1	14
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 15;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	15	0	1	15
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 1;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	1	1	1	16
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 2;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	2	2	1	16
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 3;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	3	2	1	16
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 4;
+latch	origid	destid	weight	seq	linkid
+leaves	NULL	4	3	1	16
+DELETE FROM graph_base where from_id=13 and to_id=10;
+DELETE FROM graph_base where from_id=14 and to_id=11;
+DELETE FROM graph_base where from_id=15 and to_id=12;
+DELETE FROM graph_base where from_id=16 and to_id=1;
+SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=2;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=3;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=4;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch='leaves' AND origid=6 AND destid=7;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch='leaves' AND origid=10 AND destid=11;
+latch	origid	destid	weight	seq	linkid
+SELECT * FROM graph WHERE latch='leaves' AND origid=10 AND destid=12;
+latch	origid	destid	weight	seq	linkid
 # Breadth-first search tests
 SELECT * FROM graph WHERE latch = 'breadth_first' AND origid = 1;
 latch	origid	destid	weight	seq	linkid
diff --git a/storage/oqgraph/mysql-test/oqgraph/general.inc b/storage/oqgraph/mysql-test/oqgraph/general.inc
index f27b7585dd7..48960f7cadb 100644
--- a/storage/oqgraph/mysql-test/oqgraph/general.inc
+++ b/storage/oqgraph/mysql-test/oqgraph/general.inc
@@ -120,6 +120,100 @@ SELECT linkid as `from`, destid as `to` FROM graph where latch='0' and destid =
 SELECT linkid as `from`, destid as `to` FROM graph where latch='0' and destid = 9;
 SELECT linkid as `from`, destid as `to` FROM graph where latch='0' and destid = 10;
 
+--echo # Leaves search tests
+#-- We are asking "Are there nodes reachable from origid, from which no other nodes can be reached"
+#-- We return a row for each leaf node that is reachable, with its id in 'linkid'
+#-- and the weight calculated as "How many _directed_ hops to get there"
+#-- If there is no path from origid to another node then there is no row for that linkid
+#-- 'seq' is the counted distance of the search, thus, the loop link will always have seq 1
+#--       if there are two reachable neighbours, they will have seq 2,3 and so on
+#-- linkid is the other end
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 1;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 2;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 3;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 4;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 5;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 6;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 7;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 8;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 9;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12;
+
+#-- now do it in reverse - using destid find originating vertices
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 1;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 2;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 3;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 4;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 5;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 6;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 7;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 8;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 9;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12;
+
+# Add more leaf nodes
+INSERT INTO graph_base(from_id, to_id) VALUES (10,13);
+INSERT INTO graph_base(from_id, to_id) VALUES (11,14);
+INSERT INTO graph_base(from_id, to_id) VALUES (12,15);
+
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 13;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 14;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 15;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 13;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 14;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 15;
+
+DELETE FROM graph_base where from_id=10 and to_id=13;
+DELETE FROM graph_base where from_id=11 and to_id=14;
+DELETE FROM graph_base where from_id=12 and to_id=15;
+
+# Add some root nodes
+INSERT INTO graph_base(from_id, to_id) VALUES (13,10);
+INSERT INTO graph_base(from_id, to_id) VALUES (14,11);
+INSERT INTO graph_base(from_id, to_id) VALUES (15,12);
+INSERT INTO graph_base(from_id, to_id) VALUES (16,1);
+
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 10;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 11;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 12;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 13;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 14;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 15;
+SELECT * FROM graph WHERE latch = 'leaves' AND origid = 16;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 10;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 11;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 12;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 13;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 14;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 15;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 1;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 2;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 3;
+SELECT * FROM graph WHERE latch = 'leaves' AND destid = 4;
+
+DELETE FROM graph_base where from_id=13 and to_id=10;
+DELETE FROM graph_base where from_id=14 and to_id=11;
+DELETE FROM graph_base where from_id=15 and to_id=12;
+DELETE FROM graph_base where from_id=16 and to_id=1;
+
+# path queries yield no result with "leaves"
+SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=2;
+SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=3;
+SELECT * FROM graph WHERE latch='leaves' AND origid=1 AND destid=4;
+SELECT * FROM graph WHERE latch='leaves' AND origid=6 AND destid=7;
+SELECT * FROM graph WHERE latch='leaves' AND origid=10 AND destid=11;
+SELECT * FROM graph WHERE latch='leaves' AND origid=10 AND destid=12;
+
 --echo # Breadth-first search tests
 #-- We are asking "Is there a path from node 'origid' to (all) other nodes?"
 #-- We return a row for each other node that is reachable, with its id in 'linkid'