Популярная задача на собеседовании: сотрудники с максимальной зарплатой в отделе

в 10:00, , рубрики: postgresql, sql, быстродействие, собеседование

Кто ходил на собеседования по устройству на работу, тот знает, спрашивают там всякое и странное. Нередко можно встретить задачу по нахождению сотрудников с максимальной зарплатой в отделе. Причем ваш потенциальный начальник считает, что у этой задачи есть только одно "правильное решение", то, про которое он прочитал в Интернете. Так ли это?

Постановка задачи

Разумеется ваш потенциальный начальник не придумывал ни эту задачу, ни её решение. И задачу и "правильный" ответ он подглядел в Интернете, чтобы демонстрировать своё ментальное превосходство. Мол он эту задачу решил бы "правильно" за секунды, тоже самое должен сделать и потенциальный сотрудник.

Задача формулируется так. Есть база данных, где содержатся сотрудники с их разбиением по отделам и зарплатой. Я пытался прогуглить корень зла. Ссылки меня привели к статье: https://www.jitbit.com/news/181-jitbits-sql-interview-questions/

Это рекомендации по приёму сотрудников в компанию 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;

Но и это не то. Откуда ваш потенциальный начальник взял, что существует только один "правильный" крутой ответ? И он вовсе не тот, который предлагает потенциальный сотрудник? Например отсюда.

https://stackoverflow.com/questions/16799640/employees-with-largest-salary-in-department

По-видимому эта задача на собеседовании стала популярной не только в нашей стране. Популярна настолько, что её обсуждают в 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.

https://habr.com/ru/companies/domclick/articles/516538/

Потому что в силу своей ограниченности потенциальный начальник знает только одно единственное "правильное и крутое" решение на Patroni, он об этом в Интернете прочитал. Тоже самое касается и других вопросов. Любое хорошее решение, которое будет выходить за рамки ограниченности потенциального начальника, будет расценено как ошибка или демонстрация некомпетентности.

Автор: Олег Самойлов

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js