AllYouNeedIsBackend

Ik ben een enorme fan van databases. Ik wilde zelfs mijn eigen DBMS maken toen ik op de universiteit zat. Nu werk ik zowel met RDBMS als NoSQL oplossingen, en daar ben ik erg enthousiast over. Weet je, er is geen Golden Hammer, elk probleem heeft zijn eigen oplossing. Of een subset van oplossingen.

In de serie blog posts The SQL I Love <3 loop ik met je door een aantal met SQL opgeloste problemen die ik bijzonder interessant vond. De oplossingen zijn getest met een tabel met meer dan 100 miljoen records. Alle voorbeelden maken gebruik van MySQL, maar de ideeën zijn ook toepasbaar op andere relationele data stores zoals PostgreSQL, Oracle en SQL Server.

Dit hoofdstuk is gericht op het efficiënt scannen van een grote tabel met behulp van paginering met offset op de primaire sleutel. Dit is ook bekend als keyset pagination.

Achtergrond

In het hoofdstuk gebruiken we de volgende database structuur als voorbeeld. Het canonieke voorbeeld over gebruikers zou op elk domein moeten passen.

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;

Een paar opmerkingen over de structuur:

• external_id kolom slaat verwijzing op naar dezelfde gebruiker in ander systeem in UUID formaat
• name vertegenwoordigt Firstname Lastname
• metadata kolom bevat JSON blob met allerlei ongestructureerde gegevens

De tabel is relatief groot en bevat ongeveer 100 000 000 records.

Scanning a Large Table

Probleem: je moet door de tabel lopen, elk record extraheren, transformeren in de code van je toepassing en invoegen op een andere plaats. We richten ons op de eerste fase in de post – het scannen van de tabel.

Voor de hand liggende en verkeerde oplossing

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

In mijn geval met 100 000 000 records, wordt de query nooit afgemaakt. Het DBMS stopt hem gewoon. Waarom? Waarschijnlijk, omdat het leidde tot de poging om de hele tabel in RAM te laden. Alvorens gegevens terug te sturen naar de cliënt. Een andere veronderstelling – het kostte te veel tijd om de gegevens te laden voor het verzenden en de query werd uitgetimed. Hoe dan ook, onze poging om alle records op tijd te krijgen mislukte. We moeten een andere oplossing vinden.

Oplossing #2

We kunnen proberen om de gegevens in pagina’s te krijgen. Omdat records niet gegarandeerd geordend zijn in een tabel op fysiek of logisch niveau – moeten we ze aan de DBMS-kant sorteren met ORDER BY-clausule.

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)

Zoet. Het werkte. We hebben de eerste pagina met 10.000 records opgevraagd, en het duurde slechts 0.03 sec om die terug te sturen. Maar hoe zou het werken voor de 5000e pagina?

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)

Dit is inderdaad erg traag. Laten we eens kijken hoeveel tijd er nodig is om de gegevens voor de laatste pagina op te halen.

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)

Dit is krankzinnig. Het kan echter OK zijn voor oplossingen die op de achtergrond draaien. Nog een verborgen probleem met de aanpak kan worden onthuld als u probeert om een record te verwijderen uit de tabel in het midden van het scannen van het. Stel, je bent klaar met de 10e pagina (100 000 records zijn al bezocht), en je gaat de records tussen 100 001 en 110 000 scannen. Maar de records 99 998 en 99 999 worden verwijderd vóór de volgende SELECT uitvoering. In dat geval geeft de volgende query het onverwachte resultaat:

 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, ...

Zoals u kunt zien, heeft de query de records met de id’s 100 001 en 100 002 overgeslagen. Zij worden met deze aanpak niet door de applicatiecode verwerkt omdat zij na de twee verwijderbewerkingen in de eerste 100 000 records voorkomen. Daarom is de methode onbetrouwbaar als de dataset muteerbaar is.

Oplossing #3 – de laatste voor vandaag

De aanpak lijkt erg op de vorige omdat het nog steeds paging gebruikt, maar nu in plaats van te vertrouwen op het aantal gescande records, gebruiken we de user_id van het laatst bezochte record als de offset.

Simplified algorithm:

1. We krijgen PAGE_SIZE aantal records uit de tabel. Start offset waarde is 0.
2. Gebruik de max geretourneerde waarde voor user_id in de batch als de offset voor de volgende pagina.
3. Gebruik de volgende batch van de records die user_id waarde hoger dan huidige offset hebben.

De query in actie voor de 5000e pagina, elke pagina bevat gegevens over 10 000 gebruikers:

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)

Merk op, dat de waarden van user_id niet opeenvolgend zijn en hiaten kunnen vertonen, zoals 25 348 vlak na 25 345 is. De oplossing werkt ook als records van toekomstige pagina’s worden verwijderd – zelfs in dat geval slaat de query geen records over. Sweet, right?

Explaining performance

Om verder te leren, raad ik aan de resultaten van EXPLAIN EXTENDED te onderzoeken voor elke versie van de query om de volgende 10 000 records na 50 000 000 te krijgen.

Laten we ons concentreren op het belangrijkste verschil tussen uitvoeringsplannen voor 2e en 3e oplossingen, aangezien de 1e niet praktisch bruikbaar is voor grote tabellen.

• Join type: index vs range. De eerste betekent dat de hele indexboom wordt gescand om de records te vinden. range type vertelt ons dat de index alleen wordt gebruikt om overeenkomende rijen binnen een gespecificeerd bereik te vinden. Dus, range type is sneller dan index.
• Mogelijke sleutels: NULL vs PRIMARY. De kolom toont de sleutels die kunnen worden gebruikt door MySQL. BTW, kijken naar sleutels kolom, kunnen we zien dat uiteindelijk PRIMARY sleutel wordt gebruikt voor de beide queries.
• Rijen: 50 010 000 vs 50 000 000. De waarde geeft het aantal geanalyseerde records weer alvorens het resultaat terug te geven. Voor de 2e query, de waarde hangt af van hoe diep is onze scroll. Bijvoorbeeld, als we proberen om de volgende 10 000 records te krijgen na de 9999e pagina dan worden 99 990 000 records onderzocht. Daarentegen heeft de 3e query een constante waarde; het maakt niet uit of we gegevens laden voor de 1e pagina of de allerlaatste. Het is altijd de halve grootte van de tabel.
• Gefilterd: 200.00 vs 100.00. De kolom geeft het geschatte percentage van de tabel aan dat moet worden gefilterd vóór verwerking. Een hogere waarde is beter. De waarde van 100.00 betekent dat de query de hele tabel doorzoekt. Voor de tweede query is de waarde niet constant en afhankelijk van het paginanummer: als we naar de eerste pagina vragen, zou de waarde van de gefilterde kolom 1000000.00 zijn. Voor de allerlaatste pagina, zou het zijn 100.00.
• Extra: NULL vs Using where. Geeft extra informatie over hoe MySQL de query omzet. Het gebruik van WHERE op PRIMARY sleutel maakt de uitvoering van de query sneller.

Ik vermoed dat join type de parameter van de query is die de grootste bijdrage heeft geleverd aan de prestaties om de 3e query sneller te maken. Een ander belangrijk ding is dat de 2e query is zeer afhankelijk van het aantal van de pagina’s te scrollen. Meer diepe paginering is langzamer in dat geval.

Meer richtlijnen over het begrijpen van de uitvoer voor EXPLAIN commando kan worden gevonden in de officiële documentatie voor uw RDBMS.

Samenvatting

Het hoofdonderwerp voor de blog post was gerelateerd aan het scannen van een grote tabel met 100 000 000 records met behulp van offset met een primaire sleutel (keyset paginering). In totaal werden 3 verschillende benaderingen bekeken en getest op de overeenkomstige dataset. Ik raad slechts een van hen aan als je een mutabele grote tabel moet scannen.

Ook hebben we het gebruik van EXPLAIN EXTENDED commando herzien om het uitvoeringsplan van MySQL queries te analyseren. Ik ben er zeker van dat andere RDBMS hebben analogen voor de functionaliteit.

In het volgende hoofdstuk, zullen we aandacht besteden aan data aggregatie en opslag optimalisatie. Blijf op de hoogte!

Wat is uw methode om grote tabellen te scannen?

Weet u nog een ander doel van het gebruik van keyset paginering zoals in oplossing #3?