Scalable Relational Query Processing on Big Matrix Data

A matrix, say $\boldsymbol{\mathrm{A}}$, consists of two dimensional entries, $A_{ij}$. Each entry in a matrix resembles a tuple in a table with schema: matrixA (RID, CID, val), where RID and CID are the row and column dimensions, respectively, and val is the value of the matrix entry. In addition, MatRel  maintains the dimensions of the matrix in the system catalog, i.e., the number of rows and columns. This schema specifies the logical structure of a matrix. However, it does not reflect how the matrix is physically stored. For efficiency and storage considerations, a matrix is divided into “blocks”, i.e., it is partitioned into smaller matrices that can be moved to specific compute nodes for high-performance local computations. Detailed physical storage of matrices is presented in Section 5.1.

Relational select ($\sigma$) selects matrix entries that qualify a certain predicate. We distinguish between selections on the dimensions and selections on the values of a matrix. A relational select is a unary operator of the form: $\sigma_{\theta(RID,CID,val)}(\boldsymbol{\mathrm{A}}),$ where $\theta$ is a propositional formula on the dimensions and entries of Matrix $\boldsymbol{\mathrm{A}}$. An atom in $\theta$ is defined as $u\varphi c$ or $u\varphi v$, where $u,v\in\{RID,CID,val\}$, $u\neq v$, and $c$ is a constant, $\varphi\in\{<,\leq,=,\neq,\geq,>\}$; and the logical expressions among atoms, i.e., $\land$ (and), $\lor$ (or), and $\neg$ (negation) expressions. A relational select on a matrix produces another matrix, perhaps with different dimensions. The dimensions are determined by the predicate, e.g., the predicate $``RID=i"$ produces a matrix of a single row while the predicate $``RID=CID"$ produces the diagonal vector of the matrix.

The select predicate can be composed of conditions on both dimensions and entries. For instance, selecting all the entries whose values equal 10 from the 5-th row is expressed by $\sigma_{val=10\land RID=5}(\boldsymbol{\mathrm{A}})$. Furthermore, in real-world ML applications, an empty column suggests no metrics have been observed for some feature. Removing empty columns will benefit the feature extraction procedure for better efficiency. Thus, we introduce two special predicates, $\sigma_{rows\neq NULL}(\boldsymbol{\mathrm{A}})~{}\text{and}~{}\sigma_{cols\neq NULL}(\boldsymbol{\mathrm{A}}).$ The former excludes the rows that are all NULLs, and the latter excludes the columns that are all NULLs. These are important extensions to the select operator because empty rows/columns usually do not contribute to matrix computations.

Similar rewrite rules apply to matrix-scalar and matrix element-wise operations. The following rules can be viewed as pushing the select below the matrix operations: $\sigma_{RID=i}(\boldsymbol{\mathrm{A}}\star\boldsymbol{\mathrm{B}})=\sigma_{RID=i}(\boldsymbol{\mathrm{A}})\star\sigma_{RID=i}(\boldsymbol{\mathrm{B}})$, where $\star\in\{+,*,/\}$. This rule also applies to matrix-scalar multiplications. We illustrate these transformation rules on the selects w.r.t. the row dimension. The rules apply to selections on the column dimension as well. The number of required operations drops from $O(n^{2})$ to $O(n)$ by circumventing the intermediate matrix. For matrix-matrix multiplications, we have $\sigma_{RID=i}(\boldsymbol{\mathrm{A}}\times\boldsymbol{\mathrm{B}})=\sigma_{RID=i}(\boldsymbol{\mathrm{A}})\times\boldsymbol{\mathrm{B}}$.

Analogously, the Rule: $\sigma_{CID=j}(\boldsymbol{\mathrm{A}}\times\boldsymbol{\mathrm{B}})=\boldsymbol{\mathrm{A}}\times\sigma_{CID=j}(\boldsymbol{\mathrm{B}})$ can be verified. It takes $O(n^{3})$ operations for matrix-matrix multiplications, while a matrix-vector multiplication costs $O(n^{2})$ operations. Furthermore, the rule: $\sigma_{RID=i\land CID=j}(\boldsymbol{\mathrm{A}}\times\boldsymbol{\mathrm{B}})=\sigma_{RID=i}(\boldsymbol{\mathrm{A}})\times\sigma_{CID=j}(\boldsymbol{\mathrm{B}})$ reduces the complexity from $O(n^{3})$ (matrix-matrix multiplication) to $O(n)$ (vector inner-product).

Traditionally, an aggregation is defined on the columns of a relation with various aggregate functions, e.g., sum and count. The aggregation operator is also beneficial on matrix data. For example, assume that for a user-movie rating database, each row in the matrix represents a user, and each column represents a certain movie. Then, computing the average ratings of all the users can take place in the following way. The $(i,j)$-th entry in the user-movie rating matrix denotes the rating of $user_{i}$ on $movie_{j}$. This requires an average computation on the row dimension. Unlike relational data, aggregations on a matrix may occur in different dimensions. Formally, an aggregation is a unary operator, defined as

where $\rho$ is the name of the aggregate function, and $dim$ indicates the chosen dimension, i.e., $dim$ could be row (r), column (c), diagonal (d), or all (a). Specially, MatRel supports various aggregate functions, $\rho\in\{\texttt{sum},\texttt{nnz}$, $\texttt{avg},\texttt{max},\texttt{min}\}$. We introduce each aggregate function and corresponding optimizations in this section.

We present transformation rules for optimizing sum aggregations when the input consists of various matrix operations. If the input is a matrix transpose, then we have:

By pushing a sum aggregation before a matrix transpose, MatRel computes the transpose on a matrix of smaller dimensions. For trace and all-entry summation, the evaluation of the transpose can be avoided.

For matrix-scalar operations, we can derive the following transformation rules,

where we denote $\boldsymbol{\mathrm{e}}_{n}$ to be an all-one column vector of length $n$ and Rule 5 only holds for square matrices, i.e., $m=n$. For matrix-scalar multiplications, similar rules apply when the aggregation is executed along the column direction, the diagonal direction, and the entire matrix.

For matrix element-wise operations, only the matrix element-wise addition has a compatible transformation rule for sum aggregations.

Though Rule 7 does not change the computation overhead, it circumvents storing the intermediate sum matrix $\boldsymbol{\mathrm{A}}+\boldsymbol{\mathrm{B}}$, alleviating memory footprint.

For matrix-matrix multiplications, we derive efficient transformation rules to compute the sum aggregations,

Similar derivations also apply to Rules 9 and 10. For Rule 11, both input matrices are required to be square.

The computation complexity is usually $O(n^{3})$ for square matrix-matrix multiplications. By using matrix element-wise multiplication and matrix transpose, the complexity is reduced to $O(n^{2})$.

Unfortunately, equivalent transformation rules do not apply when the input involves a relational selection. For general selection condition $\theta$,

However, there exist valid transformation rules if the sum dimension happens to match with the predicate of the selection, e.g., $\Gamma_{\texttt{sum},r}(\sigma_{RID=i}(\boldsymbol{\mathrm{A}}))=\sigma_{RID=i}(\Gamma_{\texttt{sum},r}(\boldsymbol{\mathrm{A}}))$. Swapping the execution order of sum aggregation leads to the same result. Pushing a select relational operation below a matrix operation is beneficial as it could reduce the dimension of the matrix.

We present equivalent transformation rules for optimizing count aggregations when the input is composed of various matrix operations. For matrix transpose, we have:

These rules push a count aggregation below a matrix transpose. The postponed matrix transpose is executed on a smaller matrix, e.g., a vector, avoiding $O(n^{2})$ computations for the matrix transpose.

For matrix-scalar operations, let $\boldsymbol{\mathrm{A}}$ be an $m$-by-$n$ matrix, and scalar $\beta\neq 0$. The following rules hold for an input that involves matrix-scalar operations,

By assuming the constant $\beta\neq 0$, the number of zeros is not altered for matrix-scalar multiplications. For the matrix-scalar addition, the output does not depend on the entries in $\boldsymbol{\mathrm{A}}$, which only requires the dimensions to conduct the computation.

For matrix element-wise operations, only the division operator works properly with the count aggregation.

Rule 20 indicates that the matrix element-wise division preserves the number of nonzeros of the numerator matrix. Unfortunately, such convenient transformation rules do not apply to other matrix element-wise operators and matrix-matrix multiplications.

For an input consisting of relational selections, Rule 12 can be extended too. It is impossible to swap the execution order of a count aggregation and a selection for a correct output. It is only valid to swap the execution order of a count aggregation and a selection when both work on the same dimension, e.g., $\Gamma_{\texttt{nnz},c}(\sigma_{CID=j}(\boldsymbol{\mathrm{A}}))=\sigma_{CID=j}(\Gamma_{\texttt{nnz},c}(\boldsymbol{\mathrm{A}}))$.

Just like every matrix has a schema, MatRel automatically produces a schema for a join result. The schema of a join result consists of two parts: the index and the value. In this work, we only consider equality predicates as the join condition. Given two input matrices $A(RID_{A},CID_{A},val_{A})$ and $B(RID_{B},CID_{B},val_{B})$, the cardinality of the dimension of $\boldsymbol{\mathrm{A}}\Join_{\gamma,f}\boldsymbol{\mathrm{B}}$ is

where $\delta_{dim}$ is the number of equality predicates on the join dimensions. For example, if the join predicates $\gamma=``RID_{A}=RID_{B}"$, the join output boasts the schema $(D_{1},D_{2},D_{3},val)$, where $D_{1}$ takes matching dimension from $RID_{A}$, $D_{2}$ takes relevant dimension from $CID_{A}$, $D_{3}$ takes relevant dimension from $CID_{B}$, and $val$ is the evaluation of the merge function on the matching entries from $\boldsymbol{\mathrm{A}}$ and $\boldsymbol{\mathrm{B}}$. The join output may degrade to a normal matrix when $\gamma$ contains two or more predicates on the join dimensions.

The cross-product operator is a special join operator between two matrices, where the join predicate $\gamma$ is empty, i.e., $\boldsymbol{\mathrm{A}}\otimes\boldsymbol{\mathrm{B}}=\boldsymbol{\mathrm{A}}\Join_{f}\boldsymbol{\mathrm{B}}$. If both input matrices are viewed as relations, this operator is essentially the Cartesian product. The cross-product is widely used in tensor decomposition and applications, e.g., Kronecker product (Kolda and Bader, 2009). MatRel’s optimizer infers the output schema from the join predicate, which is empty for cross-product. Therefore, a cross-product produces a 4th-order tensor from two input matrices. For example, $C(D_{1},D_{2},D_{3},D_{4},val)$ is the schema of $\boldsymbol{\mathcal{C}}=\boldsymbol{\mathrm{A}}\otimes\boldsymbol{\mathrm{B}}$. The first two dimensions $(D_{1},D_{2})$ inherit from $\boldsymbol{\mathrm{A}}$, and the last two dimensions $(D_{3},D_{4})$ inherit from $\boldsymbol{\mathrm{B}}$.

The execution of a cross-product is conducted in a fully parallel manner. MatRel stores a matrix in blocks of equal size, where the blocks are distributed among all the workers in a cluster. First, each block of the smaller matrix is duplicated $p$ times, where $p$ is the number of partitions from the larger matrix. Next, each duplicated block is sent to a corresponding partition of the larger matrix. Finally, each worker performs join operation locally without further communication. The 4th-order tensor is stored as a series of block matrices in a distributed manner. The detailed physical storage is described in Section 5.1.

The dimension-based predicates for join on two dimensions can take two different formats:

These two predicates are the only valid formats, as a propositional formula takes dimensions from both inputs. The former predicate can be viewed as an overlay on the two input matrices directly (direct overlay), while the latter can be viewed as an overlay on Matrix $\boldsymbol{\mathrm{A}}$ and the transpose of Matrix $\boldsymbol{\mathrm{B}}$ (transpose overlay). Figure 4 illustrates an example of a direct overlay, which can be viewed as a full-outer join in relational algebra. Conceptually, two input matrices can be regarded as two relations with the schema introduced in Section 3.1. The output of a join on two dimensions is a normal matrix, since two common dimensions are shared with the inputs.

To efficiently evaluate joins on two dimensions, MatRel adopts the hash join strategy to partition the matrix blocks from the inputs. By hashing the matched matrix blocks to the same worker, a worker conducts local join execution without further communications. For direct overlay, MatRel’s query planner partitions the two input matrices using the same partitioner. For transpose overlay, the planner makes sure the partitioning scheme on one input matches the partitioning scheme on the transpose of the other.

The dimension-to-dimension (D2D) predicates can take four different formats:

where $ID_{A/B}\in\{RID_{A/B},CID_{A/B}\}$. Therefore, the join output is a 3rd-order tensor, and takes the schema $(D_{1},D_{2},D_{3},val)$. Each entry from a matched row/column from $\boldsymbol{\mathrm{A}}$ is joined with the entries from the corresponding row/column from $\boldsymbol{\mathrm{B}}$.

MatRel leverages a hash-based data partitioner to map matched row or column matrix blocks to the same worker. Suppose both input matrices are partitioned into $\ell$-by-$\ell$ square blocks. Let us consider the D2D predicate to be $``RID_{A}=RID_{B}"$. Two matrix blocks $\boldsymbol{\mathrm{A}}_{mp}$ and $\boldsymbol{\mathrm{B}}_{mq}$ are mapped to the same worker. For the $t$-th row from $\boldsymbol{\mathrm{A}}_{mp}$, each entry is joined with the same row from $\boldsymbol{\mathrm{B}}_{mq}$. Thus, a $1$-by-$\ell$ vector is produced by joining a single entry in the $t$-th row from $\boldsymbol{\mathrm{A}}_{mp}$ and an entire row from $\boldsymbol{\mathrm{B}}_{mq}$. After the join operation, the $t$-th row from $\boldsymbol{\mathrm{A}}_{mp}$ leads to an $\ell$-by-$\ell$ matrix block. Potentially, there are totally $\ell$ such matrix blocks for the join result from two input matrix blocks.

The entry-based (value-to-value, or V2V) join operation takes the following format:

The join output is a 4th-order tensor, where the first two dimensions come from the dimensions of $\boldsymbol{\mathrm{A}}$, and the other two from the dimensions of $\boldsymbol{\mathrm{B}}$.

The execution of a V2V join is conducted in a fully parallel manner, similar to the execution of cross-product. MatRel broadcasts each block of the smaller input to each partition of the larger one. Each worker in the cluster adopts a nested-loop join strategy to compute the join locally by taking each pair of matrix blocks. The four dimensions are copies of the dimension values from matched entries.

The join on a single dimension and an entry operation (D2V, or V2D) takes the following format:

where $ID_{A/B}\in\{RID_{A/B},CID_{A/B}\}$. The output is a 4th-order tensor, where the 4 dimensions derive from the entry locations of the matched rows/columns, and the matched entries from the other input. To evaluate this type of join, the matrix blocks containing the matched entries are mapped to the other matrix, where the row/column dimension matches. Each worker conducts local join computation based on the matched dimensions and entries.

Relational joins over matrix data are more complex than other relational operations. They potentially have higher computation and communication overhead. We have identified several heuristics to mitigate the heavy memory footprint and computation burden. We leverage the following features: (1) sparsity-inducing merge functions, and (2) Bloom-join for join on entries. Furthermore, we also develop a cost model to capture the communication overhead among different types of joins. By utilizing the heuristics and the cost model, MatRel generates a computation- and communication-efficient execution plan for a join operation.

Identifying Sparsity-inducing Merge Functions. Given a general join operation, $\boldsymbol{\mathrm{A}}\Join_{\gamma,f}\boldsymbol{\mathrm{B}}$, there are two important parameters, $\gamma$ and $f$. The predicate $\gamma$ is utilized to locate the join entries, and $f$ is evaluated on the two entries for an output entry. In real-world applications, large matrices are usually sparse and structured¹¹1http://www.cise.ufl.edu/research/sparse. For example, Figure 4 illustrates a direct overlay on two sparse matrices, where the merge function is $f(x,y)=x+y$. We say $f(x,y)$ is a sparsity-inducing function if $f(0,\cdot)=0$ or $f(\cdot,0)=0$. Thus, the summation merge function is not sparsity-inducing since $C_{00}=A_{00}+B_{00}=0+2=2$, which does not preserve sparsity from the left- or right-hand side. On the other hand, $f_{1}(x,y)=x*y$, is sparsity-inducing on both sides.

The benefit of utilizing sparsity-inducing function is obvious, as it avoids evaluating the function completely if one of the inputs contains all zeros. Traditionally, a straw man execution plan takes two input matrix blocks. It at first converts the sparse matrix formats to the dense counterpart by explicitly filling in 0’s, then evaluates the merge function on the matched entries. Note that a sparse matrix format only records nonzeros and their locations. Compressed sparse representations reduce memory consumption and computation overhead for matrix manipulations. However, the memory consumption grows significantly when a sparse matrix is stored in the dense format.

Thus, it is critical to identify the sparsity-inducing merge functions, and avoid converting a sparse matrix format to dense format whenever possible. We consider a special family of merge functions: linear function and their linear combinations, i.e., $f(x,y)=g(x)*y+h(x)$, or $f(x,y)=g(y)*x+h(y)$, where both $g(\cdot)$ and $h(\cdot)$ are linear functions. For any merge function in this family, MatRel adopts a sampling approach to identify the sparsity-inducing property. Given a merge function $f(x,y)$, we compute $t_{1}=f(0,s_{1})$, and $t_{2}=f(0,s_{2})$, where $s_{1}$ and $s_{2}$ are non-zero random numbers. If both $t_{1}$ and $t_{2}$ are 0, it can be easily confirmed that both $g(0)$ and $h(0)$ equal to 0. Thus, $f(x,y)$ is sparsity-inducing because of the linearity of function components. A similar sparsity-inducing test could be conducted on the $y$ value.

Once a sparsity-inducing function is identified, MatRel’s planner orchestrates the execution of join operations by leveraging the sparse matrix computations. For example, if the merge function $f(x,y)$ boasts the sparsity-inducing property on the $x$ component, MatRel only retrieves the nonzero entries from the left-hand side, and joins with entries from the right-hand side. All the computations are conducted in the sparse matrix format without converting to dense matrix format.

Bloom-join on Entries. For a join predicate that involves a dimension on the matrix, it is efficient for MatRel to locate the corresponding row matrix blocks or column matrix blocks. The irrelevant matrix blocks are not accessed during evaluation. However, the join operation becomes expensive when the join predicate contains a comparison on the entries. A straw man plan compares each pair of entries exhaustively, where a lot of computation is wasted on the mismatched entries.

MatRel adopts a Bloom-join strategy when a join predicate contains matrix entries. Each worker computes a Bloom filter on the entries. Due to the existence of sparse matrices, a worker needs to determine whether to store 0’s in the Bloom filter. Thanks to the heuristic of identifying zero-preserving merge functions, 0 values are not inserted into the Bloom filter if $f(x,y)$ is sparsity-inducing. After each matrix block creates its own Bloom filter, a worker picks an entry from one of the input matrix and consults the Bloom filter on the other input. If no match is detected from the Bloom filter, the join execution continues to the next entry; otherwise, a nested-loop join is conducted on the input matrices to generate the join output.

Cost Model for Communications. MatRel extends MatFast’s (Yu et al., 2017) matrix data partitioner, and it naturally supports three matrix data partitioning schemes: Row (“$r$”), Column (“$c$”), and Broadcast (“$b$”). The Broadcast scheme is only used for sharing a matrix of low dimensions, e.g., a single vector. Different matrix data partitioning schemes lead to significantly different communication overhead for join executions. Therefore, we introduce a cost model to evaluate the communication costs of various partitioning schemes for join operations on matrix data.

We design a communication cost model based on the join predicates. For cross-product, we have

where $s_{A}$ and $s_{B}$ are the partitioning scheme of input matrix $\boldsymbol{\mathrm{A}}$ and $\boldsymbol{\mathrm{B}}$, and $N$ is the number of workers in the cluster. $|\boldsymbol{\mathrm{A}}|$ refers to the size of the Matrix $\boldsymbol{\mathrm{A}}$, i.e., $|\boldsymbol{\mathrm{A}}|=mn$ if $\boldsymbol{\mathrm{A}}$ is an $m$-by-$n$ dense matrix; and it means nnz$(\boldsymbol{\mathrm{A}})$ if $\boldsymbol{\mathrm{A}}$ is sparse. The communication cost is 0 if one of the inputs has been broadcast to every worker in the cluster. This only applies to the case when either $\boldsymbol{\mathrm{A}}$ or $\boldsymbol{\mathrm{B}}$ is a matrix of tiny dimensions. When $\boldsymbol{\mathrm{A}}$ and $\boldsymbol{\mathrm{B}}$ are partitioned in Row/Column scheme, each partition of the smaller matrix has to be mapped to every worker. Therefore, it incurs a communication cost of $(N-1)\min\{|\boldsymbol{\mathrm{A}}|,|\boldsymbol{\mathrm{B}}|\}$.

For direct overlay, we have the following cost function,

It is clear that the direct overlay operation induces 0 communication overhead if one of the inputs is broadcast to all the workers in the cluster. Furthermore, there is no communication when both inputs are partitioned using the same scheme. Each worker receives matrix blocks with the same row/column block IDs from both inputs, and the join predicates are naturally satisfied. The communication overhead is only incurred when one of operands is partitioned in Row scheme and the other is in Column scheme. To mitigate this partitioning scheme incompatibility, MatRel repartitions the smaller matrix using the same partitioning scheme from the larger matrix.

For transpose overlay, we have a similar cost function,

The cost model for a transpose overlay is very similar to that of the direct overlay case. The difference is that the communication overhead is introduced when two matrices are partitioned using the same scheme.

Table 1 summarizes the communication costs for joins on a single dimension. If any input matrix is broadcast to all the workers, there is no communication cost. We omit this case in Table 1. Let us focus on the case when $\gamma=``RID_{A}=RID_{B}"$ and $(s_{A},s_{B})=(r,c)$. Figures 5 illustrates that Matrix $\boldsymbol{\mathrm{A}}$ is partitioned in Row scheme and Matrix $\boldsymbol{\mathrm{B}}$ is partitioned in Column scheme. Suppose we have 3 workers in the cluster, i.e., $N=3$. Each square in the matrix is a block partition. The blocks with the same color are stored on the same worker. The join predicate requires that the entries sharing the same $RID$’s are joined together. There are two possible execution strategies based on the partitioning schemes of $\boldsymbol{\mathrm{A}}$ and $\boldsymbol{\mathrm{B}}$. Strategy I sends the blocks with the same $RID$ from $\boldsymbol{\mathrm{A}}$ to the workers which hold the joining blocks from $\boldsymbol{\mathrm{B}}$. For example, Worker $W_{1}$ sends all the blocks to Worker $W_{2}$ and $W_{3}$, since both $W_{2}$ and $W_{3}$ hold some joining blocks from $\boldsymbol{\mathrm{B}}$. Both $W_{2}$ and $W_{3}$ send the blocks in a similar manner. Each worker needs to send the blocks $(N\!-1)$ times to all the other workers. Thus, this strategy induces $(N\!-1)|\boldsymbol{\mathrm{A}}|$ communication cost. Strategy II adopts a different policy by sending different blocks from $\boldsymbol{\mathrm{B}}$ to the same worker that holds the blocks with the same $RID$ from $\boldsymbol{\mathrm{A}}$. For example, the blocks with diagonal lines from $W_{2}$ and $W_{3}$ are sent to $W_{1}$ to satisfy the join predicate. As illustrated in Figure 5, all the blocks with diagonal lines introduce a communication cost of $\frac{N-1}{N}|\boldsymbol{\mathrm{B}}|$. Thus, the best communication cost is $\min\{(N-1)|\boldsymbol{\mathrm{A}}|,\frac{N-1}{N}|\boldsymbol{\mathrm{B}}|\}$ when $\gamma=``RID_{A}=RID_{B}"$ and $(s_{A},s_{B})=(r,c)$. The remaining entries in Table 1 can be computed with similar strategies. Notice, the diagonal of Table 1 contains all 0’s. This is because the partitioning schemes of both matrices happen to match the join predicate.

A join on entries has an identical cost function as a cross-product. It is clear that the join execution incurs 0 communication cost if either $\boldsymbol{\mathrm{A}}$ or $\boldsymbol{\mathrm{B}}$ is partitioned in Broadcast scheme. For any other combination of partitioning schemes of $\boldsymbol{\mathrm{A}}$ and $\boldsymbol{\mathrm{B}}$, a worker needs to broadcast the smaller of the inputs to all the other workers. Hence, the communication cost is $(N-1)\min\{|\boldsymbol{\mathrm{A}}|,|\boldsymbol{\mathrm{B}}|\}$.

For a join on a single dimension and entries, Table 2 gives the communication costs for the various schemes. We use $\eta$ to denote the selectivity of entries that could match the row/column dimensions from the other matrix. Let us examine the cost function for $\gamma=``RID_{A}=val_{B}"$. When $(s_{A},s_{B})=(r,r)$, there exist two strategies to evaluate the join. Strategy I requires each worker to send its own matrix blocks of $\boldsymbol{\mathrm{A}}$ to the other $(N-1)$ workers, since any worker may hold a block from $\boldsymbol{\mathrm{B}}$ that has matched entries with the row dimension. Broadcasting $\boldsymbol{\mathrm{A}}$ incurs a communication cost of $(N-1)|\boldsymbol{\mathrm{A}}|$. Strategy II sends the matched entries from $\boldsymbol{\mathrm{B}}$ to each corresponding worker that holds the blocks of $\boldsymbol{\mathrm{A}}$. The selectivity indicates a total amount of $\eta_{B}|\boldsymbol{\mathrm{B}}|$ of matrix data is transferred. Thus, the communication cost would be $\min\{(N-1)|\boldsymbol{\mathrm{A}}|,\eta_{B}|\boldsymbol{\mathrm{B}}|\}$. For $(s_{A},s_{B})=(c,r)$, the only difference is that the selected matching entries from $\boldsymbol{\mathrm{B}}$ are sent to all the workers in the cluster, since $\boldsymbol{\mathrm{A}}$ is partitioned in Column scheme. The remaining entries in Table 2 can be computed in a similar manner.