[/Band|c00t] GettingStarted Specification Download Blog About
Fork me on GitHub

Performance of the Bandicoot v0

Published by Ostap Cherkashin on 2010 12 27.

The first cut of the Bandicoot database (v0) provides enough functionality to start building some applications. Though, as with any new system, there are several important questions arise: stability, performance, …? This blog post is about performance of the system. With regard to stability I can only say that even though there are quite some structured tests available, it is still not recommended for production use.

Execution

With the Bandicoot application developers control the execution path. This is fairly different from other databases where this responsibility is split between a human (programmer) and another "living organism" (query optimizer). It happens that sometimes they misunderstand each other and as a result we get two beliefs:</p>

I will try to address the first one here. With the second one (and having the v0 tag comment say "brute force preview") I will try to avoid the discussion for a little while ;-)

In relational algebra there is only one data structure (relation 1) and several operators (select, join, etc. 2). Relations represent your data and operators take these relations as input and produce different ones as an output. From the performance perspective one of the most important properties of a relation is the number of tuples (or rows) in its body. Execution time of an operator heavily depends on this number (it is also used to express the algorithmic complexity below). In order to improve a function performance one should try to reduce the data sets passed from one operator to another as early as possible. This is a fairly intuitive idea and it also greatly impacts the performance. To help with this and to facilitate the computation reuse the Bandicoot introduced temporary variables 3. Apart from improving performance they also make code more readable.

The table below lists the complexities for different relational operators in the Bandicoot v0. I will use #n as the number of tuples in a relation variable n.

Operator Sample Expression Big-O
join m * n O(#m * #n)
minus (semidiff) m - n O(#m * #n)
union m + n O(#m + #m*#n)
select n select(x < 0) O(#n)
extend n extend(x = 1) O(#n)
project n project(x, y) O(#n^2)
summary (m, n) summary(x = max(y, 0)) O(#m * #n)

As you can see most of the algorithms are of quadratic nature, and thus the limits of v0 are quite low in terms of number of tuples. I am working on the patch to improve this situation, and meanwhile you can master the temporary variables which is a good practice in any case.

 Figures

To turn the formulas above into the actual numbers you can use the performance tests available with the system source code. One of the interesting ones is perf/relation. It shows the execution times for some of the workloads on different relational operators. Here is the output from a run on my laptop (core i7 @2GHz and -Os gcc option). Note, that all of the test tuples have two attributes (string and integer) and are pre-generated before each test execution.

$ cd bandicoot
$ ctl pack
$ bin/test/perf/relation
   write 100000 tuples in 18ms
    read 100000 tuples in 21ms
   write 1000000 tuples in 135ms
    read 1000000 tuples in 175ms
    join 1000x1000 tuples in 20ms
    join 10000x10000 tuples in 1786ms
semidiff 1000x1000 tuples (res=500 tuples) in 15ms
semidiff 10000x10000 tuples (res=5000 tuples) in 1533ms
 project 1000 tuples from 1000 in 9ms
 project 10000 tuples from 10000 in 876ms
  select 1 tuples from 100000 in 11ms
  select 1 tuples from 1000000 in 97ms
   union 1000x1000 tuples (res=1500 tuples) in 20ms
   union 10000x10000 tuples (res=15000 tuples) in 1752ms
  extend 100000 tuples in 37ms
  extend 1000000 tuples in 372ms
     sum 1000x1000 tuples in 20ms
     sum 10000x10000 tuples in 1817ms

The first rows show the read/write performance for a data volume (I have an SSD drive + there are no fsync/fdatasync calls). The rest are the execution times of the relational operators.

 Resources

  1. read more about relations on wikipedia or in the spec
  2. more about the algebra on wikipedia or in the spec
  3. learn more about temporary variables on the getting started page or in the spec