22 ms·
Using SIMD to aggregate billions of values per second
- bluestreak 7y agoQuestDB 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 execution to achieve performance figures at the top of the high-performance databases. Results are shown in our blog post. I sincerely hope that you will find this helpful, and that this will unlock new possibilities! In the meantime, we will carry on working on QuestDB, adding more features, and taking this speed to more query types. Feel free to join us on slack or Github if you want to participate.
- The_rationalist 7y agoThank 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?
- TheTank 7y agoThank 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.
- lsb 7y agoThis looks super interesting! 1) How does this compare to BlazingDB/MapD/etc, especially in queries on <some benchmark> per $ per hour on AWS? 2) I don't see a way to give you money. What ensures that QuestDB will be around in the future if I architect my data pipelines around this product?
- bluestreak 7y agoThank you! 1) We didn't compare directly, but our aim is to squeeze as much performance out of hardware as possible to minimize cloud cost. If we are not the best at this right now - we are going to be the best. 2) We are VC funded with 24 months runway. The product is Open Source Apache 2.0 and will remain as such forever. Any future commercial offering will use open source product as a library.
- dkersten 7y agoOn point 2, I hope you have a good monetisation strategy. I’m a bit wary of new open source databases that don’t have a solid strategy for when their funding runs out, too many times have projects been more or less abandoned after funding ran out, despite being open source (eg Rethinkdb), so I’m rather wary of relying on something until it’s been well established. (Although even basho eventually shut down despite being well established...)
- deleted 7y ago[deleted]
- gautamcgoel 7y agoI'm curious what your business model is. Don't you worry that releasing your product for free will cut into your revenue?
- TheTank 7y agoIn the future, we will release other products with features geared towards enterprises. We don't think that having our code open will harm the business. On the contrary, it will hopefully help us gain some popularity by allowing any developer to access latency levels only seen in trading. We hope that QuestDB will allow them to stop worrying about database performance bottlenecks.
- amenod 7y agoJust wanted to point out a small typo in the docs: "LASTEST BY" (https://www.questdb.io/docs/crudOperations https://www.questdb.io/docs/crudOperations)
- bluestreak 7y agothanks a lot! fixed
- numlock86 7y agoSerious but bold question: What are the benefits versus Clickhouse for example? Why should I use QuestDB? Amazing work either way. The space of databases can never have too much competition.
- bluestreak 7y agoIt is hard for me to say right now as we did not benchmark against Clickhouse yet, this is clearly the most requested comparison. We will come back on this!
- throwaway_pdp09 7y agoI'll have to be careful here as I've no experience either with your DB or Postgres, but comparing questDB with PG and using that to claim it's 100X faster may be technically true but a bit of a dirty trick. It's perhaps like comparing a lorry with an F1 car and being surprised at the winner. I'm also a little surprised at the speedup using SIMD. If it's RAM constrained, and it clearly is because it scales with the number of memory channels, then I completely fail to understand how instructions - which are bloody fast to execute (SIMD or not) compared to slow RAM access - could benefit you. Both SIMD or not should be waiting on memory AFAICS. Except you clearly do get a big speedup, could anyone enlighten me on this?
- jeromerousselot 7y agoGreat work! 2.3x faster than kdb and 500x than postgres for sum (double) time series What are your goals for the next release?
- bluestreak 7y agothank you! Next release will feature similar acceleration of group-by and time sampling queries.
- quod_2058 7y agoI 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?
- bluestreak 7y agoYou are right, PostgreSQL is not necessarily optimal for time-series workloads. In this case, the benchmark is a simple task, and not related to time-series. It's consists of reading 1 billion values to a table and sum them together. It doesn't get simpler than that. The reason we are showcasing this instead of other more complex queries is because this is a simple, easily reproducible benchmark. It provides point of reference for performance figures.
- jnordwick 7y agobecause 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 char instead of the 16-byte one since that would be far more used. their partitioning scheme is only on time so less advanced than other system. single designated timestamp column (so no bitemporal), but do support asof joins which is nice. they totally screwed up on dates and time. dates only to milli and timestamps only to micros. huge mistake. long256 which is nice, but strangely no long128s (which wind up being nice when you have base-10 fixed-point numbers normalized to a large number of decimals). i didn't see any fixed-width string/byte columns. Does have 32-bit symbols (i assume similar to kdb?) that might cover some of those use cases. some good and some bad in there. never going to compete with kdb or onetick on performance (and nobody competes with kdb on query language/extensibity) , but could find a niche based on price and having simpler more easily adapted to querying and more human interface.
- bluestreak 7y ago
- sirffuzzylogik 7y agoThe numbers are impressive, especially because it is against kdb. q/kdb is mostly finance focused and closed source so not really flexible. questdb has an advantage on this, it might be a bit of a tangent but I wonder if this could be used to replace redis, I can see how having SQL as a querying language could be a big plus.
- bluestreak 7y agoit would depend on the use case of course. QuestDB goes a bit further in that it provides speed close to in-memory loads while actually storing the data on disk. If there is enough interest, we could consider releasing an "in-memory only" mode for these use cases.
- deleted 7y ago[deleted]
- jmakov 7y agoSo how does it compare to Clickhouse?
- bluestreak 7y agoWe have not benched against clickhouse yet. Sorry. Sounds like this should be an interesting things to do!
- missosoup 7y agoThe broader question though is how does your offering compare to Clickhouse?
- j1897 7y agoco-founder of questdb here - we have been asked the same question on reddit as well. We are starting to work on an article going through a comparison between QuestDB and Clickhouse today - this will also include a bench. Will share as soon as we can. stay tuned!
- continuations 7y agoWhat about data compression? How does that compare to other time series DBs?
- bluestreak 7y agoThere is no dedicated data compression at the moment as our use-case is centered around performance. That being said, we store data very efficiently with minimal overhead. One interesting consequence is that in many cases, we don't require indexes where other databases do. This synthetically compress the data relative to other DBs by removing the space taken by these indexes while improving query speed. It also means ingestion speed remains fast with O(1) complexity.
- continuations 7y ago> we store data very efficiently with minimal overhead. Do you use encoding like delta-of-delta timestamps or something similar? > One interesting consequence is that in many cases, we don't require indexes where other databases do. I don't follow. Why don't you require indexes where other databases do? Thanks.
- bluestreak 7y agoWe don't store deltas, timestamps are stored as 64-bit int back to back in column. So are other primitives actually. To avoid using indexes we store timestamps in ascending order. Timestamp interval search uses partitioning to cull chunks of data before lifting data in memory. Once in memory we use binary search on ordered timestamps to find intervals. That said we do support indexes for key-based lookups
- popotamonga 7y agoI assume the values must be all be in memory beforehand and not hard storage.
- bluestreak 7y agoThat sum() SQL is all you do as a user. There is no additional magic there. The performance numbers are indeed best when data is in memory. However in reality sum() goes over memory mapped file, lazy loading data as required.
- heartbeats 7y agoSo how would this compare to the naïve approach of using a cursor in another fast, memory-mapped database, like LMDB?
- stereosteve 7y agoIn the reference there's no mention of SQL Window functions. Is it possible to do multiple moving averages over different time spans? If not, are there plans to add support in the future?
- TheTank 7y agoWindow functions are in draft, we will release them imminently. We will support moving averages. In fact we plan to support generic multi-pass and window functions. Having multi-pass will allow you to do things like `select sum(x -sum(x)) from tab`.
- jnordwick 7y agothose things are so useless if your time points arent equidistant (ie, you don't care about the last 100 rows, you care about the last 5 minutes). they basically force you to use very slow correlated subqueries. please do something better.
- leeoniya 7y agonot to hijack too much, but since this is on the topic of timeseries...i'm currently working on a fast* Canvas2D timeseries chart: https://github.com/leeoniya/uPlot https://github.com/leeoniya/uPlot * ~4,000 pts/ms on an i5 and integrated gpu
- fake-name 7y agoThis is super interesting and quite relevant to a bunch of stuff I do at work. Next time I have a project that involves real-time plotting of data, I'll definitely take a look!
- mrtweetyhack 7y agothis is pretty cool!
- bufferoverflow 7y agoWhy canvas2d when WebGL is much faster?
- leeoniya 7y agoa few reasons. the main one is that i know canvas and can implement everything i need, but would need to learn a lot of webgl to get any further than a basic PoC. browsers limit how many webgl contexts you can acquire. chrome is capped at 16, so if you need more than 16 charts on a page, you're out of luck. initializing webgl is actually slower than canvas 2d. it's difficult to draw lines of different thicknesses in raw webgl - it takes a lot of code. there are projects which abstract webgl nicely to provide canvas-like ergonomics, like Two.js, Pixi.js, or Canvas2DtoWebGL/litegl [1], but they would make the codebase much larger and more complex. [1] https://github.com/jagenjo/Canvas2DtoWebGL https://github.com/jagenjo/Canvas2DtoWebGL
- georgewfraser 7y agoWhat dialect of SQL are you using?
- bluestreak 7y agoWe 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 https://www.questdb.io/docs/select
- georgewfraser 7y agoWhy your own dialect instead of Calcite SQL or ZetaSQL?
- bluestreak 7y agoWe support postgres wire protocol, so we are going to be leaning towards PostgreSQL dialect to allow existing PostgreSQL infrastructure connect to us.
- SimonPStevens 7y agoSuper 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 during calculations. Does quest handle decimals, just without the SIMD speed up? Is this just a dead end? Are there any SIMD implementations that deal with decimal numbers? I considered Hacky workarounds like using integer based types internally and then treating them as as fixed point decimals for display but that doesn't give enough range for my purposes.
- bluestreak 7y agoThanks! What sort of decimal type is it?
- SimonPStevens 7y agoWell 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?view=netframework-4.8 https://docs.microsoft.com/en-us/dotnet/api/system.decimal?v... [1] - https://docs.microsoft.com/en-us/sql/t-sql/data-types/decimal-and-numeric-transact-sql?view=sql-server-ver15 https://docs.microsoft.com/en-us/sql/t-sql/data-types/decima...
- bluestreak 7y agothanks! Someone else also pointed at lack of 128-bit long support. It looks as if long128 might help here.
- throwaway_pdp09 7y agoCan't you just use a binary int with the few bits being an implicit fraction (or just count in 'pennies' AKA the lowest denominction of that currency). Seems a straightforward solution, no?
- zbjornson 7y agoCool. 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)?
- bluestreak 7y agoAre you referring to https://en.wikipedia.org/wiki/Kahan_summation_algorithm https://en.wikipedia.org/wiki/Kahan_summation_algorithm by any chance? If this is the case - we can easily implement this algorithm.
- zbjornson 7y agoThere 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/3ed2005ff595d349276e5b2edeca1a8100b08c87/src/backend/utils/adt/float.c#L2723 https://github.com/postgres/postgres/blob/3ed2005ff595d34927... [1] http://blog.zachbjornson.com/2019/08/11/fast-float-summation.html http://blog.zachbjornson.com/2019/08/11/fast-float-summation...
- bluestreak 7y agoThank you Zach, this is super interesting and useful! I wonder why PG do not use Kahan?
- polskibus 7y agoIt would be great if you include clickhouse in your benchmark. It also boasts heavy SIMD use and is free + open source.
- johndoe42377 7y agoThis can't be called a database due to lacking of any persistent storage. It does not survive a system crash. It is a structured in-memory (or rather in-JVM) cache with a rudimentary SQL interface. Calling things by its proper names is a half-way to intelligence.
- sch00lb0y 7y agois it difficult to add SIMD to the existing time-series database?
- jnordwick 7y agocolumnar, probably. row-based not possible.
- binomiq 7y agoWere these benchmarks before or after 2020.03.26? There was a bug that caused max operations to take twice as long. From the KDB+ 4.0 release notes: 2020.03.26 FIX fixed performance regression for max. e.g. q)x:100000000?100;system"ts:10 max x"
- bluestreak 7y agothese are against the latest 4.0 KDB+, after 26 March. KDB before that could not aggregate in parallel implicitly.
- binomiq 7y agoIn your benchmarks, KDB's max on longs takes twice as long as sum on longs. I am not able to replicate this with the most recent version of KDB (2020.03.30). $QHOME/l64/q -s 4 KDB+ 4.0 2020.03.30 Copyright (C) 1993-2020 Kx Systems l64/ 4()core 516718MB <snip> q)zz:1000000000?1000j q)0.01*system"t do[100;max zz]" 257.52 q)0.01*system"t do[100;sum zz]" 251.95 There's a marginal difference here rather than double. For the version of KDB with the regression bug: q)0.01*system"t do[100;max zz]" 512.21 q)0.01*system"t do[100;sum zz]" 254.24 Which starts to look more like your numbers.
- bluestreak 7y agosorry, i think we tested with this one: KDB+ 4.0 2020.03.17 Copyright (C) 1993-2020 Kx Systems l64/ 12(16)core 63960MB EXPIRE 2021.03.26
- dintech 7y agoEven without that 2x, all benchmarks are still in the same ballpark which is impressive in its own right. It will be interesting to see where this goes.