MARTIN-LUTHER-UNIVERSITÄT HALLE-WITTENBERG
Institut für Informatik
Prof. Dr. Stefan Brass

Implementation Alternatives for Bottom-Up Evaluation

(Download Page for Example Programs, Under Construction, Last Change: July 14, 2010)

 


Paper


A first report about this research appeared as:

Stefan Brass: Implementation Alternatives for Bottom-Up Evaluation.
Technical Communications of the 26th International Conference on Logic Programming (ICLP'10)
Manuel Hermenegildo and Torsten Schaub (Eds.)
Leibniz International Proceedings in Informatics (LIPIcs), Vol. 7, pages 44-53,
ISBN 978-3-939897-17-0, ISSN 1868-8969,
Schloss Dagstuhl, 2010.
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2582/, DOI: 10.4230/LIPIcs.ICLP.2010.44.

There is also a Technical Report version of this paper with an appendix that explains the performance tests: PDF, Postscript.

Here are the slides for my short talk at ICLP 2010: PDF (preliminary version).

 


Test 1: Basic Comparison, Push Implementation Variants


Logic Program

p3(X, Z) :- p2(X, Y), q(Y, Z).
p2(X, Z) :- p1(X, Y), q(Y, Z).
p1(X, Z) :- p0(X, Y), q(Y, Z).
p0(X, Y) :- r(X, Y).

Test Data (EDB Predicates)

q = {(i, i+1) | 1 <= i <= 5000 }
r = {(i, i) | 1 <= i <= 5000 }

Program Code

Runtimes

MethodWindows PCLinux Server Solaris Server
Method 1: Materialization 515ms 380ms 430ms
Method 2: Pull 937ms 320ms 930ms
Method 3: Push (no opt.) 562ms 250ms 950ms
Method 3: Push (with opt.) 546ms 250ms 950ms
Method 3: Push (static) 578ms 220ms 1100ms
Method 3: Push (local) 515ms 250ms 490ms
Method 3: Push (main) 515ms 240ms 330ms

Test Machines

 


Test 2: Loop Order, Passing Bindings


Logic Program

p3(X, Z) :- q(X, Y), p2(Y, Z).
p2(X, Z) :- q(X, Y), p1(Y, Z).
p1(X, Z) :- q(X, Y), p0(Y, Z).
p0(X, Y) :- r(X, Y).

Test Data (EDB Predicates)

q = {(i, i+1) | 1 <= i <= 5000 }
r = {(i, i) | 1 <= i <= 5000 }

Program Code

Runtimes

MethodWindows PCLinux Server Solaris Server
Method 1: Materialization 781ms 830ms 1950ms
Method 2: Pull (size 200 instead 5000) 24843ms 3400ms 19660ms
Method 3: Push (no opt., local vars) 531ms 290ms 340ms
Method 4: Push+Bindings 609ms 260ms 330ms

 


Test 3: Using Keys


Logic Program (same as in Test 2)

p3(X, Z) :- q(X, Y), p2(Y, Z).
p2(X, Z) :- q(X, Y), p1(Y, Z).
p1(X, Z) :- q(X, Y), p0(Y, Z).
p0(X, Y) :- r(X, Y).

Test Data (EDB Predicates)

q = {(i, i+1) | 1 <= i <= 5000 }
r = {(i, i) | 1 <= i <= 5000 }

Program Code

Runtimes

MethodWindows PCLinux Server Solaris Server
Method 1: Materialization 390ms 360ms 740ms
Method 3: Push (no opt., local vars, other key) 250ms 110ms 230ms
Method 4: Push+Bindings 281ms 110ms 180ms
Method 4: Push+Bindings: Function 265ms 110ms 190ms

 


Test 4: Using Ordering, Merge Join


Logic Program (same as in Test 2)

p3(X, Z) :- q(X, Y), p2(Y, Z).
p2(X, Z) :- q(X, Y), p1(Y, Z).
p1(X, Z) :- q(X, Y), p0(Y, Z).
p0(X, Y) :- r(X, Y).

Test Data (EDB Predicates): Note the increase to one million!

q = {(i, i+1) | 1 <= i <= 1000000 }
r = {(i, i) | 1 <= i <= 1000000 }

Program Code

Runtimes

MethodWindows PCLinux Server Solaris Server
Method 1: Materialization 765ms 710ms 1710ms
Method 2: Pull 93ms 10ms 90ms
Method 3: Push 78ms 20ms 80ms

 


Test 5: Disjunctions, Larger Tuples


Logic Program

p1(A) :- q(A).
p2(A,1) :- p1(A).
p2(A,2) :- p1(A).
p3(A,B,1) :- p2(A,B).
p3(A,B,2) :- p2(A,B).
p4(A,B,C,1) :- p3(A,B,C).
p4(A,B,C,2) :- p3(A,B,C).
p5(A,B,C,D,1) :- p4(A,B,C,D).
p5(A,B,C,D,2) :- p4(A,B,C,D).
p6(A,B,C,D,E,1) :- p5(A,B,C,D,E).
p6(A,B,C,D,E,2) :- p5(A,B,C,D,E).
p7(A,B,C,D,E,F,1) :- p6(A,B,C,D,E,F).
p7(A,B,C,D,E,F,2) :- p6(A,B,C,D,E,F).

Test Data (EDB Predicates):

q = {i | 1 <= i <= 50000 }

Program Code

Runtimes

MethodWindows PCLinux Server Solaris Server
Method 1: Materialization 1562ms 1220ms 41500ms
Method 2: Pull 390ms 20ms 100ms
Method 3: Push 453ms 300ms 400ms
Method 3: Push (with optimization) 171ms 100ms 150ms

 


Test 6: Strings, Large Records


Logic Program (same as in Test 1)

p3(X, Z) :- p2(X, Y), q(Y, Z).
p2(X, Z) :- p1(X, Y), q(Y, Z).
p1(X, Z) :- p0(X, Y), q(Y, Z).
p0(X, Y) :- r(X, Y).

Test Data (EDB Predicates): Strings of Length 20 in Array of Length 1000

q = {(ABCDEFGHIJKLMNO-<i>, ABCDEFGHIJKLMNO-<i+1>) | 1 <= i <= 5000 }
r = {(ABCDEFGHIJKLMNO-<i>, ABCDEFGHIJKLMNO-<i>) | 1 <= i <= 5000 }

Program Code

Runtimes

MethodWindows PCLinux Server Solaris Server
Method 1: Materialization 6453ms 4280ms 12620ms
Method 2: Pull 6906ms 3600ms 12210ms
Method 3: Push 5985ms 3590ms 12450ms

Remarks

 


Test 7: Example from Paper


Logic Program

p(X, Z, 2) :- q(X, Y), r(Y, 5, Z).
q(X, Y) :- s(X, Y), Y >= 0.

Test Data (EDB Predicates):

r = {(i,j,k) | 1 <= i <= 10000, 1 <= j <= 100, 1 <= k <= 100}
     r can be accessed with binding pattern bff (index on first argument).
s = {(i,i) | 1 <= i <= 10000 }.

Program Code

Runtimes

MethodWindows PCLinux Server Solaris Server
Method 1: Materialization 921ms 490ms 1550ms
Method 2: Pull 843ms 140ms 1340ms
Method 3: Push 812ms 170ms 1360ms

 


Test 8: Recursion (seminaive, no eliminiation of duplicates necessary)


Logic Program

p(X, Y) :- q(X, Y).
p(X, Z) :- q(X, Y), p(Y, Z).

Test Data (EDB Predicates):

q = {(i, i+1) | 1 <= i <= 1000 }

Program Code

Runtimes

MethodWindows PCLinux Server Solaris Server
Method 1: Materialization 5468ms 1150ms 5310ms
Method 2: Pull with Bindings 10859ms 2780ms 39180ms
Method 3: Push 4359ms 840ms 7080ms

 


Note:


 

To be continued: More Tests follow soon (especially more recursive ones) ...

 


Stefan Brass (brass@acm.org), 27. February 2010

Original URL: http://www.informatik.uni-halle.de/~brass/botup/   [XHTML 1.0 Checked]   [Links checked]