NORMALIZING DATA FOR FAST SUPERSCALAR PROCESSING

• US 20110276607A1
• Filed: 05/05/2010
• Published: 11/10/2011
• Est. Priority Date: 05/05/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Khanolkar, Nimish S., Rangarajan, Srikumar, Ismert, Erik, Surna, Aleksandras
• Granted Patent: US 8,631,039 B2
• Time in Patent Office: Days
• US Class Current: 707/812
• 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-implemented method for normalizing an in-memory representation of stored data for faster superscalar processing, the method comprising:

accessing stored data that includes multiple columns, each column having a data type;

selecting a column in the accessed data to determine an appropriate in-memory representation;

determining a data type of the selected column;

determining whether row data associated with the selected column can be normalized based at least in part on the determined data type of the selected column; and

upon determining that the row data can be normalized, converting the row data associated with the selected column into a normalized data representation,

wherein the preceding steps are performed by at least one processor.

2. The method of claim 1 wherein the stored data comprises a file-based tabular representation of a database, including tables with columns and rows of data.

3. The method of claim 1 wherein selecting the column comprises accessing a list of columns and iterating through each column in the list.

4. The method of claim 1 wherein determining the data type of the selected column comprises accessing metadata in the stored data that identifies a type of the column data declared by a database designer.

5. The method of claim 1 wherein determining whether row data can be normalized comprises receiving configuration information that determines whether the normalized data representation is used for storing data in memory, including conditions for determining whether the normalized data representation is used.

6. The method of claim 1 wherein converting the row data into the normalized data representation comprises storing the row data in a fixed size numeric value into which the system stores multiple different native data types.

7. The method of claim 1 wherein the normalized data representation is a format that allows performing parallel processing of multiple instances of the normalized data representation using a superscalar processor.

8. The method of claim 1 further comprising, upon determining that the row data cannot be normalized, identifying a non-normalized data structure for storing row data associated with the selected column, and storing a pointer to an instance of the identified non-normalized data structure in a normalized data value.

9. The method of claim 8 wherein storing a pointer comprises setting the normalized data value to the pointer value and setting an unused bit of the pointer value to indicate that the normalized value points to another data structure.

10. The method of claim 1 further comprising storing row data values that fall outside of a range that the normalized data representation can contain in a non-normalized structure.

11. 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;

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.

12. The system of claim 11 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.

13. The system of claim 11 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.

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

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

16. A computer-readable storage medium comprising instructions for controlling a computer system to perform an operation on a tabular set of data having rows and columns, wherein the instructions, when executed, cause a processor to perform actions comprising:

identifying a batch of operations that can be executed in parallel by a superscalar processor;

identifying zero or more non-normalized rows of data associated with the batch of operations;

submitting the identified batch of operations that involve normalized rows of data to the superscalar processor for parallel processing;

submitting the identified batch of operations that involve identified non-normalized rows of data for processing; and

reporting results of performing the batch of operations to a requestor of the operations.

17. The medium of claim 16 wherein identifying the batch of operations comprises determining that an operation operates on each element of an array of data, and that the processor can handle each element independently.

18. The medium of claim 16 wherein the batch of operations that involve normalized rows of data include operations with reduced control flow and data interdependencies.

19. The medium of claim 16 wherein submitting the identified batch of operations that involve non-normalized rows includes instructions that are separated from one or more instructions that can be performed faster in parallel to benefit from the capabilities of the superscalar processor.

20. The medium of claim 16 wherein the normalized rows include string data stored in a fixed-size numeric value.