Query with a lot of entities and relations between them takes unreasonable time to compute

[VladGan]

Description

"Chain" type of query, where we have a line of entities connected with a parent-child relation (10 entities with 9 relations between them) takes an infinite time to compute. Even with 5 entities it never finished the computation

What we are querying for looks like this:

  O         <- commit
  |         <- commit-link
  O         <- commit
  |         <- commit-link
  O        ...
  |
  O
  |
  O
  |
  O
  |
 ...
  |
  O

The query:

match
$commit-0 isa commit, has sha $sha-0, has symbol "VladGan/console@4bdc38acb87f9fd2fbdb7cbcf2bcc93837382cab";
$_ (next: $commit-0, previous: $commit-1) isa commit-link;
$commit-1 isa commit, has sha $sha-1;
$_ (next: $commit-1, previous: $commit-2) isa commit-link;
$commit-2 isa commit, has sha $sha-2;
$_ (next: $commit-2, previous: $commit-3) isa commit-link;
$commit-3 isa commit, has sha $sha-3;
$_ (next: $commit-3, previous: $commit-4) isa commit-link;
$commit-4 isa commit, has sha $sha-4;
$_ (next: $commit-4, previous: $commit-5) isa commit-link;
$commit-5 isa commit, has sha $sha-5;
$_ (next: $commit-5, previous: $commit-6) isa commit-link;
$commit-6 isa commit, has sha $sha-6;
$_ (next: $commit-6, previous: $commit-7) isa commit-link;
$commit-7 isa commit, has sha $sha-7;
$_ (next: $commit-7, previous: $commit-8) isa commit-link;
$commit-8 isa commit, has sha $sha-8;
$_ (next: $commit-8, previous: $commit-9) isa commit-link;
$commit-9 isa commit, has sha $sha-9;
get $sha-0, $sha-1, $sha-2, $sha-3, $sha-4, $sha-5, $sha-6, $sha-7, $sha-8, $sha-9;

Database and schema:

https://www.dropbox.com/home/Engineering/Grabl/Issues/Grakn-2.0%20issues/6183

[haikalpribadi]

I've reproduced this bug, @flyingsilverfin, surprise, surprise: it's type resolver that's not returning :slight_smile:

With a 6 hop chain, the run time is:

Type resolver:
- optimiser: 216 millis
- traversal: 6 seconds

Query traversal:
- optimiser: 50 millis
- traversal: 18 millis

All traversal plans, for 1, 2, 3, 4, 5, 6 hop chains ALWAYS start from attribute vertex with the sha . I think we can have more faith in query planner (really 😄 ).

Let's prioritise this bug tomorrow. Type resolver is becoming a detrimental bug now. These "multi-hop" queries aren't even very long. We should expect them to be common. But type resolver has been wrongly designed to carry this "permutative" behaviour, I think. I don't know the algorithm from the heart, but hasn't really been well thought out I think.

[haikalpribadi]

This issue will be solved by #6194. I will work on it next week, and have it out in the subsequent release.

[dmitrii-ubskii]

Resolved by #6194.