Соединение между таблицами сопоставления (соединения) с определенной кардинальностью

У меня есть простой вопрос о наиболее эффективном способе выполнения определенного соединения.

Возьмите эти три таблицы, настоящие имена были изменены, чтобы защитить невиновных:

Таблица: животное

animal_id   name   ...
======================
1           bunny
2           bear
3           cat
4           mouse

Таблица: теги

tag_id     tag
==================
1          fluffy
2          brown
3          cute
4          small

Таблица сопоставления: animal_tag

animal_id   tag_id
==================
1           1
1           2
1           3
2           2
3           4
4           2

Я хочу найти всех животных, помеченных как "пушистые", "коричневые" и "милые". То есть животное должно быть помечено всеми тремя. На самом деле количество необходимых тегов может варьироваться, но это не имеет значения для данного обсуждения. Это запрос, который я придумал:

SELECT * FROM animal
JOIN (
      SELECT at.animal_id FROM animal_tag at
      WHERE at.tag_id IN (
                          SELECT tg.tag_id FROM tag tg
                          WHERE tg.tag='fluffy' OR tg.tag='brown' OR tg.tag='cute'
                          )
      GROUP BY at.animal_id HAVING COUNT(at.tag_id)=3
      ) AS jt
ON animal.animal_id=jt.animal_id

В таблице с тысячами «животных» и сотнями «тегов» этот запрос выполняет достойно... 10 миллисекунд. Однако, когда я смотрю на план запроса (Apache Derby — это БД), оценочная стоимость оптимизатора довольно высока (9945,12), а план довольно обширен. Для такого «простого» запроса я обычно пытаюсь получить планы запросов с оценочной стоимостью, выраженной однозначным или двузначным числом.

Итак, мой вопрос: есть ли лучший способ выполнить этот запрос? Кажется, простой запрос, но я был в тупике, придумывая что-нибудь лучше.


person brettw    schedule 07.02.2012    source источник
comment
я думаю, вы должны использовать AND вместо OR в WHERE tg.tag='fluffy' OR tg.tag='brown' OR tg.tag='cute'   -  person John Woo    schedule 07.02.2012
comment
@johntotetwoo Ни одна одна строка в tag не соответствует более чем одному значению, поэтому использование И не приведет к получению совпадающих строк.   -  person Branko Dimitrijevic    schedule 07.02.2012
comment
@BrankoDimitrijevic, ты прав! моя вина. о чем я думаю.   -  person John Woo    schedule 07.02.2012
comment
Взгляните на эту статью о относительное деление. Это должно дать вам еще пару вещей, чтобы попробовать.   -  person Mikael Eriksson    schedule 07.02.2012
comment
@MikaelEriksson спасибо за отличную ссылку!   -  person brettw    schedule 07.02.2012
comment
Реляционное подразделение — это действительно то, о чем вы спрашиваете, известное как поставщик, который поставляет все детали. Вот еще одна полезная статья: Как сделать реляционное деление понятным.   -  person onedaywhen    schedule 07.02.2012


Ответы (5)


Вы можете создать временную таблицу, используя DECLARE GLOBAL TEMPORARY TABLE. А затем выполните ВНУТРЕННЕЕ СОЕДИНЕНИЕ, чтобы устранить «ГДЕ В». Работа с соединениями, основанными на множестве, обычно намного эффективнее, чем операторы Where, которые должны оцениваться для каждой строки.

person Dylan Bijnagte    schedule 07.02.2012
comment
на практике запрос внутри WHERE IN оптимизируется базой данных таким образом, что он выполняется только один раз, поскольку он не зависит от внешнего запроса. Кроме того, поскольку он возвращает только (в данном случае 3 строки или небольшое число на практике), накладные расходы на создание и выборку во временную таблицу превышают первоначальную стоимость запроса. - person brettw; 07.02.2012

попробуй это:

SELECT DISTINCT f.Animal_ID, g.Name
FROM Animal f INNER JOIN 
    (SELECT a.Animal_ID, a.Name, COUNT(*) as iCount
     FROM   Animal a INNER JOIN Animal_Tag b
                  ON a.Animal_ID = b.animal_ID
                     INNER JOIN Tags c
                  On b.tag_ID = c.tag_ID
    WHERE c.tag IN ('fluffy', 'brown', 'cute') -- list all tags here
    GROUP BY a.Animal_ID) g
WHERE g.iCount = 3 -- No. of tags

ОБНОВЛЕНИЕ

    SELECT DISTINCT a.Animal_ID, a.Name, COUNT(*) as iCount
    FROM    Animal a INNER JOIN Animal_Tag b
                  ON a.Animal_ID = b.animal_ID
                     INNER JOIN Tags c
                  On b.tag_ID = c.tag_ID
    WHERE c.tag IN ('fluffy', 'brown', 'cute') -- list all tags here
    GROUP BY Animal_ID
    HAVING  iCount = 3 -- No. of tags
person John Woo    schedule 07.02.2012
comment
Спасибо, я ценю усилия. Этот запрос правильный, поскольку он дает тот же результат, что и мой запрос. К сожалению, при подключении его к нашему коду расчетная стоимость несколько выше, а время выполнения немного больше (наш запрос — 0,28 с, ваш — 0,32 с). В основном эквивалентны с точки зрения производительности (по крайней мере, с нашим набором данных). Спасибо еще раз. - person brettw; 07.02.2012
comment
@brettw я обновил этот запрос. уменьшает ли это предполагаемую стоимость? - person John Woo; 07.02.2012
comment
@johntotewoo Не знаю почему, но Дерби не нравится этот запрос. Ошибка: ссылка на столбец "A.NAME" недействительна или является частью недопустимого выражения. Для списка SELECT с GROUP BY выбираемые столбцы и выражения могут содержать только допустимые выражения группировки и допустимые агрегатные выражения. - person brettw; 07.02.2012
comment
Я немного модифицировал его, чтобы он работал в Derby, но предполагаемая стоимость и время выполнения все равно немного выше. Я думаю, что мой первоначальный запрос настолько хорош, насколько я могу ожидать. Спасибо за попытку. - person brettw; 07.02.2012

Попробуйте это:

SELECT a.*
FROM animal a
INNER JOIN 
  ( 
    SELECT at.animal_id
    FROM tag t
    INNER JOIN animal_tag at ON at.tag_id = t.tag_id
    WHERE tag IN ('fluffy', 'brown', 'cute')
    GROUP BY at.animal_id
    HAVING count(*) = 3
  ) f ON  a.animal_id = f.animal_id

Вот еще вариант, просто для удовольствия:

SELECT a.*
FROM animal a
INNER JOIN animal_tag at1 on at1.animal_id = a.animal_id
INNER JOIN tag t1 on t1.tag_id = at1.tag_id
INNER JOIN animal_tag at2 on at2.animal_id = a.animal_id
INNER JOIN tag t2 on t2.tag_id = at2.tag_id
INNER JOIN animal_tag at3 on at3.animal_id = a.animal_id
INNER JOIN tag t3 on t3.tag_id = at3.tag_id
WHERE t1.tag = 'fluffy' AND t2.tag = 'brown' AND t3.tag = 'cute'

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

person Joel Coehoorn    schedule 07.02.2012
comment
Превосходно. Первый запрос не подходит для Apache Derby, поскольку он не поддерживает оператор WITH. А вот второй вариант интересен. Он поставляется с более низкой стоимостью оптимизатора (5966,82), чем мой оригинал, но на практике время выполнения примерно на 10% больше (в среднем по 10 запускам). - person brettw; 07.02.2012
comment
@brettw - переписал первый запрос, чтобы пропустить cte. - person Joel Coehoorn; 07.02.2012
comment
Интересно, что ваш пересмотренный первый запрос компилируется точно в тот же план доступа, что и мой запрос, включая точную расчетную стоимость (9945,12). - person brettw; 07.02.2012
comment
@brettw - Первая версия, предоставленная Джоэлом Коегоорном, - это то, что я бы тоже предложил попробовать. Если бы вы могли заранее определить идентификатор тега, вы могли бы удалить таблицу tag из запроса и выполнить предложение where в подзапросе, например where tag_id in (1, 2, 3) - person Mikael Eriksson; 07.02.2012

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

Хотя много лет назад я прошел курс реляционной модели данных Кодда, этот курс, как и многие другие, на самом деле не охватывал реляционное деление. Невольно мой первоначальный запрос на самом деле является приложением Relational Division.

Ссылаясь на слайд 26–27 в этой презентации, посвященный реляционному делению, мой запрос применяет метод сравнения мощностей наборов. Я попробовал некоторые другие методы, упомянутые для применения реляционного деления, но, по крайней мере, в моем случае метод подсчета обеспечивает самое быстрое время выполнения. Я призываю всех, кто интересуется этой проблемой, прочитать вышеупомянутую стопку слайдов, а также статью, на которую ссылается на этой странице Микаэль Эрикссон. Еще раз спасибо всем.

person brettw    schedule 08.02.2012

Мне было интересно, насколько плохо было бы использовать там реляционное деление. Не могли бы вы запустить его? Я знаю, что это займет больше времени, но я заинтригован тем, сколько :) Если вы можете предоставить и ориентировочную стоимость, и время, было бы здорово.

select a2.animal_id, a2.animal_name from animal2 a2
where not exists (
    select * from animal1 a1, tags t1
    where not exists (
        select * from animal_tag at1
        where at1.animal_id = a1.animal_id and at1.animal_tag = t1.tag_id
    ) and a2.animal_id = a1.animal_id and t1.tag in ('fluffy', 'brown', 'cute')
)

Теперь ищу быстрый запрос, я не могу думать быстрее, чем у Джона или у вас. На самом деле у Джона может быть немного медленнее, чем у вас, потому что он выполняет ненужные операции (удалить отдельные и удалить количество (*) из выбора):

SELECT a.Animal_ID, a.Name FROM Animal a
INNER JOIN Animal_Tag b ON a.Animal_ID = b.animal_ID
INNER JOIN Tags c On b.tag_ID = c.tag_ID
WHERE c.tag IN ('fluffy', 'brown', 'cute') -- list all tags here
GROUP BY Animal_ID, a.Name
HAVING count(*) = 3 -- No. of tags

Это должно быть так же быстро, как и у вас.

PS: Есть ли способ удалить эту чертову 3, не дублируя предложение where? Мой мозг кипит :)

person Mosty Mostacho    schedule 07.02.2012
comment
CTE позволит вам удалить избыточность, потому что вы можете дважды ссылаться на CTE в основном запросе (второй раз будет запросом count (*) для получения числа). Но Дерби их не поддерживает. - person Joel Coehoorn; 07.02.2012