# Tag Info

## Hot answers tagged gaps-and-islands

20

Your description results in a table definition like this: CREATE TABLE tbl ( lap_id serial PRIMARY KEY , lap_no int NOT NULL , car_type enum NOT NULL , race_id int NOT NULL -- REFERENCES ... , UNIQUE(race_id, car_type, lap_no) ); General solution for this class of problems To get the longest sequence (1 result, longest of all, arbitrary pick ...

18

This is a gaps-and-islands problem. Assuming there are no gaps or duplicates in the same id_set set: WITH partitioned AS ( SELECT *, number - ROW_NUMBER() OVER (PARTITION BY id_set) AS grp FROM atable WHERE status = 'FREE' ), counted AS ( SELECT *, COUNT(*) OVER (PARTITION BY id_set, grp) AS cnt FROM partitioned ) SELECT id_set, ...

17

1. Window functions plus subqueries Count the steps to form groups, similar to Evan's idea, with modifications and fixes: SELECT id_type , min(date) AS begin , max(date) AS end , count(*) AS row_ct -- optional addition FROM ( SELECT date, id_type, count(step OR NULL) OVER (ORDER BY date) AS grp FROM ( SELECT date, id_type ...

11

So the trick here is a property of two equally incrementing series which produce a difference that can be used to identify islands {11,12,13} - {1,2,3} = {10,10,10}. This property isn't enough to identify islands in and of itself, but it's a crucial step that we can exploit to do so. Background Stepping aside from the problem. Let's check this out.. Here ...

10

Given the following sample data: DECLARE @Data AS table ( data integer PRIMARY KEY ); INSERT @Data (data) VALUES (1), (2), (3), (6), (7), (15), (16); One way to achieve the result you are after is: WITH Grouped AS ( -- Identify groups SELECT D.data, grp = D.data - ROW_NUMBER() OVER ...

10

This type of requirement comes under the banner of "gaps and islands". A popular approach is WITH T AS (SELECT *, DENSE_RANK() OVER (PARTITION BY ItemId ORDER BY DateOfChange) - DENSE_RANK() OVER (PARTITION BY ItemId, Status ORDER BY DateOfChange) AS Grp FROM ItemTable) SELECT ItemId, Status, ...

10

A simple and fast variant: SELECT min(number) AS first_number, count(*) AS ct_free FROM ( SELECT *, number - row_number() OVER (PARTITION BY id_set ORDER BY number) AS grp FROM tbl WHERE status = 'FREE' ) x GROUP BY grp HAVING count(*) >= 3 -- minimum length of sequence only goes here ORDER BY grp LIMIT 1; Requires a gapless ...

10

I would form groups with the window function count() and then take the first value for each group: SELECT foo_label , first_value(foo_price) OVER (PARTITION BY foo_label, grp ORDER BY foo_date) AS fixed_foo_price , foo_date FROM ( SELECT foo_label , count(foo_price) OVER (PARTITION BY foo_label ORDER BY foo_date) AS grp , ...

9

If this is a table of back-to-back ranges only, your case can be treated as a classic "gaps and islands" problem, where you just need to isolate islands of consecutive ranges and then "condense" them by taking the minimum [from] and the maximum [to] per island. There is an established method of solving this using two ROW_NUMBER calls: WITH islands AS ( ...

9

First off, gaps in a sequence are to be expected. Ask yourself if you really need to remove them. Your life gets simpler if you just live with it. To get gap-less numbers, the (often better) alternative is to use a VIEW with row_number(). Example in this related answer: Gap-less sequence where multiple transactions with multiple tables are involved Here ...

9

To start, while with only 202 months to check it won't be a huge issue, a recursive CTE is generally the worst possible way to derive a set, in terms of performance (I prove this here and here). If you're going to be running this query more than once (and it sounds like you will be, until you solve the separate issue of who/what is deleting this data and ...

9

One approach to this problem is to do the following: Emulate LEAD on SQL Server 2008. You can use APPLY or a suquery for this. For rows without a next row, add one month to their account date. Join to a dimension table that contains month end dates. This eliminates all rows that don't span at least a month and adds rows to fill in the gaps as necessary. I ...

8

This is a fairly generic way to do this. Bear in mind it depends on your number column being consecutive. If it's not a Window function and/or CTE type-solution will probably be needed: SELECT number FROM mytable m CROSS JOIN (SELECT 3 AS consec) x WHERE EXISTS (SELECT 1 FROM mytable WHERE number = m.number - x....

8

There are a lot of questions and articles about packing time intervals. For example, Packing Intervals by Itzik Ben-Gan. You can pack your intervals for the given user. Once packed, there will be no overlaps, so you can simply sum up the durations of packed intervals. If your intervals are dates without times, I'd use a Calendar table. This table simply ...

7

create table tbl (lap_no int, car_type text, race_id int); insert into tbl values (1,'red',1),(2,'red',1),(3,'red',1),(4,'red',1), (1,'blue',1),(5,'red',1),(2,'blue',1),(1,'green',1); select car_type, race_id, sum(case when lap_no=(prev+1) then 1 else 0 end)+1 seq_len from ( select *, lag(lap_no) over (partition by car_type,...

7

I strongly agree that a Numbers and a Calendar table are very useful and if this problem can be simplified a lot with a Calendar table. I'll suggest another solution though (that doesn't need either a calendar table or windowed aggregates - as some of the answers from the linked post by Itzik do). It may not be the most efficient in all cases (or may be the ...

7

A suggestion that should work in 2008 version. Tested at rextester.com: with end_points as -- find start and end points ( select id, time, value from table_x where value in (15, 16) ), start_points as -- only the start points ( select id, time, value from end_points where ...

7

You can do this as a simple subtraction of ROW_NUMBER() operations (or if your dates are not unique, though still unique per id_type, then you can use DENSE_RANK() instead, though it will be a more expensive query): WITH IdTypes AS ( SELECT date, id_type, Row_Number() OVER (ORDER BY date) - Row_Number() OVER (PARTITION BY ...

7

Your question is not clearly formed, but considering your examples - Phil's comment was correct: Your example only makes sense if there is another column that defines the order of the data (which is the order you have presented the data as in your question). Unless you have an additional column with the order of rows - there is no solution to your ...

6

The merge join works like a zipper - if you don't care about order, SQL Server knows that it can sort the input in any way it wants, and not have to worry about re-ordering anything. When you add the order by, in this case a merge join is no longer the best choice, because materializing and sorting the first CTE twice in the order defined by the ROW_NUMBER() ...

6

You can group the data using a trick using row number - row number partitioned by status. That will create the same number for rows with the same status for a range of dates. This just takes the rows ordered by entry_date and status, but you might want to do something better for the entries on the same day: select ID, status, min(entry_date) as ...

6

This one uses a recursive CTE. Its result is identical to the example in the question. It was a nightmare to come up with... The code includes comments to ease through its convoluted logic. SET DATEFIRST 1 -- Make Monday weekday=1 DECLARE @Ranked TABLE (RowID int NOT NULL IDENTITY PRIMARY KEY, -- Incremental uninterrupted sequence in the ...

6

select log_id ,array_agg (sequence) from (select log_id ,sequence ,count (is_restart) over ( partition by log_id order by made_at ) as restart_id from ...

6

On Postgres 8.4 you can use a RECURSIVE function. How do they do it The recursive function adds a level to each different id_type, by selecting dates one by one on descending order. date | id_type | lv -------------------------------------- 2017-01-10 07:19:21.0 3 8 2017-01-10 07:19:22.0 3 8 2017-01-10 07:19:23.1 ...

6

There are a lot of different questions here. When it comes to generating the full result set (the mapping of times to IDs), what you have is the way that I would do it, although I'd add a nonclustered index on WindowStart that includes WindowEnd. SQL Server can scan through the covering index, find the next ID and WindowStart values using LEAD() (or the dual ...

6

I've done this in stages using CTEs so that you can see how it's done as the queries progress. Each CTE adds a column in the output in order to show you progress. It's pretty much self-documenting with the CTE names, to be honest. with lags as ( select player, dt, is_winner, lag(is_winner) OVER (partition by player ORDER BY dt ...

5

First, we combine intervals that overlap to find all the contiguous "islands" of the intervals: with c as ( select *, max(end_date) over (order by start_date rows between unbounded preceding and 1 preceding) as previous_max from my_table ) select start_date, ...

5

The answer with the variables is going to be more efficient but here is an answer with pure SQL: select a.id_user, a.id_ringtype, a.number as min, min(b.number) as max from rings as a join rings as b on a.id_user = b.id_user and a.id_ringtype = b.id_ringtype and a.number <= b.number where not exists ...

5

Since MySQL doesn't support ROW_NUMBER(), You can use a variable to create a group like this. Sample Data CREATE TABLE `Rings` ( ID_RingType CHAR(2), Number MEDIUMINT UNSIGNED, ID_User INT(11) ); INSERT INTO `Rings` VALUES ('AA',1,1), ('AA',2,1), ('AA',3,1), ('AA',11,1), ('AA',12,1), ('AA',13,1), ('AA',14,1), ('AA',15,1), ('...

5

This will return only the first of the 3 numbers. It does not require that the values of number are consecutive. Tested at SQL-Fiddle: WITH cte3 AS ( SELECT *, COUNT(CASE WHEN status = 'FREE' THEN 1 END) OVER (PARTITION BY id_set ORDER BY number ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING) AS cnt FROM atable ) SELECT ...

Only top voted, non community-wiki answers of a minimum length are eligible