Содержание

1. Введение

2. Схема БД

3. SELECT-запрос, как конвейер, по которому едут таблицы

   1. Оператор FROM

   2. Оператор JOIN

   3. Оператор WHERE

   4. Оператор GROUP BY

   5. Оператор HAVING

   6. Оператор ORDER BY

   7. Операторы OFFSET и LIMIT

   8. Оператор SELECT

4. Приземляем логическую модель на код

5. SELECT-запрос, как конвейер, по которому едут строки

6. Заключение

Введение

Я отчётливо помню, как сидел на втором курсе на лабах по БД и долго и мучительно методом научного тыка подбирал порядок слов в SELECT-запросе с GROUP BY, чтобы он вернул нужный мне преподу результат. Потому что я не понимал, как работает SELECT, хотя был прилежным (на программистских курсах) студентом, ходил на все лекции и делал лабы за себя и пару "тех парней".

Двадцать лет спустя, когда я встал по ту сторону баррикад и начал сам вести лабы по БД, я столкнулся с той же самой проблемой уже у своих студентов. И, так как за двадцать лет я всё-таки понял, как работает SELECT, то придумал для них способ объяснения, который работает хорошо (в моей практике).

Посмотрите на этот запрос:

SELECT e.id,
       e.name || ', паспорт: ' || e.passport as name,
       sum(de.training_budget) as sum,
       array_agg(d.name || ' - ' || de.training_budget) as details
FROM employees e
         JOIN department_employees de on e.id = de.employee_id
         JOIN departments d on de.department_id = d.id
WHERE d.location = 'Новосибирск'
GROUP BY e.id
HAVING sum(de.training_budget) > 80000
ORDER BY sum(training_budget) desc
OFFSET 1 LIMIT 1;

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

Но прежде чем переходить непосредственно к инструменту — рассмотрим небольшую схему БД, на которой я буду его иллюстрировать.

Схема БД

В этом посте я буду использовать следующую схему БД:

CREATE TABLE employees
(
    id       BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    passport NUMERIC(10)  NOT NULL UNIQUE,
    name     VARCHAR(256) NOT NULL CHECK (length((name)) > 3)
);

CREATE TABLE departments
(
    id       BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    name     VARCHAR NOT NULL,
    location VARCHAR NOT NULL
);

CREATE TABLE department_employees
(
    department_id   BIGINT REFERENCES departments,
    employee_id     BIGINT REFERENCES employees,
    training_budget NUMERIC(8, 2),
    PRIMARY KEY (department_id, employee_id)
);

Тут у нас есть некие сотрудники и отделы, связанные отношением многие-ко-многим. Кроме того, на каждого сотрудника в рамках каждого отдела выделен собственный бюджет на обучение.

Теперь можно переходить непосредственно к логической модели SELECT-запроса.

SELECT-запрос, как конвейер, по которому едут таблицы

Представьте, что SELECT-запрос — это конвейер, по которому едут таблицы. «Постами» этого конвейера являются SQL-операторы, которые как-то трансформируют таблицы. Ключевое здесь, что «посты»/операторы — трансформируют таблицы в таблицы.

Но, вопреки синтаксической структуре SELECT-а, этот конвейер начинается не с оператора SELECT, а с оператора FROM.

Оператор FROM

Оператор FROM, пожалуй, является самым простым — он передаёт дальше по конвейеру всю таблицу целиком, без каких-либо модификаций.

В нашем примере эта часть конвейера будет выглядеть так:

Оператор JOIN

Следующим постом конвейера является оператор JOIN. У JOIN-а есть несколько вариаций, основными из которых являются CROSS, INNER, LEFT, RIGHT и FULL.

Но так как это не вводный пост в SQL SELECT в целом, а пост про логическую модель его работы, и с логической точки зрения все вариации работают одинаково, я рассмотрю только необходимый мне минимум — INNER JOIN.

Оператор INNER JOIN принимает на вход две таблицы — одну от предыдущего «поста» и одну указанную пользователем таблицу извне конвейера. Обе эти таблицы могут быть как физическими — описанными в схеме БД, так и логическими/виртуальными — получившимися в результате трансформации выше по конвейеру или в результате подзапроса.

И из этих двух таблиц JOIN строит одну. Атрибутами этой таблицы является объединение всех атрибутов входных таблиц. А строками — все пары строк, которые удовлетворяют условию объединения.

По сути, INNER JOIN — это вложенный цикл, который пробегается по строкам обеих таблиц, вычисляет значение условия объединения для каждой пары строк и — если оно истинно — добавляет в выходную таблицу объединённые строки.

Из этой логики следует, что одна входная строка может войти во сколько угодно (вплоть до количества строк во второй таблице) пар, удовлетворяющих условию соединения, и, соответственно, данные этой строки будут продублированы в выходной таблице. В нашем примере такими строками будут строки сотрудников «Маслова» и «Поздняков», для которых есть по две записи в таблице department_employees.

На иллюстрации конвейера первый JOIN выглядит так:

А второй так:

Оператор WHERE

Оператор WHERE — один из самых простых в SQL. Он принимает на вход одну таблицу и порождает таблицу с теми же атрибутами, что и входная и в которой все строки соответствуют условию фильтрации. Если во входной таблице ни одна строка не соответствует условию — на выходе будет пустая таблица.

В нашем примере соответствующий «пост» конвейера выглядит так:

Оператор GROUP BY

А вот GROUP BY — один из самых сложных операторов для понимания. Возможно, это связано с тем, что GROUP BY порождает отношения не удовлетворяющие даже первой нормальной форме. А Кодд — автор реляционной модели — ввёл нормальные формы как раз для того, чтобы сделать отношения более простыми для понимания и работы с ними ("with the objective of making the collection of relations easier to understand and control, simpler to operate upon, and more informative to the casual user" — FURTHER NORMALIZATION OF THE DATA BASE RELATIONAL MODEL).

GROUP BY принимает на вход одну таблицу и на выход порождает тоже одну таблицу, с тем же количеством атрибутов, но эти атрибуты уже разделены на два набора. А строк GROUP BY возвращает не больше, чем во входной таблице — по одной на каждое уникальное значение кортежа группировочных атрибутов.

Двумя наборами атрибутов таблицы на выходе являются группирующие и негруппирующие атрибуты. Группирующие атрибуты — это те, что перечислены после GROUP BY, а негруппирующие — все остальные атрибуты входной таблицы.

Группирующие атрибуты остаются обычными атрибутами, и с ними далее можно работать как обычно.

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

Собственно по этой причине таблица, порождаемая GROUP BY, не является отношением реляционной модели, атрибуты которого должны быть скалярами.

Для того чтобы со значениями негруппирующих атрибутов можно было работать, их необходимо снова превратить в скаляры с помощью агрегирующих функций (count, min, avg, array_agg и т.д.).

Соответственно, в нашем примере «пост» GROUP BY можно проиллюстрировать так:

Оператор HAVING

Оператор HAVING — это по сути второй WHERE, у которого есть доступ к сгруппированным строкам. Технически в HAVING вы можете выполнить фильтрацию по группирующим атрибутам (HAVING id BETWEEN 2 AND 4, например), но это может быть не эффективно — далее в посте объясню почему.

Соответственно, HAVING работает аналогично WHERE — принимает на вход таблицу и порождает на выход таблицу с такими же (разбитыми на две группы) атрибутами, все строки которой соответствуют определённому условию.

В нашем примере «пост» HAVING выглядит так:

Оператор ORDER BY

В общем случае ни SQL, ни имплементации СУБД не гарантируют какой-либо порядок строк в результате SQL-запроса.

А реляционная модель вообще оперирует отношениями — множествами кортежей, которые не упорядочены по определению.

Соответственно, оператор ORDER BY тоже в некотором роде читер — превращает отношения в таблицы с заданным порядком строк. Очевидно, он никак не меняет атрибуты или строки таблицы, а меняет только их порядок. И в нашем примере, "пост" ORDER BY выглядит так:

Операторы OFFSET и LIMIT

Эти операторы, по сути — третья ипостась WHERE на минималках, у которого появляется доступ до виртуального безымянного атрибута с порядковым номером строки в таблице и, благодаря предыдущему ORDER BY, строкам в определённом порядке.

Соответственно, он принимает на вход таблицу и выдаёт на выход таблицу с теми же атрибутами. А вот строки он возвращает только те, что начинаются с заданного офсета (или с первой строки, если офсет явно не задан), и общим количеством, не превышающий заданного лимита (или все оставшиеся строки, если лимит явно не задан).

Эти операторы могут использоваться по отдельности, поэтому, строго говоря, это два разных «поста», но я немного «срежу угол» и в нашем примере сделаю их одним:

Оператор SELECT

Ну и, наконец, последний (в нашей упрощённой модели) «пост» SELECT. Он получает на вход таблицу и даёт на выход таблицу с тем же количеством строк, но (потенциально) другими атрибутами.

С атрибутами SELECT может проделать три вещи:

1. отбросить лишние. Если атрибут явно неуказан в SELECT-е — он не попадёт в результат запроса;

2. «нормализовать» сгруппированные атрибуты с помощью агрегатных функций;

3. добавить новые атрибуты, значения которых вычисляется на основе данных строки и глобального окружения (текущее время, например).

В нашем примере соответствующий «пост» выглядит так:

Здесь мы:

1. отбрасываем большую часть атрибутов входной таблицы;

2. "нормализуем" атрибуты de.training_budget и d.name в сумму бюджета на обучение и её разбивку по отделам;

3. и добавляем новый вычисляемый атрибут с конкатенацией имени и паспорта сотрудника.

---

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

А целиком конвейер этого запроса выглядит так (картинка кликабельна):

Приземляем логическую модель на код

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

Писать полноценную СУБД в рамках вводного поста я не предлагаю, а вот запрограммировать на Kotlin наш конкретный конвейер — вполне возможно.

Для начала нам надо решить, как мы будем представлять таблицы нашего конвейера. И, думаю, вы не будете шокированы моим выбором: строки таблицы я буду представлять как мапы имён атрибутов типа String в любое значение, а таблицы — как списки мап.

А для того, чтобы код выглядел чуть аккуратнее, я введу пару алиасов:

typealias Row = Map<String, Any?>
typealias Table = List<Row>

Также нам потребуется функция для вывода таблицы в консоль:

fun Iterable<Row>.printRelation() {
    val keys = this.first().keys
    println(keys.joinToString(","))
    forEach {
        val values = keys.map { key -> it[key] }
        println(values.joinToString(","))
    }
    println("Rows: ${this.count()}")
    println()
}

И собственно таблицы:

val employees: Table = listOf(
    mapOf("e_id" to 1, "e_name" to "Маслова Александра Марковна", "passport" to "4007467248"),
    mapOf("e_id" to 2, "e_name" to "Поздняков Павел Александрович", "passport" to "4007467249"),
    mapOf("e_id" to 3, "e_name" to "Кузнецова Дарья Вячеславовна", "passport" to "4007467250"),
    mapOf("e_id" to 4, "e_name" to "Майорова Анастасия Ивановна", "passport" to "4007467251"),
    mapOf("e_id" to 5, "e_name" to "Еремина Анастасия Кирилловна", "passport" to "4007467252"),
    mapOf("e_id" to 6, "e_name" to "Авдеев Степан Матвеевич", "passport" to "4007467253"),
    mapOf("e_id" to 7, "e_name" to "Федосеева София Ивановна", "passport" to "4007467254"),
    mapOf("e_id" to 8, "e_name" to "Плотникова Арина Никитична", "passport" to "4007467255"),
)
val departments: Table = listOf(
    mapOf("d_id" to 1, "d_name" to "Аналитики", "location" to "Новосибирск"),
    mapOf("d_id" to 2, "d_name" to "Аналитики", "location" to "Москва"),
    mapOf("d_id" to 3, "d_name" to "Разработки", "location" to "Новосибирск"),
    mapOf("d_id" to 4, "d_name" to "Разработки", "location" to "Москва"),
    mapOf("d_id" to 5, "d_name" to "Бухгалтерия", "location" to "Новосибирск"),
)
val departmentEmployees: Table = listOf(
    mapOf("department_id" to 1, "employee_id" to 1, "training_budget" to 55000),
    mapOf("department_id" to 3, "employee_id" to 1, "training_budget" to 40000),
    mapOf("department_id" to 3, "employee_id" to 2, "training_budget" to 55000),
    mapOf("department_id" to 5, "employee_id" to 2, "training_budget" to 55000),
    mapOf("department_id" to 2, "employee_id" to 3, "training_budget" to 0),
    mapOf("department_id" to 1, "employee_id" to 4, "training_budget" to 10000),
    mapOf("department_id" to 5, "employee_id" to 5, "training_budget" to 70000),
    mapOf("department_id" to 2, "employee_id" to 6, "training_budget" to 13500),
    mapOf("department_id" to 4, "employee_id" to 7, "training_budget" to 25000),
    mapOf("department_id" to 4, "employee_id" to 8, "training_budget" to 94000),
)

А текущую таблицу на конвейере мы будем хранить в переменной table:

var table: Table

Теперь у нас всё готово и можем переходить к сборке конвейера.

Он начинается с «поста» FROM, который просто возвращает заданную таблицу. В нашем случае для этого надо также просто присвоить переменной table соответствующее значение:

// FROM employees e
table = employees

Далее идёт пара INNER JOIN-ов, которые, напомню, по сути являются вложенным циклом. Для их реализации мы воспользуемся расширениями Kotlin и добавим к типу Table метод innerJoin.

Возможно, вам будет более привычен и понятен императивный вариант этого метода:

fun Table.imperativeInnerJoin(right: Table, cond: (Row, Row) -> Boolean): Table {
    val result = mutableListOf<Row>()
    for (leftRow in this) {
        for (rightRow in right) {
            if (cond(leftRow, rightRow)) {
                result.add(leftRow + rightRow)
            }
        }
    }
    return result
}

Но мне больше нравится существенно более короткий декларативный вариант:

fun Table.innerJoin(right: Table, cond: (Row, Row) -> Boolean): Table =
    this.flatMap { leftRow ->
        right
            .filter { rightRow -> cond(leftRow, rightRow) }
            .map { rightRow -> leftRow + rightRow }
    }

И теперь мы можем добавить JOIN-ы в наш конвейер:

// JOIN department_employees de on e.id = de.employee_id
table = table.innerJoin(departmentEmployees) { e, de -> e["e_id"] == de["employee_id"] }

// JOIN departments d on de.department_id = d.id
table = table.innerJoin(departments) { de, d -> de["department_id"] == d["d_id"] }

Далее у нас идёт «пост» WHERE, с которым отлично справится библиотечный метод filter:

// WHERE d.location = 'Новосибирск'
table = table.filter { it["location"] == "Новосибирск" }

А вот метод groupBy в стандартной библиотеке хоть и есть, но нам он не подходит, потому как он возвращает мапу (список пар), в которой значениями являются списки мап (списки строк таблицы). Нам же нужен замкнутый оператор, дающий на выходе тот же тип данных, что и на входе — список мап, внутри которых для сгруппированных колонок будут списки значений. Возможно, в типах это будет немного нагляднее: groupBy возвращает Map<Any, List<Row>>, а нам надо, чтобы он вернул Table (List<Row>, где Row — это Map<String, Any>).

Взорвался мозг? У меня тоже. Попробую проиллюстрировать это ещё на картинке:

Здесь проиллюстрированы два варианта работы groupBy: из стандартной библиотеки и в SQL.

Обоим вариантам на вход подаётся список мап с ключами groupingKey и simpleAttr. В этом списке 5 элементов (мап), в которых ключи groupingKey имеют три уникальных значения — 1, 2, 3.

И стандартный groupBy возвращает мапу, где ключами являются уникальные значения groupingKey (1, 2, 3), а значениями — список мап, в которых ключ groupingKey равен ключу во внешней мапе.

В случае SQL-я же, на выход мы снова получаем список мап (Table) — по мапе на каждое уникальное значение groupingKey. И в этих мапах значения ключей groupingKey остаются скалярами, а вот значения негруппировочных simpleAttr превращаются в списки скаляров.

Если вы всё ещё не можете уложить в голове работу одного или обоих вариантов — прекрасно вас понимаю. Давайте попробуем последний способ объяснения.

groupBy в Kotlin реализован так:

public inline fun <T, K, M : MutableMap<in K, MutableList<T>>> Iterable<T>.groupByTo(
    destination: M, 1
    keySelector: (T) -> K
): M {
    for (element in this) { 2
        val key = keySelector(element) 3
        val list = destination.getOrPut(key) { ArrayList<T>() } 4
        list.add(element) 5
    }
    return destination
}

1. на вход получаем целевую изменяемую мапу, в которую запишем результат;

2. пробегаемся по элементам группируемой коллекции;

3. для каждого элемента получаем группировочное значение;

4. добавляем, если его не было, в целевую мапу список под группировочным значением;

5. а в сам список добавляем весь элемент группируемой коллекции.

Наша же, SQL-подобная реализация groupBy выглядит так:

fun Table.groupBy(groupingKey: String): Table {
    val keys = this.firstOrNull()?.keys 1
        ?: return emptyList() // если таблица пустая — возвращаем пустую таблицу 2

    val rowGroups: Collection<List<Row>> = this
        .groupBy { it[groupingKey] } // группируем строки таблицы по ключу 3
        .values

    return rowGroups.map { rows -> // "сворачиваем" группу (список) строк в строку со списками значений 4
        val groupedRowSeed: Map<String, List<Any?>> = keys.associateWith { listOf() } // стартовая строка с пустыми списками значений
        val groupedRow: Map<String, List<Any?>> = rows.fold(groupedRowSeed) { groupedRow, row ->
            groupedRow.mapValues { (key, values) ->
                values + row[key]
            }
        }
        // подменяем значение по ключу группировки на скаляр и возвращаем сгрупированную строку
        groupedRow + (groupingKey to rows.first()[groupingKey])
    }

}

Что здесь происходит:

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

2. Если список пустой, то и атрибуты мы получить не можем — благо в этом случае мы тоже можем вернуть пустой список;

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

4. Собираем этот список таблиц обратно в одну таблицу, для чего каждую таблицу из списка превращаем снова в строку:

   • создаём заготовку сгруппированной строки результирующей таблицы, в которой для каждого атрибута хранится пустой список значений (строка 10)

   • пробегаемся по строкам таблицы (rows.fold — строка 11)

     • пробегаемся по ключам (атрибутам) и значениям (groupedRow.mapValues — строка 12)

       • добавляем в список под соответствующим ключом в строке-заготовке значение из строки таблицы (values + row[key] — строка 13)

   • для группировочного атрибута заменяем значение со списка на скаляр, взяв его значение из первой строки таблицы, так как оно во всех строках одинаковое (строка 17)

Фух, это было сложно. Зато теперь в наш конвейер мы можем добавить группировку одной строкой:

// GROUP BY e.id
table = table.groupBy("e_id")

И далее все «посты» нашего конвейера можно реализовать очевидным, я надеюсь, образом с помощью библиотечных методов для списков:

    // HAVING sum(de.training_budget) > 80000
    table = table.filter { (it["training_budget"] as Collection<Int>).sum() > 80000 }

    // ORDER BY sum(training_budget) desc
    table = table.sortedByDescending { (it["training_budget"] as Collection<Int>).sum() }

    // OFFSET 1
    table = table.drop(1)

    // LIMIT 1
    table = table.take(1)

    // SELECT e.id,
    //       e.name || ', паспорт: ' || e.passport as name,
    //       sum(training_budget) as sum,
    //       array_agg(d.name || ' - ' || de.training_budget) as report
    table = table.map {
        mapOf(
            "e_id" to it["e_id"],
            "e_name" to "${(it["e_name"] as Collection<String>).first()}, паспорт: ${(it["passport"] as Collection<String>).first()}",
            "sum" to (it["training_budget"] as Collection<Int>).sum(),
            "details" to (it["d_name"] as Collection<String>).zip((it["training_budget"] as Collection<Int>))
                .joinToString(",", "{", "}") { (n, b) -> "$n - $b" }
        )
    }

Ну и в качестве вишенки на торте, давайте соберём этот код в единую цепочку вызовов методов, где каждый метод получает на вход и возвращает таблицу (Table aka List<Row>), и эти таблицы едут по ней как по конвейеру:

employees
    .innerJoin(departmentEmployees) { e, de -> e["e_id"] == de["employee_id"] }
    .innerJoin(departments) { de, d -> de["department_id"] == d["d_id"] }
    .filter { it["location"] == "Новосибирск" }
    .groupBy("e_id")
    .filter { (it["training_budget"] as Collection<Int>).sum() > 80000 }
    .sortedByDescending { (it["training_budget"] as Collection<Int>).sum() }
    .drop(1)
    .take(1)
    .map {
        mapOf(
            "e_id" to it["e_id"],
            "e_name" to "${(it["e_name"] as Collection<String>).first()}, паспорт: ${(it["passport"] as Collection<String>).first()}",
            "sum" to (it["training_budget"] as Collection<Int>).sum(),
            "details" to (it["d_name"] as Collection<String>).zip((it["training_budget"] as Collection<Int>))
                .joinToString(",", "{", "}") { (n, b) -> "$n - $b" }
        )
    }
    .printRelation()

---

Но это ещё не всё. На самом деле, там, где это возможно, по конвейеру едут не таблицы, а строки.

SELECT-запрос, как конвейер, по которому едут строки

В базах данных реальных продуктов хранятся миллионы и миллиарды строк. Поэтому настоящие СУБД делают всё возможное, чтобы рамках обработки запроса считывать с диска только необходимый минимум данных. И на самом деле операторы SQL, по возможности, работают с отдельными строками, а не таблицами целиком.

Для иллюстрации этого, давайте рассмотрим план запроса к одной из таблиц моего текущего проекта на ~3.5М строк:

SELECT * FROM events;

У него будет такой план:

Seq Scan on events  (cost=0.00..107812.46 rows=3632446 width=145) (actual time=0.024..295.777 rows=3632446 loops=1)
Planning Time: 0.093 ms
Execution Time: 374.656 ms

Обратите внимание на то, как указывается фактическое время выполнения: actual time=0.024..295.777. Для времени выполнения приводится два числа — время старта и полное время запроса.

И если этот запрос выполнить в IDEA, например, то первую страницу с 500 записей он вернёт мгновенно. Если же перейти на последнюю страницу, то IDEA уже задумается на несколько секунд.

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

Поэтому более реалистичной реализацией нашего конвейера будет реализация не на List-ах, а на Sequence-ах — ленивых коллекциях, которые в промежуточных операторах в духе map/filter обрабатывают элементы по одному и по требованию, а требуют данные только терминальные операторы вроде toList, forEach и…​ groupBy.

И так как фактическое API List и Sequence для наших нужд совпадает полностью, то переход на ленивую реализацию нашего конвейера осуществляется одной строкой (перевода исходной таблицы в последовательность) в описании конвейера:

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

Здесь мы в пяти местах меняем типы с List/Iterable на Sequence и в двух местах превращаем списки в последовательности.

В этом коде сто́ит обратить внимание на строки 78–80 ленивой реализации:

fun LazyTable.groupBy(groupingKey: String): LazyTable {
    // ...
    val rowGroups: Collection<List<Row>> = this
        .groupBy { it[groupingKey] } // группируем строки таблицы по ключу
        .values
    // ...
}

groupBy даже для последовательности возвращает eager коллекцию!

И если задуматься — это вполне логично. groupBy не может вернуть даже первую группу, не просмотрев все входящие данные. Потому что порядок никто не гарантирует, и два элемента с одинаковым ключом группировки могут идти первым и последним.

И СУБД в общем случае тоже не волшебники и у них нет Оракула, который бы сказал: «так, вот тут стоп, больше в этой группе строк нет и её можно выдавать». Поэтому в общем случае GROUP BY приводит к считыванию всего набора данных (который, напомню, в реальных продуктах может состоять из миллионов и миллиардов строк).

Тем не менее СУБД хоть и не волшебники, но имеют множество дополнительной информации о конвейере и данных, которые по нему едут. И если так вышло, что выше по конвейеру данные были отсортированы по ключу группировки, то СУБД может воспользоваться этой информацией и избежать полного просмотра данных перед выдачей первой группы.

Это можно проиллюстрировать на следующей паре синтаксически идентичных запросов:

SELECT addition_date_time, count(*)
FROM events
GROUP BY addition_date_time
LIMIT 1;

SELECT created_date_time, count(*)
FROM events
GROUP by created_date_time
LIMIT 1;

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

План первого запроса выглядит так:

Limit  (cost=0.43..0.48 rows=1 width=16) (actual time=0.026..0.026 rows=1 loops=1)
  ->  GroupAggregate  (cost=0.43..150112.62 rows=3194779 width=16) (actual time=0.025..0.025 rows=1 loops=1)
        Group Key: addition_date_time
        ->  Index Only Scan using events_addition_date_time_idx on events  (cost=0.43..100002.60 rows=3632446 width=8) (actual time=0.017..0.019 rows=5 loops=1)
              Heap Fetches: 0
Planning Time: 0.096 ms
Execution Time: 0.047 ms

Здесь видно, как СУБД пользуется тем, что у нас есть индекс по addition_date_time. Соответственно, она может загружать данные в порядке возрастания нашего ключа группировки. И тогда увеличение его значения будет сигналом о том, что группу можно выдавать — далее строк с таким значением точно уже не будет.

В частности, это видно по разнице в оценке стоимости времени старта и завершения узла группировки (0.43..100002.60 условных единиц — время старта намного меньше полного времени) и по фактическому количеству строк (5 штук) оператора сканирования индекса в 4-й строке.

Для created_date_time же у нас индекса нет, и план второго запроса выглядит уже сильно по-другому:

Limit  (cost=263677.47..263677.74 rows=1 width=16) (actual time=427.237..435.087 rows=1 loops=1)
  ->  Finalize GroupAggregate  (cost=263677.47..525823.00 rows=961451 width=16) (actual time=422.557..430.406 rows=1 loops=1)
        Group Key: created_date_time
        ->  Gather Merge  (cost=263677.47..506593.98 rows=1922902 width=16) (actual time=422.539..430.388 rows=2 loops=1)
              Workers Planned: 2
              Workers Launched: 2
              ->  Partial GroupAggregate  (cost=262677.45..283643.35 rows=961451 width=16) (actual time=401.635..401.762 rows=518 loops=3)
                    Group Key: created_date_time
                    ->  Sort  (cost=262677.45..266461.24 rows=1513519 width=8) (actual time=401.613..401.648 rows=519 loops=3)
                          Sort Key: created_date_time
                          Sort Method: external merge  Disk: 21352kB
                          Worker 0:  Sort Method: external merge  Disk: 20240kB
                          Worker 1:  Sort Method: external merge  Disk: 22616kB
                          ->  Parallel Seq Scan on events  (cost=0.00..86623.19 rows=1513519 width=8) (actual time=3.152..147.662 rows=1210815 loops=3)
Planning Time: 0.091 ms
JIT:
  Functions: 22
"  Options: Inlining false, Optimization false, Expressions true, Deforming true"
"  Timing: Generation 1.144 ms, Inlining 0.000 ms, Optimization 0.596 ms, Emission 13.454 ms, Total 15.194 ms"
Execution Time: 438.515 ms

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

И разница между запросами становится очевидна во времени их исполнения — фактически 0 секунд против половины секунды.

И собственно эта та причина, по которой лучше по возможности переносить фильтрацию в WHERE — это позволит сократить объём загружаемых и сортируемых данных в рамках группировки. В этом конкретном случае, моя конкретная версия PostgreSQL оказалась достаточно умной, для того, чтобы самостоятельно «пропушить» фильтрацию выше группировки по конвейеру:

SELECT created_date_time, count(*)
FROM events
GROUP by created_date_time
HAVING created_date_time > now() - '1 month'::interval AND count(*) > 1
LIMIT 1;

---

Limit  (cost=103786.39..103786.77 rows=1 width=16) (actual time=276.080..281.620 rows=1 loops=1)
  ->  Finalize GroupAggregate  (cost=103786.39..121457.98 rows=45831 width=16) (actual time=271.362..276.902 rows=1 loops=1)
        Group Key: created_date_time
        Filter: (count(*) > 1)
        Rows Removed by Filter: 8
        ->  Gather Merge  (cost=103786.39..118830.66 rows=121154 width=16) (actual time=271.343..276.883 rows=10 loops=1)
              Workers Planned: 2
              Workers Launched: 2
              ->  Partial GroupAggregate  (cost=102786.36..103846.46 rows=60577 width=16) (actual time=256.635..256.750 rows=394 loops=3)
                    Group Key: created_date_time
                    ->  Sort  (cost=102786.36..102937.81 rows=60577 width=8) (actual time=256.613..256.635 rows=614 loops=3)
                          Sort Key: created_date_time
                          Sort Method: quicksort  Memory: 3664kB
                          Worker 0:  Sort Method: quicksort  Memory: 3783kB
                          Worker 1:  Sort Method: quicksort  Memory: 3742kB
                          ->  Parallel Seq Scan on events  (cost=0.00..97974.59 rows=60577 width=8) (actual time=238.770..248.230 rows=50433 loops=3)
                                Filter: (created_date_time > (now() - '1 mon'::interval))
                                Rows Removed by Filter: 1160382
Planning Time: 0.109 ms
JIT:
  Functions: 29
"  Options: Inlining false, Optimization false, Expressions true, Deforming true"
"  Timing: Generation 1.619 ms, Inlining 0.000 ms, Optimization 0.720 ms, Emission 15.444 ms, Total 17.783 ms"
Execution Time: 282.480 ms

Обратите внимание, что фильтрация идёт в листовом узле чтения данных в 25-й строке.

Но лучше всё-таки судьбу не испытывать и выносить в WHERE все возможные фильтры данных.

Заключение

Успешно отбившись от атаки NoSQL баз данных, реляционные СУБД доминируют на рынке уже порядка 40 лет, и я не вижу причин, чтобы ситуация изменилась в обозримом будущем.

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

PS>

Все исходники доступны на GitHub-е.