Search
Write a publication
Pull to refresh
244
4.1
Егор Рогов @erogov

Пользователь

Send message

«IT-Планета 2025»: задачи третьего этапа по PostgreSQL

Reading time12 min
Views2.9K

На третьем этапе олимпиады мы, как обычно, решали задачки на SQL, но в этом году надо было написать запрос не просто правильный, но и короткий. Чем короче — тем лучше результат. В детстве мы развлекались таким на микрокалькуляторах и на ассемблере, а сейчас я решил посмотреть, что получится, если попробовать то же на SQL. Получилось, на мой взгляд, интересно. Практического смысла в этом, конечно, никакого нет, но практики и на работе хватит, а тут мы развлекаемся.

Чтобы хорошо выступить, надо было — помимо прочего — выстроить правильную стратегию. Сразу писать максимально короткий запрос, без пробелов и с односимвольными именами не получится — легко самому запутаться. Поэтому сначала надо было решить задачу «по-человечески», а уже потом применить всякие микрооптимизации и получить заветные баллы. Но решить задачу, даже простую, всегда можно разными способами, и не всегда заранее понятно, какой из вариантов окажется короче после оптимизации. Поэтому нужно было не останавливаться, пробовать разные подходы, и при этом аккуратно хранить все версии, чтобы в любой момент можно было посмотреть на запрос еще раз и, чем Тьюринг не шутит, выиграть байтик-другой.

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

Итак, к задачам

Сиквел и приквел: занимательная археология

Reading time20 min
Views2.3K

Предлагаю вашему вниманию немного дополненный доклад, который я делал на конференции PGConf.СПб 2024. В нем я рассказываю о том, как появились первые реляционные системы, как возник и всех победил язык SQL.

Погрузиться в историю

«IT-Планета 2024»: задачи третьего этапа по PostgreSQL

Reading time9 min
Views4.3K

Или, точнее, задача, поскольку в этом году мы попробовали другой формат: задача была всего одна, но большая. Требовалось написать SQL-запрос, играющий в крестики-нолики «пять в ряд».

Ну-ка, ну-ка

«IT-Планета 2024»: задачи второго этапа по PostgreSQL

Reading time32 min
Views6.6K

Вдохновившись прошлогодним опытом, мы продолжили начинание и снова проводим конкурс по SQL на международной олимпиаде «IT-Планета».

Конкурс состоит из трех этапов. Заочный теоретический тест собрал почти 3000 человек, из которых на следующий этап мы отобрали примерно 200. Вопросы для этого этапа были подготовлены моим коллегой, Евгением Давыдовым.

Второй этап — также заочный. Здесь участником было предложено подумать над пятью задачами моего авторства, о которых я сегодня и хочу рассказать.

Третий — очный — этап пройдет в конце мая; постараюсь не затягивать с отчетом, но пока храню интригующее молчание.

Поскольку все вводные слова про мотивацию я уже сказал в прошлый раз, сразу приступим к делу.

Приступить к делу

Задачи третьего этапа олимпиады «IT-Планеты» по PostgreSQL

Reading time13 min
Views9.7K

В шахматы меня когда-то легко обыгрывал восьмибитный компьютер, а действующего чемпиона мира IBM-овский Deep Blue одолел уже в 1997 году. Но игра Го держалась значительно дольше: победить обладателя девятого дана Ли Седоля удалось только в 2016 году компании Гугл с машиной AlphaGo. В Го простые правила, которые, однако, приводят к очень сложным стратегическим построениям. Ровно то, что нужно: простое условие, не дающее намека на то, как справиться с задачей одним SQL-запросом. Тема Го и легла в основу задач финала олимпиады, про которую я уже начал рассказывать в прошлый раз.

Финал проходил в Сочинском государственном университете. Пользуясь случаем, хочу сказать спасибо гостеприимным сотрудникам университета и организаторам, оперативно устранявшим все трудности.

Поговорим про задачи

Задачи второго этапа олимпиады «IT-Планеты» по PostgreSQL

Reading time16 min
Views9K

В этом году наша компания впервые провела конкурс по базам данных в рамках международной олимпиады IT-Планета по информационным технологиям. Раньше на олимпиаде использовалась СУБД Oracle; наш коллега Евгений Бредня в свое время делился таким опытом.

Олимпиада проходила в три этапа. Первым шел заочный теоретический тест, который преодолели примерно двести человек из двух тысяч зарегистрировавшихся.

На втором этапе участникам было предложено подумать над пятью задачами, каждую из которых следовало решить одним SQL-запросом. Этот этап также проводился заочно: на раздумья было дано примерно три недели. Условия всех задач были опубликованы одновременно, но у каждой был свой крайний срок; поэтому первыми шли задачи полегче, чтобы на более сложные осталось больше времени. Задачи проверялись на корректность (автоматическими тестами) и на качество кода (вручную). По результатам мы отобрали двадцать человек для последнего, очного этапа.

Третий этап состоялся 27 мая в Сочи. К сожалению, из двадцати приглашенных приехать смогли только четырнадцать; между ними и состоялось соревнование. Задачи этого этапа также предполагали решение одним запросом, но сами задания были объединены общей темой, навеянной игрой Го, и строились так, что решение одной задачи помогало подступиться к следующей.

Я занимался придумыванием задач для второго и третьего этапов. Хочу поблагодарить участников олимпиады, которым пришлось их решать, организаторов, собравших нас вместе, и своих коллег: Дарью Рисухину, взвалившую на себя все оргвопросы, Евгения Моргунова, предоставившего задания для первого этапа, а также всех помогавших мне с задачами.

Поговорим о втором этапе

Запросы в PostgreSQL: 7. Сортировка и слияние

Reading time21 min
Views17K

В предыдущих статьях я писал про этапы выполнения запросов, про статистику, про два основных вида доступа к данным — последовательное сканирование и индексное сканирование, — и успел рассказать о двух способах соединения — вложенном цикле и соединении хешированием.

В заключительной статье этой серии я расскажу про алгоритм слияния и про сортировку, и сравню все три алгоритма соединения между собой.

Читать далее

Запросы в PostgreSQL: 6. Хеширование

Reading time20 min
Views21K

В предыдущих статьях я рассказал про этапы выполнения запросов, про статистику, про два основных вида доступа к данным — последовательное сканирование и индексное сканирование, — и перешел к способам соединения.

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

Читать далее

Запросы в PostgreSQL: 5. Вложенный цикл

Reading time19 min
Views28K

Я уже рассказал об этапах выполнения запросов и о статистике, и о двух основных видах доступа к данным: о последовательном сканировании и об индексном сканировании.

Настал черед способов соединения. В этой статье я кратко напомню, какие бывают логические типы соединений, и расскажу о первом из трех физических способов соединения — о вложенном цикле. Заодно посмотрим и на новую для 14-й версии мемоизацию строк.

Читать далее

Запросы в PostgreSQL: 4. Индексное сканирование

Reading time20 min
Views23K

Я уже рассказал об этапах выполнения запросов и о статистике и перешел к способам доступа к данным. В прошлый раз темой статьи было последовательное сканирование, а сегодня поговорим о сканировании индексном.

Прежде чем погружаться в детали индексного доступа, надо было бы рассказать про интерфейс индексных методов. Но я это уже делал в статье про индексы, и, хотя та серия несколько устарела, повторяться не буду. Если слова «класс операторов» и «свойства методов доступа» не находят отклика в душе, статью лучше перечитать.

Читать далее

Запросы в PostgreSQL: 3. Последовательное сканирование

Reading time16 min
Views19K

В предыдущих статьях я рассказал об этапах выполнения запросов и о статистике.

Теперь пришла пора рассмотреть самые важные узлы, из которых может состоять план. Я начну со способов доступа к данным, и в этой статье расскажу о последовательном сканировании.

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

Читать далее

Запросы в PostgreSQL: 2. Статистика

Reading time19 min
Views36K

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

Как обычно, я буду приводить примеры из демобазы. В этой статье будет довольно много планов выполнения, но про их составные части я буду рассказывать только в следующих статьях. Здесь же нас в первую очередь будут интересовать оценки количества строк (кардинальности), то есть числа, указанные в верхней строке плана в позиции rows.

Читать далее

Запросы в PostgreSQL: 1. Этапы выполнения

Reading time17 min
Views91K

Привет, Хабр! Начинаю еще один цикл статей об устройстве PostgreSQL, на этот раз о том, как планируются и выполняются запросы.

Предыдущие циклы были посвящены изоляции и многоверсионности, журналированию и блокировкам.

В этом цикле я собираюсь рассмотреть этапы выполнения запросов, статистику, последовательное сканирование, индексное сканирование, соединение вложенным циклом, соединение хешированием, сортировку и соединение слиянием.

Материал перекликается с нашим учебным курсом QPT «Оптимизация запросов», но ограничивается только подробностями внутреннего устройства и не затрагивает оптимизацию как таковую. Кроме того, я ориентируюсь на еще не вышедшую версию PostgreSQL 14. А курс мы тоже скоро обновим (правда, на версию 13; приходится бежать со всех ног, чтобы только оставаться на месте).

Поехали

«Жизнь» на PostgreSQL

Reading time4 min
Views20K
Недавно на Хабре была опубликована статья Морской бой в PostgreSQL. Должен признаться: я обожаю решать на SQL задачи, для SQL не предназначенные. Особенно одним SQL-оператором. И полностью согласен с авторами:

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

И еще. Будем честны: всегда использовать SQL по назначению — тоска зеленая. Вспомните, какие примеры приводятся во всех учебниках, начиная с той самой статьи Кодда? Поставщики да детали, сотрудники да отделы… А где же удовольствие, где же фан? Для меня один из источников вдохновения — сравнение процедурных решений с декларативными.

Я, позвольте, не буду объяснять, что такое Жизнь Джона Конвея. Скажу только, что — оказывается — используя клеточный автомат Жизни, можно построить универсальную машину Тьюринга. Мне кажется, это грандиозный факт.

Так вот, можно ли реализовать игру Жизнь одним оператором SQL?
Конечно можно

Locks in PostgreSQL: 4. Locks in memory

Reading time10 min
Views16K
To remind you, we've already talked about relation-level locks, row-level locks, locks on other objects (including predicate locks) and interrelationships of different types of locks.

The following discussion of locks in RAM finishes this series of articles. We will consider spinlocks, lightweight locks and buffer pins, as well as events monitoring tools and sampling.


Read more →

Locks in PostgreSQL: 3. Other locks

Reading time14 min
Views9K
We've already discussed some object-level locks (specifically, relation-level locks), as well as row-level locks with their connection to object-level locks and also explored wait queues, which are not always fair.

We have a hodgepodge this time. We'll start with deadlocks (actually, I planned to discuss them last time, but that article was excessively long in itself), then briefly review object-level locks left and finally discuss predicate locks.

Deadlocks


When using locks, we can confront a deadlock. It occurs when one transaction tries to acquire a resource that is already in use by another transaction, while the second transaction tries to acquire a resource that is in use by the first. The figure on the left below illustrates this: solid-line arrows indicate acquired resources, while dashed-line arrows show attempts to acquire a resource that is already in use.

To visualize a deadlock, it is convenient to build the wait-for graph. To do this, we remove specific resources, leave only transactions and indicate which transaction waits for which other. If a graph contains a cycle (from a vertex, we can get to itself in a walk along arrows), this is a deadlock.


Read more →

Locks in PostgreSQL: 2. Row-level locks

Reading time14 min
Views14K
Last time, we discussed object-level locks and in particular relation-level locks. In this article, we will see how row-level locks are organized in PostgreSQL and how they are used together with object-level locks. We will also talk of wait queues and of those who jumps the queue.



Row-level locks


Organization


Let's recall a few weighty conclusions of the previous article.

  • A lock must be available somewhere in the shared memory of the server.
  • The higher granularity of locks, the lower the contention among concurrent processes.
  • On the other hand, the higher the granularity, the more of the memory is occupied by locks.

There is no doubt that we want a change of one row not block other rows of the same table. But we cannot afford to have its own lock for each row either.

There are different approaches to solving this problem. Some database management systems apply escalation of locks: if the number of row-level locks gets too high, they are replaced with one, more general lock (for example: a page-level or an entire table-level).

As we will see later, PostgreSQL also applies this technique, but only for predicate locks. The situation with row-level locks is different.
Read more →

Locks in PostgreSQL: 1. Relation-level locks

Reading time13 min
Views19K
The previous two series of articles covered isolation and multiversion concurrency control and logging.

In this series, we will discuss locks.

This series will consist of four articles:

  1. Relation-level locks (this article).
  2. Row-level locks.
  3. Locks on other objects and predicate locks.
  4. Locks in RAM.

The material of all the articles is based on training courses on administration that Pavel pluzanov and I are creating (mostly in Russian, although one course is available in English), but does not repeat them verbatim and is intended for careful reading and self-experimenting.

Many thanks to Elena Indrupskaya for the translation of these articles into English.



General information on locks


PostgreSQL has a wide variety of techniques that serve to lock something (or are at least called so). Therefore, I will first explain in the most general terms why locks are needed at all, what kinds of them are available and how they differ from one another. Then we will figure out what of this variety is used in PostgreSQL and only after that we will start discussing different kinds of locks in detail.
Read more →

WAL in PostgreSQL: 4. Setup and Tuning

Reading time17 min
Views9.7K
So, we got acquainted with the structure of the buffer cache and in this context concluded that if all the RAM contents got lost due to failure, the write-ahead log (WAL) was required to recover. The size of the necessary WAL files and the recovery time are limited thanks to the checkpoint performed from time to time.

In the previous articles we already reviewed quite a few important settings that anyway relate to WAL. In this article (being the last in this series) we will discuss problems of WAL setup that are unaddressed yet: WAL levels and their purpose, as well as the reliability and performance of write-ahead logging.

WAL levels


The main WAL task is to ensure recovery after a failure. But once we have to maintain the log anyway, we can also adapt it to other tasks by adding some more information to it. There are several logging levels. The wal_level parameter specifies the level, and each next level includes everything that gets into WAL of the preceding level plus something new.
Read more →

WAL in PostgreSQL: 3. Checkpoint

Reading time11 min
Views6.9K
We already got acquainted with the structure of the buffer cache — one of the main objects of the shared memory — and concluded that to recover after failure when all the RAM contents get lost, the write-ahead log (WAL) must be maintained.

The problem yet unaddressed, where we left off last time, is that we are unaware of where to start playing back WAL records during the recovery. To begin from the beginning, as the King from Lewis Caroll's Alice advised, is not an option: it is impossible to keep all the WAL records from the server start — this is potentially both a huge memory size and equally huge duration of the recovery. We need such a point that is gradually moving forward and that we can start the recovery at (and safely remove all the previous WAL records, accordingly). And this is the checkpoint, to be discussed below.

Checkpoint


What features must the checkpoint have? We must be sure that all the WAL records starting with the checkpoint will be applied to the pages flushed to disk. If it were not the case, during recovery, we could read from disk a version of the page that is too old, apply the WAL record to it and by doing so, irreversibly hurt the data.
Read more →

Information

Rating
658-th
Location
Москва, Москва и Московская обл., Россия
Works in
Date of birth
Registered
Activity