How to create fast database queries

Archive for June 7th, 2009

Longest common prefix: MySQL

Comments enabled. I *really* need your comment

This is the fourth and final article of the series on how to strip all strings in a set of their longest common prefix and concatenate the results:

, and today we will solve this task for MySQL.

A quick reminder of the problem (taken from Stack Overflow):

I have some data:

id ref
1 3536757616
1 3536757617
1 3536757618
2 3536757628
2 3536757629
2 3536757630

and want to get the result like this:

id result
1 3536757616/7/8
2 3536757629/28/30

Essentially, the data should be aggregated on id, and the ref's should be concatenated together and separated by a / (slash), but with longest common prefix removed.

MySQL solution differs from the previous ones a little.

On the one hand, MySQL is the only RDBMS of all listed above that supplies a built-in GROUP_CONCAT (aggregate function to concatenate strings).

On the other hand, MySQL lacks a way to generate an arbitrary resultset which we relied upon in all solutions above.

This makes it easier to concatenate the results, but a lot harder to find the longest common prefix.

Fortunately, there is a way to do it.

Since 5.1, MySQL offers an XPath manipulation function, namely ExtractValue, that will help us to solve this task.

Unfortunately, ExtractValue is not set generating, i. e. it cannot create an SQL resultset out of an XML nodeset. But XPath itself is quite a powerful tool, and we can implement the longest common prefix algorithm completely in XPath.
Read the rest of this entry »

Written by Quassnoi

June 7th, 2009 at 11:00 pm

Posted in MySQL