TimeStored Blog

Bitwise Operators for Kdb+ Database

Kdb does not have built-in functions for bitwise and,or,xor operations, we are going to create a C DLL extension that provides bitwise operators.

To download the source and definitions for and/or/xor bitwise operations click here
If your new to extending Kdb+ see this tutorial on writing a DLL for Kdb+

I also thought this would be a good opportunity to look at using q-code to generate C code, to generate Kdb Dll’s. When converting an existing library to work with Kdb or writing similar functions for different types, there’s a lot of repetitive coding. Either you can use macros or you can use one language to generate another, to save a lot of typing. Let’s look at bitwise operations as an example of what I mean:

If I wanted to write a bitwise and function band that takes two lists and performs a corresponding operation, we could write the C functions like so:

Notice the similarity between the bandJJ and bandII functions. Plus if we want to handle the case where the second argument is an atom we need an entire other set of C functions similar to bandJ to handle that. This is soon beginning to spiral beyond an easy copy paste job. Instead I used the following 20 lines of q code to generate the 130 lines of C code:

This generates my C code, a .def file exporting the functions that I want to provide and creates a .q file that loads those functions into kdb. Which means any time I add a function or want to support a new type, everything is done for me. let’s look at our functions in action:

Yes the q code is messy (it could be improved) but the concept of dynamically generating your imports can be a real time saver.

This code is not intended for reliability or performance, use at your own risk! If however bitwise operations are a topic that interest you I recommend this article on: Writing a fast vectorised OR function for Kdb.

Kdb qSQL vs standard SQL queries

Often at the start of one of our training courses I’m asked why banks use the Kdb Database for their tick data.

• One well known reason is that kdb is really fast at typical financial time-series queries
  (due to Kdbs column-oriented architecture).
• Another reason is that qSQL is extremely expressive and well suited for time-series queries.

To demonstrate this I’d like to look at three example queries, comparing qSQL to standard SQL.

SQL Queries dependent on order

From the table below we would like to find the price change between consecutive rows.

q Code

In kdb qSQL this would be the extremely simple and readable code:

Standard SQL

In standard SQL there are a few methods, we can use. The simplest is if we already have a sequential id column present:

Even for this simple query our code is much longer and not as clear to read. If we hadn’t had the id column we would have needed much more code to create a temporary table with row numbers. As our queries get more complex the situation gets worse.

Select top N by category

Given a table of stock trade prices at various times today, find the top two trade prices for each ticker.

qSQL Code

In q code this would be select 2 sublist desc price by sym from trade, anyone that has used kdb for a few days could write the query and it almost reads like english. Select the prices in descending order by sym and from those lists take the first 2 items (sublist).

SQL Code

In standard SQL a query that depends on order is much more difficult , witness the numerous online posts with people having problems: stackoverflow top 10 by category, mysql first n rows by group, MS-SQL top N by group. The nicest solution, if your database supports it, is:

The SQL version is much harder to read and will require someone with more experience to be able to write it.

Joining Records on Nearest Time

Lastly we want to consider performing a time based join. A common finance query is to find the prevailing quote for a given set of trades. i.e. Given the following trade table t and quote table q shown below, we want to find the prevailing quote before or at the exact time of each trade.

In qSQL this is: aj[`sym`time; t; q], which means perform an asof-join on t, looking up the nearest match from table q based on the sym and time column.

In standard SQL, again you’ll have difficulty: sql nearest date, sql closest date even just the closest lesser date isn’t elegant. One solution would be:

It’s worth pointing out this is one of the queries that is typically extremely slow (minutes) on row-oriented databases compared to column-oriented databases (at most a few seconds).

qSQL vs SQL

Looking at the simplicity of the qSQL code compared to the standard SQL code we can see how basing our database on ordered lists rather than set theory is much more suited to time-series data analysis. By being built from the ground up for ordered data and by providing special time-series based joins, kdb let’s us form these example queries using very simple expressions. Once we need to create more complex queries and nested selects, attempting to use standard SQL can quickly spiral into a verbose unmaintainable mess.

I won’t say qSQL can’t be cryptic 🙂 but for time-series queries qSQL will mostly be shorter and simpler than trying to use standard SQL.

If you think you have shorter SQL code that solves one of these examples or you are interested in one of our kdb training courses please get in touch.

RSI Relative Strength Index in Kdb

In this tutorial we are going to recreate this example RSI calculation in q, the language of the kdb database.

The relative strength index (RSI) is a technical indicator used in the analysis of financial markets. It is intended to chart the current and historical strength or weakness of a stock or market based on the closing prices of a recent trading period. The RSI is classified as a momentum oscillator, measuring the velocity and magnitude of directional price movements. Momentum is the rate of the rise or fall in price.

The RSI computes momentum as the ratio of higher closes to lower closes: stocks which have had more or stronger positive changes have a higher RSI than stocks which have had more or stronger negative changes. The RSI is most typically used on a 14 day timeframe, measured on a scale from 0 to 100, with high and low levels marked at 70 and 30, respectively. Shorter or longer timeframes are used for alternately shorter or longer outlooks. More extreme high and low levels—80 and 20, or 90 and 10—occur less frequently but indicate stronger momentum.

.

Stock Price Time-Series Data

We are going to use the following example data, you can download the csv here or the excel version here.

RSI Formulas

The formulas behind the calculations used in the table are:

• First Average Gain = Sum of Gains over the past 14 periods / 14.
• First Average Loss = Sum of Losses over the past 14 periods / 14

All subsequent gains than the first use the following:

• Average Gain = [(previous Average Gain) x 13 + current Gain] / 14.
• Average Loss = [(previous Average Loss) x 13 + current Loss] / 14.

• RS = Average Gain / Average Loss
• RSI = 100 – 100/(1+RS)

Writing the Analytic in q

We can load our data (rsi.csv) in then apply updates at each step to recreate the table above:

Code kindly donated by Terry Lynch

Rather than create all the intermediate columns we can create a calcRsi function like so:

Finally we can visualize our data using the charting functionality of qStudio (an IDE for kdb):

RSI Relative Strength Index stock chart for QQQQ created using qStudio

Or to plot RSI by itself (similar to original article

RSI Line Graph in qStudio

Writing kdb analytics such as Relative Strength Index is covered in our kdb training course, we offer both public kdb training courses in New York, London, Asia and on-site kdb courses at your offices, tailored to your needs.

jkdb – kdb Java – Running q language code within the java runtime

While doing the project euler programming challenges  it annoyed me how verbose the java answers would have to be compared to kdb. Then I got to wondering if I could create functions like til,mod,where,asc etc. in java and use them to create really short answers. Once I had the basic functions working, I wondered if I could get a working q) prompt…

I ended up with a prompt that let me run the following valid q code within the java runtime:
where[or[ =[0; mod[til[1000];3]]; =[0; mod[til[1000];5]] ]] 

Download the jkdb functional kdb code

The Code

How it Works

My Jkdb class has a number of statically defined functions that accept arrays of ints/doubles and return arrays/atoms of int/double. An example is asc:
/** perform ascending sort **/ public static double[] asc(double[] x) { Arrays.sort(x); return x; }; public static int[] asc(int[] x) { Arrays.sort(x); return x;}; public static double asc(double x) { return x; } public static double asc(int x) { return x; }
In the background each line you type has the square brackets and semi-colons converted to () and comma which are now valid java function calls. The amended string gets added to a .java file, compiled, ran and the output shown each time you press enter. Since I statically imported my class that has the til(x),max(x) etc functions, the code is valid java and works. This is why we can only use functional[x;y] form calls and not the infix notation x func y as I didn’t want to write a parser.

Interesting Points that would occur in Kdb

• All of the functions usually accept int,double, int[],double[] and boolean[] as their arguments and the various combinations. It is annoying having to copy paste these various combinations, I assume in kdb they use C macros to generate the functions, we could do something similar by writing java code to write the java functions.
• The functions I wrote often modify the array passed in, this gives us insight to why in the kdb C api you have to reference count properly, when the reference is 0 the structure is probably reused.

What use is this?

Almost entirely useless 🙂 I use the java class to occasionally spit out some sample data for tests I write. It was however insightful to get an idea of how kdb works under the covers. If you found this interesting you might also like kona an open source implementation of kdb.

I’d be interested in hearing:

• Have you tried kona? Did it work well?
• Have you found a functional library that gives you similar expressiveness to kdb for java?
• Tried Scala? Clojure?

The Jkdb provided functions are:

Exponential Moving Average EMA in Kdb

Let’s look at how to write moving average analytics in q for the kdb database. As example data (mcd.csv) we are going to use stock price data for McDonalds MCD. The below code will download historical stock data for MCD and place it into table t:

Simple Moving Average

The simple moving average can be used to smooth out fluctuating data to identify overall trends and cycles. The simple moving average is the mean of the data points and weights every value in the calculation equally. For example to find the moving average price of a stock for the past ten days, we simply add the daily price for those ten days and divide by ten. This window of size ten days then moves across the dates, using the values within the window to find the average. Here’s the code in kdb for 10/20 day moving average and the resultant chart.

Simple Moving Average Stock Chart Kdb (Produced using qStudio)

What Exponential Moving Average is and how to calculate it

One of the issues with the simple moving average is that it gives every day an equal weighting. For many purposes it makes more sense to give the more recent days a higher weighting, one method of doing this is by using the Exponential Moving Average. This uses an exponentially decreasing weight for dates further in the past.The simplest form of exponential smoothing is given by the formula:

where α is the smoothing factor, and 0 < α < 1. In other words, the smoothed statistic st is a simple weighted average of the previous observation xt-1 and the previous smoothed statistic st−1.

This table displays how the various weights/EMAs are calculated given the values 1,2,3,4,8,10,20 and a smoothing factor of 0.7: (excel spreadsheet)

To perform this calculation in kdb we can do the following:

q)ema:{first[y](1-x)\x*y} q)ema[0.7;1 2 3 4 8 10 20] 1 1.7 2.61 3.583 6.6749 9.00247 16.70074 q)/ the \ here is a very specialised shorthand q)/ The slightly longer version is: q)ema:{{z+x*y}\[first y;1-x;x*y]} q)ema[0.7;1 2 3 4 8 10 20] 1 1.7 2.61 3.583 6.6749 9.00247 16.70074
(This code was originally posted to the google mail list by Attila, the full discussion can be found here)

This backslash adverb works as

The alternate syntax generalizes to functions of 3 or more arguments where the first argument is used as the initial value and the arguments are corresponding elements from the lists:

Exponential Moving Average Chart

Finally we take our formula and apply it to our stock pricing data, allowing us to see the exponential moving average for two different smoothing factors:

Exponential Moving Average Stock Price Chart produced using qStudio

As you can see with EMA we can prioritize more recent values using a chosen smoothing factor to decide the balance between recent and historical data.

Writing kdb analytics such as Exponential Moving Average is covered in our kdb training course, we regularly provide training courses in London, New York, Asia or our online kdb course is available to start right now.

sql Dashboards 1.31 Released – Interactive Forms

sqlDashboards is a tool for creating real-time sql based charts.
The latest 1.31 release is available to download.

Our new “Forms” now make the charts interactive. here’s an example dashboard showing some stock data, notice the form in the top left allowing selecting a stock ticker and the number of days data to show. On the bottom right is another form containing checkboxes for each country. We can change these selections and the charts will be updated instantly.

Now I modify my selection to ask for more days data, and untick some country checkboxes, to alter which ones are shown in the pie chart, the charts update straight away to give this:

Full details on how to create forms can be found in the sqlDashboards help.
If you use kdb see our “help menu”->Open example kdb dashboard option.

Multiple worksheets and Full Screen

Customers had asked us for to allow multiple worksheets, it’s now been added. As well as a new Full Screen mode to maximise display use when not editing the dashboard, the options can be found here:

We are going to continue to add new functionality…increasingly configurable charts, command line chart generation, web interfaces…if you have any features you would like added please get in touch, we are always happy to receive feedback.

qStudio kdb GUI 1.31 Released – the Command Palette

qStudio is an IDE for kdb+, you can download it now.

The latest 1.31 release introduces a number of nice interface additions as requested by users:

Command Palette

Quick change server -> Hit Ctrl+P to try the new Command Palette
It lets you run common qStudio actions by fuzzy matching on keywords:

Jump to Definition

Hit Ctrl+U Ctrl+I to get an outline of the current file.

Or press Ctrl+D on a function call to jump to where it is defined.

Added User Preferences

Users had mentioned a number of connection and interface issues they wanted to be able to customize, these have been added:
– Customize the editor font and it’s background color (per server setting, useful for red warning color when connected to prod machines)
– keep same connection open for every query
– Wrap every query with selected text before and after

Eval Line by Line

Do you ever query a line, move down, query next line, move down ….
Well try control+shift+enter within the code editor.
It evaluates the current line, returns it’s value and shifts to the next line.

e.g. for the code:
a:11
b:a*rand[10]
c:b*a

The console would show:
q)a:11
11
q)b:a*rand[10]
55
q)c:b*a
605

The qStudio help guide contains more details of all functionality.

Finding Pi using Monte Carlo Simulations in kdb q

In a previous post I looked at using the monte carlo method in kdb to find the outcome of rolling two dice. I also posed the question:

How can we find the value of Pi using the Monte Carlo method?

If we randomly chose an (x,y) location, we could calculate the distance of that points location ( sqrt[x²+y²] ) from the origin, this would tell us if that point lay within a circle or outside a circle, by whether the length was greater than our radius. The ratio of the points that fall within the circle relative to the square that bounds our circle, gives us the ratio of the areas.

A diagram is probably the easiest way to visualize this problem. If we generate two lists of random numbers between -1 to 1. And use those as the coordinates (x,y), then create a scatter plot that plots (x,y) in one colour where x²+y² is greater than 1 and a different colour where it is less than 1, we would find a pattern emerging…in qStudio it looks like this:

We know the area of our bounding square is 2*2 and that areaOfCircle=Pi*r*r, where r is 1. Therefore we can see that:


areaOfCircle = shadedRatio*areaOfSquare
Pi = shadedRatio * 4

q)4*sum[not h]%count h
3.141208


The wikipedia article on monte carlo method steps through this same example, as you can see their diagram looks similar:

Solving the Birthday Paradox in kdb q

In a previous post I looked at using the monte carlo method in kdb to find the outcome of rolling two dice. I also posed the question:

How many people do you need before the odds are good (greater than 50%) that at least two of them share a birthday?

In our kdb+ training courses I always advise breaking the problem down step by step, in this case:

1. Consider making a function to examine the case where there are N people.
2. Generate lists of N random numbers between 0-365 representing their birthdays.
3. Find lists that contain collisions.
4. Find the number of collisions per possibilities examined.
5. Apply our function for finding the probability for N people to a list for many possibilities of N.

In kdb/q:

Plotting our data in using qStudio charting for kdb we get:

Therefore as you can see from either the q code or the graph, you need 23 people to ensure there’s a 50% chance that atleast 2 people in the room share a birthday. For more details see the wikipedia page. This still leaves us with the other problem of finding Pi using the monte carlo method in kdb.

Probability of a 12 when you roll two Dice

Performing probability questions in kdb/q is simple. I recently got asked how to find the probability of rolling a sum of 12 with two dice. We’ll look at two approaches to finding the likely outcomes in kdb/q:

Method 1 – Enumeration of all possibilities

Step by step we:

1. Generate the possible outcomes for one die.
2. Generate all permutations for possible outcomes of two dice, find the sum of the dice.
3. Count the number of times each sum occurs and divide by all possible outcomes to get each probability.

Method 2 – Monte Carlo Simulation

Alternatively , if it hadn’t occurred to us to use cross to generate all possible outcomes, or for situations where there may be too many to consider. We can use Monte Carlo method to simulate random outcomes and then similarly group and count their probability.


q)1+900000?/:6 6 / random pairs of dice rolls
2 5 6 6 2 4 3 1 5 1 1 4 6 5 3 4 2 4 1 2 3 6 6 1 1 3 6 3 6 2 3 1 5 4 4 4 6 3 1 3 1 2 5..
4 4 4 5 1 4 3 6 5 1 4 4 3 4 1 1 1 5 4 5 2 4 4 4 5 2 1 2 6 5 2 4 3 1 4 2 1 1 3 4 6 5 1..
q)/ same as before, count frequency of each result
q)(2+til 11)#{x%sum x} count each group sum each flip 1+900000?/:6 6
2 | 0.02766
3 | 0.05559
4 | 0.08347
5 | 0.11085
6 | 0.1391822
7 | 0.1669078
8 | 0.1386156
9 | 0.1112589
10| 0.08317222
11| 0.05556222
12| 0.02773111


Therefore the probability of rolling a sum of 12 with two dice is 1/36 or 0.27777. Here’s the similar dice permutation problem performed in java.

Kdb Problem Questions

If you want to try using the monte carlo method yourself try answering these questions:

1. The Birthday Paradox: How many people do you need before the odds are good (greater than 50%) that at least two of them share a birthday?
2. Finding the value of Pi. Consider a square at the origin of a coordinate system with a side of length 1. Now consider a quarter circle inside of the square, this circle has a radius of 1, therefore its area is pi/4. For a point (X,Y) to be inside of a circle of radius 1, its distance from the origin (X ², Y²) will be less than or equal to 1. We can generate random (X,Y) positions and determine whether each of them are inside of the circle. The ratio of those inside to outside will give the area. (bonus points for using multiple threads)