Неубывание селективности

Еще один инженерный концепт, который вам в жизни пригодится.

Подход, он же рецепт, отвечает на вопрос из ситуации «у нас что-то происходит, куда копать то вообще». Вариантов с виду много, ответов мало.

Мы можем пойти и исследовать. Можем — что-то понять. А может — вопросов и вариантов станет только больше.

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

В общем, с пространством вариантов надо что-то делать.

Ликбез инженерный, на пальцах.
Гуманитариям можно пролистать на страницу вниз.

Селективность — это когда данные выгребают из больших хранилищ. Из баз данных, обычно. Данных валяются миллионы элементов (записей), нужно быстренько найти оттуда то, что от нас запросили. Для этого хранилище данных, и его проектировщики, упрощают себе жизнь — например, строят поисковые индексы. Самый известный вариант — бинарное (N-ary) дерево.

К примеру, если я возьму 1 млн числовых значений (от 0 до 9^10*5), и разложу их по 10 кучкам, ориентируясь по первой цифре в числе — в каждой итоговой кучке окажется по 100 тыс значений, а селективность каждой кучки, и самого подхода = 10.

Но если я так буду делать, то по мере роста количества от 0 до собственно миллиона, кучки будут заполняться неравномерно: сначала первая, потом вторая итп. В моменте селективность будет у подхода = 10, а практическая у кучек = 1, если у нас всего 100к начальных значений. Окей, годится: а если я возьму не первую, а последнюю цифру в числе? Оппа вуаля, распределение становится равномерным, и почти всегда = 10.

Когда данных в выборке становится не меньше, а больше, селективность становится менее единицы, тогда обычно используют понятие мультипликатор. Было 10, стало 20 — селективность 0.5, мультипликатор = 1/0.5 = 2. Селективность иногда обозначают «s» (а не «c»), чтобы не путать, потому что «c» это cardinality, а оно 1/s.

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

Допустим, пример: я хочу найти подмножество товаров из миллиона, у которых город = Москва (городов 20), цвет = красный (цветов 7). Еще найти среди них те, которые пересекаются с теми 50, которые выбрал пользователь (то есть, усечение множества). Еще показать все их продажи за год (то есть, расширение множества). И вот там делать выводы. Пример только для иллюстрации, не парьтесь. Допустим, все распределения равномерные.

Как в этом случае поступим?

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

Если хоть один товар продавался более 1 раза, выборка уже (с мультипликатором) растёт за миллион, и селективность такого подхода только бессмысленно снизится: иногда в разы, или на порядки.
Надо сначала что-то отфильтровать, а потом работать. Вопрос, что.

Если я возьму выборку по городу, 1m/20, я получу 50к товаров, селективность 20.
Если я возьму выборку по цветам, 1m/7, я получу ~142k товаров, селективность 7.
Их нет даже смысла домножать на мультипликатор по заказам, т.к селективность дальше только снизится.

Если я возьму выборку сразу по заданным 50, я получу 50 товаров, селективность = 20000. Ого, неплохо, годится.

Если я возьму уже 50 (S=20k), домножу их на количество заказов (например, mult=2, каждый товар покупали минимум дважды), я получу итоговые S=10k. Стало хуже, значит — дальше мы можем снова огрестись. Так делать не надо. Какие еще варианты есть, смотрим.

Если же я возьму те 50, отфильтрую их по городу и цвету, что я получу? S=20000*20*7 селективность станет 2800000. Это даже больше исходной выборки, может и вообще товаров не будет. Но если нам так надо, значит нам так надо. Поделим S на mult=2 (или домножим на 0.5), итоговая S=1400000

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

Если вы описанный пример сымитируете на современной базе данных, и попросите план запроса — увидите как раз описанную логику решения.

Теперь наложим это техническое знание на наши бытовые процессы.

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

Дядя монах Оккам (ударение на О) тоже нам о чем-то таком говорил. Просто не уточнял, как именно. Ему простительно, он в 13 м веке жил.

Есть горизонт вариантов и решений — сначала иди, и сужай, по-максимуму. В том порядке, в котором неубывает селективность; так полезнее.

Правило narrow-down (оно и есть) как раз помогает в практическом разруливании всяких непоняток, и хаоса из окружающего мира.

Отладка, формализация, поиски закономерностей, структуры, причин-следствий, всякое отделение мух от котлет — значащих факторов от незначащих.

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