SQuOpt—The Scala Query Optimizer—Paolo G. Giarrusso

Introduction

This is the homepage for the Scala Query Optimizer research project, SQuOpt.

Often developers need to manually optimize computations on collections at the expense of readability and modularity. In the SQuOpt project we reuse and extend optimizations known in the database community to apply them over such collections and enjoy the modularity advantages.

Concretely, SQuOpt allows to write queries on Scala collections and run optimizations on them. Queries are expressed through a quite natural syntax, almost identical to the syntax for Scala for comprehensions; however, executing such for comprehensions yields a representation of the query, which can then be optimized.

This website will continue being updated.

What we provide

Source code of our implementation, on GitHub.
the version of FindBugs we compared our results with.
a technical report accompanying our paper submission, also available on arXiv.

Additionally, we will provide the evaluation data from our new paper submission, including the raw dataset and scripts to regenerate the graphics and the tables.

The source code for which the evaluation was run corresponds to version aosd13-evaluated.

The raw evaluation data from a previous evaluation is already available.

Credits

This project benefited from code and ideas of many different people:

Paolo G. Giarrusso (project leader)
Klaus Ostermann
Michael Eichberg
Ralf Mitschke
Tillmann Rendel
Christian Kästner
Sebastian Erdweg
Katharina Haselhorst
Cai Yufei

News

2012-12-11: our paper submission was accepted for AOSD ’13!
2012-10-25: link to technical report on arXiv.
2012-10-23: technical report published.
2012-10-12: began to update website, with link to GitHub sources.
2012-04-26: added FindBugs source code and some details on reproducing the evaluation
2012-04-23: website online

Code from our paper

Examples from our paper are implemented and tested in class ivm.tests.PaperTutorial.

Old evaluation

The code is located in class performancetests.opaltests.FindBugsAnalyses.

We provide the raw data collected, together with the script used to produce the tables included in the paper, based on R and runnable on Unix systems such as Mac OS X and probably Linux. Here they are.

For those interested only in the resulting graphs, here are the results.

In our evaluation, we compare our source code analyses with a reference implementation, namely FindBugs. We altered its source code to disable unrelated analyses, and provide the altered code.

To ensure reproducibility, we plan to simplify and document the exact steps needed to reproduce our results.

For the determined impatient, here is the current procedure, which will probably have a few rough edges and is still untested.

select a idle and sufficiently powerful machine with a *x operating system - the evaluation takes currently 1 day and was run on a Linux machine; the statistics were computed on a Mac OS X machine. The scripts should work (with minor changes) on any *x system with the needed software.
download both our source release, our evaluation code, and R.
choose the test data to use—we provide a test harness to run the evaluation on ScalaTest, that is profileLos.sh, or on the JDK, that is profileLosJDK.sh.
To reproduce the original evaluation, you need to use the JDK. The binary library is in fact available in data/rt.jar.
- Download the version which was installed on our machine and extract it, using for instance rpm2cpio (we plan to simplify this step).
- Adjust profileLosJDK.sh to find the copy of classes.jar from the extracted package.
Run the chosen test harness. You might need to comment out any invocations to git; the software assumes to be run on a git working copy.
After the end, move and rename the resulting LOSTestLog-JDK.csv or LOSTestLog-ScalaTest.csv as LOSTestLog-JDK-new-eval.csv inside squoptEval-v0.2 (the folder of the extracted evaluation).
In the same directory, run make newgraph, which will save the reproduced evaluation results by overwriting EvalRed-new.pdf.

Contacts

For any question or suggestion, feel free to contact me, Paolo G. Giarrusso, at pgiarrusso (at) informatik !dot! uni-marburg !dot! de.