  We optimize multiway equijoins on relational tables using degree information.
We give a new bound that uses degree information to more tightly bound the
maximum output size of a query. On real data, our bound on the number of
triangles in a social network can be up to $95$ times tighter than existing
worst case bounds. We show that using only a constant amount of degree
information, we are able to obtain join algorithms with a running time that has
a smaller exponent than existing algorithms--{\em for any database instance}.
We also show that this degree information can be obtained in nearly linear
time, which yields asymptotically faster algorithms in the serial setting and
lower communication algorithms in the MapReduce setting.
  In the serial setting, the data complexity of join processing can be
expressed as a function $O(\IN^x + \OUT)$ in terms of input size $\IN$ and
output size $\OUT$ in which $x$ depends on the query. An upper bound for $x$ is
given by fractional hypertreewidth. We are interested in situations in which we
can get algorithms for which $x$ is strictly smaller than the fractional
hypertreewidth. We say that a join can be processed in subquadratic time if $x
< 2$. Building on the AYZ algorithm for processing cycle joins in quadratic
time, for a restricted class of joins which we call $1$-series-parallel graphs,
we obtain a complete decision procedure for identifying subquadratic
solvability (subject to the $3$-SUM problem requiring quadratic time). Our
$3$-SUM based quadratic lower bound is tight, making it the only known tight
bound for joins that does not require any assumption about the matrix
multiplication exponent $\omega$. We also give a MapReduce algorithm that meets
our improved communication bound and handles essentially optimal parallelism.
