Default ordering of index columns and inserts to the already existing data

[ravlio]

Do you have any thoughts on sparse indexes and column preordering (like it is done in the Clickhouse, for instance)? I haven't found anything related (maybe it's already there, sorry then, I'm making my first steps in Rust :) ) in the LocustDB codebase and all the benchmark queries don't seem to imply index usage to leverage it for faster lookups. Even if sorting does not speed up most of the queries, because they imply full scan, analytical functions like LAG and LEAD require ordering and it is important to preorder data rather than order everything on each query.

My next question about inserts and it is related to the previous question. How difficult do you think is to implement the insert of new chunks of data to already present in-memory (and on-disk) columns taking into account that for each such insert you need to merge some data partitions and produce new partitions. Is it worth trying to improve LocustDB in this way and how difficult it could be? Thanks.

[cswinter]

Great questions!

Do you have any thoughts on sparse indexes

I talk about his a little bit at the start of my blogpost. Sparse indices don't help at all with worst case query performance, i.e. queries that touches and aggregates all the data. Furthermore, you can easily get something like 10-100x performance hit from indirect memory accesses scattered throughout memory when compared to just doing a linear scan, so you probably only see benefits on very sparse queries. This is worthwhile if you need to serve a very high volume of queries of this kind, but in my opinion very much the wrong thing to optimize for an analytics system where you have a small number of users that may want to run very expensive queries. The approach taken by LocustDB is to make even these worst case queries blazingly fast through highly parallelized linear scans that can go through the entire memory of each machine within seconds or less. Supporting sparse indices comes at a fairly high cost in terms of code complexity especially in the query planner, ingestion speed (because now you need to update the index), storage overhead for the index, and you pretty much need to know ahead of time what kind of queries you are going to serve and set up the right index. Druid went really deep down the route of implementing very fancy indexing structures, and certainly this has resulted in some interesting papers and the system is widely used, but it is also incredibly complex and actually a lot slower than ClickHouse for many analytics workloads.

column preordering

I think column preordering (and also partitioning tables into chunks that record summary statistics that allow large chunks to be quickly skipped, e.g. the range of values within each column or bloom filters) is very much a worthwhile optimization for this kind of system and especially useful for timestamped data which is one of the primary use cases. I never got around to implementing it in LocustDB but it could be added without any architectural changes.

How difficult do you think is to implement the insert of new chunks of data to already present in-memory (and on-disk) columns taking into account that for each such insert you need to merge some data partitions and produce new partitions.

This is already implemented, the engine supports adding new data while running queries and at one point I had a PoC with LocustDB set up as a server that was continuously ingesting data and serving queries. There isn't a way of accessing this functionality right now through the REPL, but it wouldn't be too difficult to expose.