7 марта 2001 г.

Павел Шендрыгайлов,
заместитель начальника управления автоматизации
Липецкого областного банка

Хронологические данные, временные ряды (time series) - это совокупность значений какой-либо величины, относящихся к различным моментам времени. Задачи, связанные с обработкой временных рядов, возникают в экономике, промышленности, метеорологии, демографиии и во многих других областях, где регулярно производятся одни и те же измерения.

Никакая современная финансовая или хозяйственная система не может обойтись без эффективного хранения и обработки хронологических данных. При больших объемах БД просчеты в проектировании таких данных могут вызвать серьезные проблемы с производительностью. Это может быть вызвано и невозможностью использования эквисоединений, и неопределенными значениями в столбце с датой, и различиями в точности (наличием или отсутствием временной составляющей), и многими другими причинами.

Попробуем оценить несколько возможных вариантов построения приложений на примере такой типичной задачи, как составление Price list. В одной таблице хранится информация о товаре, в другой – цена товара, устанавливаемая в разные моменты времени. Необходимо найти цену товаров на сегодняшний день. Пример, естественно, сильно упрощен, не показаны параметры STORAGE и TABLESPACE, а также другие несущественные детали.

Создадим таблицы для хранения информации о товаре и его цене в разные моменты времени:

CREATE TABLE goods(

article VARCHAR2(30) NOT NULL,

name VARCHAR2(250) NOT NULL,

CONSTRAINT pk_goods PRIMARY KEY(article));

CREATE TABLE price1(

article VARCHAR2(30) NOT NULL,

dat DATE NOT NULL,

price NUMBER NOT NULL,

CONSTRAINT fk_price1_article FOREIGN KEY(article)

REFERENCES goods(article) ON DELETE CASCADE,

CONSTRAINT pk_price1 PRIMARY KEY(article, dat));

Для получения price list выполним запрос1:

SELECT g.name, p.price

FROM test.price1 p, goods g

WHERE g.article = p.article

AND p.dat = (SELECT MAX(dat)

FROM price1

WHERE article = p.article

AND dat <= SYSDATE)

ORDER BY 1;

Explain plan запроса1

SELECT STATEMENT, COST=203,CARDINALITY=256

SORT ORDER BY, COST=203,CARDINALITY=256

FILTER, COST=0, CARDINALITY=0

HASH JOIN, COST=193,CARDINALITY=256

TABLE ACCESS FULL PRICE1,COST=182,CARDINALITY=256

TABLE ACCESS FULL GOODS,COST=10,CARDINALITY=10000

SORT AGGREGATE, COST=0, CARDINALITY=1

FIRST ROW, COST=3, CARDINALITY=19

INDEX RANGE SCAN (MIN/MAX) PK_PRICE1,COST=3,CARDINALITY=19

9981 rows selected in 161,902 seconds

Честно говоря, никакой эффективностью этот запрос не отличается.

Берем с книжной полки запылившуюся книгу классиков жанра [1] и, следуя их советам, добавляем в таблицу цен еще один столбец с датой окончания действия цены. Для соблюдения непротиворечивости границ диапазонов дат и предотвращения “открытых справа” диапазонов используем триггеры БД.

CREATE TABLE price2(

article VARCHAR2(30) NOT NULL,

date_from DATE NOT NULL,

date_to DATE NOT NULL,

price NUMBER NOT NULL,

CONSTRAINT fk_price2_article FOREIGN KEY(article)

REFERENCES goods(article) ON DELETE CASCADE,

CONSTRAINT pk_price2 PRIMARY KEY(article, date_to),

CONSTRAINT price2_date_range CHECK (date_from < date_to));

Преимущества следующего запроса по видоизмененной таблице очевидны: это и большая скорость выполнения, и простота синтаксиса. Запрос2:

SELECT g.name, p.price

FROM price2 p, goods g

WHERE g.article = p.article

AND SYSDATE BETWEEN date_from

AND date_to

ORDER BY 1;

Explain plan запроса2

SELECT STATEMENT, COST=3709,CARDINALITY=181503

SORT ORDER BY, COST=3709,CARDINALITY=181503

HASH JOIN, COST=472,CARDINALITY=181503

TABLE ACCESS FULL GOODS,COST=10,CARDINALITY=10000

TABLE ACCESS FULL PRICE2,COST=231,CARDINALITY=181503

9981 rows selected in 5,257 seconds

Авторы книги [1] не скрывают, что они являются поклонниками процедурного подхода, поэтому предлагают использовать для поиска цены хранимую функцию.

CREATE OR REPLACE FUNCTION price (

p_code IN price2.article%TYPE,

p_date IN DATE)

RETURN NUMBER

CURSOR c_price IS

SELECT price, date_from

FROM price2

WHERE article = p_code

AND date_to > p_date

ORDER BY date_to;

p_price NUMBER;

p_from DATE:=TO_DATE('31124712','DDMMYYYY');

OPEN c_price;

FETCH c_price INTO p_price, p_from;

CLOSE c_price;

IF p_from >= p_date THEN

RETURN 0;

ELSE

RETURN p_price;

END IF;

EXCEPTION WHEN no_data_found

THEN

RETURN 0;

END;

Так будет выглядеть требуемый запрос3 с использованием функции price:

SELECT name, price(article,SYSDATE)

FROM goods

ORDER BY 1;

Explain plan запроса

SELECT STATEMENT, COST=117, CARDINALITY=10000

SORT ORDER BY, COST=117, CARDINALITY=10000

TABLE ACCESS FULL GOODS,COST=10,CARDINALITY=10000

10000 rows selected in 20,319 seconds

Небольшая разница в количестве выбранных строк появилась из-за наличия в таблице товаров без цен. Я думаю, девятнадцать строк не сильно повлияли на объективность эксперимента.

Но как поступить, если по каким-либо причинам мы не можем использовать таблицу с полноценными диапазонами дат. Oracle8i предоставляет нам возможность получать доступ к более чем одной строке таблицы без self-join с помощью аналитических функций LAG и LEAD. Воспользуемся этим для получения правой границы диапазона (в качестве ее значение берем дату - 1 секунда из следующей по дате записи, в случае ее отсутствия используем максимальную дату, как в предыдущем примере):

CREATE OR REPLACE VIEW price3

(article, date_from, date_to, price) AS

SELECT article, dat,

LEAD (dat - 1/24/3600,1,TO_DATE

('31124712','DDMMYYYY'))

OVER (PARTITION BY article ORDER BY dat), price

FROM price1;

Полученное представление заменит нам в запросах таблицу с полноценными диапазонами дат. Запрос4:

SELECT g.name, p.price

FROM price3 p, goods g

WHERE g.article = p.article

AND SYSDATE BETWEEN date_from

AND date_to

ORDER BY 1;

Explain plan запроса4

SELECT STATEMENT, COST=8467,CARDINALITY=254618

SORT ORDER BY, COST=8467,CARDINALITY=254618

MERGE JOIN, COST=2277,CARDINALITY=254618

VIEW PRICE3, COST=2160,CARDINALITY=254618

WINDOW SORT, COST=0,CARDINALITY=254618

TABLE ACCESS FULL PRICE1,COST=182,CARDINALITY=254618

SORT JOIN, COST=117, CARDINALITY=10000

TABLE ACCESS FULL GOODS,COST=10,CARDINALITY=10000

9981 rows selected in 53,877 seconds

Как видим, это чуть лучше, чем наш самый первый вариант, но "TABLE ACCESS FULL PRICE1" на этом количестве строк - операция довольно накладная. Попробуем создать составной индекс на эту таблицу, чтобы "помочь" функции LEAD:

CREATE INDEX price1_idx_001 ON price1 (article, dat, price);

Повторим еще раз запрос4.

Explain plan повторения запроса4

SELECT STATEMENT, COST=7443, CARDINALITY=254618

SORT ORDER BY, COST=7443, CARDINALITY=254618

MERGE JOIN, COST=1253, CARDINALITY=254618

VIEW PRICE3, COST=1136, CARDINALITY=254618

WINDOW BUFFER, COST=0, CARDINALITY=254618

INDEX FULL SCAN PRICE1_IDX_001,COST=4543,CARDINALITY=254618

SORT JOIN, COST=117, CARDINALITY=10000

TABLE ACCESS FULL GOODS,COST=10,CARDINALITY=10000

9981 rows selected in 37,263 seconds

Немного лучше, но это слишком неэффективно - каждый раз заново пересчитывать границы диапазонов.

Во всех предыдущих примерах для хранения хронологических данных мы использовали традиционные таблицы. Внимательно поглядев на последний план выполнения запроса4 и на таблицу price1, можно заметить, что она, мягко говоря, нам не очень нужна, мы вполне можем обойтись ее индексом. Попробуем использовать для данных о ценах индекс-организованную таблицу:

CREATE TABLE price4(

article VARCHAR2(30),

dat DATE,

price NUMBER,

CONSTRAINT pk_price4 PRIMARY KEY (article, dat))

COMPRESS;

Выполним запрос, аналогичный приведенному в пункте 1:

SELECT g.name, p.price

FROM test.price4 p, goods g

WHERE g.article = p.article

AND p.dat = (SELECT MAX(dat)

FROM price4

WHERE article = p.article

AND dat <= SYSDATE)

ORDER BY 1;

Explain plan этого запроса

SELECT STATEMENT, COST=691, CARDINALITY=257

FILTER, COST=0, CARDINALITY=0

HASH JOIN, COST=691, CARDINALITY=257

INDEX FAST FULL SCAN PK_PRICE4, COST=680, CARDINALITY=257

TABLE ACCESS FULL GOODS, COST=10, CARDINALITY=10000

SORT AGGREGATE, COST=0, CARDINALITY=1

FIRST ROW, COST=3, CARDINALITY=19

INDEX RANGE SCAN (MIN/MAX) PK_PRICE4,COST=3,CARDINALITY=19

9981 rows selected in 26,748 seconds

Изменения относительно запроса1 налицо.

А теперь еще раз воспользуемся функцией LEAD для формирования правой границы диапазона:

CREATE OR REPLACE VIEW price5

(article, date_from, date_to, price) AS

SELECT article, dat,

LEAD(dat-1/24/3600,1,TO_DATE('31124712','DDMMYYYY'))

OVER (PARTITION BY article ORDER BY dat), price

FROM price4;

Повторим наш самый простой запрос6:

SELECT g.name, p.price

FROM price5 p, goods g

WHERE g.article = p.article

AND SYSDATE BETWEEN date_from

AND date_to

ORDER BY 1;

Explain plan запроса

SELECT STATEMENT, COST=12975, CARDINALITY=500000

SORT ORDER BY, COST=12975, CARDINALITY=500000

MERGE JOIN, COST=845, CARDINALITY=500000

VIEW PRICE5, COST=723, CARDINALITY=500000

WINDOW BUFFER, COST=0, CARDINALITY=500000

INDEX FULL SCAN PK_PRICE4,COST=2889,CARDINALITY=500000

SORT JOIN, COST=123, CARDINALITY=10000

TABLE ACCESS FULL GOODS,COST=10,CARDINALITY=10000

9981 rows selected in 39,177 seconds

Чем же объяснить столь "потрясающий" результат?

Этот способ получения диапазонов сопряжен с большим количеством операций сортировки, часть из которых могла проводиться (и проводилась) на диске.

Давайте испытаем индекс-таблицы в варианте с полноценным диапазоном дат:

CREATE TABLE price6(

article VARCHAR2(30),

date_from DATE,

date_to DATE,

price NUMBER,

CONSTRAINT pk_price6

PRIMARY KEY (article, date_to))

COMPRESS;

Запрос7:

SELECT g.name, p.price

FROM price6 p, goods g

WHERE g.article = p.article

AND SYSDATE BETWEEN date_from

AND date_to

ORDER BY 1;

Explain plan запроса7

SELECT STATEMENT, COST=3864, CARDINALITY=181302

SORT ORDER BY, COST=3864, CARDINALITY=181302

HASH JOIN, COST=630, CARDINALITY=181302

TABLE ACCESS FULL GOODS, COST=10, CARDINALITY=10000

INDEX FAST FULL SCAN PK_PRICE6,COST=389,

CARDINALITY=181302

Когда я делал тесты для этой статьи с индекс-организованными таблицами, я забыл при создании таблицы указать ключевое слово COMPRESS и никак не мог понять, почему результат оказался чуть хуже, чем при использовании простой таблицы аналогичной структуры.

9981 rows selected in 6,834 seconds (без компрессии)
9981 rows selected in 4,517 seconds (с компрессией ключа)

Чем это было вызвано? Сравним более детально эти запросы:

Несмотря на меньшее количество операций чтения, число прочитанных блоков во втором случае оказалось больше, чем в первом. После анализа таблиц выяснилось, что средняя длина строки (average row length) наших тестовых таблиц - 32, 34 и 26 байт соответственно.

Ну и наконец протестируем работу функции, аналогичной приведенной в запросе3, но обращающейся к индекс-таблице.

10000 rows selected in 13,349 seconds (с компрессией ключа)
10000 rows selected in 15,562 seconds (без компрессии)

Не правда ли, довольно интересный результат, а заодно и повод для разговора о процедурном подходе и SQL:

Вот мы и подтвердили применимость одного старого правила к индекс-организованным таблицам - индексные способы доступа наиболее эффективны при доступе к небольшому количеству записей в таблице.

Следует заметить, что применение индекс-организованных таблиц несколько ограничено:

Все это необходимо учесть перед их применением. В крайнем случае вам никто не мешает конвертировать их в обыкновенные таблицы с помощью предложения CREATE TABLE …AS SELECT… или выполнив следующие действия:

А теперь несколько слов о преимуществах, которые можно извлечь от их применения. Данные строк сохраняются в самом индексе, что обеспечивает быстрый доступ по ключу при запросах как на точное соответствие, так и при диапазонном сканировании. Индекс-организованные таблицы более компактны, нежели обычные вместе со своими индексами, так как столбцы ключа хранятся в единственном экземпляре (нет необходимости дублировать их в индексе) и не требуется хранение ROWID в индексе. А главное, не забывайте про возможность компрессии составных ключей, которая позволяет не хранить повторяющуюся лидирующую часть первичного ключа. На больших объемах данным это может существенно снизить нагрузку на систему ввода/вывода.

Более подробную информацию о индекс-организованных таблицах можно получить из документации Oracle [2] и [3].

Все тестовые примеры выполнялись на Oracle8i Rel.3 (8.1.7) под Microsoft Windows 2000. Табличные пространства для таблиц и индексов были размещены на разных физических дисках. Распределение данных в различных физических структурах одинаково. Количество строк в таблице товаров - 10000, цен - 500000. Тестируемые запросы выполнялись из анонимного блока PL/SQL без вывода на экран.

На этих примерах я попытался показать только несколько вариантов реализации временных данных в базах данных Oracle. Естественно, что возможных способов гораздо больше. Решения фирмы Oracle для OLAP систем - это вообще тема для отдельного разговора.

Павел Шендрыгайлов,
заместитель начальника управления автоматизации
Липецкого областного банка
e:mail: paul@oblbank.lipetsk.ru