Patent application EP17000126A (EP), filed 2017-01-25
Publication number: EP3203388A1
Title: DATABASE TABLE INDEX
Abstract: An index for a database table is provided. The index includes an index structure for each column of the database table. Each index structure includes an array of pointer tuples for each value occurring in the column and a bitmap indicating cells without values. A first pointer of the tuple indicates a value and a second pointer indicates the row of the database table with the value. The index also indicates an order of specificity of the rows of the database table. The computer system processes a request by using the bitmaps of the index structures to maintain all rows of the database table without values and the pointer tuples to filter all rows of the database table which do not include the respective input value. The one row being highest in the order of specificity from the remaining rows is selected and returned.
IPC codes: G06F  17/    30            A I
G06F  16/    22            A I
Claims: number: 1
text: A method of determining one most specific row within a database table maintained by a computer system,
the database table comprising a plurality of rows and a plurality of columns, the rows and columns of the database table forming cells, wherein each cell either includes at least one value or no value;
the computer system also maintaining an index for the database table;
the index including a respective index structure for each column of the database table;
each index structure including a respective array of pointer tuples for each value occurring in the respective column and a bitmap, wherein the each pointer tuple includes a first pointer indicating one of the values occurring in the column and a second pointer indicating the row of the database table in which the value occurs, and wherein the bitmap indicates cells within the respective column without a value;
the index indicating an order of specificity of the rows of the database table;
the method comprising:
number: 2
text: The method according to claim 1 further comprising:
number: 3
text: The method according to claim 1, wherein the respective array of pointer tuples is stored contiguous in a memory of the computer system.
number: 4
text: The method according to any one of claims 1 to 3, wherein using the pointer tuples and the bitmap of the index structure for each column indicated in the request comprises further comprises performing a binary search on the respective array of pointer tuples.
number: 5
text: The method according to any one of claims 1 to 4, further comprising:
number: 6
text: The method according to claim 5, wherein generating the index further comprises:
number: 7
text: The method according to any one of claims 1 to 6, wherein the indication of the order of specificity of the rows of the database table is realized by sorting the rows of the database table depending on a number of cells in each row without values and/or a specificity of the values in the cells of the row.
number: 8
text: The method according to claim 7, wherein the indication of the order of specificity is given by a unique row order indicating the sorted rows.
number: 9
text: The method according to any one of claims 1 to 6, wherein the indication of specificity is given by weight values included in the index of the database table.
number: 10
text: The method of any one of claims 1 to 9 wherein the computer system is a router, the database table is a routing table, each row of the routing table constitutes a routing rule for routing an incoming request towards a destination, the routing table comprising a destination column with possible destination values and a route column with corresponding values indicating a route towards the destination.
number: 11
text: The method of any one of claims 1 to 9 wherein the computer system is a firewall, the database table is a filtering table, the request is an incoming data packet and each row of the filtering table constitutes a filtering rule for allowing or preventing the incoming data packet to be forwarded towards a destination, wherein the filtering table comprises at least one destination column with possible destination addresses, at least one column with values specifying characteristics of the incoming data packet and a column with Boolean values indicating whether the incoming data packet is to be forwarded or to be discarded.
number: 12
text: The method of any one of claims 1 to 11 wherein the index is stored in a processor cache of the computer system and remains to be stored in the processor cache after the value of at least one cell of the determined row has been returned to be available for processing further requests.
number: 13
text: A computer system for determining one most specific row within a database table maintained by the computer system,
the database table comprising a plurality of rows and a plurality of columns, the rows and columns of the database table forming cell, wherein each cell either includes at least one value or no value;
the computer system also maintaining an index for the database table;
the index including a respective index structure for each column of the database table;
each index structure including a respective pointer tuple for each value occurring in the respective column and a bitmap, wherein the each pointer tuple includes a first pointer indicating one of the values occurring in the column and a second pointer indicating the row of the database table in which the value occurs, and wherein the bitmap indicates cells within the respective column without a value;
the index indicating an order of specificity of the rows of the database table;
the computer system being configured to:
number: 14
text: The computer system according to claim 13 being arranged to perform the method of any one of claims 2 to 12.
number: 15
text: A computer program for instructing a computer system to perform the method of determining the most specific row within a database table, the database table comprising a plurality of columns, the rows and columns of the database forming cell, wherein each cell either includes at least one value or no value;
the computer system maintaining an index for the database table;
the index including a respective index structure for each column of the database table;
each index structure including a respective pointer tuple for each value occurring in the respective column and a bitmap, wherein the each pointer tuple includes a first pointer indicating one of the values occurring in the column and a second pointer indicating the row of the database table in which the value occurs, and wherein the bitmap indicates cells within the respective column without a value;
the index indicating an order of specificity of the rows of the database table;
the computer program configuring the computer system to perform the method of any one of claims 1 to 12.
Office action: search_report, dated 2017-08-09
Prior art cited: ref_id: EP1304849A2
ref_type: patent
severity: background
ref_id: US5951651A
ref_type: patent
severity: background
ref_id: US5951651
ref_type: patent
severity: background
ref_id: EP1304849
ref_type: patent
severity: background
Final disposition: pending (2017-08-09)