AllYouNeedIsBackend

Olen suuri tietokantojen ystävä. Halusin jopa tehdä oman DBMS:n, kun olin yliopistossa. Nyt työskentelen sekä RDBMS- että NoSQL-ratkaisujen parissa, ja olen erittäin innostunut siitä. Tiedäthän, että kultaista vasaraa ei ole olemassa, jokaiselle ongelmalle on oma ratkaisunsa. Vaihtoehtoisesti osajoukko ratkaisuja.

Blogikirjoitussarjassa The SQL I Love <3 käyn läpi joitakin SQL:llä ratkaistuja ongelmia, jotka olivat mielestäni erityisen mielenkiintoisia. Ratkaisuja testataan käyttäen taulukkoa, jossa on yli 100 miljoonaa tietuetta. Kaikissa esimerkeissä käytetään MySQL:ää, mutta ideat soveltuvat myös muihin relaationaalisiin tietovarastoihin, kuten PostgreSQL:ään, Oracleen ja SQL Serveriin.

Tässä luvussa keskitytään suuren taulukon tehokkaaseen skannaukseen käyttämällä sivutusta, jossa käytetään offset ensisijaista avainta. Tämä tunnetaan myös nimellä keyset pagination.

Background

Luvussa käytetään esimerkkinä seuraavaa tietokantarakennetta. Kanonisen esimerkin käyttäjistä pitäisi sopia mille tahansa toimialueelle.

CREATE TABLE `users` ( `user_id` int(11) unsigned NOT NULL AUTO_INCREMENT, `external_id` varchar(32) NOT NULL, `name` varchar(100) COLLATE utf8_unicode_ci NOT NULL, `metadata` text COLLATE utf8_unicode_ci, `date_created` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP, PRIMARY KEY (`user_id`), UNIQUE KEY `uf_uniq_external_id` (`external_id`), UNIQUE KEY `uf_uniq_name` (`name`), KEY `date_created` (`date_created`)) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

Muutamia huomioita rakenteesta:

• external_id sarakkeessa tallennetaan viittaus samaan käyttäjään toisessa järjestelmässä UUID-muodossa
• name edustaa Firstname Lastname
• metadata sarakkeessa on JSON-pläjäys, jossa on kaikenlaista jäsentymätöntä dataa

Taulukko on suhteellisen suuri, ja se sisältää noin 100 000 000 tietuetta. Aloitetaan oppimismatka.

Suuren taulukon skannaaminen

Ongelma: Sinun on käytävä taulukon läpi, poimittava jokainen tietue, muunnettava se sovelluksesi koodin sisällä ja lisättävä toiseen paikkaan. Keskitymme postauksessa ensimmäiseen vaiheeseen – taulukon skannaamiseen.

Ilmeinen ja väärä ratkaisu

SELECT user_id, external_id, name, metadata, date_createdFROM users;

Tapauksessani, jossa on 100 000 000 tietuetta, kysely ei koskaan valmistu. DBMS vain tappaa sen. Miksi? Luultavasti siksi, että se johti yritykseen ladata koko taulukko RAM-muistiin. Ennen tietojen palauttamista asiakkaalle. Toinen oletus – tietojen esilataaminen ennen lähettämistä vei liikaa aikaa ja kysely keskeytyi. Joka tapauksessa yrityksemme saada kaikki tietueet ajoissa epäonnistui. Meidän on löydettävä jokin muu ratkaisu.

Ratkaisu #2

Voidaan yrittää saada tiedot sivuilla. Koska tietueiden järjestystä taulukossa ei ole taattu fyysisellä tai loogisella tasolla – meidän on lajiteltava tietueet DBMS:n puolella ORDER BY-lausekkeella.

SELECT user_id, external_id, name, metadata, date_createdFROM usersORDER BY user_id ASCLIMIT 0, 10 000;10 000 rows in set (0.03 sec)

Sweet. Se toimi. Kysyimme ensimmäisen sivun 10 000 tietuetta, ja sen palauttaminen kesti vain 0.03 sekuntia. Miten se kuitenkin toimisi 5000. sivun kohdalla?

SELECT user_id, external_id, name, metadata, date_createdFROM usersORDER BY user_id ASCLIMIT 50 000 000, 10 000; --- 5 000th page * 10 000 page size10 000 rows in set (40.81 sec)

Tämä on tosiaan hyvin hidasta. Katsotaanpa kuinka paljon aikaa tarvitaan viimeisimmän sivun tietojen saamiseen.

SELECT user_id, external_id, name, metadata, date_createdFROM usersORDER BY user_id ASCLIMIT 99 990 000, 10 000; --- 9999th page * 10 000 page size10 000 rows in set (1 min 20.61 sec)

Tämä on mieletöntä. Voi kuitenkin olla OK ratkaisuille, jotka toimivat taustalla. Vielä yksi lähestymistavan piilevä ongelma voi paljastua, jos yrität poistaa tietueen taulukosta kesken skannauksen. Oletetaan, että olet saanut valmiiksi 10. sivun (100 000 tietuetta on jo käyty läpi) ja aiot skannata tietueet välillä 100 001-110 000. Mutta tietueet 99 998 ja 99 999 poistetaan ennen seuraavaa SELECT suoritusta. Tällöin seuraava kysely palauttaa odottamattoman tuloksen:

 SELECT user_id, external_id, name, metadata, date_created FROM users ORDER BY user_id ASC LIMIT 100 000, 10 000; N, id, ... 1, 100 003, ... 2, 100 004, ...

Kuten näet, kysely ohitti tietueet, joiden tunnukset ovat 100 001 ja 100 002. Sovelluksen koodi ei käsittele niitä lähestymistavalla, koska kahden poisto-operaation jälkeen ne esiintyvät 100 000 ensimmäisen tietueen joukossa. Siksi menetelmä on epäluotettava, jos tietokokonaisuus on muuttuva.

Ratkaisu #3 – viimeinen tälle päivälle

Lähestymistapa on hyvin samankaltainen kuin edellinen, koska siinä käytetään edelleen sivutusta, mutta nyt sen sijaan, että luottaisimme skannattujen tietueiden lukumäärään, käytämme viimeisimmän käydyn tietueen user_id:aa offset.

Yksinkertaistettu algoritmi:

1. Saamme PAGE_SIZE tietueiden määrän taulukosta. Offsetin alkuarvo on 0.
2. Käytetään erän user_id suurinta palautettua arvoa seuraavan sivun offsetina.
3. Hankitaan seuraava erä niistä tietueista, joiden user_id arvo on suurempi kuin nykyinen offset.

Kysely toiminnassa 5 000. sivulle, kukin sivu sisältää tietoja 10 000 käyttäjästä:

SELECT user_id, external_id, name, metadata, date_createdFROM usersWHERE user_id > 51 234 123 --- value of user_id for 50 000 000th recordORDER BY user_id ASCLIMIT 10 000;10 000 rows in set (0.03 sec)

Huomaa, että user_id:n arvot eivät ole peräkkäisiä ja että niissä voi olla aukkoja, kuten esimerkiksi 25 348 on heti 25 345:n jälkeen. Ratkaisu toimii myös, jos tulevien sivujen tietueet poistetaan – tällöinkään kysely ei ohita tietueita. Suloista, eikö?

Suorituskyvyn selittäminen

Jatko-opiskelua varten suosittelen tutkimaan EXPLAIN EXTENDED:n tuloksia jokaiselle kyselyn versiolle, jotta 50 000 000:n jälkeen saadaan seuraavat 10 000 tietuetta.

Keskitytään 2. ja 3. ratkaisun suoritussuunnitelmien keskeisimpään eroon, koska 1. ratkaisu ei ole käytännössä käyttökelpoinen suurille taulukoille.

• Join type: index vs range. Ensimmäinen tarkoittaa, että koko indeksipuu skannataan tietueiden löytämiseksi. range-tyyppi kertoo, että indeksiä käytetään vain yhteensopivien rivien löytämiseen tietyllä alueella. range-tyyppi on siis nopeampi kuin index.
• Mahdolliset avaimet: NULL vs PRIMARY. Sarakkeessa näkyvät avaimet, joita MySQL voi käyttää. BTW, katsomalla avaimet saraketta, voimme nähdä, että lopulta PRIMARY avainta käytetään molemmissa kyselyissä.
• Rows: 50 010 000 vs 50 000 000. Arvo näyttää analysoitujen tietueiden määrän ennen tuloksen palauttamista. Toisen kyselyn osalta arvo riippuu siitä, kuinka syvällä vieritys on. Jos esimerkiksi yritämme saada seuraavat 10 000 tietuetta 9999. sivun jälkeen, tutkitaan 99 990 000 tietuetta. Sitä vastoin 3. kyselyllä on vakioarvo; sillä ei ole väliä, lataammeko tiedot ensimmäiseltä tai viimeiseltä sivulta. Se on aina puolet taulukon koosta.
• Suodatettu: 200.00 vs 100.00. Sarakkeessa ilmoitetaan arvioitu prosenttiosuus taulukosta, joka on suodatettava ennen käsittelyä. Suurempi arvo on parempi. Arvo 100.00 tarkoittaa, että kysely käy läpi koko taulukon. Toisen kyselyn arvo ei ole vakio, vaan se riippuu sivunumerosta: jos kysytään 1. sivua, suodatetun sarakkeen arvo olisi 1000000.00. Aivan viimeisellä sivulla se olisi 100.00.
• Extra: NULL vs. Using where. Antaa lisätietoja siitä, miten MySQL ratkaisee kyselyn. Käyttö WHERE on PRIMARY -avaimella nopeuttaa kyselyn suorittamista.

Epäilen, että join-tyyppi on kyselyn parametri, joka vaikutti eniten suorituskykyyn, jotta 3. kysely olisi nopeampi. Toinen tärkeä asia on se, että 2. kysely on erittäin riippuvainen selattavien sivujen määrästä. Syvempi sivuttaminen on siinä tapauksessa hitaampaa.

Lisäohjeita EXPLAIN-komennon tulostuksen ymmärtämisestä löytyy RDBMS:n virallisesta dokumentaatiosta.

Yhteenveto

Blogipostauksen pääasiallinen aihe liittyi 100 000 000 tietuetta sisältävän suuren taulukon skannaamiseen offset:llä, jossa on primääriavain (keyset pagination). Kaiken kaikkiaan tarkasteltiin 3 erilaista lähestymistapaa ja testattiin niitä vastaavalla tietokokonaisuudella. Suosittelen vain yhtä niistä, jos haluat skannata suuren muuttuvan taulukon.

Lisäksi tarkistimme EXPLAIN EXTENDED-komennon käyttöä MySQL-kyselyjen suoritussuunnitelman analysoimiseksi. Olen varma, että muilla RDBMS-järjestelmillä on analogisia toimintoja.

Seuraavassa luvussa kiinnitämme huomiota tietojen aggregointiin ja tallennuksen optimointiin. Pysy kuulolla!

Millä menetelmällä skannaat suuria taulukoita?

Muistatko mitään muuta tarkoitusta käyttää avainsarjojen sivutusta kuten ratkaisussa #3?