Identifying missing sequences in SQLite table

Question

I have a single table with 1000's of records. Each record represents a file in a sub-folder and some attributes related to the file. Fields/ columns of interest are as follows:

__dirpath = the name of each sub-folder containing files of interest track = sequence number of the file (these should be consecutive and can range from one to any number

I'm looking for missing numbers in the sequence represented by the files related to every __dirpath.

A generalised query to list the start and stop of every missing number in a sequence is as follows (credit to: https://www.xaprb.com/blog/2005/12/06/find-missing-numbers-in-a-sequence-with-sql/):

select start, stop from (
  select m.id + 1 as start,
    (select min(id) - 1 from sequence as x where x.id > m.id) as stop
  from sequence as m
    left outer join sequence as r on m.id = r.id - 1
  where r.id is null
) as x
where stop is not null order by start, stop;

In this instance however, I need to do the same for every sequence related to records with the same __dirpath value. Assuming the sequence table has a __dirpath column in addition to the id field in the generalised example, how would one do this?

Here's a table with dummy data and the aforementioned query adapted to this table without regard to __dirpath:

drop table if exists sequence;
    create table sequence (__dirpath blob, id int not null);

insert into sequence(__dirpath, id) values
    ("A", 1), ("A",2), ("A", 3), ("A", 4), ("A", 6), ("A", 7), ("A", 8), ("A", 9),
    ("A", 10), ("A", 15), ("A", 16), ("A", 17), ("A", 18), ("A", 19), ("A", 20);

If one then runs the following query you get the correct answer set:

select dir, start, stop from (
  select m.id + 1 as start,
    (select min(id) - 1 from sequence as x where x.id > m.id) as stop, m.__dirpath as dir
  from sequence as m
    left outer join sequence as r on m.id = r.id - 1
  where r.id is null
) as x
where stop is not null order by dir, start, stop;

The results are correct and as follows:

If one then adds the following records to the table:

insert into sequence(__dirpath, id) values
    ("B", 1), ("B",4), ("B", 5), ("B", 6), ("B", 7), ("B", 117), ("B", 14), ("B", 9),
    ("B", 10), ("B", 15), ("B", 16), ("B", 17), ("B", 18), ("B", 19), ("B", 20);

and reruns the above left outer join, the results are meaningless because values relating to __dirpath = "A" and __dirpath = "B" are all referenced in the query, yielding:

So the question is essentially how to modify the query to reference records only pertaining to each respective __dirpath entry.

user_10498828 · Answer

You must add the column __dirpath in the correlated subquery and the join:

SELECT dir, start, stop 
FROM (
  SELECT m.id + 1 start,
    (SELECT MIN(id) - 1 FROM sequence x WHERE x.__dirpath = m.__dirpath AND x.id > m.id) stop, 
     m.__dirpath dir
  FROM sequence m LEFT JOIN sequence r 
  ON m.__dirpath = r.__dirpath AND m.id = r.id - 1
  WHERE r.id IS NULL
) 
WHERE stop IS NOT NULL 
ORDER BY dir, start, stop;

Another solution with a CTE and window functions:

WITH cte AS (
  SELECT __dirpath, grp, MIN(id) min_id, MAX(id) max_id
  FROM (
    SELECT *, SUM(flag) OVER (PARTITION BY __dirpath ORDER BY id) grp
    FROM (
      SELECT *, id - 1 <> LAG(id, 1, id - 1) OVER (PARTITION BY __dirpath ORDER BY id) flag
      FROM sequence
    )
  )  
  GROUP BY __dirpath, grp
)  
SELECT c1.__dirpath, 
       MAX(c1.max_id) + 1 start,
       MIN(c2.min_id) - 1 stop
FROM cte c1 INNER JOIN cte c2
ON c2.__dirpath = c1.__dirpath AND c2.grp = c1.grp + 1
GROUP BY c1.__dirpath, c1.grp

See the demo.

Identifying missing sequences in SQLite table

1 Answers