středa 2. června 2010

Jak se optimalizuje SQL

Už na SW2 byl (a pořád jěště je) takový malý problém... Problém, který se asi ani nemá šanci projevit, ale v rovině teoretické přesto existuje...

Equilibrium.
Přesněji řečeno, zjišťování jestli už uživatel při zpovědi hlasoval nebo ne.
Tento údaj totiž musí být zaznamenán pro každého uživatele, což znamená že je na to potřeba samostatnou tabulku... Už nevím jak je to udělaný v SW2, myslím že tak, že při načtení Equilibria se do $_SESSION uloží záznamy o všech hlasováních uživatele...

A to je právě ten problém - pokud je jich kolem řekněme... stovky, tak je jěště všechno relativně v pořádku... Ale pokud by jich bylo... řekněme... tisíc, a na SW by bylo přihlásených v jednom momentě (a Equilibrium si čtoucích) 10 lidí, už je to 10000 záznamů, které si musí server držet v paměti... A tak dále, s každým zahlasovaným equi a každým připojeným uživatelem toto číslo roste, nemluvě o tom že tato informace se musí každému uživateli dopravit do počítače pokaždé když otevře seznam equi...

V SW3 jsem to chtěl udělat korektněji - narvat všechno do jedné query, pokud možno... aby vytáhla zpovědi a k nim přidružené informace o tom jestli momentálně přihlášený uživatel už ve zpovědi hlasoval, nebo ne.

Problém je, že tahle query byla monstrózní už než jsem se do ní začal pokoušet zakomponovat tenhle kousek... Musela vybrat zpovědi které byly přístupné dotyčnému uživateli (pokud nebyl přihlášen tak ty viditelné všem, pokud byl přihlášen tak ty viditelné všem plus ty jen pro přátele, ale od těch kdo ho mají v přátelích, plus všechny vlastní), a pak k nim jěště z další tabulky připojit informace o uživateli který zpověď přidal.
(Jak sami vidíte, v trochu jiném pořadí, ale to je detail...)

Vypadala takhle:
SELECT swEquilibrium.*, swUsers.Status, swFriends.Friend
FROM swEquilibrium
LEFT JOIN swUsers ON swEquilibrium.Owner = swUsers.Username
LEFT JOIN swFriends ON swEquilibrium.Owner = swFriends.Owner
WHERE (Friend = '{$_SESSION["Username"]}' AND VisibleTo = 2)
OR (VisibleTo <= " . Word2Privileges($_SESSION["Privileges"]) . ")
OR (swEquilibrium.Owner = '{$_SESSION["Username"]}')
GROUP BY swEquilibrium.ID
ORDER BY DateAdded DESC
LIMIT 15 OFFSET {$p};

({$_SESSION["Username"]} obsahuje vždy jméno momentálně přihlášeného uživatele, nebo prázdný řetězec, pokud uživatel není přihlášen, a {$p} je stránkovací proměnná, to je nepodstatný detail.)

Myslím že tohle byla druhá nejdelší query kterou jsem kdy vyplodil... První byla tuším na výběr deníkového záznamu na titulku, nebo equi na titulku, nejsem si jistý...
To co následovalo, se ale určitě s přehledem dostalo na první místo.

Pokus č.1.:
SELECT swEquilibrium.*, swUsers.Status, swFriends.Friend
FROM swEquilibrium
LEFT JOIN swUsers ON swEquilibrium.Owner = swUsers.Username
LEFT JOIN swFriends ON swEquilibrium.Owner = swFriends.Owner
LEFT JOIN swVotes ON swEquilibrium.ID = swVotes.ID
WHERE (Friend = '{$_SESSION["Username"]}' AND VisibleTo = 2)
OR (VisibleTo <= " . Word2Privileges($_SESSION["Privileges"]) . ")
OR (swEquilibrium.Owner = '{$_SESSION["Username"]}')
AND swVotes.Owner = '{$_SESSION["Username"]}'
GROUP BY swEquilibrium.ID
ORDER BY DateAdded DESC
LIMIT 15 OFFSET {$p};

...když jsem tohle slepil dohromady, a pustil to, a s překvapením se díval že to neháže žádný error, a pak se z toho překvapení vzpamatoval, tak jsem zjistil, že ta query jěště pořád běží...
A běžela něco kolem sedmi vteřin... Eh... Jak bych vám to... No, sedm vteřin je na SQL query SAKRA hodně, hlavně když pracujete s tak malými (v poměru k tomu na co je SQL stavěné) množstvími dat jako já...

No jo, šest a půl vteřiny, co to má sakra být? Zapoměl jsem do tabulky swVotes nahodit indexy? (Kontrola) ne, nezapoměl, primární tam není, ale ten tam ani být nemá, každý column má sice jiné kódování (databáze je utf8, sloupce této tabulky byly některé v latin2), ale to by měl být detail, a krom toho když jsem to opravil a spustil znovu, žádná velká změna...

A pak mi to došlo...
JOIN pracuje tak, že spojí všechny záznamy jedné tabulky se všemi záznamy druhé tabulky... A až pak probíhá WHERE, což je vlastně podmínka která nevyhovující odfiltruje...

Takže když máte tabulku A s 10ti záznamy, a tabulku B taky s deseti, a uděláte na nich JOIN, získáte tabulku kde bude každý záznam z A uveden desetkrát, pokaždé spojen s jiným z deseti záznamů z B... Což znamená že výsledkem bude tabulka o 100 záznamech, ze které se pak většina zahodí, protože nevyhovuje podmínce...

...a když děláte 3 joiny za sebou, udělá se třikrát to samé, takže spojením tabulek A, B a C, každé o 10ti záznamech získáte... tadá, tabulku o 1000(!) záznamech... Ze kterých se pak zase většina kvůli podmínce zahodí...

Je třeba si ale uvědomit, že každé spojení dvou řádků z tabulky, nebo kontrola řádku jestli vyhovuje podmínce, vás stojí něco času... Ono jsou to tisíciny vteřiny, někdy možná ani to ne, ale když dvě tisíciny vteřiny vynásobíte tisíci...

Zpátky ke query. Takže fungovala, ale fungovala tak, že udělala maximálně monstrózní tabulku všech možností, a pak ji celou prošla a zahazovala všechno co nevyhovovalo podmínce...

Což znamenalo:
168 (equilibrium) x 169 (users) x 212 (friends) x 6933 (votes) = 41 730 448 032

Ehm... to číslo jsem si musel pomalu pročítat odzadu aby mi došlo jak je obrovský...
Skoro 42. 42 MILIARD řádků...

Ze kterých se pak zahodí všechny kromě PATNÁCTI (což je délka jedné strany ve výpisu Equilibria)... Efektivita příkazu... 15 / 41 730 448 032 * 100 = 0,000000035945%, a myslím že to je tak neskutečně giganticky obrovsky titěrná hodnota, že mi asi můžete gratulovat... :-D. V praxi to znamená, že 99,999999964055% z těch víc jak šesti vteřin se vyplýtvá na spacování dat, které se stejně zahodí...

Tak jsem si řekl, že tohle tedy ne, musí být i jiná cesta... A po pár pokusech-omylech jsem se dopracoval k tomuto:

SELECT *
FROM (SELECT swEquilibrium.*, swUsers.Status, swFriends.Friend
FROM swEquilibrium
LEFT JOIN swUsers ON swEquilibrium.Owner = swUsers.Username
LEFT JOIN swFriends ON swEquilibrium.Owner = swFriends.Owner
WHERE (Friend = '{$_SESSION["Username"]}' AND VisibleTo = 2)
OR (VisibleTo <= " . Word2Privileges($_SESSION["Privileges"]) . ")
OR (swEquilibrium.Owner = '{$_SESSION["Username"]}')
GROUP BY swEquilibrium.ID
ORDER BY DateAdded DESC
LIMIT 15 OFFSET {$p}) AS tmpEqui
LEFT JOIN ((SELECT swVotes.Owner AS VoteOwner, swVotes.ID
FROM swVotes
WHERE swVotes.Owner = '{$_SESSION["Username"]}' AND Cathegory = 'Equilibrium') AS tmpVotes)
ON tmpEqui.ID = tmpVotes.ID;

Což znamená, že nejdřív udělám to, co jsem udělal původně, pak z toho udělám regulerní virtuální tabulku (nevím jestli se tomu tak říká, to je můj pracovní název, jde o to že jakmile query skončí, ta tabulka přestane existovat, ale do té doby se chová jako kdyby byla pevně zapsaná na disku, což není, protože je slepencem několika tabulek), kde se vyskytují jen ty záznamy které chci, a k ní pak připojím informace o hlasováních.
(Ale taky už jenom o těch hlasech, které mají souvislost s přihlášeným uživatelem a momentálně zpracovávanou zpovědí.)

Rozepsáno do bodů:
1. pospojuj všechny tabulky a informace které budeme potřebovat
168 (equilibrium) x 169 (users) x 212 (friends) = 6 019 104 řádků.

2. Projdi všechny řádky a vyřaď zpovědi které nemůže vidět
6 019 104 -> XY řádků, nemůžeme přesně vědět kolik, ale jedná se o všechny záznamy od začátku SW, bude jich obvykle kolem 80ti, a čím starší stránka bude, tím jich bude víc, ale pořád to bude kolem 0,000002%, nebo tak nějak, prostě mizivé množství, téměř zanedbatelné, pro naše účely počítejme s těmi 80.

3. Spoj s tabulkou hlasování
80 x 1 (votes na které je podmínka, takže ke každému equi vrátí jen jeden záznam, v takovém případě se tabulka "nemnoží", jen se záznamy správně seřadí) = 80

4. Vyber jen ty záznamy, které odpovídají druhé podmínce (tzn. hlasující = momentálně přihlášený, kategorie = Equilibrium, a ID zpovědi = ID ke kterému patři hlas.
80 -> 15;

Takže v tomto případě musí SQL zpracovat 6 019 104 + 80 (skládání v bodu 3) + 80 (filtrování v bodu 4) = 6019264 řádků...

Což je o 99,9999422% až 99,9999822% efektivnější, než ta první query...
A taky je to znát, proběhne přibližně za 8 setin vteřiny...

(Disclaimer: Ty čísla nejsou úplně přesná, zaprvý nevím jestli mám join a filtrování skutečně počítat jako dva průchody tabulkou, hlavně když probíhají hned po sobě, kde by je teoreticky MySQL mohlo bez obav okamžitě zahodit, pokud nevyhovují, a zadruhý jsou to jen moje odhady toho, jak MySQL uvnitř funguje... Ale ten rozdíl je naprosto jasný i kdybych měl hned ve výpočtech 50%tní chybu.)

Jo, a tenhle blog venujem Tomášovi Abaffymu, pretože sa ma pár mesiacov dozadu spýtal čo viem o optimalizovaní SQL/databázy, na čo ma napadli len správne zaindexované tabuľky a viac som si nevedel príliš predstaviť čo by chcel optimalizovať, tak som mu napísal "nie príliš veľa".

Tak teraz, neviem síce ako veľa toho o optimalizácií SQL viem z globálneho pohľadu, ale určite viac ako predtým... :-)