How to create fast database queries

Archive for December 29th, 2009

Linked lists in MySQL: multiple ordering

Comments enabled. I *really* need your comment

Answering questions asked on the site.

Rick McIntosh asks:

I have two tables, one with a list of spreadsheets (a) and the other with a list of the column headings that show in the spreadsheets (b).

id parent
1 2
2 0
id parent aid
1 1 1
2 0 1
3 2 1
4 6 2
5 4 2
6 0 2

I want to bring the columns back in first the order of the spreadsheets as defined by the a.parent_id then ordered as b.parent_id:

id parent aid aparent
6 0 2 0
4 6 2 0
5 4 2 0
2 0 1 2
3 2 1 2
1 1 1 2

This can be done using the same recursion technique as the one that was used to build a simple linked list.

MySQL does not support recursion directly, but it can be emulated using subquery calls in the SELECT clause of the query, using session variables to store the recursion state.

In this case we need to do the following:

  1. Generate a dummy recordset for recursion that would contain as many rows as the resulting recordset. This is best done by issuing a JOIN on the FOREIGN KEY, without any ordering. The values of the recordset will not be used in the actual query.
  2. Initialize @a and @b to be the first value of a and a 0, accordingly.
  3. In the loop, make a query that would return the next item of b for the current value of @a, or, should it fail, return the first item of b for the next @a. This is best done using a UNION ALL with a LIMIT.
  4. Adjust @a so that is points to the correct item: just select the appropriate value from b

Let's create a sample table:
Read the rest of this entry »

Written by Quassnoi

December 29th, 2009 at 11:00 pm

Posted in MySQL