Задачи на собеседованиях - Награждение победителя от Postgres Professional
Два месяца назад наша компания делилась с читателями сайта www.xakep.ru подборкой задач для конкурса «Задачи на собеседованиях». Сегодня мы подводим итоги этого состязания и награждаем победителя.
Награждение победителя
Лучше всех с решением задач от Postgres Professional справился Андрей Асякин. Он крутой, поздравляем победителя! Андрей получает бесплатный билет на все три дня международного форума PgConf.Russia, который Postgres Professional будет проводить 15–17 марта 2017 года в Москве.
Ответы на задачи от 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).
IT-компании, шлите нам свои задачки!
Миссия этой мини-рубрики — образовательная, поэтому мы бесплатно публикуем качественные задачки, которые различные компании предлагают соискателям. Вы шлете задачки — мы их публикуем. Никаких актов, договоров, экспертиз и отчетностей. Читателям — задачки, решателям — подарки, вам — респект от нашей многосоттысячной аудитории, пиарщикам — строчки отчетности по публикациям в топовом компьютерном журнале.
Александр Лозовский : lozovsky@glc.ru
Исходная публикация: «ХАКЕР»
от 06.10.2016
Александр Лозовский