Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?
In the clash between access methods, many factors must be considered to make the optimal decision.

FastColumns and
Modern Access Path Selection

In this project we study access path selection in modern main-memory optimized data systems. Specifically, we study how to choose between scan and secondary index scan given recent advances in system design and an OLAP workload. With optimizations like columnar or column-group storage, vectorized execution, shared scans, working directly over compressed data, and operating using SIMD/multi-core execution and large main memories, modern scans put increasing pressure on index scans to the point where many systems opt not to use secondary indexes and rely only on a single access path.

We have developed a detailed model that captures the behavior of these modern access paths. While scans have indeed become useful in more cases than before, there is still a strong case for index scans and access path selection. Contrary to the way traditional systems choose between scans and secondary indexes, we find that in addition to selectivity modern optimizers need to also take into account (1) query concurrency and (2) the underlying machine hardware configuration. Effectively, there is no fixed selectivity threshold; rather, there is a moving sweet spot that depends on the number of concurrent queries and their aggregate selectivity. We can also use the model to explain how the sweet spot between scan and secondary index has evolved through the past decades which allows for future projections based on hardware advancements.

FastColumns is the system that we have developed that includes a cost based optimizer (based on our models) for effective access path selection. FastColumns automatically detects the properties of the underlying hardware and it continuously monitors the level of concurrency and selectivity of in-flight queries to decide between a fast shared scan and a tuned shared index scan. FastColumns can quickly perform access path selection outperforming solutions that rely on a single access path or simpler access path models.

Making Indexes More Usable


Making the decision between access pathes requires an understanding of the cost components involved. There are a wide range of workloads for which scanning the whole relation is the fastest way to retrieve base data. There is also a strong use case for the use of indexes. A secondary index on a column is a copy of the data with additional structure that can be used to avoid reading unnecessary data. Intuitively, the more an index can be optimized, the more it will become the correct access path choice.

Cost Components of B+-tree Indexes

Indexes have at least three cost components: traversing the tree to the leaves; traversing the leaves themselves; and recording the results of the scan. Traversing the tree to get to the leaves has a cost that is governed by the fanout of the tree and the log of the number of items in the relation. Traversing the leaves is related to the number of items in the leaf and the selectivity of the query. Finally, the icost of recording of qualifying tuples is based on the selectivity of the workload and the style of the result set being written (a bitvector has a differnt cost profile than an array of qualifying positions).

Methods to Improve Index Structures

The key to improving the performance of indexes, and thereby increasing the number of cases that they can be used with benefit, is in improving the performance of indexes based on the underlying hardware or the system, the selectivity of the workload and its concurrency. This project is developing methods to take advantage of advancements in hardware and the high level of concurrency in modern workloads. We use a universal result set to record any number of queries on a given index. We also optimize tree descent using multi-predicate evaluation which hides memory latency by performing intra-node search while prefetching the needed nodes from the next level of the tree.