Last active
October 12, 2015 02:03
-
-
Save amosr/bda21128506944989a7c to your computer and use it in GitHub Desktop.
sapling icicle
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
When dealing large data sets that do not fit in memory, it is crucial to limit the number | |
of accesses and iterations over the data set. | |
However, in a high level language it may not be immediately obvious how many iterations a | |
particular program will require. | |
The number of iterations becomes even less obvious in the presence of heuristic and | |
statistics-based optimisations, as used by traditional databases: a small tweak to the query | |
or even modifying the number of rows in a table can cause drastic changes to the query plan. | |
With the advent of "big data", and as data sets continue to grow, a high level language with | |
predictable runtime characteristics becomes more necessary. | |
Programmers should not need to understand the internal workings of a database or query | |
optimiser in order to write fast queries. | |
We have designed and implemented Icicle, a query language specifically for single-pass queries. | |
This means that any query in our language is assured to compile into a single iteration | |
over the data set. | |
We use a type system based on temporal logic to ensure that queries can be executed in a | |
single pass without violating causality. | |
A fusion system based on our previous "flow fusion" work ensures that there is only a single | |
loop over the input data, with no unbounded buffering. | |
In this talk, we will introduce Icicle and some example queries. | |
We will show some example queries that would violate causality, and show how they are outlawed. | |
We will then describe the fusion system. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
"dealing with"