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.

7 files changed, 668 insertions, 0 deletions

diff --git a/storage/oqgraph/graphcore.cc b/storage/oqgraph/graphcore.cc
index bf454aa3333..31284a7e9a1 100644
--- a/storage/oqgraph/graphcore.cc
+++ b/storage/oqgraph/graphcore.cc
@@ -330,6 +330,40 @@ namespace open_query {
   };
 
   template <typename P, typename D>
+  struct GRAPHCORE_INTERNAL oqgraph_visit_leaves
+    : public base_visitor< oqgraph_visit_leaves<P,D> >
+  {
+    typedef on_finish_vertex event_filter;
+
+    oqgraph_visit_leaves(const P& p, const D& d,
+                       stack_cursor *cursor)
+      : seq(0), m_cursor(*cursor), m_p(p), m_d(d)
+    { assert(cursor); }
+
+    template<class T, class Graph>
+    void operator()(T u, Graph &g)
+    {
+      typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
+      boost::tuples::tie(ei, ei_end) = out_edges(u, g);
+      if (ei == ei_end)
+      {
+        m_cursor.results.push(reference(++seq, u, m_d[ u ]));
+      }
+    }
+  private:
+    int seq;
+    stack_cursor &m_cursor;
+    P m_p;
+    D m_d;
+  };
+
+  template <typename P, typename D>
+  oqgraph_visit_leaves<P,D>
+    make_oqgraph_visit_leaves(const P& p, const D& d, stack_cursor *cursor)
+  { return oqgraph_visit_leaves<P,D>(p, d, cursor); }
+
+
+  template <typename P, typename D>
   struct GRAPHCORE_INTERNAL oqgraph_visit_dist
     : public base_visitor< oqgraph_visit_dist<P,D> >
   {
@@ -829,6 +863,7 @@ namespace open_query
 
       case DIJKSTRAS | HAVE_ORIG:
       case BREADTH_FIRST | HAVE_ORIG:
+      case LEAVES | HAVE_ORIG:
         if ((cursor= new (std::nothrow) stack_cursor(share)) && (orig || dest))
         {
           boost::unordered_map<Vertex, Vertex> p;
@@ -879,6 +914,28 @@ namespace open_query
                 ),
                 make_two_bit_judy_map(get(vertex_index, share->g)));
             break;
+          case LEAVES:
+            breadth_first_visit(share->g, *orig, Q,
+                make_bfs_visitor(
+                    std::make_pair(
+                        record_predecessors(
+                            boost::make_assoc_property_map(p),
+                            on_tree_edge()
+                        ),
+                    std::make_pair(
+                        record_distances(
+                            boost::make_assoc_property_map(d),
+                            on_tree_edge()
+                        ),
+                        make_oqgraph_visit_leaves(
+                            boost::make_assoc_property_map(p),
+                            boost::make_assoc_property_map(d),
+                            static_cast<stack_cursor*>(cursor)
+                        )
+                    ))
+                ),
+                make_two_bit_judy_map(get(vertex_index, share->g)));
+            break;
           default:
             abort();
           }
@@ -886,6 +943,7 @@ namespace open_query
         break;
       case BREADTH_FIRST | HAVE_DEST:
       case DIJKSTRAS | HAVE_DEST:
+      case LEAVES | HAVE_DEST:
         if ((cursor= new (std::nothrow) stack_cursor(share)) && (orig || dest))
         {
           boost::unordered_map<Vertex, Vertex> p;
@@ -937,6 +995,28 @@ namespace open_query
                 ),
                 make_two_bit_judy_map(get(vertex_index, r)));
             break;
+          case LEAVES:
+            breadth_first_visit(r, *dest, Q,
+                make_bfs_visitor(
+                    std::make_pair(
+                        record_predecessors(
+                            boost::make_assoc_property_map(p),
+                            on_tree_edge()
+                        ),
+                    std::make_pair(
+                        record_distances(
+                            boost::make_assoc_property_map(d),
+                            on_tree_edge()
+                        ),
+                        make_oqgraph_visit_leaves(
+                            boost::make_assoc_property_map(p),
+                            boost::make_assoc_property_map(d),
+                            static_cast<stack_cursor*>(cursor)
+                        )
+                    ))
+                ),
+                make_two_bit_judy_map(get(vertex_index, r)));
+            break;
           default:
             abort();
           }
diff --git a/storage/oqgraph/graphcore.h b/storage/oqgraph/graphcore.h
index 7fa3d4554bf..c954b8b029a 100644
--- a/storage/oqgraph/graphcore.h
+++ b/storage/oqgraph/graphcore.h
@@ -70,6 +70,7 @@ namespace open_query
       DIJKSTRAS = 1,
       BREADTH_FIRST = 2,
       NUM_SEARCH_OP = 3,
+      LEAVES = 4,
 
       ALGORITHM = 0x0ffff,
       HAVE_ORIG = 0x10000,
diff --git a/storage/oqgraph/ha_oqgraph.cc b/storage/oqgraph/ha_oqgraph.cc
index 82b78285a49..a4d1aa85948 100644
--- a/storage/oqgraph/ha_oqgraph.cc
+++ b/storage/oqgraph/ha_oqgraph.cc
@@ -87,6 +87,7 @@ static const oqgraph_latch_op_table latch_ops_table[] = {
   { "", oqgraph::NO_SEARCH } ,  // suggested by Arjen, use empty string instead of no_search
   { "dijkstras", oqgraph::DIJKSTRAS } ,
   { "breadth_first", oqgraph::BREADTH_FIRST } ,
+  { "leaves", oqgraph::LEAVES },
   { NULL, -1 }
 };
 
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'