  Join evaluation is one of the most fundamental operations performed by
database systems and arguably the most well-studied problem in the Database
community. A staggering number of join algorithms have been developed, and
commercial database engines use finely tuned join heuristics that take into
account many factors including the selectivity of predicates, memory, IO, etc.
However, most of the results have catered to either full join queries or
non-full join queries but with degree constraints (such as PK-FK relationships)
that make joins \emph{easier} to evaluate. Further, most of the algorithms are
also not output-sensitive.
  In this paper, we present a novel, output-sensitive algorithm for the
evaluation of acyclic Conjunctive Queries (CQs) that contain arbitrary free
variables. Our result is based on a novel generalization of the Yannakakis
algorithm and shows that it is possible to improve the running time guarantee
of the Yannakakis algorithm by a polynomial factor. Importantly, our
algorithmic improvement does not depend on the use of fast matrix
multiplication, as a recently proposed algorithm does. The upper bound is
complemented with matching lower bounds conditioned on two variants of the
$k$-clique conjecture. The application of our algorithm recovers known prior
results and improves on known state-of-the-art results for common queries such
as paths and stars.
