egorius: (Default)

Давеча фейсбук подсунул рекламу, которую я не только не скрыл незамедлительно, но и — первый раз такое! — с интересом посмотрел. Это был университет бесполезных знаний, а в особенности меня, конечно, заинтересовали «бесполезные языки программирования».

Одна из статей там посвящена написанию игры Жизнь на APL в одну строчку. Если — вдруг — вы еще не знаете, что такое Жизнь, сошлюсь на другую статью на том же сайте — она написана интересно, с картинками и интригующими подробностями про Машину Тьюринга.

Окей, вполне допускаю, что APL — это хорошо, но зачем, когда у нас есть SQL?

Только вместо Oracle на этот раз я буду использовать PostgreSQL — времена меняются.

поехали )

Django

Jan. 7th, 2016 11:58 pm
egorius: (Default)

Вопрос о том, держать ли логику работы с данными в базе или в приложении, делит мир на два лагеря.

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

Во втором — превыше всего приложение, чудесное, высокотехнологичное, в которое пользователи влюбляются с первого клика. Конечно, оно использует данные, так что следует вооружиться ORM-ом и пусть какая-нибудь СУБД обеспечивает персистентность.

Сам я всегда принадлежал (и принадлежу) первому лагерю, но интересно же посмотреть, как другие живут. Поэтому из любопытства поковырял немного Django — на StackOverflow периодически попадаются вопросы типа Как бы мне сделать то-то и то-то, имеющие понятный ответ на SQL.

Занудно про работу Django с базой )
egorius: (Default)

Иерархии традиционно вызывают много вопросов. Обычно довольно простых, например, связанных с порядком выполнения частей запроса, особенно когда иерархия строится над несколькими таблицами. Но встречаются задачи и поинтереснее.

Предметная область состоит из сотрудников, каждый из которых работает в некотором отделе. Отделы образуют оргструктуру, то есть иерархию. Некоторым (но не всем) отделам приписан адрес.

      1   <-- адрес A
     / \
    2   3   <-- адрес B
       / \
      4   5   <-- адрес C

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

Например, для картинки выше, адреса отделов должны быть такими:

DEP_ID ADDRESS 
------ ------- 
     1 A       
     2 A       
     3 B       
     4 B       
     5 C       

Задача состоит в написании запроса, который выведет всех сотрудников с указанием их отделов и адресов.

Вот тестовые данные.

create table dep(
  id        number primary key,
  address   varchar2(1000)
);
create table dep_hier(
  parent_id references dep(id),
  child_id  references dep(id)
);
create table emp(
  id        number primary key,
  dep_id    number references dep(id)
);
insert into dep values(1, 'A');
insert into dep values(2, '');
insert into dep values(3, 'B');
insert into dep values(4, '');
insert into dep values(5, 'C');
insert into dep_hier values(1, 2);
insert into dep_hier values(1, 3);
insert into dep_hier values(3, 4);
insert into dep_hier values(3, 5);
insert into emp values(101, 1);
insert into emp values(102, 2);
insert into emp values(103, 3);
insert into emp values(104, 4);
insert into emp values(105, 5);
commit;

Поехали )

egorius: (Default)

Нередки случаи, когда сама постановка задачи подталкивает разработчика к процедурному решению. Вот пример из практики. В кадровый отчет по сотруднику требуется выводить тип родства, ФИО и дату рождения ближайшего родственника (например: «Отец — Эпиктетов Полуэкт Полуэктович, 01.04.1900»).

Модель данных упрощенно выглядит следующим образом. Есть таблица people с информацией о людях (как сотрудниках, так и их родственниках):

create table people(
  person_id         number,
  employee_flag     varchar2(1) check(   employee_flag = 'Y' -- yes
                                      or employee_flag = 'N' -- no
                                     ),
  full_name         varchar2(240),
  marital_status    varchar2(1) check(   marital_status = 'M' -- married (or null)
                                     ),
  sex               varchar2(1) check(   sex = 'M' -- male
                                      or sex = 'F' -- female
                                     ),
  date_of_birth     date
);

И есть таблица, связывающая людей с родственниками (связь односторонняя):

create table contact_relationships(
  person_id         number,
  contact_person_id number,
  contact_type      varchar2(1) check(   contact_type = 'C' -- child
                                      or contact_type = 'P' -- parent
                                      or contact_type = 'S' -- spouse
                                     ) 
);

Поскольку в системе может быть зарегистрировано много родственников, нужно определить, кто из них считается ближайшим. Вот что говорит на этот счет тех. задание:

Если в поле «Статус» = Состоит в зарегистрированном браке и Отношение = Супруг(а), то выводить данные супруга\супруги.
Если в поле «Статус» значение отличное от значения «Состоит в зарегистрированном браке», то выводим в отчет родственника в зависимости от приоритета.
Сначала проверяется наличие детей (Тип отношения = ребенок), причем если детей несколько, то выводить самого старшего.
Если детей нет, то выводить мать (тип отношения = родитель, пол = жен.)
Если матери нет, то выводить отца (тип отношения = родитель, пол = муж.).

Алгоритм определения ближайшего родственника сформулирован в терминах «если-то» и напрашивается процедурное решение. Напишем функцию, получающую person_id сотрудника и возвращающую... что? Логично было бы вернуть запись из трех полей (тип родства, ФИО и дата рождения), но что с ней потом делать в запросе? Можно написать три отдельных функции, а чтобы не ухудшать в три раза производительность, приделать кэширование. Но не будем усложнять: пусть функция будет одна и пусть она возвращает конкатенацию полей. Она могла бы выглядеть следующим образом:

запасаемся тухлыми помидорами )
egorius: (Default)

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

Для наглядности возьмем что-нибудь совсем тривиальное. Например, распределим общие затраты (расходы на электроэнергию) на все подразделения компании пропорционально их численности:

with depts(dept_id, quantity) as (
  select 1, 300 from dual union all
  select 2, 300 from dual union all
  select 3, 100 from dual union all
  select 4, 100 from dual union all
  select 5, 100 from dual
),
expenditures(amount) as (
  select 1000 from dual
),
report(dept_id,amount) as( 
  select   d.dept_id,
           e.amount * ratio_to_report(d.quantity) over ()
  from     depts d,
           expenditures e
)
select   dept_id,
         round(amount,2) amount
from     report;

DEPT_ID AMOUNT 
------- ------ 
      1 333,33 
      2 333,33 
      3 111,11 
      4 111,11 
      5 111,11

Какая досада, копеечка-то потерялась! Бухгалтер, работающий с РСБУ, этого не переживет.

Чтобы получилось правильно, надо учесть ошибки округления. Обычно их собирают вместе и добавляют к строке с максимальной суммой.

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

declare
  total     number;
  new_total number;
  max_dept  number;
begin
  select   round(sum(amount),2)
  into     total
  from     tmp;

  update   tmp
  set      amount = round(amount,2);
  
  select   sum(amount)
  into     new_total
  from     tmp;

  if total = new_total then
    return;
  end if;

  select   dept_id
  into     max_dept
  from     tmp
  where    amount = (
             select max(amount) from tmp
           )
       and rownum = 1;
       
  update   tmp
  set      amount = amount + total - new_total
  where    dept_id = max_dept;
end;
/

А одной командой SQL? )
egorius: (Default)

Посмотрим на пример из жизни. В разных вариациях он встречался мне раза три как минимум.

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

  • собственно позиция (item_id) — стол офисный, кадка с фикусом и т. п.
  • стоимость одной штуки (cost)
  • количество штук (quantity) — положительно для поступлений, отрицательно для выбытий
  • дата (trx_date)

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

Задача: написать отчет, показывающий стоимость наличных остатков каждой позиции. За неимением реальной информации о выбытиях считать, что позиции уходят со склада в порядке FIFO.

На примере (для одной позиции):

  1. Поступление 5 штук по цене 1001 руб.
  2. Поступление 4 штук по цене 1010 руб.
  3. Выбытие 3 штук
    ценапоступиловыбылоосталось
    1001532
    1010404
  4. Выбытие 3 штук
    ценапоступиловыбылоосталось
    100153+20
    1010413
  5. Поступление 2 штук по цене 1100 руб.
    ценапоступиловыбылоосталось
    100153+20
    1010413
    1100202

Итак, отчет должен показать 3×1010 + 2×1100 = 5230.

Лирическое отступление. Числа в примерах лучше подбирать так, чтобы по результату можно было сразу сказать, откуда он взялся. 5230 читается справа налево: осталось 0 от первого поступления, 3 от второго и 2 от третьего, 5 — контрольная цифра. А вот попробуйте понять, что такое 2000 при цене поступлений 1000 и 500.

Процедурное решение вполне очевидно. Например, можно сделать так:

create table transactions(
  item_id     number,
  quantity    number,
  cost        number,
  trx_date    date
);

create or replace type trx_rec is object(
  item_id     number,
  quantity    number,
  cost        number
);
/
create or replace type trx_tab is table of trx_rec;
/

-- транзакции из примера
insert into transactions values(1, +5, 1001, to_date('01.02.2014','DD.MM.YYYY'));
insert into transactions values(1, +4, 1010, to_date('02.02.2014','DD.MM.YYYY'));
insert into transactions values(1, -3, null, to_date('05.02.2014','DD.MM.YYYY'));
insert into transactions values(1, -3, null, to_date('07.02.2014','DD.MM.YYYY'));
insert into transactions values(1, +2, 1100, to_date('09.02.2014','DD.MM.YYYY'));
-- добавим еще вторую позицию
insert into transactions values(2, +3,  300, to_date('03.02.2014','DD.MM.YYYY'));
insert into transactions values(2, -1, null, to_date('04.02.2014','DD.MM.YYYY'));

set serveroutput on
declare
  trx trx_tab := trx_tab();
  qty_so_far number;
begin
  -- читаем поступления в массив (в порядке дат)
  for i in (
    select   t.item_id,
             t.quantity,
             t.cost
    from     transactions t
    where    t.cost is not null
    order by t.trx_date
  )
  loop
    trx.extend;
    trx(trx.count) := trx_rec(i.item_id, i.quantity, i.cost);
  end loop;
  -- обработка выдач
  for i in (
    select   t.item_id,
             sum(t.quantity) quantity
    from     transactions t
    where    t.cost is null
    group by t.item_id
  )
  loop
    qty_so_far := -i.quantity;
    for n in 1 .. trx.count loop
      if trx(n).item_id = i.item_id and trx(n).quantity > 0 then
        if trx(n).quantity >= qty_so_far then
          trx(n).quantity := trx(n).quantity - qty_so_far;
          exit;
        else
          qty_so_far := qty_so_far - trx(n).quantity;
          trx(n).quantity := 0;
        end if;
      end if;
    end loop;
  end loop;
  -- результат
  for i in (
    select   t.item_id,
             sum(t.cost * t.quantity) cost
    from     table(trx) t
    group by t.item_id
    order by t.item_id
  )
  loop
    dbms_output.put_line(i.item_id||': '||i.cost);
  end loop;
end;
/

Небольшая оптимизация состоит в том, чтобы списывать сразу общую сумму, а не возиться с каждым выбытием отдельно. Чтобы не засорять код сверх меры, я все-таки перепоручил заключительную часть — группировку сумм по позициям  — SQL, обратившись к коллекции как к таблице (select from table()).

А как сделать на чистом SQL? )
egorius: (Default)

А вот попробуем решить на SQL какую-нибудь типично процедурную задачу. Скажем, поиск пути в лабиринте, чтобы было не скучно.

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

Как подойти к проблеме с реляционной стороны? Во-первых, лабиринт надо представить так, как мы делали в прошлый раз с матрицей: в виде отношения, содержащего номер строки, номер столбца и значение в ячейке.

create table maze_relation(
  linenum number,
  colnum  number,
  cell    varchar2(1)
    check(   cell = ' ' -- пусто
          or cell = '#' -- стена
          or cell = 's' -- начало
          or cell = 'e' -- конец
         )
);

Залог успеха — формулировка решения в терминах множеств. Итак, начинаем с множества начальных ячеек. Далее действуем рекурсивно: на каждом следующем этапе добавляем ячейки, соседствующие с уже имеющимися в множестве. Из полученных вариантов нас будет интересовать тот, в котором содержится конечная ячейка, и у которого наименьшая длина пути.

Такого рода рекурсивные алгоритмы прекрасно соответствуют иерархическим запросам SQL. Условия первой итерации попадают во фразу start with, условия следующих итераций — в connect by (с указанием nocycle, чтобы алгоритм не ходил кругами). Отбор подходящих вариантов задается в where. Восстановление пути волнового алгоритма превращется в простой вызов функции sys_connect_by_path: если представить иерархический запрос как рекурсивный алгоритм, то эта функция возвращает не что иное, как стек возвратов.

with solutions as (
  select  sys_connect_by_path(m.linenum||','||m.colnum,' - ') path,
          level len
  from    maze_relation m
  where   m.cell = 'e'
  start with
          m.cell = 's'
  connect by nocycle
          m.cell != '#'
      and (
            (m.linenum = prior m.linenum + 1 and m.colnum = prior m.colnum) or
            (m.linenum = prior m.linenum - 1 and m.colnum = prior m.colnum) or
            (m.linenum = prior m.linenum     and m.colnum = prior m.colnum + 1) or
            (m.linenum = prior m.linenum     and m.colnum = prior m.colnum - 1)
          )
)
select  min (path) keep (dense_rank first order by len)
from    solutions;

Получив в подзапросе solutions все пути, мы отобраем из них самый короткий. Это можно сделать с подзапросом, а можно воспользоваться keep dense_rank. Смысл конструкции, изрядно затуманенный синтаксисом, прост: отобрать значение path, соответствующее минимальному значению len (если таких будет несколько, останется только одно благодаря min).

Собственно, все. По-моему, весьма поучительно сравнить объем кода с тем же волновым алгоритмом.

Естественно, простота решения не дается даром: в жертву приносится эффективность. За эффективность SQL, то есть за выбор конкретного алгоритма, отвечает оптимизатор. В свое время не верили в то, что оптимизатор может составить конкуренцию программе, написанной вручную (а еще раньше не верили в то, что языки програмирования высокого уровня смогут составить конкуренцию ассемблеру), но, охотно признаю: глупо рассчитывать на то, что оптимизатор найдет эффективное решение совершенно нетипичной для баз данных задачи.

Зато наше решение спокойно работает и в случае нескольких точек входа и выхода. Попробуйте-ка изменить волновой алгоритм, чтобы он позволял такое.

Но развлекаться — так развлекаться. Давайте сделаем решение этой задачи наглядным!

продолжаем разговор )
egorius: (Default)

Часто приходится видеть, как разработчик, столкнувшись с задачей, первым делом берется за привычный процедурный инструмент, даже не вспомнив про мантру Кайта:

You should do it in a single SQL statement if at all possible.

Откуда такая мантра? Во-первых, процедурный подход оперирует циклами, а SQL — множествами. База данных может работать с множествами на порядок эффективнее, чем с помощью циклов; это лишь один способ из целого арсенала, которым располагает СУБД. Во-вторых, декларативный подход описывает желаемый результат, а процедурный — точный способ достижения этого результата. Поэтому декларативная программа зачастую оказывается короче и проще.

Почему же предпочтение отдается PL/SQL? Тут можно было бы порассуждать об эффективности, но, на мой взгляд, реальная причина проще: декларативный подход требует смены парадигмы программирования, а это дается нелегко.

Хочу начать эту серию заметок с простого примера, эффективно взрывающего процедурно настроенный мозг, а именно с умножения матриц.

Напомню, что произведением матрицы A(L×M) на матрицу B(M×N) является матрица С(L×N), элементы которой ci,j = Σk = 1...M  ai,k×bk,j. Для иллюстрации процедурного подхода возьмем следующие определения (я использовал язык Си):

int a[L][M];
int b[M][N];
int c[L][N];

Алгоритм традиционен и хорошо иллюстрирует вышеизложенную мысль про циклы:

int i, j, k;
for (i=0; i<L; i++)
  for (j=0; j<N; j++)
    for (k=0; k<M; k++)
      c[i][j] += a[i][k] * b[k][j];

А сможете ли вы сделать это на SQL? )
egorius: (Default)

Наблюдаю интересную картину: абсолютное большинство отчётов и программ под Oracle Applications написано не в декларативном SQL-стиле, а в традиционном процедурном стиле PL/SQL. Даже родные оракловые пакеты этим грешат.

А между тем, это чревато потерей производительности, причём иногда совершенно катастрофической. Беглый взгляд в трассу (как в историю болезни), внедрение всей развесистой «программной логики» внутрь SQL-запроса, и — о чудо! — всё работает в сотню-другую раз быстрее. Почему? А вот почитайте, написал статью на эту тему.

SQL или PL/SQL? — взгляд с точки зрения производительности.

Profile

egorius: (Default)
egorius

March 2025

M T W T F S S
      1 2
34 567 89
1011 121314 1516
17181920212223
24252627 28 29 30
31      

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated May. 13th, 2025 09:50 am
Powered by Dreamwidth Studios