As of Join Performance a surprising result

The Kx wiki describes in detail how to structure as of join queries for best performance.

https://code.kx.com/wiki/Reference/aj

3. There is no need to select on quote, i.e. irrespective of the number of quote records, use:

aj[`sym`time;select .. from trade where ..;quote]

instead of

aj[`sym`time;select .. from trade where ..;
             select .. from quote where ..]

The reason for this is that since the quote table is partitioned on date and grouped on sym the as of join function simply scans the sectors of the disk in linear order and grabs the first matches using binary search.

Linear access to disk is very different from random access.  So when you perform a search linearly on partitioned historical database it runs pretty fast.

However, someone asked me if you were going to query over and over, the same data whether then it made sense to do some pre-filtering on the quote table before doing multiple ajs.

At the time, I said it shouldn’t be faster. I thought that the overhead of reading from disk afresh each time was going to be much smaller than the overhead of allocating a very large amount of room in memory.

So I tested it:

taj1:{[t;d] now:.z.T;
do[10;aj[`sym`time;select from t where date=d;select from quote where date=d]];        after:.z.T;
after-now}

taj2:{[t;d]
now:.z.T;
quotecache:select from quote where date=d, sym in exec sym from t;                                do[10;aj[`sym`time;select from t where date=d;quotecache]];
after:.z.T;
after-now}

The timings, were not even close the taj2, which precaches data when run 10 times, for a trade table with only 1000 records on only 100 symbols took more than 5 minutes to run. While taj1 was taking only 5 seconds, that is approximately 2 aj per second.

When I scaled the number of symbols to 1000, the cached version didn’t comeback and I had to cancel the query after 25 minutes.  The non cached version took 10 seconds or 1 aj per second.

The intuition is correct, if you can prefilter, then not having to read in all the data twice should be faster. So I checked the meta of the cached table, it was loosing the p attribute while filtering. 

I then created version taj3:

taj3:{[t;d]
now:.z.T;
quotecache:update `p#sym from select from quote where date=d, sym in exec sym  from t;
do[10;aj[`sym`time;select from t where date=d;quotecache]];
after:.z.T;
after-now}

If you reapply the p attribute the first query for 1000 symbols costs you 3.6 seconds, but increasing the number of times you run the aj is almost free. So running 10 times only costs 4 seconds. Running 20 times the taj3 also took 4 seconds. So if you know you have a limited universe than reducing and pre-filtering is worth it if you will be running the queries again and again, JUST REMEMBER TO REAPPLY THE P ATTRIBUTE. Since the quote table is only filtered, the p attribute will be a really cheap operation, since order is preserved.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s