2
$\begingroup$

The traditional way to implement a SQL database is to parse the query, create a parse tree, and then evaluate it using the "volcano" model. In this model you call .next() on the root node of the tree to get the next tuple, and each node calls .next() on its child nodes, percolating the tuple up the tree.

In 2011 Efficiently Compiling Efficient Query Plans for Modern Hardware introduced the data-centric "push" model of query evaluation. The theory is that calling .next() over and over again is costly, and leads to poor data locality. Instead, the author suggests a model in which children push tuples to parents using a tight loop.

A number of other papers have cited this paper and all seem to think it's the way to go. They suggest huge speedups for in-memory databases.

This makes no sense to me. Pushing a tuple up the tree will require just as many function calls as pulling it from down the tree. And in nodes where tuples need to be accumulated instead of pushing them one at a time ("pipeline breakers") both models are going to behave identically.

So I benchmarked it, push vs. pull vs hand-rolled code. I used a slight variation on the push model suggested by How to Architect a Query Compiler, Revisited in which you pass callbacks down the tree.

I simulate the evaluation of this query, select right.a, right.b from left, right where left.b > 90 and left.a = right.a;, where each table has 10 million randomly-generated in-memory rows.

Here are the results (Java 11, on a Mac Mini):

push rows per run:8606256.0 elapsed: 147932 millis. 1479.32 millis per cycle.
pull rows per run:8606256.0 elapsed: 141929 millis. 1419.29 millis per cycle.
hand rolled rows per run:8606256.0 elapsed: 137589 millis. 1375.89 millis per cycle.

Bottom line: almost zero difference among all three implementations. Certainly not the orders-of-magnitude suggested by some of the papers.

So what am I missing here? Is push evaluation nonsense? Have I implemented the benchmark code wrong? Or is the JVM so smart it just optimized out all the calls to .next() and the push model has no advantages? (I kind of doubt it, because the author used Scala on the JVM which should get all the same optimizations.)

Here's the benchmark code:

public class BenchmarkPushModel {

    // select right.a, right.b from left, right where left.b > 90 and left.a = right.a;

    final static int ROW_COUNT = 10000000;
    final static int RUN_COUNT = 100;
    final static int LEN_STRING_FIELD = 4;
    final static int MAX_VAL_INT_FIELD = 100;
    final static int INT_FIELD_PREDICATE_THRESHOLD = 90;

    Random rand = new Random(0);
    int rowsOut;
    String label;
    long start;


    public static void main(String [] args) {
        BenchmarkPushModel b = new BenchmarkPushModel();
        b.go();
    }

    private void go() {
        List<Row> leftRows = makeRows();
        List<Row> rightRows = makeRows();

        start("push");
        rowsOut = 0;
        for (int run = 0; run < RUN_COUNT; run++) {
            PushOp pushOp = new PushHashJoin(new PushFilter(new PushScan(leftRows)), new PushScan(rightRows));
            pushOp.exec(row -> {
                rowsOut++;
            });
        }
        end("push rows per run:" + ((float)rowsOut / RUN_COUNT), RUN_COUNT);

        start("pull");
        rowsOut = 0;
        for (int run = 0; run < RUN_COUNT; run++) {
            PullOp pullOp = new PullHashJoin(new PullFilter(new PullScan(leftRows)), new PullScan(rightRows));
            pullOp.open();
            while (true) {
                Row row = pullOp.next();
                if (row == null) {
                    break;
                }
                rowsOut++;
            }
        }
        end("pull rows per run:" + ((float)rowsOut / RUN_COUNT), RUN_COUNT);

        // hand rolled code
        start("hand rolled");
        rowsOut = 0;
        for (int run = 0; run < RUN_COUNT; run++) {
            HashMap<String, Row> map = new HashMap<>();
            for (Row row : leftRows) {
                if (row.b > INT_FIELD_PREDICATE_THRESHOLD) {
                    map.put(row.a, row);
                }
            }
            for (Row row : rightRows) {
                if (map.get(row.a) != null) {
                    rowsOut++;
                }
            }
        }
        end("hand rolled rows per run:" + ((float) rowsOut / RUN_COUNT), RUN_COUNT);

    }


    private List<Row> makeRows() {
        List<Row> rows = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < ROW_COUNT; i++) {
            Row row = new Row();
            sb.setLength(0);
            for (int j = 0; j < LEN_STRING_FIELD; j++) {
                sb.append((char)(rand.nextInt(26) + 'a'));
            }
            row.a = sb.toString();
            row.b = rand.nextInt(MAX_VAL_INT_FIELD);
            rows.add(row);
        }
        return rows;
    }

    class Row {
        String a;
        int b;
        public String toString() {
            return a + " " + b;
        }
    }

    /////////////////////////////////////////////////////
    // Pull Ops
    interface PullOp {
        void open();
        Row next();
    }

    class PullScan implements PullOp {

        Iterator<Row> it;

        PullScan(List<Row> rows) {
            this.it = rows.iterator();
        }

        @Override
        public void open() {
        }

        @Override
        public Row next() {
            if (it.hasNext()) {
                return it.next();
            }
            return null;
        }

    }

    class PullFilter implements PullOp {

        PullOp child;

        public PullFilter(PullOp child) {
            this.child = child;
        }

        @Override
        public void open() {
            child.open();
        }

        @Override
        public Row next() {
            while (true) {
                Row row = child.next();
                if (row == null) {
                    return null;
                }
                if (row.b > INT_FIELD_PREDICATE_THRESHOLD) {
                    return row;
                }
                continue;
            }
        }
    }

    class PullHashJoin implements PullOp {
        PullOp left;
        PullOp right;
        HashMap<String, Row> map = new HashMap<>();

        public PullHashJoin(PullOp left, PullOp right) {
            this.left = left;
            this.right = right;
        }

        @Override
        public void open() {
            left.open();
            right.open();

            // make the hash of the left table
            while (true) {
                Row row = left.next();
                if (row == null) {
                    break;
                }
                map.put(row.a, row);
            }
        }

        @Override
        public Row next() {
            while (true) {
                Row row = right.next();
                if (row == null) {
                    return null;
                }
                if (map.get(row.a) != null) {
                    return row;
                }
            }
        }

    }



    /////////////////////////////////////////////////////
    // Push Ops


    interface PushCallback {
        public void accept(Row row);
    }

    interface PushOp {
        public void exec(PushCallback cb);
    }

    class PushScan implements PushOp {

        List<Row> rows;

        PushScan(List<Row> rows) {
            this.rows = rows;
        }

        @Override
        public void exec(PushCallback cb) {
            for (Row row: rows) {
                cb.accept(row);
            }
        }

    }

    class PushFilter implements PushOp {

        PushOp child;

        public PushFilter(PushOp child) {
            this.child = child;
        }

        @Override
        public void exec(PushCallback cb) {
            child.exec(row -> {
                if (row.b > INT_FIELD_PREDICATE_THRESHOLD) {
                    cb.accept(row);
                }
            });
        }
    }

    class PushHashJoin implements PushOp {
        PushOp left;
        PushOp right;

        public PushHashJoin(PushOp left, PushOp right) {
            this.left = left;
            this.right = right;
        }

        @Override
        public void exec(PushCallback cb) {

            // make the hash of the left table
            HashMap<String, Row> map = new HashMap<>();
            left.exec(row -> {
                map.put(row.a, row);
            });

            right.exec(row -> {
                if (map.get(row.a) != null) {
                    cb.accept(row);
                }
            });

        }

    }


    public void start(String label) {
        this.label = label;
        this.start = System.currentTimeMillis();
    }

    public void end(String label, long count) {
        long elapsed = System.currentTimeMillis() - start;
        System.out.println(label + " elapsed: " + elapsed + " millis. " + (((double)elapsed) / count) + " millis per cycle." );
    }



}
$\endgroup$
4
  • 1
    $\begingroup$ There's a lot more to the paper than just inverting the direction of data flow. In particular, "data-centric" != "push-based". It's also talking about compilation technology. The "push" model is one way of enabling a "data-centric" approach. Even then, the abstraction is compiled away. Simply using the "push" model is not being "data-centric". Being "data-centric" as meant in this paper means compiling code to minimize spilling row data out of registers. Your code is not doing this at all. It's not even clear that your "hand rolled" code is attempting to minimize register spills. $\endgroup$ Nov 24, 2018 at 3:44
  • $\begingroup$ @DerekElkins, that sounds like a useful answer, one that is more appropriate in the answer section than as a comment -- would you care to write it as an answer so we can vote on it? $\endgroup$
    – D.W.
    Nov 25, 2018 at 2:03
  • $\begingroup$ I'm confused: most realistic SQL queries will be able to go via indexes. Then using 'full table scans' (however they're iterating) is already being unrealistic. Also I'm not seeing why anything in Java is relevant: tight loops for any serious DB engine will surely be hand-crafted in machine code/customised for the archtecture. $\endgroup$
    – AntC
    Nov 25, 2018 at 9:31
  • $\begingroup$ @DerekElkins Can you give an example of how the hand-rolled code could be written differently to minimize register spills? Also, I found another paper that seems to agree with my assessment: arxiv.org/abs/1610.09166. Your comments on it would be welcome. $\endgroup$
    – ccleve
    Nov 25, 2018 at 17:59

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.