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

Add "leaves" algorithm to OQGRAPH.

    XMLWordPrintable

Details

    • 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

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

            Dates

              Created:
              Updated:
              Resolved:

              Git Integration

                Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.