Using SIMD to aggregate billions of values per second
questdb.io
questdb.io
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.
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?
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?
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.
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.
Amazing work either way. The space of databases can never have too much competition.
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?
https://github.com/leeoniya/uPlot
* ~4,000 pts/ms on an i5 and integrated gpu
Next time I have a project that involves real-time plotting of data, I'll definitely take a look!
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.
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.
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...
If this is the case - we can easily implement this algorithm.
[0] https://github.com/postgres/postgres/blob/3ed2005ff595d34927...
[1] http://blog.zachbjornson.com/2019/08/11/fast-float-summation...
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.
"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.
- 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+?
Also when you are trying to do calculations on high-frequency data (tick, iot) it ruins your ability to take meaningful deltas (eg, arrival rates) since you get a lot of 0s and 1s for the time deltas. Its difficult to take weighted averages with weights of 0s.
the issues solving that (if you really need a wider range) are easier to solve that having to force everything down to micros and creating ways around that. (eg, kdb uses multiple date, time, and timestamp types and it doesn't use the unix epoch since it isn't very useful for tick, censor, or any high-frequency data i've seen).
better than a double that some systems still use.
-kdb's secret sauce that people don't seem to understand is its query language that more naturally fits the time series domain. It isn't really a database as more it is an array language with a database component. (eg, try to write an efficient sql query that calculates 5 minute bars on tick data).
I actually like Java too - I've written or worked on a couple trading systems written in core java. just get good devs who understand what it means to write zero gc code, abuse off-heap memory, and understand what hotspot can intrinsify. If you can stay in the simd code for all the heavy lifting loops (filters, aggregates, etc), I don't think java will be an impediment.
I think you have parts going in the correct direction, and you seem to have good experience from looking at the bios. Nothing really un-fixable (or un-addable) in what I saw glancing at your docs. I did bookmark you to see how the db goes. Will prob check out soon.
Are you referring to the clock precision of consumer grade hardware here?
In my experience the vast majority of financial time series data is reported in nanoseconds. The data providers, vendors, exchanges and data brokers absolutely have hardware capable of measuring timestamps in nanoseconds.
The accuracy doesn't have to be to 1ns of resolution to warrant measuring in nanos - even to the nearest 100ns is a useful and meaningful improvement beyond micros.
1707.09.22D00:12:43.145224194 (max negative) to 2292.04.10D23:47:16.854775806 (max positive)
With 0 at 2000.01.01D00:00:00.000000000
I, of course, am not disparaging your work, the performance numbers are very impressive!
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"
$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
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
KDB+ 4.0 2020.03.17 Copyright (C) 1993-2020 Kx Systems
l64/ 12(16)core 63960MB
EXPIRE 2021.03.26If not, are there plans to add support in the future?
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.
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.
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.
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
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.