  We consider the problem of sampling and approximately counting an arbitrary
given motif $H$ in a graph $G$, where access to $G$ is given via queries:
degree, neighbor, and pair, as well as uniform edge sample queries. Previous
algorithms for these tasks were based on a decomposition of $H$ into a
collection of odd cycles and stars, denoted $\mathcal{D}^*(H)=\{O_{k_1},
\ldots, O_{k_q}, S_{p_1}, \ldots, S_{p_\ell}\}$. These algorithms were shown to
be optimal for the case where $H$ is a clique or an odd-length cycle, but no
other lower bounds were known.
  We present a new algorithm for sampling and approximately counting arbitrary
motifs which, up to $\textrm{poly}(\log n)$ factors, is always at least as good
as previous results, and for most graphs $G$ is strictly better. The main
ingredient leading to this improvement is an improved uniform algorithm for
sampling stars, which might be of independent interest, as it allows to sample
vertices according to the $p$-th moment of the degree distribution.
  Finally, we prove that this algorithm is \emph{decomposition-optimal} for
decompositions that contain at least one odd cycle. These are the first lower
bounds for motifs $H$ with a nontrivial decomposition, i.e., motifs that have
more than a single component in their decomposition.
