. This
metric is called relative performance. This page shows some recent research results from the buffer pool simulator. Several buffer pool replacement algorithms have been simulated in a simulator using the TPC-C workload. The 2Q, LRU, Clock, static partitioning, and Random algorithms are studied. For the Clock algorithm, the page cleaners are used to clean dirty pages asynchronously. For the static partitioning algorithm, the clock algorithm with page cleaner is used in each partition. The performance of the dynamic page cleaning algorithm is also showed.
The DBMS employs Fix/Unfix mechanism to manage database pages. Before the DBMS accesses a page (either read or write), it sends a fix to the buffer pool (which is also called a logical read). If the page is already in the buffer pool, a read hit happens; otherwise, a read miss occurs. This read miss then triggers a physical read which brings the page from the disk into the buffer pool. Therefore, the number of read misses equals to the number of physical reads. The percentage of number of physical reads over number of logical reads is called read miss ratio.
After the DBMS finishes using a page, it sends an unfix to the buffer pool. Inside this unfix, it also sets a flag indicating whether the page has been modified during the fixing period. If this page has been changed, this unfixing operation is called a logical write. Moreover, if this page is clean before being fixed but modified during the fixing period, a write miss is said to happen since a physical write will be required to send this page back to the disk. However, if a page has already been changed before being fixed, updating it again will be considered as a write hit since no additional physical write is required to clean this page. Therefore, the number of write misses equals to the number of physical writes. This assertion is invalid for temporary pages since they do not need to be written back to the disk. However, it is sound in an OLTP environment because the simple queries do not generate temporary pages. The percentage of number of physical writes over number of logical writes is called write miss ratio.
A DBMS running OLTP workload generates many random reads and writes to the
disk. It usually is I/O bound. Therefore, the number of physical reads and
physical writes directly related to the performance. If we use Rmiss, Wmiss to
represent the number of read misses and write misses, respectively, the
performance of the system is proportional to
. This
metric is called relative performance.
In the static partitioning algorithm, the buffer pool is partitioned into two partitions, one partition contains the data and index pages of the stock and customer table, one partition contains all other data. The stock and customer tables are put into one partition because they have much higher miss rate than all the other tables. Some simulation experiments were performed to find the optimal static partition size. The following figure shows the relative performance of the static partitioning algorithm with different size of partitoins.
Figure 1 Relative performance of the static partitioning
algorithm with different partition sizes
It shows that the optimal partition percentage is different when the buffer pool size changes. When the buffer pool size is large, the proportion of the size of the partition holding the Stock&Customer data should be larger. Since the large buffer pool is more practical in large scale systems, the optimal proportion of the partition holding the Stock&Customer data is selected as 0.8 to favor large buffer pools. This optimal value is shown as the vertical line in Figure 1.
Figure 2 Read miss ratio
Figure 2 shows the read miss ratio of various algorithms under different buffer pool sizes. It shows that 2Q has the lowest read miss ratio, LRU is the second, and the Clock algorithm with dynamic page cleaning is the third. For the variations of Clock algorithms, the dynamic page cleaning has the lowest read miss ratio. If the number of page cleaners is tuned well, the read miss ratio is close to the dynamic page cleaning algorithm. Otherwise, it may be even worse than the Random algorithm. When good partition sizes are selected, its performance can be close to (but not better than) the clock algorithm with dynamic page cleaning.
Figure 3 Write miss ratio
Figure 3 shows the write miss ratio of different replacement algorithms. The write miss ratio is much higher than the read miss ratio in Figure 2. Since the number of reads is much higher than the number of writes (reads:writes=5.6:1 in TPC-C benchmark), the read miss ratio has a bigger effect on performance . The 2Q algorithm has the lowest write miss ratio. LRU is the second place. The Clock algorithm with dynamic page cleaning has the worst write miss ratio among all the variations of the Clock algorithms, although it has better read miss ratio among all variations of the Clock algorithms. This is because the dynamic cleaning algorithm cleans out pages more aggressively which increases the write misses. For the clock algorithm with 2 page cleaners, dirty pages are not cleaned out quickly, which resulted in many dirty pages in the buffer pool. Therefore, the write miss ratio is lower than the other two Clock variations. The write miss ratio of the static partitioning algorithm is close to the dynamic page cleaning algorithm.
Figure
4 Relative performance
Figure 4 shows the relative performance in terms of
. With
larger buffer pool, the performance of all algorithms increases. Because only
large buffer pool sizes (>4000) are considered, the performance increases
linearly in this range. The order of performance of all algorithms is the same
as the order of the read miss ratio. Therefore, the read miss ratio dominates
performance.
Figure 5 Normalized relative performance
Figure 5 shows the relative performance normalized to the relative performance of the Random algorithm. For large buffer pool sizes, the 2Q algorithm performs about 45% better than the Random algorithm, and the LRU performs 35% better than the Random. The performance of the Clock algorithm with dynamic page cleaning is not very stable, but performs better than the other two Clock variations. The performance of the static partitioning algorithm is higher than the clock algorithms for some buffer pool sizes but is lower for some other buffer pool sizes.
[1] T. Johnson and D. Shasha. 2Q: A low overhead high performance buffer management replacement algorithm. In Proceedings of 20th International Conference on Very Large Data Bases (VLDB’94), pages 439–450, Santiago de Chile, Chile, September 1994.