Generic database cost models for hierarchical memory systems

Accurate prediction of operator execution time is a prerequisite fordatabase query optimization. Although extensively studied for conventionaldisk-based DBMSs, cost modeling in main-memory DBMSs is still an openissue. Recent database research has demonstrated that memory access ismore and more becoming a significant---if not the major---cost componentof database operations. If used properly, fast but small cachememories---usually organized in cascading hierarchy between CPU and mainmemory---can help to reduce memory access costs. However, they make thecost estimation problem more complex.In this article, we propose a generic technique to create accuratecost functions for database operations. We identify a few basic memoryaccess patterns and provide cost functions that estimate their access costsfor each level of the memory hierarchy. Thecost functions are parameterized to accommodate various hardwarecharacteristics appropriately. Combining the basic patterns, we candescribe the memory access patterns of database operations. Thecost functions of database operations can automatically be derived bycombining the basic patterns' cost functions accordingly.To validate our approach, we performed experiments using our DBMSprototype Monet. The results presented here confirm the accuracy of ourcost models for different operations.Aside from being useful for query optimization, our models provide insightto tune algorithms not only in a main-memory DBMS, but also in adisk-based DBMS with a large main-memory buffer cache.