Normalizing data for fast superscalar processing

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.

I claim: 
     
         1 . A computing apparatus comprising:
 one or more computer readable storage media;   a processing system operatively coupled with the one or more computer readable storage media;   program instructions for normalizing an in-memory representation of stored data for faster superscalar processing, wherein the program instructions, when executed by the processing system, direct the processing system to at least:
 access stored data that includes multiple columns, each column having a data type; 
 select a column in the accessed data to determine an appropriate in-memory representation; 
 determine a data type of the selected column; 
 determine 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; 
 determine a fixed size value for a normalized data representation, wherein the fixed sized value is sized such that it can be processed by a superscalar processor as a single instruction; and 
 upon determining that the row data can be normalized, convert the row data associated with the selected column into the normalized data representation, wherein the normalized data representation is a format that allows performing parallel processing of the normalized data representation using the superscalar processor. 
   
     
     
         2 . The computing apparatus of  claim 1  wherein the format represents multiple data types as the determined fixed size value that can be processed by the superscalar processor in the single instruction. 
     
     
         3 . The computing apparatus of  claim 1  wherein the stored data comprises a file-based tabular representation of a database, including tables with columns and rows of data. 
     
     
         4 . The computing apparatus of  claim 1  wherein to select the column, the processing system accesses a list of columns and iterates through each column in the list. 
     
     
         5 . The computing apparatus of  claim 1  wherein to determine the data type of the selected column, the processing system accesses metadata in the stored data that identifies a type of the column data declared by a database designer. 
     
     
         6 . The computing apparatus of  claim 1  wherein to determine whether the row data can be normalized, the processing system receives 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. 
     
     
         7 . The computing apparatus of  claim 1  wherein to convert the row data into the normalized data representation, the processing system stores the row data in a fixed size numeric value into which the system stores multiple different native data types. 
     
     
         8 . The computing apparatus of  claim 1  wherein the processing system is further directed to, upon determining that the row data cannot be normalized, identify a non-normalized data structure for storing row data associated with the selected column, and store a pointer to an instance of the identified non-normalized data structure in a normalized data value. 
     
     
         9 . The computing apparatus of  claim 8  wherein to store a pointer, the processing system sets the normalized data value to the pointer value and sets an unused bit of the pointer value to indicate that the normalized value points to another data structure. 
     
     
         10 . The computing apparatus of  claim 1  wherein the processing system is further directed to store row data values that fall outside of a range that the normalized data representation can contain in a non-normalized structure. 
     
     
         11 . A method for 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;   determining a fixed size value for a normalized data representation, wherein the fixed sized value is sized such that it can be processed by a superscalar processor as a single instruction; and   upon determining that the row data can be normalized, converting the row data associated with the selected column into the normalized data representation, wherein the normalized data representation is a format that allows performing parallel processing of the normalized data representation using the superscalar processor.   
     
     
         12 . The method of  claim 11  wherein the format represents multiple data types as the determined fixed size value that can be processed by the superscalar processor in the single instruction. 
     
     
         13 . The method of  claim 12  wherein the stored data comprises a file-based tabular representation of a database, including tables with columns and rows of data. 
     
     
         14 . The method of  claim 11  wherein selecting the column comprises accessing a list of columns and iterating through each column in the list. 
     
     
         15 . The method of  claim 11  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. 
     
     
         16 . The method of  claim 11  determining whether the 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. 
     
     
         17 . The method of  claim 11  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. 
     
     
         18 . The method of  claim 11  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. 
     
     
         19 . The method of  claim 18  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. 
     
     
         20 . The method of  claim 11  further comprising storing row data values that fall outside of a range that the normalized data representation can contain in a non-normalized structure.