Database table index

A method of determining one most specific row within a database table including a plurality of rows and a plurality of columns, the rows and columns of the database table forming cells, each cell including either at least one value or no value, the method comprising:

• maintaining, by a computer system, an index for the database table, the index indicating an order of specificity of the rows of the database table and including a respective index structure for each column of the database table, the index structure including a respective array of pointer tuples for each value occurring in the respective column and a bitmap, each pointer tuple including 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 the bitmap indicating the cells within the respective column having no values using a first designation and indicating the cells within the respective column having values using a second designation that is distinct from the first designation;
• receiving, by the computer system, a request indicating at least one column of the database table associated with a respective input value;
• incrementally, for each column, the computer system:
• applying the bitmap of the index structure for the column to maintain all rows of the database table containing no values in the cell of the column considered, and
• applying the pointer tuples of the index structure for the column to filter all rows of the database table which do not include the respective input value;
• selecting, by the computer system from the remaining rows after the bitmap and the pointer tuples of the index structure are applied, the one most specific row that is highest in the order of specificity;
• and
• returning, by the computer system, the value of at least one cell of the one most specific row.

A computer program product for determining one most specific row within a database table including a plurality of rows and a plurality of columns, the rows and columns of the database table forming cells, each cell including either at least one value or no value, the computer program product comprising:

• a processor;
• and
• a memory including a non-transitory computer-readable storage medium;
• and
• program code that, when executed by the processor, causes the processor to:
• maintain an index for the database table, the index indicating an order of specificity of the rows of the database table and including a respective index structure for each column of the database table, the index structure including a respective array of pointer tuples for each value occurring in the respective column and a bitmap, each pointer tuple including 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 the bitmap indicating the cells within the respective column having no values using a first designation and indicating the cells within the respective column having values using a second designation that is distinct from the first designation;
• receive a request indicating at least one column of the database table associated with a respective input value;
• incrementally, for each column:
• apply the bitmap of the index structure for the column to maintain all rows of the database table containing no values in the cell of the column considered, and
• apply the pointer tuples of the index structure for the column to filter all rows of the database table which do not include the respective input value;
• select from the remaining rows, after the bitmap and the pointer tuples of the index structure are applied, the one most specific row that is highest in the order of specificity;
• and
• return the value of at least one cell of the one most specific row.