Reasoner planner struggles on small ruleset

[krishnangovindraj]

Description

The subgraph plan search assumes that the subgraph is small enough to brute-force the planning. This assumption is brittle, and exposed by the schema & data linked to below:

Environment

1. OS (where TypeDB server runs): Any
2. TypeDB version (and platform): 2.20
3. TypeDB client: Any
4. Other environment details:

Reproducible Steps

Steps to create the smallest reproducible scenario:

1. Import the schema & data linked
2. Run the query

match
    $e isa ul-entity, has id "Brie";
    $t isa ul-entity, has id "Cheese";
    $v isa verb, has id "IsA";
    $r (verb: $v, arg0: $e, arg1: $t) isa ul-verb;
get $r;

Expected Output

Immediate answers, given the universe of things is tiny.

Actual Output

The reasoner planner searches an intractably large search space for subgraph plans.

Additional information

We optimised the ordering search to use A* (in place of an almost-brute-force partial-order-reduction search), but did not touch the subgraph plan search. We can likely save a lot by caching results for intermediate values of pendingCalls or other more efficient search algorithms.

verbs_data_schema.zip