giriş
Mən bu hesabatı Moskvada GopherCon Russia 2019 konfransında ingilis dilində və Nijni Novqorodda keçirilən görüşdə rus dilində verdim. Söhbət bitmap indeksindən gedir - B-ağacından daha az yayılmışdır, lakin daha az maraqlı deyil. Paylaşma ingilis dilində konfransda çıxışlar və rus dilində mətn transkriptləri.
Bitmap indeksinin necə işlədiyinə, nə vaxt daha yaxşı olduğuna, digər indekslərdən nə vaxt pis olduğuna və hansı hallarda onlardan əhəmiyyətli dərəcədə sürətli olduğuna baxacağıq; Gəlin görək hansı məşhur DBMS-lərin artıq bitmap indeksləri var; Gəlin Go-da özümüzü yazmağa çalışaq. Və "desert üçün" biz öz super sürətli ixtisaslaşmış məlumat bazamızı yaratmaq üçün hazır kitabxanalardan istifadə edəcəyik.
Ümid edirəm ki, əsərlərim sizin üçün faydalı və maraqlı olacaq. Get!
Giriş
Hamıya salam! Axşam altıdır və hamımız çox yorğunuq. Darıxdırıcı verilənlər bazası indeksi nəzəriyyəsi haqqında danışmaq üçün əla vaxtdır, elə deyilmi? Narahat olmayın, mən burada və orada bir neçə sətir mənbə kodum olacaq. 🙂
Bütün zarafatları bir kənara qoysaq, hesabat məlumatlarla doludur və bizim çox vaxtımız yoxdur. Beləliklə, başlayaq.
Bu gün aşağıdakılar haqqında danışacağam:
- indekslər nədir;
- bitmap indeksi nədir;
- harada istifadə olunur və harada istifadə olunmur və niyə;
- Go-da sadə tətbiq və kompilyatorla bir az mübarizə;
- Go assembler-də bir qədər az sadə, lakin daha məhsuldar tətbiq;
- bitmap indekslərinin "problemləri";
- mövcud tətbiqlər.
Beləliklə, indekslər nədir?
İndeks, əsas məlumatlara əlavə olaraq saxladığımız və yenilədiyimiz ayrıca məlumat strukturudur. Axtarışı sürətləndirmək üçün istifadə olunur. İndekslər olmadan axtarış məlumatların tam şəkildə keçməsini tələb edəcək (tam skan adlanan proses) və bu proses xətti alqoritmik mürəkkəbliyə malikdir. Lakin verilənlər bazaları adətən böyük miqdarda məlumat ehtiva edir və xətti mürəkkəblik çox yavaşdır. İdeal olaraq, loqarifmik və ya sabit bir alırıq.
Bu, incəliklər və mübadilələrlə dolu olduqca mürəkkəb mövzudur, lakin onilliklər ərzində verilənlər bazası inkişafı və tədqiqatına baxdıqdan sonra, verilənlər bazası indekslərinin yaradılması üçün yalnız bir neçə geniş istifadə olunan yanaşmanın olduğunu söyləməyə hazıram.
Birinci yanaşma, axtarış sahəsini daha kiçik hissələrə bölməklə, ierarxik olaraq axtarış sahəsini azaltmaqdır.
Biz bunu adətən müxtəlif ağac növləri ilə edirik. Məsələn, qarderobunuzda müxtəlif mövzulara bölünmüş daha kiçik qutu materialları ehtiva edən böyük bir qutu material ola bilər. Əgər materiallara ehtiyacınız varsa, yəqin ki, onları "Cookie" deyilən qutuda deyil, "Materiallar" yazılan qutuda axtaracaqsınız, elə deyilmi?
İkinci yanaşma dərhal istədiyiniz elementi və ya elementlər qrupunu seçməkdir. Bunu hash xəritələrində və ya əks indekslərdə edirik. Hash xəritələrindən istifadə əvvəlki nümunəyə çox bənzəyir, lakin şkafınızda bir qutu qutu əvəzinə bir dəstə kiçik qutu son əşyalar var.
Üçüncü yanaşma, axtarış ehtiyacını aradan qaldırmaqdır. Bunu Bloom filtrlərindən və ya kuku filtrlərindən istifadə edərək edirik. Birincilər dərhal cavab verir, sizi axtarışdan xilas edir.
Sonuncu yanaşma müasir avadanlıqların bizə verdiyi bütün gücdən tam istifadə etməkdir. Bu, bitmap indekslərində etdiyimiz şeydir. Bəli, onlardan istifadə edərkən bəzən bütün indeksi nəzərdən keçirməliyik, lakin biz bunu çox səmərəli edirik.
Dediyim kimi, verilənlər bazası indekslərinin mövzusu geniş və kompromislərlə doludur. Bu o deməkdir ki, bəzən biz eyni anda bir neçə yanaşmadan istifadə edə bilərik: əgər axtarışı daha da sürətləndirmək lazımdırsa və ya bütün mümkün axtarış növlərini əhatə etmək lazımdırsa.
Bu gün mən bunların ən az bilinən yanaşması - bitmap indeksləri haqqında danışacağam.
Mən kiməm ki, bu mövzuda danışım?
Mən Badoo-da komanda rəhbəri kimi işləyirəm (bəlkə də siz digər məhsulumuz Bumble ilə daha çox tanışsınız). Artıq dünyada 400 milyondan çox istifadəçimiz və onlar üçün ən yaxşı uyğunluğu seçən bir çox funksiyamız var. Biz bunu bitmap indeksləri daxil olmaqla fərdi xidmətlərdən istifadə edərək edirik.
Beləliklə, bitmap indeksi nədir?
Bitmap indeksləri, adından da göründüyü kimi, axtarış indeksini həyata keçirmək üçün bit xəritələrindən və ya bit dəstlərindən istifadə edir. Quş baxışı baxımından bu indeks hər hansı obyekti (məsələn, insanlar) və onların xassələrini və ya parametrlərini (yaş, göz rəngi və s.) təmsil edən bir və ya bir neçə belə bitmapdan və bit əməliyyatlarından istifadə edən alqoritmdən (AND, OR, NOT) ibarətdir. ) axtarış sorğusuna cavab vermək üçün.
Bizə deyilir ki, bitmap indeksləri bir çox aşağı kardinallıq sütunları üzrə sorğuları birləşdirən axtarışların olduğu hallarda ("göz rəngi" və ya "ailə vəziyyəti" ilə müqayisədə "şəhər mərkəzindən məsafə" kimi bir şey hesab edin) ən uyğun və çox performanslıdır. Amma sonra göstərəcəyəm ki, onlar yüksək kardinallıq sütunları üçün də yaxşı işləyirlər.
Bitmap indeksinin ən sadə nümunəsinə baxaq.
Təsəvvür edin ki, bizdə bu kimi binar xüsusiyyətləri olan Moskva restoranlarının siyahısı var:
- metro yaxınlığında;
- şəxsi parkinq var;
- veranda var (terrası var);
- masa rezerv edə bilərsiniz (rezervasiyaları qəbul edir);
- vegetarianlar üçün uyğundur (vegan dostu);
- bahalı (bahalı).
Gəlin hər bir restorana 0-dan başlayan ardıcıllıq nömrəsi verək və 6 bitmap üçün yaddaş ayıraq (hər bir xüsusiyyət üçün bir). Daha sonra restoranın bu xüsusiyyətə malik olub-olmamasından asılı olaraq bu bitmapları dolduracağıq. Əgər 4-cü restoranın verandası varsa, o zaman “verandası var” bitmapında 4-cü bit 1-ə təyin olunacaq (eyvan yoxdursa, onda 0).
İndi biz mümkün olan ən sadə bitmap indeksinə sahibik və ondan aşağıdakı kimi suallara cavab vermək üçün istifadə edə bilərik:
- “Mənə vegetarianlara uyğun restoranlar göstər”;
- "Mənə masa rezerv edə biləcəyiniz eyvanlı ucuz restoranlar göstərin."
Necə? Gəlin nəzər salaq. İlk müraciət çox sadədir. Bizə lazım olan tək şey “vegetarian dostluq” bitmapını götürmək və onu bitləri açıq olan restoranların siyahısına çevirməkdir.
İkinci sorğu bir az daha mürəkkəbdir. Biz ucuz restoranların siyahısını əldə etmək üçün “bahalı” bitmap-də DEYİL bitmap-dan istifadə etməliyik, sonra “Mən masa sifariş edə bilərəm” bitmapı ilə və nəticədə “veranda var” bitmapı ilə. Nəticə bitmap bütün meyarlarımıza cavab verən müəssisələrin siyahısını ehtiva edəcək. Bu nümunədə bu, yalnız Yunost restoranıdır.
Burada çoxlu nəzəriyyə var, amma narahat olmayın, kodu tezliklə görəcəyik.
Bitmap indeksləri harada istifadə olunur?
Əgər Google bitmap indekslərini araşdırsanız, cavabların 90%-i bu və ya digər şəkildə Oracle DB ilə əlaqəli olacaq. Ancaq digər DBMS-lər də yəqin ki, belə gözəl bir şeyi dəstəkləyir, elə deyilmi? Həqiqətən yox.
Əsas şübhəlilərin siyahısını nəzərdən keçirək.
MySQL hələ bitmap indekslərini dəstəkləmir, lakin bu seçimi əlavə etməyi təklif edən bir Təklif var ().
PostgreSQL bitmap indekslərini dəstəkləmir, lakin axtarış nəticələrini çoxsaylı digər indekslərdə birləşdirmək üçün sadə bitmaplardan və bit əməliyyatlarından istifadə edir.
Tarantool bitset indekslərinə malikdir və onlar üzərində sadə axtarışları dəstəkləyir.
Redis sadə bit sahələrinə malikdir) onları axtarmaq imkanı olmadan.
MongoDB hələ bitmap indekslərini dəstəkləmir, lakin bu seçimin əlavə edilməsini təklif edən bir Təklif də var.
Elasticsearch daxili bitmaplardan istifadə edir).
- Ancaq evimizdə yeni bir qonşu peyda oldu: Pilosa. Bu, Go-da yazılmış yeni qeyri-relational verilənlər bazasıdır. O, yalnız bitmap indekslərini ehtiva edir və hər şeyi onların əsasında qurur. Bu barədə bir az sonra danışacağıq.
Go-da həyata keçirmə
Bəs niyə bitmap indeksləri bu qədər nadir hallarda istifadə olunur? Bu suala cavab verməzdən əvvəl sizə Go-da çox sadə bitmap indeksini necə tətbiq edəcəyinizi göstərmək istərdim.
Bitmaplar mahiyyətcə sadəcə məlumat parçalarıdır. Go-da bunun üçün bayt dilimlərindən istifadə edək.
Bizdə bir restoran xarakteristikası üçün bir bitmap var və bitmapdakı hər bit konkret restoranın bu xüsusiyyətə malik olub-olmadığını göstərir.
Bizə iki köməkçi funksiya lazımdır. Biri bitmaplarımızı təsadüfi məlumatlarla doldurmaq üçün istifadə olunacaq. Təsadüfi, lakin müəyyən bir ehtimalla restoranın hər bir mülkü var. Məsələn, mən hesab edirəm ki, Moskvada çox az restoran var ki, orada masa rezerv edə bilməyəcəksiniz və mənə elə gəlir ki, müəssisələrin təxminən 20%-i vegetarianlar üçün uyğundur.
İkinci funksiya bitmapı restoranların siyahısına çevirəcək.
“Mənə verandası olan və rezervasiya edə bilən ucuz restoranları göstərin” sualına cavab vermək üçün bizə iki bit əməliyyat lazımdır: NOT və AND.
Daha mürəkkəb VƏ DEYİL operatorundan istifadə etməklə kodumuzu bir az sadələşdirə bilərik.
Bu əməliyyatların hər biri üçün funksiyalarımız var. Onların hər ikisi dilimlərdən keçir, hər birindən müvafiq elementləri götürür, onları bir az əməliyyatla birləşdirib nəticəni yaranan dilimə qoyur.
İndi biz axtarış sorğusuna cavab vermək üçün bit xəritələrimizdən və funksiyalarımızdan istifadə edə bilərik.
Funksiyalar çox sadə olsa da, performans o qədər də yüksək deyil və biz funksiya hər dəfə çağırılanda yeni yaranan dilimi qaytarmamaqla xeyli pula qənaət etmişik.
pprof ilə bir az profilləşdirmə etdikdən sonra, Go kompilyatorunda çox sadə, lakin çox vacib bir optimallaşdırmanın çatışmadığını gördüm: funksiyanın daxil edilməsi.
Fakt budur ki, Go kompilyatoru dilimlərdən keçən döngələrdən dəhşətli dərəcədə qorxur və bu cür döngələri ehtiva edən daxili funksiyalardan qəti şəkildə imtina edir.
Ancaq mən qorxmuram və köhnə günlərdə olduğu kimi, döngə əvəzinə goto istifadə edərək tərtibçini aldada bilərəm.
Gördüyünüz kimi, indi kompilyator məmnuniyyətlə funksiyamızı daxil edəcək! Nəticədə təxminən 2 mikrosaniyə qənaət etməyə nail oluruq. Pis deyil!
Montaj çıxışına diqqətlə baxsanız, ikinci darboğazı görmək asandır. Tərtibatçı ən isti döngəmizin içərisinə bir dilim sərhəd yoxlamasını əlavə etdi. Fakt budur ki, Go təhlükəsiz bir dildir, tərtibçi mənim üç arqumentimin (üç dilim) müxtəlif ölçülü olmasından qorxur. Axı, o zaman sözdə tampon daşmasının baş verməsinin nəzəri ehtimalı olacaq.
Bütün dilimlərin eyni ölçüdə olduğunu göstərməklə kompilyatoru əmin edək. Bunu funksiyamızın əvvəlinə sadə bir yoxlama əlavə etməklə edə bilərik.
Bunu görən tərtibçi sevinclə çeki atlayır və biz daha 500 nanosaniyə qənaət etmiş oluruq.
Böyük itlər
Tamam, biz sadə tətbiqimizdən bəzi performansı sıxışdıra bildik, lakin bu nəticə əslində mövcud avadanlıqla mümkün olandan daha pisdir.
Etdiyimiz tək şey əsas bit əməliyyatlarıdır və prosessorlarımız onları çox səmərəli şəkildə yerinə yetirir. Ancaq təəssüf ki, prosessorumuzu çox kiçik iş parçaları ilə "qidalandırırıq". Funksiyalarımız əməliyyatları bayt-bayt əsasında yerinə yetirir. UInt8 dilimlərindən istifadə edərək 64 baytlıq parçalarla işləmək üçün kodumuzu çox asanlıqla düzəldə bilərik.
Gördüyünüz kimi, bu kiçik dəyişiklik partiyanın həcmini səkkiz dəfə artırmaqla proqramımızı səkkiz dəfə sürətləndirdi. Qazancın xətti olduğunu söyləmək olar.
Assemblerdə həyata keçirmə
Amma bu son deyil. Prosessorlarımız 16, 32 və hətta 64 baytlıq hissələrlə işləyə bilər. Bu cür “geniş” əməliyyatlar tək təlimat çoxlu verilənlər (SIMD; bir təlimat, çoxlu verilənlər) adlanır və kodun belə əməliyyatlardan istifadə etməsi üçün çevrilməsi prosesi vektorlaşdırma adlanır.
Təəssüf ki, Go kompilyatoru vektorlaşdırmada əla deyil. Hal-hazırda, Go kodunu vektorlaşdırmağın yeganə yolu Go assemblerindən istifadə edərək bu əməliyyatları əl ilə götürmək və qoymaqdır.
Go assembler qəribə bir heyvandır. Yəqin ki, montaj dilinin yazdığınız kompüterin arxitekturası ilə sıx bağlı olan bir şey olduğunu bilirsiniz, lakin Go-da belə deyil. Go assembler daha çox IRL (aralıq təmsil dili) və ya ara dil kimidir: praktiki olaraq platformadan müstəqildir. Rob Pike əla performans göstərdi bu mövzuda bir neçə il əvvəl Denverdəki GopherCon-da.
Bundan əlavə, Go ümumi qəbul edilmiş AT&T və Intel formatlarından fərqlənən qeyri-adi Plan 9 formatından istifadə edir.
Əminliklə demək olar ki, Go assembler-i əl ilə yazmaq ən əyləncəli deyil.
Ancaq xoşbəxtlikdən, Go assembler yazmağa kömək edən iki yüksək səviyyəli alət var: PeachPy və avo. Hər iki utilit müvafiq olaraq Python və Go dillərində yazılmış daha yüksək səviyyəli koddan Go assembler yaradır.
Bu yardım proqramları reyestrlərin ayrılması, dövrlərin yazılması kimi işləri sadələşdirir və ümumiyyətlə Go-da montaj proqramlaşdırma dünyasına daxil olmaq prosesini sadələşdirir.
Biz avo-dan istifadə edəcəyik, ona görə də proqramlarımız demək olar ki, müntəzəm Go proqramları olacaq.
Avo proqramının ən sadə nümunəsi belə görünür. Bizim öz daxilində Add() funksiyasını təyin edən main() funksiyamız var, onun mənası iki ədəd əlavə etməkdir. Parametrləri adla almaq və pulsuz və uyğun prosessor registrlərindən birini əldə etmək üçün burada köməkçi funksiyalar var. ADDQ-da göründüyü kimi, hər bir prosessor əməliyyatı avo-da müvafiq funksiyaya malikdir. Nəhayət, nəticədə alınan dəyəri saxlamaq üçün köməkçi funksiya görürük.
gogener deyərək proqramı avo-da icra edəcəyik və nəticədə iki fayl yaranacaq:
- Go assembler-də nəticə kodu ilə add.s;
- iki dünyanı birləşdirmək üçün funksiya başlıqları ilə stub.go: Get və assembler.
Avonun nə etdiyini və necə etdiyini gördükdən sonra indi funksiyalarımıza baxaq. Funksiyaların həm skalyar, həm də vektor (SIMD) versiyalarını tətbiq etdim.
Əvvəlcə skalyar versiyalara baxaq.
Əvvəlki nümunədə olduğu kimi, biz pulsuz və etibarlı ümumi təyinatlı registr tələb edirik, arqumentlər üçün ofsetləri və ölçüləri hesablamağa ehtiyac yoxdur. avo bütün bunları bizim üçün edir.
Performansı yaxşılaşdırmaq və Go kompilyatorunu aldatmaq üçün etiketlərdən və goto (və ya atlamalar) istifadə edirdik, lakin indi biz bunu əvvəldən edirik. Məsələ ondadır ki, dövrlər daha yüksək səviyyəli anlayışdır. Assemblerdə yalnız etiketlər və atlamalar var.
Qalan kod artıq tanış və başa düşülən olmalıdır. Etiketləri və atlamaları olan bir döngəni təqlid edirik, iki dilimimizdən kiçik bir məlumat parçası götürürük, onları bir az əməliyyatla birləşdiririk (VƏ bu vəziyyətdə YOX) və nəticəni yaranan dilimə qoyuruq. Hamısı.
Son assembler kodu belə görünür. Bizə ofsetləri və ölçüləri hesablamaq (yaşıl rənglə vurğulanmış) və ya istifadə olunan registrləri izləmək (qırmızı rənglə vurğulanmış) lazım deyildi.
Assembly dili tətbiqinin performansını Go-da ən yaxşı tətbiqetmənin performansı ilə müqayisə etsək, bunun eyni olduğunu görərik. Və bu gözlənilir. Axı biz xüsusi bir şey etmədik - biz sadəcə Go kompilyatorunun nə edəcəyini təkrarladıq.
Təəssüf ki, biz kompilyatoru assembler dilində yazılmış funksiyalarımızı daxil etməyə məcbur edə bilmərik. Go kompilyatorunda hazırda belə bir xüsusiyyət yoxdur, baxmayaraq ki, onu əlavə etmək üçün xeyli müddətdir ki, müraciət edilib.
Bu səbəbdən assembler dilində kiçik funksiyalardan heç bir fayda əldə etmək mümkün deyil. Biz ya böyük funksiyalar yazmalıyıq, ya da yeni riyaziyyat/bit paketindən istifadə etməliyik, ya da assembler dilini keçməliyik.
İndi funksiyalarımızın vektor versiyalarına baxaq.
Bu misal üçün mən AVX2-dən istifadə etmək qərarına gəldim, ona görə də 32 baytlıq parçalarda işləyən əməliyyatlardan istifadə edəcəyik. Kodun strukturu skalyar versiyaya çox bənzəyir: parametrlərin yüklənməsi, pulsuz paylaşılan reyestrin tələb edilməsi və s.
Bir yenilik ondan ibarətdir ki, daha geniş vektor əməliyyatları xüsusi geniş registrlərdən istifadə edir. 32 baytlıq hissələrdə bunlar Y ilə prefiks edilmiş registrlərdir. Buna görə kodda YMM() funksiyasını görürsünüz. Əgər mən AVX-512-ni 64 bitlik parçalarla istifadə etsəydim, prefiks Z olardı.
İkinci yenilik ondan ibarətdir ki, mən loop unrolling adlı optimallaşdırmadan istifadə etmək qərarına gəldim ki, bu da döngənin başlanğıcına keçməzdən əvvəl səkkiz dövrə əməliyyatını əl ilə etmək deməkdir. Bu optimallaşdırma koddakı filialların sayını azaldır və mövcud pulsuz registrlərin sayı ilə məhdudlaşır.
Yaxşı, performans haqqında nə demək olar? O gözəldir! Ən yaxşı Go həlli ilə müqayisədə təxminən yeddi dəfə sürətlənmə əldə etdik. Təsirli, elə deyilmi?
Lakin hətta bu tətbiqetmə potensial olaraq sorğu planlayıcısı üçün AVX-512, əvvəlcədən yükləmə və ya JIT (vaxtında tərtibçi) istifadə etməklə sürətləndirilə bilər. Ancaq bu, əlbəttə ki, ayrı bir hesabat üçün bir mövzudur.
Bitmap indeksləri ilə bağlı problemlər
İndi biz artıq Go-da bitmap indeksinin sadə tətbiqinə və montaj dilində daha məhsuldar bir tətbiqə baxdıq, nəhayət, bitmap indekslərinin niyə belə nadir hallarda istifadə edildiyi barədə danışaq.
Köhnə sənədlər bitmap indeksləri ilə bağlı üç problemdən bəhs edir, lakin daha yeni sənədlər və mən onların artıq aktual olmadığını iddia edirəm. Bu problemlərin hər birinə dərindən girməyəcəyik, lakin onlara səthi baxacağıq.
Yüksək kardinallıq problemi
Beləliklə, bizə deyilir ki, bitmap indeksləri yalnız aşağı kardinallığı olan, yəni bir neçə dəyəri olan (məsələn, cinsiyyət və ya göz rəngi) olan sahələr üçün uyğundur və bunun səbəbi belə sahələrin adi təsviri (bir dəyər başına bit) yüksək kardinallıq vəziyyətində, o, çox yer tutacaq və üstəlik, bu bitmap indeksləri zəif (nadir hallarda) doldurulacaq.
Bəzən biz nömrələri təmsil etmək üçün istifadə etdiyimiz standart kimi fərqli bir təmsildən istifadə edə bilərik. Ancaq hər şeyi dəyişdirən sıxılma alqoritmlərinin meydana gəlməsi idi. Son onilliklər ərzində elm adamları və tədqiqatçılar bitmaplar üçün çoxlu sayda sıxılma alqoritmləri hazırladılar. Onların əsas üstünlüyü ondan ibarətdir ki, bit əməliyyatlarını yerinə yetirmək üçün bitmapları dekompressiya etməyə ehtiyac yoxdur - biz bit əməliyyatlarını birbaşa sıxılmış bitmaplarda yerinə yetirə bilərik.
Bu yaxınlarda, uğultu bitmapları kimi hibrid yanaşmalar görünməyə başladı. Onlar eyni zamanda bitmaplar üçün üç müxtəlif təsvirdən istifadə edirlər - bitmapların özləri, massivlər və sözdə bit qaçışları - və performansı artırmaq və yaddaş istehlakını minimuma endirmək üçün onlar arasında tarazlıq.
Ən populyar tətbiqlərdə uğultu bitmapları tapa bilərsiniz. Go üçün üçdən çox tətbiq də daxil olmaqla, müxtəlif proqramlaşdırma dilləri üçün çoxlu sayda tətbiqlər artıq mövcuddur.
Yüksək kardinallıqla mübarizə aparmağa kömək edə biləcək başqa bir yanaşma binning adlanır. Təsəvvür edin ki, bir insanın boyunu təmsil edən bir sahəniz var. Hündürlük üzən nöqtə rəqəmidir, lakin biz insanlar bunu belə düşünmürük. Bizim üçün boy 185,2 sm ilə 185,3 sm arasında heç bir fərq yoxdur.
Məlum oldu ki, oxşar dəyərləri 1 sm ərzində qruplara ayıra bilərik.
Və əgər biz də bilsək ki, çox az adam 50 sm-dən qısa və 250 sm-dən yüksəkdir, o zaman mahiyyət etibarilə sonsuz kardinallığı olan bir sahəni 200-ə yaxın dəyərə malik bir sahəyə çevirə bilərik.
Təbii ki, lazım gələrsə, sonradan əlavə filtrasiya edə bilərik.
Yüksək bant genişliyi problemi
Bitmap indeksləri ilə bağlı növbəti problem onların yenilənməsinin çox baha başa gəlməsidir.
Potensial olaraq yüzlərlə digər sorğu məlumatları axtararkən verilənlər bazası məlumatları yeniləyə bilməlidir. Paralel məlumat girişi və ya digər paylaşma problemləri ilə bağlı problemlərin qarşısını almaq üçün kilidlərə ehtiyacımız var. Bir böyük kilidin olduğu yerdə bir problem var - kilid mübahisəsi, bu kilid darboğaza çevrildikdə.
Bu problem parçalanma və ya versiyalı indekslərdən istifadə etməklə həll edilə və ya aradan qaldırıla bilər.
Sharding sadə və məlum bir şeydir. Bitmap indeksini hər hansı digər məlumat kimi parçalaya bilərsiniz. Bir böyük kilid əvəzinə bir dəstə kiçik qıfıl əldə edəcəksiniz və beləliklə, kilid mübahisəsindən xilas olacaqsınız.
Problemi həll etməyin ikinci yolu versiyalı indekslərdən istifadə etməkdir. Siz axtarış və ya oxumaq üçün istifadə etdiyiniz indeksin bir nüsxəsinə və yazmaq və ya yeniləmək üçün istifadə etdiyiniz nüsxəyə sahib ola bilərsiniz. Və müəyyən bir müddətdə bir dəfə (məsələn, hər 100 ms və ya 500 ms-də bir dəfə) onları təkrarlayır və dəyişdirirsiniz. Əlbəttə ki, bu yanaşma yalnız tətbiqinizin bir az geri qalan axtarış indeksini idarə edə bildiyi hallarda tətbiq edilir.
Bu iki yanaşma eyni vaxtda istifadə edilə bilər: bir parçalanmış versiya indeksinə sahib ola bilərsiniz.
Daha mürəkkəb sorğular
Bitmap indeksləri ilə bağlı son problem ondan ibarətdir ki, bizə deyirlər ki, onlar span sorğuları kimi daha mürəkkəb sorğu növləri üçün uyğun deyil.
Həqiqətən də, əgər bu barədə düşünsəniz, AND, OR və s. kimi bit əməliyyatları “Mənə gecəlik 200-300 dollar otaq qiymətləri olan otelləri göstərin” sorğuları üçün çox uyğun deyil.
Sadəlövh və çox ağılsız bir həll hər bir dollar dəyəri üçün nəticələri götürmək və onları bitwise OR əməliyyatı ilə birləşdirmək olardı.
Bir az daha yaxşı həll qruplaşdırmadan istifadə etmək olardı. Məsələn, 50 dollarlıq qruplarda. Bu, prosesimizi 50 dəfə sürətləndirərdi.
Ancaq problem bu tip sorğu üçün xüsusi olaraq yaradılmış görünüşdən istifadə etməklə də asanlıqla həll olunur. Elmi məqalələrdə buna diapazonla kodlanmış bitmaplar deyilir.
Bu təqdimatda biz bəzi dəyər üçün (məsələn, 200) sadəcə bir bit təyin etmirik, lakin bu dəyəri və hər şeyi daha yüksək olaraq təyin edirik. 200 və yuxarı. 300: 300 və yuxarı üçün eynidir. Və s.
Bu təmsildən istifadə edərək, indeksi cəmi iki dəfə keçməklə bu cür axtarış sorğusuna cavab verə bilərik. Əvvəlcə otağın qiymətinin az və ya 300 dollar olduğu otellərin siyahısını alacağıq, sonra isə ondan az və ya 199 dollar olan otelləri çıxaracağıq. Hazır.
Siz təəccüblənəcəksiniz, lakin bitmap indekslərindən istifadə etməklə hətta geoqueries də mümkündür. Hiylə, koordinatınızı həndəsi fiqurla əhatə edən həndəsi təsvirdən istifadə etməkdir. Məsələn, Google-dan S2. Şəkil nömrələnə bilən üç və ya daha çox kəsişən xətlər şəklində təmsil oluna bilməlidir. Beləliklə, biz geoqueryimizi “boşluq boyunca” (bu nömrələnmiş sətirlər boyunca) bir neçə sorğuya çevirə bilərik.
Hazır Çözümler
Ümid edirəm ki, sizi bir az maraqlandırdım və indi arsenalınızda başqa faydalı alətiniz var. Əgər nə vaxtsa belə bir şey etmək lazımdırsa, hansı tərəfə baxmaq lazım olduğunu biləcəksiniz.
Bununla belə, hər kəsin sıfırdan bitmap indeksləri yaratmaq üçün vaxtı, səbri və ya resursları yoxdur. Məsələn, SIMD istifadə edərək, xüsusilə daha inkişaf etmişlər.
Xoşbəxtlikdən, sizə kömək edəcək bir neçə hazır həll yolu var.
Nəriltili bit xəritələri
Birincisi, artıq danışdığım eyni gurultulu bitmaplar kitabxanası var. Bu, tam hüquqlu bitmap indeksi yaratmaq üçün lazım olan bütün lazımi konteynerləri və bit əməliyyatlarını ehtiva edir.
Təəssüf ki, hazırda Go tətbiqlərinin heç biri SIMD-dən istifadə etmir, yəni Go tətbiqləri, məsələn, C tətbiqlərindən daha az performanslıdır.
Pilosa
Sizə kömək edə biləcək başqa bir məhsul, əslində, yalnız bitmap indekslərinə malik olan Pilosa DBMS-dir. Bu nisbətən yeni bir həlldir, lakin böyük sürətlə ürəkləri fəth edir.
Pilosa daxili olaraq uğultu bitmaplarından istifadə edir və sizə onlardan istifadə etmək imkanı verir, yuxarıda danışdığım bütün şeyləri sadələşdirir və izah edir: qruplaşdırma, diapazonla kodlanmış bitmaplar, sahə anlayışı və s.
Artıq tanış olduğunuz suala cavab vermək üçün Pilosa-dan istifadə nümunəsinə qısaca nəzər salaq.
Nümunə əvvəl gördüklərinizlə çox oxşardır. Biz Pilosa serverinə müştəri yaradırıq, indeks və lazımi sahələri yaradırıq, sonra sahələrimizi ehtimallarla təsadüfi məlumatlarla doldururuq və nəhayət, tanış sorğunu yerinə yetiririk.
Bundan sonra biz "bahalı" sahəsində DEYİL istifadə edirik, sonra nəticəni (və ya VƏ onu) "terras" sahəsi və "rezervasyonlar" sahəsi ilə kəsirik. Və nəhayət, son nəticəni əldə edirik.
Mən həqiqətən ümid edirəm ki, yaxın gələcəkdə bu yeni indeks növü MySQL və PostgreSQL kimi DBMS-lərdə - bitmap indekslərində də görünəcək.
Nəticə
Hələ yuxuya getməmisinizsə, təşəkkür edirəm. Vaxt məhdud olduğuna görə bir çox mövzuya qısaca toxunmalı oldum, amma ümid edirəm ki, söhbət faydalı və bəlkə də motivasiya edici oldu.
Bitmap indeksləri haqqında bilmək yaxşıdır, hətta onlara hazırda ehtiyacınız olmasa belə. Qoy onlar alətlər qutunuzda başqa bir alət olsunlar.
Biz Go üçün müxtəlif performans fəndlərinə və Go kompilyatorunun hələ çox yaxşı idarə etmədiyi şeylərə baxdıq. Ancaq bu, hər bir Go proqramçısının bilməsi üçün tamamilə faydalıdır.
Sənə demək istədiyim bu idi. Çox sağ ol!
Mənbə: www.habr.com