[MDEV-11271] Add "leaves" algorithm to OQGRAPH. Created: 2016-11-11  Updated: 2017-12-18  Due: 2016-12-22  Resolved: 2017-12-18

Status: Closed
Project: MariaDB Server
Component/s: Storage Engine - OQGRAPH
Fix Version/s: 10.3.3

Type: Task Priority: Critical
Reporter: Sergey Vojtovich Assignee: Vicențiu Ciorbaru
Resolution: Fixed Votes: 0
Labels: contribution, foundation

Sprint: 10.2.7-1, 10.2.10

 Description   

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

Currently, I had to perform a self-join on the graph table to get a list of all leaf nodes (all destids that themselves are not an origid). This becomes rather expensive the larger the graph is.
I created a simple, large graph of 2 million nodes in (essentially just a chain of nodes, so A->B->C->...) and finding the leaf node from the root node took about 45 seconds. With the new
"leaves" latch it completes in about 7 seconds.

Briefly discussed on oqgraph-dev (thread starting at https://lists.launchpad.net/oqgraph-dev/msg00314.html), but no review was done yet (other than mtr and works for me).


Generated at Thu Feb 08 07:48:39 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.