Varför instrumentellt stöd för paginering på nycklar behövs

Hej alla! Jag är backendutvecklare och skriver mikrotjänster i Java + Spring. Jag arbetar i ett av utvecklingsteamen för interna produkter inom Tinkoff.

I vårt team dyker frågan om optimering av förfrågningar i databaser ofta upp. Man vill alltid ha det lite snabbare, men man kan inte alltid förlita sig på noggrant uppbyggda index – man måste leta efter alternativa lösningar. Under ett av dessa nätövriga sökningar efter rimliga optimeringar när man arbetar med databaser fann jag den oändligt användbara bloggen av Markus Winand, författare till boken SQL Performance Explained. Det är den sällsynta typen av bloggar där man kan läsa alla artiklar i följd.

Jag vill översätta en liten artikel av Markus för er. Den kan kallas ett slags manifest som syftar till att dra uppmärksamhet till det gamla, men fortfarande aktuella problemet med prestanda för offset-operationen enligt SQL-standarden.

På vissa ställen kommer jag att komplettera författaren med förklaringar och anteckningar. Alla sådana ställen kommer jag att märka som «anm.» för ökad tydlighet

En kort introduktion

Jag tror att många vet hur problematiskt och trögt det kan vara att arbeta med sidbaserade urval via offset. Men visste ni att det går att ganska enkelt ersätta med en mer effektiv konstruktion?

Så, nyckelordet offset anger för databasen att hoppa över de första n posterna i förfrågan. Men databasen måste fortfarande läsa dessa första n poster från disken, i angiven ordning (anm.: tillämpa sortering om den är angiven), och först efter det är det möjligt att återge posterna från och med n+1 och framåt. Det mest intressanta är att problemet inte ligger i den specifika implementeringen i databasen, utan i den ursprungliga definitionen enligt standarden:

…the rows are first sorted according to the and then limited by dropping the number of rows specified in the from the beginning…
-SQL:2016, Part 2, 4.15.3 Deriverade tabeller (anm.: just nu den mest använda standarden)

Huvudpunkten här är att offset tar ett enda parameter – antalet poster som ska hoppas över, och det är allt. Enligt en sådan definition kan databasen bara hämta alla poster och sedan kasta bort de onödiga. Det är uppenbart att en sådan definition av offset tvingar fram onödigt arbete. Och det spelar ingen roll om det är SQL eller NoSQL.

Lite mer smärta

Offset-problemet slutar inte här, och här är varför. Om en annan operation lägger till en ny post mellan läsningen av två datorsidor, vad händer i så fall?

När offset används för att hoppa över poster från tidigare sidor, finns det en sannolikhet att få dubbletter i situationen där en ny post läggs till mellan läsningarna av olika sidor (obs: detta kan hända när vi läser sida för sida med en order by-konstruktion, så att en ny post kan hamna mitt i vår resultatlista).

Diagrammet illustrerar tydligt en sådan situation. Databasen läser de första 10 posterna, sedan läggs en ny post till, vilket skiftar alla tidigare lästa poster med 1. Därefter tar databasen den nya sidan med 10 följande poster och börjar inte med den 11:e, som den ska, utan med den 10:e, vilket duplicerar denna post. Det finns även andra anomalier kopplade till användningen av detta uttryck, men detta är den vanligaste.

Som vi redan har klargjort är detta inte ett problem specifikt för någon databas eller dess implementationer. Problemet ligger i definitionen av paginering enligt SQL-standarden. Vi säger till databasen vilken sida som behöver hämtas eller hur många poster som ska hoppas över. Men databasen har helt enkelt inte tillräckligt med information för att optimera sådan begäran.

Det bör också klargöras att detta problem inte beror på något specifikt nyckelord, utan rättare sagt på semantiken i frågan. Det finns flera identiska syntaxer med liknande problematik:

• Nyckelordet offset, som nämnts tidigare.
• Konstruktionen med två nyckelord limit [offset] (även om limit i sig inte är så dålig).
• Filtrering baserad på nedre gränser, uppbyggd på radnummer (till exempel row_number(), rownum, etc.).

Alla dessa uttryck säger bara hur många rader som ska hoppas över, utan någon ytterligare information eller kontext.

I denna artikel används nyckelordet offset som en generalisering av alla dessa varianter.

Liv utan OFFSET

Och nu kan vi föreställa oss hur vår värld skulle se ut utan alla dessa problem. Det visar sig att livet utan offset inte är så svårt: med en select-fråga kan du välja endast de rader som vi ännu inte har sett (obs: det vill säga de som inte fanns på föregående sida), med hjälp av ett villkor i where.

I det här fallet utgår vi från det faktum att selektering utförs över en sorterad mängd (den gamla goda order by). Eftersom vi har en sorterad mängd kan vi använda ett ganska enkelt filter för att bara hämta de data som ligger efter den senaste posten på föregående sida:

    SELECT ...
    FROM ...
    WHERE ...
    AND id < ?last_seen_id
    ORDER BY id DESC
    FETCH FIRST 10 ROWS ONLY

Det är hela principen för detta tillvägagångssätt. Självklart blir det mer komplicerat när man sorterar efter flera kolumner, men grundidén är densamma. Det är viktigt att notera att denna konstruktion är tillämplig i många NoSQL-lösningar.

Denna metod kallas seek-metod eller keyset-paginering. Den löser problemet med flytande resultat (exempel: situationen med poster mellan sidläsningar som beskrevs tidigare) och, som vi alla gillar, fungerar den snabbare och mer stabilt än klassisk offset. Stabiliteten ligger i att bearbetningstiden för förfrågan inte ökar i proportion till numret på den begärda tabellen (exempel: om man vill veta mer om olika metoder för paginering kan man bläddra igenom författarens presentation. Där kan man också hitta jämförande benchmark för olika metoder).

En av bilderna berättar om att paginering baserad på nycklar, naturligtvis, inte är allsmäktig — den har sina begränsningar. Den mest betydelsefulla är att den inte har möjlighet att läsa slumpmässiga sidor (exempel: oordnat). Men i en tid med oändlig skrollning (exempel: på frontend) är detta inte ett så stort problem. Att ange sidnumret för klick är hur som helst en dålig lösning när man utvecklar UI (exempel: författarens åsikt).Och vad med verktygen?

Paginering baserad på nycklar passar ofta inte på grund av bristande verktygsstöd för denna metod. De flesta utvecklingsverktyg, inklusive olika ramverk, erbjuder ingen möjlighet att välja hur pagineringen ska utföras.

Situationen förvärras av att den beskrivna metoden kräver genomgående stöd i de använda teknologierna — från databashanterare till utförandet av AJAX-förfrågningar i webbläsaren vid oändlig skrollning. Istället för att bara ange sidnumret måste man nu ange en uppsättning nycklar för alla sidor samtidigt.

Situationen förvärras av det faktum att den beskrivna metoden kräver genomgripande stöd i de teknologier som används - från databashanteringssystemet till utförandet av AJAX-förfrågningar i webbläsaren vid oändlig skrollning. Istället för att bara ange sidanumret måste man nu ange en uppsättning nycklar för alla sidor på en gång.

Antalet ramverk som stöder paginering på nycklar ökar gradvis. Här är vad som finns för tillfället:

• jOOQ för Java;
• order_query för Ruby;
• chunkator och Django Infinite Scroll Pagination för Django;
• SQL Alchemy sqlakeyset för Python;
• blaze-persistence — kriterie-API för implementationer av JPA;
• DBIx::Class::Wrapper för Perl;
• Massive.js, мапер для Node.js Keyset Documentation.

(Obs.: vissa länkar har tagits bort eftersom några bibliotek inte har uppdaterats sedan 2017–2018 vid tidpunkten för översättningen. Om du är intresserad kan du kolla in källan.)

Det är just på detta område som du behövs. Om du utvecklar eller underhåller ett ramverk som på något sätt använder paginering, ber jag dig, jag uppmanar dig, jag vädjar till dig att göra inhemskt stöd för paginering på nycklar. Om du har frågor eller behöver hjälp, hjälper jag gärna till (forum, Twitter, kontaktformulär) (Obs.: utifrån min erfarenhet av att kommunicera med Markus kan jag säga att han verkligen är entusiastisk över att sprida detta ämne).

Om du däremot använder färdiga lösningar som du anser förtjänar stöd för paginering på nycklar, skapa ett förslag eller till och med erbjud en färdig lösning om möjligt. Du kan också hänvisa till denna artikel i länken.

Slutsats

Anledningen till att en så enkel och användbar metod som paginering på nycklar är sällsynt beror inte på att det är tekniskt svårt eller kräver stora ansträngningar. Den främsta anledningen är att många är vana vid att se och arbeta med offset — denna metod dikteras av själva standarden.

Som en följd av detta funderar få på att ändra sin metod för paginering, och därför utvecklas verktygsstödet från ramverk och bibliotek svagt. Så om du är för idén och syftet med offsetsfri paginering, hjälp till att sprida den!

Källa: https://use-the-index-luke.com/no-offset
Författare: Markus Winand

Källa: habr.com