A blog by and for database architects.
As the number of CPU cores keeps growing, the scalability of concurrent data structures becomes increasingly important. A data structure that works fine on 4 cores can become a bottleneck on 32, not because of algorithmic limitations, but because of how it synchronizes access. We illustrate that with a simple binary tree. Usually these data structures are protected by some kind of lock: struct…
During automated testing we stumbled upon a problem that boiled down to transitive comparisons: If a=b, and a=c, when we assumed that b=c. Unfortunately that is not always the case, at least not in all systems. Consider the following SQL query: select a = b, a = c , b = c from ( values ( 1234567890123456789 . 0 ::double precision , 1234567890123456788 :: bigint , 1234567890123456789 :: bigint ))…
Query compilation based on the produce/consume model has a reputation for delivering high query performance, but also for being more difficult to implement than interpretation-based engines using vectorized execution . While it is true that building a production-grade query compiler with low compilation latency requires substantial infrastructure and tooling effort what is sometimes overlooked is…
On a whim I decided to do this years advent of code in pure SQL. That was an interesting experience that I can recommend to everybody because it forces you to think differently about the problems. And I can report that it was possible to solve every problem in pure SQL . In many cases SQL was actually surprisingly pleasant to use. The full solution for day 11 (including the puzzle input) is shown…
In November, I had the pleasure of attending the Dutch-Belgian DataBase Day , where I moderated a panel on practical challenges often overlooked in database research. Our distinguished panelists included Allison Lee (founding engineer at Snowflake), Andy Pavlo (professor at CMU), and Hannes Mühleisen (co-creator of DuckDB and researcher at CWI), with attendees contributing to the discussion and…
About three years ago we noticed serious performance problems in C++ exception unwinding . Due to contention on the unwinding path these became more and more severe the more cores a system had, and unwinding could slow down by orders of magnitude. Due to the constraints of backwards compatibility this contention was not easy to eliminate, and P2544 discussed ways to fix this problem via language…
Due to better access locality, B-trees are faster than binary search trees in practice -- but are they also better in theory ? To answer this question, let's look at the number of comparisons required for a search operation. Assuming we store n elements in a binary search tree, the lower bound for the number of comparisons is log 2 n in the worst case. However, this is only achievable for a…
In recent years, flash-based SSDs have largely replaced disks for most storage use cases. Internally, each SSD consists of many independent flash chips, each of which can be accessed in parallel. Assuming the SSD controller keeps up, the throughput of an SSD therefore primarily depends on the interface speed to the host. In the past six years, we have seen a rapid transition from SATA to PCIe 3.0…
For at least five decades, Moore's law consistently delivered increasing numbers of transistors. Equally significant, Dennard scaling led to each transistor using less energy, enabling higher clock frequencies. This was great, as higher clock frequencies enhanced existing software performance automatically, without necessitating any code rewrite. However, around 2005, Dennard scaling began to…
Since 1975, over 24 thousand articles have have been published in major database venues (SIGMOD, VLDB/PVLDB, ICDE, EDBT, CIDR, TODS, VLDB Journal, TKDE). The number of papers per year is rising: Over time, the topics change. Looking at the percentage of keywords appearing in paper titles (in that particular year), we can see interesting trends:
The Conference on Innovative Data Systems Research (CIDR) 2023 is over, and as usual both the official program and the informal discussions have been great. CIDR encourages innovative, risky, and controversial ideas as well as honest exchanges. One intensely-discussed talk was the keynote by Hannes Mühleisen , who together with Mark Raasveldt is the brain behind DuckDB. In the keynote, Hannes…
This article is part of the series about scalable unwinding that starts here . Now that we have all infrastructure in place, we look at the high-level algorithms. For inserts, we walk down the tree until we hit the leaf-node that should contain the new value. If that node is full, we split the leaf node, and insert a new separator into the parent node to distinguish the two nodes. To avoid…
This article is part of the series about scalable unwinding that starts here . We use a b-tree because it offers fast lookup, good data locality, and a scalable implementation is reasonable easy when using optimistic lock coupling. Nevertheless a b-tree is a non-trivial data structure. To avoid having one huge article that includes all details of the b-tree, we just discuss the data structure…
This article is part of the series about scalable unwinding that starts here . When thinking about exception handling it is reasonable to assume that we will have far more unwinding requests than changes to the unwinding tables. In our setup, the tables only change when JITed code is added to or removed from the program. That is always expensive to begin with due the mprotect calls, TLB…
This article is part of the series about scalable unwinding that starts here . As discussed in the previous article, the gcc mechanism does not scale because it uses a global lock to protect its list of unwinding frames. To solve that problem, we replace that list with a read-optimized b-tree that allows for concurrent reads and writes. In this article we just discuss the patches to gcc necessary…
Exceptions are a very handy mechanism to propagate errors in C++ programs, but unfortunately they do not scale very well . In all common C++ implementations the unwinding mechanism takes global lock during unwinding, which has disastrous consequences when the number of threads is high. On a machine with 256 hardware context we see worse-than-single-threaded behavior even for relatively modest…
Everyone knows that the major cloud vendors try to make it easy to get data in, and hard to get it out. What is less known is that high egress cost also applies to outbound traffic within the same region. Let's look at AWS specifically. In AWS, EC2 outbound traffic is only free within the same availability zone (AZ). Moving data from one AZ to another in the same region is actually quite…
Many database management systems carefully manage disk I/O operations and explicitly cache pages in main memory. Operating systems implement a page cache to speed up recurring disk accesses as well, and even allow transparent access to disk files through the mmap system call. Why do most database systems then even implement I/O handling and a caching component if the OS provides these features…
Over the past decade, AWS EC2 has introduced many new instance types with different hardware configurations and prices. This hardware zoo can make it hard to keep track of what is available. In this post we will look at how the EC2 hardware landscape changed since 2015. This will hopefully help picking the best option for a given task. In the cloud, one can trade money for hardware resources. It…
Solid-State Drives (SSDs) based on flash have largely replaced magnetic disks as the standard storage medium. From the perspective of a programmer, SSDs and disks look very similar: both are persistent, enable page-based (e.g., 4KB) access through file systems and system calls, and have large capacities. However, there are also important differences, which become important if one wants to achieve…
When operating on hierarchical data structures, it is often convenient to formulate that using pairwise recursive functions. For example, our semantic analysis walks that parse tree recursively and transforms it into an expression tree. This corresponding code looks roughly like this: unique_ptr<Expression> analyzeExpression(AST* astNode) { switch (astNode->getType()) { case AST::BinaryExpression:…
Since C++11, multi-threaded C++ code has been governed by a rigorous memory model. The model allows implementing concurrent code such as low-level synchronization primitives or lock-free data structures in a portable fashion. To use the memory model, programmers need to do two things: First, they have to use the std::atomic type for concurrently-accessed memory locations. Second, each atomic…
Standard compiler are usually used with hand-written programs. These programs tend to have reasonably small functions, and can be processed in (nearly) linear time. Generated programs however can be quite large, and compilers sometimes struggle to compile them at all. This can be seen with the following (silly) demonstration script: import subprocess from timeit import default_timer as timer def…
When picking a hash table size we usually have two choices: Either, we pick a prime number or a power of 2. Powers of 2 are easy to use, as a modulo by a power of 2 is just a bit-wise and, but 1) they waste quite a bit of space, as we have to round up to the next power of 2, and 2) they require "good" hash functions, where looking at just a subset of bits is ok. Prime numbers are more forgiving…
Cuckoo Filters are an interesting alternative to Bloom filters . Instead of maintaining a filter bitmap, they maintain a small (cuckoo-)hash table of key signatures, which has several good properties. For example is stores just the signature of a key instead of the key itself, but is nevertheless able to move an element to a different position in the case of conflicts. This conflict resolution…