Efficient use of TRIE data structure in databases
11347741 · 2022-05-31
Assignee
Inventors
Cpc classification
G06F17/11
PHYSICS
International classification
G06F9/30
PHYSICS
G06F17/11
PHYSICS
Abstract
The invention provides a time-efficient way of performing a query in a database or information retrieval system comprising operations such as intersection, union, difference and exclusive disjunction on two or more sets of keys stored in a database or information retrieval system. In a novel execution model, all data sources are tries. Two or more input tries are combined in accordance with the respective set operation, to obtain the set of keys associated with the nodes of a respective resulting trie. An intersection operation performed in this way can be used for efficient range queries, in particular when two or more data items are involved in the query. The physical algebra of the implementation of tries based on bitmaps corresponds directly to the logical algebra for the set operations and allows for efficient implementation by means of bitwise Boolean operations.
Claims
1. A method of retrieving data from an electronic database or information retrieval system by performing an electronic database or information retrieval system query, wherein the electronic database or information retrieval system query is a range query, the method comprising the steps of: obtaining definitions of one or more ranges, and obtaining two or more input tries; combining the input tries using a logical operation to obtain a set of keys associated with nodes of a resulting trie; and providing, as query output, (1) the set of keys associated with the nodes of the resulting trie, (2) a subset of the keys associated with the nodes of the resulting trie, wherein the subset of the keys is associated with the leaves of the resulting trie, or (3) a set of keys or values derived from the set of keys associated with the nodes of the resulting trie; wherein a trie comprises one or more child nodes, each child node is associated with a key portion, and the path from the root node to a particular node in the trie defines a key with which the particular node is associated, the key being a concatenation of the key portions associated with the particular nodes on the path, wherein a set of child nodes of each node in the resulting trie is a combination, based on the logical operation, of the sets of child nodes of the corresponding nodes in the input tries, wherein two or more nodes, of different tries, corresponding to each other have identical keys associated with the nodes of the different tries, wherein one input trie is an input set trie which stores the set of keys stored in the electronic database or information retrieval system or a set of result keys of an electronic database or information retrieval system query, to be searched for the one or more ranges, another input trie is a virtual range trie, wherein a range trie is a trie which when fully materialized stores all values included in the one or more ranges of which the definitions have been obtained and the logical operation is an intersection, wherein the virtual range trie is an implementation of the range trie that only materializes nodes that are dynamically generated on demand during the operation of combining the input tries, and wherein the dynamically generated nodes of the virtual range trie are those that are required for combining the input tries using the logical operation.
2. The method of claim 1, wherein the step of combining the input tries comprises performing a combination function for the root node of the resulting trie, wherein performing a combination function for an input node of a resulting trie comprises determining a set of child nodes for the input node of the resulting trie by combining, the sets of child nodes of the nodes of the input tries which correspond to the input node of the resulting trie, using the logical operation; and performing the combination function for each of the child nodes determined for the input node of the resulting trie.
3. The method of claim 1, wherein a node in an input trie, preferably at least all parent nodes in an input trie which have more than one child node, comprise a bitmap, wherein the value of a key portion of a child node in a trie is determined by the value of a bit in the bitmap comprised by the parent node with which bit the child node is associated, and wherein a combination operation of child nodes of the input tries, using the logical operation, comprises combining the bitmaps of each of the child nodes of the input tries, using the logical operation.
4. The method of claim 3, wherein using the logical operation comprises combining the bitmaps of nodes using a bitwise AND Boolean operator, a bitwise OR Boolean operator, a bitwise AND NOT Boolean operator, or a bitwise XOR Boolean operator.
5. The method of claim 1, wherein the keys associated with nodes of the input set trie code two or more data items of a specific data type, and wherein the definitions of one or more ranges comprise definitions of one or more ranges for one or more of the data items.
6. The method of claim 5, wherein the virtual range trie is a multi-item range trie obtained by combining a single-item range trie for each of the data items coded by the keys associated with nodes of the input set trie, wherein the single-item range trie for a data item stores all the values included in one or more ranges of the data item, and wherein the multi-item range trie stores all combinations of the values of the data items stored in the single-item range tries.
7. The method of claim 6, wherein the single-item range trie for each data item for which no definition of a range is obtained stores the entire range of possible values of the data item.
8. The method of claim 5, further comprising providing, as an output, a set of reduced-item keys coding a subset of the data items coded by the keys associated with the leaves of the input set trie.
9. The method of claim 8, wherein the set of reduced-item keys obtained as a result of the operation of combining the input set trie with the virtual range trie is written into a newly created trie, thereby eliminating duplicate keys, prior to providing the output.
10. The method of claim 6, wherein each of the data items coded by a key associated with nodes of the input set trie and the virtual range trie consist of two or more components, wherein a component is a bit group comprising 6 bits; and wherein the key contains two or more consecutive sections, each of the sections comprising components of two or more of the data items coded in the key.
11. The method of claim 10, wherein each component of a data item coded by a key associated with nodes of the input set trie and/or the virtual range trie corresponds to the key portion associated with one child node of the trie.
12. A non-transitory computer readable medium having stored thereon instructions for performing the method of claim 1.
13. A data-processing system comprising one or more processors and memory, the data-processing system being configured to perform the method of claim 1.
Description
BRIEF DESCRIPTION OF THE DRAWINGS
(1) In the following, the invention will be described in greater detail in connection with the preferred embodiments and with reference to the drawings, in which
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)
(18)
(19)
(20)
(21)
(22)
(23)
(24)
(25)
(26)
(27)
(28)
(29)
(30)
(31)
(32)
(33)
(34)
(35)
(36)
(37)
(38)
(39)
(40)
(41)
(42)
(43)
(44)
(45)
(46)
(47)
(48)
(49)
(50)
(51)
(52)
(53)
(54)
(55)
(56)
(57)
(58)
(59)
(60)
(61)
(62)
(63)
(64)
(65)
(66)
(67)
(68)
(69)
(70)
(71)
(72)
(73)
(74)
(75)
(76)
DETAILED DESCRIPTION
(77)
(78) Root node 102 located on the first level 110 has one child node 104 being associated with a key portion of value “0”. Therefore, there is a pointer 103 from root node 102 to child node 104 located on the second level 111 of trie 101, which indicates a value of “0”. From child node 104 on the second level, two different pointers point to nodes 105, 106 located on a third level 112, and from each of these nodes 105, 106, one further pointer points to leaf nodes 107, 108, respectively. The concatenation of the key portions of the nodes on the path from the root to the leaf nodes hence results in the keys with values “007” and “042”.
(79)
(80) The trie data structure of
(81)
(82)
(83)
(84) To determine the pointer of a child node, the amount of preceding child pointers has to be calculated. The offset to find the pointer is the amount of least significant bits set in the bitmap before the target position, as is illustrated in
(85) The trie data structure of the example of
(86) Root node 502 has one bit set in its bitmap, representing the key portion value “00”. Thus, root node 502 comprises only one pointer 503 to a child node 504, the child node being associated with the key portion with value “00”. Child node 504 has two bits 505, 507 set in its bitmap, namely the bits representing the key portion values “2A” and “00”. Thus, child node 504 comprises two pointers 507 and 508, which point to the respective child nodes 509, 510.
(87) Pointer 506 associated with the bit in the bitmap having the value “2A” is addressed by calculating how many least significant bits are set starting from the bit 505 representing the key portion value “2A”. In this case, there is only one least significant bit set, namely bit 506, so it can be determined that there is an offset of one pointer and that the pointer we are looking for is the second pointer comprised by child node 504.
General Features of the Preferred Embodiments of Tries According to the Present Invention
(88) Like all tries, the tries or trie data structures according to the invention comprise one or more nodes. As in the prior art tries described above with reference to
(89) In preferred embodiments of the tries according to the invention, a node, preferably at least each parent node which has more than one child node, comprises a bitmap and a number of pointers. Each pointer is associated with a bit which is set in the bitmap and points to a child node of the node. Typically a bit is “set” in a bitmap if its value is “1”. However, in particular embodiments a bit may count as “set” if its value is “0”. A bit in a bitmap counts as “set” herein if its value corresponds to the value which is associated with the notion that the bit in the bitmap marks a valid branch, as has been explained above with reference to the prior art tries shown in
(90) Preferably, the bitmap is stored in memory as an integer of predefined size. Furthermore, the size of the bitmap is preferably 32, 64, 128 or 256 bits. Performance of the operations of the target computer system storing and processing the trie can be increased by choosing the size of the bitmap such that it is equal to the bit width of the registers of the CPU, the system bus, data bus and/or address bus of the target computer system.
(91) For example, as mentioned above, the memory address of a pointer associated with a bit which is set in the bitmap can be calculated based on the number of least significant bits set in the bitmap. This determination can be made very efficiently using simple bit operations and a CTPOP (count population) operation that determines the number of set bits. Many modern CPUs even provide CTPOP as an intrinsic instruction. However, since in modern CPUs long integers are 64 bits wide, CTPOP works only on 64 bits. This means for the prior art tries using a bitmap of 256 bits that the operation is performed up to four times (4×64=256). Alternatively, prior art tries store the total bitcounts of the preceding bitmaps with the first three bitmaps. The number of least significant bits can then be calculated as CTPOP of the last group of bits+bitcount of the precededing groups of bits.
(92) Since currently in most computer systems the system bit width is 64 bits, a bitmap size of 64 bits is currently the most preferred size and was used by the inventor for his example implementations of the invention. This results in a 64-ary trie, which means that every node can store symbols of an alphabet of 64 symbols, that is it can encode 6 bits (2.sup.6=64). As will be explained below, tries according to embodiments of the invention may use several nodes and their associated key portions to store the information comprised by a primitive data type. For example, for storing a key represented by a 64-bit long integer, a 64-ary trie with 11 levels is required (11*6 Bits>=64).
(93) The bitmaps and/or the pointers may be stored, e.g., in an array, in a list, or in consecutive physical or virtual memory locations. Note that whenever the term “memory” is used herein, it may refer to physical or virtual memory, preferably continuous memory. In preferred embodiments, a long integer (64 bits) is used for representing the bitmap, and also for representing each of the child pointers. Instead of allocating nodes separately in memory, the nodes are stored in an array of long integers, and instead of having memory pointers for nodes, the current node is specified by an index into this array. A child pointer may be an index of the node position in the array. When traversing the trie, the offset to find the index of a child node based on the current node index is then the amount of least significant bits set in the bitmap before the target position plus one for the bitmap.
(94) Preferred embodiments work with several such arrays. One part, e.g. the lower part of a pointer is the index within the array, and another part of the pointer, e.g. the higher part is the reference to an array. This is done for memory management reasons, because it is not always possible to allocate an array of arbitrarily large size. In Java for example, the size of an array is limited to 32 bit integers, and this results in an array size of 2.sup.31 (only positive values)=2,147,483,648. However, many real-world applications require arrays comprising 16 MB or more, which corresponds to 2 million entries for a 64-bit long integer array.
(95) Like in the prior art trie of
(96) Like in the prior art trie of
(97) In the preferred embodiments of the invention, each key portion in the trie is capable of storing a value of a same predefined size, e.g. a 5-bit value (if the size of the bitmap is 32 bits), a 6-bit value (if the size of the bitmap is 64 bits), a 7-bit value (if the size of the bitmap is 128 bits) or 8-bit value (if the size of the bitmap is 256 bits). The alphabet of characters represented by a node or key portion is the set of all possible bit groups having that size. For example, where a key portion is capable of storing a 6-bit value, the alphabet is the set of all bit groups comprising 6 bits.
(98) The trie data structures according to the invention can be used for implementing key-value maps (also referred to as “associative arrays”), where the values are stored in the leaf nodes, as well as key sets (also referred to as “dynamic sets”), where no data is stored in the leaf nodes. Maps are used in cases where every key has only one value, to look up the value for a given key, whereas sets are used for determining if a given set contains a given key. For both, set operations on keys (such as union, intersection, or difference) are frequently required operations as well.
(99)
(100) Where the value data type is of fixed size, such as a date or an integer, it is more efficient to store the value “inline” as is shown in
(101)
(102) The trie data structure stores keys in an ordered manner, and therefore allows traversing keys in order. For example, a 64-bit long integer key may be stored starting with the most significant 6-bits (or 4-bits, because 64=4+10*6) to the least significant 6-bits. This way, integers are treated as unsigned long integers. For signed integers, which are typically encoded using two's complement, to have the correct ordering, they must be converted into an offset binary representation, e.g. by adding 2.sup.64-1 for 64-bit long integers. Floating point numbers are treated in a similar way. Therefore, coding a value of a data item of the key, such as a floating point number or a two's complement signed integer may comprise converting the data type of the data item into an offset binary representation consisting in an unsigned integer, e.g. an unsigned long integer.
(103) Space-Efficient Trie Data Structures
(104) In many application scenarios, use of memory space is inefficient. This is particularly true when the trie is sparsely populated and/or degenerates to a chain of nodes, where each node has only a single child pointer.
(105) Chained Node Optimization
(106) The inventor found in empirical studies that for arbitrary keys, a trie in typical application scenarios has many nodes with only a single child. This is because many keys share a common prefix, infix, or postfix. The prior art trie degenerates in such a situation into chains of nodes with single child pointers, and the space efficiency of the prior art trie data structure is low.
(107) A first space optimization of the present invention eliminates child pointers when a node only has a single child, i.e. in the bitmap comprised by a parent node, only a single bit is set. This approach is referred to herein as “chained node optimization”. An example of a trie where the chained node optimization is efficient is shown in
(108) The first space optimization of the present invention applies to a trie comprising one or more nodes, wherein a parent node comprised by the trie, preferably each parent node which has more than one child node, comprises a bitmap and one or more pointers, wherein each pointer is associated with a bit set in the bitmap and points to a child node of the parent node. The optimization is achieved by the fact that a parent node comprised by the trie, preferably each parent node which has only one child node, does not comprise a pointer to the child node, and/or the child node is stored in a predefined position in memory relative to the parent node. Preferably, a child node of a parent node having only one child node is stored in a position in memory directly behind the parent node.
(109) The first space optimization according to the invention is illustrated in
(110) Trie 910 comprises a first node 911 having only one single child, as indicated by the (64-bit wide) bitmap of node 911, in which only one bit is set (1) and all other bits are unset (0). Like in the prior art tries, node 911 consequently comprises one single pointer 914, a long integer which points to node 911′s child node, node 912. Node 912 has two child nodes, not shown in
(111) Trie 920 also comprises a first node, 921, having only one single child, as indicated by the (64-bit wide) bitmap of node 921, in which only one bit is set (1) and all other bits are unset (0). However, in contrast to node 911 in trie 910, node 921 in trie 920 does not comprise a pointer which points to node 921′s child node, node 922. Instead, node 922 is stored in a memory location directly behind node 921, as it is preferred, but alternatively could be stored anywhere in the array of long integers as long as the position in memory relative to parent node 921 is predefined. E.g., child node 922 could be stored directly before parent node 921, or there could be another data object of fixed length between parent node 921 and child node 922. Like node 912 of trie 910, node 912 of trie 920 has two child nodes, not shown in
(112) In the example embodiment of
(113) Terminal Optimization
(114) A second space optimization of the present invention provides for a more compact representation of the trie in memory where the “ends” of a trie comprise chains or strings of single nodes, i.e. many keys which do not have a common postfix. An example of a trie where the second space optimization is efficient is shown in
(115) According to the second space optimization, a node at the start of the string of single nodes is marked as a “terminal branch node”. In
(116) The second space optimization of the present invention therefore applies to a trie comprising one or more nodes, wherein a parent node comprised by the trie, preferably at least each parent node which has more than one child node, comprises a bitmap; a node, preferably each child node is associated with a key portion; and the value of the key portion of a child node, preferably of at least each child node whose parent has more than one child nodes, is determined by the value of a bit (set) in a bitmap comprised by the parent node with which bit the child node is associated.
(117) In Ph. Bagwell, “Fast And Space Efficient Trie Searches”, Technical Report, EPFL, Switzerland (2000), where nodes are allocated independently in memory, an approach called “tree tail compression” references with pointers to a string node or a stores numeric values of terminal strings directly in the terminal branch node. However, this approach is not space-efficient because offsets and node type (node with bitmap or node with character/pointer list) have to be stored in a node.
(118) The terminal optimization according to the invention overcomes this problem by marking a node, preferably each node in the trie which has only one child node and all whose descendant nodes have at most one child node as a terminal-branch node, by a bitmap with no bits set. The invention uses the special quality of the bitmap comprised by the standard nodes of the preferred embodiments that they always have at least one bit set. This is because a node with an all-zero bitmap would be one without a child node, but a node without child nodes does not need to be represented in memory. Therefore, a special meaning can be attributed to a bitmap where no bit is set, and the bitmap of the terminal-branch node can have the same length or format as a bitmap comprised by a parent node which has more than one child node.
(119) The value of the key portion associated with a descendant node, preferably each descendant node, of a terminal-branch node, preferably of each terminal-branch node, is not determined by the value of a bit (set) in a bitmap comprised by the parent node of the descendant node. Rather, the value of the key portion is encoded such that its representation requires less memory space than a bitmap comprised by a parent node which has more than one child node. Typically, the value of the key portion will be encoded as a binary number (numeral), such as an integer value. For example, where the bitmap comprised by a standard node has 32, 64, 128 or 256 bits, respectively, the key portion associated with a descendant node of a terminal-branch node is encoded by 5, 6, 7, or 8 bits, respectively.
(120) The general storage configuration of a terminal optimization according to the preferred embodiment of the invention is shown in
(121) A terminal branch node and/or its descendent nodes do not need to comprise a pointer to their one child node (if any) because the child node can be stored in a predefined position in memory relative to the parent node, preferably directly behind the parent node, as is shown in
(122) As will become apparent from the example illustrated in
(123) The second space optimization according to the invention is illustrated in
(124) Trie 1210 comprises a first node 1211 having only one single child, as indicated by the bitmap of node 1111, in which only one bit is set (1) and all other bits are unset (0). The one bit which is set has the value “60”, as can be seen from the fact that it is the fourth bit from the left in the 64-bit wide bitmap, in which the rightmost bit has a value of “0” and the leftmost bit has a value of “63”. Node 1211 comprises one single pointer 1213, a long integer which points to node 1211's child node, node 1212. As is indicated by the three dots (“ . . . ”) between node 1211 and node 1212, node 1112 will typically not be stored in a memory location directly behind node 1111, but could be stored anywhere in the array of long integers. Node 1212 also has one child node, as is indicated by the second bit from the right which is set in the 64-bit wide bitmap of node 1212, the bit with value “01”. However, since the child node of node 1212 is a leaf node, node 1212 does not comprise a pointer to its child node, but a leaf part 1214, which may be a pointer or value for a map (see
(125) As can be observed, node 1211 is a terminal-branch node because it has only one child node 1212, and all its descendant nodes (1212 and 1212's child node) have at most one child node (node 1212 has one child node, and node 1212's child node has zero child nodes). Trie 1220 is obtained from trie 1210 as a result of the application of terminal optimization. Node 1221 of trie 1220, which corresponds to node 1211 of trie 1210, has been marked as a terminal-branch node by providing it with a 64-bit wide bitmap in which no bit is set. The value of the key portion associated with its child node 1222, which corresponds to child node 1212 of trie 1211, is not determined by the value of a bit (set) in the bitmap of node 1221. Rather, the value of the key portion is encoded as a binary number, such as an integer, which is comprised by node 1221, as is indicated by the number “60” in
(126) Terminal branch node 1221 does not comprise a pointer to its child node 1222. Rather, child node 1222 is stored in a predefined position in memory relative to its parent node 1221, namely directly behind the parent node. Node 1222, which is a descendant node of terminal branch node 1221, does not comprise a bitmap, nor a pointer to its child node, but only a binary number encoding the value of the key portion associated with the child node of node 1222, as is indicated by the number “01” in
(127) In the example embodiment of
(128) Where like in the preferred embodiments an array of long integers is used for storing the trie, terminal optimization according to the invention suffers from alignment losses. In the worst case, one 6-bit key portion is stored in a 64-bit long integer. However, experiments showed that on average, 50% of the space used for storing the descendant nodes of terminal branch nodes is occupied. Furthermore, the terminal optimization still requires much less space than storing several single-child nodes with pointers or with chained node optimization.
(129) A method for accessing standard nodes, nodes optimized by chained node optimization and nodes optimized by terminal optimizations in a uniform fashion will now be sketched with reference to
(130) The difficulty which had to be overcome was how to handle the three cases in a unified, central place and not having to deal with them separately in many places in the code. According to the solution found by the inventor, and as shown in
(131) Since nodeRef always points to the first bitmap, it is used to detect the three cases in the implementation of getBitSet( ) and getChildNode(bitNum): If the bitmap has more than one bit set, it belongs to a regular node. getBitSet( )returns that bitmap; getChildNode(bitNum) determines the idx (pointer to child node) and returns a new CDBINodeMem with nodeRef set to it (and idxlnNode set to 0). If the bitmap is 0 (no bit set), it belongs to a terminal branch node. getBitSet( )converts the literally stored 6-bit-value at the idxlnNode position into a bitmap and returns it; getChildNode(bitNum) returns a new CDBINodeMem with the same nodeRef and idxlnNode+1. If the bitmap has one bit set, it belongs to a chained node. getBitSet( ) returns the bitmap at the idxlnNode position; getChildNode(bitNum) again returns a new CDBINodeMem with the same nodeRef and idxlnNode+1. CDBINodeMem can also be used as a flyweight pattern by not creating a new child node, which is time-expensive, but just updating nodeRef and idxlnNode (gotoChildNode method), i.e. by modifying an existing object which functions as a proxy.
(132)
(133) To measure the space requirements for the data structures according to various embodiments of the invention, experiments were conducted in which a random set of long integers with full long integer value range was stored.
(134) It could be observed that chained node optimization alone reduced the space requirement by about 40%, and terminal optimization alone by about 60-75%. The combined chained node and terminal optimizations did not provide a visible space improvement compared to terminal optimization alone (the graph overlaps with the terminal optimization case). However, empirical measurements performed by the inventor showed that it is still worth applying both optimizations together. When chained node optimization is applied in addition to terminal optimization, performance increases because less pointers have to be followed, and the data locality is better and honors the memory hierarchy (CPU caches).
(135) Bitmap Compression
(136) A third space optimization of the present invention provides for a more compact representation of the trie in memory where the trie is sparsely populated. It can reduce memory space of bitmaps (e.g. bitmaps indicating key portion values of the child nodes) by grouping and efficiently storing sections of a same value (e.g. sections having the value 0 in the case of sparsely populated nodes or sections having the value 1 in the case of heavily populated nodes). This third space optimization is referred to herein as “bitmap compression”.
(137) The third space optimization of the present invention applies to a trie comprising one or more nodes, wherein a node, preferably at least each parent node which has more than one child node, comprises a bitmap in the form of a logical bitmap and a number of pointers, wherein each pointer is associated with a bit set in the logical bitmap and points to a child node of the node. The logical bitmap may correspond to the bitmap comprising key portion values, as mentioned with regard to other aspects of the invention. The optimization is achieved by the fact that the logical bitmap is divided into a plurality of sections and encoded by a header bitmap and a number of content bitmaps, wherein each section is associated with a bit in the header bitmap, and wherein for each section of the logical bitmap in which one or more bits are set, the bit associated with the section in the header bitmap is set and the section is stored as a content bitmap.
(138) Using a header bitmap and a number of content bitmaps to store a logical bitmap can reduce the required memory space significantly by omitting content bitmaps for sections of the logical bitmap in which no bit is set. In other words, only content bitmaps (i.e. sections of the logical bitmap) having at least one set bit are stored in memory. In a worst-case scenario, in which each section of a logical bitmap has at least one set bit, memory usage will slightly increase, as an additional header bitmap needs to be stored. However, nodes are generally sparsely populated, and thus typically less memory is required when using bitmap compression.
(139) An embodiment of bitmap compression according to the invention is illustrated in
(140) The parent node in both tries 1601, 1611 further comprises pointers 1603 to 1605. In trie 1601, each pointer is associated with a bit 1606 to 1608 set in the logical bitmap 1602. In trie 1611, the pointers 1603 to 1605 are associated with bits 1616 to 1618 set in the content bitmaps.
(141) The logical bitmap in trie 1601 is converted into the header bitmap 1612 and the content bitmaps 1613, 1614 in the lower part 1611 by dividing the logical bitmap 1602 into sections 1621 (e.g. of 8 bits) and storing the sections 1622, 1623 which have at least one bit set as content bitmaps 1613, 1614. Sections having no bit set are not stored as content bitmaps. Each bit in the header bitmap 1612 represents a different section of the logical bitmap. The content bitmaps 1613, 1614 are referenced by respective bits 1619, 1620 set in the header bitmap 1612. The content bitmaps 1613, 1614 may be stored in the same order (not shown) or in the inverse order in which the set bits 1619, 1620 associated with their sections are arranged in the header bitmap 1612. In other words, the rank of a content bitmap within all content bitmaps of the logical bitmap may correspond to the rank of the set bit associated with the section of the content bitmap, within all set bits in the header bitmap. In this way, the content bitmaps can easily be addressed while processing the trie. Also, the sections of the logical bitmap are preferably all coherent in memory. Thus, the entire logical bitmap can be represented coherently in memory by a header bitmap followed by a number of content bitmaps.
(142) In a preferred embodiment, all sections have the same size. Sections of the same size allow an efficient processing of the compression and decompression of a logical bitmap, as no further information on the structure of the sections is necessary. Also, the header bitmap may be of the same size as the sections.
(143) Different structures for storing the header bitmap and content bitmaps can be used. The header bitmap and the content bitmaps of the logical bitmap may be stored in an array, in a list, or in consecutive physical or virtual memory locations. When the header bitmap and the content bitmaps have the size of one byte, as shown in
(144) The afore-described bitmap compression can also be applied to pointers, like the pointers used for referencing child nodes, and can also be applied to inlined leaf bitmaps. This will typically further improve space efficiency but it hurts performance because the variable size encoding makes it necessary to iterate through the pointers when calculating the offset for a certain pointer.
(145) The bitmap compression may be combined with the other aspects of the invention. For example, in combination with the pointer reduction, terminal-branch nodes according to the invention which are marked by a (logical) bitmap with no set bits set may be encoded as just a header bitmap and without any content bitmaps.
(146)
(147) Key Encoding
(148) The present invention provides way of storing different primitive data types for the keys, with fixed or variable sized keys (e.g. character string), as well as composite keys comprising two or more items of primitive data types in a trie.
(149) Keys Comprising Control Information
(150) In the preferred embodiments of the invention, keys can be encoded in such a flexible way that they can be iterated through, e.g. by a cursor, even without previous knowledge about the number, the data types, or the length of the components stored in a key.
(151) These embodiments apply to a trie for use in a database application or information retrieval system, e.g. a trie or trie data structure in accordance with one of the embodiments of tries and trie data structures as described above. The trie comprises one or more nodes, wherein a node, preferably each child node, is associated with a key portion, and the path from the root node to another node in the trie, in particular to a leaf node, defines a key with which the node is associated, the key being a concatenation of the key portions associated with the nodes on the path. The above-mentioned flexibility is achieved by the fact that in addition to content information, the key comprises control information.
(152) The key will typically comprise one or more key parts, wherein each key part comprises content information, which is a part of the overall content information comprised by the key. For each of the key parts, the control information preferably comprises a data type information element specifying the data type of the content information comprised by the key part.
(153) There are in principle two ways of arranging the control information and the content information associated with a key part. A first way is shown in
(154) A second way arranging the control information and the content information associated with a key part is shown in
(155) The data type of content information associated with a key part may be of fixed size, such as in the case of an integer, long integer, or a double precision floating point or a time/date primitive, or it may be of variable size, such as in the case of a character string, e.g. a Unicode character string, or a variable precision integer. In some embodiments of the invention, the key comprises two or more key parts comprising content information of different (primitive) data types.
(156) As will be explained below with reference to
(157) The content information of a key part may be contained by one single key portion, but typically it is contained by two or more key portions. For fixed size key parts, the number of key portions required to contain the content information comprised by a key part is typically known. Where the data type of the content information comprised by a key part is a data type of variable size, the end of the content information element may be marked by a specific symbol, e.g. null-terminated strings having a null character (‘\o’, called NUL in ASCII) as last the character for strings. Alternatively and preferably, it may be marked by a specific bit in a specific one of the key portions containing the key part, as will be explained below for Unicode character strings with reference to
(158) Although as mentioned above the content information of a key part will oftentimes be contained by two or more key portions, a key portion preferably does not contain content information of two or more key parts. In other words, the content information of the key parts is aligned with the borders of the key portions. Similarly, a key portion preferably does not contain information of two or more control information elements like data type information elements, key part counts, or information on whether the trie is used for storing a dynamic set or an associative array. This approach makes the implementation easier and more efficient, usually without significant alignment losses. Furthermore, it allows storing the content information of different key parts in an interleaved manner, as will be explained below.
(159) An example of a key encoding according to the invention is shown in
(160) As mentioned above, in the preferred embodiments of the invention, each parent node in the trie comprises a 64 bits wide bitmap, and therefore each key portion in the trie is capable of storing a 6-bit value. The information 2011 on whether the trie is used for storing a dynamic set or an associative array is stored by a first key portion, and therefore 6 bits are used for this information. In fact, 1 bit would have been sufficient for this yes/no information, but for the alignment reasons mentioned above, an entire key portion capable of storing a 6-bit value is used. The information is coded in node 2041, comprising a 64 bits wide bitmap in which a respective bit is set, and a pointer (idx) to the respective child node of node 2041.
(161) Each of the data type information elements 2012, 2013 is also stored by one key portion, whose values are coded in the bitmaps of nodes 2042, 2043. 5 bits are used for the data type information, which allows for 32 different type identifiers. The 6.sup.th bit which can be stored by the respective key portion, e.g. the high bit of the key portion, is used for indicating whether or not the key part associated with the data type information element is the last key part in the key. In the example of
(162) The content information comprised by each of the key parts is also broken down into values 2021, 2022 of generally 6 bits, and each of the values is stored by one key portion. The nodes whose bitmaps are used to code (6-bit) values 2021, 2022 are not shown in
(163)
(164) The dynamic set identifier is a 6-bit number of value 0 (0×00). Consequently, the bitmap of root node 2100 of the trie of
(165) Integer value “100” is coded in 32-bit binary as “00 000000 000000 000000 000001 100100”. Therefore, the key portions associated with nodes on levels 5 through 10 which are used for storing integer value “100” are associated with values 0 (0×00), 0 (0×00), 0 (0×00), 0 (0×00), 1 (0×01), and 36 (0×24), respectively.
(166) String value “ab” is coded as Unicode value for character “a” followed by Unicode value for character “b”. Each Unicode character is stored using 2-4 key portions, depending on the Unicode value, which may need 10, 15 or 21 bits. The coding scheme for Unicode characters used in the preferred embodiments of the invention is as follows:
(167) 10 bit Unicode character: 00xxxx xxxxxx
(168) 15 bit Unicode character: 010xxx xxxxxx xxxxxx
(169) 21 bit Unicode character: 011xxx xxxxxx xxxxxx xxxxxx
(170) The last character in a string is marked by setting the high bit, which results in the following coding scheme for the last character:
(171) 10 bit Unicode character: 10xxxx xxxxxx
(172) 15 bit Unicode character: 110xxx xxxxxx xxxxxx
(173) 21 bit Unicode character: 111xxx xxxxxx xxxxxx xxxxxx
(174) Unicode character “a” has the value 97 (0×61) and is coded in Unicode with 10 bits as “0001 100001”. According to the coding scheme used in the preferred embodiments, Unicode character “a” is coded as “000001 100001”. Unicode character “b” has the value 98 (0×62) and is coded in Unicode with 10 bits as “0001 100010”. According to the coding scheme used in the preferred embodiments, Unicode character “b” is coded as “100001 100010”, with high bit set because “b” is the last character in the string with value “ab”. Therefore, the key portions associated with nodes on levels 11 through 14 which are used for storing string value “ab” are associated with values 1 (0×01), 33 (0×21), 33 (0x21), and 34 (0×22), respectively.
(175) Interleaved Multi-Item Keys
(176) Embodiments of the present invention provide a way of storing data in trie such that queries involving more than one data item can be performed in a more efficient manner. The inventive approach is particularly useful for storing keys or keys and values in a database or information retrieval system such that they can be queried more efficiently, for storing result keys or keys and values of a database or information retrieval system query, or for storing input keys or keys and values for a database query, such that the query can be performed more efficiently.
(177) The inventive way of storing data uses a trie, such as tries with the data structures described above, the trie comprising nodes, wherein a node, preferably each child node, is associated with a key portion, and wherein the path from the root node to another node in the trie defines a key with which the node is associated, the key being a concatenation of the key portions associated with the nodes on the path. To achieve the performance gains in queries involving multiple data items, two or more data items are coded in a key, and at least one or two, preferably each of the data items consists of two or more components. The key contains two or more consecutive sections, at least one or two, preferably each of the sections comprising components of two or more of the data items coded in the key. An “item” is herein sometimes referred to as a “dimension”, and it may correspond to what was referred to as a “key part” or the “content information of a key part” above.
(178)
(179) According to preferred embodiments, the coding of the key is such that a section, preferably each of the sections of a key contains at least and/or at most one component from each of the data items coded in the key. For example, both sections S1 and S2 of the key shown in
(180) Furthermore, for two or more, preferably for all sections of a key, the components belonging to the different data items are ordered in the same sequence within the section. For example, in both sections of the key shown in
(181) Moreover, the order of the sections comprising the components of a data item preferably corresponds to an order of the components within the data item. For example, in the key shown in
(182) Two or more, preferably all of the data items of a key have the same number of components. For example, both items X and Y coded in the key shown in
(183)
(184) In the example of
(185) Where a data item is a number, a component of a data item may be a digit (like in the example of
(186) However, in the preferred embodiments, the components of a data item are bit groups of the binary encoding of the data item, the bit group preferably comprising 6 bits. This is because as explained above, in the preferred embodiments, the value of the key portion of a child node is determined by the value of a bit (set) in a bitmap comprised by the parent node with which bit the child node is associated. As a consequence, the size of the bitmap defines the possible alphabet for the key portion. For example, where each bitmap has a size of 64 bits, the amount of different values available for the key portion of a node is 2.sup.6. This means that bit groups comprising 6 bits of the binary encoding of the data item can be represented by the key portion associated with a node. Where 32-bit bitmaps are used, groups comprising 5 bits could be represented, etc.
(187) For example, where a data item is a 64-bit long integer, and each component is a 6-bit group of the binary encoding of the integer, the data item has 64/6=11 components. Where the data item is a character coded in Unicode, it may have 2 to 4 6-bit components as explained above. Where a data item is a string comprised of several characters, the components in the preferred embodiments are still 6-bit groups, i.e. a string, like any other data item, has the same type of components (6-bit groups). The number components of a string of characters corresponds to the number of components of a single character multiplied by the number of characters in the string.
(188) Instead of regarding the components of the preferred embodiments as bit groups, e.g. 6-bit groups, they could also be regarded as digits having a predefined radix or base, e.g. 64.
(189) The interleaved way of storing keys with multiple data items can greatly enhance the performance of range queries involving the multiple data items, as will become readily apparent from the below description of range queries with reference to
(190) Set Operations
(191) Embodiments of the present invention provide a time-efficient way to perform a query in a database or information retrieval system comprising operations such as intersection (Boolean AND), union (Boolean OR), difference (Boolean AND NOT) and exclusive disjunction (Boolean XOR) on two or more sets of keys stored in a database or information retrieval system, or sets of result keys of a database or information retrieval system query. These operations are here referred to as “set operations” or “logical operations”.
(192) Still most databases use the Volcano processing model which means “one tuple at a time”. However, this is not efficient for modern CPU architectures with multiple levels of caching and in-memory databases in mind. As all operators in the physical execution plan run tightly interleaved, the combined instruction footprint of the operators may be too large to fit into the instruction cache, and the combined state of the operators may be too large to fit into the data cache. Therefore, some databases apply an operator-at-a-time model or a combination of both, a vectorized execution model. The index data structure according to the present invention and unified level-by-level processing model results in a very lean instruction footprint regarding the access to the index trie and operator implementation.
(193)
(194)
(195)
(196) The iterator-based execution model provides a unified model for operators, which is independent from the data model of the data sources (database tables or database indexes) and unifies interim results of the operator nodes. However, only one unit of data, e.g. a record is delivered per operator invocation. This approach is inefficient for operators combining large sub result sets which themselves return a small result set.
(197) The tuple may be passed to other operators, as is shown in
(198) The tuple-at-a-time processing model has small intermediate results and hence low memory requirements. The operators in the execution plan run tightly interleaved and may be quite complex. However, the huge amount of function calls and the combined state of all operators causes a large function call overhead and instruction and data cache misses because their footprint is frequently too large to fit into the CPU caches.
(199) Both the iterator-based execution model and the tuple-at-a-time processing model require a sophisticated query optimizer to be efficient.
(200)
(201) The present invention solves the problems of the prior art by a novel execution model in which all data sources are tries. Two or more input tries are combined in accordance with the respective logical operation (set operation), to obtain the set of keys associated with the nodes of a respective resulting trie.
(202) A database query then provides as an output the set of keys associated with the nodes of the resulting trie, or a subset of the keys associated with the nodes of the resulting trie, in particular the keys associated with the leaves of the resulting trie, or a set of keys or values derived from the keys associated with the nodes of the resulting trie. Alternatively, it may provide other data items associated with the nodes of the resulting trie, like document identifiers. The set of keys provided as an output may be provided in a trie. It should be noted that the concept of a “resulting trie” is used herein to define the set of keys which needs to be obtained when combining the input tries using the logical operation. However, the resulting trie does not necessarily have to be formed in a physical trie data structure during the combination of the input tries, and the output set of keys may also be provided, e.g., by a cursor or iterator.
(203) If the logical operation is a difference (AND NOT), the parent nodes in the resulting trie are the parent nodes in the first input trie, and the leaves of a parent node of the resulting trie are the AND NOT combination of the set of child nodes of the corresponding parent node in the first input trie and the sets of child nodes of the corresponding parent nodes in the other input tries, if any. If the logical operation is not a difference, e.g. if the logical operation is an intersection (AND), union (OR), or exclusive disjunction (XOR), the set of child nodes of each node in the resulting trie is the combination, using the logical operation (e.g. AND, OR, or XOR), of the sets of child nodes of the corresponding nodes in the input tries. In this context, since each child node is associated with a key portion, and the path from the root node to another node in the trie defines a key with which the node is associated, the key being a concatenation of the key portions associated with the nodes on the path, two or more nodes of different tries “correspond” to each other if the keys associated with the nodes of the different tries are identical.
(204) In preferred implementations, every operator itself appears again as a trie to its consumer, up to the root operator node in the query execution plan tree, e.g. by implementing a respective trie (node) interface. Thus, instead of using an iterator-interface, a node interface can be used. This allows for functional composition and a simpler and cleaner software architecture, and it further improves the performance of the database engine because the lower implementation complexity directly results in less function call overhead and less data and instruction cache misses.
(205) Preferably, the data structures for implementing the tries are as described above. In particular, it is advantageous if a node in an input trie, preferably at least all parent nodes in an input trie comprise a bitmap, and the value of the key portion of a child node in a trie is determined by the value of a bit (set) in the bitmap comprised by the parent node with which bit the child node is associated. In such an implementation, the combination of child nodes of the input tries can easily be performed by combining the bitmaps of each of the child nodes of the input tries, using logical operations, such as bitwise AND, bitwise OR, bitwise AND NOT, or bitwise XOR. A combined bitmap is obtained, and the result of the combination is performed on the basis of the combined bitmap.
(206) Thus, the physical algebra in the implementation of the tries corresponds directly to the logical algebra for the set operations. Whereas in the prior art, bitmaps are used in tries only for reducing the memory space required for pointers, the present invention takes advantage of the bitmaps for performing set operations on tries.
(207) As mentioned above, an exemplary implementation of a trie node interface called “CDBINode” has the following main methods: getBitSet( )—returns a bitmap with bits set for all non-empty child pointers of a trie node; and getChildNode(bitNum)—returns the child node for the given node-branch as specified by the bit number.
(208)
(209)
(210) As can be observed, the set of child nodes of each node in the resulting trie is the AND combination of the sets of child nodes of the corresponding nodes in the input tries. For example, the root node of resulting trie 3005 has one child node, associated with key “1”. This one child node is obtained when forming the intersection of the set of child nodes (“1”, “5”) of the root node of input trie 3001 and the set of child nodes (“1”, “6”) of the root node of input trie 3002. Furthermore, the node associated with key “1” also has one child node, which is associated with key “13”. In fact, node “13” is obtained when forming the intersection of the set of child nodes (“13”, “14”) of node “1” of input trie 3001 and the set of child nodes (“13”, “15”) of the corresponding node “1” of input trie 3002.
(211) Thus, a resulting trie of an intersection operation, here resulting trie 3005, comprises all nodes and only the nodes which are comprised by each of the input tries, here input tries 3001, 3002. In particular, the set of leaf nodes of the resulting trie, here the node associated with key “13”, comprises all leaf nodes and only the leaf nodes which are comprised by each and all of the input tries.
(212) The algorithm performed by a preferred embodiment of the intersection operator 3003 can be described in pseudo code as follows:
(213) TABLE-US-00001 1. nodeA = root node of trie A 2. nodeB = root node of trie B 3. getBitSet of nodeA −> 00100010 4. getBitSet of nodeB −> 01000010 5. bitwise and −> 00100010 6. for all set bits nodeA = getChildNode of nodeA nodeB = getChildNode of nodeB if leaf node perform bitwise and else recursion (step 3)
(214) In this preferred embodiment, all trie nodes comprise bitmaps as described above. Furthermore, the tries are formed by nodes implementing an interface comprising the getBitSet and getChildNode methods as described above. A bitwise AND operation is performed between the bitmaps of corresponding nodes of the two input tries to determine the set of child nodes which the two corresponding nodes have in common.
(215) As will be shown in the following with reference to
(216)
(217)
(218)
(219) Finally,
(220) The example of
(221)
(222) As can be observed, the set of child nodes of each node in the resulting trie is the OR combination of the sets of child nodes of the corresponding nodes in the input tries. For example, the root node of resulting trie 3605 has three child nodes, associated with keys “1”, “5”, and “6”. These three child nodes are obtained when forming the union of the set of child nodes (“1”, “5”) of the root node of input trie 3001 and the set of child nodes (“1”, “6”) of the root node of input trie 3002. The node associated with key “1” also has three child nodes, which are associated with keys “13”, “14”, and “15”. In fact, these nodes are obtained when forming the union of the set of child nodes (“13”, “14”) of node “1” of input trie 3001 and the set of child nodes (“13”, “15”) of the corresponding node “1” of input trie 3002. Finally, the nodes in the resulting trie associated with keys “5” and “6”, respectively, each have one child node, associated with keys “55” and “64”, respectively, which are the child nodes of the corresponding nodes of the input tries 3001 and 3002, respectively.
(223) Thus, the resulting trie of a union operation, here resulting trie 3605, comprises all nodes which are comprised by any of the input tries, here input tries 3001, 3002. In particular, the set of leaf nodes of the resulting trie, here the nodes associated with “13”, “14”, “15”, “55”, and “64”, comprises all the leaf nodes which are comprised by any of the input tries.
(224) The algorithm performed by a preferred embodiment of the union operator 3503 can be described in pseudo code as follows:
(225) TABLE-US-00002 1. nodeA = root node of trie A 2. nodeB = root node of trie B 3. getBitSet of nodeA −> 00100010 4. getBitSet of nodeB −> 01000010 5. bitwise or −> 01100010 6. for all set bits if bit set in nodeA and nodeB nodeA = getChildNode of nodeA nodeB = getChildNode of nodeB if leaf node perform bitwise or else recursion (step 3) if bit set in nodeA only nodeA = getChildNode of nodeA recurse only TrieA (skipping bitwise or) if bit set in nodeB only nodeB = getChildNode of nodeB recurse only TrieB (skipping bitwise or)
(226) Again, all trie nodes comprise bitmaps as described above, and the tries are formed by nodes implementing an interface comprising the getBitSet and getChildNode methods as described above. A bitwise OR operation is performed between the bitmaps of corresponding nodes of the two input tries to determine the set of child nodes comprised by any of two corresponding nodes. If a bit is set in the bitmap of only one of two corresponding nodes, the sub-trie depending from that one node is added to the resulting trie, which in the above pseudo code is indicated by “recurse only TrieA”/“recurse only TrieB”.
(227)
(228) As can be observed, all parent nodes of the resulting trie 3705 correspond to the parent nodes of the first input trie 3001. The leaf nodes depending from a parent node of the resulting trie 3705 are the AND NOT combination of the set of child nodes of the corresponding parent node in the first input trie 3001 and the sets of child nodes of any corresponding parent node in input trie 3002.
(229) For example, the root node of resulting trie 3705 has two child nodes, associated with keys “1” and “5”, which themselves are parent nodes. These two nodes correspond to the two child nodes of the root node of input trie 3002, which themselves are parent nodes. The node associated with key “1” has one child node, which is a leaf node and associated with key “14”. This leaf node is obtained when forming the difference of the set of child nodes (“13”, “14”) of node “1” of the first input trie 3001 and the set of child nodes (“13”, “15”) of the corresponding node “1” of input trie 3002. Finally, the node in the resulting trie associated with key “5” has one child node, which is associated with key “55” and corresponds to the child of the node with key “5” of the first input trie 3001. This node with key “5” has no corresponding node in input trie 3002.
(230) Thus, the resulting trie of a difference operation, here resulting trie 3605, comprises all parent nodes which are comprised by the first input trie, here input trie 3001. The set of leaf nodes of the resulting trie, here the nodes associated with keys “14” and “55”, comprises all the leaf nodes of the first input trie, here trie 3001, minus the leaf nodes of the second input trie, here trie 3002.
(231) The algorithm performed by a preferred embodiment of the difference operator 3703 can be described in pseudo code as follows:
(232) TABLE-US-00003 1. nodeA = root node of trie A 2. nodeB = root node of trie B 3. getBitSet of nodeA −> 00100010 4. getBitSet of nodeB −> 01000010 5. bitset of nodeA −> 00100010 6. for all set bits if bit set in nodeA and nodeB nodeA = getChildNode of nodeA nodeB = getChildNode of nodeB if leaf node perform bitwise and-not else recursion (step 3) if bit set in nodeA only nodeA = getChildNode of nodeA recurse only TrieA (skipping bitwise and-not)
(233) Again, all trie nodes are formed and implement the interface as described above. If a bit is set in the bitmap of corresponding nodes of both input trie 3001 and 3002, there is recursion on both tries. If a bit is set only in the bitmap of the node of the first input trie 3001, the sub-trie depending from that node is added to the resulting trie, which in the above pseudo code is indicated by “recurse only TrieA”. Bits set only in the bitmap of the node of trie 3002 are ignored. A bitwise AND NOT operation is only performed between the bitmaps of corresponding nodes of the two input tries if their child nodes are leaf nodes.
(234) The execution of the operators comprises is a recursive descent over the trie levels (in the preferred implementation, each level is one digit of radix/base 64). At each level, the bitmap of each node is used as result prediction followed by an iteration through the predicted bits. Thus, combining the input tries comprises performing a combination function for the root node of the resulting trie. Performing the combination function for an input node of the resulting trie comprises determining the set of child nodes for the input node of the resulting trie (which may also be empty), by combining the sets of child nodes of the nodes of the input tries which correspond to the input node of the resulting trie, using the logical operation, and performing the combination function for each of the child nodes determined for the input node of the resulting trie. As already mentioned above, the root node and/or an input node of the resulting trie do not have to be generated physically.
(235) The step of combining the input tries may be performed using a depth first traversal, a breadth first traversal, or a combination thereof. Combining the input tries in depth first traversal comprises performing the combination function for one of the child nodes of the input node and traversing the sub-trie formed by that child node before the combination function is performed for the next sibling node of that child node. Combining the input tries in breadth first traversal comprises performing the combination function for each of the child nodes determined for the input node of the resulting trie and determining a set of child nodes for each of the child nodes determined for the input node of the resulting trie before performing the combination function for any of the grandchild nodes of the input node of the resulting trie.
(236) One or more of the input tries for a set operation may be a virtual trie, i.e. a trie which is dynamically generated on demand during the operation of combining the input tries. Typically, only those parts of the virtual trie are dynamically generated which are required for combining the input tries using the logical operation. There are several scenarios for the application of a virtual input trie, one of them being the implementation of a database range query, which will be described in the following.
(237) Range Queries
(238) The combination of two or more input tries by an intersection operation (Boolean AND) can advantageously be used for performing range queries in an efficient manner. A “range” can be described as a set of discrete ordered values comprising all the values between a first value and a second value of a certain data type, wherein the first and/or second values may or may not be included in the range. A range query returns the keys within a set of keys whose values correspond to (match) one or more specified ranges of values.
(239) A range query according to the present invention is performed by an intersection operation of a trie which stores a set of keys to be searched for the one or more ranges (hereinafter “input set trie”), with a trie which stores all the values included in the one or more ranges (hereinafter “range trie”). The tries are preferably implemented as has been described above. The set of keys to be searched are typically associated with the nodes of the input set trie, and the values (keys) indicating the range of values to match are typically associated with the nodes of the range tries, in particular with the leaf nodes of the range tries. The set of keys to be searched is typically a set of keys stored in a database or a set of result or input keys of a database query, or a set of keys stored in an information retrieval systems or a set of result or input keys of an information retrieval system query.
(240) A definition of one or more ranges for performing the query is obtained by user input or otherwise. The definition is used to generate the range trie, wherein the values associated with nodes (typically the leaf nodes) of the range trie correspond to the values comprised by the one or more ranges. In a next step, the input set trie is combined with the range trie using by an intersection operation as described above, to obtain the set of keys associated with the nodes of a resulting trie. Finally, the set of keys associated with the nodes of the resulting trie, or a subset of the keys associated with the nodes of the resulting trie, in particular the keys associated with the leaf nodes of the resulting trie, or a set of keys or values derived from the keys associated with the nodes of the resulting trie, are obtained as an output.
(241)
(242)
(243) The algorithm performed by intersection operator 3903 can be described in pseudo code as follows:
(244) TABLE-US-00004 1. nodeA = root node of trie A (the input set trie) 2. nodeB = root node of trie B (the range trie) 3. getBitSet of nodeA −> 00100010 4. getBitSet of nodeB −> 01111110 5. bitwise and −> 00100010 6. for all set bits nodeA = getChildNode of nodeA nodeB = getChildNode of nodeB if leaf node perform bitwise and else recursion (step 3)
(245) Range trie 3902 is an example which shows that the range trie may comprise very many nodes. Materializing range trie 3902 with all its nodes would thus be costly in terms of time and memory space. For this reason, the range trie may be implemented as a virtual trie, i.e. a trie which is dynamically generated on demand during the intersection operation. This is indicated in
(246) During the intersection operation, the operator accesses and the virtual range trie delivers “on the fly” the components required for traversing the trie, through the application programming interface (API). E.g., the bitmap of the current node may be accessed through the getBitSet( ) method and a child node through the getChildNode( ) method introduced above. The API returns the respective bitmap on the one hand and—instead of the child node of a real trie—an object on the other hand which will provide the respective bitmap for the next recursion. For the operator, the virtual trie looks just like a real, physically implemented trie.
(247) Typically, only those parts of a virtual range trie are dynamically generated which are required for combining the input set trie and the range trie by the intersection operation. In the example of
(248) In some embodiments of the range query according to the invention, like the embodiment illustrated in
(249) Multidimensional Range Query Processing
(250) In other embodiments of the range query according to the invention, the keys associated with the leaf nodes of the input set trie code two or more data items of a specific data type. In this case, the definitions of one or more ranges comprise definitions of one or more ranges for one or more of the data items. Such embodiments can also be referred to as “multi-dimensional” range queries. While in principle it is possible to execute a range query for each dimension and perform an intersection of the results, this will not be efficient as too many tries and too many operators would be involved.
(251) An example for an efficient multi-item or multi-dimensional range query processing according to the invention is illustrated in
(252) Input set trie 4001 has a root node on level 1. The bitmap associated with the root node indicates the value of the first digit of the x-dimension. Bits “1” and “5” are set in the bitmap associated with the root node, which indicates that the first digit of the x-dimensions of the keys stored in the input set trie is either “1” or “5”. The bitmaps associated with the nodes on level 2 indicate the value of the first digit of the y-dimension. Bits “3” and “4” are set in the bitmap associated with the node on level 2 which depends from bit “1” of the root node, and bit “6” is set in the bitmap associated with the node on level 2 which depends from bit “5” of the root node. This indicates that the first digit of the y-dimension of the keys whose x-dimension starts with a “1” is either “3” or “4”, and the first digit of the y-dimension of the keys whose x-dimension starts with a “5” is “6”. The bitmaps associated with the nodes on level 3 indicate the value of the second digit of the x-dimension. The bits set in these bitmaps indicate that there are keys with x-dimensions “12” and “16” whose y-dimension starts with “3”, keys with x-dimensions “12” and “15” whose y-dimension starts with “4”, and keys with x-dimensions “56” whose y-dimension starts with “6”. The bitmaps of the nodes on level 4, and the nodes on level 5 are not shown in
(253) The range trie for a multi-item or multi-dimensional range query may be a multi-item range trie obtained by combining a single-item or one-dimensional range trie for each of the data items coded by the keys associated with the leaves of the input set trie, which single-item range trie for a data item stores all the values included in one or more ranges of the data item. A single-item range trie may be a virtual range trie as described above. This means that only those parts of a virtual single-item trie are dynamically generated which are required for combining the single-item range tries to obtain the multi-item range trie, or for combining the input set trie and the single-item tries by the intersection operation.
(254) In the example of
(255) In some multi-dimensional range queries, for some of the data items (dimensions) no definition of a range may be obtained. E.g., a user may specify only a range [15 . . . 55] for the x-dimension for performing a range query processing on the two-dimensional input set trie 4001 of
(256) The multi-item or multi-dimensional range trie which is obtained from the combination of the single-item or one-dimensional range tries typically stores all combinations of the values of the data items stored in the single-item (one-dimensional) range tries. E.g., if the range for an x-dimension is [11 . . . 13], and the range for a y-dimension is [7 . . . 8], the combined two-dimensional range trie stores the keys for the (x, y) value pairs (11, 7), (11, 8), (12, 7), (12, 8), (13, 7), and (13, 8).
(257)
(258) In the preferred embodiments of the invention, and this is true for both for one-dimensional and multi-dimensional range queries, the range trie has the same structure or format as the input set trie. Thus, where a multi-dimensional input set trie stores the data items in an interleaved manner, the multi-dimensional range trie preferably uses interleaved storing, and where the input set trie stores the data items in a non-interleaved manner, the multi-dimensional range trie preferably also does not use interleaved storing. Furthermore, the keys associated with the leaves of a range trie preferably code the data items of the same data type as the keys associated with the leaves of the input set trie. Finally, in a range trie, a data item of a certain data type or a component of such a data item is preferably coded in nodes of the same level as the corresponding data item or component of the data item in the input set trie.
(259) In some embodiments of the multi-item or multi-dimensional range query processing, the combining of the single-item or one-dimensional range tries to obtain a multi-item or multi-dimensional range is performed by a function which provides the multi-item range trie as an input to the function (e.g. an intersection operator) which implements the combining of the input set trie with the multi-item range trie. This is shown in the example of
(260) In other embodiments, the combining of the single-item or one-dimensional range tries to obtain a multi-item or multi-dimensional range trie is performed within the function or operator which implements the intersection of the input set trie with the range trie. In this case, the multi-dimensional range trie will exist only conceptually. In fact, the function or operator which implements the combining of the input set trie with the range trie accesses the (virtual) one-dimensional range tries such as if they together formed a (virtual) multi-dimensional range trie. If there are dimensions for which no range is specified, these dimensions are skipped or ignored by the function or operator which implements the intersection of the input set trie with the range trie, e.g. by creating a wildcard trie as described above.
(261) In the example of
(262) TABLE-US-00005 1. nodeA = root node of trie A (the input set trie) 2. nodeB = root node of trie B (range for x-dimension) 3. nodeC = root node of trie C (range for y-dimension) 4. getBitSet of nodeA −> 00100010 5. getBitSet of nodeB −> 00111110 6. bitwise and −> 00100010 7. for all set bits nodeA = getChildNode of nodeA, 8. getBitSet of nodeA −> 00011000 9. getBitSet of nodeC −> 00001000 10. bitwise and −> 00001000 11. for all set bits Get child node of child nodeA, nodeB = getChildNode of nodeB nodeC = getChildNode of nodeC if leaf node perform bitwise and else recursion (step 4)
(263) The (virtual) multi-dimensional range trie is created conceptually in that the set of child nodes of each node in the resulting trie would be the result of the AND combination of the sets of child nodes of the corresponding nodes in the input set trie and the multi-dimensional range trie, if the one-dimensional range tries were actually combined to obtain a (virtual) multi-dimensional range trie, at least if the multi-dimensional range trie has the same structure or format as the input set trie.
(264) E.g.,
(265) Storing the different dimensions or items of a multi-dimensional or multi-item input set trie in an interleaved manner will in many cases lead to more efficient range queries, as will now be explained with reference to
(266)
(267) The nodes which are traversed for a two-dimensional range query with ranges X=[15 . . . 55] and Y=[30 . . . 31] when performing the AND combination of the input set trie 4501 with a respective (likewise non-interleaved) two-dimensional range trie in accordance with the present invention are shaded in
(268) In comparison,
(269) The reason for this is that while in non-interleaved input set trie 4501 all x-values that fall within the range of [15 . . . 55] are determined up to the last (the second) digit, in the interleaved input set trie 4001, nodes not worth traversing can be eliminated more quickly by having a look at the first digit of the y-dimension. The chances of eliminating nodes by looking at the first digit of another dimension are higher than the chances of eliminating nodes by looking at a further digit of the same dimension. As will be understood, the more digits the different dimensions have, the higher will be the performance gains of interleaved storing.
(270) As mentioned above, a range query processing may provide as an output a set of keys associated with the leaves of the input set trie, e.g. in case of a one-dimensional range query, or if the user is interested in all dimensions of multi-dimensional keys stored in an input set trie. Alternatively, the range query processing may provide as an output a set of reduced-item keys coding a subset of the data items coded by the keys associated with the leaves of the input set trie. An example for this is shown in
(271) In
(272) Like one-dimensional range tries 4002 and 4003 of
(273) In contrast to intersection operator 4004 of
(274) Where a range query processing provides as an output a set of reduced-item keys, like in
(275) In the example of
(276) An algorithm performed by two-dimensional intersection operator 4004 outputting only x-values can be described in pseudo code as follows:
(277) TABLE-US-00006 1. nodeA = root node of trie A (the input set trie) 2. nodeB = root node of trie B (wildcard trie for x-dimension) 3. nodeC = root node of trie C (wildcard trie for y-dimension) 4. getBitSet of nodeA −> 00100010 5. getBitSet of nodeB −> 11111111 6. bitwise and −> 00100010 7. for all set bits nodeA = getChildNode of nodeA, 8. getBitSet of nodeA −> 00011000 9. getBitSet of nodeC −>11111111 10. bitwise and −> 00011000 11. for all set bits Get child node of child nodeA, nodeB = getChildNode of nodeB nodeC = getChildNode of nodeC if leaf node perform bitwise and write result key (x only) to output trie else recursion (step 4)
(278) In the example of
(279) Fuzzy Search
(280) A frequent requirement for text retrieval applications is to provide an approximate string matching—also called fuzzy search capability. That is finding strings that match a pattern approximately rather than exactly.
(281) The typical measurement for this “fuzziness” (difference between two character sequences) is the Levenshtein distance. The Levenshtein distance between two strings is the minimum number of single-character edits (character insertions, deletions or substitutions) required to change one string into the other.
(282) Similar to the virtual range tries discussed above, one aspect of the present invention is directed to a preferably virtual fuzzy-match trie which is intersected using the Boolean AND with a storage trie like an index trie to return matching key strings or documents comprising matching key strings. An index trie may store each occurring term and the document ID as two key parts (character string, long) as described above.
(283) According to this aspect of the invention, data is retrieved from an electronic database or information retrieval system by performing approximate string matching. First, a search string of characters is obtained. Next, a match trie which stores a set of approximate character strings comprising the search string and/or variations of the search string is built. The match trie is combined, using an intersection operation, with a storage trie storing a set of character strings stored in the electronic database or information retrieval system or of result character strings of an electronic database or information retrieval system query. The storage trie may be an index trie, for example storing character strings comprised by documents and the respective document identifier as two key parts, such as (character string, long).
(284) Like in the intersection of tries described above, a resulting trie, is obtained. The set of child nodes of each node in the resulting trie is the intersection of the sets of child nodes of the corresponding nodes in the match trie and in the storage trie, wherein nodes of different tries correspond to each other if a same key is associated with the nodes of the different tries. Typically, the match trie, the storage trie and the resulting trie have the same structure or format. Unless otherwise stated in this section, all aspects of intersection operations on tries discussed above also apply to intersection of tries in the context of fuzzy search.
(285) As described above, a trie comprises one or more nodes, each child node is associated with a key portion, and a path from the root node to another node in the trie defines a key with which the node is associated, the key being a concatenation of the key portions associated with the nodes on the path. A trie can be implemented using the trie data structures described above. However, unlike in the examples described above, the match trie is typically a undirected cycle. This means that a child node in the match trie may have more than one parent node. Examples for undirected cycles are provided in
(286) The fuzzy search according to the invention is particularly efficient it the match trie is a virtual trie which is dynamically generated during the intersection of the match trie with the storage trie. Only those parts of the virtual trie are (dynamically) generated which are required for intersection of the match trie with the storage trie, which is sometimes referred to as “lazy evaluation”. Unless otherwise stated in this section, all aspects of virtual tries discussed above also hold true for the use of a virtual match trie in the context of fuzzy search.
(287) As an output of the fuzzy search, character strings and/or other data items such as document identifiers associated with a result set of nodes of the resulting trie are provided. Typically, the match trie comprises a set of matching nodes, each matching node being associated with one or more keys corresponding to one of the character strings from the set of approximate character strings. In this case, the result set of nodes may be the set of nodes of the resulting trie which correspond to the set of matching nodes in the match trie (a node of the resulting trie corresponds to a node of the match trie if a key associated with the node of the resulting trie is identical to a key associated with the node of the match trie). This means that only those character strings data items like document identifiers are provided as an output which are associated with the nodes of the resulting trie that correspond to matching nodes of the match trie.
(288) With reference to
(289)
(290) State 0002 is the state transition for a matching first character (“a”). For “abc” as input, the final state 0006 is reached. State 0003 is the state transition for an inserted character at the start, for example if “xabc” is provided to the automaton. The state transition 0004 reflects character substitution, e.g. providing “ybc” to the automaton. Finally, transition 0005 reflects character deletion, e.g. providing “bc” to the automation.
(291) As can be seen, the automaton of
(292) The NFA can be converted into a deterministic finite automaton (DFA) using e.g. the so-called Powerset construction method. Other methods to efficiently create a Levenshtein automaton DFA include the one proposed by Klaus Schulz and Stoyan Mihov.
(293) In the preferred embodiments, the parent nodes in the match trie and the storage trie comprise a bitmap, and a value of the key portion of a child node in a trie is determined by the value of a bit (set) in the bitmap comprised by a parent node of the child node with which bit the child node is associated. Such trie data structures have been described in the examples above. They allow for a particularly efficient intersection operation because the intersection of a child node of the match trie and of a child node of the storage trie can be achieved by combining the bitmaps of each of the child nodes, using the intersection operation.
(294) A match trie with such a data structure can be derived from the (deterministic) finite automaton by obtaining an augmented finite automaton by associating the transitions between the states of the finite automaton by an encoding of a specific character or of a wildcard character associated with the transition, which encoding consists of or is representative of one or more bitmaps whose length and/or format is equal to the bitmaps comprised by the parent nodes of the match trie. For an encoding of a specific character, exactly one bit is set in each of the bitmaps comprised or represented by the encoding. For an encoding of a wildcard character, the bits of all valid character encodings are set in the bitmaps comprised or represented by the encoding, thereby “masking” all valid character encodings (or the bits of all valid character encodings except for the encodings of the specific characters associated with the state from which the transition departs). In other words, the encoding of a wildcard is an OR combination of the bitmaps of all valid character encodings (or of all valid character encodings except for the encodings of the specific characters associated with the state from which the transition departs).
(295)
(296) Encoding 2001 represents an “a” encoded as the two 6-bit values 1 (“000001”) and 33 (“10001”), which encoded per bit position is
(297) TABLE-US-00007 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0010
and
(298) TABLE-US-00008 0000 0000 0000 0000 0000 0000 0000 0010 0000 0000 0000 0000 0000 0000 0000 0000
(299) In hexadecimal representation, where 0000=0, 0001=1, 0010=2, 0011=3, . . . , 1111=F, this corresponds to 0X0000000000000002 and 0X0000000200000000.
(300) Encoding 2003 represents a “b” encoded as the two 6-bit values 1 (“000001”) and 34 (“10010”), which encoded per bit position is
(301) TABLE-US-00009 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0010
and
(302) TABLE-US-00010 0000 0000 0000 0000 0000 0000 0000 0100 0000 0000 0000 0000 0000 0000 0000 0000
(303) In hexadecimal representation, this corresponds to 0X0000000000000002 and 0x0000000400000000.
(304) In the wildcard case, the bits of the encodings of all allowed characters—the complete Unicode alphabet in this case—are set. For example, encoding 2002 has bits set to represent all 10-bit encoded Unicode characters, i.e. 6-bit values “000000” . . . “001111” and “000000” . . . “111111”, which encoded per bit position is
(305) TABLE-US-00011 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1111 1111 1111 1111
and
(306) TABLE-US-00012 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111
(307) In hexadecimal representation, this corresponds to 0x000000000000FFFF and 0xFFFFFFFFFFFFFFFF.
(308) Encodings 2004 and 2005 denote the same character “b”, one for the non-final case and one for the matching state, i.e. for the case that the “b” is the last letter in the input string. Encodings 2006 and 2007 show the analog case for a wildcard character. 2008 and 2009 show the cases for final matching states for character “c” and for a wildcard.
(309) The complete wildcard masks for all Unicode characters (10-bit, 15-bit and 21-bit encodings as explained above with reference to
(310) TABLE-US-00013 0x000000000000FFFF, 0xFFFFFFFFFFFFFFFF 0x0000000000FF0000, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF 0x00000000FF000000, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFFL
(311) The complete wildcard masks for all Unicode characters that lead to matching states are:
(312) TABLE-US-00014 0x0000FFFF00000000, 0xFFFFFFFFFFFFFFFF 0x00FF000000000000, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF 0xFF00000000000000, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF
(313)
(314) Such a match trie can be derived directly from any of the finite automatons described above, in particular the augmented finite automaton. However, where a character stored in the match trie, the storage trie, or the resulting trie is encoded by a number of M>1 key portions of the respective trie, i.e. by more than one levels of nodes, the match trie is preferably derived from a complete finite automaton representing the set of approximate character strings. Preferably, M is between 2 and 4.
(315) The complete finite automaton from a preferably deterministic finite automaton as described above, more preferably from the augmented finite automaton, by replacing a transition, preferably every transition, between two states of the finite automaton by, or associating a transition, preferably every transition, between two states of the finite automaton with M−1 levels of intermediate states and one or more sequences of M transitions which link the two states via M−1 of the intermediate states. Thus, states not associated with a full character string are added to the finite automaton.
(316) For example, in the finite automaton of
(317) Each of the M transitions in a sequence is associated with an intermediate encoding which consists of or is representative of a bitmap whose length and/or format is equal to the bitmaps comprised by the parent nodes of the match trie, and wherein the match trie is derived from the complete finite automaton. The encoding is called “intermediate” here because it represents only a part of the encoding of an entire character, in the example of the complete finite automaton from which the match trie of
(318) For example, in the complete finite automaton from which the match trie of
(319) TABLE-US-00015 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0010
(320) In hexadecimal representation, this corresponds to 0×0000000000000002. The association of this encoding with the transition between states 0 and 110 is indicated by the upper dotted arrow between encoding 2001 that transition. The “1” to which this arrow points stands for bit no. 1 (the second bit) in the bitmap comprised by parent node 0 of the match trie of
(321) As another example, in the complete finite automaton from which the match trie of
(322) TABLE-US-00016 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1111 1111 1111 1111
(323) In hexadecimal representation, this corresponds to 0×000000000000FFFF. The association of this encoding with the transition between states 0 and 111 is indicated by the upper dotted arrow between encoding 2002 that transition. The “0, 2 . . . 63” to which this arrow points stand for bits no. 0, 2 . . . 63 (the first, third . . . 64.sup.th bit) in the bitmap comprised by parent node 0 of the match trie of
(324) Where transition between the two states of the finite automaton is associated with a specific character, the concatenation of the bitmaps comprised by or represented by the intermediate encodings associated with the M transitions of a sequence is an encoding of the specific character, and exactly one bit is set in each of the bitmaps.
(325) In the example of the finite automaton of
(326) TABLE-US-00017 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0010
and
(327) TABLE-US-00018 0000 0000 0000 0000 0000 0000 0000 0010 0000 0000 0000 0000 0000 0000 0000 0000
(328) In hexadecimal representation, this corresponds to 0X0000000000000002 and 0X0000000200000000.
(329) If the transition between the two states of the finite automaton is associated with a wildcard character, the concatenation of the bitmaps comprised by or represented by the intermediate encodings associated with the M transitions of a sequence comprises an encoding where the bits of all valid character encodings are set in the bitmaps comprised or represented by the encoding, or the bits of all valid character encodings except for the encodings of the specific characters associated with the state from which the transition departs.
(330) In the example of the finite automaton of
(331) TABLE-US-00019 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1111 1111 1111 1111
and
(332) TABLE-US-00020 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111
(333) In hexadecimal representation, this corresponds to 0×000000000000FFFF and 0×FFFFFFFFFFFFFFFF.
(334) Furthermore, in the case where the transition between the two states of the finite automaton is associated with a wildcard character, the concatenation of the bitmaps comprised by or represented by the intermediate encodings associated with the M transitions of a sequence will typically comprise one or more encodings comprising one or more portions of an encoding of the specific character and one or more portions of an encoding where the bits of all valid character encodings are set in the bitmaps comprised or represented by the encoding, or the bits of all valid character encodings except for the encodings of the specific characters associated with the state from which the transition departs.
(335) For example, in the complete finite automaton from which the match trie of
(336) TABLE-US-00021 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0010
and
(337) TABLE-US-00022 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111
(338) In hexadecimal representation, this corresponds to 0×0000000000000002 and 0×FFFFFFFFFFFFFFFF.
(339) The augmented finite automaton or the complete finite automaton, respectively, can be represented by or stored in a data structure comprising a number of rows, each row representing one state of the augmented finite automaton or the complete finite automaton and comprising a tuple for each of the transitions departing from the state, each tuple comprising the encoding associated with the transition and a reference to the state in which the transition ends.
(340) The benefit with this (virtual) match trie approach is a good performance due to the simplicity of the implementation that leads to an efficient execution, as no complex state machine or alike has to be used, and also due to the way the AND operator works on bitmaps in the preferred embodiments.
(341) Index Approaches and Performance Measurements
(342) To measure the performance of the range queries according to various embodiments of the invention, experiments were conducted whose results will discussed in the following with reference to
(343) TABLE-US-00023 ID latitude longitude street/house-number . . . 2893790155 48.1567392 11.4790834 Paul-Gerhardt-Allee 70a 2893790156 48.1603032 11.4787549 Frauendorferstraße 71 2893790157 48.1734518 11.4717007 Thaddäus-Eck-Straße 72 2893790158 48.1625381 11.4697256 Paganinistraße 72 2893790159 48.1569137 11.4791783 Paul-Gerhardt-Allee 72 2893790160 48.1601922 11.4788085 Frauendorferstraße 73 . . .
(344) A first experiment was made to see how the index size (the amount of indexed records) affects query processing performance for a constant result size. The database was queried to return the IDs of all locations within a small rectangle in the area of Munich (longitude 11.581981+/−0.01 and latitude 48.135125+/−0.01, as shown in
(345) For a first series of measurements, the matching records were loaded first and then the about 28.5 million other records were added to the database. These other records are illustrated as the shaded area in
(346) For a second series of measurements, the matching records within the rectangle were also loaded first, but the remaining records were loaded without the records within the “bands” of matching longitude or latitude. The remaining records loaded in the second series of measurements are illustrated in
(347) The first experiment was performed on five different approaches to indexing and querying geo-locations.
(348) In a prior art approach, herein referred to as “prior art indexing” a SpatialPrefixTree of an Apache Lucene 6.0.1 database engine which supports spatial indexing combining longitude and latitude was used (https://lucene.apache.org, package org.apache.lucene.spatial.prefix.tree). The SpatialPrefixTree is not a trie, but it was used for creating an inverted index optimized for spatial queries. Hence it provided a good benchmark for the approach taken here.
(349) To query all locations within the specified rectangle, a range query was performed on both dimensions. The queries each returned a set of IDs representing the records located with the specified longitude or latitude band, which was collected by a cursor-based iterator to create interim result sets. The interim result sets were intersected to obtain the final result set. This is illustrated in
(350)
(351) A first approach to indexing and querying geo-locations using preferred embodiments of the tries described above was made, which is herein referred to as “standard indexing”. One index for latitude was created by means of a first 2-dimensional trie of the preferred embodiments, and another index for longitude was created by means of a second 2-dimensional trie of the preferred embodiments. In other words, each of the 2-dimensional index tries stored two items, namely (latitude, ID) or (longitude, ID), respectively. The 2-dimensional index tries were stored in a non-interleaved manner, as shown above in the trie of
(352) A range query over the first key parts (latitude/longitude) returned the trie roots of the IDs of the locations having the matching latitudes/longitudes. In order to deliver these results with a trie interface, the lists of trie roots were combined using a multi-OR operator which provides the trie interface, as is illustrated in
(353)
(354) With matching records loaded into the database, the query performance of standard indexing decreased because more and more results of the independent latitude and longitude queries had to be combined. The performance of standard indexing with matching records is not very good because long lists of nodes (IDs) occur. To improve performance, the amount of nodes that have to be combined by an OR operation needs to be reduced.
(355) In an approach herein referred to as “variable precision indexing”, the amount of nodes that need to be OR-ed could be reduced dramatically by maintaining multiple indexes with variable precision, creating a hierarchy. This is comparable to the concept of creating several indexes for several levels of resolution in the prior art database engine mentioned above. Using for example ranges in tries which store 2-digit decimal numbers, one can have indexes for each level representing the prefixes: 0, 1, 2, . . . 9 00, 01, 02, . . . , 09, 10, . . . 99
(356) By way of example, an index for a first level of X-values (1.sup.st key part) is shown in
(357) The actual experiments conducted by the inventor used 6 bits for each precision step. The precision length was stored in the first byte of a key. A trie had 11 levels, and a node in the trie had up to 16 child nodes at the root level and up to 64 child nodes at the 10 subsequent levels (including leaf nodes). This means that at maximum 16−2 nodes at the root level and 2*(64−1) nodes at the next level for the left and right parts of the trie had to be OR-ed. This resulted in an upper bound of 16−2+2*(64−1)*10=1274 tries that had to be OR-ed. Every key value subject to a range query was stored with 11 precision levels. A range query based on a virtual range trie as described above was used to perform the query. A list of all keys which are required to select the required nodes was created.
(358)
(359) Another approach to indexing and querying geo-locations, herein referred to as “two-dimensional indexing”, showed that there a solution which is faster than standard indexing but without the drawbacks of variable precision indexing. In this approach, illustrated in
(360) To query for a rectangle, a virtual range trie 6130 specifying the longitude range and a virtual range trie 6140 specifying the latitude range were created. When the longitude index was intersected with the longitude range trie and at the same time the latitude index was intersected with the latitude range trie, the intermediate results of the intersections were combined as will be explained in the following.
(361) In a first step, a bitwise AND operation is performed between the bitmap of root node 6111 of longitude index trie 6110 and the root node of longitude range trie 6130, as is indicated by arrow 6151 in
(362) Nodes 6112 and 6122 in
(363) In a second step, keys in the index tries which do not belong to locations falling into both the specified longitude and latitude ranges are filtered out as follows: the bitmaps of the nodes of the longitude/latitude index trie 6110/6120 yielded by the first step are combined by a bitwise OR operation, and a bitwise AND operation is performed between the results of the bitwise OR operations, as is indicated by arrow 6153 in
(364) Nodes 6113 and 6123 in
(365) Nodes 6114 and 6124 in
(366) The operation was continued in the same fashion until the leaf nodes of the index tries was reached. In summary, the two indexes were combined using a matcher that returned a “view” of the alternating index with the first dimension (x) only. The second dimension was suppressed in the output of the matcher.
(367)
(368) The strategy of matching and suppressing a dimension could in principle be applied to more than two dimensions. However, this causes large chains of nodes: Each node of the x-dimension may have 64 children of the y-dimension which again may have 64 children, already 4096 in total.
(369) In a last approach to indexing and querying geo-locations, herein referred to as “single-index indexing”, only one, multi-dimensional index was created which stored both longitude and latitude in one interleaved trie as discussed above, e.g., with reference to
(370) To query for the rectangle, a two-dimensional range query was performed as described above, e.g. with reference to
(371)
(372)
(373) Prior art indexing using the Lucene database delivered nearly constant results for all result sizes, but at a lower performance level than single-index indexing. Standard indexing (two indexes non-interleaved) and two-dimensional indexing (two indexes interleaved) performed better than the prior art indexing using the Lucene database for small results sizes, but was less performant for large result sizes.
(374) In a third experiment, indexing performance (indexed entries per second) was measured. 28.5 million records were loaded, and the time was measured every 100,000 added records. It could be observed that the prior art index and all trie-based approaches offer a practically constant performance over index growth. The results are summarized in
(375)
(376) It can be concluded that standard indexing works sufficiently well for attributes with low or medium cardinality. For example, product prices typically do not have a continuous value space but discrete values like 3.99, 4.49, 4.89, etc. Instead of storing something like an order-date as a timestamp with millisecond precision, it may be sufficient to store it with day or hour precision to satisfy the requirement of making the value space “more” discrete. To index columns with continuous value space, variable precision indexing offers better performance, especially if used in multidimensional queries. However, due to slow indexing and high memory demand, use of variable precision indexing can be recommended only for static applications and where sufficient memory is available. For closely tied dimensions, single-index indexing is the best solution for moderate expected result sizes.
(377) Even though the multi-dimensional indexes have been presented here in the context of spatial queries, the trie-based range queries can be applied to many other situations, e.g. for graph databases. A property graph database is based on nodes that are connected by edges, with both nodes and edges having properties. If nodes and edges are each represented by a unique ID, a node-edge-node triplet can be represented and queried using these three IDs as dimensions. Note that the same applies to the context of the Resource Description Framework (RDF) with its subject-predicate-object expressions-called triplets in RDF-terminology.
(378) As mentioned above, the invention can easily be used also for full text search applications by storing each occurring term and the document ID as two key parts (character string, long). Since the invention is based on a prefix-tree, it inherits the string search capabilities of prefix trees. For example, it can be used to efficiently implement fuzzy (similarity) searches.
(379) In fact, measurements performed by the inventor show the competitive performance in information retrieval applications. In an experiment performed shortly before the priority date of this application, 500,000 English Wikipedia articles were indexed.
(380)
(381)
(382) The fuzzy query in this experiment searched for documents that contain words similar to “chica”. Similarity is defined by an editing distance (Levenshtein distance) of one, that is with a maximum of one character deletion, insertion and substitution. In this discipline, the inventive system proved to be four to six times faster than Lucene. It is worth noting that both Lucene and the inventive system delivered exactly the same amount of result documents: 319,809 for the term query and 30,994 for the fuzzy query.
(383) The experiment as described above was repeated shortly before the filing date of this application, i.e. about one year later. The results of the repeated experiment can be seen in
(384) As can be seen in
(385)
(386)