Normalizing data for fast superscalar processing

• US 9,547,674 B2
• Filed: 01/13/2014
• Issued: 01/17/2017
• Est. Priority Date: 05/05/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Surna, Aleksandras, Ismert, Erik, Rangarajan, Srikumar, Khanolkar, Nimish S.
• Primary Examiner(s): NGUYEN, KIM T
• Application Number:
  US14/154,159
• Publication Number:
  US 20140129525A1
• Time in Patent Office: 1,100 Days
• Field of Search: 707/790, 707/812
• US Class Current: 1/1
• CPC Class Codes: G06F 15/82 data or demand driven
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 9/30192 according to data descriptor, e.g. dynamic data typing
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units

Abstract

A data normalization system is described herein that represents multiple data types that are common within database systems in a normalized form that can be processed uniformly to achieve faster processing of data on superscalar CPU architectures. The data normalization system includes changes to internal data representations of a database system as well as functional processing changes that leverage normalized internal data representations for a high density of independently executable CPU instructions. Because most data in a database is small, a majority of data can be represented by the normalized format. Thus, the data normalization system allows for fast superscalar processing in a database system in a variety of common cases, while maintaining compatibility with existing data sets.

Claims

1. A computer system for storing and processing data in a manner that encourages parallel processing by one or more superscalar processors, the system comprising:

a processor and memory configured to execute software instructions;

a data storage component configured to store database data persistently between sessions of use of the system;

a data normalization component configured to retrieve data stored by the data storage component and to load the retrieved data into memory in a normalized data representation that allows fast superscalar processing, wherein the normalized data representation is a fixed size value and is sized such that it can be processed by the one or more superscalar processors as a single instruction;

an operation manager configured to manage requests to perform database operations on stored database data;

a batch assembly component configured to identify batches of data that have control flow and data independence such that the batch includes parallelizable operations;

an outlier identification component configured to identify data values in a batch of data that cannot be performed by a fast processing path that performs efficient superscalar processing;

a fast operation component configured to provide instructions to a superscalar processor in a manner that allows parallel execution of the instructions by multiple functional units of the superscalar processor;

a slow operation component configured to perform database operations on data within a batch that is not stored in the normalized data representation; and

a result processing component configured to gather results from the fast operation component and slow operation component and return the results to an operation requestor.

2. The system of claim 1 wherein the data normalization component is further configured to use a common format for storing multiple data types, so that processing of normalized data can be handled in a unified manner for a variety of data types.

3. The system of claim 1 wherein the data normalization component is further configured to provide an in-memory representation of data that is not normalized, by providing a normalized value that includes a pointer to a data structure for storing non-normalized values.

4. The system of claim 1 wherein the data normalization component is further configured to select an appropriate normalized representation for each data type.

5. The system of claim 1 wherein the result processing component is further configured to merge data from fast and slow paths into a unified result set.

6. The system of claim 1 further comprising:

a query engine configured to;

receive a query from one or more users or applications;

develop a query plan;

execute the query against a dataset; and

provide results back to the one or more users or applications.

7. The system of claim 1 wherein the operation manager is further configured to invoke other components of the system to efficiently use the one or more superscalar processors.

8. The system of claim 1 wherein the batch assembly component is further configured to separate data into groups that minimize control flow interruptions.

9. The system of claim 1 wherein the batch assembly component is further configured to separate data into groups that can perform multiple operations on the one or more superscalar processors in an efficient manner.

10. The system of claim 1 wherein the outlier identification component is further configured to separate outlying data into a separate data structure.

11. The system of claim 1 wherein the outlier identification component is further configured to traverse an array of data and identify values in the array that are not represented in a normalized representation of the data.

12. The system of claim 11 wherein the outlier identification component is further configured to place the identified values in the array in a queue for post processing at a later time.

13. The system of claim 1 wherein the outlier identification component and the fast operation component are merged into a single component.

14. The system of claim 1 wherein the fast operation component is further configured to perform operations on the data in a tight loop or with multiple independent loop operations executable in each loop iteration.

15. The system of claim 1 wherein the slow operation component is further configured to process data that is of a nonstandard type.