Кто ходил на собеседования по устройству на работу, тот знает, спрашивают там всякое и странное. Нередко можно встретить задачу по нахождению сотрудников с максимальной зарплатой в отделе. Причем ваш потенциальный начальник считает, что у этой задачи есть только одно «правильное решение», то, про которое он прочитал в Интернете. Так ли это?
Постановка задачи
Разумеется ваш потенциальный начальник не придумывал ни эту задачу, ни её решение. И задачу и «правильный» ответ он подглядел в Интернете, чтобы демонстрировать своё ментальное превосходство. Мол он эту задачу решил бы «правильно» за секунды, тоже самое должен сделать и потенциальный сотрудник. Я пытался прогуглить корень зла. Ссылки меня привели к статье.
Это рекомендации по приёму сотрудников в компанию JitBit, в которой описываются примеры вопросов, а также правильное поведение того человека, который проводит собеседование. Отдельно хочу отметить цитату.
And there's more than one correct solution for each of these questions.
Другими словами правильных решений тут больше одного. Там несколько задач, но эта статья только про одну из них. Задача формулируется так. Есть база данных, где содержится информация о сотрудниках, зарплатах и разбиению их по отделам.
CREATE TABLE departments (
department_id integer PRIMARY KEY,
name text NOT NULL
);
CREATE TABLE employees (
employee_id integer PRIMARY KEY,
department_id integer NOT NULL REFERENCES departments(department_id),
name text NOT NULL,
salary money NOT NULL
);Необходимо получить список сотрудников получающих максимальную зарплату в отделе.
Select employees who have the biggest salary in their departments
Иногда дополняют, что название отдела нужно получить тоже, но в этом ничего сложного или необычного нет, для простоты изложения, буду решать без этого.
Варианты решений
Полагаю их может быть множество. Первое, что приходит в голову, решать так, как я её решал всю свою молодость, когда оконных функций в PostgreSQL еще не было.
SELECT name AS employee, salary
FROM (
SELECT department_id, max(salary) AS salary
FROM employees
GROUP BY department_id
) AS m
JOIN employees AS e USING (department_id, salary);Вполне рабочий вариант, но потенциальный начальник хочет большего, он же уверил, что крутые специалисты тут же напишут крутой «правильный» ответ из интернета. Он начинает подсказывать, что нужно использовать оконные функции. И второй вариант, что тут же приходит в голову за отведённые секунды, это сделать тоже самое, но через оконные функции.
SELECT name AS employee, salary
FROM (
SELECT name, salary, max(salary) OVER (PARTITION BY department_id) AS ms
FROM employees
) AS e
WHERE salary=ms;Но и это не то. Откуда ваш потенциальный начальник взял, что существует только один «правильный» крутой ответ? И он вовсе не тот, который предлагает потенциальный сотрудник? Например отсюда.
По-видимому эта задача на собеседовании стала популярной не только в нашей стране. Популярна настолько, что её обсуждают в Stack Overflow. И там авторитетный крутой гуру (за него проголосовало целых 6 человек), утверждает, что самый крутой способ решит эту задачу использовать функцию rank(). Именно этого и ждут от вас на собеседовании:
SELECT name AS employee, salary
FROM (
SELECT name, salary, rank() OVER (PARTITION BY department_id ORDER BY salary DESC)
AS rnk FROM employees e
) AS e
WHERE rnk=1;Если вы не предложите это решение, то вас на работу не возьмут.
Ну, а если подумать? Rank() довольно тяжелая в плане потребления вычислительных мощностей функция созданная для несколько других задач. Будет ли это решение и правда самым лучшим?
Представим что вы работаете в крупной компании: 2000 сотрудников разбитых по 20 подразделениям. У вас реальная, не учебная, задача, получить список сотрудников с максимальным зарплатам по отделам. И вам очень важно решить её так, чтобы она выполнялась максимально эффективно. Зачем? Ну например, чтобы показать своему начальству что ты лучший, ты эффективен как никогда, всё делаешь наилучшим образом и достоин повышения в зарплате.
Среда тестирования
DDL для создания таблиц с сотрудниками я привел выше, нужно добавить таблицу для хранения результатов замеров.
CREATE TABLE results (
method text NOT NULL, -- название метода
start timestamptz NOT NULL, -- время начала теста
finish timestamptz NOT NULL, -- время завершения
execution_time real NOT NULL -- время выполнения по данным EXPLAIN ANALYZE
);Заполнить данными о сотрудниках.
INSERT INTO departments (department_id, name)
SELECT generate_series(0,19), random()::text;
INSERT INTO employees (employee_id, department_id, salary, name)
SELECT id AS employee_id, id/100 AS department_id,
rnd::numeric::money AS salary, rnd::text AS name
FROM (SELECT gs, random()*300000 FROM generate_series(0,1999) AS gs) AS t(id,rnd);И провести тестирование.
DO $do$
DECLARE
start_ timestamptz;
finish_ timestamptz;
execution_time_ real;
explain text; -- вывод EXPLAIN
methods CONSTANT text[] := ARRAY['max', 'window', 'rank'];
method_query CONSTANT text[] := ARRAY[
'EXPLAIN ANALYZE SELECT name AS employee, salary FROM (SELECT department_id, max(salary) AS salary FROM employees GROUP BY department_id) AS m JOIN employees AS e USING (department_id, salary)',
'EXPLAIN ANALYZE SELECT name AS employee, salary FROM (SELECT name, salary, max(salary) OVER (PARTITION BY department_id) AS ms FROM employees) AS e WHERE salary=ms',
'EXPLAIN ANALYZE SELECT name AS employee, salary FROM (SELECT name, salary, rank() OVER (PARTITION BY department_id ORDER BY salary DESC) AS rnk FROM employees e) AS e WHERE rnk=1'
];
BEGIN
PERFORM * FROM employees; -- warm cache
FOR j in 1..1000 LOOP FOR m IN 1..array_length(methods, 1) LOOP
start_ := clock_timestamp();
-- будет работать только в английской локализации lc_messages
FOR explain IN EXECUTE method_query[m] LOOP
IF starts_with(explain, 'Execution Time:')
THEN execution_time_ := substring(explain FROM 'Execution Time: ([.0-9]*) ms')::real; END IF;
END LOOP;
finish_ := clock_timestamp();
INSERT INTO results (method, start, finish, execution_time)
VALUES (methods[m], start_, finish_, execution_time_);
END LOOP;
END LOOP;
END; $do$;Для того чтобы получить максимальную точность в этом вопросе, делаю 1000 серий измерений.
Результаты тестирования
Конечно, раз уж нужно заморочиться с производительностью, то речь должна будет идти о создании индекса и индексировании запроса. Но, давайте из научного любопытства, первый эксперимент сделаем без индексов.
test=# select method, avg(execution_time) as execution_time
from results group by method;
method | execution_time
--------+-------------------
max | 98.34957398986816
rank | 51.50633999633789
window | 46.65021300888061
(3 строки)И мы видим, что даже здесь «правильное» и «крутое» решение задачи, которое знает потенциальный начальник, не самое лучшее.
Но поскольку мы считаем себя высококвалифицированными специалистами, мы задумаемся об индексе. Кажется, что этот индекс будет неплохим вариантом:
CREATE INDEX ds1 ON employees (department_id, salary);Сначала по дереву дойти до отдела, а потом, пользуясь тем, что у btree двунаправленная структура прочитать с «правого конца» максимальную зарплату. Но догадается ли так сделать PostgreSQL? Результаты тестов.
method | execution_time
--------+---------------------
max | 0.24314399652183055
rank | 0.8777229990959168
window | 0.8027530006766319Хм, «правильное и крутое» решение даёт самый худший результат по времени. Неужели наш потенциальный начальник настолько глуп, что на работу возьмёт только тех кандидатов, которые предложат самое худшее решение из всех возможных?
Но поскольку мы не начальники, а технические специалисты, свою правоту доказываем не «уверенностью в голосе», а техническими деталями. Давайте разбираться, что там происходит.
test=# EXPLAIN (COSTS false) SELECT name AS employee, salary
FROM (
SELECT department_id, max(salary) AS salary
FROM employees
GROUP BY department_id
) AS m
JOIN employees AS e USING (department_id, salary);
QUERY PLAN
--------------------------------------------------------------------------------------------------------
Nested Loop
-> GroupAggregate
Group Key: employees.department_id
-> Index Only Scan using ds1 on employees
-> Index Scan using ds1 on employees e
Index Cond: ((department_id = employees.department_id) AND (salary = (max(employees.salary))))
(6 строк)
test=# EXPLAIN (COSTS false) SELECT name AS employee, salary
FROM (
SELECT name, salary, max(salary) OVER (PARTITION BY department_id) AS ms
FROM employees
) AS e
WHERE salary=ms;
QUERY PLAN
-----------------------------------------------
Subquery Scan on e
Filter: (e.salary = e.ms)
-> WindowAgg
-> Index Scan using ds1 on employees
(4 строки)
test=# EXPLAIN (COSTS false) SELECT name AS employee, salary
FROM (
SELECT name, salary,
rank() OVER (PARTITION BY department_id ORDER BY salary DESC) AS rnk
FROM employees e
) AS e
WHERE rnk=1;
QUERY PLAN
------------------------------------------------------------
Subquery Scan on e
Filter: (e.rnk = 1)
-> WindowAgg
Run Condition: (rank() OVER (?) <= 1)
-> Incremental Sort
Sort Key: e_1.department_id, e_1.salary DESC
Presorted Key: e_1.department_id
-> Index Scan using ds1 on employees e_1
(8 строк)Видно, что первые два способа отлично разобрались как использовать этот индекс, но вот последний, который использует rank(), почему-то не справился и использует его только на половину. Не беда, чтобы ему помочь можно индекс исправить.
DROP INDEX ds1;
CREATE INDEX ds2 on employees (department_id, salary DESC);
test=# EXPLAIN (COSTS false) SELECT name AS employee, salary FROM (SELECT department_id, max(salary) AS salary FROM employees GROUP BY department_id) AS m JOIN employees AS e USING (department_id, salary);
QUERY PLAN
--------------------------------------------------------------------------------------------------------
Nested Loop
-> GroupAggregate
Group Key: employees.department_id
-> Index Only Scan using ds2 on employees
-> Index Scan using ds2 on employees e
Index Cond: ((department_id = employees.department_id) AND (salary = (max(employees.salary))))
(6 строк)
test=# EXPLAIN (COSTS false) SELECT name AS employee, salary FROM (SELECT name, salary, max(salary) OVER (PARTITION BY department_id) AS ms FROM employees) AS e WHERE salary=ms;
QUERY PLAN
-----------------------------------------------
Subquery Scan on e
Filter: (e.salary = e.ms)
-> WindowAgg
-> Index Scan using ds2 on employees
(4 строки)
test=# EXPLAIN (COSTS false) SELECT name AS employee, salary FROM (SELECT name, salary, rank() OVER (PARTITION BY department_id ORDER BY salary DESC) AS rnk FROM employees e) AS e WHERE rnk=1;
QUERY PLAN
---------------------------------------------------
Subquery Scan on e
Filter: (e.rnk = 1)
-> WindowAgg
Run Condition: (rank() OVER (?) <= 1)
-> Index Scan using ds2 on employees e_1
(5 строк)Первые два метода работают так же, как и раньше. А метод rank стал использовать индекс в полную силу. Результаты не заставили себя долго ждать.
method | execution_time
--------+---------------------
max | 0.24539799855649472
rank | 0.32680700132250784
window | 0.8033939964771271Даже в самом благоприятном для себя случае «крутой и единственный правильный» метод, по которому отбирает потенциальный начальник, в полтора раза медленнее, чем метод, который первый приходит в голову.
Выводы
Я считаю, что метод с использованием rank() это самый худшее решение этой задачи, потому что при любых рассмотренных индексах он так и не смог занять первое место. Другими словами, не нашлось ситуации, когда его использование было бы оправдано. Получается весь смысл собеседования для приёма на работу это отобрать такого сотрудника, который предлагает самое худшее решение проблемы.Остальных не возьмут.
Это можно понять и легко обобщить, проблема на самом деле имеет фундаментальное значение. Как обычно происходит? Есть full stack работник, который превращается в team lead. Обслуживание PostgreSQL по началу лежит на нём, но он не справляется, и принимается решение нанять узкоспециализированного специалиста по PostgreSQL, чтобы он решил проблемы, которые сам team lead решить не может. Но при собеседовании, если потенциальный сотрудник будет предлагать лучшие решения технические проблем, чем о которых знает потенциальный начальник, то он будет считать, что «ответы неправильные» и на работу не возьмёт. На работу возьмут лишь того, кто предлагает такие же плохие решения технических проблем, которые потенциальный начальник и так знает.
Например не стоит на собеседовании предлагать отказоустойчивый кластер на Pacemaker, который гораздо лучше Patroni.
Потому что в силу своей ограниченности потенциальный начальник знает только одно единственное «правильное и крутое» решение на Patroni, он об этом в Интернете прочитал. Тоже самое касается и других вопросов. Любое хорошее решение, которое будет выходить за рамки ограниченности потенциального начальника, будет расценено как ошибка или демонстрация некомпетентности.
Комментарии (146)
titan_pc
14.07.2024 10:34+3Ну и нафига идти работать в такие места? Где есть начальник который ничего не понимает.
А ещё решение можно на кликхаусе собрать, собственную СУБД для него сделать или вообще свой мемкеш бесконечный построить. И на квантовом компьютере. И и что
splarv Автор
14.07.2024 10:34+3Ну так в этом и есть обратная сила собеседования. Узнаешь еще и какой начальник, насколько разумный. :)
Что же касается ваших предложений по расчёту сотрудников с максимальной зарплатой в отделе, так задачу не я придумал. Сами предложите это на собеседовании.
Ivan22
14.07.2024 10:34+4Я постоянно эту задачу спрашиваю на собесах. На джунов. Принимаю любой вариант. Где-то 50% джунов решить не мугут никаким вариантом. Примерно 5% знают два варианта.
splarv Автор
14.07.2024 10:34+5Ну на самом деле задача вывести строку содержащую максимальное или минимальное значение вполне себе реальная. Я смутно припоминаю, что что-то подобное приходилось решать по работе. Поэтому я интуитивно сразу написал вариант, который уже был в подкорке, ничего на ходу не придумывал. И в этом смысле эта задача, как и другие задачи от JitBit вполне себе полезная, как у них и написано, позволяет выявить людей у которых уже есть реальный опыт работы.
Но вот когда собеседователь начинает требовать, чтобы я угадал его мысли и написал "единственный правильный и крутой" ответ, который на проверку оказывается худшим, это в первую очередь говорит, что у потенциального начальника нет никакого практического опыта работы.
sshmakov
14.07.2024 10:34+2Ну и нафига идти работать в такие места? Где есть начальник который ничего не понимает.
Вот необязательно. Начальник, который задает такие вопросы на собеседовании, может потом в реальной работе прислушиваться к вашему мнению. В конце концов он вас выбирает на экспертную должность, то есть ищет человека, способного разбираться в таких вещах, а сам таким экспертом быть не должен, но отбирать кандидатов ему как-то надо.
TerraV
14.07.2024 10:34Не бывает такого что до подписи в трудовом договоре уровень доверия - ноль, а сразу после - 100%. Да даже на 10% доверие не скачет. Оно зарабатывается и как правило не быстро. Скажу больше, человек с картиной мышления "есть два мнения - мое и неправильное", в принципе не подбирает в команду экспертов. Он выбирает "подпевал" и/или козлов отпущения. Сам провожу собесы, несмотря на десятки лет работы в IT я выслушиваю оппонента и как минимум пытаюсь понять на чем базируется уверенность. На примере из статьи, я бы вообще не заморачивался с "единственным правильным" решением. Соискатель шарит в базах это видно, а какие здесь-сейчас оптимизации зарулили - да вообще похрен. Я лично выбираю более читаемые варианты с CTE (Common Table Expressions). Но и на этом не настаиваю. Мои предпочтения это чисто мои.
splarv Автор
14.07.2024 10:34Хотел бы я было поставить респект, но прочитал про CTE. То что вы относитесь к CTE только как косметическому украшению уже вас характеризует как потенциального начальника. С CTE всё не так просто. Если до 12го Postgresql СTE не оптимизировались и ими можно было как указать PostgreSQL использовать более оптимальный план выполнения запроса (с точки зрения разработчика, причем не всегда эта точка зрения правильная), так и наоборот, можно было бы ухудшить план. Т.е. это как бы "оптимизация", но которая иногда приводит к полностью неработающему сервису. После 12го их функционал несколько изменили несовместимым образом, так это вообще головная боль при апгрейде на 12ю версию. Просмотром кода это не предсказать, даже если бы в коде были SQL запросы.
Это я к тому, что использование CTE надо оценивать вовсе не с точки зрения читабельности кода. Более того, поскольку в отличии от всякой экзотики, вроде курсоров, CTE используются очень часто, практический ежедневно, то это хороший вопрос для собеседования, их надо держать в памяти, когда они оптимизируются, а когда нет.
tr1o
14.07.2024 10:34задумайтесь, человек набирает экспертов, используя задачи и решения, которые он не понимает, он блин даже к встречи с этими экспертами не готов. а конкретно в этом кейсе все эксперты пройдут мимо, кого он наберет сказать сложно, к кому он в конечном итоге будет прислушиваться ? вполне понятно.
Gromilo
14.07.2024 10:34+12CREATE INDEX ds1 ON employees (department_id, salary);Странный индекс, чисто под эту задачу. В реальной жизни я бы рассчитывал на индекс только по департаменту.
Можно тест ещё под индекс по департаменту?
splarv Автор
14.07.2024 10:34+23Вы правы. Если не заморачиваться над оптимизацией именно этого запроса (а смысл собеседования был именно в том, чтобы заморочиться, чтобы написать его "правильным и крутым") и специального индекса не создавать, то индекс по department_id как по foreign key там должен быть, обычная практика.
Можно, чего только не сделаешь для любимых читателей:
method | execution_time
--------+--------------------
rank | 0.7331189993619919
max | 0.5216920003294945
window | 0.6920570016503335
Хм, опять, чтобы пройти собеседование и устроиться на работу, надо предложить самое худшее решение. Да что такое-то?
Mr_Cheater
14.07.2024 10:34Маленькая поправочка (простите). Все-таки, ddl - это язык, а Вы, все же, написали запрос - так ведь?
splarv Автор
14.07.2024 10:34+10Это не поправочка, а придирочка. Да, в DDL последнее слово означает language, т.е. язык. Использовать ddl для обозначения запросов задающих структуру данных - обычный жаргон.
dph
14.07.2024 10:34+9Хм, 2000 записей очень мало, скорее всего вообще все данные будут в памяти.
Возможно пробежаться по курсору в процедуре будет быстрее всего.
Или вообще на бэке посчитать.
Вот если 200000 employers и около 50000 подразделений - то все интереснее )splarv Автор
14.07.2024 10:34+6Устроиться в корпорацию где 200 тысяч сотрудников или больше... Кстати можно, это же как раз будет российская армия. Вот только вместо компьютера вам там дадут что-то другое. :) Но можете попробовать.
Курсор и процедура не прокатит. В таких задачах на собеседовании использование процедур запрещают, надо уложиться в один запрос.
Так это специально было сделано, чтобы все данные были в памяти. Машина 128 ОЗУ, shared_buffers 32GB, все в памяти с большим запасом. Ведь идея была в том, чтобы проверить алгоритмы, а не то, как работает с винчестерами postgres в виртуалке под виндой.
DSolodukhin
14.07.2024 10:34+4Кстати можно, это же как раз будет российская армия
Ну необязательно, достаточно в газпром попасть, у них порядка 500К сотрудников.
А еще можно в Wal-Mart, они вроде как мировые рекордсмены, у них 2,2М сотрудников)
Ivan22
14.07.2024 10:34+6А еще можно не людей считать, а товары и продажи. А их уже и миллионы могут быть и миллиарды. А ты уже привык к курсорам. Не надо так
Politura
14.07.2024 10:34+2Ведь идея была в том, чтобы проверить алгоритмы
Как-раз сложность алгоритмов лучше проверять на больших данных, на маленьких при тестировании, например O(n), может легко быть медленее чем O(n*log(n)) просто потому-что у первого алгоритма каждый шаг стоит чуть больше. Но на больших данных первый будет в сильном отрыве в несколько раз от второго.
splarv Автор
14.07.2024 10:34+1Весь код я выложил. Если вам и правда интересно, вы перепроверите на больших данных. Главное не уйдите в работу с винчестером.
Drac013
14.07.2024 10:34+1Ну, почти 10 таких компаний в РФ наберётся: https://www.forbes.ru/biznes/503283-15-krupnejsih-rossijskih-rabotodatelej-s-cislom-sotrudnikov-bolee-100-000-celovek?image=477074
В мире ещё больше :)
RedWolf
14.07.2024 10:34+18Зачем вложенные запросы, оконные функции и группировки? Давайте подойдем к задаче с точки зрения того, что SQL декларативный язык:
select e1.id, e1.name, e1.salary from employees e1 left outer join employees e2 on e1.department_id = e2.department_id and e2.salary > e1.salary where e2.id is nullТакие сотрудники, что в их отделе нет никого с более высокой зп. Понятно, что не очень эффективно, но прикольно.
OldNileCrocodile
14.07.2024 10:34На собеседованиях проверяют сам факт того, что Вы знаете вышеперечисленное, а не то, что знаете лучше. Вот не знаете решение через оконные функции - начальник Вас не пустит. Знаете - хорошо.
splarv Автор
14.07.2024 10:34+2Т.е. надо зубрить самые бессмысленные решения широко распространённых в Интернете задач? Ну да, победная стратегия.
karrakoliko
14.07.2024 10:34Именно так.
Perception is reality.В худшем случае вы дадите социально одобряемый ответ, и покажетесь "своим".
В лучшем - вы сделаете пометку, что это не самый оптимальный способ, разбирались, знаете нюансы, сейчас продемонстрируете... и либо пройдете тест на "своего" (ага, мы тоже знаем!), либо удивите и продемонстрируете экспертизу, после чего решение по найму на этом этапе будет де-факто принято.
splarv Автор
14.07.2024 10:34+2Любое "удивите и продемонстрируете экспертизу" - ответ неправильный. Хуже ситуация получается, когда собеседуют двое: тех.специалист и эффективный менеджер. И когда их тех.специалист начинает отчаянно вешать лапшу на уши, вообще не понимая, как это работает (так было с проектом NRD), он ни за что не признается, что облажался и будет всяческий подтасовывать информацию в спорных вопросах, лишь бы его начальник не узнал, какое он дно. А эффективный менеджер оценивает только кто говорит более уверенным голосом. :) Если ты вешаешь лапшу на уши очень уверенно - получишь работу.
list021
14.07.2024 10:34Подтверждаю. Вышла на одну такую работу и долго училась у коллег как разговаривать с менеджерами, довольно противный навык, но нужен был для выживания :(
splarv Автор
14.07.2024 10:34+1Ну да, тут вся статья про неэффективные, но прикольные способы. :) Поставил респект за изобретательность. QUERY PLAN
Hash Left Join (cost=62.00..2854.00 rows=1 width=30) (actual time=0.337..8.945 rows=20 loops=1)
Hash Cond: (e1.department_id = e2.department_id)
Join Filter: (e2.salary > e1.salary)
Rows Removed by Join Filter: 101000
Filter: (e2.employee_id IS NULL)
Rows Removed by Filter: 99000
-> Seq Scan on employees e1 (cost=0.00..37.00 rows=2000 width=34) (actual time=0.007..0.078 rows=2000 loops=1)
-> Hash (cost=37.00..37.00 rows=2000 width=16) (actual time=0.273..0.273 rows=2000 loops=1)
Buckets: 2048 Batches: 1 Memory Usage: 110kB
-> Seq Scan on employees e2 (cost=0.00..37.00 rows=2000 width=16) (actual time=0.002..0.125 rows=2000 loops=1)
Planning Time: 0.088 ms
Execution Time: 8.961 ms
(12 строк)Но все же в 10 раз тормознутее худших вариантов, я выше выкладывал статистику с индексом только по delivery_id. Но с точки зрения потенциального работодателя, я думаю вы произведёте впечатление, это единственный мне известный вариант без вложенных запросов.
Politura
14.07.2024 10:34+1В 10 раз медленнее на каких-то 2000 записях, чем больше записей в таблице, тем больше будет отставание. Впечатление производит, да, настолько сильное, что яб на месте интерьюера схватился-бы за сердце и был категорически против оффера. :)
orefkov
14.07.2024 10:34Весь вопрос в том, есть ли на собесе возможность хотя бы план запроса посмотреть. Вряд ли с ходу без этого предугадаешь, как он будет отрабатывать.
RedWolf
14.07.2024 10:34+1Почему же, предугадаешь. В моем шутливом примере, до которого некоторые начали докапываться с точки зрения производительности, хотя я сразу написал, что она там плохая и что это скорее забавный пример, сразу видно, что тут практически декартово произведение, в рамках департамента.
orefkov
14.07.2024 10:34Вопрос то тут не а вас, а в СУБД. Дать стопроцентную гарантию, как он будет выполняться - нельзя, и вдруг оптимизатор отработает отлично. Пока план запроса не посмотришь - однозначные выводы не сделаешь. Ну а декартово произведение - ну и что такого, там есть ограничения, вдруг чудо бы случилось и оптимизатор бы вывез
splarv Автор
14.07.2024 10:34Я перевел статью с JitBit и выложил в Хабр, как раз ту, где была эта задача. И там говорят, что ни кандидатам всегда предоставляют компьютеры подключенные к базе данных. Работай в привычных условиях.
А в России да, раньше надо было писать что-то ручкой на огрызке бумаги, сейчас так вообще тебе показывают скриншот, который даже не скопипастишь и надо решить задачу в уме. И от непривычных условий, которые не наработаны практикой, начинаешь стрессовать.
А что касается Красного Волка, то да, это была остроумная шутка, которая умнее, чем кажется. Дело в том, что некоторые (может многие) потенциальные начальники, в том числе и те, кто отписывались в комментариях, имеют странные предпочтения. Мол, если нет вложенных запросов, значит вариант хороший. А поскольку это единственный мне известный вариант без позапросов, получается вариант Красного Волка с точки зрения собеседователя самый лучший. А с точки зрения человека с реальной практикой отладки запросов очевидно, что всё будет наоборот. Декартово произведение, действительно, видно. :)
Batalmv
14.07.2024 10:34+6Как человек, которые ее задает на собеседованиях наверное уже скоро как 20 лет, могу открыть секрет - большинство людей, которые называли себя SQL-програмистами, data инженерами ее не решают от слова совсем. И даже если даже не 5 секунд, а минут 10.
Просто остальных (в смысле другие позиции), которые просто вписали в резюме SQL и не краснеют, когда говорят, что знают и очень хорошо я даже умолчу
Причем явно говоришь, что надо просто запрос, который вернет правильный ответ, не надо думать над оптимальным решением (что может не иметь смысла без реальной базы) - не помогает
splarv Автор
14.07.2024 10:34+2Вполне разумный подход. Хм, а вам программист PostgreSQL не нужен? Ответ на эту задачку я уже знаю. :)
NechkaP
14.07.2024 10:34+2Хорошую тему затронули, оконные функции умею писать, но они реально в большинстве случаев пригождались только на собеседованиях) И как раз мне запомнилось в положительном ключе собеседование, где я написала решение какой-то подобной задачи как раз "социально одобряемым" способом, но в итоге обсудили, что есть риск, что оно не такое уж оптимальное
akk0rd87
14.07.2024 10:34+1А можно закину задачек, для которых придумали оконные функции, и которые попадались мне на работе? Вариант "на бэке посчитать" не предлагать - вся работа идет в хранилище данных:
Есть таблица истории покупок товаров клиентами. Сегментировать клиентов в соответствии с суммой потраченных средств согласно нижеприведенной сегментации: Top 5%
High 20%
Middle 30%
Others 45%Вторая задачи достаточно сложная, чтобы давать на собеседовании, но можно подумать над ходом решения:
Имеется широкая сеть в ритейле с учетом партнерских торговых точек, и некотрые кассовые аппараты разбивают один чек на несколько чеков (то есть каждый товар в корзите проходит отдельной транзакцией), менжду которыми нет явной связи. Связь только косвенная: такие чеки имеют одинаковые идентификаторы ТТ (троговой точки), и номер аккаунта клиента (account_id). При совпадении этих параметров будем сверять время с кассового аппарата pos_time (который также является атрибутом операции) и если между операциями разница не более 5 минут, то объединяем их в один чек. Цепочки могут быть транзитивными. Результатом объединения будет добавление нового поля agg_cheque_id, который будет равен первой операции в объединенной цепочке.
Не нужно писать скрипт обновления (merge или update), достаточно написать select, который выведет операции с расчитанным agg_cheque_id.
NechkaP
14.07.2024 10:34Да, это валидно, но... ведь не утверждалось, что оконные функции действительно всегда плохи. Посыл и статьи, и комментариев вроде моего в том, что не стоит по умолчанию считать, что их использование отделяет условного сеньора от джуна или хорошего кандидата от плохого (и в принципе не стоит зацикливаться на каком-то конкретном ожидаемом решении задачи, просто потому что оно понравилось/популярно/не знаешь других)
splarv Автор
14.07.2024 10:34+1Смотрите. Все же задача собеседования выявить что специалист опытный и рукастый и он сможет решать поставленные перед ним задачи самостоятельно. Например начав с предварительного чтения документации, если он подзабыл эту тему, главное помнить, где что есть и куда смотреть. Например я за 25 лет ни разу не сталкивался с задачами, которые требовали бы оконных функций, по крайней мере, с момента их появления в PostgreSQL. И это не моя вина, просто специфика работодателя их не требовала, они больше ориентированы на каких-то финансистов. И за последние пять лет мне потребовался рекурсивный поиск только один раз (его тоже часто спрашивают на собеседовании), потому что веб программисты микросервисов не заморачиваются таблицами со ссылками на самих себя. Но это же не значит, что я не смогу справиться с работой, пролистав документацию в течении 15 минут, просто, чтобы освежить это в памяти.
У слову ваша 2 задача это явный bad design. Не стоит на собеседовании спрашивать как костылить вашу систему, вредно для репутации компании.
rqdkmndh
14.07.2024 10:34# Вы серьёзно ждете что кто-то ответит на вторую задачу на собесе?:
WITH SortedTransactions AS (
SELECT
transaction_id,
store_id,
account_id,
pos_time,
LAG(pos_time) OVER (PARTITION BY store_id, account_id ORDER BY pos_time) AS prev_pos_time
FROM
transactions
),
GroupedTransactions AS (
SELECT
transaction_id,
store_id,
account_id,
pos_time,
ROW_NUMBER() OVER (PARTITION BY store_id, account_id ORDER BY pos_time) AS rn,
CASE
WHEN prev_pos_time IS NULL OR pos_time > DATEADD(minute, 5, prev_pos_time) THEN 1
ELSE 0
END AS is_new_group
FROM
SortedTransactions
),
RecursiveGrouping AS (
SELECT
transaction_id,
store_id,
account_id,
pos_time,
rn,
transaction_id AS agg_cheque_id
FROM
GroupedTransactions
WHERE
is_new_group = 1
UNION ALL
SELECT
t.transaction_id,
t.store_id,
t.account_id,
t.pos_time,
t.rn,
rg.agg_cheque_id
FROM
GroupedTransactions t
JOIN RecursiveGrouping rg ON t.store_id = rg.store_id
AND t.account_id = rg.account_id
AND t.rn = rg.rn + 1
AND t.is_new_group = 0
)
SELECT
transaction_id,
store_id,
account_id,
pos_time,
agg_cheque_id
FROM
RecursiveGrouping
ORDER BY
store_id,
account_id,
pos_time;splarv Автор
14.07.2024 10:34Я думаю это реальная задача, которую он сам не смог решить до сих пор. Выложил под видом якобы задачи на собеседование, в надежде, что кто-то из комментаторов напишет ему запрос.
gleb_l
14.07.2024 10:34+1Господи, зачем столько писать про это? Если вам нужен специалист по БД, а не просто energizer-заяц, который в работе с БД знает только 4 буквы C, R, U, D и итератор, но зато бьет в барабан со скоростью и позитивом свежей батарейки - то он должен начать писать ответ, еще не дослушав задание, и время его выполнения долго быть равно времени набивания DML на клавиатуре. Любой другой наблюдаемый результат - это провал. Такой чел в эффективной работе с БД вам не поможет- будет, как жонглер в цирке крутить многоуровневые циклы (что итераторы в ПЯП, что многоэтажные курсоры прямо в БД - результат один), манящие O(1), O(N), O(N log N) уплывут от вас дальше Антарктиды, а на продакшене вы будете затыкать performance-дыры, выклянчивая у IT-отдела планки памяти под завязку, и сервера в стойку, чтобы хоть как-то бороться с data growth rate.
Эффективная работа с БД - это образ мышления. И он ортогонален процедурному (тредовому) у фуллстеков. Главная задача на собеседовании на БД-инженера - понять, есть оно или нет.
splarv Автор
14.07.2024 10:34+4Ну и? А вы с кем и о чем тут спорите? Мне кажется вы даже не поняли в чем тут суть и уже начали набивать коммент "со скоростью и позитивом свежей батарейки". Как вы и написали, начали писать ответ даже не разобравшись, а в чем было задание. :)
gleb_l
14.07.2024 10:34+1Хм, Вы действительно считаете, что задача взятия строк с максимальным значением какого-нибудь свойства, внутри подмножества, определяемого другим свойством, стоит того, чтобы размазывать ее по столу слоем толщиной в 1 молекулу? Со всеми этими заголовками Постановка задачи, Варианты решения? И почему вы так уверены, что сферическому начальнику в вакууме нужно будет обязательно продемонстрировать знание оконных функций? Мой заяц бьет в барабан именно по этому поводу ;)
splarv Автор
14.07.2024 10:34Не просто знание оконных функций, а то единственное решение через rank(), про которое он прочитал в интернете. Так он сам так говорит. :) Ну или отчаянно на это намекает.
А статья вовсе не про эту задачу, если вы не поняли, а про особенности собеседований и собеседователь.gleb_l
14.07.2024 10:34Ну так вменяемый кандидат должен выкатить несколько решений - сразу, или на первый же вопрос собеседующего об этом. Но если статья про особенности собеседований и собеседователя - то почему 90% из того, что не является оформляющим вводные текстом - это код, а не психологический портрет собеседующего? Если в статье стейтменты, цифры результатов запусков и execution plan’ы - как заяц догадается, что статья про особенности экзаменаторов?
PS - про то, что ожидаемый (ловушечный) метод по перформансу не лучший - и так понятно. Всякое универсальное хуже специального (С). Попробуйте без оконных решить задачу более общего вида (скажем, найти записи на n-ом месте по зарплате) - и сравните трудоемкость execution plan’ов.
splarv Автор
14.07.2024 10:34Никто не против того, чтобы использовать оконные функции там где нужны.
Тезис этой статьи, который я и написал в выводах, это то, что собеседование можно построить таким образом, что на работу будут набирать только и исключительно только сотрудников, которые предлагают самый худший вариант решения проблемы. Выглядит как забавный парадокс. Но столь громкое утверждения нельзя было подтвердить технической аргументаций, чтобы не выглядело голословно. Вы это не оценили.
nApTu3aH_nn
14.07.2024 10:34+1Создавать индексы под каждый запрос так себе решение. И если индекс по ИД отдела логичен и создаётся на автомате (тем более что скорее всего там будет внешний ключ), то включение в него зарплаты уже выглядит сомнительно. А если завтра попросят список всех сотрудников, нанятых последними в своих отделах? Ещё индекс, с ИД отдела и датой приёма на работу?
Второй способ норм и его на собеседовании вполне стоит принять, но надо понимать, что это частный случай и оконные функции намного более мощный инструмент и владеть им необходимо. Ну, ок, желательно.
splarv Автор
14.07.2024 10:34Я уже отвечал на подобный коммент.
https://habr.com/ru/articles/828728/comments/#comment_27040670
Подчеркну, мы же не рассматриваем реальную продовую базу данных с реальными задачами. Речь тут идёт о том, чем собеседование отличается от реальной работы.nApTu3aH_nn
14.07.2024 10:34+3Да, потом увидел... Тут ещё момент, что соотношение 2000 сотрудников на 20 подразделений не уверен, что жизненное, 100-200 подразделений будет ближе ИМХО, по крайней мере в ИТшных конторах так. Из-за этого вариант с max должен быть уже не так быстр. Тут заметим, что решение, производительность которого сильно зависит от семантики данных, уже не очень хорошо.
Собеседование не может не отличаться, это понятно, и данная задача как раз и хороша тем, что даёт возможность обсудить разные аспекты. Не знаю, где Вы видели таких начальников, которые бы требовали единственно верного решения, сдаётся мне, таких не бывает :о)
splarv Автор
14.07.2024 10:34О, и не такие бывают. Как-тот раз, лет пять назад, проходил собеседование в одну контору, которая работала на правительство. Собеседовало меня два человека, тех.специалист и эффективный менеджер. У тех. специалиста претензий ко мне не было. Отшил эффективный менеджер, который сделал психологическое наблюдение, что я говорю не достаточно твёрдым и уверенным голосом.
DeniSun
14.07.2024 10:34+1У нас препод был в институте. На зачете/экзамене можно было получить фразу: "Я чувствую, что Вы что-то не знаете"
vdshat
14.07.2024 10:34+1Есть у меня на одном проекте такой персонаж, который знает все эти функции и выверты с подвывертами... Но если эти знания не подкреплены логикой иои логика есть, но своя - альтернативная, то это путешествие по минному полю с завязанными глазами.
-- Почему в базе, вдруг, исчезли все внешние ключи?
-- Я их убрал, т.к. они мешали вставить данные: ошибки вылетали.
-- Так в том же и смысл, чтоб обеспечить целостность базы!
-- Я все могу обеспечить и так.
Или таблицы без ключей и индексов и с сотнями столбцов, чтоб все в одной таблице хранилось, а то скорость выборки низкая. Но зато рэнки, партишены и т.д. и т.п. от зубов отскакивают!
splarv Автор
14.07.2024 10:34+1Ну, если у него вылетали ошибки целостности данных и именно поэтому он убрал внешние ключи, так значит целостность данных он уже не обеспечил.
nApTu3aH_nn
14.07.2024 10:34Может, он таблицы заполнял в алфавитном порядке, а не как предполагает их иерархия :о)
Отключение констрейнтов и индексов в принципе практикуется при разного рода массовых заливках данных, но потом, конечно, нужно всё вернуть.
vdshat
14.07.2024 10:34+1Одно дело отключить, другое - удалить :)
Просто отсутствие базовых знаний приводит к такой каше в голове.
splarv Автор
14.07.2024 10:34Да, так работает pg_dump, только он не констрейнты отключает, а триггеры, которые их проверяют. Вообще все триггеры. Но вы это даже не заметите. А если даже вы это заметили, значит ваш сотрудник уже облажался.
sgenie
14.07.2024 10:34select employees.department_id,employees.name,salary from employees left join departments as dep on dep.department_id=employees.department_id where salary=(select max(salary) from employees where department_id=dep.department_id);
splarv Автор
14.07.2024 10:34Похожее было, но у вас есть отличия. Во первых left join в employees left join departments не нужен, потому что я авторским произволом в DDL прописал NOT NULL. Второе ваше отличие, если я получаю все максимальные зарплаты по отделам за один запрос, у вас на каждый отдел будет подзапрос.
Hash Left Join (cost=38.58..89.43 rows=1 width=30) (actual time=0.161..21.505 rows=20 loops=1)
Hash Cond: (employees.department_id = dep.department_id)
Filter: (employees.salary = (SubPlan 1))
Rows Removed by Filter: 1980
-> Seq Scan on employees (cost=0.00..37.00 rows=2000 width=30) (actual time=0.007..0.087 rows=2000 loops=1)
-> Hash (cost=22.70..22.70 rows=1270 width=4) (actual time=0.007..0.007 rows=20 loops=1)
Buckets: 2048 Batches: 1 Memory Usage: 17kB
-> Seq Scan on departments dep (cost=0.00..22.70 rows=1270 width=4) (actual time=0.004..0.005 rows=20 loops=1)
SubPlan 1
-> Aggregate (cost=4.28..4.29 rows=1 width=8) (actual time=0.010..0.010 rows=1 loops=2000)
-> Index Scan using d on employees employees_1 (cost=0.28..4.03 rows=100 width=8) (actual time=0.001..0.006 rows=100 loops=2000)
Index Cond: (department_id = dep.department_id)
Planning Time: 0.127 ms
Execution Time: 21.528 msВ результате 21.52 ms вместо 0.52 ms у очень похожего (тоже через агрегатную функцию max()) запроса у меня. Где-то в сорок раз медленнее.
alexla86
14.07.2024 10:34Я думал будет задача про стеклянные шарики или про заезд из 25 лошадей, а тут про базы данных оказывается.
NNikolay
14.07.2024 10:34Все три решения выдадут дупликаты, если у двух сотрудников одинаковая и максимальная зарплата. Нужно использовать rownumber вместо rank и сортировать по имени дополнительно.
splarv Автор
14.07.2024 10:34Если у двух разных сотрудников одинаковая зарплата, то это уже не дубликаты. Более того, если вы имели хоть какое-то отношение к математике и решали, например, уравнения, то ответом решения задачи будет все возможные решения. Написать только одно - грубая ошибка.
NNikolay
14.07.2024 10:34+1Кандидат в ситуации, где возможны разночтения, упирается в один вариант и защищает его до конца. На критику реагирует оскорблениями. Вся суть этого вопроса и подобных интервью.
Wesha
14.07.2024 10:34+1Кандидат в ситуации, где возможны разночтения, упирается в один вариант и защищает его до конца.
А Вы бы желали, чтобы кандидат пытался выяснить, чего постановщик задачи реально хотел? Будьте осторожны в своих желаниях: они иногда сбываются!
NNikolay
14.07.2024 10:34+1У Вас в статье по ссылке хороший пример как не надо делать. Я жду что кандидат спросит - а зачем это Вам нужно. Такого можно брать.
Wesha
14.07.2024 10:34+1Я жду что кандидат спросит - а зачем это Вам нужно. Такого можно брать.
Совершенно верно. "Кандидат" в статье по ссылке откровенно издевается над интервьюером — он это в самом начале статьи заявляет.
Я, например, всегда после объявления задачи начинаю разговор с what is the problem you are trying to solve? (какую проблему вы пытаетесь режить?), потому что обычно постановка задачи — из серии "как правильно забивать гвозди микроскопом?"
bosco
14.07.2024 10:34Тут лучше подойдёт другая функция постгре
Пишу с телефона по памяти, но здесь должно сработать и
select distinct on(department_id) name, salary from employees group by department_id order by department_id, max(salary), name
Базы данных надо любить, многие молодые ребята их не любят
splarv Автор
14.07.2024 10:34+1Ох, distinct on() это не функция. Это во первых. Во-вторых ваш запрос не работает. В третьих при его написании вы допустили грубые ошибки. В четвертых вариант решения с помощью distinct, действительно, существуют, но они выдают только одного сотрудника с максимальной зарплатой, а в случае если в отделе несколько сотрудников с максимальной зарплатой, их надо вывести всех.
vanxant
14.07.2024 10:34в случае если в отделе несколько сотрудников с максимальной зарплатой, их надо вывести всех
ну это вы положим на ходу выдумали, в оригинальной задаче такого требования нет.
splarv Автор
14.07.2024 10:34Ну, это очевидное правило в математике начиная со школы и решений квадратных уравнений. :) Нельзя "угадывать ответы", надо вывести их все. Иначе ответ не правильный, даже если вы одно решение угадали.
DocSportello
14.07.2024 10:34Больше нравится вариант с оконной функцией, компактно получилось)
/* 1 */ select * from public.employees where salary in ( select max(salary) from public.employees group by department_id ); /* 2 */ select * from ( select *, dense_rank() over(partition by department_id order by salary) as rank from public.employees ) as t where t.rank = 1; /* 3 */ select * from public.employees as e inner join ( select department_id, max(salary) as max_salary from public.employees group by department_id ) as d on d.department_id = e.department_id and d.max_salary = e.salary;
DocSportello
14.07.2024 10:34Больше нравится вариант с оконной функцией, компактно получилось)
/* 1 */ select * from public.employees where salary in ( select max(salary) from public.employees group by department_id ); /* 2 */ select * from ( select *, dense_rank() over(partition by department_id order by salary) as rank from public.employees ) as t where t.rank = 1; /* 3 */ select * from public.employees as e inner join ( select department_id, max(salary) as max_salary from public.employees group by department_id ) as d on d.department_id = e.department_id and d.max_salary = e.salary;splarv Автор
14.07.2024 10:34+3Ваш первый вариант, грубая ошибка. Допустим у одно сотрудника максимальная зарплата по отделу 200. А у другого такая же зарплата, но он в другом отделе и у него зарплата там не максимальная. У вас второго тоже выведет.
Второй вариант, там ошибка еще грубее. Вы выведите сотрудников с минимальной зарплатой в отделе.
Третий. Да, это первое, что приходит в голову и на проверку оказалось что лучший вариант. У меня такой же, только первый, под именем max.
eigrad
14.07.2024 10:34+2Не взяли то наверное не из за ответа на джуновую задачку (очевидно что хардскиллы выше необходимого на джуновый уровень), а скорее из за неумения общаться и излишней самоуверенности?
Btw, в реальности предпочту решение через rank, так как на производительность в данном случае пофиг, да и индекса по salary скорее всего не будет. А решение с rank не делает полноценных подзапросов/джойнов, и делает в явном виде именно то что требуется в задаче без хаков.
Моя любимая задачка про оконные функции:
Есть файл (или табличка, как удобнее кандидату) куда пишутся значения показателей датчиков. Каждая запись содержит таймстемп, идентификатор датчика, и набор значений его показателей в указанный момент времени. Значения показателей меняются сильно реже интервала считывания. Нужно отфильтровать записи, в которых не происходит изменения значений показателей.
eigrad
14.07.2024 10:34Задание со звёздочкой для оригинальной задачи (про зарплаты) - как решить её через оконные функции, но без сортировки.
eigrad
14.07.2024 10:34Лол, пока читал комменты забыл что в статье это решение приведено :-)
(с подачей "и это не то!!!" вместо объяснения про сортировку просто не обратил внимания на это решение)
splarv Автор
14.07.2024 10:34И как вы собираетесь решать через rank() без подзапросов? Без подзапросов я только одно решение в комментах видел и оно было вовсе не через rank(). И да, с ужасной производительностью.
eigrad
14.07.2024 10:34Однако, парадокс, там где результаты подзапроса используются как дополнительный набор данных (а результат берется отдельным проходом по таблице) - в explain нет слова subsquery, а там где результат подзапроса непосредственно используется для вывода (после фильтра) - это Subquery Scan :-).
RedWolf
14.07.2024 10:34+1select * from ( select *, lag((v1, v2), -1) over (partition by sensor_id order by ts desc) prev from telemetry_data ) t where prev is null or (v1, v2) <> prev order by 1Для двух показаний - v1 и v2, оба integer not null для примера, postgresql
ris58h
14.07.2024 10:34Видно, что первые два способа отлично разобрались как использовать этот индекс
Первые два метода работают так же, как и раньше.
Похоже, что значение для
windowво втором тесте у вас какое-то неправильное, т.к. оно намного ближе кrank, чем кmax.
Wesha
14.07.2024 10:34А куда делось очевидное
SELECT (SELECT employee_id FROM employees WHERE employees.department_id = departments.department_id ORDER BY salary DESC LIMIT 1) AS employee_id, departments.department_id FROM departmentsНе претендую на "быстрейшее решение по скорости выполнения" — это просто то, что немедленно приходит в голову.
splarv Автор
14.07.2024 10:34+1Смотрите, в вашем варианте если в подразделении у двух сотрудников будет максимальная зарплата, то выведет только одного. Это уже неправильно.
Wesha
14.07.2024 10:34+3Условие задачи изменилось после того, как я запостил комментарий — в нём отстутствовало требование "всех сотрудников, у кого максимальная зарплата". Потому-то я и удивился — "а чего нет такого очевидного решения?"
splarv Автор
14.07.2024 10:34Это обычное правило в математике начиная со школы и решения квадратных уравнений. В ответе на задачу должны быть приведены все решения задачи. А иначе задача не решена. А в этом контексте и смысла невозможно придумать выводить только одного сотрудника, если в отделе два таких.
mentin
14.07.2024 10:34+1А в некоторых базах можно обойтись одной агрегацией
SELECT department_id, ANY_VALUE(employee_id having max salary) AS employee FROM employees GROUP BY department_idsplarv Автор
14.07.2024 10:34Хм, но все же быстрота запроса и его эффективность определяется не количеством символов в тексте. Где-то была хороший пример, там сравнивали текст пузырькового алгоритма сортировки для функционального языка программирования и обычного, алгоритмического. Для алгоритмического текста было значительно больше, для функционального несколько строк с рекурсивными вызовами. Но это же не значило, что вариант с функциональным языком лучше, там было ровно наоборот.
mentin
14.07.2024 10:34+1Ну тут реально одна агрегация - без использования индексов быстрее никак не получится.
ris58h
14.07.2024 10:34Если в отделе 2 сотрудника с одинаковой максимальной ЗП, то что выдаст ваш запрос?
khe404
14.07.2024 10:34А чем плох вариант
SELECT name, max(salary) AS salary
FROM employees
GROUP BY department_idВозможно я что то подзабыл в SQL ,и есть ограничения на выполнение подобной процедуры.
ris58h
14.07.2024 10:34+1Такой запрос даже выполняться не будет, т.к. содержит ошибку: вы используете
nameбез агрегирования.khe404
14.07.2024 10:34Да вы правы.
Попробовал вот тут https://www.w3schools.com/mysql/trymysql.asp?filename=trysql_select_groupby
запрос
SELECT customerid, max(shipperid) FROM Orders group by employeeid ;Он хотя и выполняется но результат получается не правильный.
datacompboy
14.07.2024 10:34Разумеется ваш потенциальный начальник не придумывал ни эту задачу, ни её решение. И задачу и "правильный" ответ он подглядел в Интернете, чтобы демонстрировать своё ментальное превосходство.
В хрестоматию, в качестве иллюстрации к тому "Токсик"
rrrrex
14.07.2024 10:34+3Задача формулируется так. Есть база данных, где содержатся сотрудники с их разбиением по отделам и зарплатой. Я пытался прогуглить корень зла. Ссылки меня привели к статье: https://www.jitbit.com/news/181-jitbits-sql-interview-questions/
Просто на отлично задачу сформулировали. Выглядит так будто кусок текста вырвали, и уже мы, а не вы, должны искать как же звучала эта задача.
splarv Автор
14.07.2024 10:34Ну да мой косяк. На самом деле в статье эта фраза была дважды, второй раз, действительно, с формулировкой задачи. Первую фразу я уже стёр. Спасибо за бдительность.
eugeneyp
14.07.2024 10:34+1А почему нет простого решения через предикат?
select name from employees a
where not exists(select * from employees a where a.department_id=b.department_id and a.salary<b.salary)
Sunny-s
14.07.2024 10:34не только лишь все СУБД могут нормально обработать джойн с неравенством (в который разворачивается where not exists)
eugeneyp
14.07.2024 10:34+1Можно пример таких БД, мне кажется что это базовый функционал БД: JOIN с неравенством.
Скорее в старых версиях БД будет отсутствовать WINDOW функции или SELECT FROM SELECT, чем JOIN с неравенством.
splarv Автор
14.07.2024 10:34Ну, вполне себе вариант. Почему нет, да как-то было очевидно, что по сравнению с вариантом с max() будет хуже.
test=# explain analyze select name, salary from employees a where not exists(select * from employees b where a.department_id=b.department_id and a.salary<b.salary); QUERY PLAN
Hash Anti Join (cost=62.00..122.50 rows=1333 width=26) (actual time=0.307..0.956 rows=20 loops=1)
Hash Cond: (a.department_id = b.department_id)
Join Filter: (a.salary < b.salary)
Rows Removed by Join Filter: 9635
-> Seq Scan on employees a (cost=0.00..37.00 rows=2000 width=30) (actual time=0.008..0.089 rows=2000 loops=1)
-> Hash (cost=37.00..37.00 rows=2000 width=12) (actual time=0.284..0.284 rows=2000 loops=1)
Buckets: 2048 Batches: 1 Memory Usage: 110kB
-> Seq Scan on employees b (cost=0.00..37.00 rows=2000 width=12) (actual time=0.003..0.138 rows=2000 loops=1)
Planning Time: 0.093 ms
Execution Time: 0.972 ms
(10 строк)
Sunny-s
14.07.2024 10:34а если у нас не департаменты и сотрудники, а товарные категории и чеки в миллиардных количествах, и хранится это все в каком нибудь хайве, то оконные функции отработают быстрее, потому что все будет происходить за один проход. Вложенный запрос сгенерирует редьюсеры, которые раскатятся по всему кластеру, и пока не завершатся все - не пойдет внешний.
splarv Автор
14.07.2024 10:34Контр довод, оконная функция rank() будет считать ранги для всех сотрудников (и тратить на это ресурс), в то время как max() потребует меньше машинного времени. Плюс размер таблицы передаваемой из внутреннего запроса во внешний, в вашем случае она будет с размером с число сотрудников, в случае с max() размером с число подразделений.
Но, зачем теоретизировать? Обоснуйте свою точку зрения неголословно. Приведите такое распределение данных, при котором использование rank() будет выигрывать. Вот это уже будут слова не мальчика, но мужа.
Dikiiforever
14.07.2024 10:34Я правильно понимаю что
rank() OVER (PARTITION BY department_id ORDER BY salary DESC)даст номер 1 employee ру с максимальной salary в разрезе своего depatament_id и даст номер 2 employee ру в том же departament_id даже если у него будет такая же максимальная salary как и у 1 employee ра?
Задача вроде "нахождению сотрудников с максимальной зарплатой в отделе"
а не "нахождению сотрудников с максимальной зарплатой в отделе по одному из отдела"?splarv Автор
14.07.2024 10:34Нет, поищите документацию по rank() и rank_dense(). На собеседованиях об этом спрашивают.
Mischael
14.07.2024 10:34Проблема в том, что придумывая задачу для собеседования, работодатель не всегда корректно ее формулирует, особенно если сам он не технарь
splarv Автор
14.07.2024 10:34Задача сформулирована корректно и работодатель даже её не придумывал. :) Он взял её из блога иностранной компании.
gora76
14.07.2024 10:34select employee_name,
department_name,
salary
from
(select e.name employee_name,
d.name department_name,
first_value(e.salary) over (partition by d.department_id order by salary desc) salary,
row_number() over (partition by d.department_id) rn
from departments d
join employees e on e.department_id = d.department_id) t
where rn = 1splarv Автор
14.07.2024 10:34Поскольку в остальных ответах вывод названия департамента не требовалось, я слегка переписал ваш запрос. Но обращает внимание на то, что вы window функции применяете к таблице employee, а партицируете их по таблице departments. С точки зрения функционала может это не важно, с точки зрения потенциальной оптимизации запроса косяк. Но не суть в этом.
test=# explain analyze select employee_name,
salary
from
(select e.name employee_name,
first_value(e.salary) over (partition by e.department_id order by salary desc) salary,
row_number() over (partition by e.department_id) rn
from employees e ) t
where rn = 1;QUERY PLANSubquery Scan on t (cost=146.66..241.66 rows=10 width=26) (actual time=0.520..1.137 rows=20 loops=1)
Filter: (t.rn = 1)
-> WindowAgg (cost=146.66..216.66 rows=2000 width=46) (actual time=0.519..1.134 rows=20 loops=1)
Run Condition: (row_number() OVER (?) <= 1)
-> WindowAgg (cost=146.66..186.66 rows=2000 width=38) (actual time=0.517..1.058 rows=2000 loops=1)
-> Sort (cost=146.66..151.66 rows=2000 width=30) (actual time=0.513..0.569 rows=2000 loops=1)
Sort Key: e.department_id, e.salary DESC
Sort Method: quicksort Memory: 158kB
-> Seq Scan on employees e (cost=0.00..37.00 rows=2000 width=30) (actual time=0.008..0.141 rows=2000 loops=1)
Planning Time: 0.071 ms
Execution Time: 1.155 ms
(11 строк)Здесь, как и в других аналогичных ответах в комментах запрос идет по таблице с индексом только на department_id, раз уж решили, что такой вариант, наиболее реалистичный.
test=# \d employees
Таблица "public.employees"
Столбец | Тип | Правило сортировки | Допустимость NULL | По умолчанию
---------------+---------+--------------------+-------------------+--------------
employee_id | integer | | not null |
department_id | integer | | not null |
name | text | | not null |
salary | money | | not null |
Индексы:
"employees_pkey" PRIMARY KEY, btree (employee_id)
"d" btree (department_id)
Ограничения внешнего ключа:
"employees_department_id_fkey" FOREIGN KEY (department_id) REFERENCES departments(department_id)
Archi_Pro
14.07.2024 10:34.> Он начинает подсказывать, что нужно использовать оконные функции.
Как человек много раз проходившей собеседования с подобными вопросами могу сказать что у вас неверная формулировка
Вопрос обычно звучит как top N чего то вывести и вот тогда без оконных функций не обойтись
Возвращаясь к вашей задаче, начальник просит вывести по 3 человека с самой высокой зп в каждом отделе
Ну а если начальник просит вывести сотрудников с максимальной зп через оконную функцию то вероятно он так себе начальник в плане сикулиsplarv Автор
14.07.2024 10:34Я же не просто рассказал, как было на собеседовании, тут вы могли бы придумать, что это я всё нафантазировал, всё было по другому, уж вы то точно знаете, вас там не было. Это хрестоматийная задача, которая есть и на Stack Overflow (с лидирующим решением как раз через rank()) и я привел ссылку на оригинал в блоге JitBit. Последнее я даже перевёл и выложил на Хабр.
Archi_Pro
14.07.2024 10:34Я не говори что вы что то нафантазировали
К сожалению, на собесах я очень часто встречал задачи с неполными условиями с неверными и т.д.
Просто вопрос про вывести топ, это почти на каждом собесе на аналитика/ дата сантиста
З.Ы. а теперь про неверные формулеровки оффтоп:
В икс 5 моему коллеге дали задачу на Пуассона но не дали лямбду
Мне только в Яндексе дали корректную задачу на теорему Байеса и интрвюер сам знал как ее решить, и раз 5 давали в других местах неверно, интервьер сам решал не правильно и т.д.
brownfox
14.07.2024 10:34+1IMHO, главная задача собеседования - не найти спеца, который за 15 минут выдаст оптимальное решение, а понять, как этот специалист думает. Покрыть тестами всю область компетенции кандидата всё равно не удастся, да и само собеседование для многих - стресс, при котором показать свой максимум нереально.
Я обычно даю задачку на дом с условием на интервью подробно рассказать как именно работает решение и какие ещё варианты возможны. Ну и потрепаться на тему. Т.е. тестовое задание - не фильтр, а затравка для разговора.
aleex
Но почему очень многие берут среднее арифметическое, когда хотят получить время выполнения куска кода? Почему не P05 какое-нибудь или не P50, устойчивое к выбросам на худой конец?
Portnov
Зависит от задач. Во многих задачах важен throughput (самое простое что приходит в голову: файл с тысячами записей нужно обработать во много потоков за минимальное время). В таких случаях правильнее смотреть именно на average time. Но в других задачах, типа того же веба, важно latency. Тогда надо смотреть на процентили: медиану P50 или там P95. Бывает также важно и то и другое, поэтому приходится выводить и avg, и P95.
splarv Автор
Хм, кстати, хороший вопрос. Тут смотря кто где и на кого учился. Большинство учились только в школе и брать среднее арифметическое для них естественно, никакие P05 или P50 они не знают. Я учился на физика в МФТИ и поэтому для меня естественно было бы взять среднеквадратичное (меня учили, что только так правильно). Но среди агрегатных функций PostgreSQL я не нашел функцию которая вычисляет среднеквадратичное или по английский Root mean square (RMS). Поэтому, за неимением лучшего, я беру среднее арифметическое, всё равно эти эксперименты не несут в себе какого-то научного значения, скорее они служат для оценки, что лучше/хуже. И с этим вполне себе справляются. Были бы там случайные выбросы, то при 1000 замерах они бы всё равно сгладились бы.
Akorabelnikov
А как интерпретировать только rms? Для меня как математика логично взять среднее и ско. Это удобно наглядно показать как 5±1мс, тем кто в разных средних и персентилях не разбирается, хоть строгого смысла и не несёт (распределение даже не симметричное в общем случае)
splarv Автор
Вы правы. Похоже по старости лет я перепутал. Это же получается, 30 лет назад всё было. Да, берётся среднеарифметическое и среднеквадратичное отклонение. Для нормального распределения две трети попадает в сигму.
https://old.mipt.ru/upload/medialibrary/111/main.pdf
RMS тоже употребляется в физике, но в другом контексте.
proDan0
- вот и она : stddev
splarv Автор
Это среднеквадратичная погрешность (или стандартная девиация), а не среднеквадратичное значение Root mean square (RMS). И кто только вам респекты ставил?
И это уже было не важно, потому что я вспомнил, что всё же и в физике в этом контексте работают со среднем арифметическим.
0serg
В инженерной записи 5±1мс величина ±1 это не ско а доверительный интервал. И при вычислениях там нередко доверительный интервал стараются оценивать по верхней границе возможной погрешности (буквально 100% доверительный интервал).
splarv Автор
О, так на самом деле нет такого стандарта "в инженерной записи". И в разных отраслях может быть по разному. В физике там пишут сигму, среднеквадратичную погрешность. Это где-то две трети. В каких-то инженерных отраслях там пишут две сигмы, а это 95%. Так что буквально 100% там нет.
0serg
Ну так я и не говорю что есть стандарт. Я говорю что это доверительный интервал а не СКО. Размеры интервала зависят от выбранного p-value и значение p-value может быть буквально написано рядом. Физики нередко берут в такой записи 1 сигму, да. Но это все равно концептуально немного другое, даже если численно запись такая же.
Ну а в инженерных областях например если мы меряем что-то линейкой, то погрешность измерения будет ± 0.5мм с доверительным интервалом таки буквально в 100%. А если мы померяем две длины и сложим их то погрешности зачастую тоже просто сложат вместе хотя в статистическом смысле надо было бы по хорошему считать sqrt(e1^2 + e2^2) - у случайных величин складываются дисперсии а не СКО.
15432
Нас учили медианой усреднять, лучше всего отбрасывает выбросы
aleex
Все же она их не отбрасывает, но слабо чувствительна к ним. А вот отбросить их можно, считая, что крайние N перцентилей это и есть выбросы
Archi_Pro
не ну это очень радикально давайте хотя бы по какому нить критерию отбрасывать например по Шовенэ
tbl
Что в физтехе, что на физфаке МГУ так учат, но не объясняют, почему. Карго-культ какой-то. В итоге выходят физики, умеющие делать лабы "методом научного подгона" (когда результат подгонялся под теорию).
А дело-то всего лишь в том, что
L₂-норма - это самая простая из норм, которая имеет важное свойство непрерывной дифференцируемости на всем пространстве. Это свойство нужно для МНК (понимание вылезает, если его честно выводить из теории, а не как в вузе дают в методичках на вводных лабах на первом курсе: "вот вам метод - пользуйтесь").0serg
Смешались в кучу кони, люди... Что такое "свойство непрерывной дифференцируемости нормы"? О каком "всем пространстве" идет речь? И какое это отношение имеет к МНК? Вы вероятно хотели сказать что L2 - самая простая норма на пространстве непрерывно дифференцируемых функций, но там все равно будет неясно зачем это физикам надо
В реальности использование среднего обусловлено статистикой. Считая что ошибка измерений имеет нормальное распределение (что бывает довольно часто и является разумным вариантом по умолчанию), среднее это лучшая из возможных оценок для истинного значения. Если если ошибки НЕ являются нормальными, но они примерно одинаковы, то в силу ЦПТ среднее - лучший вариант в пределе когда у нас достаточно много измерений. И даже если не выполняется даже это, то существует неравенство Чебышева которая работает для ЛЮБЫХ распределений с конечной дисперсией и дает результат опять же для среднего.
Среднее "ломается" на систематических погрешностях (что актуально кстати для измерения времени работы программы), на некоторых распределениях с тяжелым хвостом и оно не всегда оптимально, но все эти случаи объединяет то что они встречаются не так часто (особенно в физике) и там нет альтернативы которая работала бы везде, надо изобретать свое решение для каждого частного случая. Поэтому и учат "среднему" как наиболее универсальному инструменту который зачастую оптимален или близок к оптимальному.
splarv Автор
В физике с систематическими погрешностями борются другими методами. :) Калибруют приборы. :)
splarv Автор
Да всё просто. Физлабы идут с первой недели первого семестра. И буквально с первой недели первого курса студентам уже надо хоть как-то объяснить как обрабатывать результаты эксперимента.
Потом, ближе к третьему, математика становится гораздо сложнее, но там упор идёт на диффуры.