  We study the fine-grained complexity of conjunctive queries with grouping and
aggregation. For some common aggregate functions (e.g., min, max, count, sum),
such a query can be phrased as an ordinary conjunctive query over a database
annotated with a suitable commutative semiring. Specifically, we investigate
the ability to evaluate such queries by constructing in log-linear time a data
structure that provides logarithmic-time direct access to the answers ordered
by a given lexicographic order. This task is nontrivial since the number of
answers might be larger than log-linear in the size of the input, and so, the
data structure needs to provide a compact representation of the space of
answers.
  In the absence of aggregation and annotation, past research provides a
sufficient tractability condition on queries and orders. For queries without
self-joins, this condition is not just sufficient, but also necessary (under
conventional lower-bound assumptions in fine-grained complexity). We show that
all past results continue to hold for annotated databases, assuming that the
annotation itself is not part of the lexicographic order. On the other hand, we
show infeasibility for the case of count-distinct that does not have any
efficient representation as a commutative semiring. We then investigate the
ability to include the aggregate and annotation outcome in the lexicographic
order. Among the hardness results, standing out as tractable is the case of a
semiring with an idempotent addition, such as those of min and max. Notably,
this case captures also count-distinct over a logarithmic-size domain.
