1

Cardinality estimation plays an important role in generating query plans. In this paper, we study a framework called cardinality estimation graphs (CEGs) that allows us to connect two disparate lines of work on optimistic and pessimistic estimators, adopt an optimization from pessimistic estimators to optimistic ones, and provide insights into the pessimistic estimators, such as showing that there are alternative combinatorial solutions to the linear programs that define them.