Comment by FabHK | Hacker News Reader

Comment by FabHK | Hacker News Reader

A long time ago, our team tried to implement basically a versioned time-series key-value store (ie, you have many keys with daily values, and in addition to key and value it also stored an "as-of" date, so that you could override or correct a value for a specific value date by specifying a newer "as-of" date).

To query a value for a given date, you'd specify key and value date, and it would then give you the value with the latest "as-of" date. Almost always, there'd only be one "as-of" date, and rarely, when a correction had happened, there'd be two, extremely rarely three.

Now, the SQL query then was some sort of group_by and join where as_of = max over the group of as_of. Conceptually, just find the key and date, then pick the last as_of (if there are more than one). But the stupid engine did this massive self-join with a hash-join, and it was terribly slow. The conceptually simple idea turned out to be a disaster.

Made me realise

a) how little I know about DBs.

b) that you can get a correct solution in a language by understanding the language a bit; but to obtain an efficient solution, you need to understand the language rather well.

(Note: the SO question below is just about this topic, and I assume (hope) there are performant solutions to this nowadays. (I worked on this back when Microsoft SQL Server had just introduced an XML datatype for structured unstructured columns...)

https://stackoverflow.com/questions/121387/fetch-the-row-whi... )

Standard sql:

    select key, value, asof
    from (
      select *, row_number() over (partition by key order by asof desc) as rn
      from <table>
    ) t
    where rn = 1

postgresql:

    select distinct on (key)
    key, value, asof
    from <table>
    order by key, asof desc

The DISTINCT ON clause takes the first row that the query returns, which the ORDER BY makes sure is the latest value

Disclaimer: I've used both methods, but haven't tested the perf against each other or the self-join.

Timescaledb adds a custom scan for speeding up distinct on out of the box. Just install extension, no extra work is needed.

https://blog.timescale.com/blog/how-we-made-distinct-queries...

I tried it and it really is that fast.

Fork adding it to postgresql if anyone's interested: https://github.com/jesperpedersen/postgres/tree/indexskipsca...

This is cool, thanks! Bit of a limitation that it only works on a single DISTINCT ON column, hopefully they'll be able to extend it to more in the future. And hope it makes it in for everyone that's on stock postgresql!

Yeah, indeed there's that limitation of a single distinct column. But it works for 80% cases, and it does not require any changes, so it's good. Looks like the earliest time proper implementation could hit mainline is 1.5years away.

We tried the same thing a few years ago in MySQL that was randomly non-performant: 4000x slower. Still waiting for that to be fixed.

Window functions can help here. You can try a self-join with MySQL (and it won't do a hash join because it doesn't have it; it didn't have hash joins at all before 8.10 and it still doesn't have hash outer joins, and what you want to eliminate the older rows is an anti-join, i.e. asserting null on a left join) but honestly you're better off sorting by timestamp and using a manual window when processing the results.

Reply on news.ycombinator.com