Mechanism for constant-space indexing optimized data block merging

In one aspect, a computer-implemented method includes calculating cardinality differences and combined sizes for one or more data block pairs in a relational database. The method also includes selecting a data block pair from the one or more data block pairs based on a calculated cardinality difference and a calculated combined size associated with the selected data block pair. The method further includes merging the selected data block pair to form a merged data block, and replacing the selected data block pair in the relational database by the merged data block.

TECHNICAL FIELD

The subject matter described herein relates generally to databases having constant-space indexing for relational tables.

BACKGROUND

A database management system (DBMS) generally includes computer hardware running system software for creating and managing databases. Some examples of a DBMS include MySQL, PostgreSQL, MongoDB, Microsoft SQL Server, Oracle, Sybase, SAP HANA, and IBM DB2. The DBMS provides users and programmers with a systematic way to create, retrieve update and manage data in a database. Examples of databases include relational database, flat database, object oriented database, hierarchical database etc.

Data in a relational database of a DBMS can be stored in relational tables. In a relational table, data is organized into one or more tables comprising rows (also referred to as records or tuples) and columns (also referred to as attributes). A row of the relational table can represent a type of entity, and a column can represent values corresponding to the type of entity. Data in the relational table (e.g., values in a column) can be organized in data blocks. Each time a user requests access to a data block in the table, the DBMS can sequentially search the entire table. However, sequential searches can be inefficient, especially when the database is stored in a storage disk that is slow to respond to a search request (query).

Data in a database (e.g., a data block) can be efficiently accessed by using a data index. The data index can include a copy of a selected column of the relational table along with the memory address of data blocks in the selected column. When a user requests access to a data block, a search is performed in the data index. If a match is found, the DBMS can directly access the data block in the database. Hence, data index obviates sequential searching in the database, and can therefore allow accessing data efficiently.

SUMMARY

In one aspect, a computer-implemented method includes calculating cardinality differences and combined sizes for one or more data block pairs in a relational database. The method also includes selecting a data block pair from the one or more data block pairs based on a calculated cardinality difference and a calculated combined size associated with the selected data block pair. The method further includes merging the selected data block pair to form a merged data block, and replacing the selected data block pair in the relational database by the merged data block.

In some variations one or more of the following can optionally be included. In one aspect, the one or more data block pairs are in a column of the relational database.

In another aspect, the data block pair is selected by a sliding window, the sliding window selects adjacent data blocks in the column of the database.

In yet another aspect, the cardinality difference for a first data block pair from the one or more data block pairs is calculated by calculating a combined cardinality for the first data block pair, calculating a first cardinality for a first data block in the first data block pair and a second cardinality for a second data block in the first data block pair, and subtracting a larger of the first cardinality and the second cardinality from the combined cardinality.

In another aspect, the data block pair is selected when the calculated cardinality difference parameter associated with the data block pair is below a threshold value.

In another aspect, the computer implemented method includes a data index. The data index includes a sub-index assigned to the merged data block. The size of the sub-index is related to a cardinality of the merged data block.

DETAILED DESCRIPTION

There is a need for creating a faster and more efficient way to access data stored in a database. A data index can allow a user to access data stored in a database (e.g. relational table), based on a query from the user, without sequentially searching the entire database. However, for large relational tables, the corresponding data index can become very large. This problem can be obviated, for example, by using a constant-space index (e.g., bloom filters) whose size does not change. This ensures that even when the size of the relational table increases—for example, due to the addition of a new row—the size of the constant-space index is limited by a predetermined value. However, if the size of the relational table increases for a given constant-space index, the false positive rate (FPR) for user queries may increase. The FPR is indicative of the probability of a false positive match for a user request. It can be reduced, for example, by rearranging data in the relational table to improve the efficiency of the constant-space index. For example, the FPR can be reduced by merging one or more data blocks in a column of the relational table. The current disclosure relates to various approaches for merging data blocks to improve the performance of the constant-space index (e.g., by reducing FPR).

In some implementations, the current subject matter can be configured to be implemented in a system100, as shown inFIG. 1. The system100can include a processor110, a memory120, a storage device130, and an input/output device140. Each of the components110,120,130and140can be interconnected using a system bus150. The processor110can be configured to process instructions for execution within the system100. In some implementations, the processor110can be a single-threaded processor. In alternate implementations, the processor110can be a multi-threaded processor. The processor110can be further configured to process instructions stored in the memory120or on the storage device130, including receiving or sending information through the input/output device140. The memory120can store information within the system100. In some implementations, the memory120can be a computer-readable medium. In alternate implementations, the memory120can be a volatile memory unit. In yet some implementations, the memory120can be a non-volatile memory unit. The storage device130can be capable of providing mass storage for the system100. In some implementations, the storage device130can be a computer-readable medium. In alternate implementations, the storage device130can be a floppy disk device, a hard disk device, an optical disk device, a tape device, non-volatile solid state memory, or any other type of storage device. The input/output device140can be configured to provide input/output operations for the system100. In some implementations, the input/output device140can include a keyboard and/or pointing device. In alternate implementations, the input/output device140can include a display unit for displaying graphical user interfaces.

FIG. 2illustrates an embodiment of a relational database management system200. The DBMS200includes a data index210, and a relational table220. Rows222of the table220represent countries, and the columns224represent data (e.g., name of the capital, total area) associated with the countries. The data index210includes an index file212and a key file214. An index value in the index file212is related to a key in the key file214. The index value can be representative (e.g., a copy) of a value in the relational table220. The key related to the index value can refer to the value in the relational table220. For example, the key can include the memory address of the value. InFIG. 2, an index value in the index file212is a copy of a country name in the first column of the table220. The key associated with the index value refers to the country name in the column220. If the system200receives a user query based on a country name (e.g., China), the system200may search for the country name in the index file212. If there is a match, the key associated with the matched index value can refer to the appropriate value in the first column of the table220.

FIGS. 3A and 3Bdescribe an embodiment of a method300of merging one or more data blocks (e.g.,310-318) in a column304of a relational table. Merging data blocks can improve the performance of a constant-space index302. The size of the constant-space index302does not change when new data blocks are added to the column. The size of the index302can be defined when the column304is created, and can be related to the size of the column304. The size can depend on the relevance of the column304. For example, if the DBMS associated with the relational table receives a high volume of queries for values in the column304, the size of the index302(index size) can be large (e.g., index302can be a dense-index and every value in the column304is indexed). The index size can also depend on the property of the hardware (e.g., memory size) supporting the DBMS, properties of the DBMS (e.g., distribution of the DBMS over various nodes), properties of the stored data (e.g., query type associated with the data) etc.

The column304contains multiple data blocks (310-318). Each data block is indexed by a sub-index (e.g.,350-358) of the index302. For example, keys in the sub-index350refer to values stored in the data block310. It should be noted that although the size of the constant-index data file302is fixed, the sizes of sub-indices350-358may vary. The sizes of a sub-index can depend on, for example, the size of the associate data block.

Cardinality of a data block is defined as the number of distinct values in the data block. For example, cardinality of a first data block including the values {1, 2, 2, 4, 7, 9, 9}, is 5. Similarly, cardinality of a second data block including the values {1, 5, 7, 7, 12, 15, 17} is 6. Combined cardinality is defined as the number of distinct values in a data block pair. For example, the combined cardinality of a data block pair including the first data block and the second data block is 9. The combined cardinality is representative of the distinct values in the data block pair. Cardinality of a dataset can be calculated by using cardinality algorithms, for example, HyperLogLog. The cardinality algorithms may estimate the cardinality (estimated cardinality) of a data block (or a data block pair) rather than calculating the exact cardinality thereof. In this application, “cardinality” can refer to either the exact cardinality or the estimated cardinality.

In one embodiment, the decision to merge a data block pair can be based on a cardinality difference of the data block pair. The cardinality difference can be calculated by subtracting the larger cardinality value of the data blocks in the data block pair from the combined cardinality of the data block pair. For example, the cardinality of the first data block is 5; the cardinality of the second data block is 6; and the combined cardinality is 9. Therefore, the cardinality difference of the data block pair including the first and second data blocks is 3 (9−max (5, 6)). A small cardinality difference value can indicate that the corresponding data block pair may be a good candidate for the formation of a merged data block. A large cardinality difference value can indicate that the corresponding data block pair may be a bad candidate for the formation of a merged data block.

In one embodiment, the DBMS may limit the maximum size of data blocks in a column of a relational table to a threshold size. A data block larger than the threshold size can be divided into multiple data blocks. In a preparation phase, size of the data blocks310-318is calculated. If a data block is found to be larger than the threshold size, it is divided into two or more parts. For example, data block310is larger than the threshold size, and is therefore divided into two data blocks320and322.

After the preparation phase, the “prepared” column306includes data blocks320,322,312,314,316and318. The preparation phase can be followed by the calculation phase in which cardinality differences for various data block pair in the column306is calculated. The calculation phase is followed by a merging phase. In the merging phase, desirable data block pairs are selected and merged. The first part of the selection process372involves selecting data block pairs from the column306. For example, a sliding window370can slide along the column306and select pairs of adjacent data blocks. For example, data block pairs {320,322}, {322,312}, {312,314}, {314,316}, and {316,318} can be selected. Additionally or alternately, data block pairs from the column306can be randomly selected, and/or selected according to a predetermined algorithm. The cardinality difference is calculated for the selected data block pairs.

The next step of the selection process372is determining the data block pairs with a cardinality difference smaller than a threshold cardinality value. For example, inFIG. 3A, data block pairs330(including data blocks320and312), data block pair332(including data blocks312and314), data block pair334(including data blocks314and318), and data block pair336(including data blocks316and318) have a cardinality difference less than the threshold cardinality value. The aforementioned data block pairs can be sorted374based on the value of their cardinality difference. For example, data block pairs can be sorted in an ascending order of their cardinality difference values. A data block pair with small cardinality difference may be given preference for the formation of a merged data block over a data block pair with a larger cardinality difference. InFIG. 3A, data block pair332has the smallest cardinality difference, and the data block pair330has the largest cardinality difference. The data blocks pairs are merged starting with the data block pair with the smallest cardinality difference (data block pair332).

A data block cannot be used in the formation of more than one merged data block. In other words, if a data block is part of more than one data block pair, it can be merged into a merged data block only with one of the data blocks with which it is paired. For example, data block312is a part of the data block pair332which can be the first data block pair to be merged (as it has the smallest cardinality difference). Data block312is also a part of the data block pair330. However, data block pair330cannot be merged in this example because one of its components (namely data block312) has already been used in the formation of a merged data block. Similarly, data block318is a part of data block pair336and data block pair334. Because data block pair336is merged first (as it has smaller cardinal difference than data block334), data block pair334is not merged to form a merged data block.

FIG. 3Billustrates two data block pairs332and336that are viable candidates for the formation of merged data blocks. Data blocks312and314can be merged to form a merged data block342. Data blocks316and318can be merged to form a merged data block346. Data blocks that have been merged to form a merged data block are replaced by the merged data block in the relational table, and saved in a tracking data structure. Before merging a subsequent data block pair, the database management system can check that the data blocks in the data block pair are not present in the tracking data structure. In other words, the database management system can check whether the data blocks in the data block pair have not already been used to generate a merged data block. If not, the data blocks in the data block pair are available for merging to form a merged data block.

In one embodiment, the size of the merged data blocks is calculated. If the size of a merged data block is larger than a threshold size, the merged data block is discarded. The threshold size can be related to the threshold size used in the preparation phase described above (e.g., the two threshold sizes can be the same). For example, if the size of the merged data block346is larger than the threshold size, it can be discarded. Alternately, the database management system can calculate the size of the merged data block without merging the data blocks. If the calculated size exceeds the threshold size, the merged data block may not be calculated.

The steps described inFIGS. 3A and 3Bmay be repeated multiple times. For example, the steps may be repeated until no suitable data block pair is available for the formation of a merged data block. For example, if no data block pair has a cardinality difference lower than the threshold cardinality value, no suitable data block pair would be available.

FIG. 4illustrates a modified column404and the modified constant-index data file402. In the modified column404, the merged data block342replaces the data blocks312and314. It should be noted that data blocks316and318have not been replaced by the modified data block346because its size is greater than the threshold size. The size of the constant-index data file402is the same as that of the constant-index data file302. However, the size of sub-indices in the constant-index data file402can be different from that of sub-indices in constant-index data file302. The size of a sub-index can depend on the ratio of the cardinality of the data block to which it refers, and the sum of cardinalities of all the data blocks in the column404. For example, the size of the sub-index364can be larger than that of sub-index366if the cardinality of data block342is larger than that of the data block316.

FIG. 5illustrates exemplary pseudocode illustrating features of a process for merging data blocks in a column of a relational database. The index502provides the definition of various variables, symbols and functions used in the algorithm.

In the preparation phase504, the algorithm500(which can be executed by the database management system) searches for data blocks (b1, b2. . . bn) in a data structure B (e.g., a column of a relational table) whose size is larger than a threshold size (bmax_start). If a data block (b) fulfils the aforementioned condition, it is divided into one or more data blocks (bsub) that are smaller than the threshold size. Additionally, the data block b is replaced in the data structure by the data blocks (bsub). For example, as described inFIG. 3A, data block310can be divided into two data blocks320and322. The algorithm500also calculates the cardinality of each data block in the data structure.

In the selection phase506, data block pairs are selected from the data structure B. For each data block pair, a combined cardinality (cecp) and a cardinality difference (diffp) can be calculated. Additionally, the combined size of the data block pair can be calculated (size (px, py)). Based on the value of the cardinality difference, “merge candidates” can be selected. For example, inFIG. 3A, data block pairs330,332,334and336are selected based on their cardinality difference. Additionally, the algorithm requires that the size of a data block obtained by merging the merge candidates is less than a threshold size (bmax). The merge candidates are sorted based on cardinality difference and combined size. In one embodiment, if two merge candidates have the same cardinality difference, the merge candidate with the smaller combined size can be considered as a better candidate for the formation of merged data block. After the merged candidates have been sorted (e.g., in the order with increasing cardinal difference value), they are merged to form merged data blocks and added to the data structure P. Data blocks that have been used to form a merged block are added to a tracking data structure (M). After all the merged data blocks have been calculated, the constant-space index is split508into multiple sub-indices based on the cardinality of the data blocks.

FIG. 6is a process flow diagram600illustrating features that can be included in an exemplary technique for merging data blocks in a column of a relational database. At602, cardinality differences and combined sizes are calculated for one or more data block pairs in a relational database. At604, a data block pair is selected from the one or more data block pairs based on a calculated cardinality difference and a calculated combined size that are associated with the selected data block pair. After the data block pair has been selected, the selected data block pair is merged at606to form a merged data block. The merged data block replaces the selected data block pair in the relational database at608.

Aspects of the subject matter described herein can be embodied in systems, apparatus, methods, and/or articles depending on the desired configuration. In particular, various implementations of the subject matter described herein can be realized in digital electronic circuitry, integrated circuitry, specially designed application specific integrated circuits (ASICs), computer hardware, firmware, software, and/or combinations thereof. These various implementations can include implementation in one or more computer programs that are executable and/or interpretable on a programmable system including at least one programmable processor, which can be special or general purpose, coupled to receive data and instructions from, and to transmit data and instructions to, a storage system, at least one input device, and at least one output device.

The subject matter described herein can be implemented in a computing system that includes a back-end component, such as for example one or more data servers, or that includes a middleware component, such as for example one or more application servers, or that includes a front-end component, such as for example one or more client computers having a graphical user interface or a Web browser through which a user can interact with an implementation of the subject matter described herein, or any combination of such back-end, middleware, or front-end components. A client and server are generally, but not exclusively, remote from each other and typically interact through a communication network, although the components of the system can be interconnected by any form or medium of digital data communication. Examples of communication networks include, but are not limited to, a local area network (“LAN”), a wide area network (“WAN”), and the Internet. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other.