найти разницу между двумя очень большим списком

Question

У меня есть два больших списка (может быть сто миллионов элементов), источником каждого списка может быть либо таблица базы данных, либо простой файл.оба списка имеют сопоставимые размеры, оба не отсортированы.Мне нужно найти разницу между ними.Итак, у меня есть 3 сценария:1. List1 - это таблица базы данных (предположим, что в каждой строке просто есть один элемент (ключ), который является строкой), List2 - это большой файл.2. Оба списка взяты из таблиц по 2 дБ.3. оба списка из двух файлов.

в случае 2 я планирую использовать:

select a.item from MyTable a where a.item not in (select b.item form MyTable b)

это явно неэффективно, есть ли лучший способ?

Другой подход:Я планирую отсортировать каждый список, а затем пройтись по ним обоим, чтобы найти разницу.Если список из файла, я должен сначала прочитать его в таблицу базы данных, а затем использовать сортировку базы данных для вывода списка.Означает ли сложность времени выполнения O (nlogn) в сортировке БД?

любой подход - это боль, и кажется, что он будет очень медленным, если в списке участвуют сотни миллионов элементов.какие-либо предложения?

Answer 1

Это не вопрос базы данных.

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

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

Шаг 3. Напишите ваше приложение, чтобы применить алгоритм слияния к двум спискам и таким образом выявить различия. Обратите внимание, что если текстовый файл состоит из множества фрагментов, вам потребуется вторичный алгоритм слияния для подачи основного алгоритма в отсортированном порядке.

Обратите внимание, что если вы не можете использовать UNIX или Linux для сортировки текстовых файлов, то получите исходный код команды сортировки UNIX и перенесите его в свою O / S. Эта статья объясняет почему.

Answer 2

1. Получить оба набора в базу данных при всех сценариях ... этот вид сортировки и определения - это то, для чего нужны БД. Все остальное будет изобретать велосипед.

2. Следующее, вероятно, будет быстрее, чем NOT IN (но проверьте это, чтобы убедиться):

   выберите a.item из MyTable a СЛЕДУЮЩЕЕ СОЕДИНЕНИЕ MyTable B ON A.JoinColumn = B.JoinColumn, где B.JoinColumn IS NULL

Убедитесь, что ваши JoinColumns проиндексированы. Индексация сделает весь вопрос сортировки бесполезным.