COLUMBIA UNIVERSITY COMS 6113

Overview

Overarching Questions

Three phases

It’s worth noting that a 10x over a legacy architecture is lame. A 10x win over recent state of the art is impressive. This paper is somewhat in-between, with 2-4x wins over Vectorwise. That’s still impressive!

Krikellas et al

Overview

Why compilation?

Limitations

Hyper LLVM paper

Overview

Philosophy

Pipelines and pipeline breakers

Experiments

Query Compiler Revisited

Overview

Let’s take a look at two ideas that help contextualize what produce consume are actually trying to do:

Callback-based execution and query compilation

	data = [ dict(a=0), dict(a=1), dict(a=2)]

	def cond(row):
		return row['a'] == 1
		
	def filter_run(cb):
		def f(row):
			if cond(row):
				cb(row)
		scan_run(f)
		
	def scan_run(cb):
		for row in data:
			cb(row)

	def print_run(row):
		print row

	filter_run(print_run)

Consider when scan_run’s inner loop runs. What if we inline all of the callbacks?

    # in scan:
    for row in data:
      cb(row)

Inline cb’s code:

    for row in data:
      if cond(row):
        cb(row)  # filter_run's callback

Inline the cond and cb functions:

    for row in data:
      if row['a'] == 1:
        print row

This is the same result as implementing produce consume.

Interpretors and Query Compilation

Idea

The basics:

    def pow(x, n):
      if n == 0:
        return 1
      return x * pow(x, n-1)

Let’s say we ran pow(2, 2), then there are lots of function calls etc. The snippet below shows the nested execution trace:

    call pow(2, 2)
      if 2 == 0: pass

      arg1 = 2 - 1
      res1 = pow(2, arg1)
      call pow(2, 1)
        if 1 == 0: pass

        arg2 = 1 - 1
        res2 = pow(2, arg2)
        call pow(2, 0)
          if 0 == 0:
            return 1       # res2 = 1
        return 2 * res2    # x * res2;   res1 = 2
      return 2 * res1        # x * res1;   output is 4

That is pretty expensive, but what if we replaced x with an object that works the same way, but keeps track of all operators performed on it?

    call pow(x, 2)
      if 2 == 0: pass
      arg1 = 2-1
      res1 = pow(x, arg1)
      if 1 == 0: pass
      arg2 = 1-1
      res2 = pow(x, arg2)
      if 0 ==0:
        res2 = 1
      res1 = x * res2    # x tracks that "x * 1"
    return x * res1      # x tracks that "x * (x * 1)"

    # operations performed on x are:
      x * (x * 1)

In practice, you need to track all operations performed on x. Something like:

    class Int
      def __init__(self, varname):
        self.varname = varname

      def __mul__(self, y):
        varname = new_varname()
        print "%s = %s * %s" % (varname, self.varname, y.varname)
        return Int(varname)

Let’s look at iterator approach

    filter(child, cond):
      for row in child:
        if cond(child):
          yield child

    scan():
      for row in accessmethod():
        yield child