Techniques to reduce the execution time of a Prolog query by reordering the literals in the query

General
1

Dear all,

Are there any known techniques to reduce the execution time of a Prolog query by reordering the literals in the query?

Below is a silly example where the order of the literals changes the execution time:

p(1,K):- between(1, 100000, K).
q(0).
a:- p(A,B),q(B).
b:- q(B),p(A,B).

?- time(a).
% 200,005 inferences, 0.006 CPU in 0.006 seconds (100% CPU, 32734043 Lips)
false.

?- time(b).
% 5 inferences, 0.000 CPU in 0.000 seconds (32% CPU, 454545 Lips)
false.

Is anyone aware of an existing technique and ideally a link a paper describing it? Google search is failing me on this question. I can see ways to order the literals in a rule but without any strong guarantees.

Thanks

2

Well, coroutining could be used:

p(1, K) :- freeze(K, between(1, 100000, K)).

Results:

?- time(a).
% 13 inferences, 0.000 CPU in 0.000 seconds (87% CPU, 511247 Lips)
false.

?- time(b).
% 7 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 351459 Lips)
false.

Apologies if off-topic.

3

Sorry, I should have made it clear that the example above was only meant to illustrate the problem.

4

Still, coroutining can improve order dependency and so can tabling. I’ve done something as you describe for optimizing SPARQL queries as described in this ICLP’05 publication This requires estimates of cost and number of solutions per goal, as well as instantiation restrictions. Recently I have worked on an improved version, but I’m afraid that work is not public. The overall idea is to generate orderings, validate whether they are legal and compute a cost estimate. Then select the best.

Should be doable for a well defined subset of Prolog. Stats on facts can probably be estimated from the JIT index properties. Internally there are some more stats that drive the JIT index and that could be made available.

2 Likes
5

That link is perfect, thanks! I found a closely related paper (Query optimization in inductive logic programming by reordering literals) in the related work section.

Thanks again