  In the last few years, much effort has been devoted to developing join
algorithms in order to achieve worst-case optimality for join queries over
relational databases. Towards this end, the database community has had
considerable success in developing succinct algorithms that achieve worst-case
optimal runtime for full join queries, i.e the join is over all variables
present in the input database. However, not much is known about join evaluation
with {\em projections} beyond some simple techniques of pushing down the
projection operator in the query execution plan. Such queries have a large
number of applications in entity matching, graph analytics and searching over
compressed graphs. In this paper, we study how a class of join queries with
projections can be evaluated faster using worst-case optimal algorithms
together with matrix multiplication. Crucially, our algorithms are
parameterized by the output size of the final result, allowing for choice of
the best execution strategy. We implement our algorithms as a subroutine and
compare the performance with state-of-the-art techniques to show they can be
improved upon by as much as 50x. More importantly, our experiments indicate
that matrix multiplication is a useful operation that can help speed up join
processing owing to highly optimized open source libraries that are also highly
parallelizable.
