Multithreaded execution in Firebolt

[@ishugpt17]

What is the memory layout of the tablets and the independent chunks in RAM and what do they represent? For cores to be able to work truly independently, there should not be any contention (data to be accessed should not fall on same cache line) while accessing the chunks in main memory, so how do we ensure that?

[@BenjaminWagnerFirebolt]

Great question! For us, batches of a few thousand rows are the finest granularity we can access data at. These batches are stored in our columnar format and then compressed independently (e.g. using LZ4). Worker threads can then pick these batches independently. Note that the granularity is a lot bigger than cache lines here: usually one of the tasks we pick has data that uses the whole L1 cache. As the cores can then work on these L1 sized chunks of data independently, contention isn't a big problem. The thing that's hard is what to do with operators such as joins and aggregations where some cross-core coordination is required. Here we invested a lot into having algorithms that minimize contention. For example when building a hash join, our hash tables are naturally partitioned and different threads build the hash table for different partitions. This allows us to scale up even for very complex query patterns. Andy Pavlo has a great lecture on query scheduling here: kzbin.info/www/bejne/jIvNq36Mm7pnbM0 The state-of-the-art paper for this is "Morsel-driven parallelism: a NUMA-aware query evaluation framework for the many-core age" by Leis et al.