Skip to content
A scala rewrite of the AQuery system
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
project
src
README.md
build.sbt

README.md

AQuery to Q (A2Q)

A2Q is a project that explores order-based optimizations for a simple query language. Optimizations are mainly targeted as AST rewrites and, though simple, yield empirical advantages at runtime.

It compiles AQuery into q, providing users with two advantages:

  • Allows users to query kdb+ databases with a syntax similar to SQL
  • Heuristic, order-based optimizations, which provide performance advantages, while maintaining readability in the source code
  • Transparent compilation into q code (allowing experienced users to inspect the code executed)

The transformations on queries provide the same semantics at a fraction of the cost. These involve: pushing selections below sorting, removing unnecessary sorts, maintaining order across local tables, amongst others.

Updates

This is a clean, Scala-based, rewrite of the AQuery system. The original implementation was developed in C. Note that the C implementation is no longer being supported and we encourage users to switch to the Scala version.

Installation/Building

If you are interested in using AQuery, the steps below should provide you with all the information needed to build on your system. Note that A2Q is meant for *nix. There are no plans on making this available for windows.

As AQuery currently compiles into q code, it is essential to have the kdb+ executable installed. You can visit kx systems to download the appropriate version for your machine. For licensing reasons, we cannot include this for you. However, the process is simple.

Once you install q, make sure you add its installation location to your path.

export PATH=$PATH:/my/q/installation/location/

Calling which q should echo back the appropriate location, if added succesfully.

Most uses of q in examples/demos will assume you have this appropriately setup.

Compilation of the AQuery translator is straightforward and handled exclusively by sbt (the Scala build tool used in the project). Installing sbt is straightforward and there are plenty of resources online. Once you have sbt installed it is a simple as

The first step is to clone this git repository

git clone git@github.com:josepablocam/aquery.git

You can then build by running

cd aquery/
sbt assembly

This will save the AQuery jar as target/scala-2.11/aquery.jar.

To get basic usage information you can run

java -jar aquery.jar -h

For convenience, we recommend creating a simple bash script that wraps the call to java and adding this to your path.

cat ./a2q
#!/bin/bash
java -jar target/scala-2.11/aquery.jar $*

For following examples, we assume that we have this script available by the name a2q and you have added the location of the script to your PATH variable (so that you can call as simply a2q).

The most common command will likely be translating AQuery to q code, with optimizations. This can be achieved with

a2q -a 1 -s -c -o my_output_file.q my_input_file.a

or equally

a2q -a 1 -s -c my_input_file.a > my_output_file.q

(Note that the file endings are not significant).

Basic Grammar

The grammar for AQuery is simple and should be familiar to most people familiar with SQL. A good way to get a thorough overview of the grammar is to explore the parser rules in src/parser/aquery.y. These are written for Bison, and should be fairly readable. We provide a simple summary here of the most frequently used constructs: queries, data creation, loading/saving data, and user-defined functions. We use ID to stand for identifier, and epsilon to stand for the standard notation.

program : [full-query | create | insert | load | dump | udf | verbatim-q]*

// aquery files allow standard q code within special markers
verbatim-q: <q> q code </q>

/********* Queries *********/
full-query : [local_queries] query

local_queries: WITH local_query+

local_query: ID ['('columns')'] AS '(' query ')'

query : SELECT projections FROM source order-clause where-clause groupby-clause

projections: [val as ID | val] (, [val as ID | val])*

source : ID [ID | AS ID] |
  ID INNER JOIN source USING (columns) |
  ID FULL OUTER JOIN source USING (columns) |
  fun_call

// fun can be verbatim-q function constructing table
// or FLATTEN/DISTINCT/CONCATENATE
fun_call: fun'('val (,val)*')'

order-clause: ASSUMING ([ASC|DESC] ID)+

where-clause: WHERE search-conditions;

groupby-clause: GROUP BY val [as ID] (, val [as ID])* [HAVING search-conditions]

// where search condition is a boolean-yielding expression
search-conditions: search-condition (AND search-condition)*;

/********* Creating data *********/
create: CREATE TABLE ID [AS query | '(' schema ')']
schema: ID type (, ID type)*

insert: INSERT INTO ID [query | VALUES '(' vals ')']
vals: val (, val)*;

/********* Loading/Saving data *********/
load: LOAD DATA INFILE str INTO TABLE ID FIELDS TERMINATED BY str

save: query INTO OUTFILE str FIELDS TERMINATED BY str

/********* User defined functions *********/
udf: FUNCTION ID '(' arg-list ')' '{' fun-body '}'
arg_list: ID (, ID)*
fun_body: val | ID := val;

/********* Expressions *********/
val: val binop val | fun_call | -val | ID | int |
  float | datetime | str | date | hex
fun: ID | abs| avg[s] | count | deltas | distinct | drop
  | fill | first | last | max[s] | min[s] | mod | next
  | prev | sum[s] | stddev | ratios | vars | moving

binop: +|-|=|*|!=|<|>|>=|<=|&&|||

Basic Examples

Following the commonly user grammar above, we provide some basic examples.

Queries

AQuery does not allow nested queries, but you can easily use WITH to construct as many intermediate, query-local tables. These tables are only available in subsequent queries within the same WITH statement.

WITH t1(c1, c2, c3) AS (
  SELECT c10, c20, c30 FROM t ASSUMING ASC c4
  WHERE f(c3) > 10 AND c5 != c6
  )
SELECT c1, sum(c2) FROM t1 GROUP BY c1
WITH nested_t1(c1, c2, c3) AS (
  SELECT c10, c20, c30 FROM t ASSUMING ASC c4
  WHERE f(c3) > 10 AND c5 != c6
  GROUP BY c10
  )
// must flatten out nested arrable using built-in FLATTEN
SELECT c1, sum(c2) FROM FLATTEN(nested_t1) GROUP BY c1

You are also free to have function calls that return a table as part of the from-clause. For example

SELECT * FROM FLATTEN(CONCATENATE(nested_1, nested_2, nested_3))

which uses the built-ins FLATTEN and CONCATENATE (DISTINCT is also available as a built-in). Users are also free to define functions (in verbatim-q for now) that return tables and use these in their queries.

<q>f:{([]c1: 1 2 3 1; c2:10 20 30 40)}</q>
SELECT * FROM f() WHERE c1 = 1

The only restrictions on these functions currently is that you cannot use dot notation to access table columns in the call. So for example

<q>
h:{([]c1:x * 2)};
t:([]c1:1 2 3);
</q>
SELECT * FROM h(t.c1)

is not valid. However, there is a simple workaround

SELECT * FROM h(t("c1"))

Creating Data

You can create data directly in AQuery as done below, but often the use of verbatim q <q> q commands here </q> allows for simple data creation for experiments.

CREATE TABLE my_table (c1 INT, c2 INT, c3 STRING)
INSERT INTO my_table VALUES(10, 20, "example")
INSERT INTO my_table SELECT * FROM my_table

You can also create tables using a query. For example:

CREATE TABLE my_table_derived
AS
  SELECT c1, c2 * 2 as twice_c2 FROM my_table

Note that the query can include any valid query-construct, such as a WITH statement.

Loading and Saving Data

For this example, we'll create a simple csv file from the shell command line

josecambronero demo$ echo "ID,val" > my_table.csv;\
 for i in {1..10}; do echo "$i,$((i * 10))" >> my_table.csv; done

We must first declare the schema of our table, as this is required to parse values to the appropriate type.

CREATE TABLE my_table (ID INT, val INT)

We can now parse in the csv file and insert the records into our predefined table.

LOAD DATA INFILE "my_table.csv"
INTO TABLE my_table
FIELDS TERMINATED BY ","

We can now perform a query and save the results into a new file. In this case, we use a pipe-delimited file instead.

SELECT ID, val, val * 2 as derived_val FROM my_table
INTO OUTFILE "new_my_table.csv"
FIELDS TERMINATED BY "|"
josecambronero demo$ cat new_my_table.csv
ID|val|derived_val
1|10|20
2|20|40
3|30|60
4|40|80
5|50|100
6|60|120
7|70|140
8|80|160
9|90|180
10|100|200

User-Defined Functions

Users can define their own aggregates using a simple syntax, described briefly in the grammar section. The main idea is: you can define local variables using :=, consecutive commands must be concatenated with ;, and the final result of the function corresponds to the last expression. If there is a ; on the last expression, the function produces no result. This closely mirrors function definitions in q, with some minor changes.

In the example below, we define our own covariance aggregate, for use in our queries. You are free to use other aggregates in the definition. In this case we use built-ins such as avg, sum, and sqrt, which are self-explanatory.

FUNCTION myCov(x, y) {
  center_x := x - avg(x);
  center_y := y - avg(y);
  num := sum(center_x * center_y);
  denom := sqrt(sum(center_x * center_x)) * sqrt(sum(center_y * center_y));
  num / denom
  }

Function Semantics

Arrables, the main data structure in AQuery, are designed to address values column-wise, as vectors. So for example, given a function and query as

FUNCTION my_avg(v) {sum(v) / count(v)}
SELECT my_avg(c1) FROM my_table

the call to my_avg passes c1 as a vector to my_avg, in contrast to passing each value of c1 separately. This vector-oriented mentality is critical to AQuery (and the underlying q/kdb+ systems), and results in more intuitive expressions.

(As a side-note, there is already a built-in called avg that calculates the average, but we reproduce our own here as an exercise in UDF writing).

As highlighted before, arrables can be nested. Consider the simple table shown below:

>SELECT * FROM my_table
>
c1 c2
-----
1  10
1  20
2  30
2  40
3  50

We can create a nested-arrable by using a GROUP-BY.

>CREATE TABLE nested_my_table AS SELECT c1, c2 FROM my_table GROUP BY c1
>
c1 c2    
---------
1  10 20i
2  30 40i
3  ,50i

Note that c2 now consists of nested vectors.

Now if you want to apply an aggregate on each of the vectors constituting the nested c2, you need to use a higher-order function that modifies the application of the function. These are currently not exposed directly in AQuery, as they constitute a more advanced function. However, users can directly access them using verbatim-q. In this case, they can use q's adverbs.

So our my_avg can be modified to

<q>my_avg_each:my_avg'</q>

We can now apply the aggregate on a query on nested_my_table and obtain the expected results:

>SELECT c1, my_avg_each(c2) as avg_val FROM nested_my_table
>
c1 avg_val
----------
1  15     
2  35     
3  50

Note that if an aggregate is used in the same query that has the GROUP BY clause, then AQuery automatically introduces the necessary modifiers in the aggregate application. So the following is equally valid:

>SELECT c1, my_avg(c2) as avg_val
>FROM my_table GROUP BY c1
>
c1 avg_val
----------
1  15     
2  35     
3  50

It is also worth highlighting that one level of nesting can be removed by applying FLATTEN (currently the only function application allowed in a FROM clause).

>SELECT * FROM FLATTEN(nested_my_table)
>
c1 c2
-----
1  10
1  20
2  30
2  40
3  50

We consider another example, in which we have two levels of nesting. We create a very simple table meant to reflect data collected in a timed experiment.

>CREATE TABLE t(indiv INT, grp STRING, val INT)
>INSERT INTO t VALUES(1, "A", 1)
>INSERT INTO t VALUES(1, "A", 2)
>INSERT INTO t VALUES(1, "A", 3)
>INSERT INTO t VALUES(1, "A", 4)
>INSERT INTO t VALUES(2, "A", 2)
>INSERT INTO t VALUES(2, "A", 2)
>INSERT INTO t VALUES(2, "A", 4)
>INSERT INTO t VALUES(2, "A", 8)
>INSERT INTO t VALUES(3, "B", 10)
>INSERT INTO t VALUES(3, "B", 20)
>INSERT INTO t VALUES(3, "B", 30)
>INSERT INTO t VALUES(3, "B", 40)
>INSERT INTO t VALUES(4, "B", 20)
>INSERT INTO t VALUES(4, "B", 20)
>INSERT INTO t VALUES(4, "B", 40)
>INSERT INTO t VALUES(4, "B", 80)
>

>SELECT * FROM t
>
indiv grp val
-------------
1     A   1  
1     A   2  
1     A   3  
1     A   4  
2     A   2  
2     A   2  
2     A   4  
2     A   8  
3     B   10
3     B   20
3     B   30
3     B   40
4     B   20
4     B   20
4     B   40
4     B   80

We create our first level of nesting by grouping by individual and group (indiv and grp, respectively).

>CREATE TABLE nested_1_t AS
>SELECT indiv, grp, val as timeseries
>FROM t GROUP BY indiv, grp
>
indiv grp timeseries
---------------------
1     A   1  2  3  4
2     A   2  2  4  8
3     B   10 20 30 40
4     B   20 20 40 80

This resembles our prior example. We could apply an aggregate on each row of timeseries by using a modifier as described before.

But consider another experiment, in which we fuse nested arrays, showing that we can create say a global time series that is the average of the given ones in a group.

>SELECT grp, avg(timeseries) as avg_time_series
>FROM nested_1_t GROUP BY grp
>
grp avg_time_series
-------------------
A   1.5 2  3.5 6   
B   15  20 35  60  

Let's look at the nested arrable, before we apply our aggregate.

>SELECT grp, timeseries FROM nested_1_t GROUP BY grp
>
grp timeseries             
---------------------------
A   1 2 3 4     2 2 4 8    
B   10 20 30 40 20 20 40 80

Note that there are now two levels of nesting. Each row consists of two separate vectors. If there were n individuals per group, these would then be n-vectors and so forth.

So once again, the query with GROUP BY works as expected because AQuery added the necessary modifiers to the aggregate application behind the scenes, but if you want to do this in two separate steps, you need to use our modified aggregate.

>WITH
>temp AS (SELECT grp, timeseries FROM nested_1_t GROUP BY grp)
>SELECT grp, my_avg_each(timeseries) as avg_time_series FROM temp
>
grp avg_time_series
-------------------
A   1.5 2  3.5 6   
B   15  20 35  60  

Filling in missing values

We now consider a common case in timeseries analysis: filling in missing values. Consider the the table defined below:

<q>
 t1:([]indiv:1 1 1 1 1; ts:0 1 2 3 4; val:10 20 30 40 50);
 t2:([]indiv:2 2 2; ts:2 3 4; val:30 40 50);
 t:t1,t2;
 </q>

Individual two is missing observations for timestamp (represented here as an integer for simplicity) zero and one.

In order to calculate correlation between the values for both individuals, we extend the timeseries for individual two.

<q>corEach:cor';</q>
FUNCTION fill_backward(x) {reverse(fills(reverse(x)))}

WITH
  ts AS (SELECT ts FROM t)
  indiv AS (SELECT indiv FROM t)
  complete AS (SELECT * FROM distinct(ts), distinct(indiv))
  filled AS (SELECT   
    indiv, ts,
    fill_backward(val) as filled_val
    FROM
    complete FULL OUTER JOIN t USING (indiv, ts)
    ASSUMING ASC ts
    GROUP BY indiv)
   SELECT
   f1.indiv as indiv1, f2.indiv as indiv2,
   corEach(f1.filled_val, f2.filled_val) as filled_corr
   FROM filled f1, filled f2 WHERE f1.indiv != f2.indiv

ts and indiv are single column tables representing all timestamps and individuals, respectively. complete is a cartesian-product of the distinct values in the two tables, generating a complete history for each individual. filled uses a UDF fill_backward to fill any missing values with the following non-missing value (hence the name). This is used in complete by joining our original table with our extended history table and applying the UDF by individual. Finally, our resulting query uses the filled data to calculate the correlation between the two individuals' timeseries.

If you have any doubts/issues/feedback, please do not hesitate to contact Jose Cambronero

You can’t perform that action at this time.