Uploaded image for project: 'MariaDB Server'
  1. MariaDB Server
  2. MDEV-11271

Add "leaves" algorithm to OQGRAPH.

    XMLWordPrintable

    Details

    • 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).

        Attachments

          Activity

            People

            Assignee:
            cvicentiu Vicențiu Ciorbaru
            Reporter:
            svoj Sergey Vojtovich
            Votes:
            0 Vote for this issue
            Watchers:
            6 Start watching this issue

              Dates

              Due:
              Created:
              Updated:
              Resolved: