{"id":110986,"date":"2014-09-08T22:24:25","date_gmt":"2014-09-08T22:24:25","guid":{"rendered":"http:\/\/www.timestored.com\/b\/?p=110986"},"modified":"2014-09-08T22:24:25","modified_gmt":"2014-09-08T22:24:25","slug":"time-series-calcs-cache","status":"publish","type":"post","link":"https:\/\/www.timestored.com\/b\/time-series-calcs-cache\/","title":{"rendered":"Pipe-lining Time Series Calculations for Cache Efficiency"},"content":{"rendered":"<p>I always like to investigate new technology and this week I found a nice automatic technique for improved cache use that I had previously seen some people manually write.<\/p>\n<p>Consider a database query with three steps (three SQL SELECTs), some databases may pass results of each step to temporary tables in main memory. When the first step is finished, these intermediate results are passed back into CPU cache to be transformed by the second step, then back into a new temporary table in main memory, and so on. <\/p>\n<p>To eliminate this back-and-forth, vector-based statistical functions can be pipelined, with the output of one function becoming input for the next, whose output feeds a third function, etc. Intermediate results stay in the pipeline inside CPU cache, with only the full result being materialized at the end. <\/p>\n<p>This technology is part of ExtremeDB, they have a video that explains it well:<\/p>\n\r\n<div class=\"media\" itemscope itemtype=\"http:\/\/schema.org\/VideoObject\">\r\n\t\t\t<h3 itemprop=\"name\">Time Series Calculations<\/h3>\r\n\t\t\t<meta itemprop=\"thumbnailUrl\" content=\"\/b\/videos\/mcobject-time-series-database.png\" \/>\r\n\t\t\t<meta itemprop=\"embedURL\" content=\"\/b\/videos\/mcobject-time-series-database.mp4\" \/>\r\n\r\n\t\t\t<video width=\"854\" height=\"480\" poster=\"\/b\/videos\/mcobject-time-series-database.png\" controls>\r\n\t\t\t<source src=\"\/b\/videos\/mcobject-time-series-database.mp4\" type=\"video\/mp4\" \/>\r\n\t\t\r\n\t\t\r\n\t\t\t\t <object id=\"csSWFb\" classid=\"clsid:D27CDB6E-AE6D-11cf-96B8-444553540000\"  width=\"854\" height=\"480\">\r\n\t\t\t\t\t<param name=\"movie\" value=\"\/js\/video_controller.swf\" \/>\r\n\t\t\t\t\t<param name=\"scale\" value=\"showall\" \/>\r\n\t\t\t\t\t<param name=\"bgcolor\" value=\"#1a1a1a\" \/>\r\n\t\t\t\t\t<param name=\"allowfullscreen\" value=\"true\" \/>\r\n\t\t\t\t\t<param name=\"allowscriptaccess\" value=\"always\" \/>\r\n\t\t\t\t\t<param name=\"flashvars\" value=\"tocdoc=left&amp;showsearch=false&amp;xmp=\/b\/videos\/mcobject-time-series-database.xml&amp;autostart=false&amp;autohide=true&amp;content=\/b\/videos\/mcobject-time-series-database.mp4&amp;thumb=\/b\/videos\/mcobject-time-series-database.png&amp;containerwidth=854&amp;containerheight=480&amp;smoothing=true&amp;enablejsapi=true&amp;fullscreen=true&amp;windowbox=false&amp;showbranding=false&amp;showstartscreen=true&amp;showendscreen=false&amp;basecolor=272727&amp;loop=false\" \/>\r\n\t\t\t\t\t<!--[if !IE]>-->\r\n\t\t\t\t\t<object type=\"application\/x-shockwave-flash\" data=\"\/js\/video_controller.swf\"  width=\"854\" height=\"480\">\r\n\t\t\t\t\t   <param name=\"scale\" value=\"showall\" \/>\r\n\t\t\t\t\t   <param name=\"bgcolor\" value=\"#1a1a1a\" \/>\r\n\t\t\t\t\t   <param name=\"allowfullscreen\" value=\"true\" \/>\r\n\t\t\t\t\t   <param name=\"allowscriptaccess\" value=\"always\" \/>\r\n\t\t\t\t\t   <param name=\"flashvars\" value=\"tocdoc=left&amp;showsearch=false&amp;xmp=\/b\/videos\/mcobject-time-series-database.xml&amp;autostart=false&amp;autohide=true&amp;content=\/b\/videos\/mcobject-time-series-database.mp4&amp;thumb=\/b\/videos\/mcobject-time-series-database.png&amp;containerwidth=854&amp;containerheight=480&amp;smoothing=true&amp;enablejsapi=true&amp;fullscreen=true&amp;windowbox=false&amp;showbranding=false&amp;showstartscreen=true&amp;showendscreen=false&amp;basecolor=272727&amp;loop=false\" \/>\r\n\t\t\t\t\t<!--<![endif]-->\r\n\t\t\t\t\t   <div>\r\n\t\t\t\t\t\t   <p>The video content presented here requires JavaScript to be enabled and the latest version of the Adobe Flash Player. If you are using a browser with JavaScript disabled please enable it now. Otherwise, please update your version of the free Adobe Flash Player by <a href=\"http:\/\/www.adobe.com\/go\/getflashplayer\">downloading here<\/a>. <\/p>\r\n\t\t\t\t\t   <\/div>\r\n\t\t\t\t\t<!--[if !IE]>-->\r\n\t\t\t\t\t<\/object>\r\n\t\t\t\t\t<!--<![endif]-->\r\n\t\t\t\t <\/object>\r\n\t\t\t<\/video>\r\n\t\t<\/div>\r\n\r\n\n<h2>Moving Averages Stock Price Example<\/h2>\n<p>This is what the actual code would look like to calculate the 5-day and 21-day moving averages for a stock and detect the points where the faster moving average (5-day) crosses over or under the slower moving average (21-day):<\/p>\n\r\n<textarea class=\"code\" id=\"mcobject-code-132\" cols=\"20\" rows=\"4\">\r\nselect seq_map(ClosePrice,\r\n    seq_cross(seq_sub(seq_window_agg_avg(ClosePrice, 5), \r\n    seq_window_agg_avg(ClosePrice, 21)), 1)) \r\nfrom Security;\r\n<\/textarea>\r\n<script type=\"text\/javascript\">\r\nCodeMirror.fromTextArea(document.getElementById(\"mcobject-code-132\"), {\r\n        lineNumbers: true,\r\n        matchBrackets: true,\r\n        mode: \"text\/x-plsql\", readOnly:true });\r\n<\/script>\r\n\n<ol>\n<li>Two invocations of \u2018seq_window_agg_avg\u2019 execute over the closing price sequence, \u2018ClosePrice\u2019, to obtain 5-day and 21-day moving averages.\n<\/li>\n<li>The function \u2018seq_sub\u2019 subtracts 21- from 5-day moving averages;\n<\/li>\n<li>The result \u201cfeeds\u201d a fourth function, \u2018seq_cross\u2019, to identify where the 5- and 21-day moving averages cross.\n<\/li>\n<li>Finally, the function \u2018seq_map\u2019 maps the crossovers to the original \u2018ClosePrice\u2019 sequence, returning closing prices where the moving averages crossed.\n<\/li>\n<\/ol>\n<p>This approach eliminates the need to create, populate and query temporary tables outside CPU cache in main memory. One &#8220;tile&#8221; of input data is processed by each invocation of \u2018mco_seq_window_agg_avg_double()\u2019, each time producing one tile of output that is passed to \u2018mco_seq_sub_double()\u2019 which, in turn, produces one tile of output that is passed as input to mco_seq_cross_double(), which produces one tile of output that is passed to mco_seq_map_double().  When the last function, mco_seq_map_double() has exhausted its input, the whole process repeats from the top to produce new tiles for additional processing.<\/p>\n<p>A very cool idea! <\/p>\n<p>And yes, <a href=\"http:\/\/www.mcobject.com\/extremedbfamily.shtml\">ExtremeDB<\/a> are the same guys that posted the top Stac M3 benchmark for a while (in 2012\/13 I think).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I always like to investigate new technology and this week I found a nice automatic technique for improved cache use that I had previously seen some people manually write. Consider a database query with three steps (three SQL SELECTs), some databases may pass results of each step to temporary tables in main memory. When the [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_bbp_topic_count":0,"_bbp_reply_count":0,"_bbp_total_topic_count":0,"_bbp_total_reply_count":0,"_bbp_voice_count":0,"_bbp_anonymous_reply_count":0,"_bbp_topic_count_hidden":0,"_bbp_reply_count_hidden":0,"_bbp_forum_subforum_count":0},"categories":[23],"tags":[63,64,65,24],"_links":{"self":[{"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/posts\/110986"}],"collection":[{"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/comments?post=110986"}],"version-history":[{"count":2,"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/posts\/110986\/revisions"}],"predecessor-version":[{"id":110988,"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/posts\/110986\/revisions\/110988"}],"wp:attachment":[{"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/media?parent=110986"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/categories?post=110986"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.timestored.com\/b\/wp-json\/wp\/v2\/tags?post=110986"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}