Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Поиск дырок в диапазоне  [new]
rinat mergenbaev
Member

Откуда:
Сообщений: 100
есть такой вот скрипт для поиска дырок в диапазоне
как сделать чтобы выделенное (15) подменить max(id) из #tbl1?

create table #tbl1 (id int)

insert #tbl1 select 1
insert #tbl1 select 2
insert #tbl1 select 4
insert #tbl1 select 5;
insert #tbl1 select 15;

WITH Numbers ( n ) AS (
    SELECT min(id) from #tbl1 UNION ALL
    SELECT 1 + n FROM Numbers WHERE n < [b]15[/b]
)

SELECT n FROM Numbers
except 
select id from #tbl1
OPTION ( MAXRECURSION 50 )

drop table #tbl1
26 сен 12, 18:29    [13227784]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Добрый Э - Эх
Guest
rinat mergenbaev,

дословно так и написать:

...
  SELECT 1 + n FROM Numbers WHERE n < (select max(id) from #tbl1)
...
26 сен 12, 18:33    [13227810]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Добрый Э - Эх
Guest
упс, не заметил, что у тебя там рекурсивный СТЕ
26 сен 12, 18:45    [13227869]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
rinat mergenbaev,

Ну так просто же:

SELECT 1 + n FROM Numbers inner join #tbl1 on numbers.n < #tbl1.id
26 сен 12, 18:48    [13227884]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Добрый Э - Эх
Guest
тогда так:
WITH tbl1 (id) as(select 1 union select 2 union select 4 union select 5 union select 15),
tbl2(max_id) as (select max(id) from tbl1),
Numbers ( n ) AS (
    SELECT min(id) from tbl1 UNION ALL
    SELECT 1 + n FROM Numbers cross join tbl2
  where n < max_id
)

SELECT n FROM Numbers
except 
select id from tbl1
OPTION ( MAXRECURSION 50 )
26 сен 12, 18:48    [13227887]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Добрый Э - Эх
Guest
Minamoto
rinat mergenbaev,

Ну так просто же:

SELECT 1 + n FROM Numbers inner join #tbl1 on numbers.n < #tbl1.id
А теперь попробуй вставить это в рекурсивный СТЕ.
Лично у меня выдает сообщение об ошибке:
Microsoft SQL Server 2012 - 11.0.2100.60 (X64) Feb 10 2012 19:39:15 Copyright (c) Microsoft Corporation Express Edition (64-bit) on Windows NT 6.1 <X64> (Build 7601: Service Pack 1) (Hypervisor)
GROUP BY, HAVING, or aggregate functions are not allowed in the recursive part of a recursive common table expression 'Numbers'.
26 сен 12, 18:52    [13227904]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
Minamoto
rinat mergenbaev,

Ну так просто же:

SELECT 1 + n FROM Numbers inner join #tbl1 on numbers.n < #tbl1.id
Упс, что-то я фигню написал, выше вариант с кросс джойном правильный :)
26 сен 12, 18:54    [13227916]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
Добрый Э - Эх
Minamoto
rinat mergenbaev,

Ну так просто же:

SELECT 1 + n FROM Numbers inner join #tbl1 on numbers.n < #tbl1.id
А теперь попробуй вставить это в рекурсивный СТЕ.
Лично у меня выдает сообщение об ошибке:
Microsoft SQL Server 2012 - 11.0.2100.60 (X64) Feb 10 2012 19:39:15 Copyright (c) Microsoft Corporation Express Edition (64-bit) on Windows NT 6.1 <X64> (Build 7601: Service Pack 1) (Hypervisor)
GROUP BY, HAVING, or aggregate functions are not allowed in the recursive part of a recursive common table expression 'Numbers'.
Нет там агрегатных функций, но зато я вместо этого объединяю все увеличивающуюся в размерах таблицу с исходной, и чем плотнее значения в первой таблице прилегают к последнему значению, тем дольше будет выполняться запрос, что очень нехорошо.
26 сен 12, 18:58    [13227942]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Mnior
Member

Откуда: Кишинёв
Сообщений: 6724
А что за странный метод поиска дырок?
26 сен 12, 21:05    [13228470]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Добрый Э - Эх
Guest
Minamoto
Нет там агрегатных функций...
И точно нет. Мельком смотрел, почему-то в твоем решении увидел свой первоначальный вариант с агрегированным подзапросом...
27 сен 12, 04:54    [13229356]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Добрый Э - Эх
Guest
Mnior
А что за странный метод поиска дырок?
А что странного? Все решено "в лоб" и вполне себе прямолинейно: восстановили полную последовательность чисел, откинули из нею существующие в таблице значения, получили дыры.

З.Ы.
Ну и никто не мешает тебе показать свой метод, не странный. ;)
27 сен 12, 04:57    [13229358]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Сон Веры Павловны
Member

Откуда:
Сообщений: 6202
Как вариант:
declare
  @t table (n int);
insert into @t select distinct convert(int, rand(checksum(newid()))*100)
  from master..spt_values where type='P' and number between 1 and 10 order by 1;
select * from @t;
;with cte as (
  select n, row_number() over(order by n) ord from @t
)
select f.n from cte e1
join cte e2 on e2.ord=e1.ord+1
cross apply (
  select number from master..spt_values where type='P' and number between e1.n+1 and e2.n-1
) f(n)
where e2.n-e1.n>1
27 сен 12, 06:48    [13229385]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Сон Веры Павловны
Member

Откуда:
Сообщений: 6202
Наверное, всё же лучше вот так:
;with cte as (
  select n, row_number() over(order by n) ord from @t
)
select f.n from cte e1
join cte e2 on e2.ord=e1.ord+1
cross apply (
  select e1.n+number from master..spt_values where type='P' and number between 1 and e2.n-e1.n-1
) f(n)
where e2.n-e1.n>1

на случай, если
insert into @t select distinct 100000+convert(int, rand(checksum(newid()))*100)
  from master..spt_values where type='P' and number between 1 and 10 order by 1;
27 сен 12, 07:02    [13229394]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Mnior
Member

Откуда: Кишинёв
Сообщений: 6724
Добрый Э - Эх
З.Ы. Ну и никто не мешает тебе показать свой метод, не странный. ;)
Вы издеваетесь.
Да каждый же приведёт. Очевидно же. Оттолкнуться хотя бы от этого:
SELECT N + 1 AS N	FROM <Table>
EXCEPT
SELECT N		FROM <Table>
Уже запись понятной стала.
А далее допилить.
+ Результирующий Код
WITH [Table] AS (SELECT * FROM (VALUES
	 ( 1)
	,( 2)
	,( 4)
	,( 5)
	,(15)
) X(ID)
), [Sequence] AS (
	SELECT	 Row_Number()OVER(ORDER BY S.SequenceID) AS [Sequence]
		,S.SequenceID
	FROM			[Table] L
		FULL MERGE JOIN	[Table] R ON R.ID = L.ID + 1
		CROSS APPLY (SELECT IsNull(R.ID - 1,L.ID + 1)) S(SequenceID)
	WHERE	   L.ID IS NULL
		OR R.ID IS NULL
)	SELECT	 Min(S.SequenceID) AS [From]
		,Max(S.SequenceID) AS [To]
	FROM	(SELECT Min(ID),Max(ID) FROM [Table])M([Min],[Max])
		JOIN [Sequence] S ON S.SequenceID BETWEEN M.[Min] AND M.[Max]
	GROUP BY S.[Sequence]/2
	--	JOIN master.dbo.spt_values N ON N.type = 'P' AND N.number < P.[To] - P.[From]
3 Минуты на 200т лимонной говно-табле (лимон дырок). Это на левых некластерных индексах.
И дело не во времени - ровно столько занимает чтение индексов с диска.
27 сен 12, 13:21    [13231570]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Mnior
Member

Откуда: Кишинёв
Сообщений: 6724
Да Ё, Добрый Э - Эх да вон Сон Веры Павловны намного раньше выставил.
Притом намного проще эффективнее чем у меня.

Долой императивщину! Декларативисты всех стран - объединяйтесь!

PS: Чёрд. Вот я протупил со своим запросом.
27 сен 12, 13:29    [13231684]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Добрый Э - Эх
Guest
Mnior
Вы издеваетесь.
Даже и в мыслях не было.
А что до решения задачи, то никто и не спорит, что способов есть масса. Но не факт, что по производительности они будут лучше того, что было у ТС изначально.

Я тебе даже больше скажу. И твой вариант, и вариант сна веры петровны грешат одним общим недостатком - многократное сканирование одного и того же набора данных для получения значений предыдущей строки...
;)
28 сен 12, 05:31    [13236296]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Добрый Э - Эх
Guest
Вариант под MS SQL Server 2012:
with
--
-- Тестовый набор данных:
  t0 (num) as 
    (
      select * from (values (1),(2),(4),(5),(15)) as v (x)
    ),
--
-- Предварительная обработка исходных данных
--   (вычисление для каждой строки таблицы t0 
--    следующего значения num, сортировка по num):
  t1 (curr_num, next_num) as
    (
      select t0.num, 
             lead(t0.num) over(order by t0.num) as next_num
        from t0 as t0
    )
--
-- Генерирование последовательности отсутствующих чисел:
select s.num
  from t1 as t1
 cross apply
       (
         select t1.curr_num + v.number 
           from master..spt_values as v
          where v.type = 'P'
            and v.number between 1
                             and t1.next_num - t1.curr_num - 1
       ) as s(num)


З.Ы.
Ещё как вариант - можно выкинуть из запроса ту часто, что с outer apply, заменив её на рекурсивный СТЕ. Тогда решение станет полностью самодостаточным и будет основываться только на данных исходной таблицы, без привлечения доп.объектов.
28 сен 12, 06:25    [13236314]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
,tp
Guest
без cross apply и spt_values, но на рекурсивном СТЕ (и всё также под 2012 сервер):
with
--
-- Тестовый набор данных:
  t0 (num) as 
    (
      select v.x from (values (1),(2),(4),(5),(15)) as v (x)
    ),
--
-- Предварительная обработка исходных данных
--   (вычисление для каждой строки таблицы t0 
--    следующего значения num, сортировка по num):
  t1 (curr_num, next_num) as
    (
      select t0.num, 
             lead(t0.num) over(order by t0.num) as next_num
        from t0 as t0
    ),
--
-- Генерирование последовательности отсутствующих чисел:
  t2 (curr_num, next_num, not_exists_num) as
    (
      select t1.curr_num, t1.next_num, t1.curr_num + 1 as not_exists_num
        from t1 as t1
       where t1.next_num - t1.curr_num  > 1
       union all
      select t2.curr_num, t2.next_num, t2.not_exists_num + 1
        from t2
       where t2.next_num - t2.not_exists_num > 1
    )
--
-- Окончательный вывод результата работы запроса:
select *
  from t2 as t2
 order by not_exists_num
option (maxrecursion 0)
28 сен 12, 07:08    [13236327]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
qwrqwr
Member

Откуда: Msk
Сообщений: 1684
rinat mergenbaev
как сделать чтобы выделенное (15) подменить max(id) из #tbl1?

Какие-то сложные варианты тут. =)
По сабжу из первого сообщения - надо просто тащить с собой в рекурсии максимум и сравниваться на каждом шаге с ним.

with -- Тестовый набор данных:
  t0 as 
    (select x from (values (-2),(1),(2),(4),(5),(15)) as v(x)),
  cte as
    (select min(x) as mi, max(x) as ma, min(x)+1 as n from t0 union all select mi, ma, n+1 from cte where n<ma)
    
select n from cte where not exists(select 1 from t0 where x=n)
option (maxrecursion 32767)
28 сен 12, 09:54    [13236674]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Mnior
Member

Откуда: Кишинёв
Сообщений: 6724
Добрый Э - Эх
И твой вариант, и вариант сна веры петровны грешат одним общим недостатком - многократное сканирование одного и того же набора данных для получения значений предыдущей строки.
Это недостаток?
Ты хоть планы видел?
Синхронный доступ к данным через Merge, одновременный доступ к памяти максимум двух страниц.
Это тебе не рекурсивный CTE бомбить из пустого в порожнее.
Он недалеко чем вариант 2012-го.
Или вы по общей толщине или циферкам плана сравниваете? :)
Скорость определяется толщиной индекса - и только, в отличие от СTE.
Вот тесты проведите (с планами), тогда и увидите.

qwrqwr не читатель, qwrqwr писатель.
qwrqwr
Какие-то сложные варианты тут. =)
Ага, скопировали первый же вариант ТС.
Наверно одно-буквенное наименование полей и выстраивание в одну линию упрощают запрос.
13229394 -проще твоего, а 13236314 и подавно.
option (maxrecursion 0) -- Без ограничений
28 сен 12, 21:47    [13241590]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
qwrqwr
Member

Откуда: Msk
Сообщений: 1684
Mnior
Ага, скопировали первый же вариант ТС.
Наверно одно-буквенное наименование полей и выстраивание в одну линию упрощают запрос.
13229394 -проще твоего, а 13236314 и подавно.

Странная претензия. Я отвечал на вопрос из первого поста - потому и изменения исходного запроса минимальны.
Суть изменений я также описал словами, навсякий.

Что до прочих вариантов - то правильной постановкой задачи был бы поиск начал-концов "дырок".
Последовательность потом восстановить по началам-концам - дело техники.
Начала-концы "дырок" находятся в одно чтение таблицы на всех версиях, где есть ранжирование, т.е. начиная с 2005-го.
29 сен 12, 20:22    [13244098]     Ответить | Цитировать Сообщить модератору
 Re: Поиск дырок в диапазоне  [new]
Mnior
Member

Откуда: Кишинёв
Сообщений: 6724
+ qwrqwr
qwrqwr, уже чукча в квадрате.
Зачем вы второй раз повторяетесь?

Про Max было написано сразу же (13227887), и про диапазоны тоже (13229385).

Если вы хотите сами решать без подсказок, отлично!, но зачем превращать форум в личных бложек и свалку копипасты?
А ваше удивление умиляет.

Но самое фиговое, что вы не просто не читаете других, вы продолжаете упоминать левый вариант решения. Это хорошо что вы поправились. Только зачем всем в этом участвовать?
30 сен 12, 01:30    [13244641]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить