Задачи на собеседованиях #213. Задачи от Virtuozzo и награждение победителей от Postgres Professional

В этой рубрике мы публикуем любые сложные и интересные задачи, такие, чтобы даже наши самые матерые читатели (да-да, Иннокентий Сенновский, это про тебя) нашли в них для себя то, над чем можно как следует попотеть. Но особенно мы любим задачи от международных компаний. И это не только потому, что офис Virtuozzo расположен в Сиэтле (и в один прекрасный момент ты сможешь запустить свой трактор в направлении цивилизованного места, где в конце сентября +23 по Цельсию). Международная компания — это еще и новые связи, совсем другой уровень перспектив и возможностей. А поскольку Virtuozzo не так давно отделилась от другой крупной компании — это еще и новые интересные проекты.

Задачи от Virtuozzo

Задание 1

У вас есть программа, простой таймер, запускаемая из командной строки. Программа собрана под libc6 x86_64 linux и должна работать в совместимых по архитектуре дистрибутивах Linux.

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

$ ./timer
10

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

$ ./timer (из одного терминала)
10
$ ./timer (одновременно, из другого терминала)
error!

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

Задание 2

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

Задание 3

Самораспаковывающимся (SFX) архивом называется файл, в состав которого входят как собранные в архивный формат файлы, так и программа в машинных кодах или на интерпретируемом языке, предназначенная для запуска на целевой архитектуре. Выполненный SFX-архив распаковывает содержащиеся в нем файлы в текущую директорию.

Необходимо написать программу-конвертер, которая может автоматически преобразовывать SFX-архивы в RPM-пакет. Предполагается, что SFX-архив будет запускаться в корне файловой системы, а результат установки RPM-пакета должен полностью соответствовать такому запуску, не считая дополнительных изменений rpmdb. Требуется, чтобы сконвертированный пакет содержал уже распакованные файлы, а не сам архив.

В задании приведены два примера SFX-архивов, но программа-конвертер не должна опираться на знание о конкретных форматах архивов.

Ответы на задачи от Postgres Professional

Задача 1

select p.*
  from friend f, lateral(select * post p where p.usr_id=f.friend_id order by p.added desc) p
where f.usr_id=:usr_id
order by p.added desc
limit 10

Нам потребуется индекс post(usr_id,added). Запрос «в лоб»:

select *
  from friend f, post p
where f.usr_id=:usr_id
  and p.usr_id=f.friend_id
order by p.added desc
limit 10

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

Задача 2

Можно ли в строке, состоящей из символов ( и ), проверить баланс скобок? Как?

Очень просто — сначала превратим строку в таблицу:

 select * from (select s.v[1] as v, pos from regexp_matches(')()()()()(','(.)','g') with ordinality as s(v, pos)) t     where t.v in ('(',')')

после чего для каждой открывающей скобки будем выдавать единицу, а для закрывающей — -1. Обрати внимание на предложение with ordinality — оно позволяет получить, кроме собственно значений, еще и их порядковый номер (в данном случае pos). Вообще говоря, даже без этого предложения мы получим корректный результат, и его использование в данном случае почти буквоедство, но кто знает, как в будущем станут возвращаться строки?

Посчитаем промежуточные суммы для этого выражения:

select sum(case v when '(' then 1 else -1 end)over(order by pos) as r, pos  from tokens order by pos

(tokens — имя таблицы со скобками).

Понятно, что для корректной последовательности скобок, во-первых, число закрывающих скобок должно быть равно числу открывающих и, во-вторых, слева от любой закрывающей скобки число открывающих скобок должно быть не меньше, чем число закрывающих – 1; то есть рассматривается случай ')(' и подобные.
Соберем все вместе:

with tokens as(
    select * from (select s.v[1] as v, pos from regexp_matches(')()()()()(','(.)','g') with ordinality as s(v, pos)) t where t.v in ('(',')')
),
rt as(
        select sum(case v when '(' then 1 else -1 end)over(order by pos) as r, pos  from tokens order by pos
)
    select case when (select rt.r from rt order by pos desc fetch first 1 rows only)=0
                 and not exists(select * from rt where rt.r<0)
                then true
                else false
           end

Кстати, интересное решение предложил один из читателей (из строки предварительно удаляются все символы, отличные от ( и ):

RETURN CASE WHEN EXISTS (
        WITH RECURSIVE a AS (
            SELECT regexp_replace(str, '()', '') rep
            UNION ALL
            SELECT regexp_replace(rep, '()', '') FROM a WHERE rep ~ '()'
        )
        SELECT * FROM a WHERE rep = ''
    ) THEN true ELSE false END;

В нем он удаляет все пары '()' до тех пор, пока они встречаются; если получилась пустая строка, то баланс скобок соблюден.

Задача 3

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

Задача 4

При вставке строки в такую схему накладывается блокировка FOR KEY SHARE; она подобна блокировке FOR SHARE, за тем исключением, что блокируются только колонки, входящие в первичный ключ / ограничение уникальности.

Задача 5

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

Задача 6

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

create or replace function tusrupdate(id int, name text) returns void as
$code$
declare
 temp int;
begin
  loop
    begin
        with upd as(
          update tusr tu set name=tusrupdate.name where tu.id=tusrupdate.id returning 1
        ),
        ins as(
          insert into tusr(id,name)
          select tusrupdate.id, tusrupdate.name
          where not exists(select * from upd)
          returning 2
        )
        select 1 into temp from ins;
        exit;
    exception
      when unique_violation then
        continue;
    end;
   end loop;
end;
$code$
language plpgsql

Также можно использовать конструкцию insert ... on conflict(...) do update;. К сожалению, это не всегда срабатывает — при наличии более одного ограничения уникальности (например, primary key и unique) могут также возникать ошибки с нарушением уникальности; впрочем, описанный подход должен работать и в таком случае.

Задача 7

Триггер некорректен сразу по нескольким причинам.

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

Во-вторых, если триггер создан как триггер before, то он должен вернуть какое-то значение (обычно new для добавления/обновления строки или null, если операции со строкой требуется пропустить).

Однако нередко возникает задача обеспечить уникальность сразу в нескольких таблицах — например, колонка id должна быть уникальна как в таблице t1, так и в таблице t2. В таком случае можно предложить использовать advisory-блокировки и перед проверкой блокировать значение id, например так:

create or replace function check_uniq() returns trigger as
    $code$
    begin
     if pg_advisory_xact_lock(10000, new.col) then
      if exists (select * from tbl1 t where t.col=new.col) then
        raise exception 'Unique violation';
      end if;
      if exists (select * from tbl2 t where t.col=new.col) then
        raise exception 'Unique violation';
      end if;
     end if;
    end;
    $code$
Language plpgsql

Хотелось бы обратить внимание на то, что используется функция pg_advisory_xact_lock, то есть блокировка будет снята при окончании транзакции и потому нет опасности случайно забыть снять блокировку.

Кроме того, если триггер выше подходит для случая вставки в таблицу, то для обновления его следует модифицировать (примечание: предполагается, что колонка col имеет тип int; значение 10000 в вызове функции pg_advisory_xact_lock взято для примера).

Задача 8

Блок выдаст значение ER000, потому что sqlstate, заканчивающийся на 000, определяет не ошибку, а класс ошибок и потому может обрабатывать ошибки и ER001. Кроме того, при возникновении исключения обработчики исключения просматриваются сверху вниз и используется первый подходящий. Конечно, обработка исключений в PL/pgSQL далека, скажем, от Java, но в то же время предоставляет довольно широкие возможности — с ошибкой можно установить многие дополнительные параметры, получить стек вызовов.

Следует также отметить, что с помощью работы с исключительными ситуациями в PL/pgSQL организована работа с точками сохранения (savepoints).