Testing cardinality estimation models in SQL server

Reliable query optimization greatly depends on accurate Cardinality Estimation (CE), which is inherently inexact as it relies on statistical information. In commercial database systems, cardinality estimation models are sophisticated components that over years of development can become very complex. The code that implements cardinality estimation models, like most complex software systems that handle a large space of possible inputs and conditions, can deviate from its original architecture and design points over time. Hence, it is often necessary to refactor and redesign the entire system to accommodate new inputs and conditions, and also to reflect existing ones in a more intentional way. In this paper, we describe such an exercise: the replacement and validation of a new cardinality estimation model in Microsoft SQL Server. We describe the motivation behind this change, and provide a high level sketch of the empirical methods used to ensure that the new cardinality estimation model satisfies its goals while minimizing the potential risk of plan regressions for existing customers.