кіріспе
Мен бұл баяндаманы Мәскеудегі GopherCon Russia 2019 конференциясында ағылшын тілінде және Нижний Новгородтағы кездесуде орыс тілінде айттым. Біз растрлық индекс туралы айтып отырмыз - B-ағашқа қарағанда аз таралған, бірақ қызықты емес. Бөлісу конференцияда сөйлеген сөздері ағылшын тілінде және мәтіндік транскрипттер орыс тілінде.
Біз растрлық индекстің қалай жұмыс істейтінін, қай кезде жақсы екенін, қашан басқа индекстерге қарағанда нашар екенін және қандай жағдайларда олардан айтарлықтай жылдамырақ екенін қарастырамыз; Қандай танымал ДҚБЖ растрлық индекстері бар екенін көрейік; Go бағдарламасында өзімізді жазуға тырысайық. Ал «десертке» біз өзіміздің өте жылдам мамандандырылған дерекқорымызды жасау үшін дайын кітапханаларды қолданамыз.
Менің шығармаларым сіздерге пайдалы әрі қызықты болады деп сенемін. Бар!
Кіріспе
Бәріңе сәлем! Кешкі алты, бәріміз қатты шаршадық. Дерекқор индексінің қызықсыз теориясы туралы айтудың тамаша уақыты, солай ма? Уайымдамаңыз, менде бастапқы кодтың бірнеше жолы болады. 🙂
Әзілді былай қойғанда, есеп ақпаратқа толы, ал бізде көп уақыт жоқ. Ендеше, бастайық.
Бүгін мен мыналар туралы айтатын боламын:
- индекстер дегеніміз не;
- растрлық индекс дегеніміз не;
- ол қайда қолданылады және қайда ҚОЛДАНЫЛМАЙДЫ және неге;
- Go бағдарламасында қарапайым іске асыру және компилятормен аздап күресу;
- сәл аз қарапайым, бірақ Go ассемблерінде әлдеқайда өнімді іске асыру;
- растрлық индекстердің «мәселелері»;
- қолданыстағы енгізулер.
Сонымен, индекстер дегеніміз не?
Индекс - негізгі деректерге қосымша біз сақтайтын және жаңартылатын жеке деректер құрылымы. Ол іздеуді жеделдету үшін қолданылады. Индекссіз іздеу деректерді толығымен (толық сканерлеу деп аталатын процесс) тексеруді қажет етеді және бұл процесс сызықтық алгоритмдік күрделілікке ие. Бірақ дерекқорлар әдетте деректердің үлкен көлемін қамтиды және сызықтық күрделілік тым баяу. Ең дұрысы, біз логарифмдік немесе тұрақтыны аламыз.
Бұл өте күрделі тақырып, нәзіктіктер мен келіссөздерге толы, бірақ ондаған жылдар бойы дерекқорды әзірлеу мен зерттеуді қарастырғаннан кейін, дерекқор индекстерін құрудың бірнеше кеңінен қолданылатын тәсілдері бар екенін айтқым келеді.
Бірінші тәсіл іздеу кеңістігін кішірек бөліктерге бөле отырып, іздеу кеңістігін иерархиялық түрде азайту болып табылады.
Біз мұны әдетте әртүрлі ағаш түрлерін пайдалана отырып жасаймыз. Мысал ретінде сіздің шкафыңызда әртүрлі тақырыптарға бөлінген материалдардың кішірек қораптары бар материалдардың үлкен қорабы болуы мүмкін. Егер сізге материалдар қажет болса, сіз оларды «Cookie файлдары» деп емес, «Материалдар» деп жазылған қораптан іздейтін шығарсыз, солай емес пе?
Екінші тәсіл - қажетті элементті немесе элементтер тобын дереу таңдау. Біз мұны хэш карталарында немесе кері индекстерде жасаймыз. Хэш карталарын пайдалану алдыңғы мысалға өте ұқсас, бірақ қораптардың орнына сіздің шкафта соңғы заттардың кішкене қораптары бар.
Үшінші тәсіл – іздеу қажеттілігін жою. Біз мұны Блум сүзгілері немесе көкек сүзгілері арқылы жасаймыз. Біріншілері бірден жауап береді, бұл сізді іздеуден құтқарады.
Соңғы тәсіл - заманауи аппараттық құралдар беретін барлық қуатты толық пайдалану. Растрлық индекстерде дәл осылай істейміз. Иә, оларды пайдаланған кезде біз кейде бүкіл индексті қарап шығуымыз керек, бірақ біз мұны өте тиімді жасаймыз.
Мен айтқанымдай, дерекқор индекстерінің тақырыбы кең және ымыраға толы. Бұл кейде біз бірнеше тәсілдерді бір уақытта қолдануға болатынын білдіреді: егер бізге іздеуді одан да жылдамдату қажет болса немесе барлық мүмкін іздеу түрлерін қамту қажет болса.
Бүгін мен олардың ең аз белгілі тәсілі - растрлық индекстер туралы айтатын боламын.
Мен бұл тақырыпта сөйлейтін кіммін?
Мен Badoo-да топ жетекшісі ретінде жұмыс істеймін (мүмкін сіз біздің басқа өніміміз, Bumble-мен көбірек таныс боларсыз). Бізде қазірдің өзінде бүкіл әлем бойынша 400 миллионнан астам пайдаланушылар бар және олар үшін ең жақсы сәйкестікті таңдайтын көптеген мүмкіндіктер бар. Біз мұны реттелетін қызметтерді, соның ішінде растрлық индекстерді пайдалана отырып жасаймыз.
Сонымен растрлық индекс дегеніміз не?
Растрлық индекстер, аты айтып тұрғандай, іздеу индексін жүзеге асыру үшін нүктелік кескіндерді немесе бит жиындарын пайдаланады. Құс көзқарасы бойынша бұл индекс кез келген нысандарды (мысалы, адамдар) және олардың қасиеттерін немесе параметрлерін (жасы, көздің түсі, т.б.) көрсететін бір немесе бірнеше нүктелік кескіндерден және бит операцияларын (ЖӘНЕ, НЕМЕСЕ, ЕМЕС) пайдаланатын алгоритмнен тұрады. ) іздеу сұрауына жауап беру үшін.
Бізге растрлық индекстер көптеген төмен дәрежелі бағандар бойынша сұрауларды біріктіретін іздеулер бар жағдайлар үшін ең қолайлы және өте тиімді екендігі айтылды («көз түсі» немесе «тұрмыстық жағдай» немесе «қала орталығынан қашықтық» сияқты нәрсе деп ойлаңыз). Бірақ мен кейінірек олардың жоғары кардиналдық бағандар үшін жақсы жұмыс істейтінін көрсетемін.
Растрлық индекстің ең қарапайым мысалын қарастырайық.
Бізде екілік қасиеттері бар Мәскеу мейрамханаларының тізімі бар деп елестетіп көріңізші:
- метро жанында;
- жеке автотұрақ бар;
- веранда бар (террасасы бар);
- кестені брондауға болады (брондауды қабылдайды);
- вегетарианшыларға жарамды (вегетариандықтарға қолайлы);
- қымбат (қымбат).
Әрбір мейрамханаға 0-ден басталатын реттік нөмір берейік және 6 нүктелік кескінге жадты бөлейік (әр сипаттама үшін бір). Содан кейін мейрамханада осы сипаттың бар-жоғына байланысты осы нүктелік кескіндерді толтырамыз. Егер 4-ресторанда веранда болса, онда «веранда бар» растрлық кескініндегі №4 бит 1-ге орнатылады (веранда жоқ болса, онда 0).
Енді бізде мүмкін болатын ең қарапайым нүктелік кескін индексі бар және біз оны келесідей сұрауларға жауап беру үшін пайдалана аламыз:
- «Маған вегетариандыққа қолайлы мейрамханаларды көрсет»;
- «Маған үстелді брондауға болатын верандасы бар қымбат емес мейрамханаларды көрсетіңіз».
Қалай? Қарап көрейік. Бірінші сұрау өте қарапайым. Бізге тек «вегетариандық қолайлы» нүктелік кескінді алып, оны биттері ашылған мейрамханалар тізіміне айналдыру керек.
Екінші сұрау сәл күрделірек. Бізге қымбат емес мейрамханалар тізімін алу үшін «қымбат» растрлық кескінде ЕМЕС растрлық кескінді пайдалану керек, содан кейін ЖӘНЕ оны «кестеге тапсырыс бере аламын ба» растрлық кескінімен және ЖӘНЕ нәтиже «веранда бар» растрлық кескінімен. Алынған нүктелік суретте біздің барлық критерийлерге сәйкес келетін мекемелер тізімі болады. Бұл мысалда бұл тек «Юность» мейрамханасы.
Мұнда көптеген теориялар бар, бірақ уайымдамаңыз, біз кодты жақын арада көреміз.
Растрлық индекстер қайда қолданылады?
Егер сіз Google растрлық индекстерін іздесеңіз, жауаптардың 90%-ы қандай да бір жолмен Oracle DB-ге қатысты болады. Бірақ басқа ДҚБЖ-лар да осындай керемет нәрсені қолдайды, солай ма? Онша емес.
Негізгі күдіктілердің тізімін қарастырайық.
MySQL растрлық индекстерді әлі қолдамайды, бірақ бұл опцияны қосуды ұсынатын ұсыныс бар ().
PostgreSQL растрлық индекстерге қолдау көрсетпейді, бірақ бірнеше басқа индекстер бойынша іздеу нәтижелерін біріктіру үшін қарапайым нүктелік кескіндер мен бит операцияларын пайдаланады.
Tarantool битсет индекстеріне ие және оларда қарапайым іздеулерді қолдайды.
Redis-тің қарапайым бит өрістері бар) оларды іздеу мүмкіндігінсіз.
MongoDB растрлық индекстерді әлі қолдамайды, бірақ бұл опцияны қосуды ұсынатын ұсыныс бар.
Elasticsearch растрлық кескіндерді іштей пайдаланады).
- Бірақ біздің үйде жаңа көрші пайда болды: Пилоза. Бұл Go бағдарламасында жазылған жаңа реляциялық емес дерекқор. Ол растрлық индекстерді ғана қамтиды және барлығын соларға негіздейді. Бұл туралы сәл кейінірек айтамыз.
Go жүйесінде енгізу
Бірақ растрлық индекстер неге сонша сирек пайдаланылады? Бұл сұраққа жауап бермес бұрын, мен сізге Go бағдарламасында өте қарапайым растрлық индексті қалай енгізу керектігін көрсеткім келеді.
Растрлық кескіндер негізінен деректер бөліктері болып табылады. Go бағдарламасында бұл үшін байт кесінділерін қолданайық.
Бізде бір мейрамхана сипаттамасы үшін бір нүктелік кескін бар және нүктелік кескіндегі әрбір бит белгілі бір мейрамханада бұл сипаттың бар-жоғын көрсетеді.
Бізге екі көмекші функция қажет болады. Біреуі нүктелік кескіндерді кездейсоқ деректермен толтыру үшін пайдаланылады. Кездейсоқ, бірақ белгілі бір ықтималдықпен мейрамхананың әрбір қасиеті бар. Мысалы, менің ойымша, Мәскеуде үстелді брондауға болмайтын мейрамханалар өте аз және менің ойымша, мекемелердің шамамен 20% вегетарианшыларға жарамды.
Екінші функция нүктелік кескінді мейрамханалар тізіміне түрлендіреді.
«Маған патиосы бар және брондауға болатын қымбат емес мейрамханаларды көрсетіңіз» деген сұраққа жауап беру үшін бізге екі биттік операция қажет: ЕМЕС және ЖӘНЕ.
Біз күрделірек ЖӘНЕ ЕМЕС операторын пайдалану арқылы кодты біршама жеңілдете аламыз.
Бізде осы операциялардың әрқайсысы үшін функциялар бар. Екеуі де тілімдерден өтіп, әрқайсысынан сәйкес элементтерді алып, оларды бит операциясымен біріктіріп, нәтижені алынған кесіндіге салады.
Енді біз іздеу сұрауына жауап беру үшін нүктелік кескіндер мен функцияларды пайдалана аламыз.
Функциялар өте қарапайым болса да, өнімділік соншалықты жоғары емес және біз функция шақырылған сайын жаңа алынған бөлікті қайтармау арқылы көп ақша үнемдедік.
pprof көмегімен біраз профильдеу жасағаннан кейін мен Go компиляторында өте қарапайым, бірақ өте маңызды бір оңтайландырудың жоқ екенін байқадым: функция кірістіру.
Мәселе мынада, Go компиляторы кесінділер арқылы өтетін циклдардан қатты қорқады және мұндай циклдарды қамтитын кірістірілген функциялардан үзілді-кесілді бас тартады.
Бірақ мен қорықпаймын және ескі күндердегідей циклдің орнына goto арқылы компиляторды алдай аламын.
Көріп отырғаныңыздай, енді компилятор біздің функциямызды қуана кірістіреді! Нәтижесінде біз шамамен 2 микросекундты үнемдей аламыз. Жаман емес!
Жиын шығарылымына мұқият қарасаңыз, екінші тығырықты анықтау оңай. Компилятор біздің ең ыстық циклдің ішіне кесінді шекарасын тексеруді қосты. Мәселе мынада, Go - қауіпсіз тіл, компилятор менің үш аргументім (үш тілім) әртүрлі мөлшерде деп қорқады. Өйткені, содан кейін буфердің толып кетуі деп аталатын құбылыстың пайда болуының теориялық мүмкіндігі болады.
Барлық кесінділердің өлшемі бірдей екенін көрсету арқылы компиляторды тыныштандырайық. Біз мұны функциямыздың басында қарапайым тексеруді қосу арқылы жасай аламыз.
Мұны көрген компилятор тексеруді қуана өткізіп жібереді және біз тағы 500 наносекундты үнемдейміз.
Үлкен бұталар
Жарайды, біз қарапайым іске асырудың кейбір өнімділігін сығып алдық, бірақ бұл нәтиже шын мәнінде қазіргі аппараттық құралдармен мүмкін болғаннан әлдеқайда нашар.
Біз тек негізгі биттік операцияларды жасаймыз және біздің процессорлар оларды өте тиімді орындайды. Бірақ, өкінішке орай, біз процессорды өте аз жұмыс бөліктерімен «қоректендіреміз». Біздің функциялар байт-байт негізінде операцияларды орындайды. Біз UInt8 тілімдерін пайдаланып 64 байттық бөліктермен жұмыс істеу үшін кодымызды оңай өзгерте аламыз.
Көріп отырғаныңыздай, бұл шағын өзгеріс пакет көлемін сегіз есе ұлғайту арқылы бағдарламамызды сегіз есе жылдамдатты. Пайданы сызықтық деп айтуға болады.
Ассембтерде енгізу
Бірақ бұл соңы емес. Біздің процессорлар 16, 32 және тіпті 64 байт бөліктермен жұмыс істей алады. Мұндай «кең» операциялар бір командалық көп деректер (SIMD; бір нұсқаулық, көп деректер) деп аталады, ал кодты осындай операцияларды қолданатындай түрлендіру процесі векторизация деп аталады.
Өкінішке орай, Go компиляторы векторизацияда өте жақсы емес. Қазіргі уақытта Go кодын векторлаудың жалғыз жолы - Go ассемблер көмегімен осы операцияларды қолмен қабылдау және қою.
Go assembler - біртүрлі аң. Сіз ассемблер тілі сіз жазып жатқан компьютердің архитектурасына қатты байланысты екенін білетін шығарсыз, бірақ Go бағдарламасында олай емес. Go ассемблері IRL (аралық репрезентация тілі) немесе аралық тіл сияқты: ол іс жүзінде платформаға тәуелсіз. Роб Пайк тамаша өнер көрсетті осы тақырып бойынша бірнеше жыл бұрын Денвердегі GopherCon.
Сонымен қатар, Go жалпы қабылданған AT&T және Intel форматтарынан ерекшеленетін әдеттен тыс Plan 9 пішімін пайдаланады.
Go assembler-ді қолмен жазу ең қызық емес деп айтуға болады.
Бірақ, бақытымызға орай, Go ассемблерін жазуға көмектесетін екі жоғары деңгейлі құрал бар: PeachPy және avo. Екі утилита да Python және Go тілдерінде жазылған жоғары деңгейлі кодтан Go ассемблерін жасайды.
Бұл утилиталар регистрлерді бөлу, жазу циклдері сияқты нәрселерді жеңілдетеді және жалпы Go бағдарламасында құрастыру бағдарламалау әлеміне кіру процесін жеңілдетеді.
Біз avo тілін қолданамыз, сондықтан біздің бағдарламалар дерлік тұрақты Go бағдарламалары болады.
Avo бағдарламасының қарапайым мысалы осылай көрінеді. Бізде Add() функциясын анықтайтын main() функциясы бар, оның мағынасы екі санды қосу болып табылады. Параметрлерді аты бойынша алу және тегін және қолайлы процессор регистрлерінің бірін алу үшін мұнда көмекші функциялар бар. Әрбір процессор операциясының ADDQ-да көрсетілгендей avo жүйесінде сәйкес функциясы бар. Соңында біз алынған мәнді сақтауға арналған көмекші функцияны көреміз.
gogener деп шақыру арқылы біз бағдарламаны avo-да орындаймыз және нәтижесінде екі файл жасалады:
- Go ассемблерінде алынған кодпен add.s;
- stub.go екі әлемді қосу үшін функция тақырыптары бар: Go және assembler.
Енді біз avo не істейтінін және қалай істейтінін көрдік, енді өз функцияларымызды қарастырайық. Мен функциялардың скалярлық және векторлық (SIMD) нұсқаларын енгіздім.
Алдымен скаляр нұсқаларды қарастырайық.
Алдыңғы мысалдағыдай, біз тегін және жарамды жалпы мақсаттағы тізілімді сұраймыз, бізге аргументтер үшін ығысулар мен өлшемдерді есептеудің қажеті жоқ. avo мұның бәрін біз үшін жасайды.
Біз өнімділікті жақсарту және Go компиляторын алдау үшін белгілер мен goto (немесе секіру) қолданатынбыз, бірақ қазір біз мұны басынан бастап жасаймыз. Мәселе мынада, циклдар жоғары деңгейлі ұғым. Ассемблерде бізде тек белгілер мен секірулер бар.
Қалған код бұрыннан таныс және түсінікті болуы керек. Біз белгілер мен секірулер бар циклды эмуляциялаймыз, екі тілімнен деректердің шағын бөлігін аламыз, оларды биттік операциямен біріктіреміз (ЖӘНЕ бұл жағдайда ЕМЕС) және нәтижені алынған кесіндіге саламыз. Барлық.
Соңғы ассемблер коды осылай көрінеді. Бізге ығысулар мен өлшемдерді (жасыл түспен белгіленген) есептеудің немесе пайдаланылған регистрлерді (қызыл түспен белгіленген) қадағалап отырудың қажеті жоқ еді.
Ассемблер тілін іске асыру өнімділігін Go бағдарламасындағы ең жақсы іске асыру өнімділігімен салыстырсақ, оның бірдей екенін көреміз. Және бұл күтілуде. Ақыр соңында, біз ерекше ештеңе жасамадық - біз Go компиляторы не істейтінін ғана қайта шығардық.
Өкінішке орай, біз компиляторды ассемблер тілінде жазылған функцияларымызды кірістіруге мәжбүрлей алмаймыз. Go компиляторында қазір мұндай мүмкіндік жоқ, дегенмен оны қосу туралы сұраныс біраз уақыттан бері болған.
Сондықтан ассемблер тіліндегі шағын функциялардан ешқандай пайда алу мүмкін емес. Біз үлкен функцияларды жазуымыз керек, немесе жаңа математика/бит бумасын пайдалануымыз немесе ассемблер тілін айналып өтуіміз керек.
Енді функцияларымыздың векторлық нұсқаларын қарастырайық.
Бұл мысал үшін мен AVX2 пайдалануды шештім, сондықтан біз 32 байт бөліктерде жұмыс істейтін операцияларды қолданамыз. Код құрылымы скалярлық нұсқаға өте ұқсас: параметрлерді жүктеу, тегін ортақ тізілімді сұрау және т.б.
Бір жаңалық - кеңірек векторлық операциялар арнайы кең регистрлерді қолданады. 32 байт бөліктер жағдайында бұл Y префиксі бар регистрлер. Сондықтан кодта YMM() функциясын көресіз. Егер мен AVX-512-ні 64-биттік бөліктермен пайдалансам, префикс Z болады.
Екінші жаңалық, мен циклды ашу деп аталатын оңтайландыруды қолдануды шештім, бұл циклдің басына өту алдында сегіз цикл операциясын қолмен орындауды білдіреді. Бұл оңтайландыру кодтағы тармақтардың санын азайтады және қолжетімді бос регистрлер санымен шектеледі.
Ал, өнімділік туралы не деуге болады? Ол әдемі! Ең жақсы Go шешімімен салыстырғанда біз шамамен жеті есе жылдамдыққа қол жеткіздік. Әсерлі, иә?
Бірақ тіпті бұл іске асыруды сұрауды жоспарлаушы үшін AVX-512, алдын ала алу немесе JIT (дәл уақытында компилятор) пайдалану арқылы жеделдетуге болады. Бірақ бұл, әрине, бөлек баяндаманың тақырыбы.
Растрлық индекстермен проблемалар
Енді біз Go бағдарламасында растрлық индекстің қарапайым іске асырылуын және ассемблер тілінде анағұрлым өнімділігін қарастырғандықтан, ақырында растрлық индекстер неге сонша сирек қолданылатыны туралы сөйлесейік.
Ескі қағаздар растрлық индекстермен үш мәселе туралы айтады, бірақ жаңа қағаздар мен олардың енді өзекті емес екенін дәлелдеймін. Біз бұл мәселелердің әрқайсысына тереңірек үңілмейміз, бірақ оларға үстірт қараймыз.
Жоғары кардиналдық мәселесі
Сонымен, бізге растрлық индекстер тек қана кардиналдығы төмен өрістерге, яғни мәндері аз (мысалы, жыныс немесе көздің түсі) бар өрістер үшін жарамды екендігі айтылады және себебі мұндай өрістердің әдеттегі көрінісі (бір мәнге бит) жоғары кардиналдық жағдайында ол тым көп орын алады және оның үстіне бұл растрлық индекстер нашар (сирек) толтырылады.
Кейде біз сандарды көрсету үшін қолданатын стандартты сияқты басқа көріністі пайдалана аламыз. Бірақ барлығын өзгерткен қысу алгоритмдерінің пайда болуы болды. Соңғы онжылдықтарда ғалымдар мен зерттеушілер нүктелік кескіндерге арналған қысу алгоритмдерінің үлкен санын ойлап тапты. Олардың басты артықшылығы мынада, разрядтық операцияларды орындау үшін нүктелік кескіндерді ашудың қажеті жоқ - біз разрядтық операцияларды сығылған нүктелік кескіндерде тікелей орындай аламыз.
Жақында гибридті тәсілдер пайда бола бастады, мысалы, разрядты нүктелік кескіндер. Олар бір уақытта нүктелік кескіндер үшін үш түрлі көріністі пайдаланады - нүктелік кескіндердің өздері, массивтер және биттік орындалулар деп аталатын - өнімділікті арттыру және жадты тұтынуды азайту үшін олардың арасындағы теңгерім.
Сіз ең танымал қолданбалардан айнымалы нүктелік кескіндерді таба аласыз. Қазірдің өзінде бағдарламалау тілдерінің кең ауқымы үшін көптеген енгізулер бар, соның ішінде Go үшін үштен астам іске асыру.
Жоғары кардиналдықпен күресуге көмектесетін тағы бір тәсіл биннинг деп аталады. Сізде адамның бойын көрсететін өріс бар деп елестетіп көріңіз. Биіктік - өзгермелі нүкте саны, бірақ біз адамдар оны олай ойламаймыз. Біз үшін 185,2 см мен 185,3 см биіктіктің айырмашылығы жоқ.
Ұқсас мәндерді 1 см ішінде топтарға топтастыруға болады екен.
Ал егер біз сондай-ақ өте аз адамдардың бойы 50 см-ден қысқа және 250 см-ден жоғары екенін білсек, онда біз шексіз түбегейлі өрісті 200-ге жуық мәнге ие өріске айналдыра аламыз.
Әрине, қажет болса, кейін қосымша сүзгілеуді жасай аламыз.
Жоғары өткізу қабілеттілігі мәселесі
Растрлық индекстермен келесі мәселе оларды жаңарту өте қымбат болуы мүмкін.
Жүздеген басқа сұраулар деректерді іздеп жатқанда, дерекқорлар деректерді жаңарта алуы керек. Деректерге бір мезгілде қол жеткізу немесе басқа бөлісу мәселелерін болдырмау үшін бізге құлыптар қажет. Бір үлкен құлып бар жерде мәселе туындайды - құлыптау даусы, бұл құлып тығырыққа айналған кезде.
Бұл мәселені бөлшектеу немесе нұсқаланған индекстерді пайдалану арқылы шешуге немесе айналып өтуге болады.
Бөлшектеу - қарапайым және белгілі нәрсе. Растрлық индексті кез келген басқа деректер сияқты бөлшектеуге болады. Бір үлкен құлыптың орнына сіз бірнеше кішкентай құлыптар аласыз және осылайша құлыптау дауынан құтыласыз.
Мәселені шешудің екінші жолы – нұсқаланған индекстерді пайдалану. Сізде іздеу немесе оқу үшін пайдаланатын индекстің бір данасы және жазу немесе жаңарту үшін пайдаланатын біреуі болуы мүмкін. Және белгілі бір уақыт аралығында бір рет (мысалы, 100 мс немесе 500 мс сайын) сіз оларды көшіресіз және ауыстырасыз. Әрине, бұл әдіс қолданбаңыз сәл артта қалған іздеу индексін өңдей алатын жағдайларда ғана қолданылады.
Бұл екі тәсілді бір уақытта пайдалануға болады: сізде бөлшектелген нұсқа индексі болуы мүмкін.
Күрделі сұраулар
Растрлық индекстердің соңғы мәселесі бізге олардың ауқымды сұраулар сияқты күрделірек сұрау түрлеріне сәйкес келмейтіндігін айтады.
Шынында да, егер сіз бұл туралы ойласаңыз, ЖӘНЕ, НЕМЕСЕ, т.б. сияқты бит операциялары «Маған бір түнде 200-ден 300 долларға дейінгі нөмірлері бар қонақүйлерді көрсетіңіз» деген сұрауларға өте қолайлы емес.
Аңғал және өте ақылсыз шешім әрбір доллар құны үшін нәтижелерді алу және оларды биттік НЕМЕСЕ операциясымен біріктіру болады.
Топтауды пайдалану сәл жақсырақ шешім болар еді. Мысалы, 50 доллардан тұратын топтарда. Бұл біздің процесті 50 есе жылдамдатады.
Бірақ мәселе сұраудың осы түрі үшін арнайы жасалған көріністі пайдалану арқылы да оңай шешіледі. Ғылыми еңбектерде ол диапазонмен кодталған нүктелік кескіндер деп аталады.
Бұл көріністе біз қандай да бір мән үшін бір бит орнатпаймыз (мысалы, 200), бірақ осы мәнді және барлығын жоғарырақ орнатамыз. 200 және одан жоғары. 300: 300 және одан жоғары үшін бірдей. Тағыда басқа.
Бұл ұсынуды пайдалана отырып, біз индексті екі рет айналып өту арқылы осы іздеу сұрауына жауап бере аламыз. Біріншіден, біз нөмірі төмен немесе 300 доллар тұратын қонақүйлердің тізімін аламыз, содан кейін біз одан бөлменің құны аз немесе 199 доллар тұратындарды алып тастаймыз. Дайын.
Сіз таң қаласыз, бірақ растрлық индекстерді пайдалану арқылы тіпті геосұраулар да мүмкін. Бұл сіздің координатаны геометриялық фигурамен қоршайтын геометриялық кескінді пайдалану. Мысалы, Google-дан S2. Фигураны нөмірлеуге болатын үш немесе одан да көп қиылысатын сызықтар түрінде көрсету мүмкіндігі болуы керек. Осылайша, біз геокранымызды «саңылау бойынша» (осы нөмірленген жолдар бойымен) бірнеше сұрауларға айналдыра аламыз.
Дайын шешімдер
Мен сізді аздап қызықтырды деп үміттенемін және сіздің арсеналыңызда тағы бір пайдалы құрал бар. Егер сізге осындай нәрсені жасау қажет болса, сіз қай жолды іздеу керектігін білесіз.
Дегенмен, растрлық индекстерді нөлден жасау үшін әркімнің уақыты, шыдамдылығы немесе ресурстары бола бермейді. Әсіресе жетілдірілгендер, мысалы, SIMD көмегімен.
Бақытымызға орай, сізге көмектесетін бірнеше дайын шешімдер бар.
Күрделі нүктелік кескіндер
Біріншіден, мен бұрыннан айтқан дәл сол айнымалы нүктелік суреттер кітапханасы бар. Ол толыққанды растрлық индексті жасау үшін қажет болатын барлық қажетті контейнерлерді және бит операцияларын қамтиды.
Өкінішке орай, қазіргі уақытта Go іске асыруларының ешқайсысы SIMD қолданбайды, яғни Go іске асырулары, мысалы, C іске асыруға қарағанда өнімділігі төмен.
Пилоза
Сізге көмектесетін тағы бір өнім - бұл шын мәнінде тек растрлық индекстері бар Pilosa ДҚБЖ. Бұл салыстырмалы түрде жаңа шешім, бірақ ол жүректерді үлкен жылдамдықпен жаулап алуда.
Pilosa дірілдеген нүктелік кескіндерді іштей пайдаланады және сізге оларды пайдалану мүмкіндігін береді, мен жоғарыда айтқан барлық нәрселерді жеңілдетеді және түсіндіреді: топтау, ауқымды кодталған нүктелік кескіндер, өріс түсінігі және т.б.
Сізге бұрыннан таныс сұраққа жауап беру үшін Pilosa пайдалану мысалын жылдам қарастырайық.
Мысал бұрын көргеніңізге өте ұқсас. Біз Pilosa серверіне клиент жасаймыз, индекс пен қажетті өрістерді жасаймыз, содан кейін өрістерімізді ықтималдығы бар кездейсоқ деректермен толтырамыз және соңында таныс сұранысты орындаймыз.
Осыдан кейін біз «қымбат» өрісте ЕМЕС қолданамыз, содан кейін нәтижені (немесе ЖӘНЕ оны) «террасса» өрісімен және «брондау» өрісімен қиылысамыз. Ақырында, біз түпкілікті нәтижеге қол жеткіземіз.
Таяу болашақта индекстің бұл жаңа түрі MySQL және PostgreSQL сияқты ДҚБЖ – растрлық индекстерде де пайда болады деп үміттенемін.
қорытынды
Егер сіз әлі ұйықтамаған болсаңыз, рахмет. Уақыттың шектеулілігіне байланысты көптеген тақырыптарды қысқаша қозғауға тура келді, бірақ әңгіме пайдалы болды деп үміттенемін, мүмкін тіпті мотивация берді.
Растрлық индекстер дәл қазір қажет болмаса да, олар туралы білу жақсы. Олар сіздің құралдар жинағындағы басқа құрал болсын.
Біз Go бағдарламасына арналған әртүрлі өнімділік трюктерін және Go компиляторы әлі жақсы өңдемейтін нәрселерді қарастырдық. Бірақ бұл әрбір Go бағдарламашысының білуі өте пайдалы.
Менің саған айтқым келгені осы болды. Рақмет сізге!
Ақпарат көзі: www.habr.com