kirish
Men ushbu hisobotni Moskvadagi GopherCon Russia 2019 konferensiyasida ingliz tilida va Nijniy Novgoroddagi uchrashuvda rus tilida berdim. Biz bitmap indeksi haqida gapiramiz - B-daraxtga qaraganda kamroq tarqalgan, ammo qiziq emas. Ulashish konferensiyadagi nutqlari ingliz tilida va matn transkriptlari rus tilida.
Bitmap indeksi qanday ishlashini ko'rib chiqamiz, qachon yaxshiroq, qachon u boshqa indekslarga qaraganda yomonroq va qaysi hollarda u ulardan sezilarli darajada tezroq; Keling, qaysi mashhur DBMS allaqachon bitmap indekslariga ega ekanligini ko'rib chiqaylik; Keling, Go'da o'zimizni yozishga harakat qilaylik. Va "shirinlik uchun" biz o'zimizning tezkor ixtisoslashtirilgan ma'lumotlar bazasini yaratish uchun tayyor kutubxonalardan foydalanamiz.
Umid qilamanki, mening asarlarim siz uchun foydali va qiziqarli bo'ladi. Bor!
kirish
Hammaga salom! Kechqurun olti va hammamiz juda charchaganmiz. Zerikarli ma'lumotlar bazasi indekslari nazariyasi haqida gapirish uchun ajoyib vaqt, to'g'rimi? Xavotir olmang, menda bir-ikki qator manba kodi bor. π
Hamma hazillarni bir chetga surib qoβysak, hisobot juda koβp maβlumotlarga toβla va bizda koβp vaqt yoβq. Shunday qilib, keling, boshlaylik.
Bugun men quyidagilar haqida gaplashaman:
- indekslar nima;
- bitmap indeksi nima;
- qayerda ishlatiladi va qayerda YO'Q va nima uchun;
- Go-da oddiy amalga oshirish va kompilyator bilan ozgina kurashish;
- Go assembler-da biroz soddaroq, ammo ancha samarali amalga oshirish;
- bitmap indekslarining "muammolari";
- mavjud ilovalar.
Xo'sh, indekslar nima?
Indeks alohida ma'lumotlar tuzilmasi bo'lib, biz asosiy ma'lumotlarga qo'shimcha ravishda saqlab turamiz va yangilaymiz. U qidiruvni tezlashtirish uchun ishlatiladi. Indekslarsiz qidirish ma'lumotlarni to'liq ko'rib chiqishni talab qiladi (to'liq skanerlash deb ataladigan jarayon) va bu jarayon chiziqli algoritmik murakkablikka ega. Ammo ma'lumotlar bazalari odatda katta hajmdagi ma'lumotlarni o'z ichiga oladi va chiziqli murakkablik juda sekin. Ideal holda, biz logarifmik yoki doimiyni olamiz.
Bu juda murakkab mavzu bo'lib, nozikliklar va o'zaro kelishuvlar bilan to'ldirilgan, lekin o'nlab yillar davomida ma'lumotlar bazasini ishlab chiqish va tadqiqotlarni ko'rib chiqqandan so'ng, ma'lumotlar bazasi indekslarini yaratishda faqat bir nechta keng tarqalgan yondashuvlar mavjudligini aytishga tayyorman.
Birinchi yondashuv qidiruv maydonini ierarxik ravishda qisqartirish, qidiruv maydonini kichikroq qismlarga bo'lishdir.
Biz buni odatda har xil turdagi daraxtlar yordamida qilamiz. Masalan, sizning shkafingizdagi materiallarning katta qutisi bo'lishi mumkin, unda turli mavzularga bo'lingan kichikroq materiallar qutilari mavjud. Agar sizga materiallar kerak bo'lsa, siz ularni "Cookie" deb yozilgan qutidan ko'ra "Materiallar" deb yozilgan qutidan qidirasiz, to'g'rimi?
Ikkinchi yondashuv - kerakli elementni yoki elementlar guruhini darhol tanlash. Biz buni hash xaritalarida yoki teskari indekslarda qilamiz. Xesh-xaritalardan foydalanish avvalgi misolga juda o'xshaydi, lekin sizning shkafingizda qutilar qutisi o'rniga sizda bir nechta kichik qutilar mavjud.
Uchinchi yondashuv - qidiruvga bo'lgan ehtiyojni bartaraf etish. Buni Bloom filtrlari yoki kuku filtrlari yordamida qilamiz. Birinchilari bir zumda javob beradi, bu sizni qidirishdan qutqaradi.
Oxirgi yondashuv - zamonaviy apparatlar bizga beradigan barcha quvvatdan to'liq foydalanish. Bitmap indekslarida aynan shunday qilamiz. Ha, ulardan foydalanganda biz ba'zan butun indeksni ko'rib chiqishimiz kerak, lekin biz buni juda samarali qilamiz.
Aytganimdek, ma'lumotlar bazasi indekslari mavzusi juda keng va murosaga to'la. Bu shuni anglatadiki, ba'zida biz bir vaqtning o'zida bir nechta yondashuvlardan foydalanishimiz mumkin: agar biz qidiruvni yanada tezlashtirishimiz kerak bo'lsa yoki barcha mumkin bo'lgan qidiruv turlarini qamrab olishimiz kerak bo'lsa.
Bugun men ularning eng kam ma'lum bo'lgan yondashuvi - bitmap indekslari haqida gapiraman.
Men bu mavzuda gapiradigan kimman?
Men Badoo kompaniyasida guruh rahbari sifatida ishlayman (ehtimol, siz bizning boshqa mahsulotimiz Bumble bilan ko'proq tanishdirsiz). Bizda allaqachon dunyo bo'ylab 400 milliondan ortiq foydalanuvchi va ular uchun eng yaxshi moslikni tanlaydigan ko'plab xususiyatlar mavjud. Biz buni maxsus xizmatlar, jumladan bitmap indekslari yordamida qilamiz.
Xo'sh, bitmap indeksi nima?
Bitmap indekslari, nomidan ko'rinib turibdiki, qidiruv indeksini amalga oshirish uchun bitmap yoki bit-setlardan foydalanadi. Qushlarning nigohi nuqtai nazaridan, bu indeks har qanday ob'ektlarni (masalan, odamlarni) va ularning xususiyatlari yoki parametrlarini (yosh, ko'z rangi va boshqalar) ifodalovchi bir yoki bir nechta bitmaplardan va bit operatsiyalaridan (VA, YOKI, EMAS) foydalanadigan algoritmdan iborat. ) qidiruv so'roviga javob berish uchun.
Bizga aytilishicha, bitmap indekslari ko'plab past darajadagi ustunlar bo'ylab so'rovlarni birlashtirgan qidiruvlar mavjud bo'lgan holatlar uchun eng mos keladi va juda samaralidir ("ko'z rangi" yoki "oilaviy holat" va "shahar markazidan masofa" kabi narsalarni o'ylab ko'ring). Ammo keyinroq ular yuqori kardinallik ustunlari uchun ham yaxshi ishlashini ko'rsataman.
Bitmap indeksining eng oddiy misolini ko'rib chiqaylik.
Tasavvur qiling-a, bizda ikkilik xususiyatlarga ega Moskva restoranlari ro'yxati mavjud:
- metro yaqinida;
- shaxsiy avtoturargoh mavjud;
- veranda bor (teras bor);
- stolni bron qilishingiz mumkin (bronirovkalarni qabul qiladi);
- vegetarianlar uchun mos (vegan bilan do'st);
- qimmat (qimmat).
Keling, har bir restoranga 0 dan boshlanadigan tartib raqamini beramiz va 6 bitmap uchun xotira ajratamiz (har bir xususiyat uchun bittadan). Keyin restoranda ushbu xususiyatga ega yoki yo'qligiga qarab, biz ushbu bitmaplarni to'ldiramiz. Agar 4-restoran verandaga ega bo'lsa, u holda "verandaga ega" bitmapidagi 4-bit 1 ga o'rnatiladi (agar veranda bo'lmasa, u holda 0 ga).
Endi bizda mumkin bo'lgan eng oddiy bitmap indeksi mavjud va biz undan quyidagi kabi so'rovlarga javob berish uchun foydalanishimiz mumkin:
- "Menga vegetarianlarga mos restoranlarni ko'rsating";
- "Menga stolni bron qilishingiz mumkin bo'lgan ayvonli arzon restoranlarni ko'rsating."
Qanaqasiga? Keling, ko'rib chiqaylik. Birinchi so'rov juda oddiy. Biz qilishimiz kerak bo'lgan yagona narsa "vegetarianlarga do'stona" bitmapni olish va uni bitlari ochilgan restoranlar ro'yxatiga aylantirishdir.
Ikkinchi so'rov biroz murakkabroq. Arzon restoranlar roβyxatini olish uchun biz βqimmatβ bitmapda EMAS bitmapidan foydalanishimiz kerak, soβngra βJadvalni band qilsam boβladimiβ bitmapi bilan VA va natijada βveranda borβ bitmapi bilan. Olingan bitmap barcha mezonlarga javob beradigan muassasalar ro'yxatini o'z ichiga oladi. Bu misolda bu faqat Yunost restorani.
Bu yerda juda koβp nazariya bor, lekin xavotir olmang, kodni tez orada koβramiz.
Bitmap indekslari qayerda ishlatiladi?
Agar siz Google bitmap indekslarini qidirsangiz, javoblarning 90% u yoki bu tarzda Oracle DB bilan bog'liq bo'ladi. Ammo boshqa DBMSlar ham shunday ajoyib narsani qo'llab-quvvatlaydi, to'g'rimi? Unchalik emas.
Keling, asosiy gumondorlar ro'yxatini ko'rib chiqaylik.
MySQL hali bitmap indekslarini qo'llab-quvvatlamaydi, ammo bu variantni qo'shishni taklif qiluvchi taklif mavjud ().
PostgreSQL bitmap indekslarini qo'llab-quvvatlamaydi, lekin qidiruv natijalarini bir nechta boshqa indekslarda birlashtirish uchun oddiy bitmaplar va bit operatsiyalaridan foydalanadi.
Tarantool bitset indekslariga ega va ular bo'yicha oddiy qidiruvlarni qo'llab-quvvatlaydi.
Redis oddiy bit maydonlariga ega) ularni qidirish imkoniyatisiz.
MongoDB hali bitmap indekslarini qo'llab-quvvatlamaydi, ammo bu variantni qo'shishni taklif qiluvchi taklif ham mavjud.
Elasticsearch ichki bitmaplardan foydalanadi).
- Ammo bizning uyimizda yangi qo'shni paydo bo'ldi: Pilosa. Bu Go-da yozilgan yangi aloqasiz ma'lumotlar bazasi. U faqat bitmap indekslarini o'z ichiga oladi va hamma narsani ularga asoslaydi. Bu haqda biroz keyinroq gaplashamiz.
Go'da amalga oshirish
Lekin nega bitmap indekslari juda kam ishlatiladi? Bu savolga javob berishdan oldin, men sizga Go'da juda oddiy bitmap indeksini qanday amalga oshirishni ko'rsatmoqchiman.
Bitmaplar aslida faqat ma'lumotlar bo'laklaridir. Go'da buning uchun bayt bo'laklaridan foydalanamiz.
Bizda bitta restoran xarakteristikasi uchun bitta bitmap mavjud va bitmapdagi har bir bit ma'lum bir restoranda bu xususiyatga ega yoki yo'qligini bildiradi.
Bizga ikkita yordamchi funksiya kerak bo'ladi. Bittasi bizning bitmaplarimizni tasodifiy ma'lumotlar bilan to'ldirish uchun ishlatiladi. Tasodifiy, lekin ma'lum bir ehtimollik bilan restoran har bir mulkka ega. Misol uchun, men Moskvada stolni bron qila olmaydigan juda kam restoran borligiga ishonaman va menimcha, muassasalarning taxminan 20 foizi vegetarianlar uchun mos keladi.
Ikkinchi funksiya bitmapni restoranlar ro'yxatiga aylantiradi.
"Menga hovlisi bor va bron qilish mumkin bo'lgan arzon restoranlarni ko'rsating" so'roviga javob berish uchun bizga ikkita bit amal kerak: EMAS va VA.
Biz murakkabroq VA EMAS operatoridan foydalanib, kodimizni biroz soddalashtira olamiz.
Ushbu operatsiyalarning har biri uchun bizda funktsiyalar mavjud. Ularning ikkalasi ham bo'laklardan o'tadi, har biridan mos keladigan elementlarni oladi, ularni bir oz operatsiya bilan birlashtiradi va natijani olingan bo'lakka qo'yadi.
Va endi biz qidiruv so'roviga javob berish uchun bitmap va funksiyalarimizdan foydalanishimiz mumkin.
Funktsiyalar juda oddiy bo'lsa ham, unumdorlik unchalik yuqori emas va biz har safar funksiya chaqirilganda yangi hosil bo'lgan tilimni qaytarmaslik orqali ko'p pul tejadik.
Pprof bilan bir oz profillashdan so'ng, men Go kompilyatorida juda oddiy, ammo juda muhim optimallashtirish yo'qligini payqadim: funktsiyani kiritish.
Gap shundaki, Go kompilyatori tilimlardan o'tadigan tsikllardan juda qo'rqadi va bunday tsikllarni o'z ichiga olgan inline funktsiyalaridan qat'iyan rad etadi.
Lekin men qo'rqmayman va eski yaxshi kunlardagi kabi loop o'rniga goto dan foydalanib, kompilyatorni aldashim mumkin.
Ko'rib turganingizdek, endi kompilyator bizning funktsiyamizni mamnuniyat bilan kiritadi! Natijada biz taxminan 2 mikrosekundni tejashga erishamiz. Yomon emas!
Ikkinchi darboΔazni yig'ish chiqishiga diqqat bilan qarasangiz, ko'rish oson. Kompilyator bizning eng qizg'in tsiklimiz ichida bo'lak chegarasini tekshirishni qo'shdi. Gap shundaki, Go xavfsiz tildir, kompilyator mening uchta argumentim (uch tilim) har xil o'lchamda bo'lishidan qo'rqadi. Axir, keyin bufer to'lib ketishi deb ataladigan narsaning paydo bo'lishining nazariy imkoniyati mavjud bo'ladi.
Keling, kompilyatorni barcha bo'laklar bir xil o'lchamda ekanligini ko'rsatib, ishontiraylik. Funktsiyamizning boshida oddiy chek qo'shish orqali buni qilishimiz mumkin.
Buni ko'rib, kompilyator xursandchilik bilan chekni o'tkazib yuboradi va biz yana 500 nanosekundni tejaymiz.
Katta burmalar
OK, biz oddiy amalga oshirishimizdan biroz unumdorlikni siqib chiqara oldik, ammo bu natija amaldagi uskunadan ko'ra yomonroq.
Biz qiladigan narsa - bu asosiy bit operatsiyalari va bizning protsessorlarimiz ularni juda samarali bajaradi. Ammo, afsuski, biz protsessorimizni juda kichik ish qismlari bilan "oziqlantiramiz". Bizning funktsiyalarimiz operatsiyalarni bayt-bayt asosida bajaradi. Biz UInt8 tilimlari yordamida 64 baytlik qismlar bilan ishlash uchun kodimizni juda oson sozlashimiz mumkin.
Ko'rib turganingizdek, bu kichik o'zgarish bizning dasturimizni sakkiz marta tezlashtirdi va partiya hajmini sakkiz marta oshirdi. Daromadni chiziqli deb aytish mumkin.
Assemblerda amalga oshirish
Lekin bu oxiri emas. Bizning protsessorlarimiz 16, 32 va hatto 64 bayt bo'laklar bilan ishlashi mumkin. Bunday "keng" operatsiyalar bitta buyruqli ko'p ma'lumotlar (SIMD; bitta ko'rsatma, ko'p ma'lumotlar) deb ataladi va kodni bunday operatsiyalardan foydalanadigan tarzda o'zgartirish jarayoni vektorizatsiya deb ataladi.
Afsuski, Go kompilyatori vektorlashtirishda mukammal emas. Hozirda Go kodini vektorlashtirishning yagona yo'li bu operatsiyalarni Go assembler yordamida qo'lda olish va qo'yishdir.
Go assembler - g'alati hayvon. Assambleya tili siz yozayotgan kompyuter arxitekturasi bilan qattiq bogΚ»langan narsa ekanligini bilsangiz kerak, lekin GoΚΌda bunday emas. Go assembler ko'proq IRL (oraliq vakillik tili) yoki oraliq tilga o'xshaydi: u deyarli platformadan mustaqil. Rob Pike ajoyib o'yin ko'rsatdi bu mavzuda bir necha yil oldin Denverdagi GopherConda.
Bundan tashqari, Go umumiy qabul qilingan AT&T va Intel formatlaridan farq qiluvchi noodatiy Plan 9 formatidan foydalanadi.
Ishonch bilan aytish mumkinki, Go assemblerni qo'lda yozish eng qiziqarli emas.
Ammo, xayriyatki, Go assemblerni yozishga yordam beradigan ikkita yuqori darajadagi vosita allaqachon mavjud: PeachPy va avo. Ikkala yordamchi dastur mos ravishda Python va Go-da yozilgan yuqori darajadagi koddan Go assemblerini yaratadi.
Ushbu yordam dasturlari registrlarni taqsimlash, yozish tsikllari kabi narsalarni soddalashtiradi va umuman Go'da yig'ish dasturlash dunyosiga kirish jarayonini soddalashtiradi.
Biz avo dan foydalanamiz, shuning uchun bizning dasturlarimiz deyarli oddiy Go dasturlari bo'ladi.
Avo dasturining eng oddiy misoli shunday ko'rinadi. Bizda main() funktsiyasi mavjud bo'lib, u o'zida Add() funktsiyasini belgilaydi, uning ma'nosi ikkita raqamni qo'shishdir. Parametrlarni nomi bo'yicha olish va bepul va mos protsessor registrlaridan birini olish uchun bu erda yordamchi funktsiyalar mavjud. Har bir protsessor operatsiyasi ADDQ da ko'rsatilganidek, avo-da mos keladigan funktsiyaga ega. Nihoyat, biz olingan qiymatni saqlash uchun yordamchi funktsiyani ko'ramiz.
Gogener ni chaqirish orqali biz dasturni avo-da bajaramiz va natijada ikkita fayl hosil bo'ladi:
- Go assemblerda olingan kod bilan add.s;
- Ikki dunyoni bog'lash uchun funktsiya sarlavhalari bilan stub.go: Go va assembler.
Endi biz avo nima qilishini va qanday qilishini ko'rib chiqdik, keling, funktsiyalarimizni ko'rib chiqaylik. Men funktsiyalarning skalyar va vektor (SIMD) versiyalarini amalga oshirdim.
Avval skalyar versiyalarni ko'rib chiqamiz.
Oldingi misolda bo'lgani kabi, biz bepul va haqiqiy umumiy maqsadli registrni so'raymiz, biz argumentlar uchun ofset va o'lchamlarni hisoblashimiz shart emas. avo bularning barchasini biz uchun qiladi.
Biz ishlashni yaxshilash va Go kompilyatorini aldash uchun teglar va goto (yoki sakrash) dan foydalanardik, ammo hozir biz buni boshidan qilyapmiz. Gap shundaki, tsikllar yuqori darajadagi tushunchadir. Assemblerda bizda faqat teglar va sakrashlar mavjud.
Qolgan kod allaqachon tanish va tushunarli bo'lishi kerak. Biz teglar va sakrashlar bilan halqaga taqlid qilamiz, ikkita bo'limimizdan kichik bir ma'lumotni olamiz, ularni bit operatsiyalari bilan birlashtiramiz (VA bu holda EMAS) va natijani olingan bo'lakka qo'yamiz. Hammasi.
Yakuniy assembler kodi shunday ko'rinadi. Bizga ofset va o'lchamlarni (yashil rang bilan belgilangan) hisoblash yoki foydalanilgan registrlarni (qizil rang bilan belgilangan) kuzatib borish shart emas edi.
Assembler tilini amalga oshirish samaradorligini Go-dagi eng yaxshi dastur ishlashi bilan solishtirsak, bu xuddi shunday ekanligini ko'ramiz. Va bu kutilmoqda. Axir, biz hech qanday maxsus ish qilmadik - biz faqat Go kompilyatori nima qilishini takrorladik.
Afsuski, biz kompilyatorni assembler tilida yozilgan funktsiyalarimizni kiritishga majburlay olmaymiz. Go kompilyatorida hozirda bunday xususiyat mavjud emas, garchi uni qo'shish so'rovi ancha vaqtdan beri bo'lgan.
Shuning uchun assembler tilida kichik funksiyalardan hech qanday foyda olish mumkin emas. Biz katta funksiyalarni yozishimiz yoki yangi matematik/bit paketidan foydalanishimiz yoki assembler tilini chetlab o'tishimiz kerak.
Endi funksiyalarimizning vektor versiyalarini ko'rib chiqamiz.
Ushbu misol uchun men AVX2 dan foydalanishga qaror qildim, shuning uchun biz 32 baytli qismlarda ishlaydigan operatsiyalardan foydalanamiz. Kodning tuzilishi skaler versiyaga juda o'xshaydi: parametrlarni yuklash, bepul umumiy registrni so'rash va hk.
Yangiliklardan biri shundaki, kengroq vektor operatsiyalari maxsus keng registrlardan foydalanadi. 32 baytlik bo'laklar bo'lsa, ular Y bilan prefiksli registrlardir. Shuning uchun kodda YMM() funksiyasini ko'rasiz. Agar men AVX-512 dan 64 bitli qismlardan foydalansam, prefiks Z bo'lar edi.
Ikkinchi yangilik shundan iboratki, men loop unrolling deb nomlangan optimallashtirishdan foydalanishga qaror qildim, bu tsiklning boshiga o'tishdan oldin sakkizta tsikl operatsiyasini qo'lda bajarishni anglatadi. Ushbu optimallashtirish koddagi filiallar sonini kamaytiradi va mavjud bo'lgan bepul registrlar soni bilan cheklanadi.
Xo'sh, ishlash haqida nima deyish mumkin? U go'zal! Eng yaxshi Go yechimi bilan solishtirganda biz etti marta tezlashdik. Ta'sirli, to'g'rimi?
Ammo bu amalga oshirishni AVX-512, oldindan yuklash yoki so'rovlar rejalashtiruvchisi uchun JIT (faqat o'z vaqtida kompilyator) yordamida tezlashtirish mumkin. Lekin bu, albatta, alohida hisobot uchun mavzu.
Bitmap indekslari bilan bog'liq muammolar
Endi biz Go-da bitmap indeksining oddiy amalga oshirilishini va assembler tilida ancha samaraliroqni ko'rib chiqdik, keling, nima uchun bitmap indekslari juda kam qo'llanilishi haqida gapiraylik.
Eski qog'ozlarda bitmap indekslari bilan bog'liq uchta muammo haqida so'z boradi, ammo yangi maqolalar va men ular endi ahamiyatli emasligini ta'kidlayman. Biz ushbu muammolarning har biriga chuqurroq kirmaymiz, balki ularga yuzaki qaraymiz.
Yuqori kardinallik muammosi
Shunday qilib, bizga bitmap indekslari faqat kardinalligi past bo'lgan, ya'ni kam qiymatga ega bo'lgan maydonlar uchun mos kelishini aytishdi (masalan, jins yoki ko'z rangi) va buning sababi shundaki, bunday maydonlarning odatiy ko'rinishi (bitta qiymat boshiga bit) yuqori kardinallik bo'lsa, u juda ko'p joy egallaydi va bundan tashqari, bu bitmap indekslari yomon (kamdan-kam) to'ldiriladi.
Ba'zan biz raqamlarni ifodalash uchun foydalanadigan standart kabi boshqa ko'rinishdan foydalanishimiz mumkin. Ammo siqishni algoritmlarining paydo bo'lishi hamma narsani o'zgartirdi. So'nggi o'n yilliklarda olimlar va tadqiqotchilar bitmaplar uchun ko'p sonli siqish algoritmlarini ishlab chiqdilar. Ularning asosiy afzalligi shundaki, bitli operatsiyalarni bajarish uchun bitmaplarni ochishning hojati yo'q - biz bit operatsiyalarini to'g'ridan-to'g'ri siqilgan bitmaplarda bajarishimiz mumkin.
So'nggi paytlarda gibrid yondashuvlar paydo bo'la boshladi, masalan, roaring bitmaplar. Ular bir vaqtning o'zida bitmaplar uchun uchta turli ko'rinishdan foydalanadilar - bitmaplarning o'zlari, massivlar va bit ishlanmalari - va unumdorlikni oshirish va xotira sarfini minimallashtirish uchun ular o'rtasidagi muvozanat.
Siz eng mashhur ilovalarda gurkirab turgan bitmaplarni topishingiz mumkin. Turli xil dasturlash tillari uchun juda ko'p sonli ilovalar mavjud, jumladan Go uchun uchtadan ortiq dastur.
Yuqori kardinallik bilan kurashishimizga yordam beradigan yana bir yondashuv binning deb ataladi. Tasavvur qiling, sizda odamning balandligini ifodalovchi maydon bor. Balandlik - bu suzuvchi nuqtali raqam, lekin biz odamlar buni bunday deb o'ylamaymiz. Biz uchun 185,2 sm va 185,3 sm balandlikda farq yo'q.
Ma'lum bo'lishicha, biz o'xshash qiymatlarni 1 sm ichida guruhlarga guruhlashimiz mumkin.
Va agar biz juda kam odamning bo'yi 50 sm dan pastroq va 250 sm dan yuqori ekanligini bilsak, unda biz cheksiz kardinallikka ega bo'lgan maydonni 200 ga yaqin qiymatga ega bo'lgan maydonga aylantirishimiz mumkin.
Albatta, agar kerak bo'lsa, keyin qo'shimcha filtrlashni amalga oshirishimiz mumkin.
Yuqori tarmoqli kengligi muammosi
Bitmap indekslari bilan bog'liq keyingi muammo shundaki, ularni yangilash juda qimmatga tushishi mumkin.
Ma'lumotlar bazalari ma'lumotlarni yangilash imkoniyatiga ega bo'lishi kerak, biroq yuzlab boshqa so'rovlar ma'lumotlarni qidirmoqda. Bir vaqtning o'zida ma'lumotlarga kirish yoki boshqa almashish muammolari bilan bog'liq muammolarni oldini olish uchun bizga qulflar kerak. Va bitta katta qulf bo'lgan joyda muammo bor - qulflash tortishuvi, bu qulf bo'g'ozga aylanganda.
Ushbu muammoni sharding yoki versiya indekslari yordamida hal qilish yoki chetlab o'tish mumkin.
Sharding oddiy va taniqli narsadir. Bitmap indeksini boshqa har qanday ma'lumotlar kabi parchalashingiz mumkin. Bitta katta qulf o'rniga siz bir nechta kichik qulflarga ega bo'lasiz va shu bilan qulflash bahsidan xalos bo'lasiz.
Muammoni hal qilishning ikkinchi usuli - versiyalangan indekslardan foydalanish. Siz qidirish yoki o'qish uchun foydalanadigan indeksning bitta nusxasiga va yozish yoki yangilash uchun foydalanadigan nusxasiga ega bo'lishingiz mumkin. Va ma'lum bir vaqt oralig'ida bir marta (masalan, har 100 ms yoki 500 msda bir marta) siz ularni ko'paytirasiz va almashtirasiz. Albatta, bu yondashuv faqat sizning ilovangiz biroz kechikkan qidiruv indeksini boshqarishi mumkin bo'lgan hollarda qo'llaniladi.
Ushbu ikkita yondashuv bir vaqtning o'zida ishlatilishi mumkin: siz parchalangan versiya indeksiga ega bo'lishingiz mumkin.
Keyinchalik murakkab so'rovlar
Bitmap indekslari bilan bog'liq yakuniy muammo shundaki, ular span so'rovlari kabi murakkabroq so'rovlar uchun mos emas.
Haqiqatan ham, agar siz o'ylab ko'rsangiz, AND, OR, va hokazo kabi bit operatsiyalari "Menga kechasi 200 dan 300 dollargacha bo'lgan mehmonxonalarni ko'rsating" so'rovlari uchun juda mos kelmaydi.
Har bir dollar qiymati uchun natijalarni olish va ularni bitli OR operatsiyasi bilan birlashtirish sodda va juda aqlsiz yechim bo'ladi.
Bir oz yaxshiroq yechim guruhlashdan foydalanish bo'ladi. Masalan, 50 dollarlik guruhlarda. Bu bizning jarayonimizni 50 barobar tezlashtiradi.
Ammo bu turdagi so'rovlar uchun maxsus yaratilgan ko'rinish yordamida muammo ham osonlikcha hal qilinadi. Ilmiy maqolalarda u diapazon-kodlangan bitmaplar deb ataladi.
Ushbu tasvirda biz biron bir qiymat uchun (masalan, 200) faqat bitta bitni o'rnatmaymiz, balki bu qiymatni va hamma narsani yuqoriroq qilib qo'yamiz. 200 va undan yuqori. 300: 300 va undan yuqori uchun ham xuddi shunday. Va hokazo.
Ushbu taqdimotdan foydalanib, biz indeksni ikki marta aylanib o'tish orqali bunday qidiruv so'roviga javob berishimiz mumkin. Birinchidan, biz xona narxi kamroq yoki 300 dollar bo'lgan mehmonxonalar ro'yxatini olamiz, keyin esa undan kamroq yoki 199 dollar turadiganlarni olib tashlaymiz. Tayyor.
Siz hayron qolasiz, lekin bitmap indekslari yordamida hatto geoso'rovlar ham mumkin. Ayyorlik sizning koordinatangizni geometrik figura bilan o'rab turgan geometrik tasvirdan foydalanishdir. Masalan, Google'dan S2. Shaklni raqamlash mumkin bo'lgan uch yoki undan ortiq kesishuvchi chiziqlar shaklida tasvirlash mumkin bo'lishi kerak. Shunday qilib, biz geoqueryimizni "bo'shliq bo'ylab" (bu raqamlangan qatorlar bo'ylab) bir nechta so'rovlarga aylantirishimiz mumkin.
Tayyor echimlar
Umid qilamanki, sizni biroz qiziqtirdim va endi sizning arsenalingizda yana bir foydali vosita bor. Agar biror marta shunday qilish kerak bo'lsa, qaysi tomonga qarash kerakligini bilib olasiz.
Biroq, hamma ham noldan bitmap indekslarini yaratish uchun vaqt, sabr yoki resurslarga ega emas. Masalan, SIMD-dan foydalangan holda, ayniqsa ilg'or.
Yaxshiyamki, sizga yordam beradigan bir nechta tayyor echimlar mavjud.
Shovqinli bitmaplar
Birinchidan, men allaqachon aytib o'tgan o'sha gurkirab bitmaplar kutubxonasi bor. U barcha kerakli konteynerlarni va bit operatsiyalarini o'z ichiga oladi, siz to'liq bitmap indeksini yaratishingiz kerak bo'ladi.
Afsuski, hozirda Go ilovalarining hech biri SIMD-dan foydalanmaydi, ya'ni Go ilovalari, masalan, C ilovalariga qaraganda unumdorroq.
Pilosa
Sizga yordam beradigan yana bir mahsulot Pilosa DBMS bo'lib, unda faqat bitmap indekslari mavjud. Bu nisbatan yangi yechim, lekin u katta tezlikda qalblarni zabt etmoqda.
Pilosa ichkarida gurillagan bitmaplardan foydalanadi va sizga ulardan foydalanish imkoniyatini beradi, yuqorida aytib o'tganimning barchasini soddalashtiradi va tushuntiradi: guruhlash, diapazonda kodlangan bitmaplar, maydon tushunchasi va boshqalar.
Keling, sizga tanish bo'lgan savolga javob berish uchun Pilosa-dan foydalanish misolini tez ko'rib chiqaylik.
Misol oldingi ko'rgan narsangizga juda o'xshaydi. Biz Pilosa serveriga mijoz yaratamiz, indeks va kerakli maydonlarni yaratamiz, so'ngra maydonlarimizni tasodifiy ma'lumotlar bilan tasodifiy ma'lumotlar bilan to'ldiramiz va nihoyat, tanish so'rovni bajaramiz.
Shundan so'ng, biz "qimmat" maydonida EMAS dan foydalanamiz, so'ngra natijani (yoki VA uni) "teras" maydoni va "rezervasyonlar" maydoni bilan kesib o'tamiz. Va nihoyat, biz yakuniy natijaga erishamiz.
Umid qilamanki, yaqin kelajakda ushbu yangi turdagi indeks MySQL va PostgreSQL kabi ma'lumotlar bazalarida paydo bo'ladi - bitmap indekslari.
xulosa
Agar siz hali ham uxlamagan bo'lsangiz, rahmat. Vaqt cheklanganligi sababli ko'p mavzularga qisqacha to'xtalib o'tishga to'g'ri keldi, lekin umid qilamanki, nutq foydali va hatto motivatsiya bo'ldi.
Bitmap indekslari haqida bilish juda yaxshi, hatto sizga hozir kerak bo'lmasa ham. Ular sizning asboblar qutingizdagi boshqa vosita bo'lsin.
Biz Go uchun turli xil ishlash fokuslarini va Go kompilyatori hali unchalik yaxshi ishlamaydigan narsalarni ko'rib chiqdik. Lekin buni har bir Go dasturchisi bilishi uchun juda foydali.
Sizga aytmoqchi bo'lganim shu edi. Rahmat!
Manba: www.habr.com