  We present an index structure, called the color-index, to boost the
evaluation of acyclic conjunctive queries (ACQs) over binary schemas. The
color-index is based on the color refinement algorithm, a widely used
subroutine for graph isomorphism testing algorithms. Given a database $D$, we
use a suitable version of the color refinement algorithm to produce a stable
coloring of $D$, an assignment from the active domain of $D$ to a set of colors
$C_D$. The main ingredient of the color-index is a particular database $D_c$
whose active domain is $C_D$ and whose size is at most $|D|$. Using the
color-index, we can evaluate any free-connex ACQ $Q$ over $D$ with
preprocessing time $O(|Q| \cdot |D_c|)$ and constant delay enumeration.
Furthermore, we can also count the number of results of $Q$ over $D$ in time
$O(|Q| \cdot |D_c|)$. Given that $|D_c|$ could be much smaller than $|D|$ (even
constant-size for some families of databases), the color-index is the first
index structure for evaluating free-connex ACQs that allows efficient
enumeration and counting with performance that may be strictly smaller than the
database size.
