HPCache: memory-efficient OLAP through proportional caching revisited

Improvements in CPU and DRAM efficiency allow analytical engines to place frequently accesseddatasets in-memory [41]—avoiding slow storage accesses¹. However, CPU and DRAM improvement rates have slowed in recent years, while advances in flash storage have enabled increased persistent-storage bandwidth [18, 26, 27, 36]. As a result, storing the working set in memory is no longer always advantageous. For example, when a query is CPU or memory latency bound, it has lower throughput than storage bandwidth, so storing the query’s entire input in memory is wasteful because it is possible to achieve the same execution time with the input located on storage. Instead, it would be more beneficial to use the same memory for another query.

For decades, database designs were based on the assumption that storage IO is the bottleneck in execution times and relied on in-memory caching in the buffer pool to bypass it. There are two lines of work that improve buffer pool performance for analytics: (i) improving the efficiency of accessing buffer pool pages [25, 29] and (ii) improving the probability that frequently used pages remain in memory [11, 12, 22, 31, 34, 35, 38]. In the first line of work, fast access to the buffer pool accelerates storage [3, 25, 29] and reduces the buffer pool overhead but relies on the effectiveness of the buffer pool policy to accelerate query execution. In the second line of work, frequency-based eviction policies improve the cache hit rate. High-bandwidth storage, like multiple NVMes per machine, however, allows for data loading times that are competitive to in-memory query processing (Fig. 1). Thus, improving the hit rate no longer implies faster analytics, and as a result, the available in-memory space is underutilized, slowing down query execution.

In this paper, we propose HPCache, an eviction policy and tuning agent that optimizes the caching efficiency of the buffer pool for analytical workloads on high-bandwidth storage. We show that (i) caching pages that have the same access frequency can yield variable query acceleration results, and (ii) efficient cache use should aim for partial column caching to avoid diminishing returns. HPCache is a buffer management policy that considers both the query frequency and the acceleration impact of any caching decision to derive a memory-efficient caching decision. Toward that end, HPCache (i) examines the query execution to understand caching benefits and (ii) automatically tunes the caching priority and in-memory column space budget based on past execution behavior. We extend the previous version [30] of HPCache to (1) reduce artifacts resulting from looking back a fixed number of queries during decision-making and (2) enable custom policies. Further, we provide a design that allows simple integration of HPCache with an existing analytical engine. We revisit the sensitivity analysis of HPCache using a hardware configuration with sufficiently higher storage bandwidth. Overall, HPCache improves the efficiency of in-memory data caching for analytics, allowing faster query execution for a given memory budget.

In summary, HPCache makes the following contributions:Overall, HPCache enables analytical query processing to efficiently use the available in-memory space when accessing larger-than-memory datasets, allowing faster analytics for the same memory budget, or decreased memory footprint without execution time degradation.

The additional content compared to the earlier publication of this work [30] is mainly discussed in Sects. 4.4, 5, 6, and through new experiments in Sect. 7.

Directly attached NVMe arrays have enough bandwidth to invalidate the general rule of thumb that scanning persistent data is always slower than in-memory execution. The rest of this section shows how high read bandwidth affects the execution speedups achieved by in-memory caching and how frequency-based caching policies result in ineffective eviction decisions. Finally, we quantify the relative value of caching different data.

Fast storage While local storage was once considered slow relative to memory, recent advances in flash technology have resulted in servers having comparable storage read bandwidth and memory bandwidth. Recent NVMes can sustain GB/s of read bandwidth, e.g., an Intel D7-P5600 achieves 7 GB/s. Furthermore, CPUs support 100 s of PCIe 4.0 lanes per socket [15], which allows packing multiple NVMes on the same server to achieve 10 s-100 s GB/s of aggregated read bandwidth—just a single order of magnitude lower than the CPU memory bandwidth.

Quantifying “fast” Still, an order of magnitude more bandwidth is significant. Thus, analytical engines rely on CPU memory for a wide range of operations. In addition to higher read bandwidth, CPU memory also provides better random IO performance and lower latency than NVMe arrays. As a result, CPU memory has been a crucial element in enabling efficient in-memory joins [5, 6, 8] and analytics in general [9]. Thus, for many queries, reading the input data is only a small portion of the memory operations and only dominant for scan-heavy and few-small-join queries [37].

Performing random or latency-sensitive data accesses directly on NVMe-resident data would impose a significant overhead compared to accessing the same data from memory. In contrast, sequentially accessing data from NVMe arrays rather than from memory can have a minimal impact on response times ; especially when random and latency-sensitive accesses or even compute costs dominate the execution time of complex queries. As such, when query complexity increases, and the sequentially accessed input data remains the same, the impact of slower sequential access, e.g., from a slower medium, reduces and can often be overlapped with the rest of the execution. This shrinking of the relative contribution of sequential accesses to the total execution time as query complexity increases, combined with high NVMe storage bandwidth, allows for sequentially scanning data from the NVMe-array storage with a minor penalty—a reverse application of Amdahl’s law. Instead, the caching layer can use the saved space for simpler, sequentially scan-heavy queries.

To quantify the aforementioned query complexity, we define the processing intensity of a query: an indicator for the insensitivity of a query to accessing its inputs from storage rather than from memory. Specifically, we define the processing intensity of a query as the ratio between its in-memory execution time and the time to scan its inputs from memory. For example, with a memory bandwidth of 100 GB/s and 10 GB query input data, a query that executes in 20 s would have a processing intensity of 200. With the same setup, a query that executes in 1 s would have a processing intensity of 10. A processing-intensive query has a relatively high processing intensity and is relatively insensitive to whether its input data are in memory. The converse is a data-intensive query, which has a low processing intensity and is largely bottlenecked by scan throughput.

What is a low or high processing intensity, and consequently, the slowdown of accessing sequential inputs from storage relative to memory is a function of storage bandwidth. Figure 2 models the execution time of increasingly processing-intensive queries normalized to the in-memory execution time. Each of the plotted lines shows the slowdown relative to fully in-memory execution. The sloped component of each line shows the range of processing intensities for which queries are bottlenecked by scanning inputs from the respective media. The ranges where the lines flatten, approaching in-memory query processing speeds, illustrate when the query execution is bottlenecked by in-memory processing and not scans. As storage bandwidth increases, a greater range of queries can run with fully in-memory performance while keeping their inputs entirely in storage. For example, in Fig. 2, with a single HDD, only queries with a processing intensity of over nearly 1000 are not bottlenecked by the throughput of the scan of HDD-resident input data. In contrast, the transition point from scan throughput bound to processing bound is at a processing intensity of just over 32 and 8 for a single NVMe drive and an array of NVMe drives, respectively.

In-memory analytics vs. data loading: a race Contrary to common belief, storage accesses no longer have a catastrophic impact on analytical query response time. We show this concretely using queries from the Star Schema Benchmark (SSB) [32]. Fig. 1 shows the execution time for a data-intensive (SSB Q1.3) and processing-intensive query (SSB Q3.1) as the storage bandwidth increases. Each has the same working set size of 96 GB. The storage bandwidth is controlled by varying the number of drives the data are striped across. Both queries access 96 GB of input data, but the data-intensive query has one cache-resident join while the processing-intensive query has four higher-cardinality joins. With 7 GB/s of storage bandwidth, both queries are bottlenecked by reading data from the NVMe storage. The data-intensive and processing-intensive queries are 41.2x ( ) and 2.8x ( ) slower than in-memory execution, respectively; the processing-intensive query is marginally slower as it first builds the hash tables for its hash joins. However, with 28 GB/s, the processing-intensive query is just 1% slower than in-memory ( ), as the storage bandwidth saturates the query’s processing throughput. Though, the data-intensive query is still 10.9x slower ( ). Faster storage has diminishing returns for extremely data-intensive queries, as both query processing and data loading compete for the available memory bandwidth. Caching the processing-intensive query’s input data has minimal speedup potential with storage bandwidth in excess of 28 GB/s: the query, either way, spends most of its time processing the joins. In contrast, the data-intensive query will benefit from caching for all storage bandwidths, though the time savings from caching depends on the storage bandwidth. Overall, whether in-memory caching of the input data will reduce query response time or not is query-dependent, even for simple queries.

Memory efficiency of caching While minimizing storage accesses does not harm single-query execution, it leads to inefficient memory use when considering multiple queries. With data loading times comparable to execution times for some queries, caching input data for a query that spends most of its time on non-input operations can result in wasting memory that could be used to accelerate another query. Further, it contradicts the prior wisdom of caching the most frequently accessed data. The most common caching heuristics for analytics involve prioritizing data that has not been used for a long time (LRU [40]), that was recently consumed (MRU [12]), or a combination thereof and second-chance approaches [22]. However, even if Q3.1 of the previous example were executed significantly more frequently than Q1.3, caching its input would provide little benefit: caching reduces storage IO, but as shown above, Q3.1’s execution time will improve very little. In contrast, caching the inputs of Q1.3 will accelerate each execution of Q1.3. Thus, treating all IO savings equally results in suboptimal query response times.

Based on the above observations, we propose Hybrid Proportional Caching (HPCache), a new data placement strategy that makes caching decisions based on the expected query response time reductions. Rather than aiming to reduce storage accesses, HPCache builds on three key principles to efficiently use the in-memory space: (i) not all inputs provide the same query acceleration, (ii) pages should be prioritized based on the expected impact on query execution time, (iii) optimal caching decisions should aim for the sweet spot of matching query execution times with loading the remaining data. The rest of this section outlines the above key principles and their effect on in-memory caching decisions.

Caching different inputs in memory provides different response time gains. Thus, we use the expected benefit (Sect. 4.1) when deciding between alternative caching decisions to use the in-memory space efficiently.

Figure 3 shows the execution time of three analytical queries, from the Star Schema Benchmark (SSB) [32] at scale factor 1000, when using three data placement methods: fully in-memory, fully NVMe resident, and a hybrid configuration with half the input data in-memory and half NVMe resident. Both Q1.1 and Q1.3 are data-intensive queries, and thus, their execution time is nearly halved when moving half of their inputs in memory. However, when moving to fully in-memory, the two queries have different execution times despite their equal input size due to their different processing throughputs; Q1.3 has a higher processing throughput, equivalently a lower processing intensity, and thus benefits more by having all of its inputs in memory. Q3.1 is a processing-intensive query, so it executes in nearly the same amount of time regardless of the location of its inputs. Allocating memory equally to cache the inputs of these three queries would result in a slower speed up than preferentially caching the inputs of the data-intensive queries.

However, per-query caching efficiency is not the only metric that matters when selecting which query inputs to cache: query frequency can also boost or reduce the overall efficiency. In a given workload, if the same or similar queries appear many times, then there is a multiplicative benefit to accelerating the repetitive query by caching its inputs.

To optimize caching efficiency, HPCache combines traditional frequency-based approaches with impact-based query acceleration expectations to achieve the best of both worlds. Specifically, it weights queries and input columns based on their occurrence frequency but calculates the overall expected execution time instead of purely optimizing the number of storage accesses. We model query execution as a flow (Sect. 4.2) to approximate how different data placements would affect the total execution time for a sequence of queries and select the best placement given a memory budget.

Partial input caching. Caching entire columns is wasteful: even in the simplified case of a single query, caching more than a specific fraction of a column provides minimal additional query speedup. Figure 4 shows how the execution time of SSB Q2.2 improves as we increase the percentage of in-memory input data while the rest resides on an NVMe. Initially, the execution is dominated by the data loading time and thus improves linearly as more data is found in the in-memory cache. However, despite using more memory, the query execution time sees almost no reduction after a specific point. From that point up to having fully in-memory inputs, query execution is dominated by the actual processing. Thus, additional caching has no benefit: it would be preferable to use it for another query. HPCache limits the number of pages that are cached for each column to avoid diminishing returns from caching unnecessarily high portions of a specific column. The limit is determined in a per-column base, and it is proportional to the expected impact of caching the corresponding column (Sect. 4.3).

To materialize HPCache, we provide a model that captures per-input caching impact (Sect. 4.1) and use it to provide a memory-efficient caching configuration (Sect. 4.2). Finally, we show how HPCache continuously adapts its caching configuration based on updated estimates and caching configurations (Sect. 4.3).

While in the previous sections, we focused on HPCache’s control logic, HPCache also needs to integrate with a variety of different execution modules. The rest of this section details how HPCache interacts with the buffer cache to maintain the appropriate data proportions and with the execution engine to retrieve the necessary information to drive both the decision-making process as well as the actual data fetching.

We incorporate HPCache in Proteus [13, 23, 33], a pipelined analytical engine that uses LLVM-based code generation.

Proteus uses HetExchange [13] to parallelize query execution by injecting a set of metaoperators. Proteus represents queries as a set of pipelines. Specifically, HetExchange uses the router operator to parallelize execution: each router operator creates multiple instantiations of the pipeline above it and routes inputs to the different instances based on a routing policy. Pipeline instances are affinitized to specific processors, and execution across processors uses multiple pipeline instances. For example, a commonly used routing policy is a prefer-local policy. Under that policy, tasks are assigned to pipeline instances in the same NUMA region as the input data—and only fall back into assigning an input row group to a remote instance when there is skew. Further, routers do not perform any actual data transfers but only route tasks.

The mem-move operators handle data transfers. Such operators are often placed after routers and are responsible for fetching the data to local memory if they are not already there. For example, suppose a router decides, due to skew, to send a row group to a remote pipeline instance and a mem-move follows the router. In that case, the mem-move will transfer the corresponding data pages to the NUMA node local to the pipeline instance. The mem-move is also responsible for overlapping data transfers with the execution that follows it. In that regard, each mem-move operator instance has a consumer and producer side. The producer side accepts page handles, starts an asynchronous data transfer, and registers the transfer into a queue of pending transfers. The consumer side waits on that queue for completed transfers, and when a transfer completes, it removes it from the queue and pushes the corresponding data and task to the next operator. Each mem-move supports having multiple on-the-fly data transfers.

To integrate HPCache in Proteus, we extend the scan, router policies, and mem-move operators. When executing over storage-resident data, the scan operator emits page IDs instead of in-memory block handles. Further, we augmented the routing policies to be able to consider the NVMe location when deciding where to route a row group. Specifically, locality-based routing policies select the target pipeline instance based on the current location of the in-memory input data. For HPCache support, we extended the policies so that 1) if the data are not available in memory, they consider their location as the NUMA node closer to the NVMe holding the corresponding page, 2) if the data is cached in memory, the routing policy uses the location of the in-memory copy as the page’s current NUMA affinity.

Lastly, HPCache plugs into the mem-move operator to implement the NVMe-to-memory data transfers. Specifically, when the producer side of mem-move receives a page ID instead of an in-memory block handle, it will make a request from the buffer cache through the willNeedPage interface. The consumer side will do a getPage to wait for the transfer initiated by willNeedPage to complete. Multiple requests (transfers triggered by willNeedPage) will be on the fly, even from a single operator, which assists with hiding the access latency. If the page was already in the buffer cache, then willNeedPage wouldn’t trigger any storage reads, and getPage would return the page immediately. The rest of the operators are oblivious to the storage layer.

In Proteus, the page ID uniquely identifies the page and encodes the row group ID. Using the page ID, HPCache tracks the per-thread pipeline statistics in a simple thread private data structure through the calls to getPage. All pages within a row group are requested by the same pipeline instance, and each thread executes a single pipeline instance at a time. This data structure stores the time since the first page in the row group was requested, the columns accessed, the sum of times between the first page request for one row group, the first page request for the next, and the total count of requested row groups. As for fixed-width binary columnar data Proteus sizes each data page to be close to an OS huge page (exact size depends on the types in the rowgroup), HPCache has to store the above information once per few MBs of data. When the background thread invokes the optimization problem, it aggregates the per-thread statistics in order to calculate the inputs for the optimization problem. The background thread stores a history of these aggregated statistics at least as long as the look-back window (Sect. 4.3).

In this section, we evaluate HPCache’s ability to efficiently use the available buffer cache, through a series of micro- and macro-experiments.

Experimental setup. Sect. 7.1 demonstrates the impact of varying both cached column proportions and storage bandwidth on query execution times through a set of micro-benchmarks. Further, we evaluate the accuracy and overhead of HPCache’s query execution time predictions as well as compare the exponential and fixed lookback formulations of the optimization problem.

In Sect. 7.2, we compare HPCache with an LRU eviction policy with different cache sizes and storage bandwidths. For workloads that involve many large scans, LRU is comparable to other policies that prioritize caching recently used pages.

Hardware. We use a dual-socket AMD EPYC 7413 server with Ubuntu 20.04 and kernel 5.4.0. Each CPU socket has 12 Corsair MP600 Pro NVMe drives, each using 4 PCIe 4.0 lanes, 256 GB of DRAM, and 24 cores. On each socket, we observe a maximum memory bandwidth of 116 GB/s per socket on the STREAM triad benchmark [27], and 84 GB/s sequential read bandwidth from the corresponding 12 socket-local NVMe drives, using fio [4]. In experiments that vary the storage bandwidth, we vary the number of NVMe drives and stripe the data across the selected drives.

Software. For all IO, we use io_ring with the O_DIRECT flag to bypass the operating system buffer cache. Our buffer cache uses 2 MiB pages to match the 2 MiB hugepages used by Proteus. We use the CVXPY [2, 16] library to solve the optimization problem outlined in Sect. 4.3.

OS-assisted buffer pools. Due to the difficulty of implementing an efficient buffer pool, systems have often abandoned buffer pools altogether and instead relied on the operating system kernel’s paging capabilities, often through mmap; for example, MonetDB relies on memory-mapped IO to support larger than memory datasets [7, 20]. Memory-mapped IO offloads a significant part of the buffer pool implementation to the OS and offers hardware-assisted page-fault handling. However, memory-mapped IO also reduces the control that the database engines have over buffer management and can even result in sufficient contention and reduced prefetching that prevents the database engine from saturating NVMe arrays [14]. Vmcache is a buffer pool design that uses virtual memory but retains DBMS control over page eviction by using anonymous rather than file-backed virtual memory along with the MADV_DONTNEED hint, and addresses OS page table scalability issues through a kernel module [24].

Optimizing buffer pool accesses. Providing persistency and support for out-of-memory data traditionally introduces two overheads with respect to the buffer pool. First, having a centralized buffer pool creates a point of contention [21]. Second, persistency requires a level of indirection when translating in-memory references to out-of-memory object references. Graefe et al. [19] use pointer swizzling to eliminate buffer pool overheads when all data fits in memory. Pointer swizzling dereferences page references and replaces swizzled pointers with in-memory pointers. By avoiding a hashtable, they avoid a costly central point of contention. LeanStore [25] extends on pointer swizzling by speculatively unswizzling pages, which keeps hot pages in memory without explicitly tracking page accesses in shared data structure. Umbra [29] extends LeanStore with support for variable length buffer frames, improving handling of large objects. Overall, optimizing buffer pool accesses reduces the overhead imposed on mostly in-memory analytics while adding support for out-of-memory data. In contrast, HPCache improves the cache efficiency with respect to the performance gains achieved by caching data in memory.

Buffer pool eviction policies. Apart from handling larger-than-memory datasets, traditionally, buffer pools promise efficient in-memory data caching. Multiple eviction policies have been proposed to increase the cache hit frequency, using the databases’ access patterns, such as partitioning the buffer pool by relation [38], or into priority or access patterns zones and using an access pattern-optimized eviction policy inside each partition [31, 34]. Partitions are sized based on the expected performance benefit. Other approaches provide each query with a buffer large enough for the queries modeled hotset of pages [35]. LRU and MRU are used to increase the hit chance inside each partition, with second-chance eviction policies like 2Q reducing the cache pollution [22]. However, directly attached NVMe arrays provide significant bandwidth to make data scans competitive to query execution times. Instead of relying on frequency-based cache eviction, HPCache takes into consideration the overall benefit of data caching and prioritizes caching of high-benefit data over frequently loaded but low-benefit inputs.

Heterogeneous storage. The multitude of available storage devices provides a rich spectrum of performance and budget tradeoffs. Do et al. [17] reduce the computational cost of log-structured storage by offloading the computation required for garbage collection and recovery onto computational SSDs. Mosaic [39] is a storage engine specialized for scan-heavy workloads. It calculates performance-budget Pareto-optimal data placements for data residing across multiple types of storage devices. Mosaic uses workload traces to model column-granular data placement as an optimization problem and solves it offline using linear optimization. Borovica et al. [10] propose Skipper, an execution framework optimized for cold storage devices (CSD): as CSD can result in high delays when accessing data from powered-off disks, Skipper uses out-of-order execution to codesign the execution order and disk requests to hide unnecessary latencies. Both Skipper and Mosaic optimize the performance and cost of analytics on scan-heavy workloads, assuming the storage medium is the bottleneck. In contrast, in this work, we focus on improving analytical response times over high-bandwidth, directly attached NVMes.

In this paper, we show that (i) caching pages that are accessed with the same frequency can yield significantly different query acceleration results, and (ii) optimizing the memory footprint requires partial column caching to avoid diminishing returns. We proposed HPCache, an eviction policy and tuning agent that optimizes the caching decisions of the buffer pool for analytical workloads on high-bandwidth storage. HPCache both inspects query execution to predict caching benefits and automatically tunes page caching priority. HPCache improves the efficiency of in-memory data caching for analytics, allowing faster query execution time and improved NVMe bandwidth utilization for a given memory budget. HPCache achieves up to a 1.75x speed up compared to an LRU eviction policy.