![](https://habrastorage.org/files/09e/f4a/c9e/09ef4ac9e59f43a998ad78ab1aa55fa9.png)
Автор: Юрий Цыганенко, Senior QA
Тестирование новых функций часто проводят на данных, взятых с уже функционирующей системы. В этом случае тестировщикам порою приходится строить запросы для хитрых случаев. Например, нужно протестировать новую функциональность интернет-магазина, причём играют роль интервалы между покупками. Нам доступны данные с работающей версии — можно загрузить их на тестовый стенд и проверить работу новой версии продукта. (NB!: конечно, имея дело с «живыми» данными, нужно исключить из них приватную информацию и обеспечить возможность логина интересующим нас пользователям).
Для выбора интересных нам пользовательских аккаунтов нужно сопоставить максимальные интервалы между покупками у разных пользователей.
От тестировщика требуется построить SQL-запрос, выдающий N пользователей, у которых интервалы между датами заказов будут наибольшими.
Аналогичные задачи и их разбор — под катом.
Речь идет о поиске последовательностей записей/интервалов стандартными средствами SQL. Агрегатные функции обрабатывают все данные, попадающие в условие выборки, и поэтому только ими обойтись нельзя.
В качестве примера возьмем датчик погоды, периодически выдающий состояние «ясно» или «пасмурно» и силу ветра. Рассмотрим задачи:
1. Первая часть данных выведена в таблицу 'Weather', включающую поля:
• time // Содержит время измерения;
• clear // Содержит оценку чистоты неба: пусть 0 — пасмурно; 1 — ясно.
Нам нужен запрос, выдающий несколько (допустим, три или менее) наиболее долгих периода (интервала) с ясной погодой. Иными словами, пары записей с ясной погодой, между которыми не будет периодов плотной облачности. Равномерность измерений при этом не подразумевается.
То есть задача сводится к поиску наборов трех или менее значений Period_1…Period_N в порядке убывания.
![](https://habrastorage.org/files/4c3/cbd/9a9/4c3cbd9a97324ae483dfdbcfd0b016a6.jpg)
2. В рамках второй задачи у нас есть похожая на первую таблица 'Wind', включающая записи силы ветра в отдельные моменты времени. Она имеет два поля:
• Time
• Speed
Требуется найти все «локальные максимумы» скорости — т. е. моменты времени и значения скорости, по сравнению с которыми предшествующая и последующая (по времени) записи имеют меньшую скорость.
![](https://habrastorage.org/files/c86/fdf/10f/c86fdf10f9204433aed85aa5942808c1.png)
На графике локальные максимумы соответствуют 3, 10, 14, 17. Для упрощения не будем считать граничную точку 19.
Полагаю, ясно, что «прямым» применением агрегатных функций не обойтись: нужно в условии каким-то образом указать, что точки следуют подряд. Для решения обеих задач воспользуемся приемами:
1. Неявный Join таблицы с ней же самой: в поле FROM через запятую перечислим записи и нашу таблицу (например, FROM Weather w1, Weather w2 ).
На всякий случай: при выборке SELECT w1.*, w2.* FROM Weather w1, Weather w2; выведутся все пары записей, включая совпадающие и повторяющиеся в обратном порядке пары. Т. е. при 10 записях в таблице выведутся 100.
2. Функция exists(), внутри которой пишем вложенный запрос.
Оба эти приема показаны в бесплатном курсе по SQL (видео): тут и тут.
Грубое решение первой задачи: выбираем все пары записей с плохой погодой, между которыми все записи с хорошей погодой, причем не менее 1 (то есть нет плохой поды в промежуточных записях):
SELECT (w2.time - w1.time) as duration
FROM Weather w1, Weather w2
WHERE w2.time > w1.time # вторая точка позде первой
AND w2.clear=0 # в первой точке плохая погода
AND w1.clear=0 # во второй точке плохая погода
AND exists ( # Существуют точки
SELECT * FROM Weather wg
WHERE wg.clear = 1 # с ясной погодой
AND wg.time > w1.time # в промежутке от первой точки
AND wg.time < w2.time # до второй
)
AND not exists ( # Нет точек
SELECT * FROM Weather w3
WHERE w3.clear=0 # с плохой погодой
AND w3.time>w1.time # в промежутке от первой точки
AND w3.time<w2.time # до второй
)
Order by duration DESC
LIMIT 3;
Нюансы: в разных СУБД возможно, потребуются:
• конвертации для типа timestamp, чтобы можно было вычитать w1.time и w2.time;
• ограничение на количество выводимых строк — limit или top.
Проблемы при таком решении:
• Границы периода наблюдений: если все записи в таблице только с ясной погодой, ответа мы не получим. Как, впрочем, не получим и периоды ясной погоды в начале и конце наблюдений;
• В ответе отсутствуют точные данных о первой и финальной записи с хорошей погодой.
Строго говоря, такое решение не отвечает условию задачи («пары записей с ясной погодой, между которыми не будет иной...»).
Обе проблемы лечатся этими же приемами.
Оттачиваем решение: ищем пары записей с хорошей погодой, между которыми нет записей с плохой погодой. Причем так, чтобы у первой записи в паре не было бы предшествующей записи с хорошей погодой (т. е. это была бы запись, начинающая ясный период). Соответственно, у второй записи в паре не должно быть последующей записи с хорошей погодой (т. е. запись замыкала бы ясный период).
Полагаю, достаточно идеи запроса.
Решение второй задачи: ищем тройки последовательных записей, в которых скорость ветра в средней точке больше, чем в каждой из соседних. Соседство проверяется функцией exists аналогично первой задаче: not exists(...). Порядок точек проверяется сравнением значений времени.
На этом я статью завершаю и еще раз рекомендую Стэндфордский курс!
Enjoy!
Комментарии (6)
darthunix
19.11.2016 17:40+1Забавы ради попробовал решить, не подглядывая в ваш вариант (PostgreSQL).
Создаем таблицу с данными (данные неупорядоченные)
create table weather(time timestamp, clear boolean); insert into weather(time, clear) select generate_series( '2000-01-01'::timestamp, '2009-01-01'::timestamp, random() * 7 * '1 day'::interval ) as time, random() > 0.5 as clear order by random();
Находим интервалы солнечных дней (начало, конец и длина), упорядочиваем по длине и выбираем 20.
with ordered_weather as (select * from weather order by time), nasty as ( select row_number() over() as gap_group, time, clear from ordered_weather where not clear ), gaps as ( select row_number() over(), b.gap_group, a.time, a.clear from ordered_weather a left join nasty b using (time, clear) ), limited_gaps as ( select 0 as row_number, 0 as gap_group, (select min(time) - '1 day'::interval from weather) as time, false as clear union all select * from gaps union all select (select max(row_number) + 1 from gaps), (select max(gap_group) + 1 from gaps), null::timestamp, false ) select c.time as clear_start, d.time as clear_stop, (d.time - c.time) as clear_interval from limited_gaps a left join ( select row_number, gap_group + 1 as gap_group from limited_gaps where gap_group is not null ) b using(gap_group) join limited_gaps c on c.row_number = coalesce(b.row_number,0) + 1 join limited_gaps d on d.row_number = a.row_number - 1 where a.gap_group is not null and (a.row_number - coalesce(b.row_number,0) > 1) order by (d.time - c.time) desc limit 20;
RedQuark
20.11.2016 13:56Т.е. открыть курсор с парой переменных мы принципиально не хотим? Научим писать заведомо провальные по производительности запросы. Оказывается это еще и именованный алгоритм, судя по комментарию.
darthunix
21.11.2016 00:04Курсоры — это медленно и очень плохая практика в sql. Ну и да, вы смотрели план выполнения запроса в этом именованном алгоритме?
DataArt
21.11.2016 14:181. Большое спасибо за ссылку!
2. Конечно, есть разные способы решения. Exists и неявный join будут работать везде, включая mysql.
3. Производительность не рассматривалась.
«Провальные по производительности» запросы успешно решали реальные задачи в тестировании. Хотя, конечно, кое-где произвидительность станет узким местом.
Daniil1979
Давая решение алгоритма islands/gaps, было бы неплохо обозначить, что это именно islands/gaps.
https://www.simple-talk.com/sql/t-sql-programming/calculating-gaps-between-overlapping-time-intervals-in-sql/
x893
Статья по ссылке очень неплохая. Спасибо!