Эксперименты над олимпиадной задачей / forpes.ru

Главная
Эксперименты над олимпиадной задачей

Эксперименты над олимпиадной задачей +3

03.05.2017 10:31

ejsmile 4 2300 Источник

Так получилось, что я попал в магистратуру, и как то гуляя мимо кафедры на глаза попалась олимпиадная задача по 1С. Кратко задача звучит так: «Есть записи продажи за каждый день, необходимо найти наибольший период когда план выполнялся». А потом когда я гулял со спящей дочкой у меня встав вопрос, а сколькими способами это можно сделать на SQL. Решения будут на основе MS SQL.

Создадим таблицу и начнем

Текст SQL скрипта по созданию таблицы

CREATE TABLE [tmp].[forFindDate](
	[date] [datetime] NOT NULL,
	[value] [int] NOT NULL,
 CONSTRAINT [PK_forFindDate] PRIMARY KEY CLUSTERED 
(
	[date] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]

GO

INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170401', 10)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170402', 20)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170403', 20)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170404', 20)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170405', 10)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170406', 10)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170407', 30)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170408', 36)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170409', 35)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170410', 30)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170411', 30)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170412', 20)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170413', 10)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170414', 40)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170415', 40)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170416', 10)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170417', 50)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170418', 52)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170419', 53)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170420', 53)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170421', 50)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170422', 51)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170423', 52)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170424', 50)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170425', 50)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170426', 50)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170427', 10)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170428', 10)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170429', 10)
INSERT INTO [tmp].[forFindDate] ([date], [value]) VALUES ('20170430', 10)

GO

Первый способ через соединения самого на себя (через join-ы).

SQL запросы через join

declare @planValue int = 15

--самый очевидный left
select 	
	top 1
	'сам на себя',
	BeginDate,
	DATEADD(Day, -1, EndDate) EndDate
from (select 
		s.date BeginDate, 
		ISNULL(min(e.date), '20170501') EndDate
	from [tmp].[forFindDate] s
		left join [tmp].[forFindDate] e
			on
				s.date < e.date
			and
				not e.value > @planValue
	where
		s.value > @planValue
	group by
		s.date) tmp
order by
	DATEDIFF(day, BeginDate, EndDate) desc

-- или как мне нравиться больше через with

;with periodDate1 as(
	select 
		s.date BeginDate, 
		ISNULL(min(e.date), '20170501') EndDate
	from [tmp].[forFindDate] s
		left join [tmp].[forFindDate] e
			on
				s.date < e.date
			and
				not e.value > @planValue
	where
		s.value > @planValue
	group by
		s.date
)
select 
	top 1
	'сам на себя (with left)' title,
	BeginDate,
	DATEADD(Day, -1, EndDate) EndDate
from periodDate1
order by
	DATEDIFF(day, BeginDate, EndDate) desc

--меняем на full

;with periodDate2 as(
	select 
		s.date BeginDate, 
		ISNULL(min(e.date), '20170501') EndDate
	from [tmp].[forFindDate] s
		full join [tmp].[forFindDate] e
			on
				s.date < e.date
			and
				not e.value > @planValue
	where
		s.value > @planValue
	group by
		s.date
)
select 
	top 1
	'сам на себя (with full)' title,
	BeginDate,
	DATEADD(Day, -1, EndDate) EndDate
from periodDate2
order by
	DATEDIFF(day, BeginDate, EndDate) desc
--меняем на right
;with periodDate3 as(
	select 
		ISNULL(max(s.date), '20170401') BeginDate,
		e.date EndDate
	from [tmp].[forFindDate] s
		right join [tmp].[forFindDate] e
			on
				s.date < e.date
			and
				not s.value > @planValue
	where
		e.value > @planValue
	group by
		e.date
)
select 
	top 1
	'сам на себя (with right)' title,
	DATEADD(Day, 1, BeginDate) BeginDate, 
	EndDate
from periodDate3
order by
	DATEDIFF(day, BeginDate, EndDate) desc

Причем при любом join получим абсолютно одинаковый план (через NESTED LOOP (left outer join)).

Планы исполнения запросов через join

Второй способ через корреляционный запрос

SQL запросы через корреляционный запрос

declare @planValue int = 15

;with periodDate4 as(
	select 
		s.date BeginDate, 
		ISNULL((select DATEADD(DAY, -1, isNull(min(d.date), '20170501')) from [tmp].[forFindDate] d where d.date > s.date and not d.value > @planValue), '20170501') EndDate
	from 
		[tmp].[forFindDate] s
	where
		s.value > @planValue			
)
select top 1 
	'корреляционный запрос', p.BeginDate, p.EndDate
from 
	periodDate4 p 
order by 
	DATEDIFF(DAY,  p.BeginDate, p.EndDate) desc

В данном случай мы получаем NESTED LOOP (inner join)).

Планы исполнения корреляционного запроса

Третий способ пока все не интересно, теперь возьмем функцию APPLY (появилась в MS SQL 2005). Фактически на каждую строку будем делать под запрос.

SQL запросы через outer apply

declare @planValue int = 15

;with periodDate5 as(
	select 
		s.date BeginDate, 
		ISNULL(min(e.date), '20170501') EndDate
	from [tmp].[forFindDate] s
		outer apply
		(
		--особенностью храненим данных (сортировка по дате)
		select
			top 1
				ee.date
		from
			[tmp].[forFindDate] ee
		where
				s.date < ee.date
			and
				not ee.value > @planValue
		) e
	where
		s.value > @planValue
	group by
		s.date
)

select 
	top 1
	'sql 2005 apply' title,
	BeginDate,
	DATEADD(Day, -1, EndDate) EndDate
from periodDate5
order by
	DATEDIFF(day, BeginDate, EndDate) desc

В данном случай опять получаем NESTED LOOP (left outer join), но этот способ самый оптимальный на данный момент (по крайне мере так считает MS SQL).

Планы исполнения apply

Пока все было скучно и обыденно.

Четвертый способ поиграем с рекурсией: к текущей строке будем клеить данные если дата на один день старше и выполняется план продаж. Таким образом будем расширять интервал.

Т.к. данных не много, то длина последовательности небольшая, как и глубина стека вызовов (CTE recursive возможно начиная с 2005).

SQL запросы рекурсия

declare @planValue int = 15

;with periodDate6 as (
	select
		f.date BeginDate,
		DATEADD(day, 1, f.date) EndDate
	from
		[tmp].[forFindDate] f
	where
		f.date = '20170417'
	and
		f.value > @planValue
	union all
	select
		r.BeginDate,
		DATEADD(day, 1, f.date) EndDate
	from
		[tmp].[forFindDate] f
			inner join periodDate6 r
				on
					r.EndDate = f.Date
				and
					value > @planValue
)
select 
	top 1
	'recursive' title,
	BeginDate,
	DATEADD(Day, -1, EndDate) EndDate
from periodDate6
order by
	DATEDIFF(day, BeginDate, EndDate) desc

Планы исполнения корреляционного запроса

Пятый способ перейдем к возможностям MS SQL 2012 к аналитической функций LEAD. Функция LEAD возвращает следующие значения со сдвигом в пределах секций по сортировке. Сортировать будем по датам, секций у нас две выполнения и не выполнения плана, что бы найти максимальный период поступим хитро: будем искать пропуски в не выполнении плана, т.е. когда мы потом сдвинем даты начала вперед, а конец назад, то получим отрезки выполнения плана.

SQL запросы LEAD

declare @planValue int = 15

;with periodDate7 as (
	select
		date beforDate,
		lead(f.date, 1, '20170501')
		OVER ( PARTITION BY iif(f.value < @planValue, 1, 0) order by f.date) afterDate

	from [tmp].[forFindDate] f
)
select 
	top 1
	'func 2012' title,
	DATEADD(Day, 1, beforDate) BeginDate,
	DATEADD(Day, -1, afterDate) EndDate
from periodDate7
order by
	DATEDIFF(day, beforDate, afterDate) desc

На плане исполнения видно, что не происходит соединения таблиц

Планы исполнения LEAD

Шестой способ А теперь побалуемся перемножим таблицу саму на себя: найдем все возможные сочетания дат (30*30 = 900), отберем те у которых дата начало меньше даты конца и в этом интервале нет события не исполнения плана.

SQL запросы рекурсия

declare @planValue int = 15

;with periodDate8 as(
	select 
		ISNULL(s.date, '20170401') BeginDate, 
		ISNULL(e.date, '20170501') EndDate
	from [tmp].[forFindDate] s, [tmp].[forFindDate] e
)
select top 1 
	'for Fun', p.BeginDate, p.EndDate
from periodDate8 p 
	left join [tmp].[forFindDate] b
		on
			b.date between p.BeginDate and p.EndDate
		and
			not b.value > @planValue
where
	p.BeginDate < p.EndDate
and
	b.date is null
order by
	DATEDIFF(day, BeginDate, EndDate) desc

Самый медленный и тяжелый способ. Но мы гонимся не за производительностью, а за количество решений задачи.

Планы исполнения перемножения таблицы

Седьмой способ Обычный курсор. По перебираем данные у которых план выполнен, и ищем максимальный последовательный участок.

SQL запросы курсором

declare @planValue int = 15
declare @endDate datetime = null, 
		@Intervat int = 0,
		@maxIntervat int = 0, 
		@old_date datetime = '20170401', 
		@cur_date datetime

DECLARE date_cursor CURSOR  
    FOR SELECT date FROM [tmp].[forFindDate] where value > @planValue
	OPEN date_cursor  
		FETCH NEXT FROM date_cursor 
		INTO @cur_date  
		WHILE @@FETCH_STATUS = 0  
			BEGIN

			IF (@cur_date = DATEADD(DAY, 1, @old_date)) BEGIN
				SET @Intervat = @Intervat + 1
				IF(@Intervat > @maxIntervat) BEGIN
					SET @maxIntervat = @Intervat
					SET @endDate = @cur_date
				END
			END else 
			Begin
				set @Intervat = 0
			end
			SET @old_date = @cur_date
			FETCH NEXT FROM date_cursor 
			INTO @cur_date
		END   
	CLOSE date_cursor;  
DEALLOCATE date_cursor;  

select 'cursor' title, DATEADD(DAY, - @maxIntervat, @endDate) BeginDate, @endDate EndDate

Пока это все, что смог придумать. Жду еще вариантов в комментариях.

Поделиться с друзьями

-->

Комментарии (4)

mezastel
04.05.2017 12:00
#10202992
олимпиадная задача по 1С

Вот на этом этапе уже становится немного некомфортно. Олимпиады по 1С. Что следующее?
1. ejsmile
  04.05.2017 15:48
  #10203480
  1С выполняет свою функцию ищет ресурсы среди студентов, проводит пропаганду. Там еще есть конкурсы дипломных проектов на технологиях 1С и прочие.
  
  Но суть упражнения есть задача (откуда её брать без разницы), и под нее надо подобрать наибольшие количество запросов с разными планами исполнения, у меня на практике переписывания запроса под другой план давала много кратный прирост производительности.
  
  Гулял со спящим ребенком разминал мозги. Жаль, что еще вариантов не предлагают.

exit999
04.05.2017 15:38
#10203454
Хотелось бы уточнить, что в языке запросов от 1С, который присутствует в платформе «1С: Предприятие» нет таких вещей, как:
1) Курсоры
2) Оператор WITH
3) Функция LEAD
4) Функция APPLY
5) Соединения полей из подзапроса с полями внешнего запроса (Корреляционные подзапросы)

Т.е. ваши решения очень интересные, но именно в контексте программ от 1С подходит только решение с join'ами.
1. ejsmile
  04.05.2017 15:44
  #10203470
  Да я представляю, что в 1С можно либо локально данные выгрузить и обойти циклом, либо join-ы. Поэтому мне было интересно, как это решить именно на SQL, особенно с расширениями на MS SQL server-а. Если бы кто написал какие возможности на Oracla-е, тоже было бы интересно. Бывает такие изыскания помогает в смежных проектах, т.к. планы разные и от размера многое зависит и структуры хранения.

Эксперименты над олимпиадной задачей +3

Комментарии (4)

mezastel

ejsmile

exit999

ejsmile