# Performance is not good when finding the paths between 2 nodes with k-shortest

**URL:** <https://discuss.dgraph.io/t/performance-is-not-good-when-finding-the-paths-between-2-nodes-with-k-shortest/3533>\
**Category:** Dgraph\
**Created:** [November 1, 2018, 4:41am UTC](https://discuss.dgraph.io/t/performance-is-not-good-when-finding-the-paths-between-2-nodes-with-k-shortest/3533 "2018-11-01T04:41:59Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![peterZ](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/peterz/32/1357_2.png) [@peterZ](https://discuss.dgraph.io/u/peterZ)\
**Post date:** [November 1, 2018, 4:41am UTC](https://discuss.dgraph.io/t/performance-is-not-good-when-finding-the-paths-between-2-nodes-with-k-shortest/3533/1 "2018-11-01T04:41:59Z")

</div>

Hi there,  
I tried to find paths between 2 nodes, currently only k-shortest path queries could be used, the performance was not good when i queried with numpaths larger than 10.  
Is there any suggestion on that ?  
Why the performance lose a lot when numpaths become larger?  
Why the performance changed with depth 10?  
Any way to improve it?

I used the [dgraph-ha.yaml](https://github.com/dgraph-io/dgraph/blob/master/contrib/config/kubernetes/dgraph-ha.yaml) to deploy my dgraph  
and here’s my ql to query  
{  
path as shortest(from: 0x107db5, to: 0x138ac1, numpaths:10) {  
\_Concept  
~\_Concept  
\_MainProduct  
~\_MainProduct  
}  
path(func: uid(path)) {  
Name  
StockCode  
}  
}

here’s the results:  
10\<=numpaths\<=20 : 9.5s to 10s  
numpaths\<10 : 100 to 300ms

BTW, i used the HDD for this test

Thanks

---

<div class="post-metadata">

**Author:** ![kortschak](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/kortschak/32/1284_2.png) [@kortschak](https://discuss.dgraph.io/u/kortschak)\
**Post date:** [November 1, 2018, 5:50am UTC](https://discuss.dgraph.io/t/performance-is-not-good-when-finding-the-paths-between-2-nodes-with-k-shortest/3533/2 "2018-11-01T05:50:54Z")

</div>

k-shortest paths is not a particularly cheap calculation. Yen’s  
algorithm (I don’t know if dgraph uses this, but it likely uses  
something similar - it does look much more complicated than it needs to  
be though) has a time complexity of O(k|V|(|E|+|V|log|V|)).

---

<div class="post-metadata">

**Author:** ![peterZ](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/peterz/32/1357_2.png) [@peterZ](https://discuss.dgraph.io/u/peterZ)\
**Post date:** [November 1, 2018, 3:29pm UTC](https://discuss.dgraph.io/t/performance-is-not-good-when-finding-the-paths-between-2-nodes-with-k-shortest/3533/4 "2018-11-01T15:29:38Z")

</div>

> [@kortschak](#):
>
> -shortest paths

hi kortschark, thanks for your reply. With the time complexity, it should cost more time with larger k. But by my testing, the time didn’t change a lot when i changed the k to 10 or larger, it looks very strange. Do you have any idea on that?

---

<div class="post-metadata">

**Author:** ![kortschak](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/kortschak/32/1284_2.png) [@kortschak](https://discuss.dgraph.io/u/kortschak)\
**Post date:** [November 1, 2018, 8:58pm UTC](https://discuss.dgraph.io/t/performance-is-not-good-when-finding-the-paths-between-2-nodes-with-k-shortest/3533/5 "2018-11-01T20:58:15Z")

</div>

I’ve just had a closer look at the [code](https://github.com/dgraph-io/dgraph/blob/master/query/shortest.go), and despite the illegibility of it it’s reasonably clear that they are not using Yan, though they are doing similar work less efficiently.

I can’t see any discontinuity at 10 unless it’s something in the runtime (grow map?, though that seems unlikely) or something to do with the backing store (more likely).

---

<div class="post-metadata">

**Author:** ![peterZ](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/peterz/32/1357_2.png) [@peterZ](https://discuss.dgraph.io/u/peterZ)\
**Post date:** [November 2, 2018, 12:52am UTC](https://discuss.dgraph.io/t/performance-is-not-good-when-finding-the-paths-between-2-nodes-with-k-shortest/3533/6 "2018-11-02T00:52:17Z")

</div>

thanks for your info, i’ll try to find if there’s some limitation on the backing store

---

<div class="post-metadata">

**Author:** ![system](https://canada1.discourse-cdn.com/flex007/uploads/dgraph/original/2X/2/2b38fdece2abe5814f2e51bee69d1e67fc304b0a.png) [@system](https://discuss.dgraph.io/u/system)\
**Post date:** [December 2, 2018, 12:52am UTC](https://discuss.dgraph.io/t/performance-is-not-good-when-finding-the-paths-between-2-nodes-with-k-shortest/3533/7 "2018-12-02T00:52:20Z")

</div>

This topic was automatically closed 30 days after the last reply. New replies are no longer allowed.