Cool. I see you're doing a regular (not compensated) horizontal sum in a loop. Horizontal sums are slow, but I'm guessing you wanted to have exactly the same result as if the sum was calculated sequentially (for doubles)? Do you know if any databases use more accurate summation methods (compensated summation)?
Using SIMD to aggregate billions of values per second
31–40 of 74 posts
Re: Using SIMD to aggregate billions of values per second
#32QuestDB co-founder and CTO here - happy to share questdb, a performance-driven open-source time-series database that uses SQL. High performance databases have a reputation of being inaccessible. They are expensive, closed-source, and require complex proprietary languages. We have made our code available under Apache 2.0. Under this new release, QuestDB leverages SIMD instructions, vectorizations and parallel executio…
Thank you for advancing the state of the art! Do you consider offloading some code to the gpu at some point? JITs are really good at doing speculative optimization then deoptimizing if the optimization failed. Couldn't DBs speculatively offload to the gpu (with coherent memory (HSA, etc) access) at least under some constraints/patterns?
Thank you for your kind comment! We would consider offloading to a GPU when the time is right. It feels right to fully utilise CPU capabilities before jumping to GPU.
Re: Using SIMD to aggregate billions of values per second
#33Cool. I see you're doing a regular (not compensated) horizontal sum in a loop. Horizontal sums are slow, but I'm guessing you wanted to have exactly the same result as if the sum was calculated sequentially (for doubles)? Do you know if any databases use more accurate summation methods (compensated summation)?
Are you referring to https://en.wikipedia.org/wiki/Kahan_summation_algorithm by any chance?
If this is the case - we can easily implement this algorithm.
Re: Using SIMD to aggregate billions of values per second
#34Re: Using SIMD to aggregate billions of values per second
#35Super interesting product I'll definitely be taking a deeper look at this when I'm at work tomorrow. I notice all your comparisons are with floating point and integer types. I was recently looking at SIMD as a possible way to speed up some of our calculations. But we create financial software and most data is typically stored as decimals not floating points to avoid problems with binary floating point precision durin…
Thanks! What sort of decimal type is it?
Re: Using SIMD to aggregate billions of values per second
#36Earlier quoted context omitted.
We try to stick to ANSI SQL as best as we can, but we have own own dialect. This should be a good entry point: https://www.questdb.io/docs/select
Why your own dialect instead of Calcite SQL or ZetaSQL?
We support postgres wire protocol, so we are going to be leaning towards PostgreSQL dialect to allow existing PostgreSQL infrastructure connect to us.
Re: Using SIMD to aggregate billions of values per second
#37I came across QuestDB in the past, but never tried myself. At my company, we use kx and onetick. Could you please elaborate why you are also comparing with Postgres since it's not really a time-series database nor revendicating to be part of the "high performance" club?
because they seem to only support that, from their page: "As of now, SIMD operations are available for non-keyed aggregation queries, such as select sum(value) from table." not even sure if they support where clauses on that, sums of functions of a column, or even other things like stddev of the column. their storage format though looks good and simple (similar to kdb actually), but they really should have an 8-byte…
Good summary, thank you.
- we will extend SIMD to where clause, keyed aggregations, sampling, ordering, joins etc. It is a matter of time.
- do you mind elaborating on how we screwed up date and time?
- what makes you think we are never going to compete on performance with kdb+?
Re: Using SIMD to aggregate billions of values per second
#38Cool. I see you're doing a regular (not compensated) horizontal sum in a loop. Horizontal sums are slow, but I'm guessing you wanted to have exactly the same result as if the sum was calculated sequentially (for doubles)? Do you know if any databases use more accurate summation methods (compensated summation)?
Are you referring to https://en.wikipedia.org/wiki/Kahan_summation_algorithm by any chance? If this is the case - we can easily implement this algorithm.
There are several accurate summation algorithms; Kahan is one of them. Looks like Postgresql uses an accurate summation method[0] (and not Kahan), so that's probably a big factor in why theirs is so much slower and also makes for an unfair comparison. FWIW I posted AVX2 and AVX512 Kahan summation implementations here[1].
[0] https://github.com/postgres/postgres/blob/3ed2005ff595d34927...
[1] http://blog.zachbjornson.com/2019/08/11/fast-float-summation...
Re: Using SIMD to aggregate billions of values per second
#39Super interesting product I'll definitely be taking a deeper look at this when I'm at work tomorrow. I notice all your comparisons are with floating point and integer types. I was recently looking at SIMD as a possible way to speed up some of our calculations. But we create financial software and most data is typically stored as decimals not floating points to avoid problems with binary floating point precision durin…
Thanks! What sort of decimal type is it?
Well in code we're using C#'s decimal type (128 bit. 96 bits are used for an integer and the rest used for the sign and scaling factor) [0]. It's essentially just floating point applied to a base 10 integer rather than a binary one.
In the SQL server database the column types are usually decimal(18,5) or decimal(25,12) [1]
[0] - https://docs.microsoft.com/en-us/dotnet/api/system.decimal?v...
[1] - https://docs.microsoft.com/en-us/sql/t-sql/data-types/decima...
Re: Using SIMD to aggregate billions of values per second
#40Earlier quoted context omitted.
Are you referring to https://en.wikipedia.org/wiki/Kahan_summation_algorithm by any chance? If this is the case - we can easily implement this algorithm.
There are several accurate summation algorithms; Kahan is one of them. Looks like Postgresql uses an accurate summation method[0] (and not Kahan), so that's probably a big factor in why theirs is so much slower and also makes for an unfair comparison. FWIW I posted AVX2 and AVX512 Kahan summation implementations here[1]. [0] https://github.com/postgres/postgres/blob/3ed2005ff595d34927... [1] http://blog.zachbjornson.…
Thank you Zach, this is super interesting and useful! I wonder why PG do not use Kahan?