News for hackers. Stuff that matters.
Re:Window Functions in SQL (2013) by jnordwick on Wednesday October 05, 2016 @12:16PM (#12645187)
LAG/LEAD are basically SQL having to give in a little to the timeseries and column db people. It obliterates the set theoretic nature of SQL, and they are dog slow.

This is why any decent columnar/timeseries db has its own often arrish query language to take advantages of ordering information inherent in the data. There is an order in that index and SQL table, you just don't have good tools to access and use it.

This touches on a conversation I was having a couple weeks ago where somebody was saying that column/array storage is purely a backend consideration and don't need to care about it in the front end of the database. That view gets you ugly primitives like LAG/LEAD. Being able to exploit your backend decision is paramount to performance.

Products like Informix or KDB+ just give you full access to the data on and off disk as an array so you ca build complex windowing primitives (and even store them and reuse them later).

(PS: I just find this really funny. KDB+ is probably is the only database I know that literally does streaming analytics on a Raspberry Pi. No joke, the full DB on Linux ARM/Pi. https://kx.com/download/ )

Re:Window Functions in SQL (2013) by alfalfasprout on Wednesday October 05, 2016 @02:55PM (#12646678)
KDB+ is incredibly well designed, fast, and very mature. But it has one big problem. At $$$ / year (can't divulge pricing due to NDAs but it's > $10^4 for a very modest installation) you're talking about a massive expense if you want any kind of large deployment.
Re:Window Functions in SQL (2013) by jnordwick on Wednesday October 05, 2016 @03:09PM (#12646797)
I love KDB. When I first started, I hated it... with a fierce passion. I didn't see the point, but I was young and dumb and better looking.

When the "Why's that company so big? I can do that in a weekend." article came out last week:

https://news.ycombinator.com/item?id=12626314

I immediately thought of Kx and KDB and how it is literally the exact opposite. If people only knew how small the firm started with Arthur hacking away seemingly out developing entire corporations they would laugh.

"Yeah give me about two years and a dev team of a about 20 then about 10 for QA and we've have something shippable... abother year or two for performance... 5 years we'll be in the hunt." Yeah, we'll this guy over here basically did it in six months with only two others. And it's 100x faster than anything else. Why can't you do that?

Given his history too with A+ at Morgan Stanley, it wouldn't be the first time a team of a small handful he was at the core of beat the socks off everybody else either. Some people just have this amazing ability to see simplicity. I've had the pleasure of being around a few people boss like that.

Re:Window Functions in SQL (2013) by saurik on Wednesday October 05, 2016 @12:41PM (#12645440)
Exciting! Can you point at something where one could learn about this specific feature of these kinds of databases? (Maybe like, "this is an example of that aspect of their syntax in particular, go read how it works", or "here is an article taking about how awesome this property is".)
Re:Window Functions in SQL (2013) by jnordwick on Wednesday October 05, 2016 @01:54PM (#12646127)
Not exciting. Most of the array processing / streaming facilities are steaming piles.

You have Hadoop/MR and Monet in the OSS group. SysbaseIQ, KDB, Teradata, Vertica, VectorWise, etc. all provide either extended SQL or additional query support to use ordering information in some (often weak) way.

You can even count Oracle In Memory Analytics with TSQL with its cursor model if you really want.

For example for KDB to get the last price and sum of volumer for each second of AAPL you would do in KSQL:

  select last px, sum vol by time.second from trade where sym=`AAPL
on it can be done in its lower level language K/Q as (approx, I'm a little rusty)

  g:group trade.time.second @ where trade.sym=`AAPL
  flip`px`vol!(last each trade.px g; sum each trade.vol g)
Re:Window Functions in SQL (2013) by lukaseder on Wednesday October 05, 2016 @01:51PM (#12646094)
I would be very surprised if LEAD and LAG couldn't profit from indexing, if you design your query / window function in a way that it actually can profit.

Perhaps you're hinting at the idea that it's too easy to screw this up as a user, for it to be inefficient

Re:Window Functions in SQL (2013) by jnordwick on Wednesday October 05, 2016 @02:25PM (#12646423)
The doesn't help that much since you are probably already using an index for filter criteria, the table is probably unkeyed (fact table).

The case it does work is that you are ordered on timestamp (for example), the query planner properly figures to use any filtering indexes and sequential indexes, ... magic occurs

Now the job is making an SQL statement that the query planner can actual understand and optimize since SQL lacks so much of the machinery for order-dependent processing (this was a feature when SQL was conceived remember).

Re:Window Functions in SQL (2013) by lukaseder on Thursday October 06, 2016 @02:10AM (#12650558)
What if I'm designing a covering index to cover for both my filtering and ordering needs? The SQL engine should pick that up in my opinion and avoid needing to re-order anything.

Of course, SQL is by far more general purpose than producing ordered stuff. In fact, ordering is a completely non-relational thing that was even criticised in SQL in early days (such as offsets, limits, duplication, etc.). But SQL has learned to shoehorn foreign concepts into the language / platform for a long time, so I'm just curious about a concrete example where SQL window functions fail (and couldn't be fixed) in SQL for you.

Re:Window Functions in SQL (2013) by jnordwick on Thursday October 06, 2016 @02:43AM (#12650664)
Try doing a VWAP in a group by 5000 stock symbol over a LAG of last 30000 - basically a sample every 10 millis for 5 minutes. This is the simple case where you can actually use LAG of a fixed amount.

(When the query returns tomorrow morning you realize that LAG was actually useless because your observation arrivals weren't periodic and you need to deal with / bucket for that to actually get usable results).

We used to run a lot of LEAD/LAG queries on a very, very large Oracle install could never get the performance we wanted out of it. Basically turned it into a very expensive file server that spat out HDF that we then processed by a mix of shell and python. Should not have been faster than the overpriced heater in the corner we called a database but was.

Re:Window Functions in SQL (2013) by thom on Thursday October 06, 2016 @04:35AM (#12650994)
Just to clarify, when you say LEAD/LAG here, do you actually mean ROWS/RANGE? So, approximately:

    sum(price * quantity) over w / sum(quantity) over w as VWAP
    ⋮
    window w as (partition by stock order by time range 30000 preceding)
Totally willing to believe first-hand experience, but surprised and disappointed if it's impossible to make that fast. (Apologies if I'm totally misunderstanding the use case).
Re:Window Functions in SQL (2013) by jnordwick on Thursday October 06, 2016 @11:23AM (#12653243)
Is there really that much of a difference between LEAD/LAG and OVER+RANGE when using an aggregation function? I'm sure there is, but it has been a few years since I had to deal with some of this.

There are probably also difference between OVER when used in TSQL and PLSQL.

Last time I had to do this was actually with real-time advertising bidding, and it was across keywords, not ticker symbols (many more, much sparser). We had a 20 millisecond budget, and had to break the queries up to at least get partial results to push out bid even if we didn't have all the results back in from the database that we wanted.

We used OVER+RANGE for average price, but needed LAG for first derivative (is the price trending up or down). We had to start doing roll ups of the data hourly and be constantly trimming to keep the real-time performance high enough, but that meant we needed to have have a separate off-line analytical system. Common to do, but still I think it can be done without it if you use the correct tech stack.

Re:Window Functions in SQL (2013) by lukaseder on Thursday October 06, 2016 @04:13PM (#12655695)
What you're doing certainly doesn't sound like an easy job for window functions, although it might be possible with RANGE + interval - at least in Oracle 12c.

How about Oracle 12c's MATCH_RECOGNIZE, though?

http://www.oracle.com/ocom/groups/public/@otn/documents/webc...

Re:Window Functions in SQL (2013) by jnordwick on Thursday October 06, 2016 @09:06PM (#12657414)
Thanks. That was very interesting. Overall, a total band-aid of course, but still better than nothing. I can completely see doing ad hoc queries with that (and I can't wait to try it out) but I fear the performance hit of trying to build a system around it :)

It didn't give any examples of queries going both directions, e.g. the down-up V first example. You probably often also want the up-down ^ shapes too. It would be nice if the PATTERN had alternation too "STRT (DOWN+ UP+)|(UP+ DOWN+)" so you didn't need to double your queries. Or else you're probably better off creating a temp on CUR-LAG(1) to give you the sign and then pattern match the sign (if that makes sense).

Oracle really does go out of their way to keep SQL modern though. I remember the first time I saw a "CONNECT BY". lol. I had an interview a few months later and was asked to write an SQL query to basically traverse a tree (the gist of it). I being a young smart ass gave the correct answer (you can't) and proceeded to write the START / CONNECT just to show off a little.

Re:Window Functions in SQL (2013) by lukaseder on Friday October 07, 2016 @04:55AM (#12659121)
Yes, it's a band-aid. But perhaps it will feel less so, if you're looking at the original invention by Esper Tech (I have no experience with it, just know that I've seen MATCH_RECOGNIZE there first): http://www.espertech.com/esper/release-5.1.0/esper-reference...

Hah, yeah CONNECT BY is great for simple recursion, but for more complex (probably less performing) cases, I prefer the standard approach with CTEs...

Re:Window Functions in SQL (2013) by Jweb_Guru on Thursday October 06, 2016 @01:47AM (#12650478)
Eh, there's been work done on this, e.g. order dependencies. Not sure how much of it has made it into commercial SQL engines, though.
Re:Window Functions in SQL (2013) by jnordwick on Friday October 07, 2016 @07:28AM (#12659781)
link?
Re:Window Functions in SQL (2013) by Jweb_Guru on Friday October 07, 2016 @12:03PM (#12661697)
Here's one: https://arxiv.org/pdf/1208.0084v1.pdf

(Note the involvement of IBM. Dunno whether this has made it into DB2, but a lot of really interesting research has; also keep in mind that whatever IBM wants to put in DB2 has a high probability of making it into the SQL standard).

Re:Window Functions in SQL (2013) by thom on Wednesday October 05, 2016 @01:31PM (#12645894)
Do you know what the story is for using geospatial data with KDB+?
Re:Window Functions in SQL (2013) by jnordwick on Wednesday October 05, 2016 @02:10PM (#12646276)
This is about the closest I know. Kx does a lot with utilities for metering and IoT stuff, but I haven't really kept up with that side of things as much as I do with the finance side. However I do know there are some using it for geospatial, and they are always eager to push into new areas so love the challenge. If a new datatype/index type needs to be done to support geospatial and be the fastest there, they are always up to the challenge.

There were a couple really, really cool tech talks I've been to. The title alone gives it props :)

"where Rumsfeldism & Kx collide"

https://kx.com/2014/12/07/visualizing-really-big-data/

in case you're curious about one of the other: a polymer hypergrid with an absurd amount of real time updating data:

http://openfin.github.io/fin-hypergrid-polymer-demo/componen...

Re:Window Functions in SQL (2013) by aksyn on Saturday October 08, 2016 @05:14AM (#12666247)