Швидке визначення інтервалів у запиті
Суть завдання визначення інтервалів полягає в тому, що є таблиця, що містить безліч дат, дат з часом або просто чисел. Потрібно побудувати по цій таблиці інтервали, куди вихідні дати (числа) розбивають тимчасову (числову) вісь.
| t1 | t1 | t2 | |
| t2 | t2 | t3 | |
| t3 | ------> | t3 | t4 |
| . | . | . | |
| tn | tn-1 | tn |
Наприклад, є дати встановлення цін. За ними можна визначити інтервали сталості цін у вигляді: початок дії ціни – початок дії наступної ціни. Щоб у результаті визначити, наприклад, середню за часом ціну. Або, наприклад, є дата та час документів відвантаження. Тоді можна визначити величини проміжків часу між відвантаженнями: визначити, наприклад, мінімальний чи максимальний інтервал між відвантаженнями одного товару чи одному контрагенту, побудувати гістограму розподілу часу між відвантаженнями.
Судячи з обговорення "У яких завданнях може знадобитися визначати інтервали", такого роду завдання зустрічається на практиці досить часто.
Загальновідомим методом вирішення цієї задачі у запиті є запит такого вигляду:
Найчастіше цього достатньо. Однак коли кількість елементів у вихідній таблиці стає досить великою, час виконання запиту суттєво зростає. Це з квадратичним характером залежності часу роботи запиту від обсягу вихідної таблиці: кожної записи при розрахунку агрегатної функції МІНІМУМ проглядається у середньому половина інших записів!
Ідея, що лежить в основі даного методу,раніше була використана при прискоренні розрахунку наростаючого підсумку в запиті, описаному в статті Баттерфляй - метод швидкого розрахунку наростаючого підсумку у запиті. Однак у цьому випадку запит вийшов більш простим та універсальним.
В основі методу лежить порозрядне сортування, а його схема має багато спільного з олімпійською системою змагань (методом плей-офф). У кожному турі групуються записи, що відрізняються (при відніманні одиниці) молодшим розрядом номера: 1-2, 3-4, 5-6, 7-8 і так далі. У кожній парі визначається (і далі потрапляє в результуючу вибірку) проміжок: інтервал від верхньої межі молодшого елемента до нижньої межі верхнього. А також визначається нова загальна нижня та верхня межа. У наступному турі пара одержує номер, отриманий відкиданням молодшого розряду номерів елементів пари. І так до фіналу. Проміжок визначається лише тоді, коли в угрупованні є обидва елементи, інакше з пари наступного туру виходить єдиний елемент з тими ж межами.
Вищесказане ілюструється схемою одного угруповання (матчу):
та загальною схемою угруповань:
Для тридцяти двох турів та інтервалів, що вимірюються секундами, запит має вигляд:
Здається дивним, що така громіздка конструкція тридцяти трьох запитів може перемагати за часом вихідний запит. Поясненням цього є той факт, що у кожному наступному турі кількість учасників скорочується вдвічі (плюси плей-офф). Отже, кількість матчів дорівнюватиме кількості учасників мінус один! Тобто кількість операцій у цій схемі буде пропорційним числу вихідних записів, а чи не квадрату цього числа. Чим і пояснюється швидкодія методу.
Сказане підтверджується результатами випробувань, наведеними на Фіг.2 (для файлового варіанту) та Фіг.3(Для MSSQL).
З графіків випливає, що запропонований метод перевершує традиційний, починаючи приблизно з 250 записів у файловому варіанті та з 1500 записів у варіанті SQL. Отже, наприклад, середній курс валюти протягом року у файловому варіанті вже вигідніше вважати запропонованим методом.
Але взагалі це запит не "на кожен день". Тільки для дійсно великих обсягів даних та випадків, коли результат потрібний для подальшого використання у запиті. Інакше простіше використовувати позазапитову техніку (наприклад, СКД).
Певною проблемою цього методу є "розрідженість" даних, коли інтервали досить великі. Тоді в перших турах буде багато "неодружених" зустрічей без суперника, що призведе до невеликого уповільнення методу при збереженні в цілому лінійної залежності. У цій залежності лише трохи збільшиться коефіцієнт.
Також слід сказати, що це рішення призначене поки що лише для випадків тета-соединений таблиці із собою. Зовнішньо схожа на дану задачу "множинних зрізів останніх" пропонованим способом не вирішується, хоча також має певні проблеми зі швидкодією та перспективи його підвищення даним методом на великих обсягах даних. Для поширення описаного підходу цей випадок потрібні певні ускладнення, про які, можливо, буде розказано пізніше.
Як приклад використання запропонованого методу до статті додається звіт на основі СКД, який будує гістограму інтервалів між продажами у розрізі організацій з усіма можливими відборами. Звіт побудований на стандартних формах зміни " Управління торгівлею 10.3 " . Використовується оборотний регістр "Продажі". Завдяки методу, що застосовується, досягається висока швидкість побудови звіту на будь-якихобсяги даних.