Выберите объект Foo без каких-либо конкретных событий Bar

Рассмотрим две таблицы:

Foo:
  id INT,
  name VARCHAR

Bar:
  id INT,
  foo_id INT REFERENCES Foo(id),
  event_type VARCHAR DEFAULT NULL,
  event_duration INT DEFAULT NULL

Каждый элемент Foo может иметь несколько событий Bar. Как запросить элементы Foo, у которых нет событий Bar, отвечающих любому из следующих условий:

  1. event_type, не являющееся одним из следующих значений: 'miss', 'scratch', 'scrape'
  2. event_duration, который не равен нулю

Например, рассмотрим:

Foo id=1:
    event_type: hit       | event_duration: NULL
    event_type: poke      | event_duration: NULL
    event_type: capture   | event_duration: NULL

Foo id=2:
    event_type: hit       | event_duration: 2
    event_type: poke      | event_duration: NULL
    event_type: capture   | event_duration: NULL

Foo id=3:
    event_type: miss      | event_duration: NULL
    event_type: poke      | event_duration: NULL
    event_type: capture   | event_duration: NULL

Foo id=4:
    event_type: strike    | event_duration: NULL
    event_type: hit       | event_duration: NULL
    event_type: land      | event_duration: NULL

Должны быть возвращены только элементы Foo с id=1 и id=4. Элемент с id=2 не должен возвращаться, так как один из его event_duration не равен NULL. Элемент с id=3 не должен быть возвращен, так как один из его event_type является miss (который находится в списке запрещенных типов_событий).

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

SELECT
    f.name
FROM
    Foo f JOIN Bar b ON f.id = b.foo_id
GROUP BY
    b.event_type, b.event_duration
HAVING
    b.event_type not in ('miss', 'scratch', 'scrape')
  AND
    b.event_duration not null

Вот еще один нерабочий запрос:

SELECT
    f.name
FROM
    (
    SELECT
        f.name, b.event_duration
    FROM
        Foo f JOIN Bar b ON f.id = b.foo_id
    GROUP BY
        b.event_type
    HAVING
        b.event_type not in ('miss', 'scratch', 'scrape')
    )
GROUP BY
    b.event_duration
HAVING
    b.event_duration not null

Было много других неработающих запросов с несколькими идеями о JOIN и подзапросах. Обратите внимание, что в таблице Foo почти 5 миллионов строк, а в таблице Bar почти 2 миллиона строк. Таблицы индексируются по соответствующим полям, но O(n^2) на таких больших таблицах это просто невозможно.


mysql sql join group-by having
person dotancohen    schedule 26.01.2014    source источник

Ответы (4)


arrow_upward
0
arrow_downward

Вы можете использовать NOT EXISTS для получения желаемых результатов.

SELECT f.name
FROM foo f
WHERE NOT EXISTS (SELECT 1 FROM bar b
                  WHERE b.foo_id = f.id
                  AND (b.event_type IN ('miss','scratch','scrape')
                       OR b.event_duration IS NOT NULL)
                  )
person Tin Tran    schedule 26.01.2014
comment
Спасибо. Этот запрос действительно выражает то, что мне нужно, но он делает это абсолютно наименее эффективным способом. Вы создаете временную таблицу со всеми результатами, которые не должны быть возвращены, а затем сравниваете каждую строку в существующей базе данных, чтобы убедиться, что они не совпадают. Это означает, что каждая из 5 миллионов строк существующей базы данных сравнивается с 5 миллионами несовпадающих строк, чтобы найти лишь несколько совпадающих. Это O(n^2) операция. - person dotancohen; 26.01.2014

arrow_upward
0
arrow_downward

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

select f1.id, f1.name from
Foo f1 
left join 

(
     select distinct f.id 
     from Foo f
     join Bar b on f.id = b.foo_id
     where
     ( b.event_type IN ('miss','scratch','scrape') ) OR ( b.event_duration IS NOT NULL )
) f2 on f1.id = f2.id 

WHERE
(f2.id is null)
person peter.petrov    schedule 26.01.2014
comment
Спасибо, но этот запрос не может работать с таблицами указанного размера (миллионы строк). Вы создаете временную таблицу со всеми результатами, которые не должны возвращаться, а затем сравниваете каждую строку в существующей базе данных, чтобы убедиться, что они не совпадают. Это означает, что каждая из 5 миллионов строк существующей базы данных сравнивается с 5 миллионами несовпадающих строк, чтобы найти лишь несколько совпадающих. Это операция O(n^2). - person dotancohen; 26.01.2014
comment
Я не уверен, как вы можете добиться большего успеха, чем проверять все строки из Bar в любом случае. Тогда я бы не сказал, что соответствие от f1 до f2 равно O (n ^ 2), потому что вы сопоставляете идентификатор, который является PK и индексируется. Так что на самом деле это не так, как взять каждую строку из f2 и сопоставить ее с каждой строкой из f1. Я бы грубо/интуитивно сказал, что это O (max (n, m)), где n и m - размеры Foo и Bar. Но я не уверен. Итак, хорошо, вы можете подождать ответа от более крупного эксперта здесь. Кстати, вы пробовали мой запрос? Вы можете быть удивлены, так как я думаю, что ваши оценки на самом деле не так уж близки к тому, как это делает БД. - person peter.petrov; 26.01.2014

arrow_upward
0
arrow_downward

Вы можете создать поле «кэш-счетчик» в таблице Foo, которое будет просто содержать количество связанных элементов Bar.

Я думаю, что ваша проблема будет быстрее решена двумя запросами:

  1. запрос для обновления кеша счетчика для всех элементов Foo. Поскольку это будет смотреть только на индексированные столбцы, это должно быть довольно быстро.

  2. второй запрос, который НЕ будет выполнять какие-либо соединения, а будет просто запрашивать таблицу Foo по нужным вам критериям и иметь значение «кэш счетчика», равное 0.

При грамотном управлении столбцом «счетчик кеша» вам, возможно, придется выполнить первый запрос только один раз. (Конечно, ваша программа должна будет поддерживать синхронизацию столбца "counter cache").

person Ilie Pandia    schedule 26.01.2014
comment
Спасибо Илие. Это сработало бы, если бы я каждый раз искал одни и те же типы событий или продолжительность бара. Однако на самом деле каждый запрос будет для другого списка event_types или продолжительности. - person dotancohen; 26.01.2014
comment
Я все еще думаю, что сегментация проблемы, основанная на знании того, сколько данных доступно для различных типов событий и продолжительности, будет самой быстрой. Поэтому сначала вам нужно будет сгенерировать некоторую статистику. И на основе этой статистики найти стратегию для запросов к базе данных. Запрос на перехват, который не принимает во внимание распределение данных, я думаю, будет очень медленным в большинстве случаев. Поэтому я бы нашел способ сегментировать свои данные, чтобы O (n ^ 2) было не так уж плохо. Создайте несколько полей кэша счетчиков, если вам нужно... просто найдите способ уменьшить количество строк, которые войдут в соединение O (n ^ 2). - person Ilie Pandia; 26.01.2014

arrow_upward
0
arrow_downward

я бы попробовал этот

SELECT DISTINCT f.Id
FROM Foo f
WHERE NOT EXIST (
                 SELECT DISTINCT b.foo_id
                 WHERE b.foo_id = f.Id
                       AND   (b.event_type IN ('miss','scratch','scrape')                     
                               OR b.event_duration IS NOT NULL)
                 )

Вы также можете использовать слияние следующим образом:

  1. Создайте список различных идентификаторов баров, которые либо имеют «промах», «царапину», «скребок» в event_type ИЛИ event_duration не равно нулю
  2. Объединить Foo и Bar
  3. Используйте WHEN NOT MATCHED, чтобы найти свой результат
person Mzf    schedule 26.01.2014
comment
Спасибо, но это в MySQL, а не в SQL-сервере. В любом случае, предложение merge такое же, как (несостоятельное) предложение подзапроса, только таблица хранится на диске. - person dotancohen; 26.01.2014