HK1229918B - Managing data profiling operations related to data type - Google Patents

Description

Management of data profiling operations related to data types

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims priority to U.S. application serial number 61/949,477, filed on March 7, 2014.

Technical Field

This specification relates to the management of data profiling operations related to data types.

Background Art

Databases or other information management systems often include data sets, and many characteristics of the data sets may not be known. For example, for a data set, the range or typical values of its values, the relationship between different fields in the data set, or the functional correlation between the values of different fields may not be known. Data profiling may include examining the data set to determine the above characteristics. Some data profiling techniques include: receiving information about a data profiling job, running the data profiling job, and then returning the results of the operation after a delay, where the delay is based on the length of time it takes to perform the various processing steps involved in performing the data profiling. One of the steps that may involve significant processing time is "canonicalization", which involves changing the data type of the values appearing in the records of the data set to a predetermined or "standard" data type to facilitate other processing. For example, canonicalization may include converting the values into a human-readable string representation.

Summary of the Invention

In one aspect, generally speaking, a method for processing data in a computer system includes receiving, via an input device or port of the computer system, a plurality of records, each of the records including one or more values corresponding to each of a plurality of fields. The method further includes storing data type information in a storage medium of the computer system, the data type information associating each of the one or more data types with at least one identifier. The method further includes processing, using at least one processor of the computer system, the plurality of data values from the records. The processing includes: generating multiple data units based on the record, each of the data units including a field identifier and a binary value from one of the records, the field identifier uniquely marking one of the fields, and the binary value being extracted from the field of the record marked by the field identifier; collecting information about the binary values from the multiple data units; establishing a list of entries for each of one or more of the fields, at least some of the entries each including one of the binary values and information about the binary values collected from the multiple data units; obtaining a data type associated with a first identifier from the data type information, and associating the obtained data type with at least one binary value included in an entry in the list; and after collecting information about the binary values from the multiple data units, establishing profile information for at least one of the fields based at least in part on the obtained data type of a specific binary value appearing in the field.

A solution may include one or more of the following features.

The binary value extracted from the field of the record identified by the field identifier is extracted as an untyped bit sequence. Establishing parsing information for at least one of the fields based at least in part on the obtained data type of the specific binary value appearing in the field comprises reinterpreting the untyped bit sequence as a typed data value, the typed data value having the obtained data type.

The profiling information includes a type-dependent profiling result that depends on original data types of the plurality of data values of the record.

Gathering information about the binary values from a plurality of the data units includes comparing the binary values from the plurality of the data units with binary values in the list of entries to determine if a match exists between the binary values.

The information regarding the binary values collected from the plurality of the data units includes a total number of matching binary values, the total number being incremented each time a match is determined to exist when comparing binary values.

A match between a first binary value and a second binary value corresponds to a bit sequence comprising the first binary value being the same as a sequence comprising the second binary value.

The data type information associates each of the one or more data types with at least one of the field identifiers.

Obtaining the data type associated with the first identifier from the data type information includes obtaining the data type associated with the first field identifier.

Each data unit includes: a field identifier, a binary value in the record, and a data type identifier that uniquely identifies a data type.

The data type information associates each of the one or more data types with at least one of the data type identifiers.

Obtaining the data type associated with the first identifier from the data type information includes obtaining the data type associated with the first data type identifier.

Associating the obtained data type with at least one binary value included in an entry in the list includes instantiating a local variable having the obtained data type and initializing the instantiated variable to a value based on the binary value included in the entry.

Associating the obtained data type with at least one binary value included in an entry in the list includes setting a pointer associated with the obtained data type to point to a storage location where the binary value included in the entry is located.

Each data unit includes: a field identifier, a binary value in the record, and a length indicator of the binary value.

The length indicator is stored as a prefix of the binary value.

The method further includes receiving record format information associated with the plurality of records through the input device or a port of the computer system.

The data type information is generated based at least in part on the acquired record format information.

The processing further includes: for a first field in the obtained data type associated with the binary value, converting the binary values in different entries of the first list into a target data type; and for a second field in the obtained data type associated with the binary value, converting the binary values in different entries of the second list into the same target data type.

In another embodiment, generally speaking, software stored in a non-transitory form on a computer-readable medium includes instructions to trigger the following actions of a computer system: receiving a plurality of records through an input device or a port of the computer system, each of the records including one or more values corresponding to each of a plurality of fields; storing data type information in a storage medium of the computer system, the data type information associating each of the one or more data types with at least one identifier; and processing a plurality of data values from the records using at least one processor of the computer system. The processing includes: generating multiple data units based on the record, each of the data units including a field identifier and a binary value from one of the records, the field identifier uniquely marking one of the fields, and the binary value being extracted from the field of the record marked by the field identifier; collecting information about the binary values from the multiple data units; establishing a list of entries for each of one or more of the fields, at least some of the entries each including one of the binary values and information about the binary values collected from the multiple data units; obtaining a data type associated with a first identifier from the data type information, and associating the obtained data type with at least one binary value included in an entry in the list; and after collecting information about the binary values from the multiple data units, establishing profile information for at least one of the fields based at least in part on the obtained data type of a specific binary value appearing in the field.

In another aspect, generally, a computer system includes an input device or port of the computer system configured to receive a plurality of records, each of the records including one or more values corresponding to respective fields of a plurality of fields; a storage medium of the computer system configured to store data type information, the data type information associating each of the one or more data types with at least one identifier; and at least one processor of the computer system configured to process a plurality of data values from the records. The processing includes: generating multiple data units based on the record, each of the data units including a field identifier and a binary value from one of the records, the field identifier uniquely marking one of the fields, and the binary value being extracted from the field of the record marked by the field identifier; collecting information about the binary values from the multiple data units; establishing a list of entries for each of one or more of the fields, at least some of the entries each including one of the binary values and information about the binary values collected from the multiple data units; obtaining a data type associated with a first identifier from the data type information, and associating the obtained data type with at least one binary value included in an entry in the list; and after collecting information about the binary values from the multiple data units, establishing profile information for at least one of the fields based at least in part on the obtained data type of a specific binary value appearing in the field.

In another embodiment, a computer system generally includes: receiving means for receiving a plurality of records, each record including one or more values corresponding to respective fields of a plurality of fields; storing means for storing data type information, the data type information associating each of the one or more data types with at least one identifier; and processing means for processing the plurality of data values from the records. The processing includes: generating a plurality of data units from the records, each data unit including a field identifier and a binary value from one of the records, the field identifier uniquely identifying one of the fields, the binary value extracting the field of the record identified by the field identifier; collecting information about the binary values from the plurality of data units; establishing a list of entries for each of one or more of the fields, at least some of the entries each including a binary value and information about the binary values collected from the plurality of data units; retrieving a data type associated with a first identifier from the data type information and associating the retrieved data type with at least one binary value included in an entry in the list; and, after collecting information about the binary values from the plurality of data units, establishing profile information for at least one of the fields based at least in part on the retrieved data type of a particular binary value occurring in the field.

Each aspect may have one or more of the following advantages.

Data profiling is sometimes performed by a program that provides a user interface specifically designed for the purpose of managing the data profiling program. In this case, when analyzing large amounts of data (e.g., larger data sets and/or a large number of data sets), the user can expect to experience longer delays. In some scenarios, it is useful to incorporate the data profiling functionality into another user interface, such as a user interface used to develop a data processing program (e.g., presented as a data flow). However, if a user is developing a data processing program, even if a request for data profiling results for a specific data set from the development user interface is useful, it is still inappropriate to let the user experience a long delay before obtaining the results.

By using the techniques described herein, certain delays in certain data profiling procedures (e.g., particularly for field-level data profiling) can be reduced. For example, instead of having to wait three minutes for data profiling results, a user only has to wait 30 seconds. One of the techniques for producing at least some of these speed-ups is based on the recognition that processing for standardization and other type dependencies can be delayed and performed more efficiently after other data profiling steps that collect the data values to be standardized. The processing is more efficient because all distinct values are processed using one field, rather than having all distinct values present, which generally results in significantly fewer operations (unless the field is particularly large in number due to a particular value). The technique avoids redundant processing, which can take a significant amount of time for large sets of records. One consequence of this technique is the need to properly manage data type information that will later be used for standardization and type dependency validation, as described in more detail below.

Reduced processing delays make it feasible to perform data profiling within a development user interface. User interface elements (e.g., context menus) can be added to the development user interface and displayed when a user interacts with an icon representing a dataset or a link representing a data flow (e.g., using a right-click). The user interface elements can present the user with instructions for initiating one or more data profiling procedures to be executed on the associated dataset or data flow. After a relatively short delay, the results can be displayed in a window within the user interface. During the delay, a progress bar can be displayed to indicate to the user that the delay is relatively short. In one example scenario, if a user expects a particular field in a dataset to have only a fixed set of values, the data profiling results can be displayed to the user to indicate whether any unexpected values appear in the dataset. In another example scenario, the user can check to see if a field that is expected to be fully populated has blank or empty values. The user can then add "defensive logic" to the program to appropriately handle any observed unexpected situations. In another example scenario, the user may wish to view a summary of all data that flowed along a particular data flow during the most recent run of a dataflow diagram.

Other features and advantages of the invention will be apparent from the following description and from the claims.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a block diagram of a data processing system.

Figure 2 is a schematic diagram of the data analysis process.

FIG3 is a schematic diagram of extracting field-value pairs and data type information.

FIG4 is a flow chart of the data analysis process.

DETAILED DESCRIPTION

FIG1 illustrates an example of a data processing system 100 in which techniques for managing information of technical type to implement efficient data profiling can be applied. System 100 includes a data source 102, which may include one or more data sources, such as storage devices or connections to online data streams. Each data source may store or provide data in any of a variety of formats (e.g., database tables, spreadsheet files, plain text files, or a format native to a host computer). An execution environment includes a profiling module 106 and an execution module 112. Profiling module 106 executes a data profiling program on data source 102 or on intermediate data or output data generated by a data processing program executed by execution module 112. Storage device 112 providing data source 102 may be local to execution environment 104, e.g., stored on a storage medium (e.g., hard disk 108) connected to the computer hosting execution environment 104, or remote from execution environment 104, e.g., hosted on a remote system (e.g., host 110) that communicates with the computer hosting execution environment 104 via a remote connection (e.g., provided by a cloud computing infrastructure).

Execution environment 104 can be hosted, for example, on one or more general-purpose computers under the control of a suitable operating system, such as a version of the UNIX operating system. For example, execution environment 104 can include a multi-node parallel computing environment, including a computer system architecture using multiple central processing units (CPUs) or processor cores, where the architecture of the computer system can be local (e.g., a multi-processor system such as a symmetric multiprocessing (SMP) computer), locally distributed (e.g., multiple processors connected in a cluster or a massively parallel processing (MPP) system), remote, or remotely distributed (e.g., multiple processors connected via a local area network (LAN) and/or a wide area network (WAN)), or any combination thereof.

The profiling module 106 reads data from the data source 102 and stores profiling information 114 generated by a data profiling program executed by the profiling module 106. The profiling module 106 may run on the same host(s) as the execution module 112 in the execution environment 104, or may utilize additional resources, such as a dedicated data profiling server in communication with the execution environment 104. The profiling information 114 includes the results of the data profiling program and intermediate data compiled in the process of generating the results. The profiling information 114 may be stored back in the data source 102 or in a data storage system 116 accessible to the execution environment 104, or used in other ways.

The execution environment 104 also provides a development user interface 118 that enables developers 120 to both develop data processing programs and initiate data analysis programs. In some implementations, the development user interface 118 facilitates the development of data processing programs using a data flow graph that includes vertices (representing data processing elements or data sets) connected by directed links between the vertices (representing flows of work elements, i.e., data flows). For example, such a user interface is described in more detail in U.S. Patent Publication No. 2007/0011668, entitled "Managing Parameters for Graph-Based Applications," which is incorporated herein by reference. A system for performing such graph-based computations is described in U.S. Patent No. 5,966,072, entitled "Executing Computations Expressed as Graphs," which is incorporated herein by reference. A data flow graph created according to the present system provides methods for obtaining information flowing into and out of each process represented by the graph components, methods for transferring information between processes, and methods for defining the order in which processes are to be executed. The system includes algorithms for selecting an inter-process communication method from any available method (e.g., the communication path may use TCP/IP or UNIX domain sockets, or may use shared memory to transfer data between processes, depending on the links in the graph). In addition to the data analyzer launched from within the development user interface 118, the data analyzer may also be executed by a analyzer component in the data flow graph, which has an input port connected by a data flow link to an input data set and an output port connected by a data flow link to a downstream component configured to perform a task using the results of the data analysis.

The parsing module 106 can receive data from various types of systems that can embody the data source 102, including different types of database systems. The data can be organized into data sets that represent a collection of records with corresponding field (also called "attribute" or "column") values, including possible invalid values. When first reading data from a data source, the parsing module 106 typically starts with some initial formatting information about the records of the data source. In some cases, the record structure of the data source may not be known initially, but rather determined after analyzing the data source or the data. The initial information about the records may include, for example, the number of bits used to store a single value, the order of the fields in the record, and the data type (e.g., string, signed/unsigned integer) of the values appearing in a particular field.

Typically, the records of a particular data set all have the same record format, and all values within a particular field have the same data type (i.e., the record format is "static"). It is possible to have a "dynamic" record format, where each subset of records can have a different format, and/or one or more fields can have values of different data types. Some of the examples described herein assume a static record format, but various modifications can be made to support a dynamic record format. For example, processing can be reinitialized at the beginning of each subset of records in a data set that has a change in record format. Alternatively, subsets of records having the same record format can be treated as different virtual data sets having the static record format, and the results of those virtual record formats can be merged at a later time if necessary.

When performing data profiling, the profiling module 106 reads data from the data source 102 and stores profiling information 114, which can be used to perform various types of analysis to characterize different data sets and different fields within different data sets. In some implementations, the profiling information 114 includes a census of values that appear in a particular field (e.g., selected fields of a selected data set, or all fields of all data sets). The census lists all unique values in the field and determines the number of times each unique value appears. In some implementations, the census data is stored in a single data structure, optionally indexed by field, and in other embodiments, the census data is stored in multiple data structures, e.g., one data structure for each field.

The statistical survey data for a particular field being profiled can be organized as a list of entries, where each entry includes: an identifier for the field, the value that appears in the field, and a count of the number of times the value appears in the field in the dataset. For some datasets, the count is equivalent to the number of records in which the value appears in the field. For other datasets (e.g., a hierarchical dataset containing nested vectors as values for certain fields), the count may be different from the number of records. In some implementations, the statistical survey entry may also indicate whether the value is null. There is an entry for each unique value, so each value in an entry is different from the values in other entries, and the number of entries is equal to the number of unique values that appear in the field. The identifier of the field can be any value that uniquely identifies the field being profiled. For example, the profiled fields can be enumerated by assigning each field an integer index ranging from 1 to the number of the profiled fields. Such an index can be stored concisely in the statistical survey data structure. Even if the statistical survey data for different fields are stored in separate data structures, it is still useful to include the specific field identifier for the field in each entry of the data structure (e.g., to distinguish entries from different data structures). Alternatively, in some implementations, if statistical survey data for different fields is stored in separate data structures, the field only needs to be stored once in the data structure, with each entry implicitly associated with the segment and each entry including only the value and count.

FIG2 illustrates an example of a statistical survey-based data profiling process performed by the profiling module 106. The extraction module 200 executes an extraction process for generating a data stream 203 of extracted field-value pairs, such as table 201, from the profiled data set. In this embodiment, table 201 has three fields, named FIELD1, FIELD2, and FIELD3, and the first few data records (i.e., the first three rows) in table 201 show values corresponding to each of these three fields. The statistical survey generation module 202 processes the data stream 203 of field-value pairs to generate one or more statistical survey files 205 for each field. The type-dependent processing module 204 associates various data types from the retained data type information 208 with each field so that the type-dependent profiling results are included in the profiling information 114. The type-independent processing module 206 normalizes the typed data values recovered by the type-dependent processing module 204, thereby providing data values of predetermined types to facilitate additional processing independent of the initial data type. By delaying type-dependent processing and normalization until after the statistical survey is generated, potentially large speedups are realized because multiple instances of the same data value can be processed together (i.e., processing common data values at the same time) rather than separately.

The extraction module 200 generates the field-value pairs by decomposing a particular data record into a series of field-value pairs, each field-value pair comprising: a field index and a binary data value. A field index is an index value assigned to a particular field to uniquely (and effectively) identify the field (e.g., 1=FIELD1, 2=FIELD2, 3=FIELD3), and a binary data value is a typeless (or "raw") bit sequence that represents the corresponding data value contained in the data record for that field. In this example, the first data record in table 201 will generate the following field-value (i.e., field index, binary data value) pairs: (1, bin(A)), (2, bin(M)), (3, bin(X)) (wherein, for purposes of illustration, it should be understood that "bin(A)" in this example represents a binary data value (i.e., a bit sequence) representing the data value "A").

Statistical survey generation module 202 aggregates binary data values from field-value pairs in data stream 203 to produce statistical survey file 205. This aggregation, which is part of the statistical survey, only needs to be performed to have enough information to know whether a particular data value is the same as another data value. This matching can be performed using the original binary data values, so there is no need to waste valuable processing time providing data types to statistical survey generation module 202. (In Figure 2, the values shown in the entries of statistical survey file 205 correspond to the first three data records in table 201. This will be updated as field-value pairs from additional data records in table 201 are processed by statistical survey generation module 202.)

For a particular dataset, the field-value pairs can be inserted into data stream 203 in any order. In this embodiment, as a particular record appears in table 201, data stream 203 includes all the field-value pairs for that particular data record, followed by all the field-value pairs for the next data record. Alternatively, table 201 can be processed field by field, so that as a particular record appears in table 201, the data stream includes all the field-value pairs for that particular field, followed by all the field-value pairs for the next field. High-dimensional datasets can also be processed in this manner, so that field-value pairs are added to data stream 203 based on an order that is most efficient, for example, for reading the dataset or generating a statistical survey file from the resulting data stream 203. After all field-value pairs are generated, the data stream 203 of field-value pairs can be written to a file processed by the downstream statistical survey generation module 202, or the data stream 203 of field-value pairs can be provided to the downstream statistical survey generation module 202 simultaneously with its generation (e.g., to take advantage of the resulting pipeline parallelism).

The statistical survey generation module 202 processes the field-value pairs until the end of the data stream 203 is reached (for example, the end is indicated by a data stream tail record if the data stream corresponds to a finite batch of data records, or the end is indicated by a marker that defines a work unit if the data stream corresponds to a continuous stream of data records). Module 202 performs a data operation on the field-value pair, referred to as a "statistical survey match operation", to determine whether the binary data value in the field-value pair matches a previous binary data value from a previously processed field-value pair. Module 202 performs the statistical survey match operation at least once for each field-value pair in the data stream 203. Module 202 stores the results of the statistical survey match operation in a data structure that is stored in the working storage space of the storage device. If the statistical survey match operation finds a match to a previous data value, a stored count associated with the data value is incremented. Otherwise, if the statistical survey match operation does not find a match to a previous data value, a new entry is stored in the data structure.

For example, the data structure can be an associative array capable of storing key-value pairs with a unique key that is used to look up the associated value within the array. In this example, the key is a binary data value from a field-value pair, and the value is a count to be added to the total number of statistical survey data. When a key-value pair is created for a field-value pair with a specific binary value as its key (which does not match any key already in the associative array), the count starts at 1 and increases by 1 each time another field-value pair has a binary data value that matches the existing key. Module 202 searches different associative arrays for the binary data values of the field-value pairs corresponding to different fields (determined by the field index in each field-value pair), where one associative array is assigned to each field being analyzed. In some implementations, the number of fields being analyzed is known in advance, and an empty associative array (which uses only a minimum amount of storage space) is assigned to each field at the beginning of the analysis process.

An associative array can be implemented, for example, using a hash table or other data structure that provides efficient lookup of keys and modification of associated values. The binary data value used as the key of a key-value pair can store a copy of the binary data value itself or a pointer to a binary data value stored in a different location in the working memory (for example, stored in a backup of a field-value pair). The associative array, together with the stored backup of the binary data value from the field-value pair, or even the entire field-value pair itself, can be viewed as a data structure for storing statistical survey matching results. In embodiments where pointers to binary data values in field-value pairs are stored in the associative array, only the first field-value pair containing a particular key needs to be stored in the working memory, and subsequent field-value pairs containing the particular key can be deleted from the working memory after the statistical survey matching operation.

In the following examples, the associative array of the fields being profiled is referred to as a "poll array," and the key-value pairs are referred to as "poll entries" within the poll array. At the end of poll generation, the poll array generated by the poll generation module 202 will store all unique binary data values within table 201 that appear in each poll entry, as well as a total of the number of times that binary data value appears in the row of table 201, which represents the data record being profiled. Optionally, perhaps as part of type-dependent processing, the poll array can be updated to store not only the raw binary data values, but also the types associated with those binary data values, so that the poll entries store all different types of data values that appear in data table 201. For a static record format, in which all data values in a field have the same data type, data values that were different before being typed will remain different after being typed.

The type dependency processing module 204 causes a data parser to run to determine whether a particular data value is valid relative to its native data type. For example, if the native data type of a value appearing in a particular field is defined (in a record format) as having a data type of "date," then valid data values for that field may have a specific string format and value range that takes into account different parts of the string. For example, the string format may be specified as YYYY-MM-DD, where YYYY is any four-digit integer representing the year, MM is any two-digit integer representing the month between 1 and 12, and DD is any two-digit integer representing the day between 1 and 31. Additional restrictions on valid values of type "date" may further specify that certain months only allow for days between 1 and 30, for example. In another example, validating a data value in a field having a 'UTF-8' data type may include checking for the presence of bytes that are not permitted as valid UTF-8 characters for each UTF-8 character in the data value for a particular bit sequence. In another example, validating a data value in a field having a data type in a particular host format may include checking for specific characteristics defined by the host format. Type-dependent validation checks can also include the application of user-defined validation rules that depend on the original data type of a data value. If a data value is found to be invalid for its data type, the type-dependent processing module 204 can mark it as invalid, which can avoid additional processing of the data by the type-independent processing module 206. Before performing such validation checks, the type-dependent processing module 204 retrieves the data type from the retained data type information 208 and associates the retrieved data type with the corresponding binary value included for a given field in the statistical survey, as described in more detail below.

An example of a technique for extracting binary data values and separately saving data type information 208 for later use is shown in FIG3 . Table 201 is associated with a record format that describes the data types of the values appearing with the three fields of table 201. In this example, record format 300 is defined using a list of field declarations, as shown below:

T ₁ L ₁ FIELD1

T ₂ L ₂ FIELD2

T ₃ L ₃ FIELD3

The record format 300 includes a field declaration for each of the three fields of table 201: FIELD1, FIELD2, and FIELD3. For FIELD i, the field declaration includes an identifier Ti for the data type of the data value in the field, an identifier Li for the length of the data value in the field, and the field name. The data type and length identifiers (Ti and Li) are represented symbolically in this example (from i=1 to i=the number of fields), but actual record formats may use any of a variety of keywords, punctuation marks, and other syntactic elements to identify the data type and length.

Here is an example of how data types and length identifiers are specified using a particular type of syntax (i.e., Data Manipulation Language (DML) syntax), where there are field declarations delimited by the terms "record" and "end"; and each field declaration ends with a semicolon:

In this example, there are three different data types: a string data type identified by the keyword "string", an integer data type identified by the keyword "int", and a floating-point decimal data type identified by the keyword "decimal". This example also includes a length identifier (in bytes) in parentheses following the data type keyword.

Other types of record formats may also be used. For example, in some record formats, the length of a data value is not explicitly specified in the field declaration (e.g., for variable-length data values, or bounded data values). Some record formats have a potentially complex structure (e.g., hierarchical or nested), which can be used, for example, to specify conditional record formats or to specify record formats for a particular type of storage system (e.g., a COBOL copybook). Such complex structures can be parsed (or "walked"), and each field can be assigned a unique field identifier.

Extraction module 200 stores data type information 208, which includes sufficient information about the original data type of the field, as defined by record format 300, to enable type-dependent processing module 204 to recover the original data type for type-dependent processing. For example, data type identifiers _Ti and length identifiers _Li can be stored in an associative array that associates the data type identifiers and length identifiers with the corresponding field identifiers for the respective fields, as shown in FIG3 . Optionally, additional information can also be stored in data type information 208, such as the name of the field. The data type identifier _Ti can be stored in its original form or in a different form that retains sufficient information to recover the original data type. The generation of data type information 208 only needs to be performed once per dataset, avoiding potentially extensive work by the system to extract the data type along with the data value when generating field-value pairs for statistical survey generation. Even if the generation of data type information 208 is repeated multiple times (e.g., once by extraction module 204 and again by type-dependent processing module 204), the potentially extensive work can still be avoided by limiting the data type extraction to a constant number of times, rather than a number that approximates the number of records in the dataset.

If the data type information 208 is generated once by the extraction module 200, it can then be stored (or otherwise communicated) to the type dependency processing module 204 for retrieval. Conversely, if the data type information 208 is generated by the extraction module 200 and then generated separately by the type dependency processing module 204 (e.g., just before it is needed), the same data type information 208 will be obtained for both, as long as the process of assigning index values to the fields defined by the record format is the same. Whichever module generates the data type information 208, the same field index value 302 that is mapped to a particular field will be used, and the field index value 302 that is used by the extraction module 200 to insert the field index value into the field-value pair will be used.

The output of extraction module 200 is a stream of elements that optionally includes other information besides the pairs of field indexes and binary data values. Still referring to FIG3 , stream 203′ of optional field value pairs extracted from table 201 by extraction module 200 consists of elements that also include a record index and the length of each binary data value. An element 306 in stream 203′ includes a field index value of “2” (corresponding to FIELD2), a length value of len(M), a binary data value of bin(M), and a record index value of “1” (corresponding to the first record in table 201). The field index and binary data value are used to compile statistical survey entries, as described above. The record index can be used to compile location information, as described below. The length value len(M) can, for example, be 4 (e.g., encoded as a fixed-length integer), which represents a 4-byte length for the following binary data value bin(M). Data stream 203 in FIG2 that does not carry this length may be sufficient for fixed-length field data values. The length (L _i ) of this data value is specified in the record format and can be accessed by statistical survey generation module 202 when reading elements of stream 203. However, if the record format does not specify a fixed length, but allows data values to be of variable length, each element may include a length prefix, such as in stream 203'. For a blank data value, a length prefix of 0 may be used, followed by no corresponding binary data value.

Statistics generation is generally performed to enable "field-level" profiling, in which profiling information characterizes the values that appear in a field. In some implementations, for each unique data value, the statistics generation module 202 also adds location information to each statistics entry that identifies all records in the data set where the data value appears, which is useful for "record-level" profiling. In this example, the location information can be compiled and mapped to specific records in table 201 based on a record index value 304. For example, in the generation of a statistics entry for a particular data value in a particular field, a bit vector has a set of bit positions corresponding to the integer value of the record index for each record having the data value in the field. The bit vector can be compressed to reduce the storage space required. The record index value 304 can be generated, for example, by assigning a continuous sequence of integers to each record. The analysis program modules 204 and 206 or other data analysis programs can then use this location information to compile record-level data statistics and locate (or "drill down" to) records with specific attributes discovered by the data analysis (e.g., all records with a specific data value that is not expected to appear in a certain field). Compiling the location information may consume additional processing time, but it will not consume as much as compiling record-level statistics by directly processing each record before the statistical survey is generated.

The type dependency processing module 204 can employ various techniques to associate the original data type with the corresponding binary data value in the statistical survey array for type dependency processing and eventual canonicalization. In some embodiments, the data type of the binary data value from the statistical survey entry is retrieved by instantiating a local variable having the data type retrieved from the data type information 208 using the field index from the statistical survey entry. The local variable is initialized to a value corresponding to the binary data value included in the statistical survey entry (e.g., by parsing the binary data value according to the data type of the local variable). For example, the local variable can be a variable in the programming language that implements the dependency processing module 204 (e.g., a C or C++ variable). The instantiated and initialized local variable can then be used for processing performed by the type dependency processing module 204. Alternatively, in some embodiments, rather than instantiating a new local variable, a pointer associated with the retrieved data type can be set to point to the storage location where the binary data value is stored (e.g., in the statistical survey entry). Alternatively, a function reference that calls a processing module (e.g., a dedicated engine for interpreting DML code) may be used to perform the restoration of the original data type to generate a code line to reinterpret the binary data value as a typed data value. For example, the function reference may be represented as follows.

reinterpret_as(<data type identifier>,<binary data value>)

The function "reinterpret_as" calls the necessary processing to reinterpret the second "binary data value" parameter as a typed data value having a data type corresponding to the first "data type identifier" parameter.

As described above, some of the type-dependent processing performed may include a check to determine whether a data value is valid for its type. Before determining whether a data value is valid or invalid for its type, there may be a check to determine whether the data value is null or missing (indicating that the field is empty for at least one record). There may be a predetermined null value (or values, such as any number of "space" characters), which may be defined in the record format. Missing values may be indicated, for example, by a length prefix indicating a zero-length binary data value. In some cases, missing values may be treated differently, forming a null value. Which data value is considered a null value may depend on the data type.

Normalization can be performed at the beginning of type-independent processing (performed by module 206) or at the end of type-dependent processing (performed by module 204). Normalization can include, for example, converting all data values to data values having a target data type of "string". If a data value already has a (recovery) data type of "string", the normalization process may not perform any operations on the data value. In some implementations, the normalization process may still perform certain operations (e.g., removing leading or trailing "space" characters) even if the data value has the target data type. It is possible for normalization to map two different data values to the same normalized data value. For example, a data value of "3.14" having a data type of "string" (from the first field) may have a trailing "space" character removed to generate the "string" value "3.14", while a data value of "3.14" having a data type of "decimal" (from the second field) may be converted to the same "string" value "3.14". If two different data values from the same field (and therefore having the same original data type) are converted to the same normalized data value, then, in some embodiments, the type-independent processing module 206 may optionally update the appropriate statistics array to aggregate the statistics entries for those two data values so that the count for the new value is the sum of the individual counts of the old values.

FIG4 shows a flowchart 400 of an example of process data profiling using data type management techniques for delayed type dependency handling and standardization. The flowchart represents a possible algorithm for data profiling and is not meant to limit the order in which specific steps may be performed (e.g., to allow for various forms of parallelism). In an outer loop, the system 100 receives (402) a data set to be profiled and stores (404) corresponding data type information that associates a data type with a corresponding identifier for each profiled field. In an inner loop, the system 100 generates (406) data units (i.e., field-value pairs), each data unit comprising a field identifier that uniquely identifies a field and a binary value from a record. The binary value is extracted from the field of the record identified by the field identifier. The system 100 checks (408) to determine if there are any additional records to be processed as a condition for terminating the inner loop, and checks (410) to determine if there are any additional data sets to be processed as a condition for terminating the outer loop.

In potentially parallel operation with the inner and outer loops (e.g., using the pipeline parallelism of the modules in FIG. 2 ), the system 100 aggregates (412) information related to binary values from a set of data elements (e.g., data elements of a particular field based on a field identifier). In some implementations, this aggregation takes the form of a statistical survey procedure, and a list of entries in the statistical survey procedure is generated (414) for each field being profiled. Each statistical survey entry includes a particular binary value and information related to the binary values aggregated from the plurality of data elements (e.g., a total count). In a type-dependent processing phase, the system 100 retrieves (416) the data type associated with each field identifier from the data type information and associates each retrieved data type with a binary value included in an entry of an appropriate list (based on the field identifier). This enables the system 100, after aggregating information related to binary values from the plurality of data elements, to efficiently generate (418) profile information for one or more fields based, at least in part, on the retrieved data type for the particular binary value appearing in the field.

Along with delay type dependent processing and normalization up to statistics based aggregation, other techniques can be used in combination to further improve the efficiency of data profiling (reduce possible delays). For example, techniques can be used to effectively overflow a working storage space into an overflow storage space. In some embodiments, the program that performs the data profiling process, or a portion of the program (e.g., the statistics generation module 202), can be given a storage limit, that is, a maximum working storage space allowed to be used by the program is set within the storage device. The program can use the working storage space to store the statistics array (which may require most of the allowed working storage space), as well as to store other temporary values (which may require significantly less space than the statistics array). When module 202 determines that there may not be enough available working storage space to add additional entries to the statistics array, or when there is no longer any available working storage space to add additional entries (e.g., due to the addition of the last entry), an overflow condition for the working storage space is met. Module 202 may make this determination by measuring the total size of the statistical survey array (including any data values or field-value pairs referenced by pointers within the statistical survey array) and comparing that size to a memory limit (or other threshold), or by determining the amount of available working memory space remaining without directly measuring the total size of the statistical survey array (e.g., the range of storage addresses remaining from a block of memory address allocations).

In some implementations, the program sets an overflow threshold to detect when the total size of the statistical survey arrays is approaching the storage limit. The total size of the statistical survey arrays can be measured directly, for example, by calculating the sum of the sizes of the individual statistical survey arrays, where the size of an individual statistical survey array is measured as the number of bits of working memory space occupied by the statistical survey array. Alternatively, the total size of the statistical survey arrays can be measured indirectly, for example, by calculating the amount of free space remaining in the working memory space. In some implementations, the program sets the overflow threshold just below the memory limit to reserve some space for other values. In some implementations, the overflow threshold can be equal to the memory limit, for example, if the space required for other values is negligible and/or the profiling module 106 does not impose strict memory limits, thereby allowing small amounts of exceeding the storage limit for relatively short periods of time.

After the overflow condition has been triggered, the program uses an overflow handling process to store the necessary data to generate a complete statistical survey array in the overflow storage space within the storage device (e.g., data storage system 116). Exactly what is stored in the overflow storage space depends on the type of overflow handling program used. U.S. Patent Publication No. 2014/0344508, entitled "Managing Memory and Storage Space for a Data Operation," which is incorporated herein by reference, describes an example of an overflow handling program in which, after the overflow condition is triggered, the program continues to perform statistical survey matching operations on each processed field-value pair and stores information associated with the result of the data operation (i.e., an incremented count in the statistical survey entry, or a new statistical survey entry) in the same set of statistical survey arrays in the working memory, or in a new set of statistical survey arrays in the working memory. If the overflow condition is triggered at some point during the processing of the field-value pairs of the data stream 203, some data will be stored in the working storage space, while some data will be stored in the overflow storage space. In some cases, the data in these two locations is merged in some manner to produce a complete statistical survey array. Each statistical survey array is output in its own statistical survey file 205 by the type-dependent processing module 204 for processing. Because each binary data value can be extracted and stored in the statistical survey array without associated intermediate data indicating its data type, the storage size of the statistical survey data can be kept small, which also reduces the chance of overflow.

The above techniques can be implemented, for example, using a programmable computing system that executes appropriate software instructions, or on suitable hardware, such as a field programmable gate array (FPGA), or in some hybrid form. For example, in one programming approach, the software can include processes in one or more computer programs that are executed on one or more programmed or programmable computer systems (which can be of various architectures, such as distributed, client/server, or grid), each computer system including at least one processor, at least one data storage system (including volatile and/or non-volatile memory and/or storage elements), and at least one user interface (using at least one input device or port to receive input and at least one output device or port to provide output). The software can include one or more modules of a larger program, for example, providing services related to designing, configuring, and executing data flow graphs. The modules of the program (e.g., elements of a data flow graph) can be implemented as data structures or other organizational forms of data that conform to a data model stored in a data repository.

The software may be provided on a tangible, non-transitory medium, such as a CD-ROM or other computer-readable medium (e.g., readable by a general-purpose or special-purpose computing system or device), or a tangible, non-transitory medium delivered (e.g., in an encoded propagated signal) to a computer system executing the software via a network communication medium. Some or all of the processing may be performed on a dedicated computer or using dedicated hardware, such as a coprocessor or field programmable gate array (FPGA) or a dedicated application-specific integrated circuit (ASIC). The processing may be implemented in a distributed manner, where different computational portions specified by the software may be performed by different computing elements. Each such computer program is preferably stored on or downloaded to a computer-readable storage medium (e.g., solid-state memory or medium, or magnetic or optical medium) of a storage device accessible by a general-purpose or special-purpose programmable computer, for configuring and operating the computer to perform the processing described herein when the computer reads the storage device medium. The system of the present invention may also be considered to be implemented on a tangible, non-transitory medium configured with a computer program, wherein the medium so configured causes the computer to operate in a specific and predetermined manner to perform one or more processing steps described herein.

Several embodiments of the present invention have been described. However, it should be understood that the foregoing description is intended to illustrate and not to limit the scope of the present invention, which is determined by the scope of the following claims. Therefore, other embodiments are within the scope of the following claims. For example, various modifications may be made without departing from the scope of the present invention. Furthermore, some of the steps described above may be order-independent and, therefore, may be performed in an order different from that described.

Claims (23)

1. A method for processing data in a computer system, the method comprising: Multiple records are received through an input device or a port of the computer system, each record including one or more values corresponding to each of the multiple fields; The data type information is stored in the storage medium of the computer system, the data type information associating each of one or more data types with at least one identifier; and The computer system employs at least one processor to process multiple data values from the record, the processing comprising: Multiple data units are generated based on the records, each data unit including a field identifier that uniquely identifies one of the fields of the multiple records and the original binary value of the identified field from one of the multiple records; Information based on the original binary value is collected from multiple data units to build various lists of entries for one or more fields, wherein each list entry includes at least a portion of the list entries and information about the original binary value collected from multiple data units; The data type associated with the first identifier is obtained from the data type information, and the obtained data type is associated with at least one primitive binary value included in an entry in the list; and Generating profiling information includes: after collecting information based on the raw binary values from the plurality of data units, generating standardized data values converted from typed binary values in at least one list entry, based at least in part on the data types acquired and associated with specific raw binary values appearing in the list entries. 2. The method of claim 1, wherein the raw binary value extracted from a field of the record marked by the field identifier is extracted as an untyped bit sequence; the generation of a normalized data value from a typed binary value in at least one list entry based at least in part on a data type already associated with a particular raw binary value appearing in the list entry comprises: reinterpreting the untyped bit sequence as a typed data value having the acquired data type. 3. The method of claim 2, wherein the profiling information includes type-dependent profiling results that depend on the original data type of a plurality of data values of the record. 4. The method of claim 1, wherein collecting information based on the original binary values from the plurality of data units comprises comparing the original binary values from the plurality of data units with original binary values in the list of entries to determine whether there is a match between the original binary values. 5. The method of claim 4, wherein the information regarding the raw binary values collected from the plurality of said data units includes the total number of matching raw binary values, the total number being increased accordingly each time a match is determined when comparing raw binary values. 6. The method of claim 4, wherein a match between the first original binary value and the second original binary value corresponds to the same bit sequence including the first original binary value and the same bit sequence including the second original binary value. 7. The method of claim 1, wherein the data type information associates each of one or more data types with at least one of the field identifiers. 8. The method of claim 7, wherein obtaining the data type associated with the first identifier from the data type information includes obtaining the data type associated with the first field identifier. 9. The method of claim 1, wherein each data unit comprises: a field identifier, a raw binary value in the record, and a data type identifier that uniquely identifies a data type. 10. The method of claim 9, wherein the data type information associates each of one or more data types with at least one of the data type identifiers. 11. The method of claim 10, wherein obtaining the data type associated with the first identifier from the data type information includes obtaining the data type associated with the first data type identifier. 12. The method of claim 1, wherein associating the acquired data type with at least one primitive binary value included in an entry of the list comprises: instantiating a local variable having the acquired data type, and initializing the instantiated variable with a value based on the primitive binary value included in the entry. 13. The method of claim 1, wherein associating the acquired data type with at least one raw binary value included in an entry of the list comprises: setting a pointer associated with the acquired data type to a storage location where the raw binary value included in the entry is located. 14. The method of claim 1, wherein each data unit comprises: a field identifier, a raw binary value in the record, and a length indicator of the raw binary value. 15. The method of claim 14, wherein the length indicator is stored as a prefix of the original binary value. 16. The method of claim 1, further comprising: receiving record format information associated with the plurality of records via the input device or a port of the computer system. 17. The method of claim 16, wherein the data type information is generated at least in part based on the acquired record format information. 18. The method of claim 1, further comprising: for a first field in an acquired data type associated with the original binary value, converting the original binary values in different entries of a first list into a target data type; and for a second field in an acquired data type associated with the original binary value, converting the original binary values in different entries of a second list into the same target data type. 19. The method of claim 1, wherein generating a normalized data value from a typed binary value comprises: determining, at least in part, whether to perform one or more normalization operations on a particular typed binary value based on the data type acquired and associated with a particular original binary value appearing in the list entry. 20. The method of claim 19, wherein generating a normalized data value from a typed binary value comprises: at least in part based on the data type acquired and associated with a particular original binary value appearing in the list entry, without performing any normalization operation on at least one particular typed binary value. 21. Software stored in a non-transitory form on a computer-readable medium, the software including instructions to trigger a computer system to execute: Multiple records are received through an input device or a port of the computer system, each record including one or more values corresponding to each of the multiple fields; The data type information is stored in the storage medium of the computer system, the data type information associating each of one or more data types with at least one identifier; and The computer system employs at least one processor to process multiple data values from the record, the processing comprising: Multiple data units are generated based on the records, each data unit including a field identifier that uniquely identifies a field and the original binary value of the identified field from one of the multiple records; Information based on the original binary value is collected from multiple data units to build various lists of entries for one or more fields, wherein each list entry includes at least a portion of the list entries and information about the original binary value collected from multiple data units; The data type associated with the first identifier is obtained from the data type information, and the obtained data type is associated with at least one primitive binary value included in an entry in the list; and After collecting information based on the original binary values from the plurality of data units, at least in part based on the data type already associated with the specific original binary values appearing in the list entries, a standardized data value is generated from the typed binary values in at least one list entry. 22. A computer system, comprising: An input device or port of the computer system is configured to receive multiple records, each record including one or more values corresponding to each of the multiple fields; The computer system's storage medium is configured to store data type information, which associates each of one or more data types with at least one identifier; and At least one processor of the computer system is configured to process a plurality of data values from the record, the processing including: Multiple data units are generated based on the records, each data unit including a field identifier that uniquely identifies a field and the original binary value of the identified field from one of the multiple records; Information based on the original binary value is collected from multiple data units to build various lists of entries for one or more fields, wherein each list entry includes at least a portion of the list entries and information about the original binary value collected from multiple data units; The data type associated with the first identifier is obtained from the data type information, and the obtained data type is associated with at least one primitive binary value included in an entry in the list; and After collecting information based on the original binary values from the plurality of data units, at least in part based on the data type already associated with the specific original binary values appearing in the list entries, a standardized data value is generated from the typed binary values in at least one list entry. 23. A computer system, comprising: A receiving device for receiving a plurality of records, each of the records including one or more values corresponding to each of the plurality of fields; A storage device for storing data type information, wherein the data type information associates each of one or more data types with at least one identifier; A processing device for processing multiple data values from the record, the processing including: Multiple data units are generated based on the records, each data unit including a field identifier that uniquely identifies a field and the original binary value of the identified field from one of the multiple records; Information based on the original binary value is collected from multiple data units to build various lists of entries for one or more fields, wherein each list entry includes at least a portion of the list entries and information about the original binary value collected from multiple data units; The data type associated with the first identifier is obtained from the data type information, and the obtained data type is associated with at least one primitive binary value included in an entry in the list; and After collecting information based on the original binary values from the plurality of data units, at least in part based on the data type already associated with the specific original binary values appearing in the list entries, a standardized data value is generated from the typed binary values in at least one list entry.