# Реляционные паттерны MapReduce. Лекция 7

## Выборка


Пусть Map принимает кортеж t, если этот кортеж удовлетворяет заданному условию, то продвигается дальше в контекст.

Реализация выборки обходится без Reduce.

## Проекция


Здесь Map также принимает кортеж t, но оставляет в нем только нужные элементы, формируя кортеж g, который продвигает дальше в контекст в качестве ключа, в качестве значений используются нулевые ссылки.


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

## Объединение


На вход Map передаются кортежи из 2-х множеств: A и B. Всякий кортеж просто продвигается дальше в контекст в качестве ключа, в качестве значения выступает нулевая ссылка.


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

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

## Пересечение


На вход Map передаются кортежи из 2-х множеств: A и B. Всякий кортеж просто продвигается дальше в контекст в качестве ключа, в качестве значения выступает нулевая ссылка.


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

## Разность

В данном случае нам важно из какого множества пришел кортеж.


На вход Map передаются кортежи из 2-х множеств: A и B. Всякий кортеж просто продвигается дальше в контекст в качестве ключа, в качестве значения выступает имя множества, из которого пришел кортеж.


Reduce проверяет, что кортеж присутсвует только в 1 множестве, делает он это по длине итерируемого списка. Но требуется и дополнительная проверка: это должно быть именно множество А, только в этом случае кортеж формирует ответ.

## Симметрическая разность


На вход Map передаются кортежи из 2-х множеств: A и B. Всякий кортеж просто продвигается дальше в контекст в качестве ключа, в качестве значения выступает имя множества, из которого пришел кортеж.


В данном случае у Reduce нет проверки множества, поскольку все кортежи, входящие только одно из множеств формируют ответ.

## Агрегирование и группировка данных


Map принимает на вход кортеж, поле, по которому предполагается группировка - **GroupBy**, поле, по которму предполагается агрегирование - **AggregateBy**.

Map записывает в контекст пару ключ-значение, где в качестве ключа используется **GroupBy**, а в качестве значения выступает **AggregateBy**.

✓ Группировка по нужному полю произойдёт автоматически, в фазе shuffle and sort.


✓ Агрегацию значений для отдельного ключа легко выполнить уже в Reduce.

В контекст записывается пара ключ-значение, где **GroupBy** остается в качестве ключа, а в качестве значения выступает результат применения агрегирующей функции к итерируемому списку значений **AggregateBy**.

## Repartition Join (Reduce Join, Sort-Merge Join): Map


Применяется, когда необходимо объединить два множества R и L по ключу k.

Map получает на вход кортежи из каждого множества, и пишет в контекст пары ключ-значение:

1. **Ключ** - ключевое поле k, по которому предполагается соединение. В контексте реляционных баз данных может рассматриваться как первичный ключ или как внешний ключ.
2. **Значение** - информационные поля [ v1, v2, ... ], промаркированные тегом, определяющим множество, из которого пришло значение.

## Repartition Join (Reduce Join, Sort-Merge Join): Reduce


Применяется, когда необходимо объединить два множества R и L по ключу k.

Reduce получает на вход группу значений для одного ключа, и размещает их по двум корзинам, соответствующим каждому входному множеству. Это легко реализовать, создав ассоциативный массив h, который будет содержать всего 2 элемента, **его ключами будут имена входных множеств**, а **значениями списки, моделирующие соответствующие корзины**.

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

После этого Reduce проходит по обеим корзинам и генерирует объединения значений из двух множеств с общим ключом.

## Repartition Join (Reduce Join, Sort-Merge Join): Особенности

**Достоинства**: универсальность.

**Недостатки**:
1. Map отправляет на выход все данные, даже для тех ключей, которые есть только в одном множестве.
2. Reduce должен хранить все значения для одного ключа впамяти.
3. Нужно самостоятельно управлять памятью в случае, если данные в нее не помещаются.

## Replicated Join (Map Join, Hash Join)

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


Для этого можно:
1. Использовать хеш-таблицу, куда загружаются все элементы маленького множества, сгруппированные по ключу k;
2. Осуществить проход по элементам большого множества с помощью задач Map, выполняя поисковый запрос к этой хеш-таблице для каждого входного кортежа.

Сформировать хэш-таблицу можно при помощи ассоциативного массива h в момент реализации задачи Map, поскольку эта таблица будет применяться неоднократно при обработке входного сплита.

**Ключи h** будут определяться значениями ключевого поля k, по которому предполагается соединение.

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

Функция Map принимает на вход кортеж из большого множества, **поле k**, по которому предполагается соединение, выделено **в качестве ключа**, а **полезная нагрузка** с информационными полями **в виде значения**.