Viimeisin päivitetty 8. joulukuuta 2019
Sattumanvaraisten rivien palauttaminen satunnaiseen järjestykseen relaatiotietokannasta on hyvin vaikea ongelma. Tässä artikkelissa näemme antipatternin, keskustelemme siitä, miksi tämä ongelma on niin vaikea, ja tarkastelemme joitakin epätäydellisiä ratkaisuja.
UPDATE: Jotkut DBMS:t tukevat TABLESAMPLE. En maininnut sitä, koska tunsin tähän päivään asti vain SQL Serverin toteutuksen, enkä pidä sitä hyvänä satunnaisrivien poimimiseen (selitän miksi). Mutta Daniël van Eedenin Facebookissa esittämän kysymyksen jälkeen tein tutkimusta ja huomasin, että PostgreSQL-toteutus voisi olla paljon sopivampi. Luen siitä lisää ja kokeilen sitä, ja sitten kirjoitan luultavasti toisen artikkelin siitä. Joka tapauksessa MySQL ja MariaDB eivät tue TABLESAMPLE.
Väärällä tavalla: ORDER BY RAND()
Monet kehittäjät luulevat voivansa tehdä sen tällä tavalla:
SELECT some_columns FROM some_table ORDER BY RAND() LIMIT 10;Tämä on ainoa kysely, joka tekee juuri sen, mitä odotetaan. Jos RAND()-funktio on luotettavasti satunnainen, se palauttaa satunnaisen joukon rivejä, joissa jokaisella rivillä on samat mahdollisuudet tulla palautetuksi.
Ongelma on siinä, miten se toimii konepellin alla. Jotta satunnaisarvot voidaan järjestää, ne on ensin luotava. Luodakseen satunnaisarvon jokaiselle taulukon riville DBMS:n on luettava jokainen rivi. DBMS tekee siis kaksivaiheisen operaation:
- Kopioi rivit plus satunnaisarvo väliaikaiseen taulukkoon, joka on toivottavasti muistissa;
- järjestä rivit väliaikaiseen taulukkoon.
Huomaa tämä yksityiskohta: toivottavasti muistissa. DBMS:stä riippuen voi olla syitä, miksi taulukko on luotava levylle. Tyypillisesti näin tapahtuu, jos taulukko on liian suuri. Vanhat MySQL-versiot luovat myös väliaikaisia taulukoita levylle, jos ne sisältävät TEXT tai BLOB sarakkeita.
On sanomattakin selvää, että jos taulukko on suuri, tämä on hidas operaatio, joka kuluttaa paljon resursseja.
Miksi relaatiotietokantajärjestelmät eivät tarjoa sisäänrakennettua tapaa palauttaa satunnaisia rivejä?
Relaatiotietokannat on rakennettu matematiikan haaran ympärille, jota kutsutaan nimellä relaatioalgebra. Se perustuu logiikkaan, koska se käsittelee tosia/vääriä predikaatteja; ans samanlainen kuin joukko-oppi, vaikka relaatio on jotain monimutkaisempaa kuin joukko, ja edes sen näkeminen taulukkona ei ole matemaattisesti oikein. Tämä artikkeli on hieno esimerkki siitä, mitä tarkoitan, mutta on olemassa monimutkaisempiakin argumentteja.
Huolimatta siitä, että SQL ei ole relaatiomallin tarkka toteutus, sen algebraa käytetään vertailukohtana. Kuten kaikilla matematiikan aloilla, sillä on hyvin määritelty joukko operaatioita. Satunnaisten tuplien hakeminen relaatiosta ei todellakaan kuulu niihin.
Tämä vastaus kuulostaa hieman liian teoreettiselta, eikö? ORDER BY ja taulukot, joissa ei ole ensisijaista avainta, rikkovat myös relaatioalgebran sääntöjä, mutta SQL tukee niitä.
Tietokannoille nopeus on kuitenkin elintärkeää. Relationaaliset tietokantajärjestelmät on suunniteltu suorittamaan relaatio-operaatiot hyvin nopeasti. On selvää, että tietorakenne, joka on suunniteltu optimoimaan tiettyjä operaatioita, ei ole optimoitu muita operaatioita varten. Relationaalisia tietokantajärjestelmiä ei siis ole optimoitu satunnaishakuja varten.
Pitäisi olla selvää, että rivien läpikäyminen ja joidenkin rivien valitseminen satunnaisesti olisi hidasta. Teoriassa satunnaisen rivin lukeminen indeksin avulla olisi yhtä nopeaa kuin rivin etsiminen ensisijaisen avaimen arvon perusteella. Mutta silloin eri riveillä olisi erilaiset mahdollisuudet tulla valituksi.
Yllä oleva kuva on Jeremy Colen GitHub-arkistosta innodb_diagrams. Minun pitäisi ennemmin tai myöhemmin kirjoittaa hänen projekteistaan InnoDB:n tietorakenteiden analysoimiseksi.
Tärkeää tässä on se, että indeksi on puu, jonka solmut ovat muistisivuja. Lehtisolmut sisältävät varsinaista dataa; ylemmät tasot sisältävät vain tietoa, jota tarvitaan lyhimmän polun valitsemiseen haluttuun lehtisolmuun. Yksityiskohdat eivät ole tässä yhteydessä tärkeitä.
Tietokantajärjestelmä voisi teoriassa valita satunnaisen sivun tekemällä sarjan satunnaisia päätöksiä: menenkö vasemmalle vai oikealle? Mutta silloin lehtisivut sisältävät vaihtelevan määrän rivejä. Ne voivat olla jopa tyhjiä. Joten eri riveillä olisi erilaiset mahdollisuudet tulla valituksi.
Tulos on selvästi DBMS:n suunniteltujen käyttötapausten ulkopuolella; ja se voi olla hidas tai väärä riippuen siitä, käytetäänkö indeksiä vai ei. DBMS:t ovat perustellusti päättäneet olla toteuttamatta tätä ominaisuutta.
Joitakin ratkaisuja
Täydellisiä ratkaisuja ei ole. On ratkaisuja, jotka voivat olla hyväksyttäviä, mutta joissa on haittoja. Meidän on valittava yksi tapauskohtaisesti.
Valitaan satunnaisesti alueelta
Tämä ratkaisu soveltuu taulukoihin, joissa on autoinkrementaalinen ensisijainen avain. Se on helpoin toteuttaa, mutta ”pirstaleinen” pääavain aiheuttaa ongelmia.
Se koostuu minimi-id:n ja maksimi-id:n tarkistamisesta ja satunnaisluvun luomisesta kyseiseltä alueelta:
Ei sillä, että kyselyt, joissa on MIN() ja MAX() millä tahansa indeksillä ilman muita lausekkeita, ovat hyvin nopeita.
Tuloksena on todella satunnainen rivi. Jos haluamme valita useamman kuin yhden rivin, voimme toistaa tämän kyselyn useita kertoja. Tästä seuraa kaksi haittaa:
- Jos tämä operaatio suoritetaan usein, voimme suorittaa tämän kyselyn monta kertaa.
- Ei ole mitään takeita siitä, että samaa riviä ei valita useaan kertaan. Jos näin tapahtuu, sovellus voi yrittää kyselyä uudelleen. Jos taulukko on suuri, tämä tapahtuma on harvinainen ja voimme jättää sen huomiotta – ellei
RAND()funktio ole epäluotettava. Mutta pienissä taulukoissa tämä voi olla ongelma.
Esimerkkiavaimessa voi myös olla aukkoja – toisin sanoen jotkut numerot voivat puuttua. Tämä johtuu poistoista ja epäonnistuneista transaktioista. Enimmäisarvoa pienempiä numeroita ei käytetä uudelleen. Tämän ongelman kiertämiseksi voimme käyttää kahta tekniikkaa.
Käytetään >=
Jos käytämme >=-operaattoria WHERE-lausekkeessa, kysely palauttaa aina rivin. Jos tuotettua numeroa ei ole, käytetään seuraavaa. Tämä tarkoittaa kuitenkin sitä, että heti reiän jälkeen olevilla arvoilla on enemmän mahdollisuuksia tulla valituksi. Mitä suurempi reikä, sitä suuremmat mahdollisuudet.
Voit ajatella, että sinun ei pitäisi välittää tästä, ja olet luultavasti oikeassa. Mutta ennen kuin päätöksesi on lopullinen, ota huomioon suuren reiän mahdollisuus.
Trying hard
Jos kysely ei palauta yhtään riviä, voimme vain yrittää uudelleen. Suurille taulukoille, joissa on vain muutama pieni reikä, tämä on täysin hyvä. Mutta isoissa rei’issä, joissa on monta reikää, tai suurissa rei’issä, tämä tekniikka voi kuluttaa liikaa resursseja.
Ei kannata olla liian vainoharhainen tämän suhteen. Tehkää vain vähän matematiikkaa. Mikä on puuttuvien arvojen suhde taulukossasi? Tämä kertoo, kuinka monta kertaa kyselyä yritetään keskimäärin uudelleen.
Monien rivien valitseminen
Voidaksemme valita useita rivejä tällä tekniikalla, voimme:
- toistaa kyselyn useaan kertaan;
- tai paremman suorituskyvyn saamiseksi käyttää
>=-operaattoria ja käyttääLIMITsuurempaa kuin yksi. Tämä tekee kuitenkin tuloksista paljon vähemmän satunnaisia.
Sattumanvaraisen valinnan siirtäminen sovellukseen
Yksinkertaisimmillaan tämä tekniikka koostuu siitä, että valitaan sattumanvaraisesti vierekkäisten id:ien lohko. Sovellus valitsee satunnaisesti ne, joita se käyttää, ja valitsee sitten yhteensopivat rivit.
Esitellään, että halutaan valita 1000 arvon lohkoista:
Mitä suurempi lohko, sitä enemmän resursseja kuluu, sitä satunnaisempi on tulos. Sovelluksen vastuulla on valita lohkoista satunnaiset uniikit olemassa olevat id:t, joten kyselyä ei pitäisi koskaan joutua yrittämään uudelleen.
MOD-vaihtoehto
Tämän tekniikan ongelmana on, että rivit palautetaan samasta lohkosta, jossa on vierekkäisiä id:itä. Tämä voi olla täysin hyväksyttävää, varsinkin jos lohko on suuri. Mutta jos se ei ole, voisimme lisätä jonkin verran monimutkaisuutta valitsemalla lohkon, jossa on ei-yhtenäisiä rivejä.
Tämän vaihtoehdon ideana on:
- Määritellä makrolohkoja, joissa on enimmäkseen ei-yhtenäisiä rivejä;
- Valita sattumanvaraisesti yksi makrolohko;
- Palauta lohko siitä.
Tätä varten voimme laskea id:n moduulin ja käyttää sitä satunnaisten tulosten valintaan. Voimme esimerkiksi määritellä indeksoidun virtuaalisen sarakkeen lausekkeella (id MOD 4). Jokaisella rivillä on arvo 0:n ja 3:n välillä. Vaikka näissä makrolohkoissa olisi reikiä, näiden makrolohkojen rivit eivät useimmiten ole vierekkäisiä, ja niiden pitäisi olla suunnilleen sama luku.
Sovelluksen pitäisi luoda satunnaisluku väliltä 0 ja 3. Sen jälkeen valitaan lohkot näistä makrolohkoista:
SET @block_size := 1000;SELECT id FROM some_table WHERE id_mod = FLOOR(RAND() * 3) ORDER BY id LIMIT @block_size;Kaltainen tapa toteuttaa tämä ajatus on käyttää osioita, joissa osioinnin funktio on id:n moduuli. Ehdottaisin tätä vain, jos taulukko hyötyisi osioinnista muista syistä.
Tekniikan valinta
Lohkotekniikoilla ajetaan enemmän kyselyjä kuin ensimmäisellä >=-operaattorilla, ja tulos voi olla parempi tai sitten ei. Verrattuna retry-vaihtoehtoon tämä voi ajaa enemmän tai vähemmän kyselyitä, ja tulos on huonompi.
Yleisesti lohkotekniikat ovat parempia, jos meillä on aukkoja ensisijaisessa avaimessa.
Satunnaissarjojen välimuistiin tallentaminen
Edelliset menetelmät ovat kompromissi: suorituskyky vs. parempi satunnaislaatuisuus, jossa nopeampi ratkaisu on myös monimutkaisempi toteuttaa. Niin kauan kuin emme käytä ORDER BY RAND() antipatternia, satunnaisrivien valinnan ei pitäisi aiheuttaa suorituskykyongelmia. Mutta entä jos se aiheuttaa?
Voisimme tallentaa välimuistiin joitakin satunnaisesti lajiteltuja tunnuksia, jotka on saatu millä tahansa edellisistä ratkaisuista. Voisimme käyttää tällaista kyselyä (MySQL-syntaksi):
Voisimme käyttää sarjoja nousevassa tai laskevassa järjestyksessä, satunnaisesti. Tai sovellus voisi sekoittaa niitä.
Ongelmat:
- Kun kohde lisätään, meidän pitäisi valita satunnaisesti, pitääkö se lisätä sarjaan, korvaten satunnaisen kohteen.
- Kun kohde poistetaan, meidän pitäisi poistaa se kaikista sarjoista. Se pitäisi korvata toisella satunnaisella kohteella.
- Voisimme ehkä ajoittain poistaa vanhimmat sarjat ja korvata ne uusilla, jotta käyttäjäkokemuksen satunnaisuus paranisi.
Johtopäätökset
Kommentoi tavalliseen tapaan ja kerro minulle, jos huomaat virheen tässä artikkelissa, jos olet eri mieltä jostain asiasta, jos kerrot omakohtaisia kokemuksiasi tai jos sinulla on lisää ideoita, joita voit lisätä.