Most databases implement indices as a kind of tree. I will show you that columnar storages can do even better.<\/p>\n\n\n\n\n\n\n\n
The most widely used kind of tree structure in databases is the B-Tree. A B-Tree is a n-ary tree whose nodes fit exactly into one “page” – may it be a cache line of 64 bytes or a HDD page of 512 bytes or a memory page of 4K.<\/p>\n\n\n\n
The advantage of btrees is that it balances the memory fetch time with the time spent on computing on a chunk of memory. A btree node is basically layouted like This means, half of the space of the index is wasted on pointers, the other half is wasted on values. Latter is problematic when values get wide – especially when dealing with strings.<\/p>\n\n\n\n We will provide a different approach for indices that are far more memory efficient and thus faster in in-memory storage engines: sorted list indices<\/strong>.<\/p>\n\n\n\n In contrast to OLTP databases that need fast insert and delete procedures, in a separated main and delta storage<\/a>, we don’t have to care about insert performance because we never insert into the main storage. When items are inserted, they are inserted into the delta storage and the main storage is rebuilt on demand. Deletions are also easy to handle. When scanning through a table, we can just ignore deleted items.<\/p>\n\n\n\n So instead of storing pointers and values (where on multidimensional indices, values can span multiple columns), we can just store the recordId. For a 10k items storage, this would require less then 20KiB of RAM ! The list of recordIds can then be sorted according to our sort criterion and compressed into a bit compressed integer storage<\/a>.<\/p>\n\n\n\n Whenever we want to find a certain item or a range of items, we can now walk through the sorted list of recordIds and perform our binary search algorithms.<\/p>\n\n\n\n This is the data structure I came up with:<\/p>\n\n\n\n Here some facts:<\/p>\n\n\n\n In memcp, we use scheme<\/a> – a lisp dialect – as the internal query plan language. This has one big advantage: Every piece of code is an array that can be examined by our optimizer.<\/p>\n\n\n\n We implemented a helper function So we define a datatype like:<\/p>\n\n\n\n And then collect all conditions into a variable After collecting all boundaries, we sort As soon as the perfect index constellation is found, we create the <\/p>\n\n\n\n We did some measurements on the performance of on-the-fly index building:<\/p>\n\n\n\n The first query did an unoptimized table scan with 8.3ms<\/p>\n\n\n\n The second query did the index build with 18.2ms<\/p>\n\n\n\n The third query already uses the index and only needs 42\u00b5s – this is a speedup of almost 200x!<\/p>\n\n\n\n So you see: A index build is about twice the cost as a full table scan. This means, as soon as a index is used the second time, we can build the index and remove the When a table is rebuild, we can of course take over our measurements stored in the Most databases implement indices as a kind of tree. I will show you that columnar storages can do even better.<\/p>\n","protected":false},"author":2,"featured_media":4768,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_editorskit_title_hidden":false,"_editorskit_reading_time":4,"_editorskit_is_block_options_detached":false,"_editorskit_block_options_position":"{}","_uag_custom_page_level_css":"","footnotes":""},"categories":[129],"tags":[],"class_list":["post-4767","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-memcp","single-item"],"featured_image_urls_v2":{"full":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920.jpg",1920,1280,false],"thumbnail":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920-150x150.jpg",150,150,true],"medium":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920-300x200.jpg",300,200,true],"medium_large":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920-768x512.jpg",751,501,true],"large":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920-1024x683.jpg",751,501,true],"1536x1536":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920-1536x1024.jpg",1536,1024,true],"2048x2048":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920.jpg",1920,1280,false],"trp-custom-language-flag":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920.jpg",18,12,false],"xs-thumb":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920-64x64.jpg",64,64,true],"appku-shop-single":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920.jpg",620,413,false]},"post_excerpt_stackable_v2":" Most databases implement indices as a kind of tree. I will show you that columnar storages can do even better. The most widely used kind of tree structure in databases is the B-Tree. A B-Tree is a n-ary tree whose nodes fit exactly into one “page” – may it be a cache line of 64 bytes or a HDD page of 512 bytes or a memory page of 4K. The advantage of btrees is that it balances the memory fetch time with the time spent on computing on a chunk of memory. A btree node is basically layouted like pointer|value|pointer|value|pointer|value|pointer…<\/p>\n","category_list_v2":"MemCP<\/a>","author_info_v2":{"name":"Carl-Philip H\u00e4nsch","url":"https:\/\/launix.de\/launix\/author\/carli\/"},"comments_num_v2":"0 comments","uagb_featured_image_src":{"full":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920.jpg",1920,1280,false],"thumbnail":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920-150x150.jpg",150,150,true],"medium":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920-300x200.jpg",300,200,true],"medium_large":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920-768x512.jpg",751,501,true],"large":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920-1024x683.jpg",751,501,true],"1536x1536":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920-1536x1024.jpg",1536,1024,true],"2048x2048":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920.jpg",1920,1280,false],"trp-custom-language-flag":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920.jpg",18,12,false],"xs-thumb":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920-64x64.jpg",64,64,true],"appku-shop-single":["https:\/\/launix.de\/launix\/wp-content\/uploads\/2023\/01\/concept-18290_1920.jpg",620,413,false]},"uagb_author_info":{"display_name":"Carl-Philip H\u00e4nsch","author_link":"https:\/\/launix.de\/launix\/author\/carli\/"},"uagb_comment_info":0,"uagb_excerpt":"Most databases implement indices as a kind of tree. I will show you that columnar storages can do even better.","_links":{"self":[{"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/posts\/4767","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/comments?post=4767"}],"version-history":[{"count":6,"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/posts\/4767\/revisions"}],"predecessor-version":[{"id":4847,"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/posts\/4767\/revisions\/4847"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/media\/4768"}],"wp:attachment":[{"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/media?parent=4767"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/categories?post=4767"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/launix.de\/launix\/wp-json\/wp\/v2\/tags?post=4767"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}pointer|value|pointer|value|pointer|value|pointer<\/code><\/p>\n\n\n\nSorted lists of Record IDs<\/h2>\n\n\n\n
type<\/font> StorageIndex struct<\/font> {\n cols []string<\/font> \/\/ sort equal-cols alphabetically, so similar conditions are canonical<\/font>\n savings float64<\/font> \/\/ store the amount of time savings here -> add selectivity (outputted \/ size) on each<\/font>\n sortedItems StorageInt \/\/ we can do binary searches here<\/font>\n t *table\n inactive bool<\/font>\n}\n<\/pre>\n\n\n\n\n
cols<\/code>is the list of columns that are considered in the index<\/li>\n\n\n\nsortedItems<\/code><\/li>\n\n\n\ncols[0]<\/code>; in case of equality, cols[1]<\/code> is considered and so on<\/li>\n\n\n\ninactive<\/code> to true, so the index is considered<\/em> but not built<\/li>\n\n\n\nsavings<\/code>, we accumulate the amount of computation time we could save by having the index<\/li>\n\n\n\nsavings<\/code> exceeds a threshold, the index is built. Otherwise, we will do a full table scan.<\/li>\n\n\n\nfunc (s *StorageIndex) iterate(lower []scmer, upperLast scmer) chan uint<\/code> which will start a index scan beginning at lower<\/code> and will stop as soon as the last column reaches a value greater than upperLast<\/code>. When inactive<\/code> is set, the function will instead increase the savings<\/code> value and stream all recordIds of the table<\/li>\n<\/ul>\n\n\n\nFinding the Perfect Index for a Certain Condition<\/h2>\n\n\n\n
func (t *table) iterateIndex(condition scmer) chan uint<\/code> that takes a condition, finds the perfect index or creates it and then streams all recordIds that might<\/em> fit into the condition into a ring buffer (chan uint<\/code>)<\/p>\n\n\n\ntype<\/font> columnboundaries struct<\/font>{\n col string<\/font>\n lower scmer\n upper scmer\n}\n<\/pre>\n\n\n\ncols<\/code> of the type []columnbounbdaries<\/code>. For doing so, we implemented a recursive function traverseCondition(condition scmer)<\/code> that scans the condition for equal?<\/code>, <<\/code>, ><\/code>, <=<\/code>, >=<\/code> as well as BETWEEN ... AND ...<\/code> and IN<\/code> expressions. Whenever a column value is compared against a constant, we can fill in a columnboundaries<\/code> object.<\/p>\n\n\n\ncols<\/code> according to the following rules:<\/p>\n\n\n\n\n
equals?<\/code> is more selective than <<\/code> or ><\/code> comparisons, so we put all boundaries with lower == upper<\/code> first<\/li>\n\n\n\nlower != upper<\/code><\/li>\n\n\n\nequals?<\/code>-boundaries alphabetically by the column name, so that similar SQL queries can use the same index<\/li>\n\n\n\nStorageIndex<\/code> object, but set it to inactive<\/code> first. We then delegate the task of filling a chan uint<\/code> to the StorageIndex<\/code> object by calling func (s *StorageIndex) iterate(lower []scmer, upperLast scmer) chan uint<\/code><\/p>\n\n\n\nAutomatic Index Building and Cost Calculation<\/h2>\n\n\n\n
> (scan \"PLZ\" (lambda (Ort) (equal? Ort \"Neugersdorf\")) (lambda (PLZ Ort) (print PLZ \" - \" Ort)))\n02727 - Neugersdorf\n==> \"8.275433ms\"\n> (scan \"PLZ\" (lambda (Ort) (equal? Ort \"Neugersdorf\")) (lambda (PLZ Ort) (print PLZ \" - \" Ort)))\nbuilding index on PLZ over [Ort]\n02727 - Neugersdorf\n==> \"18.187862ms\"\n> (scan \"PLZ\" (lambda (Ort) (equal? Ort \"Neugersdorf\")) (lambda (PLZ Ort) (print PLZ \" - \" Ort)))\n02727 - Neugersdorf\n==> \"43.871\u00b5s\"\n> (scan \"PLZ\" (lambda (Ort) (equal? Ort \"Neugersdorf\")) (lambda (PLZ Ort) (print PLZ \" - \" Ort)))\n02727 - Neugersdorf\n==> \"45.681\u00b5s\"\n> (scan \"PLZ\" (lambda (Ort) (equal? Ort \"Neugersdorf\")) (lambda (PLZ Ort) (print PLZ \" - \" Ort)))\n02727 - Neugersdorf\n==> \"39.021\u00b5s\"\n> \n<\/pre>\n\n\n\n
inactive<\/code> flag. When we increase savings<\/code> by 1.0 every time the index is used and build the index at a threshold of 2.0, we will have the optimal heuristic for index creation.<\/p>\n\n\n\nsavings<\/code> variable to start the index build a bit earlier.<\/p>\n","protected":false},"excerpt":{"rendered":"