Patent Description:
As technologies advance, the amount of information stored in electronic form and the desire for real-time or pseudo real-time ability to search, organize and/or manipulate such information is ever increasing. Database management systems, sometimes also referred to as databases and data warehouses, are designed to organize data in a form that facilitates efficient search, retrieval or manipulation of select information. Typical database management systems allow a user to carry out transactional or analytical processing by submitting a "query" or calling one or more functions in a query language for searching, organizing, retrieving and/or manipulating information stored within a respective database.

Certain database table or record set structures, also known as access methods, are designed to store data in accordance with how the data is going to be used. Two examples of different database access method designs are rowstore tables and columnstore tables. Typically, rowstore tables are used for online transaction processing (OLTP) workloads and columnstore tables are used for online analytical processing (OLAP) workloads. However, sometimes both transactional processing and analytical processing are required.

"<NPL> discloses the structure and use of columnstore indexes. <CIT> discloses optimization of wiede data-type storage and analysis of data in a columnstore database. "<NPL> discloses the structure of columnstore indexes and how they are used. "<NPL> discloses a process for creating a columnstore and using a columnstore.

It would be advantageous to be able to serve a workload containing both transactional and analytical queries. In addition, it would be advantageous to reduce the resources incurred in processing queries and updates on a rowstore table and a columnstore table.

The object of the invention is solved by the features of the independent claims.

Various features of the present disclosure will be apparent from the detailed description which follows, taken in conjunction with the accompanying drawings, which together illustrate, features of the present disclosure, and wherein:.

A columnstore access method stores data using a column-wise format so that entries of a particular column of a table are grouped together, followed by entries of another column and so on.

<FIG> shows a columnstore table <NUM> (sometimes referred to as a "columnstore" or a "column-oriented table") to which embodiments described herein have particular application. The columnstore <NUM> comprises a plurality of segments <NUM> containing a first segment <NUM>, a second segment <NUM> and a third segment <NUM>. Each segment <NUM>-<NUM> contains segments of data for each column of a plurality of columns <NUM>, referred to as column segments. In the example of <FIG>, the plurality of columns <NUM> comprises a first column <NUM> and a second column <NUM>. The first column <NUM> is divided into column segments 121a-c stored in each of the segments <NUM>-<NUM>, respectively. As for the first column, the second column <NUM> is split into column segments 122a-c that are stored in the segments <NUM>-<NUM>, respectively. Each of the column segments 121a-c and 122a-c comprise a plurality of rows that have entries in each of the plurality of columns <NUM>. In one example, each column segment may contain in the order of hundreds of a million rows.

A query defines one or more parameters that are used as the basis for filtering data. In some examples, a value of a parameter may define a key that can be used to identify rows of a data structure, for example, a columnstore, deemed to be relevant to the parameter. Data within the relevant rows is then retrieved and may be used to form a query response.

<FIG> shows the columnstore <NUM>, a plurality of mapping structures <NUM>, and a plurality of index tables <NUM> according to an example. The plurality of mapping structures <NUM> comprises a first mapping structure <NUM>, a second mapping structure <NUM> and a third mapping structure <NUM>. The first mapping structure <NUM> corresponds to the first segment <NUM>, the second mapping structure <NUM> corresponds to the second segment <NUM> and the third mapping structure <NUM> corresponds to the third segment <NUM>. In this respect, it is understood that each of the mapping structures <NUM>-<NUM> corresponds to a subsection of the overall columnstore <NUM> and is therefore local to its respective segment and may be referred to as a "local mapping structure". In a variation, the mapping structures <NUM>-<NUM> may be merged to form, or be initially generated as, a single "global" mapping structure for the entirety (or majority) of the columnstore <NUM> that corresponds to the plurality of index tables <NUM>.

The plurality of mapping structures may be exemplified by hash tables; dictionaries; B-trees; radix trees; and interval buckets.

The plurality of index tables <NUM> comprises a first index table <NUM>, a second index table <NUM> and a third index table <NUM>. The plurality of index tables <NUM> each comprise at least one row. The first index table <NUM> corresponds to the first segment <NUM>, the second index table <NUM> corresponds to the second segment <NUM> and the third index table <NUM> corresponds to the third segment <NUM>. In this respect, it is understood that each of the index tables <NUM>-<NUM> is local to its respective segment and thus may be referred to as a "local index table".

Accordingly, each of the plurality of mapping structures <NUM> is paired with a respective index table of the plurality of index tables <NUM>. In one example, a pairing of a mapping structure and an index table is created when the respective segment of the columnstore is created.

Each mapping structure <NUM>-<NUM> maps a plurality of keys to respective values that identify rows of the corresponding index table <NUM>-<NUM>. Each index table <NUM>-<NUM> maps the same plurality of keys, as mapped by its corresponding mapping structure <NUM>-<NUM>, to at least one row of the corresponding segment <NUM>-<NUM>.

Using one or more mapping structures and per-segment index tables provides fast seeking to one or more rows of the columnstore <NUM> because scanning of entire segments of the columnstore <NUM> is not required. In another example, described above in relation to a "global mapping structure", a mapping structure may correspond to a plurality of segments of the columnstore, thereby having a one-to-many relationship with segments of the columnstore (and the corresponding index tables), where the number of segments to which a mapping structure corresponds depends on a target or predetermined speed for seeking rows or providing a response to a query. Where there is a single mapping structure corresponding to a majority of, or all, of the segments of the columnstore (and the corresponding index tables) the mapping structure also has a one-to-many relationship with the segments and index table and is considered to be a "global" mapping structure with respect to the columnstore, whereas the index tables are understood to be "local" with respect to segments of the columnstore because the index tables have a one-to-one relationship with the segments of the columnstore.

The plurality of keys that is mapped by the mapping structures <NUM>-<NUM> and the index tables <NUM>-<NUM> relates to one or more conditions of a query, where such conditions are defined by a parameter within the query. The values within the index tables - to which the keys are mapped through use of the mapping structures - identify one or more rows of a segment of the columnstore <NUM> that relate to a parameter of a query. The entries of the identified rows contain data related to the key and thus the parameter of the query. The data related to the key may be retrieved from the columnstore <NUM> for use in a join operation. In one example, the columnstore <NUM> is a fact table that is part of a star schema of a relational database. In this example, a filter process may be implemented with respect to a dimension table within the relational database, for example by application of a filter based on a query parameter. As a result of the filter process, one or more rows of the dimension table are identified as satisfying the filter, so-called "filtered rows". The data (that is, the values) within the entries of the filtered rows can be retrieved and mapped, using the mapping structures, to one or more rows of at least one index table of a plurality of index tables that are associated with the columnstore <NUM>. Then a lookup can be performed with respect to the at least one index table based on the retrieved values. The lookup process identifies one or more rows within the columnstore <NUM> that are relevant to the retrieved values. A join process can then be executed on the rows of the columnstore that are relevant to the retrieved values, which means the join can be processed on fewer rows, speeding up the join process.

<FIG> shows the columnstore <NUM> and a row number array <NUM> that contains numbers for each row within each segment of the columnstore <NUM>. In the example of <FIG> the column segments 121a-c of the first column <NUM> contain numerical identifiers, id numbers, and the column segments 122a-c of the second column <NUM> contain text, which in some examples, may be represented by a string. Blank entries in each column within <FIG> are simply used to represent entries that are not referred to in the example of <FIG>, rather than empty or null values. In one example, the columnstore <NUM> could be considered as a fact table within a star schema, where the schema would also contain respective dimension tables for the numerical identifiers of the column 121a and the text of column 122a.

A query, Q, is received that states: find text where id=<NUM>. The query contains a parameter "id=<NUM>". The value of the parameter is the number "<NUM>". In this example, the value "<NUM>" can be considered to be a key because it can be used to identify and access rows within the columnstore <NUM> because "<NUM>" is an id number and the first column <NUM> of the columnstore contains id numbers. In the example of <FIG>, the key "<NUM>" is a non-unique key of the column <NUM> because there a three rows containing "<NUM>", that is rows <NUM> of segment <NUM>, and rows <NUM> and <NUM> of segment <NUM>, so "<NUM>" is not unique within the column. In addition, the key "<NUM>" may be a primary key in another table (not shown), for example a dimension table that contains the description information associated with the numerical identifiers, in which case it would be a foreign key.

In this example, the first segment <NUM> contains the value "<NUM>" in the row identified as "<NUM>" within the row number array <NUM> and the third segment <NUM> contains the value "<NUM>" in the rows identified as "<NUM>" and "<NUM>" within the row number array <NUM>.

<FIG> shows the first mapping structure <NUM> and the first index table <NUM>, and the third mapping structure <NUM> and the third index table <NUM> for the example of <FIG>. As such, the second mapping structure <NUM>, which does not contain the value "<NUM>" in any rows, is not relevant so is not shown in <FIG>.

The first mapping structure <NUM> maps the key <NUM> to a value that identifies the index table <NUM> at position <NUM> as containing location data relating to the key <NUM>. The first index table <NUM> contains, at position <NUM>, a value "<NUM>" that identifies the location of row <NUM> within the first segment <NUM> of the columnstore <NUM> as containing data related to the key <NUM>, in accordance with the example of <FIG>.

The third mapping structure <NUM> maps the key <NUM> to a value that identifies the index table <NUM> at positions <NUM> and <NUM> as containing location data relating to the key <NUM>. The third index table <NUM> contains, at position <NUM> a value "<NUM>" and at position <NUM> a value "<NUM>" that respectively identify the locations of rows <NUM> and <NUM> within the third segment <NUM> of the columnstore <NUM> as containing data related to the key <NUM>, in accordance with the example of <FIG>. The mapping provided by the index tables <NUM> and <NUM> is also shown in <FIG>.

Accordingly, the mapping structures are lookup structures. The first and third mapping structures <NUM>, <NUM> may be merged together to form a single mapping structure, in which case it is understood that respective sub-sections of the single mapping structure correspond to the index tables <NUM> and <NUM> and thus the column segments <NUM> and <NUM>. In one example, the mapping structures may be stored on-disk.

After the query Q is received, the mapping structures <NUM> and <NUM> are interrogated using the key <NUM> to identify the index tables <NUM> and <NUM> and positions therein. The index tables <NUM> and <NUM> are then interrogated directly at the identified positions to determine the values <NUM>, <NUM> and <NUM>, respectively. Data relating to the parameter is then retrieved based on the values stored at the identified positions of the index tables, that is the values <NUM>, <NUM> and <NUM>. For example, these rows can be identified as <NUM>:<NUM>, <NUM>:<NUM>, and <NUM>:<NUM>, based on the pairing of segment identifier ("segmentID") and row number ("rowNumber"). Using the row identifiers (<NUM>:<NUM>; <NUM>:<NUM>; <NUM>: <NUM>) data within the entries of the rows <NUM>, <NUM> and <NUM> in each of the column segments 122a (row <NUM>) and 122c (rows <NUM> and <NUM>) is then retrieved. In the example of <FIG>, the data to be retrieved is the text "abc" for row <NUM> of column segment 122a, "def' for row <NUM> of column segment 122c, and "ghi" for row <NUM> of column segment 122c. In an example scenario, a deduplication process may be carried out when inserting new rows into the columnstore or a segment thereof. In such a scenario, values within the new rows are checked against the index tables <NUM>-<NUM> to determine whether one or more of the new rows is a duplicate of a row already present in the columnstore <NUM>, or a particular segment. If a duplication is detected, insertion of the new row in question may be skipped and, optionally, the row that is already present in the columnstore <NUM> may be updated. In another example, the deduplication process may be used to "tidy-up" duplicated rows that are already present within the columnstore <NUM>. To address the repeated data, a deduplication process can be implemented to eliminate at least one of the identified rows from the columnstore so that a single row remains containing the key-data pair in question. In this way, less storage space is required to store the columnstore. In some examples, the rows that are deleted can be replaced by pointers to the remaining row containing the key-data pair.

Using a combination of one or more mapping structure and a plurality of index tables as described herein to identify rows of a columnstore that correspond to a parameter of a query enables fast seeks to the relevant rows, which makes the columnstore more useable for OLTP-like workloads, which often require one or more rows to be located extremely efficiently. In examples where the mapping structures are hash tables, it is understood that the uniqueness constraint required for primary indexes would not be not enforced because, as discussed in relation to <FIG>, the key "<NUM>" is a non-unique key, accordingly, in such a scenario the mapping structures are secondary indexes that do not physically cluster rows together based on key values (as in a primary index).

The mapping structures may be generated as the columnstore is created, whereby each new mapping structure is combined with other, older mapping structures as segments within the columnstore are created. Alternatively, the mapping structure may be combined with one or more others after all or a predetermined number of mapping structures have been created. A mapping structure that is formed by combining other mapping structures is to be understood to correspond to a plurality of index tables and thus a plurality of the segments of a columnstore, such that said mapping structure has a one-to-many relationship with the respective data structures. The mapping structures and the corresponding index tables can be generated for particular columns of a columnstore that relate to a particular parameter within a query. In one example, the particular parameter may be client or user specific.

In relation to the processing of a particular query, there may be a determination or identification of the selectivity of each parameter of the query and, sometimes, a subsequent identification of the parameter that is most selective or the one or more parameters that satisfy a threshold relating to selectivity. In one example, a filter reordering algorithm may be executed to determine the order in which to apply the one or more parameters within the query, for example, whether to use a hash index to filter rows in a segment in cases where the query contains a mix of AND and OR conditions. Accordingly, the mapping structures and index tables may be interrogated based on the selectivity of parameters within a received query.

As an example, mapping structures and index tables may be generated in advance of receiving a query for a highly-selective, or most selective, filters so that further evaluation of rows is reduced. By tailoring the order of filtering based on selectivity, order-of magnitude speedups are provided for processing queries, reducing the required processing resources.

For example, a second parameter of a query may be determined to be less selective than a first parameter within the same query. In one scenario, a plurality of index tables may be generated for only the first parameter. Alternatively, a first plurality of index tables may be generated for the first parameter and a second plurality of index tables may be generated for the second parameter, whereby a respective key is determined for both parameters and used to identify a corresponding mapping structure from a first and second plurality of mapping structures. The identified mapping structures are interrogated to determine values corresponding to the respective keys, where the values identify respective entries of an index table of the first and second plurality of index tables and the respective entries identifies a row of the respective segment of the columnstore relating to the first parameter and a row of the respective segment of the columnstore relating to the second parameter. In this way, interrogation of the respective mapping structures for the first and second parameters may occur concurrently. The values relating to the first and second parameter are compared and one or more intersections between the parameters are identified based on the comparison. That is, it is determined whether any of the values relating to the first parameter are the same as those relating to the second parameter. Based on the intersections, data is retrieved from a data source that relates to both the first and second parameters. The index intersection may be used when an AND filter is used to define the relationship between the first and second parameters.

In a variation, where the first parameter is determined to be more selective than the second parameter, identification of values corresponding to the first parameter may occur before such identification for the second parameter, resulting in identification of values corresponding to the second parameter being based on the values identified for the first parameter. In this way, identification relating to the second parameter is carried out on a smaller pool of possible values (that is, only those deemed relevant to the first parameter) making the identification quicker because checks are not required on all the index tables of the second plurality of index tables.

In a further example, a mapping structure and a corresponding plurality of index tables may be generated, for example, by a database user (developer or administrator), for columns that are determined to have been referred to by a predetermined number of queries in order to speed-up seeks for those columns in response to future queries.

In the examples described, a mapping structure maps a plurality of keys to a plurality of positions within an index table in order to locate the keys within rows of a columnstore. The keys may be single or multi-column keys. For instance, in the previous example, the key "<NUM>" is only for the identifier column so is a single column key. In addition, the corresponding mapping structures <NUM>-<NUM> are for the identifier column and not for both the identifier and text columns.

The use of the index tables with a mapping structure formed from merging of other mapping structures, that is, having multiple index tables and a single mapping structure, speeds up filtering of rows of the columnstore in response to a query because it is not necessary to scan each index table to identify a relevant row(s) of the columnstore. In addition, other processes that are concerned with the local index tables may be performed at the same time as the above-described seeking to relevant rows.

<FIG> is a flowchart of a method <NUM> of processing a query (for example, query Q described in relation to <FIG>) using a columnstore comprising a plurality of segments according to an embodiment. The method <NUM> is carried out by a computing device that may form part of a database management system or be a component that is logically and physically separate therefrom. The method <NUM> starts at block <NUM> where a query comprising a parameter is received (Q: find text where id=<NUM>). The parameter (id=<NUM>) specifies a condition on which the query Q is based and may be referred to as a query predicate. Next, the method <NUM> proceeds to block <NUM> where a key (<NUM>) corresponding to the parameter (id=<NUM>) is determined. Following this determination, at block <NUM>, one or more mapping structures (mapping structures <NUM> and <NUM> in the example of <FIG>), or a subsection(s) of a mapping structure formed by merging a plurality of mapping structures, that relate to the key (<NUM>), are identified from a plurality of mapping structures (<NUM>), each corresponding to one or more respective segments of the columnstore <NUM>. Each of the plurality of mapping structures associated with the columnstore <NUM> may be checked to find the one or more mapping structures that contain matches for the key "<NUM>".

The method <NUM> then proceeds to block <NUM> where the identified mapping structure (mapping structures <NUM> and <NUM>), or a subsection thereof, is interrogated to determine one or more index tables ("Local index id" - <FIG>) and a position(s) therein ("Position in local index"- <FIG>) corresponding to the key (<NUM>). The determined position identifies an entry of the related index table (in the example of <FIG>, the mapping structure <NUM> identifies entry <NUM> of index table <NUM> and the mapping structure <NUM> identifies entries <NUM> and <NUM> of index table <NUM>). The entry of the index table identifies a row of the corresponding segment relating to the key (in the example of <FIG> entry <NUM> of index table <NUM> identifies row <NUM> of the first segment of the columnstore and entries <NUM> and <NUM> of the index table <NUM> identified rows <NUM> and <NUM> of the third segment of the columnstore).

Next, the method <NUM> proceeds to block <NUM> where data relating to the parameter (id=<NUM>) is retrieved from a data source based on the rows' positions stored in the identified entries of the index tables. In the example of <FIG>, data is retrieved from the columnstore <NUM>, where the data contained by row <NUM> of the first segment includes the text "abc" and the data contained by rows <NUM> and <NUM> of the third segment includes text "def' and "ghi", respectively). In one example, the data relating to the parameter is contained within one or more fields in various columns of the identified row (in the example of <FIG> the text data, which is the direct result of the query Q: find text where id=<NUM>, is contained within the identified rows of the column 122a). Alternatively, the data relating to the parameter may be contained in a row of another data structure, where the data contained by the identified row identifies or points to the other data structure, for example a rowstore table or another columnstore table.

Once rows of a segment of the columnstore <NUM> have been identified as being relevant to a parameter of a received query, other data stored within the same row in different one or more columns of the columnstore is retrieved in order to generate a query response. The relevant rows may be identified using the seeking operation described in the section entitled "Seek using mapping structures", such as the seeking operation based on "id=<NUM>" in the example presented with regard to <FIG>.

<FIG> shows the first segment <NUM> of the columnstore <NUM> of <FIG>. As explained above, the first index table <NUM> maps the key <NUM> to the value <NUM> in row number array <NUM>, which identifies row <NUM> of the first segment <NUM>, highlighted in bold and labelled <NUM>. Accordingly, data within the other entries (sometimes referred to as "fields") of the identified row <NUM>, such as data within the second column 122a, needs to be retrieved. In the example of <FIG>, the entry "abc" within the text column 122a is located and retrieved in accordance with the query find text where id=<NUM>. Accordingly, the data to be retrieved from fields of identified rows within one or more other columns depends on the content of a received query. As for query Q, other queries may specify the type of data of interest (and thus to be retrieved) and this could include data of any number of other columns of the columnstore. Otherwise, a received query may exclude data from certain columns from being retrieved or request for data to be retrieved from all the columns of a columnstore.

Although in <FIG> the "<NUM>" entry of the column 121a and the "abc" entry of the second column 122a are depicted as being aligned and at the same position within the respective columns, this is a logical representation of the identified row <NUM> and the location of each of the entries will be dependent on how data in the respective columns have been stored. The data stored within the columnstore <NUM> is stored on disk and can be cached in memory. The storing of the data on disk may be implemented using a different storage scheme to that used to store the data in memory.

<FIG> shows the first and second columns 121a and 122a of the first segment <NUM>.

Data in columns 121a and 122a is stored according to a corresponding storage scheme, which, in some examples, may comprise a compression scheme and/or an encoding scheme such as integer encoding, run length encoding, integer run-length encoding, string run-length encoding, string encoding, integer value encoding, integer delta encoding, LZ4 encoding, and string dictionary encoding. The storage scheme of a column defines how many bits or bytes are assigned for storing data. Different columns may be associated with different storage schemes. This is visually represented within <FIG> by the entry "<NUM>" of the column 121a being associated with a first offset <NUM> and entry "abc" of column 122a being associated with a second offset <NUM>. In this example, the first offset <NUM> is smaller than the second offset <NUM>, which may e.g. be a result of the fact that data of column 121a is stored with a higher compression ratio than that of the column 122a.

In order to retrieve the data abc from column 122a the offset <NUM> within the column 122a is determined based on the location of the identified row <NUM> of this column 122a, which in this example, is row <NUM> and the compression scheme for this column 122a, as will be explained below. After the offset <NUM> is determined, a location of the data abc is determined and the column 122a is accessed at that location in order to retrieve the data. This means that a seek operation can seek directly to a location in a column 122a that corresponds to the identified row, which makes the seek operation more efficient because the entire column segment does not require loading and then decompressing and/or decoding. This also results in a speed up in the time taken to access relevant data and, thus, quicker results.

As part of determining the offset <NUM>, a number of rows preceding the identified row <NUM> within the first segment <NUM> is determined, for instance, for row <NUM> there are two preceding rows within the first segment <NUM>. Looking to the third segment <NUM> in <FIG>, row <NUM> has one preceding row within the segment <NUM> and row <NUM> has three preceding rows.

The determined number of preceding rows is used with the storage scheme of a particular column of the segment <NUM>, in this case the storage scheme of column 122a, to determine the corresponding offset within the column segment.

The storage scheme of a column defines how many bits or bytes are assigned to storing each row of the segment <NUM>. Accordingly, the offset <NUM> is determined by determining a fixed number of bits or bytes assigned to the rows preceding the identified row <NUM>. For instance, in the example of <FIG>, there are two rows preceding the identified row <NUM> and these two rows can be allocated a fixed number of bits or bytes per column segment 121a, 122a based on the storage scheme thereof.

As described in relation to <FIG> and <FIG>, for storage schemes with a fixed number of bytes or bits assigned per row or segment of a column (for example, dictionary encoding), the offset may be calculated during execution of each storage scheme by multiplying the fixed number of bytes or bits with the number of preceding rows. For storage schemes without a fixed, predetermined number of bytes per row, in other words a scheme that assigns a variable number of bytes per row (for example run-length encoding), an offset table may be built to contain information for such storage schemes, such as the offsets per-row or per-block. In cases where the offset table stores offsets per-block, the row offset within may be calculated during execution of the storage scheme by summing up the number of bytes per row for preceding rows within the block. For run-length encoding, values are stored in a column, such as: (value1, runLength1); (value2, runLength2);. (valueN, runLengthN), so to find the value at position k the (value, runLength) pairs are scanned and totaled until k is reached. This calculation may be determined during execution of a query, such as query, Q.

After the data "abc" of the column <NUM> has been located and retrieved a data processing operation may be performed. In an example where the data "abc" is encoded, one such data processing operation may be a decoding operation. In the example of <FIG>, a seek operation will directly seek to the relevant rows and so the subsequent decoding of those rows is the decoding of a subset of rows within a segment and may be referred to as segment-level selective decoding. In this way, the decoding is more efficient than decoding a whole segment because rows of a column segment that are not relevant to the query are not read or accessed and instead, are skipped. Other processes that are not related to the processing of the query Q, for example one or more unrelated transactional or analytical processes such as a "read query", may be carried out on the rows that are skipped at the same time as the identified rows are decoded because the rows skipped in relation to query Q may be relevant to the other, unrelated processes.

Although in the example of <FIG> reference is made to an "identified row", in some scenarios, the identified row may comprise a plurality of rows, for example, if multiple of consecutive rows pass a filter (such as a filter corresponding to a parameter of a query) the rows may be identified as a run of X rows rather than X individual rows to improve efficiency by processing the run of X rows together. For run-length encoding, the identified row may be inside a multi-row run. In this case, the subsequent decoding of a block of X rows may be referred to as block-level selective decoding, so results in decoding of contiguous rows but advantageously avoids fully decoding an entire column. In some examples, namely where a row has already been decoded, the result may be stored in a cache and re-used so that the decoding process is not repeated for that row, saving processing resources and speeding up the response to a query.

In some examples, multiple processes (transactional and/or analytical) may require access to the same segment of a columnstore at the same time, for example the first segment <NUM> of the columnstore <NUM>. Using a segment-wide access lock can cause subsequent processes requiring access to that same segment to be blocked whilst a first process is being executed in relation to the segment. The blocking of processes can cause unnecessary waiting that slows down a computer or computer system that is relying upon the execution of one or more of the blocked processes.

A rowstore can be used in conjunction with the columnstore in order to improve concurrent access to a single segment of the columnstore <NUM>. In some examples, access may be required to update data stored in a particular row or set of rows within the columnstore <NUM>. A rowstore logically organizes data in a table with rows and columns yet physically stores data in a row-wise format so that fields of a particular row of a table are grouped together, followed by fields of another row and so on. Using a rowstore in combination with a columnstore provides a data store that allows easy update of the more recent data. In some examples, the rowstore is stored in Random Access Memory.

<FIG> shows the columnstore <NUM> described in relation to <FIG> and a logical representation of a rowstore <NUM>, according to an example. Accordingly, the methods described in relation to the "Seek using mapping structures" and "Subsegment access" sections are compatible with the method described within this "Concurrent updates" section. The rowstore <NUM> comprises a plurality of rows <NUM> identified by a row number array <NUM>, which is an optional feature shown in <FIG> for the purposes of explanation. A query, Q', is received that specifies: "update text to bgh for id=<NUM>". Query Q' is understood to be a request to update a table comprising the columnstore <NUM> and the rowstore <NUM>. Rows that are relevant to the query Q' are identified, in the example of <FIG> a relevant row is row "<NUM>" of segment <NUM> containing the identifier "<NUM>" and the text "bdf". In some examples, row <NUM> may be identified using the seeking operation described in the section entitled "Seek using mapping structures". In addition, the location of data within row <NUM> of the second column 122a may be identified using the access operation described in the section entitled "Subsegment access".

After row <NUM> is identified, it is moved in its entirety to the rowstore <NUM>. In the example of <FIG>, row <NUM> is moved to the first row of the rowstore <NUM>, row <NUM>. Advantageously, the extraction of a particular row from the columnstore <NUM> to the rowstore <NUM> is not reliant on custom scripts written by a user of a computer system associated with the columnstore <NUM>.

<FIG> shows the columnstore <NUM> and the rowstore <NUM>, according to an example. The rowstore <NUM> contains row <NUM> of the columnstore <NUM> in row <NUM>. After row <NUM> is moved to row <NUM> of the rowstore, an access lock may be applied to the identifier ("rowID") of row <NUM>, that is the segment identifier ("segment ID") and row number ("rowNumber") pair, which is (<NUM>, <NUM>), within the rowstore <NUM> and the columnstore <NUM>. Whilst the access lock is active the data within row <NUM> is manipulated in accordance with the query Q'. Accordingly, the text "bdf' is updated to "bdh". After the manipulation of row <NUM> is completed and row <NUM> contains updated data the access lock is released. The access lock is understood to be a temporary, row-level access lock that blocks access to the row in question but, due to its row-level granularity, allows other processes to access the first segment <NUM> of which row <NUM> is a part, which means concurrent processes can be carried out within the segment <NUM> without waiting, thus improving system throughput and response time. As a result of the moving and/or the updating of row <NUM>, its status is updated to indicate that updated data of row <NUM> is located in the rowstore <NUM>.

The row-level lock provides fine-grain concurrency control compared to segment-level lock, which means that conflicts between processes requiring access to the same segment, such as two write requests, is reduced because the likelihood of the two write requests requiring access to the same row is less than the probability of the two requests requiring access to the same segment.

In the example of <FIG>, the row number array <NUM> of the columnstore <NUM> updates the status of row <NUM> by incorporating a pointer to row <NUM> in the rowstore <NUM> in place of row <NUM>; this is depicted in <FIG> using "<NUM>" within the row number array <NUM>. In some examples, a log data structure (not shown) comprises statuses of each of the rows in the columnstore <NUM> and thereby indicates whether a particular row in the columnstore <NUM> is active or has moved to the rowstore <NUM>, in which case the row of the columnstore <NUM> is marked as inactive or retired. The log data structure may contain records of rows in the rowstore <NUM> that correspond to retired rows within the columnstore <NUM>. For example, the log data structure may be a bit vector marking the inactive or retired rows.

The rowstore <NUM> may comprise multiple indexes, for example, more than one or each column of the rowstore <NUM> may correspond to at least one index table. Referring to <FIG>, the "identifier" and "text" columns of the rowstore <NUM> could have corresponding index tables. Having multiple index tables associated with the rowstore <NUM> improves the performance of a lookup by enabling fast seeking to rows within the rowstore <NUM> rather than scanning the entire rowstore <NUM>.

<FIG> shows the rowstore <NUM>, according to an example. The plurality of rows <NUM> of the rowstore <NUM> contain data: the first row, row <NUM>, contains row <NUM> of the columnstore <NUM> after it was promoted and updated as a result of the received query, Q'; and the second row, row <NUM>, contains another row promoted from the columnstore <NUM> as a result of another, different query and contains the identifier <NUM> and the text mnl. After a predetermined period of time, for example, when a predefined number of rows of the plurality of rows <NUM> are unchanged for a predetermined period of time, for example <NUM> minutes, a new segment of the columnstore <NUM> is created comprising the data of the rowstore <NUM>. In another example, a new segment of the columnstore <NUM> may be created as a result of the size of the rowstore <NUM> satisfying (for example, exceeding) a predetermined size threshold for the rowstore <NUM>. As an example, a predetermined size threshold for the rowstore <NUM> may be <NUM> MB.

<FIG> shows a new segment <NUM> of the columnstore <NUM> that has a first column 121d containing identifiers and a second column 122d containing text, according to an example. Creating a new segment of a columnstore <NUM> based on the status of the rowstore <NUM> moves all or some of the data that was previously stored in the rowstore <NUM> into the new segment of the columnstore <NUM>.

In some cases, recently accessed data is promoted from the columnstore and then maintained within the rowstore and not moved into a new segment, allowing the rowstore <NUM> to contain the recently accessed data. This improves concurrency within the table comprising the columnstore <NUM> and the rowstore <NUM>, increases throughput and results in lower wait time for queries to be processed.

An agent could be designed and used with the combined columnstore <NUM> and rowstore <NUM> data structure of <FIG>. In one example, the agent is configured to analyze queries that are received over a predetermined time period. The analysis carried out by the agent could be to profile incoming queries and identify a frequency of certain types of queries to determine the most recently used or most frequently used queries. An index of such queries could be built for future reference to speed up query processing.

Such analysis could form the basis of operations performed by the agent to speed up future query processing and obtaining of results. In some examples, the agent may: determine commonly used filters and/or indexes; automatically determine which columns of a columnstore to index without user input; when to generate a new column segment from a rowstore; dynamically determine whether to store data in a row-wise or column-wise format based on previously received queries relating to said data, for instance whether the data is relied upon for transaction and/or analytical processed. Using an agent in this manner would make the columnstore <NUM> and the rowstore <NUM> more tunable.

In one example, the agent could be embodied using machine learning. For instance, the agent may undergo one or more training and testing phases. In a training phase the agent is provided with a set of queries that train the agent to recognize patterns in the queries and subsequently perform various actions based on the recognized patterns, for example, to build indexes that would benefit a filter present within a plurality of queries. In a testing phase, the agent is provided with another set of queries and its performance in analyzing those queries is monitored, for example, how much performance is gained from the indexes built by the agent based on the recognized patterns or how successful the agent is in recognizing a particular filter. The performance of the agent in a testing phase may form the basis of the next or future training phase of the agent. For example, to improve the agent in areas where it had a weaker performance. In some examples, the agent is defined by computer readable instructions that are executed by a processor of a computing system.

At least some aspects of the embodiments described herein with reference to <FIG> comprise computer processes performed in processing systems or processors. However, in some examples, the invention also extends to computer programs, particularly computer programs on or in a carrier, adapted for putting the invention into practice. The program may be in the form of non-transitory source code, object code, a code intermediate source and object code such as in partially compiled form, or in any other non-transitory form suitable for use in the implementation of processes according to the invention. The carrier may be any entity or device capable of carrying the program. For example, the carrier may comprise a storage medium, such as a solid-state drive (SSD) or other semiconductor-based RAM; a ROM, for example a CD ROM or a semiconductor ROM; a magnetic recording medium, for example a floppy disk or hard disk; optical memory devices in general; etc..

In the preceding description, for purposes of explanation, numerous specific details of certain examples are set forth. Reference in the specification to "an example" or similar language means that a particular feature, structure, or characteristic described in connection with the example is included in at least that one example, but not necessarily in other examples.

Claim 1:
A computer-implemented method (<NUM>) of processing a query, the method comprising:
obtaining a columnstore comprising a plurality of columns and a plurality of rows, wherein each of the plurality of columns is segmented into a plurality of segments, wherein each segment of the respective column comprises a plurality of rows;
receiving (<NUM>) a query comprising a first parameter and a second parameter;
determining (<NUM>) a first key corresponding to the first parameter;
identifying (<NUM>) a mapping structure, from a first plurality of mapping structures, relating to said first key, wherein each mapping structure corresponds to a respective segment of the columnstore;
interrogating (<NUM>) the identified mapping structure to determine a value corresponding to the first key, wherein the value identifies an entry of an index table of a first plurality of index tables that corresponds to the respective segment, wherein the identified entry of the index table identifies a row of the respective segment of the columnstore relating to the first parameter;
determining that the second parameter is less selective than the first parameter;
determining (<NUM>) a second key relating to the second parameter;
identifying (<NUM>) a further mapping structure, from a second plurality of mapping structures, relating to said second key, wherein each mapping structure of the second plurality of mapping structures corresponds to a respective segment of the columnstore;
interrogating (<NUM>) the identified further mapping structure to determine a further value corresponding to the second key, wherein the further value identifies an entry of a further index table of a second plurality of index tables that corresponds to the respective segment, wherein the entry of the further index table identifies a row of the respective segment of the columnstore relating to the second parameter;
comparing the identified values relating to the first and second parameters;
identifying one or more intersections of the identified values based on the comparison; and
retrieving (<NUM>) data relating to the first parameter and the second parameter from the data source based on the one or more intersections.