оршил
Би энэ илтгэлийг Москвад болсон GopherCon Russia 2019 бага хурал дээр англи хэлээр, Нижний Новгород хотод болсон уулзалтын үеэр орос хэл дээр тавьсан. Бид битмап индексийн тухай ярьж байна - B модноос бага түгээмэл боловч сонирхолтой биш. Хуваалцах бага хуралд илтгэлүүдийг англи хэл дээр, орос хэл дээрх текстийн хуулбар.
Бид битмап индекс хэрхэн ажилладаг, хэзээ илүү сайн, бусад индексүүдээс муу, ямар тохиолдолд тэдгээрээс хамаагүй хурдан болохыг авч үзэх болно; Аль алдартай DBMS-ууд аль хэдийн bitmap индекстэй болохыг харцгаая; Go-д өөрийнхөөрөө бичихийг хичээцгээе. Мөн "амттаны хувьд" бид бэлэн номын сангуудыг ашиглан өөрийн маш хурдан мэргэшсэн мэдээллийн санг бий болгоно.
Миний бүтээлүүд танд хэрэгтэй, сонирхолтой байх болно гэдэгт би үнэхээр найдаж байна. Яв!
Танилцуулга
Сайн уу! Орой зургаан болж, бид бүгд маш их ядарч байна. Өгөгдлийн сангийн индексийн уйтгартай онолын талаар ярих сайхан цаг, тийм ээ? Санаа зоволтгүй, надад энд тэнд хоёр мөр эх код байх болно. 🙂
Бүх хошигнолуудыг эс тооцвол тайлан нь мэдээллээр дүүрэн бөгөөд бидэнд цаг зав бага байна. Ингээд эхэлцгээе.
Өнөөдөр би дараахь зүйлийн талаар ярих болно.
- индекс гэж юу вэ;
- битмап индекс гэж юу вэ;
- хаана ашигладаг, хаана, яагаад хэрэглэхгүй байгаа;
- Go дахь энгийн хэрэгжилт, хөрвүүлэгчтэй бага зэрэг тэмцэл;
- арай бага энгийн, гэхдээ Go assembler дээр илүү бүтээмжтэй хэрэгжүүлэх;
- bitmap индексүүдийн "асуудал";
- одоо байгаа хэрэгжүүлэлтүүд.
Тэгэхээр индекс гэж юу вэ?
Индекс нь үндсэн өгөгдлөөс гадна бидний хадгалж, шинэчилдэг тусдаа өгөгдлийн бүтэц юм. Энэ нь хайлтыг хурдасгахад ашиглагддаг. Индексгүйгээр хайлт хийхэд өгөгдлийг бүрэн судлах шаардлагатай (бүрэн скан гэж нэрлэдэг процесс) бөгөөд энэ процесс нь шугаман алгоритмын нарийн төвөгтэй байдаг. Гэхдээ мэдээллийн сан нь ихэвчлэн асар их хэмжээний өгөгдөл агуулдаг бөгөөд шугаман нарийн төвөгтэй байдал нь хэтэрхий удаан байдаг. Хамгийн тохиромжтой нь бид логарифм эсвэл тогтмолыг авах болно.
Энэ бол маш нарийн төвөгтэй сэдэв бөгөөд нарийн ширийн зүйлс, харилцан тохиролцоонуудаар дүүрэн боловч олон арван жилийн өгөгдлийн сангийн хөгжүүлэлт, судалгааг судалсны дараа мэдээллийн сангийн индексийг бий болгоход өргөн хэрэглэгддэг цөөн хэдэн арга байдаг гэдгийг хэлэхэд бэлэн байна.
Эхний арга нь хайлтын орон зайг эрэмбэлэн багасгаж, хайлтын орон зайг жижиг хэсгүүдэд хуваах явдал юм.
Бид үүнийг ихэвчлэн янз бүрийн мод ашиглан хийдэг. Жишээ нь таны шүүгээнд өөр өөр сэдэвт хуваагдсан жижиг хайрцаг бүхий материалын том хайрцаг байж болно. Хэрэв танд материал хэрэгтэй бол "Күүки" гэхээсээ илүү "Материал" гэсэн хайрцагнаас хайж олох байх, тийм ээ?
Хоёрдахь арга нь хүссэн элемент эсвэл бүлгийн элементүүдийг нэн даруй сонгох явдал юм. Бид үүнийг хэш зураг эсвэл урвуу индексээр хийдэг. Хэш газрын зургийг ашиглах нь өмнөх жишээтэй маш төстэй боловч таны шүүгээнд хайрцагны хайрцагны оронд олон тооны эцсийн эд зүйлс байгаа.
Гурав дахь арга нь хайх хэрэгцээг арилгах явдал юм. Бид үүнийг Bloom шүүлтүүр эсвэл хөхөө шүүлтүүр ашиглан хийдэг. Эхнийх нь хариултыг шууд өгч, таныг хайх шаардлагагүй болно.
Сүүлийн арга бол орчин үеийн техник хангамжийн бидэнд өгч буй бүх хүчийг бүрэн ашиглах явдал юм. Энэ бол бид битмап индекс дээр яг хийдэг зүйл юм. Тиймээ, тэдгээрийг ашиглахдаа бид заримдаа бүхэл бүтэн индексийг үзэх шаардлагатай байдаг, гэхдээ бид үүнийг маш үр дүнтэй хийдэг.
Миний хэлсэнчлэн өгөгдлийн сангийн индексийн сэдэв нь өргөн уудам бөгөөд буултаар дүүрэн байдаг. Энэ нь заримдаа бид хэд хэдэн аргыг нэгэн зэрэг ашиглаж болно гэсэн үг юм: хэрэв бид хайлтыг илүү хурдасгах шаардлагатай бол эсвэл бүх хайлтын төрлийг хамрах шаардлагатай бол.
Өнөөдөр би эдгээрийн хамгийн бага мэддэг арга болох bitmap indexes-ийн талаар ярих болно.
Би энэ сэдвээр хэн ярих вэ?
Би Badoo-д багийн ахлагчаар ажилладаг (магадгүй та манай бусад бүтээгдэхүүн болох Bumble-г илүү сайн мэддэг байх). Бид дэлхий даяар аль хэдийн 400 сая гаруй хэрэглэгчтэй бөгөөд тэдэнд хамгийн сайн тохирохыг сонгох олон функцтэй болсон. Бид үүнийг захиалгат үйлчилгээ, түүний дотор битмап индекс ашиглан хийдэг.
Тэгэхээр bitmap индекс гэж юу вэ?
Нэрнээс нь харахад битмап индексүүд нь хайлтын индексийг хэрэгжүүлэхийн тулд битийн зураг эсвэл битсетийг ашигладаг. Шувууны нүдээр харахад энэ индекс нь аливаа аж ахуйн нэгж (хүмүүс гэх мэт) болон тэдгээрийн шинж чанар, параметрүүдийг (нас, нүдний өнгө гэх мэт) төлөөлдөг нэг буюу хэд хэдэн ийм бит зураглалаас, мөн битийн үйлдлүүдийг (AND, OR, NOT) ашигладаг алгоритмаас бүрдэнэ. ) хайлтын асуулгад хариулна уу.
Битмап индексүүд нь үндсэн чанар багатай олон багана ("нүдний өнгө" эсвэл "гэр бүлийн байдал" гэх мэтийг "хотын төвөөс зай" гэх мэт асуултуудыг нэгтгэсэн хайлтууд байдаг тохиолдолд хамгийн тохиромжтой бөгөөд маш сайн ажилладаг гэж бидэнд хэлсэн. Гэхдээ би дараа нь тэд өндөр кардиналтай баганад сайн ажилладаг гэдгийг харуулах болно.
Bitmap индексийн хамгийн энгийн жишээг авч үзье.
Бидэнд хоёртын шинж чанартай Москвагийн ресторануудын жагсаалт байгаа гэж төсөөлөөд үз дээ:
- метроны ойролцоо;
- хувийн зогсоол байдаг;
- веранда байдаг (дэнжтэй);
- та ширээ захиалж болно (захиалгыг хүлээн авна);
- цагаан хоолтнуудад тохиромжтой (веганд ээлтэй);
- үнэтэй (үнэтэй).
Ресторан бүрт 0-ээс эхлэн дарааллын дугаар өгч, санах ойг 6 битийн зураглалд (шинж чанар бүрт нэг) хуваарилъя. Дараа нь ресторанд ийм өмч байгаа эсэхээс хамаарч бид эдгээр битмапуудыг бөглөнө. Хэрэв 4-р ресторан верандатай бол "верандатай" битийн зураг дээрх 4-р бит 1-ээр тохируулагдана (хэрэв веранда байхгүй бол 0-д).
Одоо бидэнд хамгийн энгийн битмап индекс байгаа бөгөөд бид үүнийг дараах асуултуудад хариулахад ашиглаж болно.
- “Надад цагаан хоолтонд ээлтэй ресторануудыг үзүүл”;
- "Надад ширээ захиалж болох верандатай хямд ресторануудыг үзүүл."
Хэрхэн? Ингээд харцгаая. Эхний хүсэлт нь маш энгийн. Бидний хийх ёстой зүйл бол "цагаан хоолтонд ээлтэй" битмапийг авч, түүнийг хэсэг нь ил гарсан рестораны жагсаалт болгон хувиргах явдал юм.
Хоёр дахь хүсэлт нь арай илүү төвөгтэй юм. Бид хямд ресторануудын жагсаалтыг авахын тулд "үнэтэй" битмап дээрх NOT bitmap-ийг ашиглах хэрэгтэй бөгөөд дараа нь "Би ширээ захиалж болох уу" гэсэн битмап, үр дүнд нь "веранда байна" гэсэн битийн зураглалыг авах шаардлагатай. Үүссэн битмап нь бидний бүх шалгуурыг хангасан байгууллагуудын жагсаалтыг агуулна. Энэ жишээнд энэ нь зөвхөн Юностын ресторан юм.
Үүнд маш олон онол бий, гэхдээ санаа зовох хэрэггүй, бид удахгүй кодыг харах болно.
Bitmap индексийг хаана ашигладаг вэ?
Хэрэв та Google-ийн битмап индексийг хайж байгаа бол хариултуудын 90% нь ямар нэг байдлаар Oracle DB-тэй холбоотой байх болно. Гэхдээ бусад DBMS-ууд ч гэсэн ийм сайхан зүйлийг дэмждэг байх, тийм үү? Үнэхээр биш.
Гол сэжигтнүүдийн жагсаалтыг авч үзье.
MySQL нь битмап индексийг хараахан дэмждэггүй боловч энэ сонголтыг нэмэхийг санал болгож байна ().
PostgreSQL нь битмап индексийг дэмждэггүй боловч хайлтын үр дүнг бусад олон индекст нэгтгэхийн тулд энгийн битмап болон битийн үйлдлүүдийг ашигладаг.
Tarantool нь битсет индекстэй бөгөөд тэдгээр дээр энгийн хайлтуудыг дэмждэг.
Redis нь энгийн бит талбаруудтай) тэдгээрийг хайх чадваргүй.
MongoDB нь битмап индексийг хараахан дэмжээгүй байгаа ч энэ сонголтыг нэмэхийг санал болгож байна.
Elasticsearch нь дотооддоо битмап ашигладаг).
- Гэтэл манай гэрт шинэ хөрш гарч ирэв: Пилоза. Энэ бол Go-д бичигдсэн шинэ хамааралгүй мэдээллийн сан юм. Энэ нь зөвхөн битмап индексийг агуулсан бөгөөд бүх зүйлийг тэдгээрт үндэслэдэг. Бид энэ талаар бага зэрэг дараа ярих болно.
Go-д хэрэгжүүлэх
Гэхдээ яагаад bitmap индексийг маш ховор ашигладаг вэ? Энэ асуултад хариулахын өмнө би Go программ дээр маш энгийн битмап индексийг хэрхэн хэрэгжүүлэхийг харуулахыг хүсч байна.
Bitmap нь үндсэндээ зөвхөн өгөгдлийн хэсэг юм. Go-д үүний тулд байт зүсмэлүүдийг ашиглая.
Бидэнд нэг рестораны онцлогт зориулсан нэг бит зураглал байдаг бөгөөд бит зураг дээрх бит бүр нь тухайн ресторанд ийм өмч байгаа эсэхийг харуулдаг.
Бидэнд хоёр туслах функц хэрэгтэй болно. Нэг нь бидний битмапуудыг санамсаргүй мэдээллээр дүүргэхэд ашиглагдана. Санамсаргүй, гэхдээ зоогийн газар өмч бүртэй байх магадлалтай. Жишээлбэл, Москвад ширээ захиалах боломжгүй цөөхөн ресторан байдаг гэдэгт би итгэдэг бөгөөд эдгээр газруудын 20 орчим хувь нь цагаан хоолтнуудад тохиромжтой гэж би бодож байна.
Хоёрдахь функц нь битийн зургийг рестораны жагсаалт болгон хувиргах болно.
"Надад хашааны талбайтай, захиалга өгөх боломжтой хямд ресторануудыг үзүүлээрэй" гэсэн асуултад хариулахын тулд бидэнд NOT болон AND гэсэн хоёр бит үйлдэл хэрэгтэй.
Бид илүү төвөгтэй БА БИШ операторыг ашигласнаар кодоо бага зэрэг хялбарчилж чадна.
Бид эдгээр үйлдлүүд тус бүрийн функцуудтай. Хоёулаа зүсмэлүүдээр дамжиж, тус бүрээс тохирох элементүүдийг авч, тэдгээрийг бага зэрэг үйлдэлтэй хослуулж, үр дүнг үүссэн зүсмэл дээр хийнэ.
Одоо бид хайлтын асуулгад хариулахын тулд бит зураг болон функцуудыг ашиглаж болно.
Хэдийгээр функцууд нь маш энгийн бөгөөд функцийг дуудах болгонд шинээр үүссэн зүсмэлийг буцааж өгөхгүй байснаар бид маш их мөнгө хэмнэсэн ч гүйцэтгэл тийм ч өндөр биш юм.
pprof программыг ашиглан бага зэрэг профайл хийсний дараа Go хөрвүүлэгчид маш энгийн боловч маш чухал оновчлол дутуу байгааг анзаарсан: функцийг оруулах.
Гол нь Go хөрвүүлэгч нь зүсмэлүүдээр дамждаг гогцооноос айдаг бөгөөд ийм гогцоо агуулсан мөрийн функцүүдээс эрс татгалздаг.
Гэхдээ би айхгүй бөгөөд хуучин үеийнх шиг давталтын оронд goto ашиглан хөрвүүлэгчийг хуурч чадна.
Таны харж байгаагаар хөрвүүлэгч нь бидний функцийг баяртайгаар оруулах болно! Үүний үр дүнд бид ойролцоогоор 2 микросекунд хэмнэж чадсан. Муугүй шүү!
Хэрэв та угсралтын гаралтыг сайтар ажиглавал хоёр дахь саад тотгорыг харахад хялбар байдаг. Хөрвүүлэгч нь бидний хамгийн халуун давталт дотор зүсмэлийн хилийн шалгалтыг нэмсэн. Гол нь Go бол аюулгүй хэл, хөрвүүлэгч миний гурван аргумент (гурван зүсмэл) өөр өөр хэмжээтэй байна гэж айдаг. Эцсийн эцэст, дараа нь буфер халих гэж нэрлэгддэг онолын боломж бий болно.
Бүх зүсмэлүүд ижил хэмжээтэй гэдгийг харуулж хөрвүүлэгчийг тайвшруулцгаая. Бид үүнийг функцийнхээ эхэнд энгийн чек нэмснээр хийж болно.
Үүнийг хараад хөрвүүлэгч чекийг баяртайгаар алгасаж, бид дахин 500 наносекунд хэмнэнэ.
Том бухнууд
За, бид энгийн хэрэгжүүлэлтийнхээ үр дүнд зарим гүйцэтгэлийг шахаж чадсан боловч энэ үр дүн нь одоогийн техник хангамжтай харьцуулахад хамаагүй муу байна.
Бидний хийдэг зүйл бол үндсэн битийн үйлдлүүд бөгөөд манай процессорууд тэдгээрийг маш үр дүнтэй гүйцэтгэдэг. Гэвч харамсалтай нь бид процессороо маш жижиг ажлаар "тэжээдэг". Манай функцууд үйлдлүүдийг байт байтаар гүйцэтгэдэг. Бид UInt8 зүсмэлүүдийг ашиглан 64 байт хэмжээтэй хэсгүүдтэй ажиллахын тулд кодоо хялбархан өөрчилж чадна.
Таны харж байгаагаар энэ жижиг өөрчлөлт нь багцын хэмжээг найм дахин нэмэгдүүлснээр манай хөтөлбөрийг найман удаа хурдасгасан. Олз нь шугаман гэж хэлж болно.
Ассемблер дээр хэрэгжүүлэх
Гэхдээ энэ бол төгсгөл биш. Манай процессорууд 16, 32, бүр 64 байт хэмжээтэй хэсгүүдтэй ажиллах боломжтой. Ийм "өргөн" үйлдлүүдийг нэг заавар олон өгөгдөл (SIMD; нэг заавар, олон өгөгдөл) гэж нэрлэдэг бөгөөд кодыг ийм үйлдлийг ашиглахын тулд хувиргах үйл явцыг векторжуулалт гэж нэрлэдэг.
Харамсалтай нь Go хөрвүүлэгч нь векторжуулалтын хувьд маш сайн биш юм. Одоогоор Go кодыг векторжуулах цорын ганц арга бол Go ассемблер ашиглан эдгээр үйлдлүүдийг гараар авч, оруулах явдал юм.
Го ассемблер бол хачин араатан юм. Ассемблер хэл нь таны бичиж буй компьютерийн бүтэцтэй нягт холбоотой гэдгийг та мэдэх байх, гэхдээ Go-д тийм биш юм. Go ассемблер нь IRL (завсрын төлөөллийн хэл) эсвэл завсрын хэлтэй төстэй: энэ нь бараг платформоос хамааралгүй юм. Роб Пайк гайхалтай тоглолт үзүүлсэн Энэ сэдвээр хэдэн жилийн өмнө Денвер дэх GopherCon дээр.
Нэмж дурдахад Go нь нийтээр хүлээн зөвшөөрөгдсөн AT&T болон Intel форматуудаас ялгаатай Plan 9 форматыг ашигладаг.
Go assembler-ийг гараар бичих нь тийм ч хөгжилтэй биш гэж хэлж болно.
Гэхдээ аз болоход, Go assembler-ийг бичихэд туслах хоёр дээд түвшний хэрэгсэл байдаг: PeachPy болон avo. Хоёр хэрэгсэл хоёулаа Python болон Go дээр бичигдсэн дээд түвшний кодоос Go ассемблерийг үүсгэдэг.
Эдгээр хэрэгслүүд нь регистрийн хуваарилалт, бичих гогцоо гэх мэт зүйлсийг хялбаршуулж, ерөнхийдөө Go дахь угсралтын програмчлалын ертөнцөд орох үйл явцыг хялбаршуулдаг.
Бид avo-г ашиглах тул манай программууд бараг ердийн Go програмууд байх болно.
Avo програмын хамгийн энгийн жишээ иймэрхүү харагдаж байна. Бидэнд үндсэн() функц байгаа бөгөөд энэ нь Add() функцийг дотроо тодорхойлдог бөгөөд үүний утга нь хоёр тоог нэмэх явдал юм. Параметрүүдийг нэрээр нь авч, үнэ төлбөргүй, тохиромжтой процессорын регистрийн аль нэгийг авах туслах функцууд энд байна. Процессорын үйлдэл бүр нь ADDQ-д үзүүлсэн шиг avo дээр харгалзах функцтэй байдаг. Эцэст нь бид үүссэн утгыг хадгалах туслах функцийг харж байна.
gogener гэж дуудснаар бид програмыг avo дээр ажиллуулах ба үр дүнд нь хоёр файл үүснэ:
- Go assembler дээр гарсан кодтой add.s;
- stub.go хоёр ертөнцийг холбох функцийн толгойтой: Go and assembler.
Одоо бид avo юу хийдгийг, хэрхэн хийдэгийг олж мэдсэнийхээ дараа өөрсдийн функцуудыг харцгаая. Би функцүүдийн скаляр болон вектор (SIMD) хувилбаруудыг хоёуланг нь хэрэгжүүлсэн.
Эхлээд скаляр хувилбаруудыг харцгаая.
Өмнөх жишээний нэгэн адил бид үнэ төлбөргүй, хүчинтэй ерөнхий зориулалтын бүртгэлийг хүсч байгаа тул аргументуудын офсет болон хэмжээг тооцоолох шаардлагагүй. avo энэ бүхнийг бидний төлөө хийдэг.
Бид гүйцэтгэлийг сайжруулах, Go хөрвүүлэгчийг хуурахын тулд шошго болон goto (эсвэл үсрэлт) ашигладаг байсан бол одоо бид үүнийг эхнээс нь хийж байна. Гол нь мөчлөг бол дээд түвшний ойлголт юм. Ассемблер дээр бид зөвхөн шошго, үсрэлттэй байдаг.
Үлдсэн код нь аль хэдийн танил, ойлгомжтой байх ёстой. Бид шошго, үсрэлт бүхий гогцоог дуурайж, хоёр зүсмэлээсээ жижиг өгөгдлийн хэсгийг авч, тэдгээрийг битийн үйлдлээр нэгтгэж (энэ тохиолдолд БИШ) дараа нь үр дүнг үүссэн зүсмэлүүд рүү оруулна. Бүгд.
Эцсийн ассемблерийн код иймэрхүү харагдаж байна. Бид офсет болон хэмжээг тооцоолох (ногооноор тодруулсан) эсвэл ашигласан бүртгэлийг (улаан өнгөөр тодруулсан) хянах шаардлагагүй байсан.
Хэрэв бид ассемблер хэлний хэрэгжилтийн гүйцэтгэлийг Go дахь хамгийн сайн хэрэгжүүлэлтийн гүйцэтгэлтэй харьцуулж үзвэл энэ нь адилхан болохыг харах болно. Мөн энэ нь хүлээгдэж байна. Эцсийн эцэст бид ямар ч онцгой зүйл хийгээгүй - бид зүгээр л Go хөрвүүлэгчийн хийх зүйлийг хуулбарласан.
Харамсалтай нь бид хөрвүүлэгчийг ассемблер хэлээр бичсэн функцүүдээ оруулахыг албадах боломжгүй. Go хөрвүүлэгч нь одоогоор ийм функцгүй байгаа ч үүнийг нэмэх хүсэлт нэлээд удсан.
Тийм ч учраас ассемблер хэл дээрх жижиг функцүүдээс ямар ч ашиг тус хүртэх боломжгүй юм. Бид том функц бичих, эсвэл шинэ математик/бит багц ашиглах, эсвэл ассемблер хэлийг алгасах хэрэгтэй.
Одоо функцийнхээ вектор хувилбаруудыг харцгаая.
Энэ жишээний хувьд би AVX2 ашиглахаар шийдсэн тул бид 32 байт хэсгүүд дээр ажилладаг үйлдлүүдийг ашиглах болно. Кодын бүтэц нь скаляр хувилбартай маш төстэй: параметрүүдийг ачаалах, үнэгүй хуваалцсан бүртгэл хүсэх гэх мэт.
Нэг шинэлэг зүйл бол илүү өргөн вектор үйлдлүүд нь тусгай өргөн регистрүүдийг ашигладаг явдал юм. 32 байт хэсгүүдийн хувьд эдгээр нь Y-ийн угтвартай регистрүүд юм. Ийм учраас та кодонд YMM() функцийг харж байна. Хэрэв би AVX-512-г 64 битийн хэсгүүдтэй ашиглаж байсан бол угтвар нь Z байх болно.
Хоёр дахь шинэлэг зүйл бол би давталтыг задлах гэж нэрлэгддэг оновчлолыг ашиглахаар шийдсэн бөгөөд энэ нь давталтын эхэнд шилжихээс өмнө XNUMX давталтын үйлдлийг гараар хийх гэсэн үг юм. Энэхүү оновчлол нь кодын салбаруудын тоог багасгаж, үнэгүй бүртгэлийн тоогоор хязгаарлагддаг.
За, гүйцэтгэлийн талаар юу хэлэх вэ? Тэр үзэсгэлэнтэй! Шилдэг Go шийдэлтэй харьцуулахад бид долоон дахин хурдасгасан. Гайхалтай, тийм үү?
Гэхдээ энэ хэрэгжилтийг ч гэсэн асуулга төлөвлөгчийн хувьд AVX-512, урьдчилан татаж авах эсвэл JIT (цаг хугацаанд нь хөрвүүлэгч) ашиглан хурдасгах боломжтой. Гэхдээ энэ бол мэдээж тусдаа тайлангийн сэдэв юм.
Битмап индекстэй холбоотой асуудлууд
Одоо бид Go программ дээрх битмап индексийн энгийн хэрэгжилт болон ассемблер хэл дээр илүү үр дүнтэй хувилбарыг аль хэдийн авч үзсэн тул эцэст нь битмап индекс яагаад тийм ховор хэрэглэгддэг талаар ярилцъя.
Хуучин нийтлэлүүд нь битмап индекстэй холбоотой гурван асуудлыг дурдсан боловч шинэ баримтууд болон би тэдгээр нь хамааралгүй болсон гэж маргаж байна. Бид эдгээр асуудал тус бүрийг гүнзгийрүүлэхгүй, харин өнгөцхөн харах болно.
Өндөр кардинал байдлын асуудал
Тиймээс, битмап индексүүд нь зөвхөн үндсэн чанар багатай, өөрөөр хэлбэл цөөн утгатай (жишээ нь, хүйс эсвэл нүдний өнгө) талбаруудад тохиромжтой гэж бидэнд хэлсэн бөгөөд шалтгаан нь эдгээр талбаруудын ердийн дүрслэл (нэг утга тутамд бит) өндөр кардиналтай тохиолдолд хэт их зай эзэлнэ, үүнээс гадна эдгээр битмап индексүүд муу (ховор) бөглөгдөнө.
Заримдаа бид тоонуудыг илэрхийлэхэд ашигладаг стандарт гэх мэт өөр дүрслэлийг ашиглаж болно. Гэхдээ шахалтын алгоритмууд гарч ирснээр бүх зүйл өөрчлөгдсөн. Сүүлийн хэдэн арван жилийн хугацаанд эрдэмтэд, судлаачид бит зурагт зориулсан олон тооны шахалтын алгоритмуудыг гаргаж ирсэн. Тэдний гол давуу тал нь битийн үйлдлийг гүйцэтгэхийн тулд битийн зураглалыг задлах шаардлагагүй - бид шахсан битийн зураг дээр шууд битийн үйлдлийг гүйцэтгэх боломжтой.
Сүүлийн үед шуугиантай битмап гэх мэт эрлийз аргууд гарч ирж байна. Тэд битмапийн хувьд гурван өөр дүрслэлийг нэгэн зэрэг ашигладаг - битийн зураглал, массив ба битийн гүйлт гэж нэрлэгддэг - гүйцэтгэлийг нэмэгдүүлэх, санах ойн хэрэглээг багасгахын тулд тэдгээрийн хооронд тэнцвэрийг бий болгодог.
Та хамгийн алдартай програмуудаас архиран битмапуудыг олох боломжтой. Go-д зориулсан гурваас дээш хувилбарыг багтаасан олон төрлийн програмчлалын хэлэнд зориулсан асар олон тооны хэрэгжүүлэлтүүд аль хэдийн байгаа.
Өндөр кардиналтай тэмцэхэд туслах өөр нэг аргыг биннинг гэж нэрлэдэг. Танд хүний өндрийг харуулсан талбар байна гэж төсөөлөөд үз дээ. Өндөр бол хөвөгч цэгийн тоо боловч хүмүүс бид үүнийг тэгж боддоггүй. Бидний хувьд 185,2 см, 185,3 см өндөр хоёрын хооронд ялгаа байхгүй.
Бид ижил төстэй утгыг 1 см-ийн дотор бүлэгт хувааж болно.
Хэрэв бид маш цөөхөн хүн 50 см-ээс намхан, 250 см-ээс өндөр байдаг гэдгийг мэддэг бол бид үндсэндээ хязгааргүй кардиналтай талбарыг 200 орчим утга бүхий талбар болгон хувиргаж чадна.
Мэдээжийн хэрэг, хэрэв шаардлагатай бол бид дараа нь нэмэлт шүүлтүүр хийх боломжтой.
Өндөр зурвасын өргөнтэй холбоотой асуудал
Битмап индексүүдийн дараагийн асуудал бол тэдгээрийг шинэчлэх нь маш үнэтэй байх явдал юм.
Өгөгдлийн сан нь өгөгдлийг шинэчлэх боломжтой байх ёстой бөгөөд энэ нь олон зуун өөр асуулга өгөгдлийг хайж байх үед. Өгөгдөл зэрэгт нэвтрэх болон бусад хуваалцах асуудлаас зайлсхийхийн тулд бидэнд түгжээ хэрэгтэй. Нэг том цоож байгаа газарт асуудал үүсдэг - түгжээний маргаан, энэ түгжээ нь гацаа болж хувирдаг.
Шардинг ашиглах эсвэл хувилбарын индексийг ашиглан энэ асуудлыг шийдэж эсвэл тойрч болно.
Хуваах нь энгийн бөгөөд сайн мэддэг зүйл юм. Та бусад өгөгдлийн нэгэн адил битмап индексийг хувааж болно. Нэг том цоожны оронд та олон жижиг цоож авах бөгөөд ингэснээр түгжээний маргаанаас ангижрах болно.
Асуудлыг шийдэх хоёр дахь арга бол хувилбарын индексийг ашиглах явдал юм. Та хайлтын болон уншихад ашигладаг индексийн нэг хувийг, бичих эсвэл шинэчлэхэд ашигладаг нэг хувийг авах боломжтой. Мөн тодорхой хугацаанд нэг удаа (жишээлбэл, 100 мс эсвэл 500 мс тутамд нэг удаа) та тэдгээрийг хуулбарлаж, солино. Мэдээжийн хэрэг, энэ арга нь таны програм бага зэрэг хоцрогдсон хайлтын индекстэй ажиллах боломжтой тохиолдолд л хэрэглэгдэх болно.
Эдгээр хоёр аргыг нэгэн зэрэг ашиглаж болно: та хуваасан хувилбартай индекстэй байж болно.
Илүү төвөгтэй асуултууд
Битмап индексүүдийн эцсийн асуудал бол тэдгээр нь span асуулга гэх мэт илүү төвөгтэй төрлийн асуулгад тохиромжгүй гэж бидэнд хэлдэг.
Үнэхээр, хэрэв та бодож байгаа бол AND, OR гэх мэт битийн үйлдлүүд нь "Надад шөнийн 200-300 долларын өрөөний үнэ бүхий зочид буудлуудыг харуул" гэсэн асуултанд тийм ч тохиромжтой биш юм.
Долларын үнэ цэнэ тус бүрийн үр дүнг авч, тэдгээрийг битийн OR үйлдлээр нэгтгэх нь гэнэн бөгөөд маш ухаалаг бус шийдэл байх болно.
Бага зэрэг илүү сайн шийдэл бол бүлэглэлийг ашиглах явдал юм. Жишээлбэл, 50 доллараар бүлгээрээ. Энэ нь бидний үйл явцыг 50 дахин хурдасгах болно.
Гэхдээ энэ төрлийн хүсэлтэд тусгайлан үүсгэсэн харагдац ашиглан асуудлыг хялбархан шийддэг. Шинжлэх ухааны бүтээлүүдэд үүнийг муж-кодлогдсон битмап гэж нэрлэдэг.
Энэ дүрслэлд бид ямар нэг утгыг (жишээ нь, 200) нэг битээр тогтоодоггүй, харин энэ утгыг болон бүх зүйлийг илүү өндөр болгож өгдөг. 200 ба түүнээс дээш. 300: 300 ба түүнээс дээш хувьд ч мөн адил. гэх мэт.
Энэ дүрслэлийг ашигласнаар бид индексийг хоёр удаа давснаар ийм төрлийн хайлтын асуулгад хариулж чадна. Эхлээд бид өрөө нь 300 доллараас бага үнэтэй зочид буудлуудын жагсаалтыг гаргаж, дараа нь 199 доллараас бага үнэтэй зочид буудлуудыг хасах болно. Бэлэн.
Та гайхах болно, гэхдээ битмап индексийг ашиглан газарзүйн судалгаа хийх боломжтой. Гол арга бол координатаа геометрийн дүрсээр хүрээлэх геометрийн дүрслэлийг ашиглах явдал юм. Жишээлбэл, Google-ийн S2. Зураг нь дугаарлаж болох гурав ба түүнээс дээш огтлолцсон шугам хэлбэрээр дүрслэх боломжтой байх ёстой. Ингэснээр бид геокеригээ "цоорхойн дагуу" (эдгээр дугаарлагдсан шугамын дагуу) хэд хэдэн асуулга болгон хувиргаж чадна.
Бэлэн шийдэл
Би чамайг бага зэрэг сонирхсон гэж найдаж байна, одоо та өөрийн зэвсэглэлд өөр нэг хэрэгтэй хэрэгсэлтэй болсон. Хэрэв та ийм зүйл хийх шаардлагатай бол аль талаас нь харахаа мэдэх болно.
Гэсэн хэдий ч хүн бүр эхнээс нь битмап индекс үүсгэх цаг, тэвчээр, нөөцтэй байдаггүй. Ялангуяа илүү дэвшилтэт, жишээ нь SIMD ашигладаг.
Аз болоход танд туслах хэд хэдэн бэлэн шийдэл байна.
Архирах битмапууд
Нэгдүгээрт, миний аль хэдийн ярьсан битмапийн номын сан байдаг. Энэ нь танд бүрэн хэмжээний битмап индекс хийхэд шаардлагатай бүх контейнерууд болон битийн үйлдлүүдийг агуулдаг.
Харамсалтай нь, одоогоор Go-ийн аль нь ч SIMD-г ашигладаггүй бөгөөд энэ нь Go-ийн хэрэгжүүлэлт нь C-ээс бага гүйцэтгэлтэй гэсэн үг юм.
Пилоза
Танд туслах өөр нэг бүтээгдэхүүн бол Pilosa DBMS бөгөөд үнэндээ зөвхөн битмап индекстэй. Энэ бол харьцангуй шинэ шийдэл боловч асар хурдтайгаар хүмүүсийн зүрх сэтгэлийг байлдан дагуулж байна.
Пилоса нь дотооддоо шуугиантай битмап ашигладаг бөгөөд тэдгээрийг ашиглах боломжийг танд олгож, дээр дурдсан бүх зүйлийг хялбарчилж, тайлбарлаж өгдөг: бүлэглэх, мужаар кодлогдсон битмап, талбарын тухай ойлголт гэх мэт.
Таны мэддэг асуултанд хариулахын тулд Pilosa-г ашиглах жишээг хурдан харцгаая.
Жишээ нь таны өмнө харсан зүйлтэй маш төстэй юм. Бид Pilosa серверт үйлчлүүлэгч үүсгэж, индекс болон шаардлагатай талбаруудыг үүсгэж, дараа нь талбаруудыг магадлал бүхий санамсаргүй мэдээллээр дүүргэж, эцэст нь танил асуулгыг гүйцэтгэдэг.
Үүний дараа бид "үнэтэй" талбар дээр NOT-г ашиглаад дараа нь үр дүнг (эсвэл БА үүнийг) "дэнж" талбар болон "захиалга" талбартай огтолно. Эцэст нь бид эцсийн үр дүнд хүрнэ.
Ойрын ирээдүйд энэ шинэ төрлийн индекс нь MySQL болон PostgreSQL - bitmap indexes зэрэг DBMS-д гарч ирнэ гэдэгт би үнэхээр найдаж байна.
дүгнэлт
Хэрэв та унтаж амжаагүй бол баярлалаа. Цаг хугацаа хязгаарлагдмал байсан тул олон сэдвийг товчхон хөндөх шаардлагатай болсон ч энэ яриа ашигтай, магадгүй урам зориг өгсөн байх гэж найдаж байна.
Bitmap индексүүд нь танд яг одоо хэрэггүй байсан ч мэдэхэд тохиромжтой. Тэдгээрийг таны хэрэгслийн хайрцагт өөр хэрэгсэл болго.
Бид Go-д зориулсан янз бүрийн гүйцэтгэлийн заль мэх, Go хөрвүүлэгчийн хараахан тийм ч сайн зохицуулаагүй зүйлсийг авч үзсэн. Гэхдээ энэ нь Go програмист бүрт мэдэхэд үнэхээр хэрэгтэй зүйл юм.
Үүнийг л чамд хэлэхийг хүссэн юм. Баярлалаа!
Эх сурвалж: www.habr.com