Type:
Task
Priority:
Critical
Resolution:
Fixed
Sprint:
10.2.7-1, 10.2.10
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).
Vicențiu Ciorbaru
made changes -
2017-02-04 16:42
Field
Original Value
New Value
Assignee
Sergei Golubchik
[ serg
]
Vicentiu Ciorbaru
[ cvicentiu
]
Sergei Golubchik
made changes -
2017-06-01 09:28
Priority
Major
[ 3
]
Critical
[ 2
]
Sergei Golubchik
made changes -
2017-10-04 14:47
Sprint
10.2.7-1
[ 171
]
10.2.7-1, 10.2.10
[ 171, 183
]
Vicențiu Ciorbaru
made changes -
2017-12-18 15:01
issue.field.resolutiondate
2017-12-18 15:01:59.0
2017-12-18 15:01:59.252
Vicențiu Ciorbaru
made changes -
2017-12-18 15:01
Fix Version/s
10.3.3
[ 22644
]
Fix Version/s
10.2
[ 14601
]
Resolution
Fixed
[ 1
]
Status
Open
[ 1
]
Closed
[ 6
]
Sergei Golubchik
made changes -
2021-12-06 21:23
Workflow
MariaDB v3
[ 78272
]
MariaDB v4
[ 132997
]
{"report":{"fcp":1179.2000000476837,"ttfb":255.59999990463257,"pageVisibility":"visible","entityId":58872,"key":"jira.project.issue.view-issue","isInitial":true,"threshold":1000,"elementTimings":{},"userDeviceMemory":8,"userDeviceProcessors":64,"apdex":0.5,"journeyId":"b2395e3c-3623-4adb-8c81-db99f1d4d1a8","navigationType":0,"readyForUser":1239,"redirectCount":0,"resourceLoadedEnd":1233.8999998569489,"resourceLoadedStart":261.5,"resourceTiming":[{"duration":93.59999990463257,"initiatorType":"link","name":"https://jira.mariadb.org/s/2c21342762a6a02add1c328bed317ffd-CDN/lu2cib/820016/12ta74/0a8bac35585be7fc6c9cc5a0464cd4cf/_/download/contextbatch/css/_super/batch.css","startTime":261.5,"connectEnd":0,"connectStart":0,"domainLookupEnd":0,"domainLookupStart":0,"fetchStart":261.5,"redirectEnd":0,"redirectStart":0,"requestStart":0,"responseEnd":355.09999990463257,"responseStart":0,"secureConnectionStart":0},{"duration":93.79999995231628,"initiatorType":"link","name":"https://jira.mariadb.org/s/7ebd35e77e471bc30ff0eba799ebc151-CDN/lu2cib/820016/12ta74/494e4c556ecbb29f90a3d3b4f09cb99c/_/download/contextbatch/css/jira.browse.project,project.issue.navigator,jira.view.issue,jira.general,jira.global,atl.general,-_super/batch.css?agile_global_admin_condition=true&jag=true&jira.create.linked.issue=true&slack-enabled=true&whisper-enabled=true","startTime":261.7999999523163,"connectEnd":0,"connectStart":0,"domainLookupEnd":0,"domainLookupStart":0,"fetchStart":261.7999999523163,"redirectEnd":0,"redirectStart":0,"requestStart":0,"responseEnd":355.59999990463257,"responseStart":0,"secureConnectionStart":0},{"duration":157,"initiatorType":"script","name":"https://jira.mariadb.org/s/0917945aaa57108d00c5076fea35e069-CDN/lu2cib/820016/12ta74/0a8bac35585be7fc6c9cc5a0464cd4cf/_/download/contextbatch/js/_super/batch.js?locale=en","startTime":262,"connectEnd":262,"connectStart":262,"domainLookupEnd":262,"domainLookupStart":262,"fetchStart":262,"redirectEnd":0,"redirectStart":0,"requestStart":262,"responseEnd":419,"responseStart":418.89999985694885,"secureConnectionStart":262},{"duration":320.39999985694885,"initiatorType":"script","name":"https://jira.mariadb.org/s/2d8175ec2fa4c816e8023260bd8c1786-CDN/lu2cib/820016/12ta74/494e4c556ecbb29f90a3d3b4f09cb99c/_/download/contextbatch/js/jira.browse.project,project.issue.navigator,jira.view.issue,jira.general,jira.global,atl.general,-_super/batch.js?agile_global_admin_condition=true&jag=true&jira.create.linked.issue=true&locale=en&slack-enabled=true&whisper-enabled=true","startTime":262.2000000476837,"connectEnd":262.2000000476837,"connectStart":262.2000000476837,"domainLookupEnd":262.2000000476837,"domainLookupStart":262.2000000476837,"fetchStart":262.2000000476837,"redirectEnd":0,"redirectStart":0,"requestStart":262.2000000476837,"responseEnd":582.5999999046326,"responseStart":582.5999999046326,"secureConnectionStart":262.2000000476837},{"duration":324.09999990463257,"initiatorType":"script","name":"https://jira.mariadb.org/s/a9324d6758d385eb45c462685ad88f1d-CDN/lu2cib/820016/12ta74/c92c0caa9a024ae85b0ebdbed7fb4bd7/_/download/contextbatch/js/atl.global,-_super/batch.js?locale=en","startTime":262.5,"connectEnd":262.5,"connectStart":262.5,"domainLookupEnd":262.5,"domainLookupStart":262.5,"fetchStart":262.5,"redirectEnd":0,"redirectStart":0,"requestStart":262.5,"responseEnd":586.5999999046326,"responseStart":586.5999999046326,"secureConnectionStart":262.5},{"duration":324.39999985694885,"initiatorType":"script","name":"https://jira.mariadb.org/s/d41d8cd98f00b204e9800998ecf8427e-CDN/lu2cib/820016/12ta74/1.0/_/download/batch/jira.webresources:calendar-en/jira.webresources:calendar-en.js","startTime":262.7000000476837,"connectEnd":262.7000000476837,"connectStart":262.7000000476837,"domainLookupEnd":262.7000000476837,"domainLookupStart":262.7000000476837,"fetchStart":262.7000000476837,"redirectEnd":0,"redirectStart":0,"requestStart":262.7000000476837,"responseEnd":587.0999999046326,"responseStart":587.0999999046326,"secureConnectionStart":262.7000000476837},{"duration":324.59999990463257,"initiatorType":"script","name":"https://jira.mariadb.org/s/d41d8cd98f00b204e9800998ecf8427e-CDN/lu2cib/820016/12ta74/1.0/_/download/batch/jira.webresources:calendar-localisation-moment/jira.webresources:calendar-localisation-moment.js","startTime":262.7999999523163,"connectEnd":262.7999999523163,"connectStart":262.7999999523163,"domainLookupEnd":262.7999999523163,"domainLookupStart":262.7999999523163,"fetchStart":262.7999999523163,"redirectEnd":0,"redirectStart":0,"requestStart":262.7999999523163,"responseEnd":587.3999998569489,"responseStart":587.3999998569489,"secureConnectionStart":262.7999999523163},{"duration":326,"initiatorType":"link","name":"https://jira.mariadb.org/s/b04b06a02d1959df322d9cded3aeecc1-CDN/lu2cib/820016/12ta74/a2ff6aa845ffc9a1d22fe23d9ee791fc/_/download/contextbatch/css/jira.global.look-and-feel,-_super/batch.css","startTime":263,"connectEnd":0,"connectStart":0,"domainLookupEnd":0,"domainLookupStart":0,"fetchStart":263,"redirectEnd":0,"redirectStart":0,"requestStart":0,"responseEnd":589,"responseStart":0,"secureConnectionStart":0},{"duration":324.59999990463257,"initiatorType":"script","name":"https://jira.mariadb.org/rest/api/1.0/shortcuts/820016/47140b6e0a9bc2e4913da06536125810/shortcuts.js?context=issuenavigation&context=issueaction","startTime":263.2999999523163,"connectEnd":263.2999999523163,"connectStart":263.2999999523163,"domainLookupEnd":263.2999999523163,"domainLookupStart":263.2999999523163,"fetchStart":263.2999999523163,"redirectEnd":0,"redirectStart":0,"requestStart":263.2999999523163,"responseEnd":587.8999998569489,"responseStart":587.8999998569489,"secureConnectionStart":263.2999999523163},{"duration":325.59999990463257,"initiatorType":"link","name":"https://jira.mariadb.org/s/3ac36323ba5e4eb0af2aa7ac7211b4bb-CDN/lu2cib/820016/12ta74/d176f0986478cc64f24226b3d20c140d/_/download/contextbatch/css/com.atlassian.jira.projects.sidebar.init,-_super,-project.issue.navigator,-jira.view.issue/batch.css?jira.create.linked.issue=true","startTime":263.5,"connectEnd":0,"connectStart":0,"domainLookupEnd":0,"domainLookupStart":0,"fetchStart":263.5,"redirectEnd":0,"redirectStart":0,"requestStart":0,"responseEnd":589.0999999046326,"responseStart":0,"secureConnectionStart":0},{"duration":324.90000009536743,"initiatorType":"script","name":"https://jira.mariadb.org/s/5d5e8fe91fbc506585e83ea3b62ccc4b-CDN/lu2cib/820016/12ta74/d176f0986478cc64f24226b3d20c140d/_/download/contextbatch/js/com.atlassian.jira.projects.sidebar.init,-_super,-project.issue.navigator,-jira.view.issue/batch.js?jira.create.linked.issue=true&locale=en","startTime":263.59999990463257,"connectEnd":263.59999990463257,"connectStart":263.59999990463257,"domainLookupEnd":263.59999990463257,"domainLookupStart":263.59999990463257,"fetchStart":263.59999990463257,"redirectEnd":0,"redirectStart":0,"requestStart":263.59999990463257,"responseEnd":588.5,"responseStart":588.5,"secureConnectionStart":263.59999990463257},{"duration":506.90000009536743,"initiatorType":"script","name":"https://jira.mariadb.org/s/d41d8cd98f00b204e9800998ecf8427e-CDN/lu2cib/820016/12ta74/1.0/_/download/batch/jira.webresources:bigpipe-js/jira.webresources:bigpipe-js.js","startTime":264.39999985694885,"connectEnd":264.39999985694885,"connectStart":264.39999985694885,"domainLookupEnd":264.39999985694885,"domainLookupStart":264.39999985694885,"fetchStart":264.39999985694885,"redirectEnd":0,"redirectStart":0,"requestStart":264.39999985694885,"responseEnd":771.2999999523163,"responseStart":771.2000000476837,"secureConnectionStart":264.39999985694885},{"duration":774.2999999523163,"initiatorType":"script","name":"https://jira.mariadb.org/s/d41d8cd98f00b204e9800998ecf8427e-CDN/lu2cib/820016/12ta74/1.0/_/download/batch/jira.webresources:bigpipe-init/jira.webresources:bigpipe-init.js","startTime":268.5,"connectEnd":268.5,"connectStart":268.5,"domainLookupEnd":268.5,"domainLookupStart":268.5,"fetchStart":268.5,"redirectEnd":0,"redirectStart":0,"requestStart":268.5,"responseEnd":1042.7999999523163,"responseStart":1042.7999999523163,"secureConnectionStart":268.5},{"duration":196.5,"initiatorType":"xmlhttprequest","name":"https://jira.mariadb.org/rest/webResources/1.0/resources","startTime":574.2000000476837,"connectEnd":574.2000000476837,"connectStart":574.2000000476837,"domainLookupEnd":574.2000000476837,"domainLookupStart":574.2000000476837,"fetchStart":574.2000000476837,"redirectEnd":0,"redirectStart":0,"requestStart":574.2000000476837,"responseEnd":770.7000000476837,"responseStart":770.7000000476837,"secureConnectionStart":574.2000000476837},{"duration":137.79999995231628,"initiatorType":"link","name":"https://jira.mariadb.org/s/d5715adaadd168a9002b108b2b039b50-CDN/lu2cib/820016/12ta74/be4b45e9cec53099498fa61c8b7acba4/_/download/contextbatch/css/jira.project.sidebar,-_super,-project.issue.navigator,-jira.general,-jira.browse.project,-jira.view.issue,-jira.global,-atl.general,-com.atlassian.jira.projects.sidebar.init/batch.css?agile_global_admin_condition=true&jag=true&jira.create.linked.issue=true&slack-enabled=true&whisper-enabled=true","startTime":913.0999999046326,"connectEnd":0,"connectStart":0,"domainLookupEnd":0,"domainLookupStart":0,"fetchStart":913.0999999046326,"redirectEnd":0,"redirectStart":0,"requestStart":0,"responseEnd":1050.8999998569489,"responseStart":0,"secureConnectionStart":0},{"duration":137.39999985694885,"initiatorType":"link","name":"https://jira.mariadb.org/s/50bc9be5bfead1a25e72c1a9338c94f6-CDN/lu2cib/820016/12ta74/e108c7645258ccb43280ed3404e3e949/_/download/contextbatch/css/com.atlassian.jira.plugins.jira-development-integration-plugin:0,-_super,-jira.view.issue,-jira.global,-jira.general,-jira.browse.project,-project.issue.navigator,-atl.general/batch.css?agile_global_admin_condition=true&jag=true&jira.create.linked.issue=true&slack-enabled=true&whisper-enabled=true","startTime":913.7000000476837,"connectEnd":0,"connectStart":0,"domainLookupEnd":0,"domainLookupStart":0,"fetchStart":913.7000000476837,"redirectEnd":0,"redirectStart":0,"requestStart":0,"responseEnd":1051.0999999046326,"responseStart":0,"secureConnectionStart":0},{"duration":315,"initiatorType":"script","name":"https://jira.mariadb.org/s/d41d8cd98f00b204e9800998ecf8427e-CDN/lu2cib/820016/12ta74/e65b778d185daf5aee24936755b43da6/_/download/contextbatch/js/browser-metrics-plugin.contrib,-_super,-project.issue.navigator,-jira.view.issue,-atl.general/batch.js?agile_global_admin_condition=true&jag=true&jira.create.linked.issue=true&slack-enabled=true&whisper-enabled=true","startTime":915.2000000476837,"connectEnd":915.2000000476837,"connectStart":915.2000000476837,"domainLookupEnd":915.2000000476837,"domainLookupStart":915.2000000476837,"fetchStart":915.2000000476837,"redirectEnd":0,"redirectStart":0,"requestStart":915.2000000476837,"responseEnd":1230.2000000476837,"responseStart":1230.2000000476837,"secureConnectionStart":915.2000000476837},{"duration":316.7999999523163,"initiatorType":"script","name":"https://jira.mariadb.org/s/097ae97cb8fbec7d6ea4bbb1f26955b9-CDN/lu2cib/820016/12ta74/be4b45e9cec53099498fa61c8b7acba4/_/download/contextbatch/js/jira.project.sidebar,-_super,-project.issue.navigator,-jira.general,-jira.browse.project,-jira.view.issue,-jira.global,-atl.general,-com.atlassian.jira.projects.sidebar.init/batch.js?agile_global_admin_condition=true&jag=true&jira.create.linked.issue=true&locale=en&slack-enabled=true&whisper-enabled=true","startTime":915.7000000476837,"connectEnd":915.7000000476837,"connectStart":915.7000000476837,"domainLookupEnd":915.7000000476837,"domainLookupStart":915.7000000476837,"fetchStart":915.7000000476837,"redirectEnd":0,"redirectStart":0,"requestStart":915.7000000476837,"responseEnd":1232.5,"responseStart":1232.5,"secureConnectionStart":915.7000000476837},{"duration":317.89999985694885,"initiatorType":"script","name":"https://jira.mariadb.org/s/e0bf5781d46ea69fb123572974cf39de-CDN/lu2cib/820016/12ta74/e108c7645258ccb43280ed3404e3e949/_/download/contextbatch/js/com.atlassian.jira.plugins.jira-development-integration-plugin:0,-_super,-jira.view.issue,-jira.global,-jira.general,-jira.browse.project,-project.issue.navigator,-atl.general/batch.js?agile_global_admin_condition=true&jag=true&jira.create.linked.issue=true&locale=en&slack-enabled=true&whisper-enabled=true","startTime":916,"connectEnd":916,"connectStart":916,"domainLookupEnd":916,"domainLookupStart":916,"fetchStart":916,"redirectEnd":0,"redirectStart":0,"requestStart":916,"responseEnd":1233.8999998569489,"responseStart":1233.8999998569489,"secureConnectionStart":916},{"duration":216.59999990463257,"initiatorType":"xmlhttprequest","name":"https://jira.mariadb.org/rest/webResources/1.0/resources","startTime":1092.5,"connectEnd":1092.5,"connectStart":1092.5,"domainLookupEnd":1092.5,"domainLookupStart":1092.5,"fetchStart":1092.5,"redirectEnd":0,"redirectStart":0,"requestStart":1092.5,"responseEnd":1309.0999999046326,"responseStart":1309.0999999046326,"secureConnectionStart":1092.5}],"fetchStart":0,"domainLookupStart":0,"domainLookupEnd":0,"connectStart":0,"connectEnd":0,"requestStart":82,"responseStart":255,"responseEnd":259,"domLoading":259,"domInteractive":1315,"domContentLoadedEventStart":1315,"domContentLoadedEventEnd":1377,"domComplete":1743,"loadEventStart":1743,"loadEventEnd":1743,"userAgent":"Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)","marks":[{"name":"bigPipe.sidebar-id.start","time":1274.3999998569489},{"name":"bigPipe.sidebar-id.end","time":1275.2999999523163},{"name":"bigPipe.activity-panel-pipe-id.start","time":1275.3999998569489},{"name":"bigPipe.activity-panel-pipe-id.end","time":1278.0999999046326},{"name":"activityTabFullyLoaded","time":1410.5999999046326}],"measures":[],"correlationId":"61f33278747b3","effectiveType":"4g","downlink":9,"rtt":0,"serverDuration":117,"dbReadsTimeInMs":19,"dbConnsTimeInMs":28,"applicationHash":"9d11dbea5f4be3d4cc21f03a88dd11d8c8687422","experiments":[]}}