پیژندنه
ما دا راپور په انګلیسي ژبه په مسکو کې د ګوفر کان روسیه 2019 کنفرانس کې او په روسیه کې په نزني نوګورډ کې په یوه ناسته کې ورکړ. موږ د بټ میپ شاخص په اړه خبرې کوو - د B - ونې په پرتله لږ عام، مګر لږ په زړه پورې. شریکول په کنفرانس کې ویناوې په انګلیسي ژبه او متنونه په روسي ژبه.
موږ به وګورو چې د بټ میپ شاخص څنګه کار کوي، کله غوره وي، کله د نورو شاخصونو په پرتله خراب وي، او په کوم حالت کې دا د دوی په پرتله خورا ګړندی وي؛ راځئ وګورو چې کوم مشهور DBMSs دمخه د بټ میپ شاخصونه لري؛ راځئ هڅه وکړو چې خپل ځان په Go کې ولیکئ. او "د ډیزرټ لپاره" موږ به چمتو شوي کتابتونونه وکاروو ترڅو خپل خورا ګړندی ځانګړي ډیټابیس جوړ کړو.
زه واقعیا امید لرم چې زما کارونه به ستاسو لپاره ګټور او په زړه پوري وي. لاړ شه!
پېژندنه
سلام و ټولو ته! د ماښام شپږ بجې دي او موږ ټول ستړي یو. د بورینګ ډیټابیس شاخص تیوري په اړه د خبرو کولو لپاره ښه وخت ، سمه ده؟ اندیښنه مه کوئ، زه به دلته او هلته د سرچینې کوډ څو کرښې ولرم. 🙂
ټولې ټوکې په څنګ کې، راپور له معلوماتو ډک دی، او موږ ډیر وخت نه لرو. نو راځئ چې پیل وکړو.
نن زه به د لاندې په اړه خبرې وکړم:
- شاخصونه څه دي؛
- د بټ میپ شاخص څه شی دی؛
- چیرته کارول کیږي او چیرته نه کارول کیږي او ولې؛
- په Go کې ساده پلي کول او د کمپیلر سره لږ مبارزه؛
- یو څه لږ ساده ، مګر په Go اسمبلر کې خورا ډیر ګټور پلي کول؛
- د بټ میپ شاخصونو "ستونزې"؛
- موجوده تطبیقونه.
نو شاخصونه څه دي؟
شاخص د معلوماتو جلا جوړښت دی چې موږ د اصلي معلوماتو سربیره ساتو او تازه کوو. دا د لټون چټکولو لپاره کارول کیږي. د شاخصونو پرته، لټون به په بشپړ ډول د معلوماتو له لارې تیرولو ته اړتیا ولري (یو بهیر چې بشپړ سکین بلل کیږي)، او دا پروسه خطي الګوریتمیک پیچلتیا لري. مګر ډیټابیسونه معمولا د ډیټا لوی مقدار لري او خطي پیچلتیا خورا ورو ده. په مثالي توګه، موږ به یو لوګاریتمیک یا ثابت ترلاسه کړو.
دا یوه ډیره پیچلې موضوع ده، چې د فرعياتو او تجارتونو څخه ډکه ده، مګر د لسیزو ډیټابیس پراختیا او څیړنې ته په کتلو سره، زه غواړم ووایم چې د ډیټابیس شاخصونو رامینځته کولو لپاره یوازې یو څو پراخه کارول شوي لارې شتون لري.
لومړۍ طریقه دا ده چې په ترتیب سره د لټون ځای کم کړي، د لټون ځای په کوچنیو برخو ویشل.
موږ معمولا دا د مختلف ډوله ونو په کارولو سره ترسره کوو. یو مثال به ستاسو په المارۍ کې د موادو لوی بکس وي چې د موادو کوچني بکسونه لري چې په مختلفو موضوعاتو ویشل شوي. که تاسو موادو ته اړتیا لرئ، نو تاسو به شاید دوی په یوه بکس کې وپلټئ چې "توکي" وايي، نه دا چې "کوکیز" وايي؟
دویمه لاره دا ده چې سمدلاسه مطلوب عنصر یا د عناصرو ګروپ غوره کړئ. موږ دا د هش نقشې یا ریورس شاخصونو کې کوو. د هش نقشې کارول د تیرو مثالونو سره ورته دي، مګر د بکسونو د بکس پرځای، تاسو په خپل المارۍ کې د وروستي توکو کوچني بکسونه لرئ.
دریمه طریقه د لټون اړتیا له منځه وړل دي. موږ دا د بلوم فلټرونو یا کوکو فلټرونو په کارولو سره ترسره کوو. لومړی یې سمدستي ځواب درکوي، تاسو د لټون کولو څخه وژغورئ.
وروستنۍ لاره دا ده چې د ټول ځواک څخه بشپړه ګټه پورته کړئ چې عصري هارډویر موږ ته راکوي. دا په حقیقت کې هغه څه دي چې موږ یې د بټ میپ شاخصونو کې کوو. هو، کله چې د دوی کارول موږ ځینې وختونه اړتیا لرو چې ټول شاخص ته لاړ شو، مګر موږ دا په خورا اغیزمنه توګه ترسره کوو.
لکه څنګه چې ما وویل، د ډیټابیس شاخصونو موضوع پراخه او له جوړجاړي څخه ډکه ده. دا پدې مانا ده چې ځینې وختونه موږ کولی شو په ورته وخت کې څو طریقې وکاروو: که موږ اړتیا لرو چې لټون نور هم ګړندی کړو، یا که موږ د ټولو ممکنه لټون ډولونو پوښلو ته اړتیا ولرو.
نن زه به د دې لږترلږه پیژندل شوي چلند په اړه وغږیږم - bitmap indexes.
زه څوک یم چې په دې موضوع خبرې وکړم؟
زه په بدو کې د ټیم مشر په توګه کار کوم (شاید تاسو زموږ د بل محصول ، بومبل سره ډیر آشنا یاست). موږ دمخه په ټوله نړۍ کې له 400 ملیون څخه ډیر کاروونکي لرو او ډیری ځانګړتیاوې چې د دوی لپاره غوره لوبه غوره کوي. موږ دا د ګمرکي خدماتو په کارولو سره ترسره کوو، په شمول د بټ میپ شاخصونه.
نو د بټ میپ شاخص څه شی دی؟
د بټ میپ شاخصونه ، لکه څنګه چې نوم وړاندیز کوي ، د لټون شاخص پلي کولو لپاره بټ میپ یا بټ سیټونه وکاروئ. د مرغیو د سترګو له نظره، دا شاخص د یو یا ډیرو داسې بټ میپونو څخه جوړ دی چې د هرې ادارې استازیتوب کوي (لکه خلک) او د دوی ملکیتونه یا پیرامیټونه (عمر، د سترګو رنګ، او نور)، او د بټ عملیاتو په کارولو سره یو الګوریتم (AND, OR, NOT) د لټون پوښتنې ته د ځواب ویلو لپاره.
موږ ته ویل شوي چې د بټ میپ شاخصونه د هغو قضیو لپاره خورا مناسب او خورا غوره دي چیرې چې لټونونه شتون لري چې د ډیری ټیټ کارتینالیټي کالمونو کې پوښتنې سره یوځای کوي (فکر وکړئ "د سترګو رنګ" یا "دواړه حالت" په مقابل کې د "ښار له مرکز څخه فاصله"). مګر زه به وروسته وښیم چې دوی د لوړ کارتینالیټي کالمونو لپاره هم ښه کار کوي.
راځئ چې د بټ میپ شاخص ترټولو ساده مثال وګورو.
تصور وکړئ چې موږ د ماسکو رستورانتونو لیست لرو د بائنری ملکیتونو سره د دې په څیر:
- میټرو ته نږدې؛
- شخصي پارکینګ شتون لري؛
- دلته یو برنډه شتون لري (چت لري)؛
- تاسو کولی شئ یو میز خوندي کړئ (ریزرویشنونه مني)؛
- د سبزیجاتو لپاره مناسب (د سبزیجاتو دوستانه)؛
- ګران (ګرانه).
راځئ چې هر رستورانت ته د ترتیب شمیره ورکړو چې له 0 څخه پیل کیږي او د 6 بټ میپس لپاره حافظه تخصیص کړئ (د هرې ځانګړتیا لپاره یو). بیا به موږ دا بټ میپس په دې پورې اړه ولرو چې آیا رستورانت دا ملکیت لري یا نه. که چیرې رستورانت 4 برنډه ولري، نو بیا د "ورنډا لري" بټ میپ کې 4 بټ نمبر به 1 ته ټاکل کیږي (که چیرې برنډه نه وي نو بیا 0 ته).
اوس موږ د امکان تر ټولو ساده بټ میپ شاخص لرو، او موږ کولی شو دا د پوښتنو ځوابولو لپاره وکاروو لکه:
- "ما ته د سبزیجاتو دوستانه رستورانتونه وښایاست"؛
- "ما ته ارزانه رستورانتونه د برنډا سره وښایاست چیرې چې تاسو کولی شئ میز خوندي کړئ."
هغه څنګه؟ راځئ چې یو نظر ترلاسه کړو. لومړۍ غوښتنه خورا ساده ده. ټول هغه څه چې موږ یې کولو ته اړتیا لرو د "سبزیارو دوستانه" بټ میپ واخلئ او د رستورانتونو لیست ته یې واړوئ چې ټوټې یې افشا شوي.
دویمه غوښتنه یو څه پیچلې ده. موږ اړتیا لرو چې د ارزانه رستورانتونو لیست ترلاسه کولو لپاره په "ګران" بټ میپ کې نه بټ میپ وکاروو ، بیا یې د "ایا زه یو میز کتاب کولی شم" بټ میپ او او پایله یې د "برینډا شتون" بټ میپ سره. پایله لرونکی بټ میپ به د تاسیساتو لیست ولري چې زموږ ټول معیارونه پوره کوي. په دې مثال کې، دا یوازې د Yunost رستورانت دی.
دلته ډیری تیوري شامل دي، مګر اندیښنه مه کوئ، موږ به ډیر ژر کوډ وګورو.
د بټ میپ شاخصونه چیرته کارول کیږي؟
که تاسو د ګوګل بټ میپ شاخصونه ولیکئ، نو 90٪ ځوابونه به په یو ډول یا بل ډول د اوریکل DB سره تړاو ولري. مګر نور DBMSs شاید د داسې یو ښه شی ملاتړ وکړي، سمه ده؟ واقعیآ نه.
راځئ چې د اصلي شکمنو لیست له لارې لاړ شو.
MySQL لا تر اوسه د بټ میپ شاخصونو ملاتړ نه کوي، مګر یو وړاندیز شتون لري چې د دې اختیار اضافه کولو وړاندیز کوي ().
PostgreSQL د بټ میپ شاخصونو ملاتړ نه کوي ، مګر ساده بټ میپ او بټ عملیات کاروي ترڅو د ډیری نورو شاخصونو کې د لټون پایلې یوځای کړي.
ټارنټول د بټ سیټ شاخصونه لري او په دوی کې د ساده لټونونو ملاتړ کوي.
ریډیس ساده بټفیلډونه لري) د دوی د لټون کولو وړتیا پرته.
MongoDB لاهم د بټ میپ شاخصونو ملاتړ نه کوي ، مګر یو وړاندیز هم شتون لري چې وړاندیز کوي دا اختیار اضافه شي
Elasticsearch په داخلي توګه bitmaps کاروي).
- مګر زموږ په کور کې یو نوی ګاونډی راڅرګند شو: پیلوسا. دا یو نوی غیر اړونده ډیټابیس دی چې په Go کې لیکل شوی. دا یوازې د بټ میپ شاخصونه لري او په دوی باندې هرڅه اساس کوي. موږ به لږ وروسته په دې اړه خبرې وکړو.
په Go کې پلي کول
مګر ولې د بټ میپ شاخصونه خورا لږ کارول کیږي؟ مخکې لدې چې دې پوښتنې ته ځواب ووایو ، زه غواړم تاسو ته وښیم چې څنګه په Go کې د خورا ساده بټ میپ شاخص پلي کول.
Bitmaps په اصل کې یوازې د معلوماتو ټوټې دي. په Go کې، راځئ چې د دې لپاره د بایټ سلائسونه وکاروو.
موږ د یو رستورانت ځانګړتیا لپاره یو بټ میپ لرو، او په بټ میپ کې هر بټ دا په ګوته کوي چې آیا یو ځانګړی رستورانت دا ملکیت لري که نه.
موږ به دوه مرستندویه کارونو ته اړتیا ولرو. یو به د تصادفي معلوماتو سره زموږ د بټ میپس ډکولو لپاره وکارول شي. تصادفي، مګر د یو ځانګړي احتمال سره چې رستورانت هر ملکیت لري. د مثال په توګه، زه باور لرم چې په مسکو کې ډیر لږ رستورانتونه شتون لري چیرې چې تاسو نشئ کولی میز خوندي کړئ، او داسې ښکاري چې شاوخوا 20٪ تاسیسات د سبزیجاتو لپاره مناسب دي.
دوهم فعالیت به بټ میپ د رستورانتونو لیست ته واړوي.
دې پوښتنې ته د ځواب ورکولو لپاره "ما ته ارزانه رستورانتونه وښایاست چې انګړ لري او کولی شي ریزرویشن وکړي" موږ دوه بټ عملیاتو ته اړتیا لرو: نه او او.
موږ کولی شو د ډیر پیچلي او نه چلونکي په کارولو سره خپل کوډ یو څه ساده کړو.
موږ د دې هرې عملیاتو لپاره دندې لرو. دواړه د سلائسو له لارې تیریږي، د هر یو څخه ورته عناصر واخلئ، دوی د یو څه عملیاتو سره یوځای کړئ او پایله یې په پایله شوې ټوټه کې واچوئ.
او اوس موږ کولی شو د لټون پوښتنې ته د ځواب ویلو لپاره خپل بټ میپ او افعال وکاروو.
فعالیت دومره لوړ ندی ، که څه هم افعال خورا ساده دي او موږ هرکله چې فنکشن ته زنګ وهلو نوې پایله شوې سلائس بیرته نه راګرځولو سره ډیرې پیسې خوندي کړې.
د pprof سره د یو څه پروفایل کولو وروسته ، ما ولیدل چې د Go کمپیلر یو خورا ساده مګر خورا مهم اصلاح له لاسه ورکړی: فنکشن انلاین کول.
حقیقت دا دی چې د ګو کمپیلر د لوپونو څخه خورا ویره لري چې د سلائسو څخه تیریږي ، او په کلکه د انلاین افعالاتو څخه انکار کوي چې دا ډول لوپونه لري.
مګر زه ویره نه لرم او زه کولی شم د لوپ پرځای د ګوتو په کارولو سره کمپیلر احمق کړم ، لکه په پخوانیو ورځو کې.
او، لکه څنګه چې تاسو لیدلی شئ، اوس کمپیلر به په خوښۍ سره زموږ فعالیت انلاین کړي! د پایلې په توګه، موږ اداره کوو چې شاوخوا 2 مایکرو ثانیې خوندي کړو. بد نه دی!
دوهم خنډ د لیدلو لپاره اسانه دی که تاسو د مجلس محصول ته نږدې وګورئ. تالیف کونکي زموږ د ترټولو ګرم لوپ دننه د سلائس حدود چیک اضافه کړ. حقیقت دا دی چې Go یوه خوندي ژبه ده، تالیف کونکي ویره لري چې زما درې دلیلونه (درې ټوټې) د مختلف اندازو څخه دي. په هرصورت، بیا به د تش په نامه بفر اوور فلو د واقع کیدو نظري امکان شتون ولري.
راځئ چې کمپیلر ته د دې په ښودلو سره ډاډ ورکړو چې ټولې ټوټې ورته اندازه دي. موږ کولی شو دا زموږ د فعالیت په پیل کې د ساده چک اضافه کولو سره ترسره کړو.
د دې په لیدلو سره، کمپیلر په خوښۍ سره چک پریږدي، او موږ د نورو 500 نانو ثانیو خوندي کولو پای ته ورسوو.
لوی قصابان
سمه ده، موږ د خپل ساده پلي کولو څخه یو څه فعالیت ونیسو، مګر دا پایله په حقیقت کې د اوسني هارډویر سره د امکان په پرتله خورا خرابه ده.
ټول هغه څه چې موږ یې کوو لومړني بټ عملیات دي، او زموږ پروسیسرونه په خورا اغیزمنه توګه ترسره کوي. مګر، له بده مرغه، موږ خپل پروسیسر د خورا کوچنیو کارونو سره "غذایی" ورکوو. زموږ دندې د بایټ بایټ په اساس عملیات ترسره کوي. موږ کولی شو په اسانۍ سره خپل کوډ ټیک کړو ترڅو د UInt8 سلائسونو په کارولو سره د 64-بایټ ټوټو سره کار وکړو.
لکه څنګه چې تاسو لیدلی شئ ، دې کوچني بدلون زموږ برنامه اته ځله ګړندۍ کړه د بست اندازې اته ځله زیاتولو سره. ګټه د خطي په توګه ویل کیدی شي.
په جمع کونکي کې پلي کول
مګر دا پای نه دی. زموږ پروسیسرونه کولی شي د 16، 32 او حتی 64 بایټونو سره کار وکړي. دا ډول "پراخه" عملیات د واحد لارښوونې څو ډیټا (SIMD؛ یو لارښوونې، ډیری ډاټا) په نوم یادیږي، او د کوډ بدلولو پروسه چې دا ډول عملیات کاروي د ویکتوریزیشن په نوم یادیږي.
له بده مرغه، د Go کمپیلر د ویکٹر کولو په برخه کې خورا ښه دی. اوس مهال، د Go کوډ د ویکتوریز کولو یوازینۍ لار د Go assembler په کارولو سره دا عملیات په لاسي ډول اخیستل او ساتل دي.
ګو جمع کوونکی یو عجیب حیوان دی. تاسو شاید پوهیږئ چې د مجلس ژبه هغه څه دي چې د کمپیوټر له جوړښت سره په کلکه تړلي دي چې تاسو یې لیکئ ، مګر دا په Go کې قضیه نده. ګو اسمبلر د IRL (منځنۍ نمایندګۍ ژبه) یا منځمهاله ژبه په څیر دی: دا په عملی ډول پلیټ فارم خپلواک دی. روب پیک یو ښه فعالیت وړاندې کړ په دې موضوع څو کاله دمخه په ډنور کې په ګوفر کان کې.
برسېره پردې، Go یو غیر معمولي پلان 9 بڼه کاروي، کوم چې په عمومي توګه منل شوي AT&T او Intel فارمیټونو څخه توپیر لري.
دا خوندي ده چې ووایو چې د لاس په واسطه د ګو اسمبلر لیکل خورا ساتیري ندي.
مګر ، خوشبختانه ، دمخه دوه د لوړې کچې وسیلې شتون لري چې موږ سره د Go اسمبلر لیکلو کې مرسته کوي: PeachPy او avo. دواړه اسانتیاوې په ترتیب سره په Python او Go کې لیکل شوي د لوړې کچې کوډ څخه Go اسمبلر تولیدوي.
دا اسانتیاوې شیان ساده کوي لکه د راجستر تخصیص ، د لیکلو لوپونه ، او په عمومي ډول په Go کې د مجلس برنامو نړۍ ته د ننوتلو پروسه ساده کوي.
موږ به avo وکاروو، نو زموږ پروګرامونه به تقریبا منظم Go پروګرامونه وي.
دا هغه څه دي چې د avo پروګرام ساده مثال ورته ښکاري. موږ یو اصلي () فنکشن لرو، کوم چې په خپل ځان کې د Add() فنکشن تعریفوي، چې معنی یې د دوو شمیرو اضافه کول دي. دلته مرستندویه دندې شتون لري ترڅو د نوم په واسطه پیرامیټونه ترلاسه کړي او یو وړیا او مناسب پروسیسر راجستر ترلاسه کړي. د هر پروسیسر عملیات په avo کې ورته فعالیت لري، لکه څنګه چې په ADDQ کې لیدل کیږي. په نهایت کې ، موږ د پایلې ارزښت ذخیره کولو لپاره یو مرستندویه فعالیت ګورو.
د go generate په زنګ وهلو سره، موږ به برنامه په avo کې اجرا کړو او په پایله کې به دوه فایلونه تولید شي:
- add.s د Go assembler کې د پایلې کوډ سره؛
- stub.go د فنکشن سرلیک سره دوه نړۍ سره وصل کړئ: لاړ شئ او راټولونکی.
اوس چې موږ ولیدل چې avo څه کوي او څنګه، راځئ چې زموږ دندې وګورو. ما د دندو دواړه سکیلر او ویکتور (SIMD) نسخې پلي کړې.
راځئ چې لومړی د سکیلر نسخې وګورو.
لکه څنګه چې په تیر مثال کې، موږ د وړیا او باوري عمومي هدف راجستر غوښتنه کوو، موږ اړتیا نلرو چې د دلیلونو لپاره آفسیټونه او اندازې محاسبه کړو. دا ټول زموږ لپاره کوي.
موږ د فعالیت ښه کولو او د Go کمپیلر چلولو لپاره لیبلونه او ګوتو (یا کودونه) کاروو ، مګر اوس موږ دا له پیل څخه کوو. ټکی دا دی چې سایکلونه د لوړې کچې مفهوم دی. په جمع کولو کې، موږ یوازې لیبلونه او کودونه لرو.
پاتې کوډ باید دمخه پیژندل شوی او د پوهیدو وړ وي. موږ د لیبلونو او کودونو سره یو لوپ تقلید کوو ، زموږ له دوه سلائسو څخه د ډیټا یوه کوچنۍ ټوټه واخلو ، د یو څه عملیاتو سره یې یوځای کړو (او پدې حالت کې نه) او بیا پایله په پایله شوې ټوټه کې واچوو. ټول.
دا هغه څه دي چې د وروستي راټولونکي کوډ په څیر ښکاري. موږ اړتیا نه درلوده چې آفسیټونه او اندازې محاسبه کړو (په شنه کې روښانه شوي) یا کارول شوي راجسترونه تعقیب کړو (په سور کې روښانه شوي).
که موږ د اسمبلۍ ژبې پلي کولو فعالیت په Go کې د غوره پلي کولو فعالیت سره پرتله کړو ، نو موږ به وګورو چې دا ورته دی. او دا تمه کیږي. په هرصورت ، موږ هیڅ ځانګړي ندي کړي - موږ یوازې هغه څه تولید کړل چې د Go کمپیلر به څه وکړي.
له بده مرغه، موږ نشو کولی کمپیلر مجبور کړو چې زموږ دندې د مجلس په ژبه لیکل شوي انلاین کړي. د Go کمپیلر اوس مهال داسې ځانګړتیا نلري، که څه هم د یو څه مودې لپاره د دې اضافه کولو غوښتنه شوې.
له همدې امله دا ناشونې ده چې د مجلس په ژبه کې له کوچنیو کارونو څخه کومه ګټه ترلاسه شي. موږ اړتیا لرو چې یا لوی فنکشنونه ولیکئ، یا د نوي ریاضی / بټس کڅوړه وکاروئ، یا د راټولونکي ژبې څخه ډډه وکړئ.
راځئ چې اوس زموږ د دندو ویکتور نسخې وګورو.
د دې مثال لپاره، ما پریکړه وکړه چې AVX2 وکاروم، نو موږ به هغه عملیات وکاروو چې په 32-بایټ ټوټو کې کار کوي. د کوډ جوړښت د سکیلر نسخې سره ورته دی: د پیرامیټونو بار کول، د وړیا شریک شوي راجستر غوښتنه کول، او نور.
یو نوښت دا دی چې د ویکتور پراخه عملیات ځانګړي پراخه راجسترونه کاروي. د 32-بایټ ټوټو په حالت کې، دا د Y سره مخکینۍ راجسترونه دي. له همدې امله تاسو په کوډ کې د YMM() فعالیت وګورئ. که زه AVX-512 د 64-bit ټوټو سره کاروم، نو مخکینۍ به Z وي.
دوهم نوښت دا دی چې ما پریکړه وکړه چې د لوپ انرولینګ په نوم اصلاح وکاروم ، پدې معنی چې د لوپ پیل ته د کود کولو دمخه په لاسي ډول اته لوپ عملیات ترسره کول. دا اصلاح کول په کوډ کې د څانګو شمیر کموي، او د وړیا راجسترونو شمیر محدود دی.
ښه، د فعالیت په اړه څه؟ هغه ښکلې ده! موږ د غوره Go حل په پرتله شاوخوا اوه ځله سرعت ترلاسه کړ. اغیزمن، سمه ده؟
مګر حتی دا پلي کول په احتمالي توګه د پوښتنې مهالویش کونکي لپاره د AVX-512 ، پری فیچ کولو یا JIT (یوازې په وخت کې کمپیلر) کارولو سره ګړندی کیدی شي. مګر دا یقینا د جلا راپور لپاره موضوع ده.
د بټ میپ شاخصونو سره ستونزې
اوس چې موږ دمخه په Go کې د بټ میپ شاخص ساده پلي کولو او د مجلس په ژبه کې خورا ډیر ګټور یو ته ګورو ، راځئ په پای کې په دې اړه وغږیږو چې ولې د بټ میپ شاخصونه خورا لږ کارول کیږي.
زاړه کاغذونه د بټ میپ شاخصونو سره درې ستونزې یادوي، مګر نوي کاغذونه او زه استدلال کوم چې دوی نور اړوند ندي. موږ به د دې هرې ستونزې په ژوره توګه ونه ګورو، مګر په سطحه به یې وګورو.
د لوړ کارتینیلیت ستونزه
نو، موږ ته ویل کیږي چې د بټ میپ شاخصونه یوازې د ټیټ کارتینالیت ساحو لپاره مناسب دي، دا هغه کسان دي چې لږ ارزښتونه لري (د بیلګې په توګه، جندر یا د سترګو رنګ)، او دلیل یې دا دی چې د ورته ساحو معمول استازیتوب (یو bit per value) د لوړ کارډینالیت په حالت کې ، دا به ډیر ځای ونیسي او سربیره پردې ، دا د بټ میپ شاخصونه به ضعیف (په ندرت سره) ډک شي.
ځینې وختونه موږ ممکن مختلف استازیتوب وکاروو، لکه معیاري چې موږ یې د شمیرو نمایندګي لپاره کاروو. مګر دا د کمپریشن الګوریتم راتګ و چې هرڅه یې بدل کړل. په تیرو لسیزو کې، ساینس پوهان او څیړونکي د بټ میپ لپاره د کمپریشن الګوریتمونو لوی شمیر سره راغلي دي. د دوی اصلي ګټه دا ده چې د بټ عملیاتو ترسره کولو لپاره د بټ میپ ډیکمپریس کولو ته اړتیا نشته - موږ کولی شو په مستقیم ډول په کمپریس شوي بټ میپونو کې بټ عملیات ترسره کړو.
په دې وروستیو کې، د هایبرډ تګلارې څرګندیدل پیل شوي، لکه د بټ میپ رور کول. دوی په ورته وخت کې د بټ میپ لپاره درې مختلف نمایشونه کاروي - بټ میپ پخپله ، سرې او تش په نامه بټ رنز - او د دوی ترمینځ توازن د فعالیت اعظمي کولو او د حافظې مصرف کمولو لپاره.
تاسو کولی شئ په خورا مشهور غوښتنلیکونو کې د رورنګ بټ میپس ومومئ. د پروګرام کولو ژبو پراخه ډولونو لپاره دمخه د پلي کولو لوی شمیر شتون لري ، پشمول د Go لپاره له دریو څخه ډیر پلي کول.
بله طریقه چې کولی شي زموږ سره د لوړ کارډینالیت سره معامله کولو کې مرسته وکړي د بننګ په نوم یادیږي. تصور وکړئ چې تاسو یو ساحه لرئ چې د یو شخص لوړوالی استازیتوب کوي. لوړوالی د تیري نقطې شمیره ده، مګر موږ انسانان د هغې په اړه فکر نه کوو. زموږ لپاره د 185,2 سانتي مترو او 185,3 سانتي مترو په قد کې هیڅ توپیر نشته.
دا معلومه شوه چې موږ کولی شو ورته ارزښتونه په 1 سانتي مترو کې په ګروپونو کې ګروپ کړو.
او که موږ دا هم پوهیږو چې ډیر لږ خلک د 50 سانتي مترو څخه لنډ دي او د 250 سانتي مترو څخه لوړ دي، نو موږ کولی شو د لامحدود کارتینیلیت سره ساحه د 200 ارزښتونو سره په ساحه کې بدل کړو.
البته، که اړتیا وي، موږ کولی شو وروسته اضافي فلټر وکړو.
د لوړ بینډ ویت ستونزه
د بټ میپ شاخصونو سره بله ستونزه دا ده چې د دوی تازه کول خورا ګران کیدی شي.
ډیټابیسونه باید د دې وړتیا ولري چې ډاټا تازه کړي پداسې حال کې چې احتمالي سلګونه نورې پوښتنې ډاټا لټوي. موږ لاکونو ته اړتیا لرو ترڅو د معلوماتو د لاسرسي یا نورو شریکولو ستونزو سره د ستونزو مخه ونیسو. او چیرې چې یو لوی قفل شتون لري، ستونزه شتون لري - د قفل اختلاف، کله چې دا قفل یو خنډ شي.
دا ستونزه د شارډینګ په کارولو یا د نسخه شوي شاخصونو په کارولو سره حل یا مخنیوی کیدی شي.
شیر کول یو ساده او پیژندل شوی شی دی. تاسو کولی شئ د بټ میپ شاخص شارډ کړئ لکه څنګه چې تاسو کوم بل معلومات لرئ. د یو لوی قفل پر ځای، تاسو به د کوچنیو قفلونو یوه ډله ترلاسه کړئ او پدې توګه به د تالاشۍ له مینځه وړلو څخه خلاص شئ.
د ستونزې د حل لپاره دویمه لاره د نسخه شوي شاخصونو کارول دي. تاسو کولی شئ د هغه شاخص یوه کاپي ولرئ چې تاسو یې د لټون یا لوستلو لپاره کاروئ، او هغه چې تاسو یې د لیکلو یا تازه کولو لپاره کاروئ. او یو ځل په یوه ټاکلې موده کې (د مثال په توګه، په هرو 100 ms یا 500 ms کې یو ځل) تاسو دوی نقل کړئ او بدل یې کړئ. البته، دا طریقه یوازې په هغه قضیو کې د تطبیق وړ ده چیرې چې ستاسو غوښتنلیک کولی شي د لټون یو څه وروسته پاتې شاخص اداره کړي.
دا دوه طریقې په یو وخت کې کارول کیدی شي: تاسو کولی شئ د شارډ نسخه شاخص ولرئ.
ډیرې پیچلې پوښتنې
د بټ میپ شاخصونو سره وروستۍ ستونزه دا ده چې موږ ته ویل کیږي چې دوی د پوښتنو پیچلي ډولونو لپاره مناسب ندي ، لکه د سپان پوښتنو.
په حقیقت کې، که تاسو د دې په اړه فکر کوئ، د بټ عملیات لکه AND، OR، او داسې نور د پوښتنو لپاره خورا مناسب ندي "ما ته هغه هوټلونه وښایاست چې د خونې نرخونه په هره شپه د 200 او 300 ډالرو ترمنځ وي."
یو ساده او خورا غیر عقلمند حل به دا وي چې د هر ډالر ارزښت لپاره پایلې واخلئ او دوی د bitwise یا عملیاتو سره یوځای کړئ.
یو څه ښه حل به د ګروپ کولو کارول وي. د مثال په توګه، د 50 ډالرو په ګروپونو کې. دا به زموږ پروسه 50 ځله ګړندي کړي.
مګر ستونزه هم په اسانۍ سره د دې ډول غوښتنې لپاره رامینځته شوي لید په کارولو سره حل کیږي. په ساینسي کاغذونو کې دې ته د رینج کوډ شوي بټ میپ ویل کیږي.
په دې نمایش کې، موږ یوازې د یو څه ارزښت لپاره یو څه نه ټاکلو (د مثال په توګه، 200)، مګر دا ارزښت او هرڅه لوړ تنظیم کړئ. 200 او پورته. د 300 لپاره ورته: 300 او پورته. او همداسی پسی.
د دې نمایندګۍ په کارولو سره، موږ کولی شو دا ډول د لټون پوښتنې ته ځواب ووایو یوازې دوه ځله د شاخص په تیریدو سره. لومړی، موږ به د هوټلونو لیست ترلاسه کړو چیرې چې د کوټې لګښت لږ یا $ 300 دی، او بیا به موږ له هغې څخه هغه کسان لرې کړو چیرې چې د خونې لګښت لږ یا $ 199 وي. چمتو.
تاسو به حیران شئ، مګر حتی جیوکوریزونه د بټ میپ شاخصونو په کارولو سره ممکن دي. چال دا دی چې د جیومیټریک نمایش څخه کار واخلئ کوم چې ستاسو همغږي د جیومیټریک شکل سره محاصره کوي. د مثال په توګه، د ګوګل څخه S2. ارقام باید ممکنه وي چې د دریو یا ډیرو متقابلو لیکو په بڼه استازیتوب وکړي چې شمیرل کیدی شي. په دې توګه موږ کولی شو خپل جیوکوري په څو پوښتنو کې "د تشې سره" (د دې شمیرې لینونو سره) بدل کړو.
د ګړندۍ حلونه
زه امید لرم چې زه تاسو سره لږ علاقه لرم او تاسو اوس ستاسو په آرسنال کې بل ګټور وسیله لرئ. که تاسو کله هم د دې په څیر یو څه کولو ته اړتیا لرئ، تاسو به پوه شئ چې کومه لاره وګورئ.
په هرصورت، هرڅوک د سکریچ څخه د بټ میپ شاخصونو رامینځته کولو لپاره وخت، صبر، یا سرچینې نلري. په ځانګړې توګه ډیر پرمختللي، د مثال په توګه د SIMD کارول.
خوشبختانه، ستاسو سره د مرستې لپاره ډیری چمتو شوي حلونه شتون لري.
رورنګ بټ میپس
لومړی ، دلته ورته د بټ میپس کتابتون شتون لري چې ما دمخه یې په اړه خبرې کړې وې. دا ټول اړین کانټینرونه او بټ عملیات لري چې تاسو به یې د بشپړ بټ میپ شاخص رامینځته کولو ته اړتیا ولرئ.
له بده مرغه، دا مهال، د Go پلي کولو څخه هیڅ یو SIMD نه کاروي، پدې معنی چې د Go پلي کول د C پلي کولو په پرتله لږ فعالیت کوي، د بیلګې په توګه.
پیلوسا
بل محصول چې تاسو سره مرسته کولی شي پیلوسا DBMS دی، کوم چې په حقیقت کې یوازې د بټ میپ شاخصونه لري. دا یو نسبتا نوی حل دی، مګر دا په چټکۍ سره زړونه ګټل دي.
پیلوسا په داخلي توګه د بټ میپس کارول کوي او تاسو ته د دې کارولو وړتیا درکوي، ټول هغه شیان ساده او تشریح کوي چې ما پورته په اړه خبرې وکړې: ګروپ کول، د رینج کوډ شوي بټ میپس، د ساحې مفهوم، او نور.
راځئ چې د پیلوسا کارولو مثال ته یو ګړندي نظر واچوو ترڅو یوې پوښتنې ته ځواب ووایو چې تاسو دمخه ورسره آشنا یاست.
مثال د هغه څه سره ډیر ورته دی چې تاسو مخکې لیدلی. موږ د پیلوسا سرور ته یو پیرودونکی رامینځته کوو ، یو شاخص او اړین ساحې رامینځته کوو ، بیا زموږ ساحې د احتمالاتو سره تصادفي معلوماتو سره ډکوو او په نهایت کې ، پیژندل شوې پوښتنه اجرا کوو.
له هغې وروسته، موږ په "خرچه" ساحه کې نه کاروو، بیا پایله (یا AND دا) د "تریس" ساحې او د "ریزرویشن" ساحې سره وصل کړو. او په نهایت کې ، موږ وروستۍ پایله ترلاسه کوو.
زه واقعیا امید لرم چې په نږدې راتلونکي کې به دا نوی ډول شاخص په DBMSs لکه MySQL او PostgreSQL - bitmap indexes کې هم څرګند شي.
پایلې
که تاسو تر اوسه خوب نه وي کړی، مننه. ما باید د محدود وخت له امله په ډیرو موضوعاتو لنډ تماس ونیسم، مګر زه هیله لرم چې خبرې ګټورې او حتی هڅونکي وي.
د بټ میپ شاخصونه د پوهیدو لپاره ښه دي، حتی که تاسو اوس ورته اړتیا نلرئ. اجازه راکړئ چې دوی ستاسو په وسیله بکس کې بل وسیله وي.
موږ د Go او هغه شیانو لپاره د فعالیت مختلف چلونه لیدلي چې د Go کمپیلر لاهم ښه نه اداره کوي. مګر دا د هر Go پروګرامر لپاره د پوهیدو لپاره خورا ګټور دی.
دا ټول هغه څه دي چې ما غوښتل تاسو ته ووایم. له تاسو مننه!
سرچینه: www.habr.com