Performance issue (or infinite loop)

[Abramo-Bagnara]

I've tried a variation of this example present in tutorial:

shortest[b, min(dist)] := *route{fr: 'LHR', to: b, dist} 
                          # Start with the airport 'LHR', retrieve a direct route from 'LHR' to b

shortest[b, min(dist)] := shortest[c, d1], # Start with an existing shortest route from 'LHR' to c
                          *route{fr: c, to: b, dist: d2},  # Retrieve a direct route from c to b
                          dist = d1 + d2 # Add the distances

?[dist] := shortest['YPO', dist] # Extract the answer for 'YPO'. 
                                 # We chose it since it is the hardest airport to get to from 'LHR'.

Changing it in this way:

shortest[a, b, min(dist)] := *route{fr: a, to: b, dist} 
shortest[a, b, min(dist)] := shortest[a, c, d1],
                          *route{fr: c, to: b, dist: d2},
                          dist = d1 + d2

?[dist] := shortest['LHR', 'YPO', dist]

Despite it should be an equivalent query I don't get any result in reasonable time in https://cozodb.github.io/wasm-demo/

I don't think it is expected, am I missing something?

[zh217]

Unfortunately this is how it is supposed to work now. Let me explain.

In your changed query, you are asking the database to compute the all-pair shortest path, and then extract the answer to a particular shortest path. Normally Cozo would apply a technique called magic set rewrite so that only the needed answer would be calculated. However, in your query the presence of the aggregation operator min prevents that. In this case, applying the rewrite would still yield the correct answer, but in the more general case with recursive aggregations this is a can of worms and mindlessly rewriting could lead to wrong results.

So as explained in the manual, magic set rewrites are only applied to rules without aggregations or recursions for the moment, until we are sure of the exact conditions under which the rewrites are safe. So for now at least the database executes your query as written, computing the result of the shortest rule containing more than ten million rows (to be exact, 3700 * 3700 = 13,690,000 rows) first.

The solution now is, to be careful of the cardinality of the return sets of recursive rules. In your case, if you really need to pre-compute the more than 10M rows (I highly doubt it), you should use the ShortestPathDijkstra algorithm, which is much faster (but still takes some time). Unfortunately you cannot use graph algorithms in WASM due to the lack of support for many critical functions on WASM that make graph algorithms run fast.

Hope this helps.

[zh217]

Perhaps the above explanation should be included in the tutorial to make people aware of this behaviour.