search

typedb / typedb-studio

TypeDB Studio (IDE)
https://typedb.com
Mozilla Public License 2.0
191 stars 43 forks source link

Control Graph Layout Duration #596

Open mathieuisabel opened 2 years ago

mathieuisabel commented 2 years ago

Problem to Solve

When a query returns a significant amount of data, studio spends a significant amount of time (several minutes)/CPU resources trying to layout the graph. While that's happening, Studio becomes unresponsive and you cannot start exploring the query result graph.

Current Workaround

Limit amount of data returned.

Proposed Solution

It might be good to have a button at a minimum to interrupt the graph layout operation when the layout looks good enough.

Additional Information

This happened with about ~25K things returned.

I return a large number of item to visually see things with a lot of edges to zoom-in, investigate further. I might be doing another query to scope around that finding as a subsequent step.

Is the renderer using the GPU? It seems this is very CPU bound and not GPU bound.

mathieuisabel commented 2 years ago

Might be related to #563

jamesreprise commented 2 years ago

Also somewhat related to https://github.com/vaticle/typedb-studio/issues/435

alexjpwalker commented 2 years ago

Is the renderer using the GPU? It seems this is very CPU bound and not GPU bound.

Drawing shapes onto the graph is GPU-accelerated, computing their positions (via physics engine) is CPU-parallelised.

Performance of physics engine is O(n*log(n)) where n is the number of vertices; edges have a negligible impact. Currently we consider the performance to be strong up to 5k vertices and acceptable up to 10k. If visualising more than 10k vertices, expect significant slowdown.

It might be good to have a button at a minimum to interrupt the graph layout operation when the layout looks good enough.

As you say, this is a "minimal" solution, however the graph layout has already been optimised to the point at which we can't realistically optimise any further and guarantee a "correct" layout. We can certainly implement an interrupt button, but it would result in an inaccurate layout, which makes me reluctant to offer it as a band-aid.

I would suggest the workaround of limiting the result size for now - is a 25k-vertex graph useful to visualise? Intuitively there comes a point where the visualisation is pretty, but not hugely meaningful.

mathieuisabel commented 2 years ago

Maybe the option is not so much interrupting but controlling how much you want the physics engine to come up with the "perfect" layout. Maybe something like a quick/balanced/perfect slider would achieve that. I did encounter on a few occasion even with less nodes ~500-1000s where I got annoyed with the graph elements still trying to position themselves as I was trying to zoom in on those. i.e. the rough layout was there and the highly connected things were properly positioned but the physics engine was trying to constantly fine tune the positioning. i.e. moving by just a number of pixel.

So I think there is a range of how much of a problem that is. It goes from annoying to blocking (at scale).

I was looking again at the 3d-force-graph component as a comparison. You can see a demo here with 4k nodes but I did a local test using 22k vertices and ~2200 edges as a quick test by just copying over and over the data that was in the file. It took about 15s to layout the graph. It still looked CPU bound to a certain degree but not too bad. Maybe a good reference point.

Here's where that stuff is: https://vasturiano.github.io/3d-force-graph/example/large-graph/ https://github.com/vasturiano/3d-force-graph https://github.com/vasturiano/d3-force-3d

alexjpwalker commented 2 years ago

There is a known issue currently impacting the performance of small graphs as well:

I've also updated the following issue based on this report.