  The classic Yannakakis framework proposed in 1981 is still the
state-of-the-art approach for tackling acyclic join-aggregate queries defined
over commutative semi-rings. It has been shown that the time complexity of the
Yannakakis framework is $O(N + \OUT)$ for any free-connex join-aggregate query,
where $N$ is the input size of database and $\OUT$ is the output size of the
query result. This is already output-optimal. However, only a general upper
bound $O(N \cdot \OUT)$ on the time complexity of the Yannakakis framework is
known for the remaining class of acyclic but non-free-connex queries.
  We first show a lower bound $\Omega\left(N \cdot \OUT^{1- \frac{1}{\outw}} +
\OUT\right)$ for computing an acyclic join-aggregate query by {\em semi-ring
algorithms}, where $\outw$ is identified as the {\em out-width} of the input
query, $N$ is the input size of the database, and $\OUT$ is the output size of
the query result. For example, $\outw =2$ for the chain matrix multiplication
query, and $\outw=k$ for the star matrix multiplication query with $k$
relations. We give a tighter analysis of the Yannakakis framework and show that
Yannakakis framework is already output-optimal on the class of {\em
aggregate-hierarchical} queries. However, for the large remaining class of
non-aggregate-hierarchical queries, such as chain matrix multiplication query,
Yannakakis framework indeed requires $\Theta(N \cdot \OUT)$ time. We next
explore a hybrid version of the Yannakakis framework and present an
output-optimal algorithm for computing any general acyclic join-aggregate query
within $\O\left(N\cdot \OUT^{1-\frac{1}{\outw}} + \OUT\right)$ time, matching
the out-width-dependent lower bound up to a poly-logarithmic factor. To the
best of our knowledge, this is the first polynomial improvement for computing
acyclic join-aggregate queries since 1981.
