  Sketching is a powerful dimensionality reduction technique for accelerating
algorithms for data analysis. A crucial step in sketching methods is to compute
a subspace embedding (SE) for a large matrix $\mathbf{A} \in \mathbb{R}^{N
\times d}$. SE's are the primary tool for obtaining extremely efficient
solutions for many linear-algebraic tasks, such as least squares regression and
low rank approximation. Computing an SE often requires an explicit
representation of $\mathbf{A}$ and running time proportional to the size of
$\mathbf{A}$. However, if $\mathbf{A}= \mathbf{T}_1 \Join \mathbf{T}_2 \Join
\dots \Join \mathbf{T}_m$ is the result of a database join query on several
smaller tables $\mathbf{T}_i \in \mathbb{R}^{n_i \times d_i}$, then this
running time can be prohibitive, as $\mathbf{A}$ itself can have as many as
$O(n_1 n_2 \cdots n_m)$ rows.
  In this work, we design subspace embeddings for database joins which can be
computed significantly faster than computing the join. For the case of a two
table join $\mathbf{A} = \mathbf{T}_1 \Join \mathbf{T}_2$ we give
input-sparsity algorithms for computing subspace embeddings, with running time
bounded by the number of non-zero entries in $\mathbf{T}_1,\mathbf{T}_2$. This
results in input-sparsity time algorithms for high accuracy regression,
significantly improving upon the running time of prior FAQ-based methods for
regression. We extend our results to arbitrary joins for the ridge regression
problem, also considerably improving the running time of prior methods.
Empirically, we apply our method to real datasets and show that it is
significantly faster than existing algorithms.
