US 10,382,056 B2Granted

Fast evaluation of predicates against compressed data

AssigneeInternational Business Machines Corporation

InventorRobert W. Lyle

Life of this patent

Estimating the term…

Loading patent…

Abstract

Evaluating LIKE predicates against compressed data. An alphabet, a LIKE predicate, a compressed string, and a compression dictionary for the compressed string are received. Entries in the compression dictionary include a character string and an associated token. The LIKE predicate is converted to an equivalent pattern matching form, involving a search pattern of length m. For each character of the alphabet that appears in a string associated with a token, a mask of predetermined length k is created. For each entry in the compression dictionary a cumulative mask of length k is computed. A bit vector of length k is initialized, based on the search pattern. Successive tokens in the compressed string are processed using a logical shift of the bit vector and a bitwise operation of the bit vector with the cumulative mask associated with the token.

Claims19

Dependent claims

A computer-implemented method for evaluating LIKE predicates against compressed data, the method comprising:

receiving, by a computer, an alphabet, a LIKE predicate, a compressed string, and a compression dictionary for the compressed string, the compression dictionary comprising entries that include a character string and an associated token, and wherein at least one character string of the entries contains an end of value character, wherein the compressed string is a compressed column of a relational database, and wherein the LIKE predicate is selected from a group of patterns consisting of:
a sequence of characters and a wild card following the sequence of characters, a sequence of characters and a wild card preceding the sequence of characters, and a sequence of characters and wild cards preceding and following the sequence of characters;
converting, by the computer, the LIKE predicate to an equivalent pattern matching form, including a search pattern;
creating, by the computer, for each character of the alphabet that appears in a string associated with a token, a mask of a predetermined length k;
computing, by the computer, for an entry in the compression dictionary a cumulative mask of length k;
initializing, by the computer, a bit vector of length k;
processing, by the computer, successive tokens in the compressed string, using a logical shift of the bit vector and a bitwise operation of the bit vector with the cumulative mask associated with the token;
determining one or more matches between the LIKE predicate and a portion of the compressed string based on the processing of successive tokens;
and
returning tuplets relating to the location of the one or more matches in the column of the relational database.

7 more elements

A computer system for evaluating LIKE predicates against compressed data, the 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 receive an alphabet, a LIKE predicate, a compressed string, and a compression dictionary for the compressed string, the compression dictionary comprising entries that include a character string and an associated token, and wherein at least one character string of the entries contains an end of value character, wherein the compressed string is a compressed column of a relational database, and wherein the LIKE predicate is selected from a group of patterns consisting of:
a sequence of characters and a wild card following the sequence of characters, a sequence of characters and a wild card preceding the sequence of characters, and a sequence of characters and wild cards preceding and following the sequence of characters;
program instructions to convert the LIKE predicate to an equivalent pattern matching form, including a search pattern;
program instructions to create for each character of the alphabet that appears in a string associated with a token, a mask of a predetermined length k;
program instructions to compute for an entry in the compression dictionary a cumulative mask of length k;
program instructions to initialize a bit vector of length k;
program instructions to process successive tokens in the compressed string, using a logical shift of the bit vector and a bitwise operation of the bit vector with the cumulative mask associated with the token;
program instructions to determine one or more matches between the LIKE predicate and a portion of the compressed string based on the processing of successive tokens;
and
program instructions to return tuplets relating to the location of the one or more matches in the column of the relational database.

8 more elements

A computer program product for evaluating LIKE predicates against compressed data, the 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 receive an alphabet, a LIKE predicate, a compressed string, and a compression dictionary for the compressed string, the compression dictionary comprising entries that include a character string and an associated token, and wherein at least one character string of the entries contains an end of value character, wherein the compressed string is a compressed column of a relational database, and wherein the LIKE predicate is selected from a group of patterns consisting of:
a sequence of characters and a wild card following the sequence of characters, a sequence of characters and a wild card preceding the sequence of characters, and a sequence of characters and wild cards preceding and following the sequence of characters;
program instructions to convert the LIKE predicate to an equivalent pattern matching form, including a search pattern;
program instructions to create for each character of the alphabet that appears in a string associated with a token, a mask of a predetermined length k;
program instructions to compute for an entry in the compression dictionary a cumulative mask of length k;
program instructions to initialize a bit vector of length k;
program instructions to process successive tokens in the compressed string, using a logical shift of the bit vector and a bitwise operation of the bit vector with the cumulative mask associated with the token;
program instructions to determine one or more matches between the LIKE predicate and a portion of the compressed string based on the processing of successive tokens;
and
program instructions to return tuplets relating to the location of the one or more matches in the column of the relational database.

8 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/937,067Filed 10 Nov 2015
Published: US 2017/0134044 A111 May 2017
Granted: 13 Aug 2019
Term ends: Not estimatedThe source records don’t support an estimate.

Classification8 codes

H03M 7/3088
Using adaptive string matching, e.g. the Lempel-Ziv method: employing the use of a dictionary, e.g. LZ78
G06F 16/2458
Query processing: special types of queries, e.g. statistical queries, fuzzy queries or distributed queries
G06F 16/284
Databases characterised by their database models, e.g. relational or object models: relational databases
H03M 7/3066
Compression ; Expansion; Suppression of unnecessary data, e.g. redundancy reduction: by means of a mask or a bit-map