International Business Machines Corporation

Microsoft Technology Licensing, LLC

Facebook, Inc.

Lin Qiao

Vijayshankar Raman

Richard Sefton Sidle

Ronald Jason Barber

Guy Maring Lohman

Eugene Jon Shekita

Sam Sampson Lightstone

Min-Soo Kim

Gopi K Attaluri

Frederick Ralph Reiss

Stefan Arndt

Garret Frederick Swart

Wei Han

Jae Gil Lee

Balakrishna Raghavendra Iyer

Peter Haas

Inderpal Singh Narang

You-Chin Gene Fuh

Fen-Ling Lin

Kapil Laxmikant Surlaker

Aamer U Sachedina

Min Tu

Hongzhong Jia

Sandeep Tata

Shirshanka Das

Rajiv Krishnamurthy

Yinan Li

Chavdar Botev

F Ryan Johnson

Issac Buenrostro

Ying-Lin Chen

Kouhorng Allen Yang

Narasimha R Veeramreddy

Ying Dai

Joshua David Metzler

Kenneth D Goodhope

Viyayshankar Raman

Sahil Takiar

Ziyang Liu

A dataset management system ('system') reduces the amount of data to be stored for future analyses. The system determines a sampling rate of the data based on a required level of accuracy, and samples the data at the determined sampling rate. Initially, all data transactions ('full dataset') and the sampled data (&#x201c;sampled dataset&#x201d;) are logged and stored. Based upon a trigger condition, e.g., after a specified period, the full dataset and the sampled dataset are analyzed separately and the analysis results are compared. If the comparison is sufficiently similar (i.e., the sampling produces a sufficiently accurate set of data or a variance between the analysis results of the datasets is within a specified threshold), the system discontinues full data logging and stores only the sampled dataset. Further, the full dataset is deleted. The sampling thus reduces the required data volume significantly, thereby minimizing consumption of the storage space.

Reducing data storage requirements

A database table is partitioned with column-major layout by limiting partitioning one or more columns containing join-column values for a join operator. Join operations are executed for joining the partitioned columns.

Efficient partitioned joins in a database with column-major layout

A system joins predicate evaluated column bitmaps having varying lengths. The system includes a column unifier for querying column values with a predicate generating an indicator bit for each of the column values that is then joined with the respective column value. The system also includes a bitmap generator for creating a column-major linear bitmap from the column values and indicator bits. The column unifier also determines an offset between adjacent indicator bits. The system also includes a converter for multiplying the column-major linear bitmap with a multiplier to shift the indicator bits into consecutive positions in the linear bitmap.

Multiplication-based method for stitching results of predicate evaluation in column stores

In order to ingest data from an arbitrary source in a set of sources, a computer system accesses predefined configuration instructions. Then, the computer system generates a dynamic data-ingestion pipeline that is compatible with a Hadoop file system based on the predefined configuration instructions. This dynamic data-ingestion pipeline includes a modular arrangement of operators from a set of operators that includes: an extraction operator for extracting the data of interest from the source, a converter operator for transforming the data, and a quality-checker operator for checking the transformed data. Moreover, the computer system receives the data from the source. Next, the computer system processes the data using the dynamic data-ingestion pipeline as the data is received without storing the data in memory for the purpose of subsequent ingestion processing.

Dynamic data-ingestion pipeline

The embodiments described herein relate to accessing a plurality of data elements. A page of column data is compressed and stored in a format that includes a collection of data elements. A tuple map is stored, and the collection of data elements is indexed via the tuple map. A query is processed based on the compressed page by identifying a set of tuple identifiers mapping to stored data in support of the query. Each tuple identifier corresponds to a location of a respective tuple of the compressed page.

Data encoding and processing columnar data

Embodiments of the present invention provide a database processing system for efficient partitioning of a database table with column-major layout for executing one or more join operations. One embodiment comprises a method for partitioning a database table with column-major layout, partitioning only the join-columns by limiting the partitions by size and number, executing one or more join operations for joining the partitioned columns, and optionally de-partitioning the join result to the original order by sequentially writing and randomly reading table values using P cursors.

System, method and computer program products for probing a hash table by receiving a compressed input key, computing a hash value for the compressed input key and probing one or more buckets in a hash table for a match. Each bucket includes multiple chunks. For a bucket in the hash table, chunks are searched in that bucket by comparing in parallel the hash value with multiple slots in each chunk, such that if a value in a chunk equals the hash value of the compressed input key, then a match is declared and a vector is returned with a significant bit of a matching slot in the bucket set to a value. If a value stored in a chunk corresponds to an empty slot, then a mismatch is declared, and the vector is returned as the result with the significant bit of a matching empty slot set to the value.

Systems, methods and computer program products for probing a hash table for improved latency and scalability in a processing system

A method for storing database information includes storing a table having data values in a column major order. The data values are stored in a list of blocks. The method also includes assigning a tuple sequence number (TSN) to each data value in each column of the table according to a sequence order in the table. The data values that correspond to each other across a plurality of columns of the table have equivalent TSNs. The method also includes assigning each data value to a partition based on a representation of the data value. The method also includes assigning a tuple map value to each data value. The tuple map value identifies the partition in which each data value is located.

Intra-block partitioning for database management

Aspects of the invention are provided for accessing a plurality of data elements. A page of column data is stored in a format that includes compressed and/or non-compressed elements, with the format including a plurality of arrays and a vector. Each of the arrays stores elements with common characteristics, with the vector functioning as a mapping to the stored data elements. The vector is leveraged to identify an array and determine an offset to support access to one or more of the data elements.

A system joins predicate evaluated column bitmaps having varying lengths. The system includes a column unifier for querying column values with a predicate and generating an indicator bit for each of the column values that is then joined with the respective column value. The system also includes a bitmap generator for creating a column-major linear bitmap from the column values and indicator bits. The column unifier also determines an offset between adjacent indicator bits. The system also includes a converter for multiplying the column-major linear bitmap with a multiplier to shift the indicator bits into consecutive positions in the linear bitmap.

System, method and computer program products for storing data by computing a plurality of hash functions of data values in a data item, and determining a corresponding memory location for one of the plurality of hash functions of data values in the data item. Each memory location is of a cacheline size wherein a data item is stored in a memory location. Each memory location can store a plurality of data items. A key portion of all data items is contiguously stored within the memory location, and a payload portion is contiguously stored within the memory location. Payload portions are packed as bit-aligned in a fixed-sized memory location, comprising a bucket in a bucketized hash table, each bucket sized to store multiple key portions and payload portions that are packed as bit-aligned in a fixed-sized bucket. Corresponding key portions are stored as compressed keys in said fixed-sized bucket.

Systems, methods and computer program products for reducing hash table working-set size for improved latency and scalability in a processing system

Embodiments of the present invention provide query processing for column stores by accumulating table record attributes during application of query plan operators on a table. The attributes and associated attribute values are compacted when said attribute values are to be consumed for an operation in the query plan, during the execution of the query plan. Table column record values are materialized late in query plan execution.

Predicate pushdown with late materialization in database query processing

Growing community of inventors

San Jose, CA, United States of America

Lin Qiao