[MySQL] NOT filter efficient implementeren

[gnoe93]

Een tijdje geleden vroeg ik me af hoe ik een AND/OR filter kon implementeren in SQL: https://gathering.tweaker...message/48819529#48819529

Nu zou ik ook de functionaliteit willen voorzien om deze om te draaien.

Stel bijvoorbeeld met de tabellen product, category en product_has_category waarbij een product geen of meerdere categorieen kan hebben.

De OR filter lijkt me eenvoudig te implementeren:

code:

SELECT
  product.id,
  product.name
FROM
  product
  LEFT JOIN product_has_category ON product.id = product_has_category.product_id
  LEFT JOIN category ON product_has_category.category_id = category.id
WHERE
  category.id NOT IN (1, 2, 3)
  OR category.id IS NULL
GROUP BY
  product.id,
  product.name

Als ik hetzelfde wil doen bij een AND filter door gebruik te maken van meerdere joins (subquery in MySQL is trager) wordt dit echter enorm traag bij meerdere categorieen omdat er veel meer rijen verwerkt moeten worden.

code:

SELECT
  product.id,
  product.name
FROM
  product
  LEFT JOIN product_has_category phc1 ON product.id = phc1.product_id
  LEFT JOIN product_has_category phc2 ON product.id = phc2.product_id
  LEFT JOIN product_has_category phc3 ON product.id = phc3.product_id
  LEFT JOIN product_has_category phc_null ON product.id = phc_null.product_id
WHERE
  (phc1.category_id <> 1
  AND phc2.category_id <> 3
  AND phc3.category_id <> 2)
  OR phc_null.category_id IS NULL
GROUP BY
  product.id,
  product.name

Hoe kan ik dit efficienter doen?

[ Voor 17% gewijzigd door gnoe93 op 25-10-2016 22:51 ]

[Laurens-R]

gnoe93 schreef op dinsdag 25 oktober 2016 @ 17:23:
Een tijdje geleden vroeg ik me af hoe ik een AND/OR filter kon implementeren in SQL: https://gathering.tweaker...message/48819529#48819529

Nu zou ik ook de functionaliteit willen voorzien om deze om te draaien.

Stel bijvoorbeeld met de tabellen product, category en product_has_category waarbij een product geen of meerdere categorieen kan hebben.

De OR filter lijkt me eenvoudig te implementeren:

code:

SELECT
  *
FROM
  product
  LEFT JOIN product_has_category ON product.id = product_has_category.product_id
  LEFT JOIN category ON product_has_category.category_id = category.id
WHERE
  category.id NOT IN (1, 2, 3)
  OR category.id IS NULL

Als ik hetzelfde wil doen bij een AND filter door gebruik te maken van meerdere joins (subquery in MySQL is trager) wordt dit echter enorm traag bij meerdere categorieen omdat er veel meer rijen verwerkt moeten worden.

code:

FROM
  product

  LEFT JOIN product_has_category ON product.id = product_has_category.product_id

  LEFT JOIN category category1 ON product_has_category.category_id = category1.id
  LEFT JOIN category category2 ON product_has_category.category_id = category2.id
  LEFT JOIN category category3 ON product_has_category.category_id = category3.id

WHERE
  category1.id <> 1
  AND category2.id <> 2
  AND category3.id <> 3
  OR product_has_category.category_id IS NULL

Hoe kan ik dit efficienter doen?

Begin maar eens met het specifiek vermelden van je velden in je SQL query, als is het maar vanwege de duidelijkheid van je query. (SELECT * is zo evil) Verder is deze query helemaal niet spannend vanuit een performance perspectief, dus leg 'enorm traag' eens uit? Ben je toevallig miljoenen rijen aan het ophalen? en over hoeveel columns hebben we het? Heb je indexes gezet? Heb je het execution plan al eens bekeken? Hoeveel ms execution hebben we het over bij hoeveel rijen?

[ Voor 3% gewijzigd door Laurens-R op 25-10-2016 17:57 ]

[gnoe93]

Heb even mijn voorbeeld vervolledigd (inclusief group by).

De product tabel bevat rond de 10000 records, terwijl er 10 categorieen zijn.
Op alle foreign keys zit een index.

Uit het execution plan blijkt dat de indexes gebruikt worden behalve bij product?

code:

id  select_type table       type    possible_keys                            
1   SIMPLE      product,    ALL     NULL                                     
1   SIMPLE      phc1        ref     PRIMARY, fk_product_has_category_product1_idx
1   SIMPLE      phc2        ref     PRIMARY, fk_product_has_category_product1_idx
1   SIMPLE      phc3        ref     PRIMARY, fk_product_has_category_product1_idx
1   SIMPLE      phc_null    ref     PRIMARY, fk_product_has_category_product1_idx

key       key_len   ref            rows    filtered    Extra
NULL      NULL      NULL           8831    100.00      Using temporary; Using filesort
PRIMARY   4         db.product.id  1       100.00      Using index
PRIMARY   4         db.product.id  1       100.00      Using index
PRIMARY   4         db.product.id  1       100.00      Using index
PRIMARY   4         db.product.id  1       100.00      Using where; Using index

Bij 3 categorieen zoals in het voorbeeld duurt het uitvoeren een 600ms, maar bij 4 categorieen duurt het 4 seconden en bij 5 zelfs 40. Boven de 5 blijkt er maar geen eind aan te komen.

[ Voor 9% gewijzigd door gnoe93 op 25-10-2016 22:59 ]

[NMe]

Die temporary/filesort op duizenden rows is natuurlijk aardig funest.

Eén keer joinen tussen product en category, de category-count meenemen, WHERE veld_dat_je_voorwaarde_bevat IN (waardes waarop je zoekt) GROUP BY op het product, HAVING COUNT(category.id) = <aantal voorwaarden waarop je zoekt). Feitelijk dus je OR-query zonder de null-check en met in plaats daarvan het controleren van het aantal gevonden resultaten.

[ Voor 20% gewijzigd door NMe op 25-10-2016 23:41 ]

[gnoe93]

NMe schreef op dinsdag 25 oktober 2016 @ 23:01:
Die temporary/filesort op duizenden rows is natuurlijk aardig funest.

Eén keer joinen tussen product en category, de category-count meenemen, WHERE veld_dat_je_voorwaarde_bevat IN (waardes waarop je zoekt) GROUP BY op het product, HAVING COUNT(category.id) = <aantal voorwaarden waarop je zoekt). Feitelijk dus je OR-query zonder de null-check en met in plaats daarvan het controleren van het aantal gevonden resultaten.

Bedankt voor je hulp, maar wat ik eigenlijk wil is dat enkel de producten met bijvoorbeeld beiden categorie 1 en 2 niet in het resultaat worden weergegeven.

Stel dat er 10000 producten zijn, en 50 van deze producten hebben beiden categorie 1 en 2. Met bovenstaande query worden ook alle producten die ofwel categorie 1 of 2 uitgesloten. Wat ik dus eigenlijk wil is dat er 9950 producten weergegeven worden.

[GlowMouse]

Zorg dat de producttabel een index bevat op de gezamelijke velden (id,name), en zorg dat die index wordt gebruikt. Waarschijnlijk gaat dat vanzelf, maar gebruik desnoods FORCE INDEX. Als er weinig rijen gefilterd kunnen worden, is dat het meest efficiënt. De rijen worden dan netjes gesorteerd opgehaald voor de GROUP BY (DISTINCT is syntactisch netter al is de output hetzelfde).

[ Voor 34% gewijzigd door GlowMouse op 26-10-2016 03:44 ]

[NMe]

gnoe93 schreef op woensdag 26 oktober 2016 @ 01:58:
[...]

Bedankt voor je hulp, maar wat ik eigenlijk wil is dat enkel de producten met bijvoorbeeld beiden categorie 1 en 2 niet in het resultaat worden weergegeven.

Stel dat er 10000 producten zijn, en 50 van deze producten hebben beiden categorie 1 en 2. Met bovenstaande query worden ook alle producten die ofwel categorie 1 of 2 uitgesloten. Wat ik dus eigenlijk wil is dat er 9950 producten weergegeven worden.

In dat geval werkt de OR in je startpost toch ook niet? Als een product aan categoriën 1, 2, 3 en 4 hangt en je voert die query uit, dan krijg je toch gewoon het product terug omdat die weliswaar in categoriën 1-3 zit maar ook in 4. Dat lijkt me niet wat je wil? Wat je feitelijk wil is éérst selecteren welke producten in een verborgen categorie zitten, en daarna alles selecteren uit de producttabel dat niet al in die lijst zit. Dat zou je met een subquery kunnen doen, voor allebei je problemen.

[GlowMouse]

Een subquery met bv. NOT EXISTS lijkt me de aangewezen weg.

[gnoe93]

NMe schreef op woensdag 26 oktober 2016 @ 11:12:
[...]

In dat geval werkt de OR in je startpost toch ook niet? Als een product aan categoriën 1, 2, 3 en 4 hangt en je voert die query uit, dan krijg je toch gewoon het product terug omdat die weliswaar in categoriën 1-3 zit maar ook in 4. Dat lijkt me niet wat je wil? Wat je feitelijk wil is éérst selecteren welke producten in een verborgen categorie zitten, en daarna alles selecteren uit de producttabel dat niet al in die lijst zit. Dat zou je met een subquery kunnen doen, voor allebei je problemen.

Het OR voorbeeld had ik er gewoon bijgezet vanwege mijn vorige topic. Wat ik dus eigenlijk wil, zijn 2 filteringsmechanismen, zijnde "wel/niet" en "of/en" zoals hier bij pricewatch bijvoorbeeld. Dus samengevat:

"niet" + "of" = alle resultaten behalve de geselecteerde categorieen apart.
"niet" + "en" = alle resultaten behalve de geselecteerde categorieen gecombineerd

De OR (niet + of) query uit mijn voorbeeld werkt dus naar behoren. Enkel bij AND (niet + en) wist ik niet goed deze efficient te implementeren.

[GlowMouse]

En werkt het met de voorgestelde index?

[gnoe93]

GlowMouse schreef op woensdag 26 oktober 2016 @ 22:12:
En werkt het met de voorgestelde index?

Met de index gaat het stukken sneller, maar eigenlijk haal ik alles op van de product tabel (had geen zin om alle kolommen te vermelden), dus dit lijkt me niet echt een oplossing.

Bedoel je met NOT EXISTS dit?

code:

SELECT
    SQL_NO_CACHE
    product.id,
    product.name
FROM
    product
WHERE
    NOT EXISTS (
        SELECT
            1
        FROM
            product product_inner
            INNER JOIN product_has_category phc1 ON product_inner.id = phc1.product_id
            INNER JOIN product_has_category phc2 ON product_inner.id = phc2.product_id
        WHERE
            product_inner.id = product.id
                AND phc1.category_id = 2
                AND phc2.category_id = 7
    )

Ik heb 8681 producten in totaal, waarvan 35 met beiden categorieen 2 en 7. Het resultaat hiervan geeft 8646 rijen. Werkt naar behoren dus.

Wel nog een vraagje over mijn eerste post: waarom geeft de eerder vermelde query:

code:

SELECT
  SQL_NO_CACHE
  product.id,
  product.name
FROM
  product
  LEFT JOIN product_has_category phc1 ON product.id = phc1.product_id
  LEFT JOIN product_has_category phc2 ON product.id = phc2.product_id
  LEFT JOIN product_has_category phc_null ON product.id = phc_null.product_id
WHERE
  (phc1.category_id <> 2
  AND phc2.category_id <> 7)
  OR phc_null.category_id IS NULL
GROUP BY
  product.id,
  product.name

Niet hetzelfde resultaat als de vorige query? Ik krijg 7156 rijen terug, waarbij alle producten met ofwel categorie 2 of 7 uit het resultaat zijn, ipv enkel de producten met beiden (8681 - 35 = 8646).

[ Voor 35% gewijzigd door gnoe93 op 27-10-2016 23:57 ]

[GlowMouse]

gnoe93 schreef op donderdag 27 oktober 2016 @ 23:52:
[...]


Met de index gaat het stukken sneller, maar eigenlijk haal ik alles op van de product tabel (had geen zin om alle kolommen te vermelden), dus dit lijkt me niet echt een oplossing.

Waarom niet?

Niet hetzelfde resultaat als de vorige query? Ik krijg 7156 rijen terug, waarbij alle producten met ofwel categorie 2 of 7 uit het resultaat zijn, ipv enkel de producten met beiden (8681 - 35 = 8646).

Omdat de rijen aan de WHERE voldoen. Zet phc1.category_id en phc2.category_id maar in de SELECT clause.

[NMe]

gnoe93 schreef op donderdag 27 oktober 2016 @ 23:52:
Niet hetzelfde resultaat als de vorige query? Ik krijg 7156 rijen terug, waarbij alle producten met ofwel categorie 2 of 7 uit het resultaat zijn, ipv enkel de producten met beiden (8681 - 35 = 8646).

Hint: wat nou als phc1.category_id 7 is en phc2.category_id 2?

[gnoe93]

OK, nu begrijp ik het

Door 3x te joinen krijg je uiteindelijk join 1 rows * join 2 rows * join 3 rows terug.
Dus stel dat een product 1 categorie heeft, zal dit in totaal 1 rij geven, maar als een product 2 categorieen heeft (2 en 7) zal dit het volgende resultaat (2^3) geven:

code:

2  2  2
2  2  7
2  7  2
2  7  7
7  2  2
7  2  7
7  7  2
7  7  7

Bij een gewone equals maakt dit niet uit, zolang er maar 1 tussen zit die aan de voorwaarde voldoet, maar bij not equals <> komen andere combinaties niet in dezelfde volgorde er nog door.

GlowMouse schreef op vrijdag 28 oktober 2016 @ 19:04:
[...]
Waarom niet?

Moet ik dan niet een index op alle kolommen zetten zodat group by ze kan gebruiken?

[GlowMouse]

gnoe93 schreef op vrijdag 28 oktober 2016 @ 20:25:
Moet ik dan niet een index op alle kolommen zetten zodat group by ze kan gebruiken?

Alleen de kolommen uit GROUP BY hoeven in de index. Dat zijn immers de kolommen waarop MySQL zal moeten sorteren om de GROUP BY uit te voeren.

[gnoe93]

GlowMouse schreef op zaterdag 29 oktober 2016 @ 00:52:
[...]

Alleen de kolommen uit GROUP BY hoeven in de index. Dat zijn immers de kolommen waarop MySQL zal moeten sorteren om de GROUP BY uit te voeren.

Klopt, maar als ik alle kolommen uit de product tabel selecteer, moet ik deze ook onderbrengen in GROUP BY, tenzij het aggregatiekolommen zijn. Ik weet dat dit in MySQL toegelaten is en dat er willekeurige waarden genomen worden, maar dit is in strijd met de SQL standaard.

[ Voor 15% gewijzigd door gnoe93 op 29-10-2016 04:32 ]

[GlowMouse]

Dat hoeft niet. In dit geval is het handiger om de GROUP BY klein te houden omdat je anders gigantische indices nodig hebt zoals je al opmerkte.
https://dev.mysql.com/doc...en/group-by-handling.html

SQL99 and later permits such nonaggregates per optional feature T301 if they are functionally dependent on GROUP BY columns: If such a relationship exists between name and custid, the query is legal. This would be the case, for example, were custid a primary key of customers.

en:
https://dev.mysql.com/doc...s.html#function_any-value

[gnoe93]

GlowMouse schreef op zaterdag 29 oktober 2016 @ 04:36:
Dat hoeft niet. In dit geval is het handiger om de GROUP BY klein te houden omdat je anders gigantische indices nodig hebt zoals je al opmerkte.
https://dev.mysql.com/doc...en/group-by-handling.html

[...]

en:
https://dev.mysql.com/doc...s.html#function_any-value

Ik heb mij altijd al laten wijsmaken dat dit een "MySQL kwaal" was. Goed dit te weten.