ordering a linked list in mysql-CodePudding

I have a mysql database that stores records in a linked list that maintains the position of records in the list by storing the previous and next id.

the first record of the list has a previous id of 0 and the last record of the list has a next id of 0.

This database can't be changed.

I want to order the items in the list as they should be presented but was having a lot of trouble working out how to do it. I tried numerous approaches - like joining the table to itself on next_id = id. i also tried trying to do a group_concat on next_ids and ordering by find_in_set but didn't get anywhere with that approach either.

here is an sql fiddle with the basic idea. http://sqlfiddle.com/#!9/29b681/2

create table tmp (
  id int unsigned NOT NULL AUTO_INCREMENT,
  prev_id int unsigned  comment 'previous id',
  next_id int unsigned comment 'next id',
  title char(100) comment 'the record',
  primary key (id),
  key prev_id_idx (prev_id),
  key next_id_idx (next_id)
)
ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;
insert into tmp values (1,0,2,'seq 1'),
(2,1,3,'seq 2'),
(3,2,10,'seq 3'),
(10,3,5,'seq 4'),
(5,10,6,'seq 5'),
(6,5,0,'seq 6');

select * from tmp order by title

my question is, how do i order the records so they are presented in order, as defined by the previous and next ids?

CodePudding user response：

This is something interesting for me. I'm assuming that you're on a newer MySQL version that supports most of the latest functions. Your idea of returning a comma-separated list kind of aligned with my thoughts however I don't think that it's easy to determine the ordering using FIND_IN_SET. Although, I could be wrong.

Here's an idea; using JSON_TABLE function on a converted comma-separated list to a valid JSON array. The first step is to get values in a single row according to the order of id=next_id. The end result should be:

1,2,3,10,5,6

This need a multiple LEFT JOIN according to the total rows in the table, so 6 rows turn to 5 LEFT JOINs:

SELECT t1.id, 
               t1.next_id ,
               t2.next_id ,
               t3.next_id ,
               t4.next_id ,
               t5.next_id 
  FROM tmp t1 
   LEFT JOIN tmp t2 ON t1.next_id=t2.id 
   LEFT JOIN tmp t3 ON t2.next_id=t3.id 
   LEFT JOIN tmp t4 ON t3.next_id=t4.id 
   LEFT JOIN tmp t5 ON t4.next_id=t5.id 
   LEFT JOIN tmp t6 ON t5.next_id=t6.id 
WHERE t1.id=1;

Result:
 ---- --------- --------- --------- --------- --------- 
| id | next_id | next_id | next_id | next_id | next_id |
 ---- --------- --------- --------- --------- --------- 
|  1 |    2    |    3    |    10   |    5    |    6    |
 ---- --------- --------- --------- --------- ---------

Next is to convert those comma-separated values to become a JSON ARRAY. I achieved this using a combination of a couple of concatenation method in SELECT. Thus:

Result:
 ------------------------------------  
| CONCAT('["',CONCAT_WS('","',t1.id, |
|               t1.next_id ,         |
|               t2.next_id ,         | 
|               t3.next_id ,         |
|               t4.next_id ,         |
|               t5.next_id ),'"]')   |
 ------------------------------------  
|     ["1","2","3","10","5","6"]     |  <---- this becomes a valid JSON value
 ------------------------------------

Then with that, I used a combination of JSON_TABLE with ROW_NUMBER() function retaining the order from the converted JSON value in the end query.

SELECT *
 FROM tmp t JOIN
  (SELECT idx,
        ROW_NUMBER() OVER () rn
       FROM
        JSON_TABLE(@values,"$[*]"
          COLUMNS(
            idx INT PATH "$"
           )
        ) data) r
  ON t.id=r.idx
ORDER BY rn;

Value from the first query I've inserted into @values variable before I used it in the final query.

Since the first query depends on how many rows present in the table, it has to be always updated whenever there's a new/removed row of data. To resolve the dynamism issue, you probably can generate the first query using prepared statement:

SET @sql := NULL;

WITH RECURSIVE cte AS (
SELECT 1 ctr, COUNT(*) mxct FROM tmp UNION ALL
SELECT ctr 1, mxct FROM cte WHERE ctr 1 <= mxct)
SELECT CONCAT('SELECT CONCAT(\'["\',CONCAT_WS(\'","\',t1.id, ',
         GROUP_CONCAT(CONCAT('t',c1.ctr,'.next_id ')),
       '),\'"]\') INTO @val FROM tmp t1 ',
       GROUP_CONCAT(CONCAT('LEFT JOIN tmp t',c2.ctr,' ON t',c1.ctr,'.next_id=t',c2.ctr,'.id') 
      SEPARATOR ' '),' WHERE t1.id=1;') INTO @sql
FROM cte c1 
 LEFT JOIN cte c2
 ON c1.ctr = c2.ctr-1
WHERE c2.ctr IS NOT NULL;

PREPARE stmt FROM @sql;
EXECUTE stmt;
DEALLOCATE PREPARE stmt;

Demo fiddle

CodePudding user response：

Hi you have a double linked list, please see below example of recursive cte function:

WITH RECURSIVE cte ( id, prev_id, next_id, title )
 AS
  ( SELECT id, prev_id,next_id,title
      FROM tmp WHERE next_id =0
  UNION ALL
  SELECT tmp.id,tmp.prev_id,tmp.next_id,tmp.title
     FROM cte JOIN tmp ON cte.id = tmp.next_id
   )
SELECT * FROM cte ORDER BY id;

prev_id and next_id should be referencing the same table with that your table definition should look like this:

create table tmp (
id int unsigned NOT NULL AUTO_INCREMENT,
prev_id int unsigned reference tmp(id)  comment 'previous id',
next_id int unsigned reference tmp(id) comment 'next id',
title char(100) comment 'the record',
primary key (id),
key prev_id_idx (prev_id),
key next_id_idx (next_id)
);

You should also enforce constraint on this columns to be sure that next_id -> next_id.prev_id

Hope i give you an idea how to solve your problem.