Как количество данных влияет на выбор индекса для поиска

Что проверяют

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

Как отвечать

Решает не только объём, но и селективность запроса, нагрузка на запись и то, помещается ли индекс в память.

В реляционных базах:

• маленькая таблица: планировщик PostgreSQL прочитает её целиком даже при наличии индекса, и будет прав;
• B-tree: основной выбор для таблиц в миллионы строк при селективных запросах, поиск за O(log n), поддерживает диапазоны и сортировку;
• BRIN: для огромных таблиц, где данные физически упорядочены (логи, события по времени). Весит на порядки меньше B-tree, но полезен только при корреляции порядка строк с колонкой;
• партиционирование: когда таблица растёт до сотен миллионов строк, отсечение партиций часто даёт больше, чем любой индекс.

В аналитике (ClickHouse, Parquet) вместо точечных индексов работают разреженный первичный ключ и min/max-статистика по блокам, которые позволяют пропускать целые куски данных.

В векторном поиске зависимость нагляднее всего:

• точный перебор (IndexFlatL2 в Faiss): на сотнях тысяч векторов даёт стопроцентную полноту за приемлемое время;
• IVF: делит пространство на кластеры. В pgvector число списков советуют начинать с rows / 1000 до миллиона строк и с sqrt(rows) выше;
• HNSW: высокая полнота и скорость на миллионах, но граф занимает много памяти и строится заметно дольше IVF;
• PQ-сжатие (IndexIVFPQ): для сотен миллионов и миллиардов, когда полные векторы в RAM уже не влезают, ценой точности.

Где спотыкаются

Говорят «данных много, значит хэш-индекс». Для точного совпадения B-tree обычно не хуже, а диапазоны хэш не умеет вообще.

Забывают про запись. Каждый индекс замедляет вставку, а на потоке новых векторов HNSW обходится дороже IVF и по времени, и по памяти.

Выбирают приближённый индекс, не измерив полноту. Сравните recall@k с точным перебором на своих данных, иначе поиск тихо теряет релевантное.