  Cost-based query optimization remains a critical task in relational databases
even after decades of research and industrial development. Query optimizers
rely on a large range of statistical synopses -- including attribute-level
histograms and table-level samples -- for accurate cardinality estimation. As
the complexity of selection predicates and the number of join predicates
increase, two problems arise. First, statistics cannot be incrementally
composed to effectively estimate the cost of the sub-plans generated in plan
enumeration. Second, small errors are propagated exponentially through join
operators, which can lead to severely sub-optimal plans. In this paper, we
introduce COMPASS, a novel query optimization paradigm for in-memory databases
based on a single type of statistics -- Fast-AGMS sketches. In COMPASS, query
optimization and execution are intertwined. Selection predicates and sketch
updates are pushed-down and evaluated online during query optimization. This
allows Fast-AGMS sketches to be computed only over the relevant tuples -- which
enhances cardinality estimation accuracy. Plan enumeration is performed over
the query join graph by incrementally composing attribute-level sketches -- not
by building a separate sketch for every sub-plan. We prototype COMPASS in MapD
-- an open-source parallel database -- and perform extensive experiments over
the complete JOB benchmark. The results prove that COMPASS generates better
execution plans -- both in terms of cardinality and runtime -- compared to four
other database systems. Overall, COMPASS achieves a speedup ranging from 1.35X
to 11.28X in cumulative query execution time over the considered competitors.
