Page filtering via compression dictionary filtering

• US 10,432,217 B2
• Filed: 06/28/2016
• Issued: 10/01/2019
• Est. Priority Date: 06/28/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Finlay, Ian R.
• Primary Examiner(s): Skhoun, Hicham
• Application Number:
  US15/194,635
• Publication Number:
  US 20170371972A1
• Time in Patent Office: 1,190 Days
• Field of Search: 707756
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/60 General implementation details not specific to a particular type of compression

Abstract

Page filtering in a database using a compression dictionary. A page of a database table is compressed, creating a compression dictionary. The compression dictionary includes entries with a byte sequence from the page and a compression symbol associated with the byte sequence. A part of the compressed page, the compression dictionary, and a page symbol list with compression symbols from the dictionary present in the part of the page, are received. A query having a predicate with a predicate value is received. A predicate symbol list, including symbols in the dictionary whose byte sequences at least partially match the predicate value, is generated. Based on the predicate symbol list and the page symbol list, it is determined that at least one symbol from the predicate symbol list is also present in the part of the page. The query is performed by evaluating the predicate on the part of the page.

Claims

1. A computer system comprising:

one or more computer processors, one or more computer-readable storage media, and program instructions stored on one or more of the computer-readable storage media for execution by at least one of the one or more processors, the program instructions comprising;

program instructions to compress a page of a database table, whereby a compression dictionary is created, the compression dictionary comprising entries that include a byte sequence from the page and a compression symbol associated with the byte sequence;

program instructions to receive a part of the compressed page and the compression dictionary;

program instructions to receive a page symbol list, comprising compression symbols from the compression dictionary that are present in the part of the page;

program instructions to receive a query, wherein the query includes a predicate having a predicate value;

program instructions to generate a predicate symbol list for the predicate, comprising compression symbols in the compression dictionary whose associated byte sequences at least partially match the predicate value;

program instructions to generate a page symbol indicator data, indicating which compression symbols from the compression dictionary are present among the compression symbols in the page symbol list;

program instructions to generate a predicate symbol indicator data, indicating which compression symbols from the compression dictionary are present among the compression symbols in the predicate symbol list;

program instructions to determine, based on the page symbol indicator data and the predicate symbol indicator data, that at least one compression symbol from the predicate symbol list is also present in the part of the page;

program instructions to determine, based on the predicate symbol list and the page symbol list, that at least one compression symbol from the predicate symbol list is also present in the part of the page; and

program instructions to perform the query, whereby the predicate is evaluated on the part of the page.

2. The computer system of claim 1, wherein the predicate symbol list for the predicate comprises compression symbols in the compression dictionary whose associated byte sequences:

match the predicate value, or contain a subsequence that matches the predicate value, or have a suffix that matches a prefix of the predicate value, or have a prefix that matches a suffix of the predicate value.

3. The computer system of claim 1, wherein

the page symbol indicator data comprises a first bit vector with bit positions corresponding to entries in the compression dictionary, wherein a 1 bit in a bit position of the first bit vector indicates the presence of a corresponding compression symbol in the part of the page;

and wherein

the predicate symbol indicator data comprises a second bit vector with bit positions corresponding to entries in the compression dictionary, wherein a 1 bit in a bit position of the second bit vector indicates the presence of a corresponding compression symbol among the compression symbols in the predicate symbol list; and

wherein

program instructions to determine that at least one compression symbol from the predicate symbol list is also present in the part of the page comprise program instructions to determine that the first bit vector has a 1 bit in at least one of the bit positions where the second bit vector has a 1 bit.

4. The computer system of claim 1, wherein

the compression dictionary includes column indicator data, indicating, for each compression symbol in the compression dictionary which columns of the database table may include the compression symbol, and wherein

the predicate symbol list comprises compression symbols in the compression dictionary for which the column indicator data indicates that the compression symbols may be present in a search column of the query, whose associated byte sequences:

match the predicate value, or contain a subsequence that matches the predicate value, or have a suffix that matches a prefix of the predicate value, or have a prefix that matches a suffix of the predicate value.

5. The computer system of claim 4, wherein the column indicator data comprises, for each compression symbol in the compression dictionary, a list of columns of the database table that may include the compression symbol.

6. The computer system of claim 4, wherein the column indicator data comprises a bit vector with bit positions corresponding to columns of the database table in which the compression symbol may appear.

7. A computer program product comprising:

one or more computer-readable storage media and program instructions stored on the one or more computer-readable storage media, the program instructions comprising;

program instructions to compress a page of a database table, whereby a compression dictionary is created, the compression dictionary comprising entries that include a byte sequence from the page and a compression symbol associated with the byte sequence;

program instructions to receive a part of the compressed page and the compression dictionary;

program instructions to receive a page symbol list, comprising compression symbols from the compression dictionary that are present in the part of the page;

program instructions to receive a query, wherein the query includes a predicate having a predicate value;

program instructions to generate a predicate symbol list for the predicate, comprising compression symbols in the compression dictionary whose associated byte sequences at least partially match the predicate value;

program instructions to generate a page symbol indicator data, indicating which compression symbols from the compression dictionary are present among the compression symbols in the page symbol list;

program instructions to generate a predicate symbol indicator data, indicating which compression symbols from the compression dictionary are present among the compression symbols in the predicate symbol list;

program instructions to determine, based on the page symbol indicator data and the predicate symbol indicator data, that at least one compression symbol from the predicate symbol list is also present in the part of the page;

program instructions to determine, based on the predicate symbol list and the page symbol list, that at least one compression symbol from the predicate symbol list is also present in the part of the page; and

program instructions to perform the query, whereby the predicate is evaluated on the part of the page.

8. The computer program product of claim 7, wherein the predicate symbol list for the predicate comprises compression symbols in the compression dictionary whose associated byte sequences:

match the predicate value, or contain a subsequence that matches the predicate value, or have a suffix that matches a prefix of the predicate value, or have a prefix that matches a suffix of the predicate value.

9. The computer program product of claim 7, wherein

the page symbol indicator data comprises a first bit vector with bit positions corresponding to entries in the compression dictionary, wherein a 1 bit in a bit position of the first bit vector indicates the presence of a corresponding compression symbol in the part of the page;

and wherein

the predicate symbol indicator data comprises a second bit vector with bit positions corresponding to entries in the compression dictionary, wherein a 1 bit in a bit position of the second bit vector indicates the presence of a corresponding compression symbol among the compression symbols in the predicate symbol list; and

wherein

program instructions to determine that at least one compression symbol from the predicate symbol list is also present in the part of the page comprise program instructions to determine that the first bit vector has a 1 bit in at least one of the bit positions where the second bit vector has a 1 bit.

10. The computer program product of claim 7, wherein

the compression dictionary includes column indicator data, indicating, for each compression symbol in the compression dictionary which columns of the database table may include the compression symbol, and wherein

the predicate symbol list comprises compression symbols in the compression dictionary for which the column indicator data indicates that the compression symbols may be present in a search column of the query, whose associated byte sequences:

match the predicate value, or contain a subsequence that matches the predicate value, or have a suffix that matches a prefix of the predicate value, or have a prefix that matches a suffix of the predicate value.

11. The computer program product of claim 10, wherein the column indicator data comprises a bit vector with bit positions corresponding to columns of the database table in which the compression symbol may appear.