Comments 198
Но почему очень многие берут среднее арифметическое, когда хотят получить время выполнения куска кода? Почему не P05 какое-нибудь или не P50, устойчивое к выбросам на худой конец?
Зависит от задач. Во многих задачах важен throughput (самое простое что приходит в голову: файл с тысячами записей нужно обработать во много потоков за минимальное время). В таких случаях правильнее смотреть именно на average time. Но в других задачах, типа того же веба, важно latency. Тогда надо смотреть на процентили: медиану P50 или там P95. Бывает также важно и то и другое, поэтому приходится выводить и avg, и P95.
Хм, кстати, хороший вопрос. Тут смотря кто где и на кого учился. Большинство учились только в школе и брать среднее арифметическое для них естественно, никакие P05 или P50 они не знают. Я учился на физика в МФТИ и поэтому для меня естественно было бы взять среднеквадратичное (меня учили, что только так правильно). Но среди агрегатных функций PostgreSQL я не нашел функцию которая вычисляет среднеквадратичное или по английский Root mean square (RMS). Поэтому, за неимением лучшего, я беру среднее арифметическое, всё равно эти эксперименты не несут в себе какого-то научного значения, скорее они служат для оценки, что лучше/хуже. И с этим вполне себе справляются. Были бы там случайные выбросы, то при 1000 замерах они бы всё равно сгладились бы.
А как интерпретировать только rms? Для меня как математика логично взять среднее и ско. Это удобно наглядно показать как 5±1мс, тем кто в разных средних и персентилях не разбирается, хоть строгого смысла и не несёт (распределение даже не симметричное в общем случае)
Вы правы. Похоже по старости лет я перепутал. Это же получается, 30 лет назад всё было. Да, берётся среднеарифметическое и среднеквадратичное отклонение. Для нормального распределения две трети попадает в сигму.
https://old.mipt.ru/upload/medialibrary/111/main.pdf
RMS тоже употребляется в физике, но в другом контексте.
PostgreSQL я не нашел функцию которая вычисляет среднеквадратичное
- вот и она : stddev
В инженерной записи 5±1мс величина ±1 это не ско а доверительный интервал. И при вычислениях там нередко доверительный интервал стараются оценивать по верхней границе возможной погрешности (буквально 100% доверительный интервал).
О, так на самом деле нет такого стандарта "в инженерной записи". И в разных отраслях может быть по разному. В физике там пишут сигму, среднеквадратичную погрешность. Это где-то две трети. В каких-то инженерных отраслях там пишут две сигмы, а это 95%. Так что буквально 100% там нет.
Ну так я и не говорю что есть стандарт. Я говорю что это доверительный интервал а не СКО. Размеры интервала зависят от выбранного p-value и значение p-value может быть буквально написано рядом. Физики нередко берут в такой записи 1 сигму, да. Но это все равно концептуально немного другое, даже если численно запись такая же.
Ну а в инженерных областях например если мы меряем что-то линейкой, то погрешность измерения будет ± 0.5мм с доверительным интервалом таки буквально в 100%. А если мы померяем две длины и сложим их то погрешности зачастую тоже просто сложат вместе хотя в статистическом смысле надо было бы по хорошему считать sqrt(e1^2 + e2^2) - у случайных величин складываются дисперсии а не СКО.
Если я за прошедшие десятилетия не забыл напрочь основы метрологии, то под 250±0,5 мм подразумевается именно 100% изделий, а всё, что за пределами этой выборки - брак.
Оффтоп
Единственное, что неизгладимо врезалось в память, это лабораторка, на которой мы измеряли отклонение шага резьбы на болту с помощью оптического микрометра, и у меня на пяти витках погрешность получилась ровно 0 - у меня не хотели результат принимать, т.к. "не бывает идеальной резьбы", а показания я "не с лимба списывал, а на калькуляторе считал"... это был второй случай, когда у меня не хотели принять честные результаты проведённой лабораторки - первый раз мы меряли температурную зависимость проводимости полупроводника, и у меня никак не строился линейный график - был чёткий перелом, и по температуре этого перелома выходило, что в муфельной печи мы гоняли не кремниевый, а германиевый транзистор... после занятий разобрали стенд с лаборантом и извлекли из него... ГТ311 - лабораторку зачли =)
Нас учили медианой усреднять, лучше всего отбрасывает выбросы
меня учили, что только так правильно
Что в физтехе, что на физфаке МГУ так учат, но не объясняют, почему. Карго-культ какой-то. В итоге выходят физики, умеющие делать лабы "методом научного подгона" (когда результат подгонялся под теорию).
А дело-то всего лишь в том, что L₂-норма - это самая простая из норм, которая имеет важное свойство непрерывной дифференцируемости на всем пространстве. Это свойство нужно для МНК (понимание вылезает, если его честно выводить из теории, а не как в вузе дают в методичках на вводных лабах на первом курсе: "вот вам метод - пользуйтесь").
Смешались в кучу кони, люди... Что такое "свойство непрерывной дифференцируемости нормы"? О каком "всем пространстве" идет речь? И какое это отношение имеет к МНК? Вы вероятно хотели сказать что L2 - самая простая норма на пространстве непрерывно дифференцируемых функций, но там все равно будет неясно зачем это физикам надо
В реальности использование среднего обусловлено статистикой. Считая что ошибка измерений имеет нормальное распределение (что бывает довольно часто и является разумным вариантом по умолчанию), среднее это лучшая из возможных оценок для истинного значения. Если если ошибки НЕ являются нормальными, но они примерно одинаковы, то в силу ЦПТ среднее - лучший вариант в пределе когда у нас достаточно много измерений. И даже если не выполняется даже это, то существует неравенство Чебышева которая работает для ЛЮБЫХ распределений с конечной дисперсией и дает результат опять же для среднего.
Среднее "ломается" на систематических погрешностях (что актуально кстати для измерения времени работы программы), на некоторых распределениях с тяжелым хвостом и оно не всегда оптимально, но все эти случаи объединяет то что они встречаются не так часто (особенно в физике) и там нет альтернативы которая работала бы везде, надо изобретать свое решение для каждого частного случая. Поэтому и учат "среднему" как наиболее универсальному инструменту который зачастую оптимален или близок к оптимальному.
Да всё просто. Физлабы идут с первой недели первого семестра. И буквально с первой недели первого курса студентам уже надо хоть как-то объяснить как обрабатывать результаты эксперимента.
Потом, ближе к третьему, математика становится гораздо сложнее, но там упор идёт на диффуры.
Ну и нафига идти работать в такие места? Где есть начальник который ничего не понимает.
А ещё решение можно на кликхаусе собрать, собственную СУБД для него сделать или вообще свой мемкеш бесконечный построить. И на квантовом компьютере. И и что
Ну так в этом и есть обратная сила собеседования. Узнаешь еще и какой начальник, насколько разумный. :)
Что же касается ваших предложений по расчёту сотрудников с максимальной зарплатой в отделе, так задачу не я придумал. Сами предложите это на собеседовании.
Я постоянно эту задачу спрашиваю на собесах. На джунов. Принимаю любой вариант. Где-то 50% джунов решить не мугут никаким вариантом. Примерно 5% знают два варианта.
Ну на самом деле задача вывести строку содержащую максимальное или минимальное значение вполне себе реальная. Я смутно припоминаю, что что-то подобное приходилось решать по работе. Поэтому я интуитивно сразу написал вариант, который уже был в подкорке, ничего на ходу не придумывал. И в этом смысле эта задача, как и другие задачи от JitBit вполне себе полезная, как у них и написано, позволяет выявить людей у которых уже есть реальный опыт работы.
Но вот когда собеседователь начинает требовать, чтобы я угадал его мысли и написал "единственный правильный и крутой" ответ, который на проверку оказывается худшим, это в первую очередь говорит, что у потенциального начальника нет никакого практического опыта работы.
А на какую позицию собес, бэкенд разработчик?
Ну и нафига идти работать в такие места? Где есть начальник который ничего не понимает.
Вот необязательно. Начальник, который задает такие вопросы на собеседовании, может потом в реальной работе прислушиваться к вашему мнению. В конце концов он вас выбирает на экспертную должность, то есть ищет человека, способного разбираться в таких вещах, а сам таким экспертом быть не должен, но отбирать кандидатов ему как-то надо.
Не бывает такого что до подписи в трудовом договоре уровень доверия - ноль, а сразу после - 100%. Да даже на 10% доверие не скачет. Оно зарабатывается и как правило не быстро. Скажу больше, человек с картиной мышления "есть два мнения - мое и неправильное", в принципе не подбирает в команду экспертов. Он выбирает "подпевал" и/или козлов отпущения. Сам провожу собесы, несмотря на десятки лет работы в IT я выслушиваю оппонента и как минимум пытаюсь понять на чем базируется уверенность. На примере из статьи, я бы вообще не заморачивался с "единственным правильным" решением. Соискатель шарит в базах это видно, а какие здесь-сейчас оптимизации зарулили - да вообще похрен. Я лично выбираю более читаемые варианты с CTE (Common Table Expressions). Но и на этом не настаиваю. Мои предпочтения это чисто мои.
Хотел бы я было поставить респект, но прочитал про CTE. То что вы относитесь к CTE только как косметическому украшению уже вас характеризует как потенциального начальника. С CTE всё не так просто. Если до 12го Postgresql СTE не оптимизировались и ими можно было как указать PostgreSQL использовать более оптимальный план выполнения запроса (с точки зрения разработчика, причем не всегда эта точка зрения правильная), так и наоборот, можно было бы ухудшить план. Т.е. это как бы "оптимизация", но которая иногда приводит к полностью неработающему сервису. После 12го их функционал несколько изменили несовместимым образом, так это вообще головная боль при апгрейде на 12ю версию. Просмотром кода это не предсказать, даже если бы в коде были SQL запросы.
Это я к тому, что использование CTE надо оценивать вовсе не с точки зрения читабельности кода. Более того, поскольку в отличии от всякой экзотики, вроде курсоров, CTE используются очень часто, практический ежедневно, то это хороший вопрос для собеседования, их надо держать в памяти, когда они оптимизируются, а когда нет.
задумайтесь, человек набирает экспертов, используя задачи и решения, которые он не понимает, он блин даже к встречи с этими экспертами не готов. а конкретно в этом кейсе все эксперты пройдут мимо, кого он наберет сказать сложно, к кому он в конечном итоге будет прислушиваться ? вполне понятно.
CREATE INDEX ds1 ON employees (department_id, salary);
Странный индекс, чисто под эту задачу. В реальной жизни я бы рассчитывал на индекс только по департаменту.
Можно тест ещё под индекс по департаменту?
Вы правы. Если не заморачиваться над оптимизацией именно этого запроса (а смысл собеседования был именно в том, чтобы заморочиться, чтобы написать его "правильным и крутым") и специального индекса не создавать, то индекс по department_id как по foreign key там должен быть, обычная практика.
Можно, чего только не сделаешь для любимых читателей:
method | execution_time
--------+--------------------
rank | 0.7331189993619919
max | 0.5216920003294945
window | 0.6920570016503335
Хм, опять, чтобы пройти собеседование и устроиться на работу, надо предложить самое худшее решение. Да что такое-то?
Спасибо!
Любой вариант с применением индекса, что по департаменту, что по департаменту с зарплатой, получился примерно на порядок быстрее без оного. Что наводит на мысль, что применение индекса куда эффективнее, чем выбор "правильного" решения. Тем более, что "одноразовые" выборки в реальной жизни имеют тенденцию становиться дашбордами и регулярными отчетами.
Маленькая поправочка (простите). Все-таки, ddl - это язык, а Вы, все же, написали запрос - так ведь?
Хм, 2000 записей очень мало, скорее всего вообще все данные будут в памяти.
Возможно пробежаться по курсору в процедуре будет быстрее всего.
Или вообще на бэке посчитать.
Вот если 200000 employers и около 50000 подразделений - то все интереснее )
Устроиться в корпорацию где 200 тысяч сотрудников или больше... Кстати можно, это же как раз будет российская армия. Вот только вместо компьютера вам там дадут что-то другое. :) Но можете попробовать.
Курсор и процедура не прокатит. В таких задачах на собеседовании использование процедур запрещают, надо уложиться в один запрос.
Так это специально было сделано, чтобы все данные были в памяти. Машина 128 ОЗУ, shared_buffers 32GB, все в памяти с большим запасом. Ведь идея была в том, чтобы проверить алгоритмы, а не то, как работает с винчестерами postgres в виртуалке под виндой.
Кстати можно, это же как раз будет российская армия
Ну необязательно, достаточно в газпром попасть, у них порядка 500К сотрудников.
А еще можно в Wal-Mart, они вроде как мировые рекордсмены, у них 2,2М сотрудников)
Ведь идея была в том, чтобы проверить алгоритмы
Как-раз сложность алгоритмов лучше проверять на больших данных, на маленьких при тестировании, например O(n), может легко быть медленее чем O(n*log(n)) просто потому-что у первого алгоритма каждый шаг стоит чуть больше. Но на больших данных первый будет в сильном отрыве в несколько раз от второго.
Ну, почти 10 таких компаний в РФ наберётся: https://www.forbes.ru/biznes/503283-15-krupnejsih-rossijskih-rabotodatelej-s-cislom-sotrudnikov-bolee-100-000-celovek?image=477074
В мире ещё больше :)
Зачем вложенные запросы, оконные функции и группировки? Давайте подойдем к задаче с точки зрения того, что 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Такие сотрудники, что в их отделе нет никого с более высокой зп. Понятно, что не очень эффективно, но прикольно.
На собеседованиях проверяют сам факт того, что Вы знаете вышеперечисленное, а не то, что знаете лучше. Вот не знаете решение через оконные функции - начальник Вас не пустит. Знаете - хорошо.
Т.е. надо зубрить самые бессмысленные решения широко распространённых в Интернете задач? Ну да, победная стратегия.
Именно так.
Perception is reality.
В худшем случае вы дадите социально одобряемый ответ, и покажетесь "своим".
В лучшем - вы сделаете пометку, что это не самый оптимальный способ, разбирались, знаете нюансы, сейчас продемонстрируете... и либо пройдете тест на "своего" (ага, мы тоже знаем!), либо удивите и продемонстрируете экспертизу, после чего решение по найму на этом этапе будет де-факто принято.
Любое "удивите и продемонстрируете экспертизу" - ответ неправильный. Хуже ситуация получается, когда собеседуют двое: тех.специалист и эффективный менеджер. И когда их тех.специалист начинает отчаянно вешать лапшу на уши, вообще не понимая, как это работает (так было с проектом NRD), он ни за что не признается, что облажался и будет всяческий подтасовывать информацию в спорных вопросах, лишь бы его начальник не узнал, какое он дно. А эффективный менеджер оценивает только кто говорит более уверенным голосом. :) Если ты вешаешь лапшу на уши очень уверенно - получишь работу.
Подтверждаю. Вышла на одну такую работу и долго училась у коллег как разговаривать с менеджерами, довольно противный навык, но нужен был для выживания :(
Вас научили врать твёрдым и уверенным голосом? :)
Думаю, что что-то около того - я даже не в начале трудовой карьеры, а будучи студентом, освоил навык уверенно утверждать что-либо, о чём имею лишь самое поверхностное понимание, и при общении с преподавателями, а в последствии и руководителями, стоящими на несколько ступеней тебя выше, этот навык иногда пригождался. То есть, нести пургу с важным видом, порой, бывает выгодно. Увы.
Иногда такие кадры ловят удачу там, где ее и быть не может ))) https://www.liveinternet.ru/community/1224098/post33848889/
Хех! Я подобным образом Гос на военке сдал - все 3 года провёл в кабинете начальника цикла, набирая документы кафедры, на госэкзамене вытащил билет, по которому знал лишь как выглядит упоминаемое оборудование, в итоге "на пальцах" (ну, и на самих узлах и приборах, присутствующих в кабинете) ответил устройство и способы применения за пару минут (вместо отведённых 15), не получил дополнительных вопросов и ушёл нервно курить... в итоге - такой же "отл.", как и по приведённой ссылке - никто даже не ожидал, что "писарь" сможет в нужном порядке к нужным стендам подойти.
Я подобным образом Гос на военке сдал
Когда местные будут у меня интересоваться, почему русские войска ведут себя так беспомощно — я буду показывать этот комментарий.
Ну, и ещё особняк Иванова.
Оооо! Про мои отношения с армией можно фельетон писать - мало того, что моё личное дело умудрился потерять военкомат, так ещё, когда его восстанавливали (после моего обращения за удостоверением офицера запаса), мне вписали не ту ВУС, по которой я обучался (и сдавал тот самый "Гос")... а недавно я целую неделю провёл в "группе запаса 2", пока не подняли возрастной ценз на 5 лет и я снова не оказался в "группе запаса 1", так что офицер из меня не то, что "так себе", а вообще "никакой". Тут надо принимать во внимание, что все мои "армейские приключения" происходили в 90-е годы, тогда вообще не было уверенности, что военная кафедра нас "выпустит"... да, вообще, с уверенность было плохо.
Думаешь, в армиях других стран подобного быть не может по определению? Вояки везде не академики, мягко говоря.
Из всех собеседований два стоят особняком, то в Национальный Российский Депозитарий и в Промсвязьбанк, через который проходит гос. и оборонный заказ. Обе конторы официально крышует ФСБ. И только там на собеседовании собеседовали мне нагло и беспардонно врали, самым уверенным голосом.
Например в НРД вешали лапшу на уши, что если в столбце одно значение преобладает 100, то он считается "нерепрезентативным" и его postgresql никогда в индексированном поиске использоваться не будет. Я возражал, что не бывает нерепрезентативных столбцов, всё дело в конкретном значении и Postgresql не использует поиск по 100 потому что он находится в списке наиболее часто встречаемых значений. И для доказательства своей правоты предложил вместо 100 выбрать 1. На что собеседователь сверился с какой-то табличкой и выбрал 5, как я понимаю еще одно число из списка наиболее часто встречаемых значений и тем самым "доказал" мою неправоту. А еще там меня убеждали, что если в процедуре встречается begin end, то это "анонимный блок" и входя в него postgresql всегда открывает вложенную транзакцию.
В Промсвязьбанке, меня убеждали, что если написать выражение, например:
with cte as (select * from table) delete from cte; то оно нормально отработает и якобы он сам лично это протестировал и так работает начиная с версии 9.4. Разумеется ложь.
Парадокс в том, что жулики занимают ведущие, руководящие посты в тех.отделах именно там, где ФСБ следит, чтобы этого не было. Другими словами значимых для государства конторах. А в обычных коммерческих фирмах я ни разу не встречал ничего подобного, разная степень знаний, но всегда адекватное поведение, никаких наглых развешиваний лапши.
Так что с вашими талантами нести пургу, идите туда. Там вы отлично впишитесь в коллектив.
Так, моё первое место работы - ФДС (в последствии РосАвтоДор, подразделение МинТранса) - Вы весьма близко угадали - именно в окологосструктурах данный навык чуть ли не обязателен. С прошлого века с ними не связан, но когда приходилось пересекаться - приходилось извлекать из глубин памяти сей навык. Отсюда и финальное "Увы.", и "выгодно", а не "полезно". Иногда аж вздрагиваю, вспоминая свою первую работу.
Ну да, тут вся статья про неэффективные, но прикольные способы. :) Поставил респект за изобретательность. 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. Но с точки зрения потенциального работодателя, я думаю вы произведёте впечатление, это единственный мне известный вариант без вложенных запросов.
В 10 раз медленнее на каких-то 2000 записях, чем больше записей в таблице, тем больше будет отставание. Впечатление производит, да, настолько сильное, что яб на месте интерьюера схватился-бы за сердце и был категорически против оффера. :)
Хорошо, что вы не на месте интервьюера!
Весь вопрос в том, есть ли на собесе возможность хотя бы план запроса посмотреть. Вряд ли с ходу без этого предугадаешь, как он будет отрабатывать.
Почему же, предугадаешь. В моем шутливом примере, до которого некоторые начали докапываться с точки зрения производительности, хотя я сразу написал, что она там плохая и что это скорее забавный пример, сразу видно, что тут практически декартово произведение, в рамках департамента.
Вопрос то тут не а вас, а в СУБД. Дать стопроцентную гарантию, как он будет выполняться - нельзя, и вдруг оптимизатор отработает отлично. Пока план запроса не посмотришь - однозначные выводы не сделаешь. Ну а декартово произведение - ну и что такого, там есть ограничения, вдруг чудо бы случилось и оптимизатор бы вывез
Я перевел статью с JitBit и выложил в Хабр, как раз ту, где была эта задача. И там говорят, что ни кандидатам всегда предоставляют компьютеры подключенные к базе данных. Работай в привычных условиях.
А в России да, раньше надо было писать что-то ручкой на огрызке бумаги, сейчас так вообще тебе показывают скриншот, который даже не скопипастишь и надо решить задачу в уме. И от непривычных условий, которые не наработаны практикой, начинаешь стрессовать.
А что касается Красного Волка, то да, это была остроумная шутка, которая умнее, чем кажется. Дело в том, что некоторые (может многие) потенциальные начальники, в том числе и те, кто отписывались в комментариях, имеют странные предпочтения. Мол, если нет вложенных запросов, значит вариант хороший. А поскольку это единственный мне известный вариант без позапросов, получается вариант Красного Волка с точки зрения собеседователя самый лучший. А с точки зрения человека с реальной практикой отладки запросов очевидно, что всё будет наоборот. Декартово произведение, действительно, видно. :)
salary money NOT NULL
Давно деньги в money хранят?
Как человек, которые ее задает на собеседованиях наверное уже скоро как 20 лет, могу открыть секрет - большинство людей, которые называли себя SQL-програмистами, data инженерами ее не решают от слова совсем. И даже если даже не 5 секунд, а минут 10.
Просто остальных (в смысле другие позиции), которые просто вписали в резюме SQL и не краснеют, когда говорят, что знают и очень хорошо я даже умолчу
Причем явно говоришь, что надо просто запрос, который вернет правильный ответ, не надо думать над оптимальным решением (что может не иметь смысла без реальной базы) - не помогает
Хорошую тему затронули, оконные функции умею писать, но они реально в большинстве случаев пригождались только на собеседованиях) И как раз мне запомнилось в положительном ключе собеседование, где я написала решение какой-то подобной задачи как раз "социально одобряемым" способом, но в итоге обсудили, что есть риск, что оно не такое уж оптимальное
А можно закину задачек, для которых придумали оконные функции, и которые попадались мне на работе? Вариант "на бэке посчитать" не предлагать - вся работа идет в хранилище данных:
Есть таблица истории покупок товаров клиентами. Сегментировать клиентов в соответствии с суммой потраченных средств согласно нижеприведенной сегментации: Top 5%
High 20%
Middle 30%
Others 45%Вторая задачи достаточно сложная, чтобы давать на собеседовании, но можно подумать над ходом решения:
Имеется широкая сеть в ритейле с учетом партнерских торговых точек, и некотрые кассовые аппараты разбивают один чек на несколько чеков (то есть каждый товар в корзите проходит отдельной транзакцией), менжду которыми нет явной связи. Связь только косвенная: такие чеки имеют одинаковые идентификаторы ТТ (троговой точки), и номер аккаунта клиента (account_id). При совпадении этих параметров будем сверять время с кассового аппарата pos_time (который также является атрибутом операции) и если между операциями разница не более 5 минут, то объединяем их в один чек. Цепочки могут быть транзитивными. Результатом объединения будет добавление нового поля agg_cheque_id, который будет равен первой операции в объединенной цепочке.
Не нужно писать скрипт обновления (merge или update), достаточно написать select, который выведет операции с расчитанным agg_cheque_id.
Да, это валидно, но... ведь не утверждалось, что оконные функции действительно всегда плохи. Посыл и статьи, и комментариев вроде моего в том, что не стоит по умолчанию считать, что их использование отделяет условного сеньора от джуна или хорошего кандидата от плохого (и в принципе не стоит зацикливаться на каком-то конкретном ожидаемом решении задачи, просто потому что оно понравилось/популярно/не знаешь других)
Смотрите. Все же задача собеседования выявить что специалист опытный и рукастый и он сможет решать поставленные перед ним задачи самостоятельно. Например начав с предварительного чтения документации, если он подзабыл эту тему, главное помнить, где что есть и куда смотреть. Например я за 25 лет ни разу не сталкивался с задачами, которые требовали бы оконных функций, по крайней мере, с момента их появления в PostgreSQL. И это не моя вина, просто специфика работодателя их не требовала, они больше ориентированы на каких-то финансистов. И за последние пять лет мне потребовался рекурсивный поиск только один раз (его тоже часто спрашивают на собеседовании), потому что веб программисты микросервисов не заморачиваются таблицами со ссылками на самих себя. Но это же не значит, что я не смогу справиться с работой, пролистав документацию в течении 15 минут, просто, чтобы освежить это в памяти.
У слову ваша 2 задача это явный bad design. Не стоит на собеседовании спрашивать как костылить вашу систему, вредно для репутации компании.
# Вы серьёзно ждете что кто-то ответит на вторую задачу на собесе?: 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;
Я думаю это реальная задача, которую он сам не смог решить до сих пор. Выложил под видом якобы задачи на собеседование, в надежде, что кто-то из комментаторов напишет ему запрос.
Можно даже проще, без рекурсии. Если для поля is_new_group сделать сумму набегающим итогом, то получатся номера групп. Была у меня похожая задачка в реальной практике.
Господи, зачем столько писать про это? Если вам нужен специалист по БД, а не просто energizer-заяц, который в работе с БД знает только 4 буквы C, R, U, D и итератор, но зато бьет в барабан со скоростью и позитивом свежей батарейки - то он должен начать писать ответ, еще не дослушав задание, и время его выполнения долго быть равно времени набивания DML на клавиатуре. Любой другой наблюдаемый результат - это провал. Такой чел в эффективной работе с БД вам не поможет- будет, как жонглер в цирке крутить многоуровневые циклы (что итераторы в ПЯП, что многоэтажные курсоры прямо в БД - результат один), манящие O(1), O(N), O(N log N) уплывут от вас дальше Антарктиды, а на продакшене вы будете затыкать performance-дыры, выклянчивая у IT-отдела планки памяти под завязку, и сервера в стойку, чтобы хоть как-то бороться с data growth rate.
Эффективная работа с БД - это образ мышления. И он ортогонален процедурному (тредовому) у фуллстеков. Главная задача на собеседовании на БД-инженера - понять, есть оно или нет.
Ну и? А вы с кем и о чем тут спорите? Мне кажется вы даже не поняли в чем тут суть и уже начали набивать коммент "со скоростью и позитивом свежей батарейки". Как вы и написали, начали писать ответ даже не разобравшись, а в чем было задание. :)
Хм, Вы действительно считаете, что задача взятия строк с максимальным значением какого-нибудь свойства, внутри подмножества, определяемого другим свойством, стоит того, чтобы размазывать ее по столу слоем толщиной в 1 молекулу? Со всеми этими заголовками Постановка задачи, Варианты решения? И почему вы так уверены, что сферическому начальнику в вакууме нужно будет обязательно продемонстрировать знание оконных функций? Мой заяц бьет в барабан именно по этому поводу ;)
Не просто знание оконных функций, а то единственное решение через rank(), про которое он прочитал в интернете. Так он сам так говорит. :) Ну или отчаянно на это намекает.
А статья вовсе не про эту задачу, если вы не поняли, а про особенности собеседований и собеседователь.
Мне кажется статья больше про особенность собеседуемых.
Ну так вменяемый кандидат должен выкатить несколько решений - сразу, или на первый же вопрос собеседующего об этом. Но если статья про особенности собеседований и собеседователя - то почему 90% из того, что не является оформляющим вводные текстом - это код, а не психологический портрет собеседующего? Если в статье стейтменты, цифры результатов запусков и execution plan’ы - как заяц догадается, что статья про особенности экзаменаторов?
PS - про то, что ожидаемый (ловушечный) метод по перформансу не лучший - и так понятно. Всякое универсальное хуже специального (С). Попробуйте без оконных решить задачу более общего вида (скажем, найти записи на n-ом месте по зарплате) - и сравните трудоемкость execution plan’ов.
Никто не против того, чтобы использовать оконные функции там где нужны.
Тезис этой статьи, который я и написал в выводах, это то, что собеседование можно построить таким образом, что на работу будут набирать только и исключительно только сотрудников, которые предлагают самый худший вариант решения проблемы. Выглядит как забавный парадокс. Но столь громкое утверждения нельзя было подтвердить технической аргументаций, чтобы не выглядело голословно. Вы это не оценили.
Создавать индексы под каждый запрос так себе решение. И если индекс по ИД отдела логичен и создаётся на автомате (тем более что скорее всего там будет внешний ключ), то включение в него зарплаты уже выглядит сомнительно. А если завтра попросят список всех сотрудников, нанятых последними в своих отделах? Ещё индекс, с ИД отдела и датой приёма на работу?
Второй способ норм и его на собеседовании вполне стоит принять, но надо понимать, что это частный случай и оконные функции намного более мощный инструмент и владеть им необходимо. Ну, ок, желательно.
Я уже отвечал на подобный коммент.
https://habr.com/ru/articles/828728/comments/#comment_27040670
Подчеркну, мы же не рассматриваем реальную продовую базу данных с реальными задачами. Речь тут идёт о том, чем собеседование отличается от реальной работы.
Да, потом увидел... Тут ещё момент, что соотношение 2000 сотрудников на 20 подразделений не уверен, что жизненное, 100-200 подразделений будет ближе ИМХО, по крайней мере в ИТшных конторах так. Из-за этого вариант с max должен быть уже не так быстр. Тут заметим, что решение, производительность которого сильно зависит от семантики данных, уже не очень хорошо.
Собеседование не может не отличаться, это понятно, и данная задача как раз и хороша тем, что даёт возможность обсудить разные аспекты. Не знаю, где Вы видели таких начальников, которые бы требовали единственно верного решения, сдаётся мне, таких не бывает :о)
О, и не такие бывают. Как-тот раз, лет пять назад, проходил собеседование в одну контору, которая работала на правительство. Собеседовало меня два человека, тех.специалист и эффективный менеджер. У тех. специалиста претензий ко мне не было. Отшил эффективный менеджер, который сделал психологическое наблюдение, что я говорю не достаточно твёрдым и уверенным голосом.
Есть у меня на одном проекте такой персонаж, который знает все эти функции и выверты с подвывертами... Но если эти знания не подкреплены логикой иои логика есть, но своя - альтернативная, то это путешествие по минному полю с завязанными глазами.
-- Почему в базе, вдруг, исчезли все внешние ключи?
-- Я их убрал, т.к. они мешали вставить данные: ошибки вылетали.
-- Так в том же и смысл, чтоб обеспечить целостность базы!
-- Я все могу обеспечить и так.
Или таблицы без ключей и индексов и с сотнями столбцов, чтоб все в одной таблице хранилось, а то скорость выборки низкая. Но зато рэнки, партишены и т.д. и т.п. от зубов отскакивают!
Ну, если у него вылетали ошибки целостности данных и именно поэтому он убрал внешние ключи, так значит целостность данных он уже не обеспечил.
Может, он таблицы заполнял в алфавитном порядке, а не как предполагает их иерархия :о)
Отключение констрейнтов и индексов в принципе практикуется при разного рода массовых заливках данных, но потом, конечно, нужно всё вернуть.
Одно дело отключить, другое - удалить :)
Просто отсутствие базовых знаний приводит к такой каше в голове.
Да, так работает pg_dump, только он не констрейнты отключает, а триггеры, которые их проверяют. Вообще все триггеры. Но вы это даже не заметите. А если даже вы это заметили, значит ваш сотрудник уже облажался.
select 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);
Похожее было, но у вас есть отличия. Во первых 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()) запроса у меня. Где-то в сорок раз медленнее.
Я думал будет задача про стеклянные шарики или про заезд из 25 лошадей, а тут про базы данных оказывается.
Задача выглядит разовой, кажется, проще сделать в экселе.
Все три решения выдадут дупликаты, если у двух сотрудников одинаковая и максимальная зарплата. Нужно использовать rownumber вместо rank и сортировать по имени дополнительно.
Если у двух разных сотрудников одинаковая зарплата, то это уже не дубликаты. Более того, если вы имели хоть какое-то отношение к математике и решали, например, уравнения, то ответом решения задачи будет все возможные решения. Написать только одно - грубая ошибка.
Кандидат в ситуации, где возможны разночтения, упирается в один вариант и защищает его до конца. На критику реагирует оскорблениями. Вся суть этого вопроса и подобных интервью.
Кандидат в ситуации, где возможны разночтения, упирается в один вариант и защищает его до конца.
А Вы бы желали, чтобы кандидат пытался выяснить, чего постановщик задачи реально хотел? Будьте осторожны в своих желаниях: они иногда сбываются!
У Вас в статье по ссылке хороший пример как не надо делать. Я жду что кандидат спросит - а зачем это Вам нужно. Такого можно брать.
Я жду что кандидат спросит - а зачем это Вам нужно. Такого можно брать.
Совершенно верно. "Кандидат" в статье по ссылке откровенно издевается над интервьюером — он это в самом начале статьи заявляет.
Я, например, всегда после объявления задачи начинаю разговор с what is the problem you are trying to solve? (какую проблему вы пытаетесь режить?), потому что обычно постановка задачи — из серии "как правильно забивать гвозди микроскопом?"
Тут лучше подойдёт другая функция постгре
Пишу с телефона по памяти, но здесь должно сработать и
select distinct on(department_id) name, salary from employees group by department_id order by department_id, max(salary), name
Базы данных надо любить, многие молодые ребята их не любят
Ох, distinct on() это не функция. Это во первых. Во-вторых ваш запрос не работает. В третьих при его написании вы допустили грубые ошибки. В четвертых вариант решения с помощью distinct, действительно, существуют, но они выдают только одного сотрудника с максимальной зарплатой, а в случае если в отделе несколько сотрудников с максимальной зарплатой, их надо вывести всех.
в случае если в отделе несколько сотрудников с максимальной зарплатой, их надо вывести всех
ну это вы положим на ходу выдумали, в оригинальной задаче такого требования нет.
Да, поспешил, согласен.
Оно бы работало без name. Но тоже пожалуй не оптимально быстро.
Самый быстрый - это простой вариант от автора, который приведен первым, а вот ранк очевидно медленнее.
Что забавно, один мой достаточно умный сотрудник недавно написал ровно такой запрос с ранком.
И я смог ему показать решение побыстрее.
А то что я тут ошибся, увы, бывает со мной и не редко, признаю. Главное учиться. И делать.
Мой посыл был в том что молодежь реально не очень любит sql. А он интересный и мощный.
Больше нравится вариант с оконной функцией, компактно получилось)
/* 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;
Больше нравится вариант с оконной функцией, компактно получилось)
/* 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;Ваш первый вариант, грубая ошибка. Допустим у одно сотрудника максимальная зарплата по отделу 200. А у другого такая же зарплата, но он в другом отделе и у него зарплата там не максимальная. У вас второго тоже выведет.
Второй вариант, там ошибка еще грубее. Вы выведите сотрудников с минимальной зарплатой в отделе.
Третий. Да, это первое, что приходит в голову и на проверку оказалось что лучший вариант. У меня такой же, только первый, под именем max.
Не взяли то наверное не из за ответа на джуновую задачку (очевидно что хардскиллы выше необходимого на джуновый уровень), а скорее из за неумения общаться и излишней самоуверенности?
Btw, в реальности предпочту решение через rank, так как на производительность в данном случае пофиг, да и индекса по salary скорее всего не будет. А решение с rank не делает полноценных подзапросов/джойнов, и делает в явном виде именно то что требуется в задаче без хаков.
Моя любимая задачка про оконные функции:
Есть файл (или табличка, как удобнее кандидату) куда пишутся значения показателей датчиков. Каждая запись содержит таймстемп, идентификатор датчика, и набор значений его показателей в указанный момент времени. Значения показателей меняются сильно реже интервала считывания. Нужно отфильтровать записи, в которых не происходит изменения значений показателей.
Задание со звёздочкой для оригинальной задачи (про зарплаты) - как решить её через оконные функции, но без сортировки.
И как вы собираетесь решать через rank() без подзапросов? Без подзапросов я только одно решение в комментах видел и оно было вовсе не через rank(). И да, с ужасной производительностью.
select * 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
Видно, что первые два способа отлично разобрались как использовать этот индекс
Первые два метода работают так же, как и раньше.
Похоже, что значение для window во втором тесте у вас какое-то неправильное, т.к. оно намного ближе к rank, чем к max.
А куда делось очевидное
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Не претендую на "быстрейшее решение по скорости выполнения" — это просто то, что немедленно приходит в голову.
Смотрите, в вашем варианте если в подразделении у двух сотрудников будет максимальная зарплата, то выведет только одного. Это уже неправильно.
Условие задачи изменилось после того, как я запостил комментарий — в нём отстутствовало требование "всех сотрудников, у кого максимальная зарплата". Потому-то я и удивился — "а чего нет такого очевидного решения?"
Это обычное правило в математике начиная со школы и решения квадратных уравнений. В ответе на задачу должны быть приведены все решения задачи. А иначе задача не решена. А в этом контексте и смысла невозможно придумать выводить только одного сотрудника, если в отделе два таких.
А на собеседованиях есть другое обычное правило: "Всё, что явно не оговорено в задании, кандидат может выбрать на своё усмотрение". Ну, если это не собеседование на позицию телепата, конечно.
Ну смотрите. В отделе два сотрудника с максимальной зарплатой. Вы выводите только одного. Причем случайного. Как вы объясните, почему у вас возникло такое "усмотрение"? Потому что так вам было ленивее и проще? :) Даже не смотря на то, что вы придумали какое-то "негласное правило на собеседовании", которого нет, на собеседовании вы демонстрируете именно то, как вы потом и будите работать. Если так, то умный человек вас на работу не возьмёт.
почему у вас возникло такое "усмотрение"?
Потому что мимокрокодил на хабре, а не реально рабочее задание на интервью? Уж там бы я Вас помучил...
За "Гости из будущего" (если я не ошибаюсь) респект, а за "помучил", повторю еще раз. На собеседовании вы будите показывать то, как вы реально собираетесь работать, свои рабочие навыки. За демонстрацию того, что в армии называется "тупить", вы можете услышать "спасибо, было очень интересно" очень быстро. :)
А в некоторых базах можно обойтись одной агрегацией
SELECT
department_id,
ANY_VALUE(employee_id having max salary) AS employee
FROM employees
GROUP BY department_id
Хм, но все же быстрота запроса и его эффективность определяется не количеством символов в тексте. Где-то была хороший пример, там сравнивали текст пузырькового алгоритма сортировки для функционального языка программирования и обычного, алгоритмического. Для алгоритмического текста было значительно больше, для функционального несколько строк с рекурсивными вызовами. Но это же не значило, что вариант с функциональным языком лучше, там было ровно наоборот.
Если в отделе 2 сотрудника с одинаковой максимальной ЗП, то что выдаст ваш запрос?
А чем плох вариант
SELECT name, max(salary) AS salary
FROM employees
GROUP BY department_id
Возможно я что то подзабыл в SQL ,и есть ограничения на выполнение подобной процедуры.
Такой запрос даже выполняться не будет, т.к. содержит ошибку: вы используете name без агрегирования.
Да вы правы.
Попробовал вот тут https://www.w3schools.com/mysql/trymysql.asp?filename=trysql_select_groupby
запрос
SELECT customerid, max(shipperid) FROM Orders group by employeeid ;
Он хотя и выполняется но результат получается не правильный.
Разумеется ваш потенциальный начальник не придумывал ни эту задачу, ни её решение. И задачу и "правильный" ответ он подглядел в Интернете, чтобы демонстрировать своё ментальное превосходство.
В хрестоматию, в качестве иллюстрации к тому "Токсик"
Задача формулируется так. Есть база данных, где содержатся сотрудники с их разбиением по отделам и зарплатой. Я пытался прогуглить корень зла. Ссылки меня привели к статье: https://www.jitbit.com/news/181-jitbits-sql-interview-questions/
Просто на отлично задачу сформулировали. Выглядит так будто кусок текста вырвали, и уже мы, а не вы, должны искать как же звучала эта задача.
А почему нет простого решения через предикат?
select name from employees a
where not exists(select * from employees a where a.department_id=b.department_id and a.salary<b.salary)
не только лишь все СУБД могут нормально обработать джойн с неравенством (в который разворачивается where not exists)
Не увидел где у вас b определено.
Ну, вполне себе вариант. Почему нет, да как-то было очевидно, что по сравнению с вариантом с 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 строк)
А можно результат с индексом?CREATE INDEX ds2 on employees (department_id, salary DESC);
Вариант с EXISTS внутри сервера будет преобразован в LEFT JOIN ... WHERE e2.salary IS NULL т.е. планы и результат выполнения будут совместимые.
Для того чтобы показать что решение с MAX плохое достаточно сделать чтобы SORT работал долго, вырожденный случай когда один департамент и много дублей в salary. Либо увеличить количество записей чтобы сортировка начала захлебываться.
Открытый вопрос как запрос будет вести себя если ставить LIMIT, будет выполнять MAX для всего и потом JOIN или пропустит остальные записи.
Ps Сейчас mainstream Postgres SQL, но есть и другие RDBMS результаты на которых могут быть разные, вплоть до отсутствии поддержка RANK().
Ну смотрите, статья на самом деле не про то, какой самый эффективный алгоритм для решения поиска строки с максимальным значением. Как в комментах мудро заметили, вообще нет смысла заморачиваться с оптимизацией, если нет выборки реальных данных. Ваш "вырожденный" случай с одним отделом означает что в предприятии вообще отделов нет, а это уже противоречит условию задачи.
Статья была про другое, о чём я и написал в выводах статьи. Но если вам интересно очень тщательно изучить алгоритмы поиска строки с максимальным значением, вы можете это сделать сами.
а если у нас не департаменты и сотрудники, а товарные категории и чеки в миллиардных количествах, и хранится это все в каком нибудь хайве, то оконные функции отработают быстрее, потому что все будет происходить за один проход. Вложенный запрос сгенерирует редьюсеры, которые раскатятся по всему кластеру, и пока не завершатся все - не пойдет внешний.
Контр довод, оконная функция rank() будет считать ранги для всех сотрудников (и тратить на это ресурс), в то время как max() потребует меньше машинного времени. Плюс размер таблицы передаваемой из внутреннего запроса во внешний, в вашем случае она будет с размером с число сотрудников, в случае с max() размером с число подразделений.
Но, зачем теоретизировать? Обоснуйте свою точку зрения неголословно. Приведите такое распределение данных, при котором использование rank() будет выигрывать. Вот это уже будут слова не мальчика, но мужа.
Я правильно понимаю что rank() OVER (PARTITION BY department_id ORDER BY salary DESC) даст номер 1 employee ру с максимальной salary в разрезе своего depatament_id и даст номер 2 employee ру в том же departament_id даже если у него будет такая же максимальная salary как и у 1 employee ра?
Задача вроде "нахождению сотрудников с максимальной зарплатой в отделе"
а не "нахождению сотрудников с максимальной зарплатой в отделе по одному из отдела"?
Проблема в том, что придумывая задачу для собеседования, работодатель не всегда корректно ее формулирует, особенно если сам он не технарь
select 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 = 1
Поскольку в остальных ответах вывод названия департамента не требовалось, я слегка переписал ваш запрос. Но обращает внимание на то, что вы 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 PLAN
Subquery 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)
.> Он начинает подсказывать, что нужно использовать оконные функции.
Как человек много раз проходившей собеседования с подобными вопросами могу сказать что у вас неверная формулировка
Вопрос обычно звучит как top N чего то вывести и вот тогда без оконных функций не обойтись
Возвращаясь к вашей задаче, начальник просит вывести по 3 человека с самой высокой зп в каждом отделе
Ну а если начальник просит вывести сотрудников с максимальной зп через оконную функцию то вероятно он так себе начальник в плане сикули
Я же не просто рассказал, как было на собеседовании, тут вы могли бы придумать, что это я всё нафантазировал, всё было по другому, уж вы то точно знаете, вас там не было. Это хрестоматийная задача, которая есть и на Stack Overflow (с лидирующим решением как раз через rank()) и я привел ссылку на оригинал в блоге JitBit. Последнее я даже перевёл и выложил на Хабр.
Я не говори что вы что то нафантазировали
К сожалению, на собесах я очень часто встречал задачи с неполными условиями с неверными и т.д.
Просто вопрос про вывести топ, это почти на каждом собесе на аналитика/ дата сантиста
З.Ы. а теперь про неверные формулеровки оффтоп:
В икс 5 моему коллеге дали задачу на Пуассона но не дали лямбду
Мне только в Яндексе дали корректную задачу на теорему Байеса и интрвюер сам знал как ее решить, и раз 5 давали в других местах неверно, интервьер сам решал не правильно и т.д.
IMHO, главная задача собеседования - не найти спеца, который за 15 минут выдаст оптимальное решение, а понять, как этот специалист думает. Покрыть тестами всю область компетенции кандидата всё равно не удастся, да и само собеседование для многих - стресс, при котором показать свой максимум нереально.
Я обычно даю задачку на дом с условием на интервью подробно рассказать как именно работает решение и какие ещё варианты возможны. Ну и потрепаться на тему. Т.е. тестовое задание - не фильтр, а затравка для разговора.
Как бы да, ваш вариант хорош. Но например при приёме на работу в государственные или окологосударственные структуры, которые крышует ФСБ и в которые есть реальный интерес у вражеских разведок внедрить своих людей, там накладывается ограничение, что им важно видеть, что именно этот человек реально решает задачу, а не группа поддержки из вражеских разведок. :) Да даже если это коммерческий банк, у него такой же интерес, но быть может уже против агентов из ОПГ. Так что дать задачку на дом это встречается очень редко. Чаще собеседование должно проводится онлайн, а иногда и требуют обязательно видеть твоё лицо при этом. :)
А не группа поддержки из вражеских разведок. :)
Так это не препятствие для подготовленной службы поддержки иностранной разведки. Сначала на собесы ходят кандидаты, задача которых - собрать типовые задания и понять приоритеты. Потом целевой шпион просто прокачивается на эти кейсы :)
Но, на самом деле, проверки СБ - совсем другая история.
А вообще, "расколоть" товарища, который не сам написал код, на очном собеседовании как нефиг делать совсем несложно.
Мне кажется еще от уровня спеца зависит, для найма джуна полюбому нужно тестовое а вот от толкового мидла и выше - скорее всего тестовое отпугнет норм кандидата. Но это мое субъективное мнение, причем я вижу только свой маленький участок Айтишечки и что там происходит в каком нить фротенде вообще не вкурсе
За последний год был где то на 5ти собесах из них 4 были с live coding сессиями и только одна какая то дно контора предлагала сделать домашку ну там как бэ все сразу пошло не так, кроме первого разговора с девочкой HR из агентства.
А и вспомнил еще один случай когда бизнесовые девачки из крупной страховой хотели себе дата саенс и ИИ ну и я решил сходить пособеситься это был лютый трэшак, у людей вообще ничего нет: ни понимания, ни инфраструктуры, только надежда что какой то принц прискачет и спасет их, еще и под их руководством еще и за весьма скромную зп
Короч такой себе Damsel in distress
З.Ы. у вас тестовое на какую позицию в плаане уровня джун миддл синьор?
В защиту варианта с rank() отмечу, что с его помощью легче всего адаптировать запрос под внезапное изменение требований вида "а теперь выведи топ-3 сотрудников по зп в каждом отделе".
И в копилку вариантов добавлю ещё один без агрегатных и оконных функций
SELECT e.name AS employee, e.salary
FROM employees e
LEFT JOIN employees e_higher
ON e.department_id = e_higher.department_id
AND e.salary > e_higher.salary
WHERE e_higher.id IS NULLНадо смотреть планы, но зачастую запросы в такой форме оказываются весьма эффективными.
По поводу первого тезиса аргумент не принимается. Запросы надо писать с нуля под задачу, а не костылить старые под "похожую" задачу.
А по поводу вашего варианта, уже было.
https://habr.com/ru/articles/828728/comments/#comment_27040894
Запросы надо писать с нуля под задачу, а не костылить старые под "похожую" задачу.
Это довольно категоричное утверждение, как будто в реальности существует единственное "как надо" (что особенно иронично в контексте обсуждения статьи, где "начальник уверен, что запрос надо писать только одним единственно правильным образом"). На мой взгляд, реальность немного сложнее и в разных ситуациях может требоваться разное. Например, уточнить, а что делать с ситуацией, когда самую большую зарплату получают несколько сотрудников в отделе. Если надо вывести всех - то варианты с MAX, RANK и LEFT JOIN равно подходят. А если окажется, что вернуть надо строго одного сотрудника (иначе дальше где-то что-то сломается) - то стоит уточнить "по какому критерию выбирать топового сотрудника?" и использовать DENSE_RANK.
Помимо производительности запроса бывают и другие нефункциональные требования, которые тоже имеют значение. И когда нам нужна производительность любой ценой - ну да, тогда наверное оправдано под каждое изменение требований переписывать запрос целиком, чтобы выдать максимум. А если важны поддерживаемость и готовность к изменениям требований, при этом объемы данных не такие, чтобы доставлять проблемы - то лучше бы иметь понятный, легко читаемый запрос, который легко адаптируется от "топ 1" к "топ N" и к "все с наибольшей зп".
По поводу первого довода - контрдоводы. Не все, но некоторые компании практикуют, чтобы главным в проекте (продукте), был product owner, причем ключевое качество для такого по сути начальника это... не иметь вообще никакой профессии. Быть "эффективным менеджером" или бюрократом. Поскольку профессии у него нет, то он особенно сильно боится быть уволенным и панический держится за своё место. Очень сомнительная кадровая политика. Так вот, от таких начальником максимум чего добьёшься это фразы: "Хочу, чтобы всё было круто!" Но если сверху прилетит недовольство, он тут же переобуется и всю вину свалит на тех, кто ниже, т.е. на вас.
Но не в этом суть. Представьте себе строго математическую задачу по нахождению элементов из какого-то множества обладающих определённым свойством. Если таких элементов несколько, а вы в ответе напишите только одно, то ответ будет неправильным.
Запрос, тем более такой, в пяток строк, это не софтверная библиотека. Вот софтверную библиотеку там да, надо проектировать с взглядом на будущее. А проектировать запрос в пять строк с прицелом, как вы его будите переписывать под другие задачи, чтобы код был универсальным и reusable. Ну нет, выглядит гротескно. И дело даже не в количестве строк. Другое дело если бы вы мутили функцию, тогда да, можно было бы подумать об более широком её использовании в будущем.
Главный мой поинт в том, что не бывает одного "как надо". Вовремя заданный PO вопрос (вместо восприятия задачи как математически точной) может привести к ответу: эх, точно, а про это-то мы и не подумали, у нас верстка на дашборде ожидает строго одну фамилию, надо с дизайнером обсудить... А может не привести.
Товарищи разработчики, я вам сугубо рекомендую меньше задаваться вопросом "а как эту задачу решить наиболее оптимально в сферическом коне в вакууме", и чуть больше задаваться вопросом "а зачем мы ее решаем?" :)
Вы этим сэкономите и себе, и окружающим много времени и нервных клеток :)
В данном случае ожидался конкретный ответ, но в реальности подобные "странные" запросы ранжируются от "один раз запустить, чтобы принять конкретное управленческое решение" - и тогда подходит лучше всего то решение, которое вы быстрее накидаете.
До "мы будем строить 150 реалтайм дашбордов по такого рода запросам, которые будут выводиться на 1,5 миллионах клиентов от Сиднея, до Москвы и Вашингтона" :) и вот в таком случае то как именно стоить запрос... Будет проблемой к которой вы перейдете не на первом часу общения с заказчиком :D
В реальной жизни, к сожалению или счастью, нет правильных ответов :) Мы вечно ищем компромисс, который больше всего подходит к конкретной ситуации :) помните об этом :)
Ну нет. Даже на "один раз запустить" можно по быстрому накидать такое решение, которое положит всю базу данных, точнее не её, а микросервис, он перестанет отвечать на запросы. Как сказал один мой знакомый: "я пишу говнокод, зато делаю это очень быстро". Не надо так делать в любом случае.
Что же касается задачи, то если ответ условиям задачи соответствует, то он должен быть принят. Нужен другой ответ, изменяйте условия задачи. Например вместо сотрудника с максимальной зарплатой попросить вывести топ 3 было бы корректно, хотя и там можно было бы решить не через rank(). Но кандидат бы показал, что он умеет. А вот "угадай, какой вариант я знаю, там есть оконные функции", это уже неправильная постановка задачи. Такие задачи надо задавать не на собеседовании на тех.должность, а на битве экстрасенсов.
Статья просто шик, спасибо огромное! Сразу видно, у вас есть чему поучиться. Подскажите, поучиться, какие книги читать, чтобы так же глубоко SQL познать?
Как говорили древние хакеры: "RTFM".
https://www.postgresql.org/docs/current/index.html
Добавил запрос
SELECT E.name, S.Salary
FROM (
SELECT DISTINCT ON (department_id) department_id, salary
FROM employees
ORDER BY department_id, salary DESC) S
JOIN employees E ON E.department_id=S.department_id AND E.salary=S.salary;
Переделал индекс, так как иначе тупит
CREATE INDEX employees_salary_idx ON employees (department_id, salary DESC);Сравнил:
distinct on 0.262997000515461 0.2619999945163727
max 0.37648000022768974 0.37299999594688416
rank 0.4569539994597435 0.4490000009536743
window 1.0760890009403228 1.065000057220459P.S. Так как сервер не только мной загружен, то для более честного измерения изменил оригинальный запрос на
select method, avg(execution_time) as execution_time,
percentile_cont(0.5)
WITHIN GROUP (ORDER BY execution_time) AS mean_execution_time
from results group by method;
Нда, вы меня озадачили. И дело вовсе не в том, что похоже вы лидируете в этом негласном соревновании. Я думаю тут имеет место косяк в планировщике PostgreSQL, по идее (моей), ваш distinct и то что я предложил с max должны были бы давать одинаковый результат по времени. Для меня неочевидно, где max проигрывает. Но вот что я заметил. Похоже, когда я писал статью, я отключил
set enable_seqscan to false;
Потому что изначально экспериментировал с маленькой таблицей, а потом забыл включить его обратно. А это, оказалось, важно. Тестирование ниже проводилось с выбранным вами индексом
ON employees USING btree (department_id, salary DESC)
Если
set enable_seqscan to false;
то
method | execution_time
----------+---------------------
distinct | 0.21507000043988228
max | 0.24675499747693538
rank | 0.3294130029976368
window | 0.8126180001497268
А вот если
set enable_seqscan to true; -- это по умолчанию
method | execution_time
----------+---------------------
rank | 0.3307799963951111
distinct | 0.46438600090146065
max | 0.5562520008087158
window | 0.8275660008192063
И тут rank, внезапно, выходит на первое место (хотя быстрее работать не стал). Очевидно (по времени выполнения), что это ошибка планировщика. Здесь по дефолту стояло random_page_cost=4. Я попытался исправить это выставив random_page_cost=1, что разумно, всё целиком и полностью помещается в кэш ОЗУ.
set enable_seqscan to true; set random_page_cost=1;
method | execution_time
----------+---------------------
distinct | 0.21147700223326682
max | 0.30990499967336654
rank | 0.32765100106596945
window | 0.8102550018429756
Уже похоже на правду. но не очень. После random_page_cost=1 почти все демонстрируют такие же хорошие результаты как и с set enable_seqscan to false, кроме max. Который чуть-чуть все же работает медленнее и если сравнить планы:
Nested Loop
-> HashAggregate
Group Key: employees.department_id
-> Seq Scan on employees
-> Index Scan using ds2 on employees e
Index Cond: ((department_id = employees.department_id) AND (salary = (max(employees.salary))))
А с отключенным сиквенс сканом
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))))
Видно, что проблема в оптимизаторе планировщика.
И теперь я ломаю голову, чего бы еще такого подкрутить в конфиге, чтобы с включенным сиквенс сканом, postgresql все же бы выдавал оптимальный план (с двумя индекс сканами) для метода max. Изменение effective_cache_size не помогает.
Подозреваю, что skip index scan, пришедший в PostgreSQL из TimeScaleDB, сразу включается в случае DISTINCT ON, но только принудительно - в случае GROUP BY. Собственно говоря отсюда и очередной патч для skip index scan
похоже вы лидируете в этом негласном соревновании
Проверил на 20 тыс. сотрудниках и SET enable_seqscan = OFF;
distinct on 2.6078910019397736
max 2.9574180014133455
rank 6.917046000480652
window 13.669837007522583DISTINCT ON всё равно выигрывает. Его, если не ошибаюсь, в 15 версии хорошо оптимизировали. А в 12 версии он точно проигрывал MAX()/GROUP BY.
Следует отметить, что у варианта MAX()/GROUP BY есть заметное преимущество - он универсален. Например, в MS SQL DISTINCT ON нет.
История с тем, что решение через RANK кто-то может считать единственно верным, мне кажется немного натянутой.
Вообще, сам тест действительно очень древний, мне он тоже попадался. Раскопки привели к статье на хабре аж 2013 года: https://habr.com/ru/articles/181033/
А самое забавное, что она опубликована 27 мая, как и тест на сайте jitbit, если смотреть через веб-архив: http://web.archive.org/web/20130607185217/https://www.jitbit.com/news/181-jitbits-sql-interview-questions/
Вот только наборы задач в статье на хабре и на сайте jitbit отличаются, совпадают только 4 задачи, включая задачу с поиском сотрудников с максимальной зарплатой (идет под номером 2).
Так вот дело в том, что в оригинальной статье приведено как раз другое решение:
select a.*
from employee a
where a.salary = ( select max(salary) from employee b
where b.department_id = a.department_id )
Популярная задача на собеседовании: сотрудники с максимальной зарплатой в отделе