Page filtering via compression dictionary filtering

• US 10,439,638 B2
• Filed: 09/06/2017
• Issued: 10/08/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/696,304
• Publication Number:
  US 20170371973A1
• Time in Patent Office: 762 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-implemented method comprising:

compressing, by a computer, 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;

receiving, by the computer, a part of the compressed page and the compression dictionary;

receiving, by the computer, a page symbol list, comprising compression symbols from the compression dictionary that are present in the part of the page;

receiving, by the computer, a query, wherein the query includes a predicate having a predicate value;

generating, by the computer, 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;

generating, by the computer, a page symbol indicator data, indicating which compression symbols from the compression dictionary are present among the compression symbols in the page symbol list;

generating, by the computer, a predicate symbol indicator data, indicating which compression symbols from the compression dictionary are present among the compression symbols in the predicate symbol list;

determining, by the computer, 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;

determining, by the computer, 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

performing, by the computer, the query, whereby the predicate is evaluated on the part of the page.

2. The method 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 method 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

determining that at least one compression symbol from the predicate symbol list is also present in the part of the page comprises determining 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 method of claim 1, wherein

the compression dictionary includes column indicator data, indicating, for each symbol in the compression dictionary which columns of the database table may include the 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 method 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 method 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.