KDB

KDB

However kdb+ evaluates expressions right-to-left. There are no precedence rules. The reason commonly given for this behaviour is that it is a much simpler to understand system, many q-gods would agree, beginners however may not.

The kdb+ built-in commands are mostly a single letter. If a system command that is not built-in is entered, that command will be passed to the underlying operating system.

Created with financial institutions in mind, the database was developed as a central repository to store time series data that supports real-time analysis of billions of records.

Columnar databases return answers to some queries in a more efficient way than row-based database management systems.

kdb+ dictionaries, tables and nanosecond time stamps are native data types and are used to store time series data.

In 1998, Kx Systems released kdb, a database built on the language K written by Arthur Whitney. In 2003, kdb+ was released as a 64-bit version of kdb.

kdb/q/kdb+ is both a database (kdb) and a vector language (q). It’s used by almost every major financial institution

Kdb+ is an in-memory column-oriented database based on the concept of ordered lists. In-memory means it primarily stores its data in RAM. This makes it extremely fast with a much simplified database engine but it requires a lot of RAM (Which no longer poses a problem as servers with massive amounts of RAM are now inexpensive). Column oriented database means that each column of data is stored sequentially in memory

Column DB

The main reason why indexes dramatically improve performance on large datasets is that database indexes on one or more columns are typically sorted by value, which makes range queries operations (like the above “find all records with salaries between 40,000 and 50,000” example) very fast (lower time-complexity).

Kdb+ the Database - Column Oriented DB allowing fast timeseries analysis

Column-oriented systems

A column-oriented database serializes all of the values of a column together, then the values of the next column, and so on. For our example table, the data would be stored in this fashion: 10:001,12:002,11:003,22:004; Smith:001,Jones:002,Johnson:003,Jones:004; Joe:001,Mary:002,Cathy:003,Bob:004; 40000:001,50000:002,44000:003,55000:004; In this layout, any one of the columns more closely matches the structure of an index in a row-based system. This may cause confusion that can lead to the mistaken belief a column-oriented store “is really just” a row-store with an index on every column. However, it is the mapping of the data that differs dramatically. In a row-oriented indexed system, the primary key is the rowid that is mapped from indexed data. In the column-oriented system, the primary key is the data, which is mapped from rowids.[2] This may seem subtle, but the difference can be seen in this common modification to the same store:

…;Smith:001;Jones:002,004;Johnson:003;…

Whether or not a column-oriented system will be more efficient in operation depends heavily on the workload being automated. Operations that retrieve all the data for a given object (the entire row) are slower. A row-based system can retrieve the row in a single disk read, whereas numerous disk operations to collect data from multiple columns are required from a columnar database. However, these whole-row operations are generally rare. In the majority of cases, only a limited subset of data is retrieved. In a rolodex application, for instance, collecting the first and last names from many rows to build a list of contacts is far more common than reading all data for any single address. This is even more true for writing data into the database, especially if the data tends to be “sparse” with many optional columns. For this reason, column stores have demonstrated excellent real-world performance in spite of many theoretical disadvantages.

Why are most databases row-oriented?

Imagine we want to add one row somewhere in the middle of our data for 2011-02-26, on the row oriented database no problem, column oriented we will have to move almost all the data! Lucky since we mostly deal with time series new data only appends to the end of our table.

Difference vs row based DB

a subtle point is that unlike most standard SQL which is based on set theory, kdb+ is based on vectors of ordered lists. Where standard SQL has struggled with queries like find the top 3 stocks by price, find the bottom 3 by market cap because it has no concept of order, kdb’s ordering significantly simplifies many queries. This ordered concept allows kdb+ to provide unique timeseries joins that would be be extremely difficult in other variations of SQL and require the use of slow cursors.

Language Q

the primary design objectives of q are expressiveness, speed and efficiency. In these, it is beyond compare. The design trade-off is a terseness that can be disconcerting to programmers coming from verbose traditional database programming environments – e.g., C++, Java, C# or Python – and a relational DBMS

Q evolved from APL (A Programming Language), which was first invented as a mathematical notation by Kenneth Iverson at Harvard University in the 1950s. APL was introduced in the 1960s by IBM as a vector programming language, meaning that it processes a list of numbers in a single operation. It was successful in finance and other industries that required heavy number crunching.

q is Kx’s proprietary language. It’s a powerful, concise and elegant array language, which means that a production system could just be a single page of code, not pages and pages of code and a nightmare to maintain. Clearly there is an initial investment in learning it, but the power it gives you to manipulate streaming, real-time and historical data makes that initial investment really worthwhile.

q language - fast, interpreted vector based language

Q is a interpreted vector based dynamically typed language built for speed and expressiveness.

Since q is interpreted you can enter commands straight into the console there is no waiting for compilation, feedback is instantaneous.

Key features of Q

Interpreted Q is interpreted, not compiled. During execution, data and functions live in an in-memory workspace. Iterations of the development cycle tend to be quick because all run-time information needed to test and debug is immediately available in the workspace. Q programs are stored and executed as simple text files called scripts. The interpreter’s eval and parse routines are exposed so that you can dynamically generate code in a controlled manner.

Types Q is a dynamically typed language, in which type checking is mostly unobtrusive. Each variable has the type of its currently assigned value and type promotion is automatic for most numeric operations. Types are checked on operations to homogenous lists.

Evaluation Order While q is entered left-to-right, expressions are evaluated right-to-left or, as the q gods prefer, left of right – meaning that a function is applied to the argument on its right. There is no operator precedence and function application can be written without brackets. Punctuation noise is significantly reduced.

Null and Infinity Values In classical SQL, the value NULL represents missing data for a field of any type and takes no storage space. In q, null values are typed and take the same space as non-nulls. Numeric types also have infinity values. Infinite and null values can participate in arithmetic and other operations with (mostly) predictable results.

Integrated I/O I/O is done through function handles that act as windows to the outside world. Once such a handle is initialized, passing a value to the handle is a write.

Table Oriented Give up objects, ye who enter here. In contrast to traditional languages, you’ll find no classes, objects, inheritance and virtual methods in q. Instead, q has tables as first class entities. The lack of objects is not as severe as might first appear. Objects are essentially glorified records (i.e., entities with named fields), which are modeled by q dictionaries. A table can be viewed as a list of record dictionaries.

Ordered Lists Because classical SQL is the algebra of sets – which are unordered with no duplicates – row order and column order are not defined, making time series processing cumbersome and slow. In q, data structures are based on ordered lists, so time series maintain the order in which they are created. Moreover, simple lists occupy contiguous storage, so processing big data is fast. Very fast.

Column Oriented SQL tables are organized as rows distributed across storage and operations apply to fields within a row. Q tables are column lists in contiguous storage and operations apply on entire columns.

In-Memory Database One can think of kdb+ as an in-memory database with persistent backing. Since data manipulation is performed with q, there is no separate stored procedure language. In fact, kdb+ comprises serialized q column lists written to the file system and then mapped into memory.

In q, data structures are based on ordered lists, so time series maintain the order in which they are created. Moreover, simple lists occupy contiguous storage, so processing big data is fast. Very fast.

Q tables are column lists in contiguous storage and operations apply on entire columns.

Sample of Q code

q)l:10 12 14 16 18 22 32 45
q)sum l
169
q)avg l
21.125
q)l*10
100 120 140 160 180 220 320 450

q)k:til 8
q)k
0 1 2 3 4 5 6 7
q)l+k
10 13 16 19 22 27 38 52
        

Notice in the example code above the absence of loops, no for/while/do yet we could easily express adding one array to another. This is because the vector/list is the primary unit of data in kdb+. Operations are intended to be performed and expressed as being on an entire set of data. Dictionaries can be defined using lists, they provide a hashmap datastructure for quick lookups. Tables are constructed from dictionaries and lists. This brevity of data structures is actually one of the attributes that gives q its ability to express concisely what would take many lines in other languages.

Some of the practical applications of being able to combine both streaming and real-time data together with historical, all in the same database?

The most important thing is the simplicity, which translates into speed and ease of doing analysis. For example, it allows you to do complicated, time-critical analysis, such as pre-trade risk. This means that you are likely to see interesting trading opportunities before those who are using the same off-the-shelf solution as everybody else. So you’re there first and you’re there so early, you can afford to do comprehensive pre-trade risk analysis, and you’re able to look for patterns you’ve seen in the past.

In addition to capturing market data, firms are using kdb+ for order-book management, algorithmic trading, and risk assessment. “They are using kdb+/q for queries being performed on both streaming or historical data — the latter easily accommodating research and back-testing,”

DeltaFlow, a platform from First Derivatives that’s based on kdb+, is used by traders for high volume, low-latency algorithmic trading and by regulators for real-time detection of market abuse and unauthorized trading activity across multiple asset classes.

Combined power of kdb+/q

What’s beautiful about kdb+ is that since tables are columns of vectors, all the power of the q language can be used as easily on table data as it was on lists. Where we had sum[l],avg[l],weightedAvg[l1;l2] of lists we can write similar qSQL: select avg price, sum volume, weightedAvg[time;price] from trade Want to apply a function to a timeseries, simply place it inline: select {a:avg x; sqrt avg (xx)-aa} price from trade

Q commadns

To obtain official console display of any q value, apply the built-in function show to it.

q)show a:42

comments

At least one whitespace character must separate / intended to begin a comment from any text to the left of it on a line.

boolean

Boolean values in q are stored in a single byte and are denoted as the binary values they really are with an explicit type suffix b. One way to generate boolean values is to test for equality.

q)42=40+2 1b

date

One interesting and useful feature of q temporal values is that, as integral values under the covers, they naturally participate in arithmetic. For example, to advance a date five days, add 5.

q)2000.01.01+5 _ Or to advance a time by one microsecond (i.e., 1000 nanoseconds) add 1000.

q)12:00:00.000000000+1000 _ Or to verify that temporal values are indeed their underlying values, test for equality.

q)2000.01.01=0

Symbols

Symbols are denoted by a leading back-quote (called “back tick” in q-speak) followed by characters. Symbols without embedded blanks or other special characters can be entered literally into the console. q)`aapl _

Since symbols are atoms, any two can be tested for equality.

q)aapl=apl _

list

The fundamental q data structure is a list, which is an ordered collection of items sequenced from left to right. The notation for a general list encloses items with ( and ) and uses ; as separator. Spaces after the semi-colons are optional but can improve readability.

q)(1; 1.2; `one) _

In the case of a homogenous list of atoms, called a simple list, q adopts a simplified format for both storage and display. The parentheses and semicolons are dropped. For example, a list of underlying numeric type separates its items with a space.

q)(1; 2; 3) 1 2 3

A simple list of booleans is juxtaposed with no spaces and has a trailing b type indicator.

q)(1b; 0b; 1b) 101b A simple list of symbols is displayed with no separating spaces.

q)(one; two; three) onetwothree

basic operations

to construct and manipulate lists. The most fundamental is til, which takes a non-negative integer n and returns the first n integers starting at 0 (n itself is not included in the result).

q)til 10 0 1 2 3 4 5 6 7 8 9

til list tips

Be mindful that q always evaluates expressions from right to left and that operations work on vectors whenever possible.

q)1+til 10 1 2 3 4 5 6 7 8 9 10

Similarly, we obtain the first 10 even numbers and the first ten odd numbers.

q)2til 10 _ q)1+2til 10 _ Finally, we obtain the first 10 even numbers starting at 42.

q)42+2*til 10 _

Another frequently used list primitive is join , that returns the list obtained by concatenating its right operand to its left operand.

q)1 2 3,4 5 1 2 3 4 5

extract

To extract items from the front or back of a list, use the take operator #. Positive argument means take from the front, negative from the back.

q)2#til 10 0 1 q)-2#til 10

Applying # always results in a list.

In particular, the idiom 0# returns an empty list of the same type as the first item in its argument. Using an atom argument is a succinct way to create a typed empty list of the type of the atom.

q)0#1 2 3 `long$()

Should you extract more items than there are in the list, # restarts at the beginning and continues extracting. It does this until the specified number of items is reached.

q)5#1 2 3 1 2 3 1 2

As with atoms, a list can be assigned to a variable.

q)L:10 20 30 The items of a list can be accessed via indexing, which uses square brackets and is relative to 0.

q)L[0] 10

Function

Conceptually, a q function is a sequence of steps that produces an output result from an input value. Since q is not purely functional, these rules can interact with the world by reaching outside the context of the function. Such actions are called side effects and should be carefully controlled.

Function definition is delimited by matching curly braces { and }. Immediately after the opening brace, the formal parameters are names enclosed in square brackets [ and ] and separated by semi-colons. These parameters presumably appear in the body of the function, which follows the formal parameters and is a succession of expressions sequenced by semi-colons.

Following is a simple function that returns the square of its input. On the next line we assign the same function to the variable sq. The whitespace is optional.

q){[x] xx} _ q)sq:{[x] xx} _

Here is a function that takes two input values and returns the sum of their squares.

q){[x;y] a:xx; b:yy; a+b} _ q)pyth:{[x;y] a:xx; b:yy; a+b} _

Here are the previous functions applied to arguments.

q){[x] xx}[5] 25 q)sq[5] _ q){[x;y] a:xx; b:y*y; a+b}[3;4] 25 q)pyth[3;4] _

monadic function

In q, as in most functional languages, we don’t need no stinkin’ brackets for application of a monadic function – i.e., with one parameter. Simply separate the function from its argument by whitespace. This is called function juxtaposition.

q){xx} 5 _ q)f:{xx} q)f 5 _

x,y,z

It is common in mathematics to use function parameters x, y, or z. If you are content with these names (in the belief that descriptive names provide no useful information to the poor soul reading your code), you can omit their declaration and q will understand that you mean the implicit parameters x, y, and z in that order.

q){xx}[5] 25 q){a:xx; b:y*y; a+b}[3;4] 25

verbs

higher order functions, or as they are called in q, adverbs.

In words, we tell q to start with the initial value of 0 in the accumulator and then modify + with the adverb / so that it adds across the list.

q)0 +/ 1 2 3 4 5 15

In this situation we don’t really need the flexibility to specify the initial value of the accumulator. It suffices to start with the first item of the list and proceed across the rest of the list. There is an even simpler form for this case.

q)(+/) 1 2 3 4 5

for loop

If you are new to functional programming, you may think, “Big deal, I write for loops in my sleep.”

More importantly, you can focus on what you want done without the irrelevant scaffolding of how to set up control structures. This is called declarative programming.

What else can we do with our newfound adverb? Change addition to multiplication for factorial.

q)(*/) 1+til 10 3628800

larger vs smaller

The fun isn’t limited to arithmetic primitives. We introduce |, which returns the larger of its operands and &, which returns the smaller of its operands.

q)42|98 98 q)42&98

q)(|/) 20 10 40 30 40 q)(&/) 20 10 40 30

command ‘over’ adverb

Some applications of / are so common that they have their own names.

q)sum 1+til 10 55 q)prd 1+til 10 “o” _ q)max 20 10 40 30 _ q)min 20 10 40 30

At this point the / pattern should be clear: it takes a given function and produces a new function that accumulates across the original list, producing a single result. In particular, / converts a dyadic function to a monadic aggregate function – i.e., one that collapses a list to an atom.

data type

long¶

In q versions 3.0 and later, the basic integer type is a signed eight-byte integer, called long. A literal is identified as a long by the fact that it contains only numeric digits, with an optional leading minus sign, and no decimal point. It may also have an optional trailing type indicator j indicating it is a long and not another integer type. Here is a typical long integer value.

q)42 42 Observe that the type indicator j is accepted but redundant.

q)42j 42

The short type represents a two-byte signed integer and requires the trailing type indicator h. For example,

q)-123h _ Similarly, the int type represents a four-byte signed integer and requires the trailing type indicator i.

The float type represents an IEEE standard eight-byte floating-point number, often called “double” in traditional languages. A float can hold (at least) 15 decimal digits of precision. It is denoted by optionally signed numeric digits with either a decimal point or an optional trailing type indicator f. Observe that the console shortens the display of floats with no significant digits to the right of the decimal.

You can change this by using the \P command (note upper case) to specify a display width up to 16 digits. If you issue \P 0 the console will display all 17 decimal digits of the underlying binary representation, although the last digit is unreliable.

boolean¶

The boolean type uses one byte to store a bit and is denoted by the bit value with the trailing type indicator b. There are no keywords for ‘true’ or ‘false’, nor are there separate logical operators for booleans.

q)0b _ q)1b

Text Data¶

There are two atomic text types in q. They are more akin to the SQL types CHAR and VARCHAR than the character types of traditional languages.

2.4.1 char¶

A char holds an individual ASCII or 8-bit Unicode character that is stored in one byte. It corresponds to a SQL CHAR. It is denoted by a single character enclosed in double quotes.

q)”q”

Some keyboard characters – e.g., the double-quote – cannot be entered directly into a char since they have special meaning in the q console. As in C, special characters are escaped with a preceding back-slash . The console display somewhat confusingly displays the escape, but the following are all actually single characters.

q)”"” “"” q)”\” _ q)”\n” _ q)”\r” _ q)”\t” _ Also as in C, you can escape any ASCII character by specifying its underlying numeric value as three octal digits.

q)”\142” “b”

symbol¶

A symbol is an atom holding text. It is denoted by a leading back-quote, read “back tick” in q-speak.

q)q _ q)zaphod _

a symbol is not a collection of char. The symbol `a and the char “a” are not the same, as we can see by asking q if they are identical.

q)`a~”a” 0b

list

Index Notation¶

To access the item at index i in a list, follow the list immediately with [i]. This is called item indexing. For example,

q)(100; 200; 300)[0]

Indexed Assignment¶

Items in a list can also be assigned via item indexing. Thus,

q)L:1 2 3 q)L[1]:42 q)L 1 42 3

An omitted index returns the entire list.

q)L:10 20 30 40 q)L[] 10 20 30 40

• 2021 18
• 2020 29
• 2019 8
• 2018 41
• 2017 40
• 2016 54
• 2007 1