invoering
Dit verslag heb ik in het Engels gegeven op de GopherCon Russia 2019 conferentie in Moskou en in het Russisch tijdens een meetup in Nizjni Novgorod. We hebben het over een bitmapindex - minder gebruikelijk dan B-tree, maar niet minder interessant. Delen toespraken op de conferentie in het Engels en teksttranscripties in het Russisch.
We zullen bekijken hoe een bitmapindex werkt, wanneer deze beter is, wanneer deze slechter is dan andere indexen, en in welke gevallen deze aanzienlijk sneller is dan deze; Laten we eens kijken welke populaire DBMS'en al bitmapindexen hebben; Laten we proberen onze eigen in Go te schrijven. En “als dessert” zullen we kant-en-klare bibliotheken gebruiken om onze eigen supersnelle gespecialiseerde database te creëren.
Ik hoop echt dat mijn werken nuttig en interessant voor je zullen zijn. Gaan!
Introductie
Dag Allemaal! Het is zes uur 's avonds en we zijn allemaal supermoe. Een goed moment om over saaie database-indextheorie te praten, toch? Maak je geen zorgen, ik heb hier en daar een paar regels broncode. 🙂
Alle grappen terzijde: het rapport staat boordevol informatie en we hebben niet veel tijd. Dus laten we beginnen.
Vandaag zal ik het hebben over het volgende:
- wat zijn indexen;
- wat is een bitmapindex;
- waar het wordt gebruikt en waar het NIET wordt gebruikt en waarom;
- eenvoudige implementatie in Go en een beetje gedoe met de compiler;
- iets minder eenvoudige, maar veel productievere implementatie in Go assembler;
- “problemen” van bitmapindexen;
- bestaande implementaties.
Dus wat zijn indexen?
De index is een aparte datastructuur die we naast de hoofdgegevens onderhouden en bijwerken. Het wordt gebruikt om het zoeken te versnellen. Zonder indexen zou het zoeken nodig zijn om de gegevens volledig te doorlopen (een proces dat volledige scan wordt genoemd), en dit proces heeft een lineaire algoritmische complexiteit. Maar databases bevatten doorgaans enorme hoeveelheden gegevens en de lineaire complexiteit is te traag. Idealiter zouden we een logaritmische of constante waarde krijgen.
Dit is een enorm complex onderwerp, vol subtiliteiten en compromissen, maar na decennia van databaseontwikkeling en onderzoek te hebben bekeken, ben ik bereid te zeggen dat er slechts een paar veelgebruikte benaderingen zijn voor het maken van database-indexen.
De eerste benadering is om de zoekruimte hiërarchisch te verkleinen, door de zoekruimte in kleinere delen te verdelen.
Meestal doen we dit met verschillende soorten bomen. Een voorbeeld is een grote doos met materialen in je kast, waarin kleinere dozen met materialen zijn verdeeld over verschillende onderwerpen. Als je materialen nodig hebt, zul je ze waarschijnlijk zoeken in een doos met de tekst 'Materialen' in plaats van een doos met de tekst 'Cookies', toch?
De tweede benadering is om onmiddellijk het gewenste element of de gewenste groep elementen te selecteren. Dit doen we in hashmaps of omgekeerde indexen. Het gebruik van hash-kaarten lijkt erg op het vorige voorbeeld, maar in plaats van een doos met dozen heb je een aantal kleine dozen met laatste items in je kast.
De derde benadering is het elimineren van de noodzaak van zoeken. Dit doen wij met behulp van Bloomfilters of koekoekfilters. De eerste geven direct antwoord, zodat u niet hoeft te zoeken.
De laatste aanpak is om volledig gebruik te maken van alle kracht die moderne hardware ons geeft. Dit is precies wat we doen in bitmapindexen. Ja, als we ze gebruiken, moeten we soms de hele index doornemen, maar we doen het superefficiënt.
Zoals ik al zei, het onderwerp database-indexen is omvangrijk en vol compromissen. Dit betekent dat we soms meerdere benaderingen tegelijk kunnen gebruiken: als we het zoeken nog meer moeten versnellen, of als we alle mogelijke zoektypen moeten bestrijken.
Vandaag zal ik het hebben over de minst bekende benadering hiervan: bitmapindexen.
Wie ben ik om over dit onderwerp te spreken?
Ik werk als teamleider bij Badoo (misschien ben je meer bekend met ons andere product, Bumble). We hebben al meer dan 400 miljoen gebruikers over de hele wereld en veel functies die de beste match voor hen selecteren. Dit doen wij met behulp van aangepaste diensten, waaronder bitmapindexen.
Dus wat is een bitmapindex?
Bitmapindexen gebruiken, zoals de naam al doet vermoeden, bitmaps of bitsets om een zoekindex te implementeren. Vanuit vogelperspectief bestaat deze index uit een of meer van dergelijke bitmaps die entiteiten (zoals mensen) en hun eigenschappen of parameters (leeftijd, oogkleur, enz.) vertegenwoordigen, en een algoritme dat bitbewerkingen gebruikt (AND, OR, NOT ) om de zoekopdracht te beantwoorden.
Er is ons verteld dat bitmapindexen het meest geschikt zijn en zeer goed presteren voor gevallen waarin er zoekopdrachten zijn die zoekopdrachten combineren in veel kolommen met lage kardinaliteit (denk aan "oogkleur" of "burgerlijke staat" versus zoiets als "afstand tot stadscentrum" ). Maar ik zal later laten zien dat ze ook prima werken voor kolommen met een hoge kardinaliteit.
Laten we eens kijken naar het eenvoudigste voorbeeld van een bitmapindex.
Stel je voor dat we een lijst hebben met restaurants in Moskou met binaire eigenschappen zoals deze:
- dichtbij metro;
- er is privéparkeergelegenheid;
- er is een veranda (heeft terras);
- u kunt een tafel reserveren (accepteert reserveringen);
- geschikt voor vegetariërs (veganistisch);
- duur (duur).
Laten we elk restaurant een volgnummer geven dat begint bij 0 en geheugen toewijzen aan 6 bitmaps (één voor elk kenmerk). Vervolgens vullen we deze bitmaps in, afhankelijk van of het restaurant over deze eigenschap beschikt of niet. Als restaurant 4 een veranda heeft, wordt bit nr. 4 in de bitmap “heeft een veranda” op 1 gezet (als er geen veranda is, dan op 0).
Nu hebben we de eenvoudigst mogelijke bitmapindex en kunnen we deze gebruiken om vragen te beantwoorden zoals:
- “Laat mij vegetarische restaurants zien”;
- “Laat mij goedkope restaurants zien met een veranda waar je een tafel kunt reserveren.”
Hoe? Laten we eens kijken. Het eerste verzoek is heel eenvoudig. Het enige wat we hoeven te doen is de ‘vegetarischvriendelijke’ bitmap te nemen en deze om te zetten in een lijst met restaurants waarvan de stukjes zichtbaar zijn.
Het tweede verzoek is iets ingewikkelder. We moeten de NIET-bitmap op de “dure” bitmap gebruiken om een lijst met goedkope restaurants te krijgen, dan EN met de “kan ik een tafel reserveren” bitmap en EN het resultaat met de “er is een veranda” bitmap. De resulterende bitmap bevat een lijst met vestigingen die aan al onze criteria voldoen. In dit voorbeeld is dit alleen restaurant Yunost.
Er komt veel theorie bij kijken, maar maak je geen zorgen, we zullen de code zeer binnenkort zien.
Waar worden bitmapindexen gebruikt?
Als u bitmapindexen op Google gebruikt, zal 90% van de antwoorden op de een of andere manier verband houden met Oracle DB. Maar andere DBMS'en ondersteunen waarschijnlijk ook zoiets cools, toch? Niet echt.
Laten we de lijst met hoofdverdachten doornemen.
MySQL ondersteunt nog geen bitmapindexen, maar er is een voorstel dat voorstelt deze optie toe te voegen ().
PostgreSQL ondersteunt geen bitmapindexen, maar gebruikt eenvoudige bitmaps en bitbewerkingen om zoekresultaten uit meerdere andere indexen te combineren.
Tarantool heeft bitset-indexen en ondersteunt eenvoudige zoekopdrachten daarop.
Redis heeft eenvoudige bitvelden) zonder de mogelijkheid om ernaar te zoeken.
MongoDB ondersteunt nog geen bitmapindexen, maar er is ook een voorstel dat suggereert deze optie toe te voegen
Elasticsearch maakt intern gebruik van bitmaps).
- Maar er is een nieuwe buurvrouw in ons huis verschenen: Pilosa. Dit is een nieuwe niet-relationele database geschreven in Go. Het bevat alleen bitmapindexen en baseert alles daarop. We zullen er later over praten.
Implementatie in Go
Maar waarom worden bitmapindexen zo zelden gebruikt? Voordat ik deze vraag beantwoord, wil ik u laten zien hoe u een zeer eenvoudige bitmapindex in Go implementeert.
Bitmaps zijn in wezen slechts stukjes gegevens. Laten we hiervoor in Go byteplakken gebruiken.
We hebben één bitmap voor één restaurantkenmerk, en elk bit in de bitmap geeft aan of een bepaald restaurant deze eigenschap heeft of niet.
We hebben twee helperfuncties nodig. Eén ervan zal worden gebruikt om onze bitmaps te vullen met willekeurige gegevens. Willekeurig, maar met een zekere waarschijnlijkheid dat het restaurant elke eigenschap heeft. Ik geloof bijvoorbeeld dat er maar heel weinig restaurants in Moskou zijn waar je geen tafel kunt reserveren, en het lijkt mij dat ongeveer 20% van de etablissementen geschikt is voor vegetariërs.
De tweede functie converteert de bitmap naar een lijst met restaurants.
Om de vraag 'Laat mij goedkope restaurants zien die een terras hebben en kunnen reserveren' te beantwoorden, hebben we twee bewerkingen nodig: NIET en EN.
We kunnen onze code een beetje vereenvoudigen door de complexere AND NOT-operator te gebruiken.
We hebben functies voor elk van deze bewerkingen. Beiden doorlopen de plakjes, nemen de overeenkomstige elementen van elk, combineren ze met een beetje bewerking en plaatsen het resultaat in het resulterende segment.
En nu kunnen we onze bitmaps en functies gebruiken om de zoekopdracht te beantwoorden.
De prestaties zijn niet zo hoog, ook al zijn de functies heel eenvoudig en hebben we veel geld bespaard door niet elke keer dat de functie werd aangeroepen een nieuw resulterend segment terug te sturen.
Na wat profilering met pprof, merkte ik dat de Go-compiler een heel eenvoudige maar zeer belangrijke optimalisatie miste: functie-inlining.
Feit is dat de Go-compiler vreselijk bang is voor lussen die door plakjes gaan, en categorisch weigert functies inline te plaatsen die dergelijke lussen bevatten.
Maar ik ben niet bang en ik kan de compiler voor de gek houden door goto te gebruiken in plaats van een lus, zoals vroeger.
En zoals je kunt zien, zal de compiler nu met plezier onze functie inlineen! Hierdoor slagen we erin om ongeveer 2 microseconden te besparen. Niet slecht!
Het tweede knelpunt is gemakkelijk te zien als je goed naar de assemblage-output kijkt. De compiler heeft een slice-grenscontrole toegevoegd aan onze populairste lus. Feit is dat Go een veilige taal is, de compiler is bang dat mijn drie argumenten (drie plakjes) van verschillende grootte zijn. Er bestaat dan immers theoretisch een mogelijkheid dat er een zogenaamde buffer overflow optreedt.
Laten we de compiler geruststellen door hem te laten zien dat alle segmenten even groot zijn. We kunnen dit doen door een eenvoudige controle toe te voegen aan het begin van onze functie.
Als de compiler dit ziet, slaat hij de controle vrolijk over, en uiteindelijk besparen we nog eens 500 nanoseconden.
Grote butches
Oké, we zijn erin geslaagd wat prestaties uit onze eenvoudige implementatie te halen, maar dit resultaat is eigenlijk veel slechter dan mogelijk is met de huidige hardware.
Het enige wat we doen zijn eenvoudige bitbewerkingen, en onze processors voeren deze zeer efficiënt uit. Maar helaas 'voeden' we onze processor met heel kleine stukjes werk. Onze functies voeren bewerkingen byte voor byte uit. We kunnen onze code heel gemakkelijk aanpassen om te werken met chunks van 8 bytes met behulp van UInt64-plakken.
Zoals u kunt zien, versnelde deze kleine verandering ons programma acht keer door de batchgrootte acht keer te vergroten. Er kan worden gezegd dat de winst lineair is.
Implementatie in assembler
Maar dit is niet het einde. Onze processors kunnen werken met chunks van 16, 32 en zelfs 64 bytes. Dergelijke “brede” operaties worden single instruction multiple data (SIMD; één instructie, veel data) genoemd, en het proces van het transformeren van code zodat deze dergelijke operaties gebruikt, wordt vectorisatie genoemd.
Helaas is de Go-compiler verre van uitstekend in vectorisatie. Momenteel is de enige manier om Go-code te vectoriseren het uitvoeren en handmatig uitvoeren van deze bewerkingen met behulp van Go assembler.
Go-assembler is een vreemd beest. Je weet waarschijnlijk dat assembleertaal iets is dat sterk verbonden is met de architectuur van de computer waarvoor je schrijft, maar dat is niet het geval in Go. Go assembler lijkt meer op een IRL (tussenliggende representatietaal) of tussentaal: het is praktisch platformonafhankelijk. Rob Pike leverde een uitstekende prestatie over dit onderwerp enkele jaren geleden op GopherCon in Denver.
Bovendien gebruikt Go een ongebruikelijk Plan 9-formaat, dat afwijkt van de algemeen aanvaarde AT&T- en Intel-formaten.
Het is veilig om te zeggen dat het met de hand schrijven van Go assembler niet het leukste is.
Maar gelukkig zijn er al twee tools van hoog niveau die ons helpen bij het schrijven van Go assembler: PeachPy en avo. Beide hulpprogramma's genereren de Go-assembler op basis van code op een hoger niveau, geschreven in respectievelijk Python en Go.
Deze hulpprogramma's vereenvoudigen zaken als registertoewijzing, het schrijven van lussen en vereenvoudigen in het algemeen het proces om in de wereld van assemblageprogrammering in Go te komen.
We gebruiken avo, dus onze programma's zullen bijna gewone Go-programma's zijn.
Dit is hoe het eenvoudigste voorbeeld van een avo-programma eruit ziet. We hebben een functie main() die in zichzelf de functie Add() definieert, waarvan de betekenis het optellen van twee getallen is. Er zijn hier helperfuncties om parameters op naam te krijgen en een van de gratis en geschikte processorregisters te krijgen. Elke processorbewerking heeft een overeenkomstige functie op avo, zoals te zien in ADDQ. Ten slotte zien we een hulpfunctie voor het opslaan van de resulterende waarde.
Door go generator aan te roepen, zullen we het programma op avo uitvoeren en als resultaat zullen er twee bestanden worden gegenereerd:
- add.s met de resulterende code in Go assembler;
- stub.go met functieheaders om de twee werelden met elkaar te verbinden: Go en assembler.
Nu we hebben gezien wat avo doet en hoe, gaan we eens kijken naar onze functies. Ik heb zowel scalaire als vectorversies (SIMD) van de functies geïmplementeerd.
Laten we eerst naar de scalaire versies kijken.
Net als in het vorige voorbeeld vragen we om een gratis en geldig register voor algemene doeleinden. We hoeven geen offsets en afmetingen voor de argumenten te berekenen. avo doet dit allemaal voor ons.
Vroeger gebruikten we labels en goto (of sprongen) om de prestaties te verbeteren en de Go-compiler te misleiden, maar nu doen we het vanaf het begin. Het punt is dat cycli een concept op een hoger niveau zijn. In assembler hebben we alleen labels en sprongen.
De resterende code zou al bekend en begrijpelijk moeten zijn. We emuleren een lus met labels en sprongen, nemen een klein stukje gegevens van onze twee segmenten, combineren ze met een bitbewerking (EN NIET in dit geval) en plaatsen het resultaat vervolgens in het resulterende segment. Alle.
Zo ziet de uiteindelijke assemblercode eruit. We hoefden geen offsets en afmetingen te berekenen (groen gemarkeerd) of de gebruikte registers bij te houden (rood gemarkeerd).
Als we de prestaties van de assembleertaalimplementatie vergelijken met de prestaties van de beste implementatie in Go, zullen we zien dat deze hetzelfde zijn. En dit wordt verwacht. We hebben tenslotte niets speciaals gedaan - we hebben alleen gereproduceerd wat een Go-compiler zou doen.
Helaas kunnen we de compiler niet dwingen om onze in assembleertaal geschreven functies inline te zetten. De Go-compiler beschikt momenteel niet over een dergelijke functie, hoewel er al geruime tijd een verzoek is om deze toe te voegen.
Dit is de reden waarom het onmogelijk is om enig voordeel te halen uit kleine functies in assembleertaal. We moeten óf grote functies schrijven, óf het nieuwe math/bits-pakket gebruiken, óf de assembler-taal omzeilen.
Laten we nu naar de vectorversies van onze functies kijken.
Voor dit voorbeeld heb ik besloten AVX2 te gebruiken, dus we zullen bewerkingen gebruiken die werken op chunks van 32 bytes. De structuur van de code lijkt sterk op de scalaire versie: parameters laden, vragen om een gratis gedeeld register, enz.
Eén innovatie is dat bredere vectoroperaties speciale brede registers gebruiken. In het geval van chunks van 32 bytes zijn dit registers met het voorvoegsel Y. Daarom zie je de functie YMM() in de code. Als ik AVX-512 zou gebruiken met 64-bits chunks, zou het voorvoegsel Z zijn.
De tweede innovatie is dat ik heb besloten om een optimalisatie te gebruiken die 'loop unrolling' wordt genoemd, wat betekent dat je acht lusbewerkingen handmatig moet uitvoeren voordat je naar het begin van de lus springt. Deze optimalisatie vermindert het aantal vertakkingen in de code en wordt beperkt door het aantal beschikbare gratis registers.
Nou, hoe zit het met de prestaties? Ze is mooi! We bereikten een versnelling van ongeveer zeven keer vergeleken met de beste Go-oplossing. Indrukwekkend, toch?
Maar zelfs deze implementatie zou mogelijk kunnen worden versneld door gebruik te maken van AVX-512, prefetching of een JIT (just-in-time compiler) voor de queryplanner. Maar dit is zeker een onderwerp voor een apart rapport.
Problemen met bitmapindexen
Nu we al hebben gekeken naar een eenvoudige implementatie van een bitmapindex in Go en een veel productievere in assembleertaal, laten we het eindelijk hebben over waarom bitmapindexen zo zelden worden gebruikt.
Oudere artikelen noemen drie problemen met bitmapindexen, maar nieuwere artikelen en ik betogen dat deze niet langer relevant zijn. We zullen niet diep op elk van deze problemen ingaan, maar ze oppervlakkig bekijken.
Het probleem van hoge kardinaliteit
Er wordt ons dus verteld dat bitmapindexen alleen geschikt zijn voor velden met een lage kardinaliteit, dat wil zeggen velden met weinig waarden (bijvoorbeeld geslacht of oogkleur), en de reden is dat de gebruikelijke weergave van dergelijke velden (één bit per waarde) bij hoge kardinaliteit te veel ruimte in beslag neemt en bovendien zullen deze bitmapindexen slecht (zelden) gevuld zijn.
Soms gebruiken we een andere weergave, zoals de standaardweergave die we gebruiken om getallen weer te geven. Maar het was de komst van compressie-algoritmen die alles veranderden. De afgelopen decennia hebben wetenschappers en onderzoekers een groot aantal compressie-algoritmen voor bitmaps bedacht. Hun belangrijkste voordeel is dat het niet nodig is om bitmaps te decomprimeren om bitbewerkingen uit te voeren; we kunnen bitbewerkingen rechtstreeks op gecomprimeerde bitmaps uitvoeren.
Onlangs zijn er hybride benaderingen verschenen, zoals brullende bitmaps. Ze gebruiken tegelijkertijd drie verschillende representaties voor bitmaps - bitmaps zelf, arrays en zogenaamde bitruns - en balanceren daartussen om de prestaties te maximaliseren en het geheugenverbruik te minimaliseren.
U kunt brullende bitmaps vinden in de meest populaire toepassingen. Er zijn al een groot aantal implementaties voor een grote verscheidenheid aan programmeertalen, waaronder meer dan drie implementaties voor Go.
Een andere benadering die ons kan helpen met hoge kardinaliteit om te gaan, wordt binning genoemd. Stel je voor dat je een veld hebt dat de lengte van een persoon weergeeft. Hoogte is een getal met drijvende komma, maar wij mensen denken er niet zo over na. Voor ons is er geen verschil tussen hoogte 185,2 cm en 185,3 cm.
Het blijkt dat we vergelijkbare waarden in groepen binnen 1 cm kunnen groeperen.
En als we ook weten dat heel weinig mensen kleiner zijn dan 50 cm en langer dan 250 cm, dan kunnen we in wezen een veld met oneindige kardinaliteit omzetten in een veld met een kardinaliteit van ongeveer 200 waarden.
Indien nodig kunnen we achteraf uiteraard nog extra filteren.
Probleem met hoge bandbreedte
Het volgende probleem met bitmapindexen is dat het updaten ervan erg duur kan zijn.
Databases moeten gegevens kunnen bijwerken terwijl potentieel honderden andere zoekopdrachten de gegevens doorzoeken. We hebben sloten nodig om problemen met gelijktijdige gegevenstoegang of andere problemen met delen te voorkomen. En waar er één grote sluis is, is er een probleem: slotconflicten, wanneer deze sluis een knelpunt wordt.
Dit probleem kan worden opgelost of omzeild door gebruik te maken van sharding of versie-indexen te gebruiken.
Sharding is een eenvoudig en bekend iets. U kunt een bitmapindex op dezelfde manier delen als andere gegevens. In plaats van één groot slot krijgt u een aantal kleine sloten en bent u zo van de slotconflicten af.
De tweede manier om het probleem op te lossen is het gebruik van versie-indexen. U kunt één exemplaar van de index hebben dat u gebruikt voor zoeken of lezen, en één exemplaar dat u gebruikt voor schrijven of bijwerken. En een keer in een bepaalde periode (bijvoorbeeld een keer per 100 ms of 500 ms) dupliceer je ze en verwissel je ze. Deze aanpak is uiteraard alleen van toepassing in gevallen waarin uw toepassing een enigszins achterblijvende zoekindex aankan.
Deze twee benaderingen kunnen tegelijkertijd worden gebruikt: u kunt een gesharde versie-index hebben.
Complexere vragen
Het laatste probleem met bitmapindexen is dat ons wordt verteld dat ze niet goed geschikt zijn voor complexere typen zoekopdrachten, zoals span-query's.
Als je erover nadenkt, zijn bitbewerkingen als AND, OR, etc. inderdaad niet erg geschikt voor vragen a la “Laat me hotels zien met kamerprijzen van 200 tot 300 dollar per nacht.”
Een naïeve en zeer onverstandige oplossing zou zijn om de resultaten voor elke dollarwaarde te nemen en deze te combineren met een bitsgewijze OR-bewerking.
Een iets betere oplossing zou zijn om groepering te gebruiken. Bijvoorbeeld in groepen van 50 dollar. Dit zou ons proces vijftig keer versnellen.
Maar het probleem kan ook eenvoudig worden opgelost door een weergave te gebruiken die speciaal voor dit type verzoek is gemaakt. In wetenschappelijke artikelen worden dit bereikgecodeerde bitmaps genoemd.
In deze weergave stellen we niet slechts één bit in voor een bepaalde waarde (bijvoorbeeld 200), maar stellen we deze waarde en alles hoger in. 200 en hoger. Hetzelfde voor 300: 300 en hoger. Enzovoort.
Met behulp van deze representatie kunnen we dit soort zoekopdrachten beantwoorden door de index slechts twee keer te doorlopen. Eerst krijgen we een lijst met hotels waar de kamer minder of $ 300 kost, en dan verwijderen we de hotels waar de kamer minder of $ 199 kost. Klaar.
U zult verrast zijn, maar zelfs geoquery's zijn mogelijk met behulp van bitmapindexen. De truc is om een geometrische weergave te gebruiken die je coördinaat omringt met een geometrische figuur. Bijvoorbeeld S2 van Google. De figuur moet kunnen worden weergegeven in de vorm van drie of meer elkaar snijdende lijnen die kunnen worden genummerd. Op deze manier kunnen we onze geoquery omzetten in verschillende zoekopdrachten “langs de kloof” (langs deze genummerde lijnen).
Ready-oplossingen
Ik hoop dat ik je een beetje heb geïnteresseerd en dat je nu weer een handig hulpmiddel in je arsenaal hebt. Als je ooit zoiets als dit moet doen, weet je welke kant je op moet kijken.
Niet iedereen heeft echter de tijd, het geduld of de middelen om helemaal opnieuw bitmapindexen te maken. Vooral geavanceerdere, bijvoorbeeld met behulp van SIMD.
Gelukkig zijn er verschillende kant-en-klare oplossingen die je kunnen helpen.
Brullende bitmaps
Ten eerste is er diezelfde brullende bitmapbibliotheek waar ik het al over had. Het bevat alle benodigde containers en bitbewerkingen die u nodig hebt om een volwaardige bitmapindex te maken.
Helaas maakt op dit moment geen van de Go-implementaties gebruik van SIMD, wat betekent dat Go-implementaties minder presteren dan bijvoorbeeld C-implementaties.
pilosa
Een ander product dat u kan helpen is Pilosa DBMS, dat feitelijk alleen bitmapindexen heeft. Dit is een relatief nieuwe oplossing, maar wint met grote snelheid harten.
Pilosa gebruikt intern brullende bitmaps en geeft je de mogelijkheid om ze te gebruiken, vereenvoudigt en legt alle dingen uit waar ik het hierboven over had: groepering, bereikgecodeerde bitmaps, het concept van een veld, enz.
Laten we even snel kijken naar een voorbeeld van het gebruik van Pilosa om een vraag te beantwoorden waarmee u al bekend bent.
Het voorbeeld lijkt erg op wat je eerder zag. We maken een client voor de Pilosa-server, maken een index en de benodigde velden, vullen onze velden vervolgens met willekeurige gegevens met waarschijnlijkheden en voeren ten slotte de bekende zoekopdracht uit.
Daarna gebruiken we NOT op het veld "duur" en kruisen we het resultaat (of EN) met het veld "terras" en met het veld "reserveringen". En uiteindelijk krijgen we het eindresultaat.
Ik hoop echt dat dit nieuwe type index in de nabije toekomst ook zal verschijnen in DBMS'en zoals MySQL en PostgreSQL - bitmapindexen.
Conclusie
Als je nog niet in slaap bent gevallen, bedankt. Vanwege de beperkte tijd moest ik veel onderwerpen kort bespreken, maar ik hoop dat de lezing nuttig en misschien zelfs motiverend was.
Bitmapindexen zijn goed om te weten, zelfs als u ze nu niet nodig heeft. Laat ze een extra hulpmiddel in uw gereedschapskist zijn.
We hebben verschillende prestatietrucs voor Go bekeken en dingen die de Go-compiler nog niet zo goed kan. Maar dit is absoluut nuttig voor elke Go-programmeur om te weten.
Dat is alles wat ik je wilde vertellen. Bedankt!
Bron: www.habr.com