Delphi Notes Робота з n-арними деревами на PL
Нотатки Delphi + Oracle програміста
Робота з n-арними деревами на PL/SQL
Уявіть собі майже класичну ситуацію: є якісь дані в БД (одна, дві і більше таблиць), і треба ці дані обробити хитрим чином, а потім зберегти результат окрему таблицю для подальшого представлення даних користувачу.
Вибирати дані на клієнтський додаток, обробляти локально, а потім зберігати результат назад у БД – законом не забороняється, але не раціонально. Причому що більше обсяг вихідних даних, то більше вписувалося потрібен час просто вибірку даних. Тому будь-які завдання, пов'язані з обробкою даних, краще вирішувати на стороні сервера.
Припустимо, що в процесі обробки даних нам необхідно побудувати дерево.
На Delphi структуру вузла дерева можна описати так:
Процедура створення вузла дерева в цьому випадку може бути такою:
Та й процедура перебору всіх дочірніх вузлів:
Думаю, наведеного коду достатньо, щоб зрозуміти, про що йдеться.
Тепер спробуємо зробити щось на стороні сервера.
Інтерпретована мова PL/SQL, що використовується в СУБД Oracle, дуже потужний засіб в умілих руках. Однак він має низку неприємних обмежень. Наприклад, у PL/SQL немає покажчиків, а тому й не можна посилатися на типи даних, які ще не оголошені (або оголошені за кодом нижче). Тому, якщо написати так:
то отримаємо помилку під час компіляції. Та й не зрозуміло, як послатись на батьківську ноду?
Зіткнувшись з такою проблемою, я вже хотів вирішити поставлене завдання з використанням об'єктів. Але об'єкт у Oracle – це тип SQL, а логіку обробки даних треба реалізовувати у PL/SQL, а звідси є деякі неприємні моменти. Наприклад, не всі типи данихPL/SQL можна використовувати в SQL. Та й робота з об'єктами відбувається повільніше, ніж із PL/SQL масивами (колекціями).
Таким чином, структуру даних на PL/SQL можна описати так:
Тут варто звернути увагу на:
- g_nodes – це колекція вузлів, оголошена як index by pls_integer, це означає, що g_nodes окремо не потрібно ініціалізувати.
- g_nodes_seq - це лічильник вузлів, збережених в g_nodes, за великим рахунком можна обійтися і без нього, але він потрібний для зручності.
- p_root_node – індекс, яким буде зберігатися корінь дерева.
Тепер для побудови дерева нам знадобляться такі функції:
Думаю, тут все зрозуміло: дерево починаємо будувати із кореня (create_root), потім створюємо вузли (create_node).
Ітерація дерева робиться так:
Ну, загалом приблизно так. Трохи громіздко вийшло, але працює та працює досить швидко.
Якщо навігація “вгору” від вузла не потрібно, можна спростити опис структури t_node.
Навіщо такий гемор. Не простіше в процесі обробки зберігати дані в тимчасову таблицю #TEMP(ID, ParID, . ). І на сервері простіше (у того ж оракла є SQL для бігу по деревах) і на клієнті (якщо використовувати гриди типу EhLib або DevEx вони самі будують дерева)
Проще воно простіше. Тільки кешування ієрархічної структури в оперативній пам'яті для подальшої обробки підвищує швидкість обробки даних на 1-2 порядку (це залежить від обсягу оброблюваних даних, чим більше даних - тим помітніша різниця).
Тут фокус у тому, що вставки в таблиці, та й взагалі SQL оператори працюють повільніше, ніж вся маніпуляція з даними оперативної пам'яті.
Напевно, все-таки треба живий приклад. я подумаю над прикладом (нехочеться брати приклад із комерційного проекту). Тоді буде зрозуміло, що завантажувати дані на клієнт для обробки – вкрай марнотратно.
Коли я писав про приріст продуктивності на 1-2 порядку - я робив тести з відносно невеликими обсягами даних (відпрацьовував за 22 секунди проти
Зараз я одержав результат за всіма даними. вже записів може бути менше, але з вузлами другого дерева зберігаються додаткові дані з інших таблиць), і далі йде спільна робота з двома деревами - результат роботи ітерації зберігається в таблицю (т.к. боюся, що ВП може просто не вистачити і почне використовуватися файл підкачування), робиться commit (щоб RBS не переповнився), друге дерево вбивається -> наступна ітерація - знову проходжу по першому дереву. ну втім там ще три етапи.
Після всього цього користувачу доступний результат - крос таблиця, в БД це 2411695 записів, на екрані - 37103 рядків і (65 * 2 + 2 =) 132 стовпця.
Алгоритм з деревами в пам'яті відпрацював за 113 хвилин (причому найповільнішими операціями виявилися вставки в таблиці; дерево в пам'яті розгортається за пару секунд). на роботу я побачив, що вона ще працює.
У вашому конкретному випадку, ваші конструкції однозначно краще. Але якщо ваш сервак використовують не тільки Ви один, а купа народу і кожен оперує такими об'ємами. Адже пам'ять не гумова, а диск напевно можна сказати що "гумовий".
Юрію, такими обсягами оперують не "купа народу", а один сервер. А ось "купанароду" вже працює з результатами проведених обчислень, роблячи запити до цього результату з додатковими умовами (щоб не витягувати на клієнт усі 2.5 млн записів. хоча ніхто їм цього не забороняє).
Можливо, я не дуже зрозуміло викладаю свої думки, навіщо це все робилося. почитайте літературу щодо OLAP.
а аналітика чим не вгадала? select .. start with .. connect by ..
start with – штука класна. Але тут фішка в тому, що якщо відкрити курсор і, рухаючись по ньому, робити підзапити (ну таке у мене завдання, причому підзапити працюють з тими ж даними, за якими будується основний селект) - це буде працювати дуже повільно. підзапитів також можна, тобто. із використанням аналітичних функцій. Тільки практика показала, що аналітика не набагато швидше працює, т.к. по суті, все зводиться до тих же підзапитів, які відпрацьовують за кадром.
А ось якщо зробити select BULK COLLECT INTO, а потім по цьому масиву побудувати дерево – це працює у рази швидше.