Machine Learning Part 6 — Matrix multiplication in SQL

This is the sixth part of the ML series. For your convenience you can find other parts in the table of contents in Part 1 – Linear regression in MXNet

Today we are going to implement a matrix multiplication in Redshift. Let’s go.

First, let’s see what we want to calculate:

$\begin{gather*} \left[\begin{array}{cc}2&3\\4&5\end{array}\right] \left[\begin{array}{cc}5&3\\2&4\end{array}\right] = \left[\begin{array}{cc}16&18\\30&32\end{array}\right] \end{gather*}$

Nothing fancy. We would like our algorithm to be extensible to any sizes and non-uniform matrices as well.

Let’s start with matrix representation:

DROP TABLE IF EXISTS matrix1;

CREATE TEMP TABLE matrix1 (
  rowNumber INT,
  columnNumber INT,
  value INT
);

DROP TABLE IF EXISTS matrix2;

CREATE TEMP TABLE matrix2 (
  rowNumber INT,
  columnNumber INT,
  value INT
);

INSERT INTO matrix1 VALUES
   (1, 1, 2)
  ,(1, 2, 3)
  ,(2, 1, 4)
  ,(2, 2, 5)
;

INSERT INTO matrix2 VALUES
   (1, 1, 5)
  ,(1, 2, 3)
  ,(2, 1, 2)
  ,(2, 2, 4)
;

DROP TABLE IF EXISTS matrix1;

CREATE TEMP TABLE matrix1 (

rowNumber INT,

columnNumber INT,

value INT

);

DROP TABLE IF EXISTS matrix2;

CREATE TEMP TABLE matrix2 (

rowNumber INT,

columnNumber INT,

value INT

);

INSERT INTO matrix1 VALUES

(1, 1, 2)

,(1, 2, 3)

,(2, 1, 4)

,(2, 2, 5)

;

INSERT INTO matrix2 VALUES

(1, 1, 5)

,(1, 2, 3)

,(2, 1, 2)

,(2, 2, 4)

;

We store the matrices as a rows where each row represents one value for given row and column. Rows and columns are one-based.

First, we need to calculate size of the result:

WITH maxWidth AS(
  SELECT MAX(columnNumber) AS width FROM matrix2
),
maxHeight AS (
  SELECT MAX(rowNumber) AS height FROM matrix1
),
resultDimensions AS (
  SELECT width, height FROM maxWidth CROSS JOIN maxHeight
),

WITH maxWidth AS(

SELECT MAX(columnNumber) AS width FROM matrix2

maxHeight AS (

SELECT MAX(rowNumber) AS height FROM matrix1

resultDimensions AS (

SELECT width, height FROM maxWidth CROSS JOIN maxHeight

So we just get the maximum width and maximum height from the respective matrices. Now, we want to generate all the cells we need to fill:

rowNums AS (
  SELECT (row_number() OVER (ORDER BY 1)) AS rowNumber FROM matrix1 WHERE rowNumber <= (SELECT MAX(height) FROM resultDimensions)
),
columnNums AS (
  SELECT (row_number() OVER (ORDER BY 1)) AS columnNumber FROM matrix2 WHERE columnNumber <= (SELECT width FROM resultDimensions)
),
positions AS (
  SELECT rowNumber, columnNumber FROM rowNums CROSS JOIN columnNums
),

rowNums AS (

SELECT (row_number() OVER (ORDER BY 1)) AS rowNumber FROM matrix1 WHERE rowNumber <= (SELECT MAX(height) FROM resultDimensions)

columnNums AS (

SELECT (row_number() OVER (ORDER BY 1)) AS columnNumber FROM matrix2 WHERE columnNumber <= (SELECT width FROM resultDimensions)

positions AS (

SELECT rowNumber, columnNumber FROM rowNums CROSS JOIN columnNums

So we basically do the Cartesian product and we are done. Now, we would like to get correct pairs for each cell:

pairsForPositions AS (
  SELECT P.rowNumber, P.columnNumber, M1.value AS M1, M2.value AS M2
  FROM positions AS P
  JOIN matrix1 AS M1 ON M1.rowNumber = P.rowNumber
  JOIN matrix2 AS M2 ON M2.columnNumber = P.columnNumber AND M2.rowNumber = M1.columnNumber
),

pairsForPositions AS (

SELECT P.rowNumber, P.columnNumber, M1.value AS M1, M2.value AS M2

FROM positions AS P

JOIN matrix1 AS M1 ON M1.rowNumber = P.rowNumber

JOIN matrix2 AS M2 ON M2.columnNumber = P.columnNumber AND M2.rowNumber = M1.columnNumber

This is what we get for our sample matrices:

row	column	m1	m2
1	1	2	5
1	1	3	2
1	2	2	3
1	2	3	4
2	1	4	5
2	1	5	2
2	2	4	3
2	2	5	4

row column m1 m2

1 1 2 5

1 1 3 2

1 2 2 3

1 2 3 4

2 1 4 5

2 1 5 2

2 2 4 3

2 2 5 4

Looks good. Now we just need to aggregate the pairs:

results AS (
  SELECT rowNumber, columnNumber, SUM(M1 * M2) AS value
  FROM pairsForPositions
  GROUP BY rowNumber, columnNumber
)
SELECT * FROM results ORDER BY rowNumber, columnNumber

results AS (

SELECT rowNumber, columnNumber, SUM(M1 * M2) AS value

FROM pairsForPositions

GROUP BY rowNumber, columnNumber

)

SELECT * FROM results ORDER BY rowNumber, columnNumber

And we are done. You can see the code here.