Как эффективно сравнить и найти список целых чисел?

Question

У меня есть база данных, заполненная 1 миллионом объектов. Каждый объект имеет поле 'tags' - набор целых чисел.

Например:

object1: tags(1,3,4)
object2: tags(2)
object3: tags(3,4)
object4: tags(5)

и т. Д.

Параметр запроса - это набор целых чисел, попробуем q (3,4,5)

object1 does not match ('1' not in '3,4,5')
object2 does not match ('2' not in '3,4,5')
object3 matches ('3 and 4' in '3,4,5' )
object4 matches ('5' in '3,4,5' )

Как эффективно выбирать совпавшие объекты?

Answer 1

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

Вам нужно смоделировать сопоставление между объектами и тегами в отдельной таблице.

CREATE TABLE Tagged (
  object_id  INT NOT NULL,
  tag_id     INT NOT NULL,
  PRIMARY KEY (object_id, tag_id),
  FOREIGN KEY (object_id) REFERENCES Objects(object_id),
  FOREIGN KEY (tag_id) REFERENCES Tags(tag_id)
);

Вставьте одну строку для каждой пары объект / тег. Конечно, это означает, что у вас есть несколько строк для каждого object_id, но это нормально.

Вы можете запросить все объекты с тегами 3,4,5:

SELECT DISTINCT object_id
FROM Tagged
WHERE tag_id IN (3, 4, 5);

Но это соответствует object1, который вам не нужен. Вы хотите исключить объекты, у которых есть другие теги, кроме 3,4,5.

SELECT DISTINCT t1.object_id
FROM Tagged t1 
 LEFT OUTER JOIN Tagged t2
 ON (t1.object_id = t2.object_id AND t2.tag_id NOT IN (3, 4, 5))
WHERE t1.tag_id IN (3, 4, 5)
 AND t2.object_id IS NULL;

Answer 2

Учитывая, что вы используете PostgreSQL, вы можете использовать его array datatype и его операторы содержит / перекрываются.

Конечно, это сильно привязало бы ваше приложение к PostgreSQL, что может быть нежелательно. С другой стороны, это может сэкономить вам кодирование, когда оно действительно необходимо (т. Е. Когда вам, наконец, придется перенести его в другую базу данных)

Хотя, учитывая, что в Python для этой конкретной группы операций установлен установленный тип данных , использование PostgreSQL может оказаться излишним (в зависимости от требований к производительности)

>>> a = set([1,2,3])
>>> a
set([1, 2, 3])
>>> 1 in a
True
>>> set([1,2]) in a
False
>>> set([2,3]) & a
set([2, 3])
>>> set([8,9]) & a
set([])
>>> set([1,3]) & a
set([1, 3])
>>>

Answer 3

Если я правильно понял, это что-то вроде:

Post-> posttags <-tags

вид схемы.

Интересно, почему ты так делаешь?

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

Подобно классу Post и Tag в SQLAlchemy, с отображением Post, имеющим свойство 'tags', которое может загружать множество объектов Tag для данного объекта Post.

Если это так, такие операции обычно очень дороги в ORM и должны выполняться с поддержкой ORM операторов SQL или с использованием прямых dbapi, подобных psycopg2. Опять же, если количество объектов, загруженных из запроса, огромно (с учетом вашего 1 миллиона), вам нужен компьютер с большим количеством ресурсов (или, может быть, вообще без него - pure ORM не рекомендуется).

Если это не ORM и все же ваши теги хранятся как (наборы), то я думаю, что что-то не так со схемой.

posttags - это отношение «многие ко многим», как я его вижу, и это отдельная таблица (которая легко запрашивается), а не «набор» в таблице сообщений.

Answer 4

Извините. Похоже, мне было трудно хорошо объяснить проблему:)

Тег 'postgresql' здесь гораздо более значимый, чем 'python'. Самостоятельно соединенный TAG-стол с условием IS NULL - вот что мне действительно нужно.

SQLalchemy также хороший совет.

Спасибо всем.

Answer 5

Мне кажется, что issubset() метод наборов - это то, что вы ищете:

tags(1, 2, 3).issubset(q(1, 2, 3, 4))

Если tags и q являются подклассами класса set. Но я согласен с другими ответами, что решение этого в базе данных будет лучшим решением.

Answer 6

Это базовая теория множеств. Пересечь два набора, и если результат совпадает с оригиналом, то результат "соответствует" В противном случае его нет.

Вы можете применять этот принцип на многих языках. У большинства есть библиотеки для работы с множествами. Вы даже можете сделать это с помощью SQL.

Answer 7

Вы не указали, какую погоду вы хотели бы использовать SQL или считывали ли вы данные в приложение перед этим. Из звуков вещей вы ищете решение на основе кода?

В .NET вы должны заставить класс реализовать интерфейс ICompare и написать свой собственный метод для сравнения двух значений, которые будут возвращать 0 или 1.