Hacking Linear Algebra in SQL…

The power and convenience of modern programming tools means that there a few good reasons for doing linear algebra in SQL, so this blog post is just a bit of fun. But more than just fun, it speaks to a growing trend towards data exploration and machine learning within industry and the explosion of interest in languages like R & Python. Let me begin though with where this little challenge came from…

 

Data discovery tools are a high priority for businesses, but vendor products can be lacking…(source: Magic Quadrants focus on data discovery tools in his news recap)


 

One of my favourite things to do is to explore data. Data exploration is a big part of my day, whether investigating database performance, customer data or just for fun. I am a SQL Server DBA and work in a purely Microsoft shop, inevitably I have to find ways to reproduce processes in a Microsoft technology common to our team. There is hot debate around the suitability and relevance of Microsoft’s Business Intelligence stack when it comes to advanced analytics, data mining and machine learning.

 

“In recent years, Microsoft has been losing ground among [data scientists]” (source: SearchBusinessAnalytics)


 

On one hand, Microsoft report themselves as “leaders” in BI industry and cite Gartner’s Magic Quadrant for Business Intelligence and Analytics Platforms. And yet, other groups describe the diminishing presence of Microsoft in the advanced analytics space, and quote the exact same Gartner report.

 

Microsoft’s SQL Server 2012 Analysis Services software fails to deliver adequate functionality when compares to market leaders… (source: Microsoft buys R language vendor Revolution Analytics)

 

Which ever side of the fence you sit on, no will argue that a combination of technologies yields the best results. A view-point that perhaps Microsoft themselves would support following their recent acquisition of of Revolution R.

In this post, we explore and compare some very basic linear transformations in SQL and Octave. These are operations that we use daily to reduce the dimensionality of data and visualise trends / patterns. Even with a little experimentation, it quickly becomes clear why picking the right tool for the job is critical.

 
 
Setup

Let’s begin by creating a couple of matrices:

A = \begin{bmatrix} 1 & 2 & 1 \end{bmatrix}, \newline\newline B = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}

 

create table A
(
    rowID int identity(0, 1) not null,
    a0 int,
    a1 int,
    a2 int
);
go
insert into A
    select 1, 2, 1;
go

create table B
(
    rowID int identity(0, 1) not null,
    b1 int
);
go
insert into B
    values (1), (0), (1);
go

 
 
 
The Dot Product
 

The first transformation we will attempt is a dot product which is a nice, simple operation:

A \cdot B = \begin{bmatrix} 1 & 2 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} = 2

Most programming languages provide a simple interface, for example Octave:

octave> A = [1 2 1]; B = [1; 0; 1];
octave> A * B
ans =
  2

In theory, doing this in SQL should be straight forward – a join and aggregate. But there are a couple of tricks:

  1. we need to treat both vectors as column vectors, which means we need to transpose A
  2. we need something to join the rows on, which is why we introduced the artificial ‘rowID’ into table B, and which we will also introduce into the transpose of A

And here it is:
 

with A_transpose as
(
	select 0 as 'rowid', a0 as 'ax' from A
	union all select 1 as 'rowid', a1 as 'ax' from A
	union all select 2 as 'rowid', a2 as 'ax' from A
)
select sum(ax * b1) as 'DotProduct'
from A_transpose
	inner join B on B.rowid = A_transpose.rowid;

 
It’s not too bad, even if the code is a little exaggerated. Perhaps we should try something more interesting…

 
 
The Inner Product
 
Let’s extend this and take the inner product of a matrix, A, and a vector, B, shown below:

A = \begin{bmatrix} 1 & 2 & 1 \\ -1 & 1 & 0 \\ 1 & 0 & -2 \end{bmatrix} , B = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} ,  A \cdot B =  \begin{bmatrix} 2 \\ -1 \\ -1 \end{bmatrix}

Again, this isn’t a challenge in most programming languages and Octave is particularly simple:

octave> A = [1 2 1; -1 1 0; 1 0 -2]; B = [1; 0; 1];
octave> A * B
ans =
   2
  -1
  -1

 
It gets a little more interesting in SQL now. Unfortunately our previous query will not work:
 

with A_transpose as
(
	select 0 as 'rowid', a0 as 'ax' from A
	union all select 1 as 'rowid', a1 as 'ax' from A
	union all select 2 as 'rowid', a2 as 'ax' from A
)
select sum(ax * b1) as 'DotProduct'
from A_transpose
	inner join B on B.rowid = A_transpose.rowid;
-- output: 0

 
 
Looking more closely at A_transpose, you will notice that it completely ‘melts’ matrix A into a single column:
 

-- A is essentially 'melted' into a single column vector
with A_transpose as
(
	select 0 as 'rowid', a0 as 'ax' from A
	union all select 1 as 'rowid', a1 as 'ax' from A
	union all select 2 as 'rowid', a2 as 'ax' from A
)
select * from A_transpose

 
 
What we need to return, is a scalar value for each row of A (or column of A_transpose). We can do this by adding an artificial column id, “colID”, to A_transpose and aggregating by column:
 

select sum(ax * b1) as 'DotProduct'
from (
		select rowid
			 , ROW_NUMBER() over (partition by rowid order by rowid) as 'colID'
			 , ax from (
							select 0 as 'rowid', a0 as 'ax' from A
							union all select 1 as 'rowid', a1 as 'ax' from A
							union all select 2 as 'rowid', a2 as 'ax' from A
					   ) a_melt
) as A_transpose
	inner join B on B.rowid = A_transpose.rowid
group by colID;

 
 
Wow – this just got messy. Not only do you have to decipher what the query is doing, you probably need to understand at least the basics of linear algebra to figure this out.

 
Here is a slightly cleaner version using CTEs:
 

-- and the equivalent CTE (more readable, but...)
with a_melt as
(
	select 0 as 'rowid', a0 as 'ax' from A
	union all select 1 as 'rowid', a1 as 'ax' from A
	union all select 2 as 'rowid', a2 as 'ax' from A
),
A_transpose as
(
	select rowid
		 , ROW_NUMBER() over (partition by rowid order by rowid) as 'colID'
		 , ax
	from a_melt
)
select sum(ax * b1) as 'DotProduct'
from A_transpose
	inner join B on B.rowid = A_transpose.rowid
group by colID;

 
I still don’t think we would be asking many people in our team to maintain this.

 
 
Rotation Matrices

Here’s one more example of a reasonably straight forward linear transformation, a rotation of A by B:

A = \begin{bmatrix} 1 & 2 & 1 \\ -1 & 1 & 0 \\ 1 & 0 & -2 \end{bmatrix} , B = \begin{bmatrix} 1 & -1 & 1 \\ 0 & 1 & 1 \\ 1 & -1 & -3 \end{bmatrix} ,  A \cdot B =  \begin{bmatrix} 2 & 0 & 0 \\ -1 & 2 & 0 \\ -1 & 1 & 7 \end{bmatrix}

 
Once again, Octave handles all the detail under the hood:

octave> A = [1 2 1; -1 1 0; 1 0 -2];
octave> B = [1 -1 1; 0 1 1; 1 -1 -3];
ans =
  2 0 0
 -1 2 0
 -1 1 7

 
And here is the SQL:

with a_melt as
(
	select 0 as 'rowid', a0 as 'ax' from A
	union all select 1 as 'rowid', a1 as 'ax' from A
	union all select 2 as 'rowid', a2 as 'ax' from A
),
A_transpose as
(
	select rowid
		 , ROW_NUMBER() over (partition by rowid order by rowid) as 'colID'
		 , ax
	from a_melt
)
select sum(ax * b1) as 'rotation_one'
     , sum(ax * b2) as 'rotation_two'
	 , sum(ax * b3) as 'rotation_three'
from A_transpose
	inner join B on B.rowid = A_transpose.rowid
group by colID;

 
 
A practical example
At the beginning of this post, I said that these were operations that we used to summarise and visualise data. As an example, let’s look at DMV data from sys.dm_dm_index_operational_stats. This DMV is one of my favourites and I quite frequently use R or Python to visualise trends. Here is a portion of the source table, dmv_data:

Range Scans Singleton Lookups Row Locks Row lock Waits (ms) Page Locks Page lock Waits (ms) Page IO Latch Wait (ms)
-0.0041 0.037 0.092 0.396 0.055 1 -0.0077
1 0.241 0.0225 0.260 0.091 0.318 0.013
-0.0034 0.4838 1 -0.0053 0.8480 0.239 0.2669
..

And the rotation matrix which we will use to help visualise this data:

PC1 PC2 PC3
0.046 -0.451 0.832
0.476 -0.035 0.225
0.480 0.0036 0.0036
0.0208 -0.648 -0.445
0.634 0.0828 -0.0625
0.0889 -0.590 -0.181
0.3608 0.136 -0.0502

By applying he “rotation query” that we used earlier, we are able to create a 2-dimensional matrix for visualisation. Below are two (identical) plots, one created using R and the other as a result of the “rotation query”:

Index Operational Stats, created using R

Index Operational Stats, created using R

Index Operational Stats created using SQL

Index Operational Stats created using SQL

So, it seems that we can successfully recreate some basic linear transformations in SQL. However, the code is somewhat ugly especially when compared to equivalent operations in Octave. So whatever Microsoft’s plans are for Revolution R, I am looking forward to the power and convenience that a marriage between these two companies might create.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: