W-order scan: Minimizing cache pollution by application software level cache management for MMDB

The utilization of shared LLC(Last Level Cache) is important for efficiency of multi-core processor. Uncontrolled sharing leads to cache pollution i.e. the weak locality data(single-usage data without re-using) continuously evict the strong locality data (frequently re-used data) from LLC in both inner query processing and co-running programs. For analytical MMDB (Main-Memory Database) applications, with skewed star schema of DW, more than 95% memory capacity is occupied by memory-resident fact table with weak locality and there are only small size dimension tables with strong locality. Cache partitioning must manage data with different localities inside query processing to avoid cache pollution by weak locality fact table. The static OS-based cache partitioning suffers from insufficient memory address capacity due to large fact table and the dynamic OS-based cache partitioning also suffers from data movement overhead during cache re-allocation. In order to employ a practical and effective cache partitioning policy, we propose an application software-based W-order scan policy for real analytical MMDB application. The consecutive physical address based W-order policy is proposed to reduce cache misses with high memory utilization by controlling the physical page accessing order within large and consecutive physical pages. Another approach is page-color index i.e. we extract page-color bits from pages of weak locality data and sort the page address by page-color bits, when we perform a page-color index scan, we can control the physical page accessing order too without supporting from OS for large consecutive physical page allocating. We measure the L2 cache miss rate by simulating a typical hash join operation. The experimental results show that DBMSs can improve cache performance through controlling weak locality data accessing pattern by themselves oppose to depending on supports by hardware or OS.