Predicate application through partial compression dictionary match

• US 9,780,806 B2
• Filed: 04/14/2015
• Issued: 10/03/2017
• Est. Priority Date: 10/22/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Finlay, Ian R.
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Santos, Pedro J
• Application Number:
  US14/685,947
• Publication Number:
  US 20160118998A1
• Time in Patent Office: 903 Days
• Field of Search: 707999003, 707E17014, 707693, 707802, 707741, 707715, 707706, 707E17084, 341106
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/4087 Encoding of a tuple of symbols
• CPC Class Codes: H03M 7/6005 Decoder aspects
• CPC Class Codes: H03M 7/6017 Methods or arrangements to increase the throughput

Abstract

Apparatus and systems, including computer program products, implementing and using techniques for predicate application using partial compression dictionary match. A search strategy is developed for each predicate to be applied to compressed data. The compressed data is searched using the search strategy to locate the compression symbols identified in the search strategy. In response to locating a compression symbol from the search strategy in the compressed data, a respective row and applying the predicate is decompressed and a respective row that matches the predicate is returned to a database engine or an application.

Claims

1. A computer-implemented method for predicate application using partial compression dictionary match, the method comprising:

developing a search strategy for each predicate to be applied to compressed data, the search strategy comprising;

searching entries of a compression dictionary for an entire predicate value to identify each matching symbol and noting an exact match, and a subsumed match of a compression symbol in a search list;

searching the entries of the compression dictionary to identify entries in which a predicate prefix forms a dictionary entry suffix and noting each matching compression symbol in the search list;

searching the entries of the compression dictionary to identify entries in which a predicate suffix forms a dictionary entry prefix and noting each matching compression symbol in the search list;

searching the entries of the compression dictionary to identify entries which form a mid-predicate match and noting each matching compression symbol in the search list; and

adding one or more uncompressed symbols for predicates having no match in the compression dictionary, and for predicates having only one or more subsumed dictionary matches;

searching the compressed data to locate the compression symbols identified in the search list; and

in response to locating a compression symbol from the search list in the compressed data,

decompressing a respective row and applying the predicate, and

returning a respective row that matches the predicate to one of;

a database engine and an application.

2. The method of claim 1, wherein searching the compressed data to locate the compression symbols identified in the search list further comprises:

tracking column positions and offset of the search list within the column; and

matching the compression symbol lists and associated column positions.

3. The method of claim 1, further comprising identifying a full match of each predicate by:

forming an initial search list including the compression symbols identified in the search strategy;

forming a finished match list, the finished match list including;

a predicate suffix for each predicate prefix that matches a dictionary entry suffix, wherein the predicate suffix includes one or more of;

uncompressed symbols and compressed mid-predicate match symbols,

a predicate prefix for each predicate suffix that matches a dictionary entry prefix, wherein the predicate prefix includes one or more of;

uncompressed symbols and compressed mid-predicate match symbols,

a mid-predicate match for each predicate prefix and predicate suffix that matches one of;

a dictionary entry prefix and a dictionary entry suffix and do not overlap in their matching of the predicate, wherein the mid-predicate match includes one or more of;

uncompressed symbols and compressed mid-predicate match symbols, and

a predicate prefix and a predicate suffix for each dictionary entry that forms a mid-predicate match, wherein the predicate prefix and predicate suffix includes one or more of;

uncompressed symbols and compressed mid-predicate match symbols;

searching the compressed data for lead compression symbols identified in the initial search list;

in response to locating a lead compression symbol from the initial search list in the compressed data, completing a predicate match by applying the associated symbols to the compression symbols identified in the finished match list; and

decompressing a respective row and fully applying the predicate using the initial search list, the finished match list and the lead compression symbols identified in the initial search list.

4. The method of claim 3, wherein fully applying the predicate further comprises:

including in the initial search list a column position associated with each symbol;

tracking column positions during the compressed data scan;

matching the compression symbol lists and associated column positions; and

qualifying with column position information, to form an exact predicate match, to fully qualify the row.

5. The method of claim 1, further comprising:

receiving a predicate to be applied to the compressed data.

6. The method of claim 3, wherein an associated symbol is one of:

a predicate suffix completing a dictionary entry suffix, a predicate prefix completing a dictionary suffix, a prefix completing a mid-predicate match and a suffix completing a mid-predicate match.

7. The method of claim 1, wherein the compressed data is multi-level compressed data.

8. The method of claim 1, wherein the dictionary is one of:

an embedded dictionary and a progressively built dictionary.

9. The method of claim 8, further comprising:

updating the initial search list is as the progressively built dictionary evolves.