SQL - Как DISTINCT так быстро без индекса?

Question

У меня есть база данных с таблицей 'links' с 600 миллионами строк в SQLite.В базе данных есть 2 столбца - столбец src и столбец dest.В настоящее время индексов нет.

Между src и dest существует довольно много общих значений, но также имеется значительное количество дублированных строк.

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

Во-первых, SELECT * FROM links WHERE src=434923 AND dest=5010182.Теперь это возвращает довольно быстро один результат, а затем занимает довольно много времени для запуска, так как я предполагаю, что он выполняет табличное сканирование на оставшихся 600-метровых строках.

Однако, если я делаю SELECT DISTINCT * FROM links, то он сразу же запускаетсявозвращать строки очень быстро.Вопрос в том, как это возможно?Конечно, для каждой строки эта строка должна сравниваться со всеми остальными строками в таблице, но для этого потребуется табличное сканирование оставшихся строк в таблице, которое СЛЕДУЕТ занимает годы!

Есть идеи, почему SELECT DISTINCT намного быстрее, чем стандартный SELECT?

Answer 1

Подумай об этом. Без упорядочения он может возвращать результаты в порядке сканирования. Он просто хранит список (более вероятно, эффективную структуру, такую ​​как b-дерево) значений, замеченных до сих пор. Если данное значение не найдено, оно возвращается и добавляется в структуру учета. Абсолютно не нужно сравнивать все остальные строки.

Answer 2

Чтобы быть более точным, один запрос не быстрее, чем другой.Точнее, количество времени, необходимое для выполнения запроса, должно быть одинаковым для обоих запросов.Разница в том, что запрос с DISTINCT просто имеет больше строк для возврата, поэтому он, кажется, отвечает быстрее, поскольку вы получаете строки с высокой скоростью.Тем не менее, то, что происходит под капотом обоих, - это одно и то же сканирование таблицы.Отличительный запрос имеет структуру данных, хранящую то, что было возвращено, и фильтрует дубликаты.Следовательно, на самом деле ДОЛЖНО потребоваться больше времени, пока запрос не будет завершен, но (возвращенные строки) / время больше, поскольку просто совпадающих строк больше.(Также обратите внимание: некоторые зрители добавляют лимит результатов запроса, который может привести к тому, что отдельный запрос будет казаться быстрее (так как вы достигнете лимита результата и остановитесь)).