K and KDB, tools for finance

Dennis Shasha
Courant Institute of Mathematical Sciences
Department of Computer Science
New York University
shasha@cs.nyu.edu
http://cs.nyu.edu/cs/faculty/shasha/index.html

What is K?

Programming language and environment based on arrays designed and implemented (in C) by Arthur Whitney.
Used extensively at Union Bank of Switzerland during a three-year exclusive license (ending in early 1997).
Now in wider distribution: Zurich Insurance, Lehman brothers, other New York investment banks, etc.
Library built over the last year on top of K: KSQL. This is a language and database system optimized for time series and other array-oriented applications.

Good Points about K

K applications often run faster than the corresponding C program, because K operators handle bulk data types (arrays and tables), so are willing to do some setup to make the whole thing go fast, e.g. multiple sorting methods.
Expressive:
- math
- database, relational and time series
- graphical user interface
- interprocess communication
- Good connections to the web (accepts http messages and Java calls).
Working in a single language reduces errors and interface overhead.
It is also more fun because you can concentrate on the algorithm.
Interpreted so zero time recompile.
No pointers so no seg faults or bus errors.
Very portable: NT, Linux, many Unixes.
After a three day steep learning curve, a very comfortable language to program in.

What are KDB and KSQL?

KDB is a database system implemented on top of the K language environment. Data structures (e.g. tables) can be interchanged between the two and functions can be called in both directions.
KDB supports an SQL dialect called KSQL. KSQL is easy to learn (for anyone fluent in SQL) and carries over the speed and functionality of K to large data manipulation. KDB also supports most of standard SQL.
The basic data structure in KSQL is the arrable (array-table) which is a table whose order can be exploited.
Arrables are non-first-normal form objects: a field of a record can be an array. For example, an entire time series can be stored in a field.
Like most modern SQLs, KSQL allows the inclusion of user-defined functions inside database statements. Unlike other SQL's KSQL allows functions to be defined over arrays as well as scalars.
Like classical SQL, KSQL has aggregates, grouping, selections and string matching, and so on.
KSQL adds many useful functions to SQL, permitting economical expression and often better performance by exploiting order. For example, finding the second highest value is a linear time operation in KSQL but requires a self-join in SQL, which is only sometimes linear time.
KDB can function as a high performance distributed server with full recovery and distributed consistency. (KDB guarantees consistency by using ordered atomic broadcast and a replicated state machine design rather than two phase commit.)
Some performance notes
- KDB can do 40,000+ TPC/B transactions per second against a 100 megabyte database on a Pentium 2.
- Kx will soon demonstrate excellent data warehouse performance using a 100 gigabyte TPC/D benchmark (scale factor 100).
- Real application at Lehman Brothers: time series: keyed by instrument id, date.
  Data: 11 million rows, couple of hundred columns, typical query returns 7500 rows with 15 columns. 10 gigabytes.
  Query: is find all information having to do with a given set of instruments at a given date. This returns 7500 rows in less than a second.

KSQL Basics -- an extended example

Create tables (arrables, really, but we'll conform to standard terminology, even though it's slightly inexact) either through K or within .t scripts. This example uses a mixture of the two.

/ Calling KSQL from K

\l db / running from K, just load the library


`"build stock"
stock.name: `Alcatel `Alstom `"Air France" `"France Telecom" `"Snecma" `Supra
stock.industry: `telecom `engineering `"aviation" `"telecom" `"aviation" `consulting

.d.r"stock: 'name'key stock"

.d.r"stock['Alcatel'].industry"

`"build trade"

n:1000	/ number of trades

t1: ,/("trade:([]"
 " stock:n rand stock.name,"
 " price:50 + .25 * n rand 200,"
 " amount:100 * 10 + n rand 20,"
 " date:date['1998-01-01'] + n rand 449)")

.d.r t1

t2: "trade:'date' asc trade"
.d.r t2

.d.r "show'trade'"

/ now it's time to calculate 6 month hi, low, average, volume
/ for a given stock.
getstats:{[name;date]
 x: " select first stock, hi: max price, low: min price, "
 x,: " avgprice: avg price, vol: sum amount "
 x,: " from trade where stock = '"
 x,: ($name)
 x,: "', date within (date['"
 x,: ($date)
 x,: "'], date['"
 x,: ($date)
 x,: "'] + 182)"
 res: .d.r x
 :res
}

res: getstats["Alcatel";"1998-01-01"] 

.d.r "show'res'"

Let's go through this line by line.
The first line is just a comment. K uses slashes instead of pound signs.
```
/ Calling KSQL from K
```

The following line loads the KDB library.

\l db / running from K, just load the library

The following builds a table in K, preceded by the emission of a string saying that we are building the stock table.

`"build stock"
stock.name: `Alcatel `Alstom `"Air France" `"France Telecom" `"Snecma" `Supra
stock.industry: `telecom `engineering `"aviation" `"telecom" `"aviation" `consulting

Now we specify that the field name is a key of the stock table within KSQL. Any time we want to call a KSQL function, we invoke that function as a string argument to .d.r.
```
.d.r"stock: 'name'key stock"
```
Having established name as a key, we can use it as an index as we would normally in KSQL.
```
.d.r"stock['Alcatel'].industry"
```

Next we build the trade table. Notice that the assignment operator (colon) works in both K and KSQL. Notice also that we first construct a string in K in the variable t1, then we invoke .d.r on the string.


`"build trade"

n:1000	/ number of trades

t1: ,/("trade:([]"
 " stock:n rand stock.name,"
 " price:50 + .25 * n rand 200,"
 " amount:100 * 10 + n rand 20,"
 " date:date['1998-01-01'] + n rand 449)")

.d.r t1

Now, we sort trade and then show the table in KSQL format.


t2: "trade:'date' asc trade"
.d.r t2

.d.r "show'trade'"

Now we establish a function in K to compute various statistics about stocks.


/ now it's time to calculate 6 month hi, low, average, volume
/ for a given stock.
getstats:{[name;date]
 x: " select first stock, hi: max price, low: min price, "
 x,: " avgprice: avg price, vol: sum amount "
 x,: " from trade where stock = '"
 x,: ($name)
 x,: "', date within (date['"
 x,: ($date)
 x,: "'], date['"
 x,: ($date)
 x,: "'] + 182)"
 res: .d.r x
 :res
}

Next, we call that function and show the result.


res: getstats["Alcatel";"1998-01-01"] 

.d.r "show'res'"

Performance Advantage of KSQL

The above implementation is reasonably classic, but it has some performance problems. The following takes too long.

m: 500
do[m
  res: getstats["Alcatel";"1998-01-01"]
]
("These "), ($m), (" getstats requests required "),($ _t - start), (" seconds.")

An alternative implementation is to store the data by stock, so we have vectors for prices, amounts, and dates. We do this in the statement:
```
.d.r "tradeseq: select price, amount, date by stock from trade"
```
The time shows this to be much faster. The same trick can be used to do data mining on stock sequences, e.g. to find correlations among stock price movements (pairs trading).

KSQL and Interprocess Communication

K supports interprocess communication very easily and therefore so does KSQL.
The server declares a port that clients will use:
```
\m i 1234
```
The receiver of a request in a server is a function with the reserved name
```
 .m.g 
```
(the dots represent a kind of directory structure in the namespace; the first dot is the root).


/ Receive communication from another process
.m.g:{[pair]
  x: getstatsseq[$pair[0]; $pair[1]]
  :x
}

The client code then sends a request

machine: ` / local machine

server: 3: machine,1234 / declare a handle

x: server 4: (`Alcatel; `"1998-01-01")
`show $ `x

The overhead of interprocess communication is quite small (e.g. 500 requests require 6 seconds instead of 4). This is similar to the overhead for web requests.

KSQL and the Web

K programs can listen directly on port 80. When a signal is received on that port, it goes to a function named .m.h. Here is the .m.h function for our example.

/ receive from web
.m.h:{[string]
  i: string _ss "stock"
  string: *(i+6) _ string
  i: string ? "&"
  name: string[!i]
  s: #string
  date: string[(s-10) + !10]
  res: getstats[name;date]
  out: printheader[!res]
  vals: ,+res[]
  out,: ,/tablehtmlize[vals]'!#vals
  :out
}

This function parses its input and then calls a normal K function (which may in turn calls KSQL). The result is returned to the browser as a string.