HK1224050B - Managing memory and storage space for a data operation - Google Patents

Description

Manage memory and storage space for data operations

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims priority to U.S. Patent Application No. 61/824,686, filed May 17, 2013.

Technical Field

The present application relates to a memory and storage space for managing data operations.

Background Art

Some computing systems use a virtual memory scheme to manage the memory devices used by programs executed within the operating system. For example, using memory pages swapped in and out of a storage device, the operating system can handle the translation between the larger virtual address space and the smaller real address space of a memory device (also referred to as "main memory"), wherein the above-mentioned storage device is used as a backup storage with a larger storage capacity than the memory device. Therefore, the amount of working memory accessible to the program is not limited to the size of the main memory. In a virtual memory scheme, the round-trip movement of address pages in the working memory of the program between the memory device and the backup storage is usually transparent to the program using the working memory. Some computing systems may have hardware support for virtual memory, such as a memory management unit (MMU) built into a central processing unit (CPU). Some computing systems may also use a cache system with one or more levels to store a limited number of copies of main memory addresses in a relatively faster cache memory to speed up repeated access to memory addresses.

Summary of the Invention

In one embodiment, a computing system includes a memory device for providing working memory space, a storage device for providing overflow storage space, and at least one processor configured to process a plurality of data units to generate result information. The processing includes performing a data operation on each data unit of a first subset of data units of the plurality of data units and storing information associated with the result of the data operation in a first set of one or more data structures stored in the working memory space; after an overflow condition for the working memory space is satisfied, storing the information in the overflow storage space and freeing at least some of the working memory space, performing the data operation on each data unit of a second subset of data units of the plurality of data units and storing information associated with the result of the data operation in a second set of one or more data structures stored in the working memory space; and combining a plurality of sets of one or more data structures, including the first set and the second set, to generate the result information. Storing the information associated with the result of the data operation in the set of one or more data structures includes, for at least one data unit, performing an operation that changes the information in the set of one or more data structures without increasing the amount of working memory space used by the set of one or more data structures.

These aspects may include one or more of the following features.

The overflow condition of the working memory space is satisfied if the amount of the working memory space used by the first set of one or more data structures is greater than or equal to a predetermined threshold.

The processing also includes, after the overflow condition is met and before performing the data operation for each data unit of the second subset of data units, storing the first set of one or more data structures in the overflow storage space and removing the first set of one or more data structures from the working memory space.

Combining the multiple sets of one or more data structures includes merging at least one data structure of the first set with at least one data structure of the second set.

Merging at least one data structure of the first set with at least one data structure of the second set includes matching a first key in the data structure of the first set of one or more data structures with a second key in the data structure of the second set of one or more data structures, and performing an aggregation operation on a value associated with the first key and a value associated with the second key.

The processing also includes, after the overflow condition is met and before performing the data operation for each data unit of the second subset of data units, performing the data operation for each data unit of a third subset of data units of the plurality of data units, and storing information associated with a result of the data operation in the first set of one or more data structures stored in the working memory space.

The second subset of data units is a subset of the data units of the third subset of data units.

The processing also includes, after performing the data operation for the first data unit of the third subset of the data units, determining to store information associated with the result of the data operation in: (1) the first set of one or more data structures stored in the working memory space, or (2) the overflow storage space.

The operation to change information in the set of one or more data structures includes an in-place memory operation that overwrites a value stored in a location within the working memory space with a different value and stores it in the same location within the working memory space.

Storing information associated with a result of the data operation in the overflow storage space includes storing at least some contents of the first data unit in the overflow storage space.

Performing the data operation for the first data unit includes comparing a key in the first data unit with one or more keys in the first set of one or more data structures, and if the comparison result is a match, storing the information associated with the result of the data operation in the first set of one or more data structures stored in the working memory space, and if the comparison result is a mismatch, storing the information associated with the result of the data operation in the overflow storage space.

The processing also includes generating the plurality of data units based on a data source, each data unit including an identifier of a field of the data source and a value appearing in the field within a record of the data source.

The data operation includes aggregating information of a plurality of data units using the value included in the data unit as a key, the key being used to select a matching data unit whose information is aggregated.

The memory device includes a volatile memory device.

The storage device includes a non-volatile storage device.

In another embodiment, in general, a computing system includes: means for providing working memory space; means for providing overflow storage space; and means for processing a plurality of data units to generate result information. The processing includes: performing a data operation for each data unit of a first subset of data units of the plurality of data units and storing information associated with the results of the data operation in a first set of one or more data structures stored in the working memory space; after an overflow condition for the working memory space is satisfied, storing the information in the overflow storage space and freeing at least some of the working memory space, and performing the data operation for each data unit of a second subset of data units of the plurality of data units and storing information associated with the results of the data operation in a second set of one or more data structures stored in the working memory space; and combining a plurality of sets of one or more data structures, including the first set and the second set, to generate the result information. Storing the information associated with the results of the data operation in the set of one or more data structures includes, for at least one data unit, performing an operation that changes the information in the set of one or more data structures without increasing the amount of working memory space used by the set of one or more data structures.

In another embodiment, in general, a method for processing a plurality of data units to generate result information includes: performing a data operation for each data unit of a first subset of data units of the plurality of data units and storing information associated with the results of the data operation in a first set of one or more data structures stored in working memory space of a memory device; after an overflow condition of the working memory space is satisfied, storing the information in overflow storage space of the memory device and freeing at least some of the working memory space, performing the data operation for each data unit of a second subset of data units of the plurality of data units and storing information associated with the results of the data operation in a second set of one or more data structures stored in the working memory space; and combining a plurality of sets of one or more data structures, including the first set and the second set, to generate the result information. Storing the information associated with the results of the data operation in the set of one or more data structures includes, for at least one data unit, performing an operation that changes the information in the set of one or more data structures without increasing the amount of the working memory space used by the set of one or more data structures.

In another embodiment, generally, software is stored on a computer-readable medium for processing a plurality of data units to generate result information. The software includes instructions for causing a computing system to: perform a data operation on each data unit of a first subset of data units of the plurality of data units and store information associated with the result of the data operation in a first set of one or more data structures stored in working memory space of a memory device; after an overflow condition of the working memory space is satisfied, store the information in overflow storage space of the memory device and free up at least some of the working memory space; perform the data operation on each data unit of a second subset of data units of the plurality of data units and store information associated with the result of the data operation in a second set of one or more data structures stored in the working memory space; and combine a plurality of sets of one or more data structures, including the first set and the second set, to generate the result information. Storing the information associated with the result of the data operation in the set of one or more data structures includes, for at least one data unit, performing an operation that changes the information in the set of one or more data structures without increasing the amount of working memory space used by the set of one or more data structures.

In another embodiment, in general, a computing system includes: a memory device for providing a working memory space; a storage device for providing an overflow storage space; and at least one processor configured to process a plurality of data units to generate result information. The processing includes: performing a data operation for each data unit of a first subset of data units of the plurality of data units and storing information associated with the result of the data operation in a first set of one or more data structures stored in the working memory space; and after an overflow condition of the working memory space is satisfied, performing the data operation for each data unit of a second subset of data units of the plurality of data units and determining to store information associated with the result of the data operation in: (1) the first set of one or more data structures stored in the working memory space, or (2) the overflow storage space.

These aspects may include one or more of the following features.

The overflow condition of the working memory space is satisfied if the amount of the working memory space used by the first set of one or more data structures is greater than or equal to a predetermined threshold.

The data operation is based at least in part on a key value in each data unit, and the determining includes searching for at least one key value in at least one of the data structures in the first set to determine: (1) updating information associated with the key value in a data structure of the first set of one or more data structures in the working memory space, or (2) storing information associated with the key value in the overflow storage space.

The data operation includes an in-place memory operation that overwrites a value stored in a location within the working memory space with a different value and stores it at the same location within the working memory space.

Storing information associated with a result of the data operation in the overflow storage space includes storing at least some contents of a data unit on which the data operation was performed in the overflow storage space.

Performing the data operation for the first data unit includes comparing a key in the first data unit with one or more keys in the first set of one or more data structures, and if the comparison result is a match, storing the information associated with the result of the data operation in the first set of one or more data structures stored in the working memory space, and if the comparison result is a mismatch, storing the information associated with the result of the data operation in the overflow storage space.

The processing also includes generating the plurality of data units based on a data source, each data unit including an identifier of a field of the data source and a value appearing in the field within a record of the data source.

The data operation includes aggregating information of a plurality of data units using the value included in the data unit as a key, the key being used to select a matching data unit whose information is aggregated.

Generating the plurality of data units includes generating data units for at least a first field of the data source and at least a second field of the data source.

Performing the data operation for each data unit of the second subset includes storing information associated with a result of the data operation performed on the first data unit in the first set of one or more data structures, and storing information associated with a result of the data operation performed on the second data unit in the overflow storage space.

The first data unit and the second data unit respectively include identifiers for the same field of the data source.

The memory device includes a volatile memory device.

The storage device includes a non-volatile storage device.

In another embodiment, in general, a computing system includes: a device for providing a working memory space; a device for providing an overflow storage space; and a device for processing a plurality of data units to generate result information, the processing including: performing a data operation for each data unit of a first subset of data units of the plurality of data units and storing information associated with the result of the data operation in a first set of one or more data structures stored in the working memory space; and after an overflow condition of the working memory space is satisfied, performing the data operation for each data unit of a second subset of data units of the plurality of data units and determining to store information associated with the result of the data operation in: (1) the first set of one or more data structures stored in the working memory space, or (2) the overflow storage space.

In another embodiment, in general, a method for processing multiple data units to generate result information includes: performing a data operation for each data unit of a first subset of data units of the multiple data units and storing information associated with the result of the data operation in a first set of one or more data structures stored in a working memory space of a memory device; and after an overflow condition of the working memory space is met, performing the data operation for each data unit of a second subset of data units of the multiple data units, and determining whether to store the information associated with the result of the data operation in: (1) the first set of one or more data structures stored in the working memory space, or (2) the overflow storage space of the storage device.

In another embodiment, generally, software is stored on a computer-readable medium for processing a plurality of data units to generate result information. The software includes instructions for causing a computing system to: perform a data operation for each data unit of a first subset of data units of the plurality of data units and store information associated with the result of the data operation in a first set of one or more data structures stored in a working memory space of a storage device; and, after an overflow condition of the working memory space is satisfied, perform the data operation for each data unit of a second subset of data units of the plurality of data units and determine whether to store information associated with the result of the data operation in: (1) the first set of one or more data structures stored in the working memory space, or (2) an overflow storage space of the storage device.

In another embodiment, in general, a computing system includes a memory device for providing working memory space, a storage device for providing overflow storage space, and at least one processor configured to process a plurality of data units to generate result information. The processing includes performing a data operation for each data unit of a first subset of data units of the plurality of data units, the data operation comprising searching for a value in a data unit within at least one data structure of a first set of one or more data structures stored in the working memory space and, if the value is found, modifying information in the at least one data structure of the first set, and, if the value is not found, adding information to the at least one data structure of the first set; storing information in the overflow storage space and freeing at least some of the working memory space after an overflow condition of the working memory space is satisfied; performing a data operation for each data unit of a second subset of data units of the plurality of data units, the data operation comprising searching for a value in a data unit within at least one data structure of a second set of one or more data structures stored in the working memory space and, if the value is found, modifying information in the at least one data structure of the second set; and combining a plurality of sets of one or more data structures, including the first set and the second set, to generate the result information.

These aspects may include one or more of the following features.

The overflow condition of the working memory space is satisfied if the amount of the working memory space used by the first set of one or more data structures is greater than or equal to a predetermined threshold.

The processing also includes, after the overflow condition is met and before performing the search for each data unit of the second subset of data units, storing the first set of one or more data structures in the overflow storage space and removing the first set of one or more data structures from the working memory space.

Combining the multiple sets of one or more data structures includes merging at least one data structure of the first set with at least one data structure of the second set.

Merging at least one data structure of the first set with at least one data structure of the second set includes matching a first key in the data structure of the first set of one or more data structures with a second key in the data structure of the second set of one or more data structures, and performing an aggregation operation on a value associated with the first key and a value associated with the second key.

The processing also includes, after the overflow condition is met and before performing the search for each data unit of the second subset of data units, searching for a value in a data unit within at least one data structure of the first set of one or more data structures stored in the working memory space for each data unit of a third subset of data units of the plurality of data units, and if the value is found, modifying information in the at least one data structure of the first set.

The second subset of data units is a subset of the data units of the third subset of data units.

Modifying the information includes performing an in-place memory operation that overwrites a value stored at a location in the working memory space with a different value stored at the same location in the working memory space.

The processing also includes generating the plurality of data units based on a data source, each data unit including an identifier of a field of the data source and a value appearing in the field within a record of the data source.

The first set of one or more data structures includes a plurality of associative arrays of key-value paired entries.

Searching the data unit within at least one data structure of the first set of one or more data structures stored in the working memory space for the value includes searching for the value as a key of an entry within a selected one of the key-value pair entry associative arrays.

The selected one of the key-value pair entry associative arrays corresponds to the identifier in the data unit.

Modifying information in at least one data structure of the first set includes increasing the value of the found key-value pair entry.

Adding information to at least one data structure of the first set includes adding a new key-value pair entry to the selected array such that the key of the entry is the value in the data unit and the value of the entry is a count of one.

The memory device includes a volatile memory device.

The storage device includes a non-volatile storage device.

In another embodiment, in general, a computing system includes: means for providing working memory space; means for providing overflow storage space; and means for processing a plurality of data units to generate result information. The processing includes: performing a data operation for each data unit of a first subset of data units of the plurality of data units, the data operation comprising searching for a value in a data unit within at least one data structure of a first set of one or more data structures stored in the working memory space and, if the value is found, modifying information in the at least one data structure of the first set, and, if the value is not found, adding information to the at least one data structure of the first set; storing information in the overflow storage space and freeing at least some of the working memory space after an overflow condition of the working memory space is satisfied; performing a data operation for each data unit of a second subset of data units of the plurality of data units, the data operation comprising searching for a value in a data unit within at least one data structure of a second set of one or more data structures stored in the working memory space and, if the value is found, modifying information in the at least one data structure of the second set; and combining a plurality of sets of one or more data structures, including the first set and the second set, to generate the result information.

In another embodiment, in general, a method for processing multiple data units to generate result information includes: performing a data operation for each data unit of a first subset of data units of the multiple data units, the data operation including searching for a value in a data unit within at least one data structure of a first set of one or more data structures stored in a working memory space of a memory device, and if the value is found, modifying information in the at least one data structure of the first set, and if the value is not found, adding information to the at least one data structure of the first set; after an overflow condition of the working memory space is met, storing information in an overflow storage space of a storage device and releasing at least some of the working memory space, and performing a data operation for each data unit of a second subset of data units of the multiple data units, the data operation including searching for a value in a data unit within at least one data structure of a second set of one or more data structures stored in the working memory space, and if the value is found, modifying information in the at least one data structure of the second set, and combining multiple sets of one or more data structures, including the first set and the second set, to generate the result information.

In another embodiment, generally, software is stored on a computer-readable medium for processing a plurality of data units to generate result information. The software includes instructions for causing a computing system to: perform a data operation for each data unit of a first subset of data units of the plurality of data units, the data operation comprising searching for a value in a data unit within at least one data structure of a first set of one or more data structures stored in working memory space of a memory device, and if the value is found, modifying information in the at least one data structure of the first set, and if the value is not found, adding information to the at least one data structure of the first set; storing information in overflow storage space of the memory device and freeing at least some of the working memory space after an overflow condition of the working memory space is satisfied; performing a data operation for each data unit of a second subset of data units of the plurality of data units, the data operation comprising searching for a value in a data unit within at least one data structure of a second set of one or more data structures stored in the working memory space, and if the value is found, modifying information in the at least one data structure of the second set; and combining a plurality of sets of one or more data structures, including the first set and the second set, to generate the result information.

In another aspect, in general, a computing system includes: a memory device for providing a working memory space; a storage device for providing an overflow storage space; and at least one processor configured to process a plurality of data units to generate result information. The processing includes performing a data operation for each data unit of a first subset of the data units of the plurality of data units and storing information associated with the result of the data operation in a first set of one or more data structures stored in the working memory space; storing the information in the overflow storage space after an overflow condition of the working memory space is satisfied; and repeating a plurality of overflow processing steps during the processing of the plurality of data units, the overflow processing including updating a new set of one or more data structures stored in the working memory space using at least some of the information stored in the overflow storage space.

These aspects may include one or more of the following features.

The overflow condition of the working memory space is satisfied if the amount of the working memory space used by the first set of one or more data structures is greater than or equal to a predetermined threshold.

The processing also includes, after the overflow condition is met and before performing the data operation for each data unit of the second subset of data units, storing the first set of one or more data structures in the overflow storage space as a moved set, and removing the first set of one or more data structures from the working memory space.

Using at least some of the information stored in the overflow storage space to update a new set of one or more data structures stored in the working memory space includes merging information of at least one data structure of the moved set of one or more data structures stored in the overflow storage space with information of at least one data structure of the new set of one or more data structures stored in the working memory space.

The merging includes matching a first key in the data structure of the moved set of one or more data structures with a second key in the data structure of the new set of one or more data structures, and performing an aggregation operation on a value associated with the first key and a value associated with the second key.

Using at least some of the information stored in the overflow storage space to update a new set of one or more data structures stored in the working memory space includes matching a first key in a data unit stored in the overflow storage space with a second key in a data structure of the new set of one or more data structures, and increasing a value associated with the second key.

Using at least some of the information stored in the overflow storage space to update a new set of one or more data structures stored in the working memory space includes performing an in-place memory operation that overwrites a value stored at a location in the working memory space with a different value stored at the same location in the working memory space.

The processing also includes generating the plurality of data units based on a data source, each data unit including an identifier of a field of the data source and a value appearing in the field within a record of the data source.

The data operation includes aggregating information of a plurality of data units using the value included in the data unit as a key, the key being used to select a matching data unit whose information is aggregated.

The first set of one or more data structures includes a plurality of associative arrays of key-value paired entries.

The data operation of the first data unit includes using a value in the first data unit as a key to search within a selected one of an associative array of key-value pair entries.

The selected one of the key-value pair entry associative arrays corresponds to the identifier in the first data unit.

The memory device includes a volatile memory device.

The storage device includes a non-volatile storage device.

In another aspect, in general, a computing system includes: means for providing a working memory space; means for providing an overflow storage space; and means for processing a plurality of data units to generate result information. The processing includes performing a data operation for each data unit of a first subset of the data units of the plurality of data units and storing information associated with the result of the data operation in a first set of one or more data structures stored in the working memory space; storing the information in the overflow storage space after an overflow condition of the working memory space is satisfied; and repeating a plurality of overflow processing steps during the processing of the plurality of data units, the overflow processing including updating a new set of one or more data structures stored in the working memory space using at least some of the information stored in the overflow storage space.

In another embodiment, in general, a method for processing multiple data units to generate result information includes: performing a data operation for each data unit of a first subset of data units of the multiple data units, and storing information associated with the result of the data operation in a first set of one or more data structures stored in a working memory space of a memory device; storing the information in an overflow storage space of a storage device after an overflow condition of the working memory space is met; and repeating an overflow processing process multiple times during the processing of the multiple data units, the overflow processing process including: using at least some of the information stored in the overflow storage space to update a new set of one or more data structures stored in the working memory space.

In another embodiment, generally, software is stored on a computer-readable medium for processing a plurality of data units to generate result information. The software includes instructions for causing a computing system to: perform a data operation for each data unit of a first subset of the plurality of data units, and store information associated with the result of the data operation in a first set of one or more data structures stored in a working memory space of a memory device; store the information in an overflow storage space of the memory device after an overflow condition of the working memory space is satisfied; and repeat a plurality of overflow handling procedures during the processing of the plurality of data units, the overflow handling procedure including updating a new set of one or more data structures stored in the working memory space using at least some of the information stored in the overflow storage space.

These aspects may include one or more of the following advantages.

Some computing systems (e.g., some database management systems) do not rely solely on virtual memory to manage working memory, but rather are able to directly control whether the data being processed is stored in the main memory of a storage device or in overflow storage space. For example, some systems impose explicit limits on the amount of working memory available to a program, whereby the working memory limit is smaller than the main memory size (e.g., because the program can share working memory with other programs). If a program approaches its working memory limit, the program has the option of using a "spill to disk" technique to temporarily store some data in overflow storage space, and later terminate processing of the data after sufficient working memory is available. In some cases, spilling data to disk, or relying on the operating system to swap memory pages, can significantly impact the performance of data operations.

For some applications of a data processing system, such as data profiling, which is described in more detail below, if data operations are to be performed on potentially large amounts of data (e.g., large data sets and/or a large number of data sets), the system should be configured to manage working memory and overflow storage in an efficient manner to ensure that the data processing application can provide adequate performance. One approach to managing working memory and overflow storage is based on the recognition that for some data operations, instead of overflowing input data to disk without processing the data, the system can perform the data operation at least partially on the input data, and in some cases, without overflowing the input data to disk.

For example, some data operations process a stream of input records associated with each key value, and for records whose key values match the previous key values, the data operations update the results stored in the data structure of the memory. In some implementations, an "overflow handling" process is used so that the computing system described herein can keep processing new records with any key used even after the working memory limit has been reached. Two specific examples of overflow handling processes are described. The two processes enable some records to be matched and used to update the result data structure without overflowing those records. For matching records, the result data structure can be updated in place without using more memory. One overflow handling process handles overflow by simply moving the result data structure to overflow storage and continuing to process all new records (in a new result data structure to be merged with the moved result data structure), and the other overflow handling process handles overflow by simply moving unmatched records to overflow storage and continuing to process all new records (in the same result data structure).

An example of a data operation that can be performed using the techniques described herein is a census operation, which is used to generate a census of data values (including the values that appear in the data set and the count of each value) within a large data set for the purpose of profiling the data set. Data profiling operations can include any operation performed on data (processed in the process of performing data profiling), such as a census operation. Census operations can also be performed on data processed in other environments (such as in a data quality system that tracks data characteristics over time). Other data operations to which the technology can be applied include data operations that allow for the merging of incomplete results, and data operations that can handle at least some situations in situ within a data structure in memory, as described in more detail below. The technology can be used to process data units such as the standardized records described herein, or any other data units that represent separate data portions within a data stream.

Other features and advantages of the invention will become 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.

Figures 3 and 5 are schematic diagrams of the census generation process.

4A-4C and 6 are flow charts of the census generation process.

Specific implementation method

FIG1 illustrates an example of a data processing system 100 in which techniques for managing working memory and overflow storage space may be used. Data processing system 100 includes a data source 102, which may include one or more sources of data, such as storage devices or connections to online data streams. Each such source may store or provide data in any of a variety of formats (e.g., database tables, spreadsheet files, flat text files, or a native format used by a host computer). Data processing system 100 includes a computing system 104, which includes at least one processor 106, at least one memory device 108 (e.g., volatile memory, such as dynamic random access memory) coupled to processor 106, and at least one storage device 110 (e.g., non-volatile storage, such as a magnetic hard drive) coupled to processor 106. After computing system 100 processes data from data source 102, the results of the processing may be provided in a user interface (UI) 112, including automatically providing a user with visual indications of conditions prevalent in data source 102 or conditions that will be prevalent in a destination that is to receive and process data from data source 102.

A variety of configurations of the different components of data processing system 100 are possible. Processor 106 can be configured to host an execution environment controlled, for example, by a suitable operating system (such as a version of the UNIX operating system). In some implementations, computing system 104 can be part of a multi-node parallel computing environment, including a configuration of multiple central processing units (CPUs) or processor cores, which can be local (e.g., a multiprocessor system such as a symmetric multi-processing (SMP) computer), locally distributed (e.g., multiple processors coupled as a cluster or massively parallel processing (MPP) system), remote or remotely distributed (e.g., multiple processors coupled via a local area network (LAN) and/or a wide area network (WAN)), or any combination thereof. The storage device providing data source 102 may be a storage device local to computing system 104, for example, stored on a storage medium connected to computing system 104 (including storage device 110); or it may be a storage device remote from computing system 104, for example, hosted on a remote system (e.g., a host) that communicates with computing system 104 via a remote connection (e.g., provided by a cloud computing infrastructure).

In some implementations, the computing system 104 is configured to execute an application as a dataflow graph, which includes nodes (representing processing components or data sets) connected by direct links between the nodes (representing flows of work elements, i.e., data). For example, such an environment is described in more detail in U.S. Publication No. 2007/0011668, entitled "Managing Parameters for Graph-Based Applications," which is incorporated herein by reference. A system for executing 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. Dataflow graphs created according to this system provide methods for bringing information into and out of various processes represented by graph components, for moving information between processes, and for defining the order in which processes are run. This system includes algorithms that select an inter-process communication method from any available methods (for example, the communication path view table links can use TCP/IP or UNIX domain sockets, or use shared memory to pass data between processes).

The computing system 104 can receive data from various types of systems that can implement the data source 102, including different forms of database systems. The data can be organized into data sets representing a number of records, with values for various fields (also called "attributes" or "columns"), which may include null values. When first reading data from a data source, the computing system 104 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 initially known, but instead may be determined after analyzing the data source or the data. The initial information about the record may include, for example, the number of bits representing a unique value, the order of the fields within the record, and the type of value represented by the bits (e.g., string, signed/unsigned integer).

An example of a type of processing that the data processing system 100 can perform on data within the data source 102 is data profiling. Stored data sets may include data whose various characteristics are unknown in advance. For example, the range of values or typical values of the data set, the relationship between different fields in the data set, or the functional dependencies between values in different fields may be unknown. Data profiling can involve examining many potentially related data sets to determine such characteristics. The computing system 104 can also perform various tasks, such as cleaning the data in the data source 102 or managing metadata for the data sets stored in the data source 102. In an implementation in which the computing system 104 is configured to execute an application as a dataflow graph, data profiling can be performed, for example, by a profiler component node in the dataflow graph, the profiler component node having an input port connected by a dataflow link to the input data set and an output port connected by a dataflow link to a downstream component (which is configured to use the results of the data profiling to perform a task).

When performing data profiling, the computing system 104 reads data from the data source 102 and stores profile information that 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 profile information 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 within the field and quantifies the number of times each unique value appears. In some implementations, the census data is stored in a single data structure that is optionally indexed by field, while in other implementations, the census data is stored in multiple data structures, for example, one data structure for each field.

Census data for a particular field being profiled can be organized as a list of entries, each entry consisting of: a field identifier, a value that occurs within the field, and a count of the number of records in which that value occurs within the field. Each unique value has one entry, so each value in an entry is distinct from the values in other entries, and the number of entries is equal to the number of unique values that occur within the field. A field identifier can be any value that uniquely identifies the profiled field. For example, the profiled fields can be enumerated by assigning each field an integer index ranging from 1 to the number of profiled fields. This index can be compactly stored within the census data structure. Even if census data for different fields is stored in separate data structures, it may still be useful to include a specific field identifier for that field in each entry in the data structure (e.g., to distinguish entries from different data structures flowing into the processing module). Alternatively, in some implementations, if census data for different fields is stored in separate data structures, the fields need only be stored once by the data structure, and each entry is implicitly associated with the field and includes only the value and count.

FIG2 illustrates an example of a census-based data profiling process performed by a program running on computing system 104, including a standardization module 200 for generating a stream 208 of standardized records; a census generation module 202 for processing stream 208 of standardized records into a census file 210; and a census processing module 204 for analyzing census file 210 to compute profiling results. Standardization module 200 reads one or more data sets to be profiled, such as table 206. Table 206 has three fields, designated Field 1, Field 2, and Field 3, and the first few data records (the first three rows) in table 206 show the values for each of the three fields. Standardization module 200 generates standardized records by splitting a particular data record into a series of standardized records, each including a field index and a data value. A field index is an index value assigned to a particular field to uniquely (and efficiently) identify that field (e.g., 1 = Field 1, 2 = Field 2, 3 = Field 3), and a data value is the corresponding value contained in the data record for that field. In this example, the first data record in table 206 will generate the following (field index, data value) pairs within the three standardized records: (1, A), (2, M), and (3, X), respectively. Census generation module 202 aggregates the data values of the standardized records in stream 208 to produce census file 210. (In FIG. 2 , the values shown in the entries of census file 210 correspond to the first three data records in table 206, which are updated as standardized records from additional data records in table 206 are processed by census generation module 202.)

For a particular data set, normalized records can be inserted into stream 208 in any order. In this example, as a data record appears in table 206, stream 208 includes all normalized records for the particular data record, followed by all normalized records for the next data record. Alternatively, table 206 can be processed by fields such that, as a data record appears in table 206, the stream includes all normalized records for a particular field, followed by all normalized records for the next field. Higher-dimensional data sets can also be normalized in this manner, for example, by adding normalized records to the output stream in the order that is most efficient for reading the data set or generating a census file based on the generated stream. After all normalized records are generated, stream 208 of normalized records can be written to a file to be processed by downstream census generation module 202, or, as the stream 208 of normalized records is generated, it can be provided to downstream census generation module 202 (e.g., to exploit generated pipeline parallelism).

Census generation module 202 processes standardized records until it reaches the end of stream 208 (e.g., as indicated by an end stream record). Module 202 performs a type of census operation (referred to as a "census match operation") on the standardized records to determine whether a data value in the standardized record matches a previous data value in a previously processed standardized record. Module 202 performs at least one census match operation for each standardized record in stream 208. Module 202 stores information associated with the results of the census match operation in at least one data structure, which is stored in working memory space of memory device 108. The working memory space used by the data structure includes memory for any overhead of the data structure and memory for all information in the data structure, including any memory for data referenced by pointers. If a census match operation finds a match with a previous data value, the stored count associated with the data value is incremented. Otherwise, if the census match operation does not find a match with 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, each with a unique key used to look up an associated value within the array. In this example, the key is a data value from a standardized record, and the value is a count that will be added to the total count of the census data. When a key-value pair is created for a standardized record with a particular data value, since its key does not match any key existing in the associative array, the count starts at 1, and each time another standardized record has a data value that matches the existing key, the count is increased by 1. Module 202 looks up the data value of the standardized record for different fields within different associative arrays (determined by the field index within each standardized record), allocating one associative array for each field being parsed. In some implementations, the number of fields to be parsed is known in advance, and at the beginning of the parsing process, an empty associative array (which uses only a minimum amount of storage space) is allocated for each field.

For example, an associative array can be implemented using a hash table or other data structure that provides efficient key lookup and associated value modification. The data value used as the key of a key-value pair can store a copy of the data value itself or a pointer to a data value stored at a different location in the working memory (for example, stored in a copy of the standardized record). The associative array, together with the stored copies of the data values of the standardized record, or even the entire standardized record itself, can be viewed as a data structure for storing census matching results. In an implementation in which pointers to the data values in the standardized record are stored in the associative array, only the first standardized record containing a particular key needs to be stored in the working memory, and subsequent standardized records containing the particular key can be removed from the working memory after the census matching operation.

In the following examples, these associative arrays of profiled fields are referred to as "census arrays" and the key-value pairs are referred to as "census entries" within the census arrays. At the end of the data profiling process, the census arrays generated by the census generation module 202 will store all unique data values that appear in the table 206 within individual census entries, as well as a total count of the number of times that data value appears within the row of the table 206 that represents the data record being profiled.

A program or portion of a program that performs a data profiling process (e.g., census generation module 202) can be assigned a memory limit that sets a maximum amount of working memory space within the memory device 108 that the program is allowed to use. The program can use the working memory space for storing the census array, which may require a large portion of the allowed working memory space, and for storing other temporary values, which may require significantly less space than the census array. A working memory overflow condition is met when module 202 determines that insufficient working memory space may be available to add additional entries to the census array, or when there is no longer any working memory space available to add additional entries (e.g., due to the last entry being added). Module 202 can make this determination by measuring the memory size of the census array. The memory size represents the amount of working memory space used by the census array, including the total amount of memory occupied by the data structures representing the census array and any system overhead used by all information in these data structures (including any data values or normalized records referenced by pointers within the census array). Module 202 then compares this memory size to the memory limit (or other threshold).

In some implementations, the program sets an overflow threshold to detect when the memory size of the census array approaches the memory limit. For example, the memory size of the census array can be measured directly by summing the sizes of the individual census arrays, where the size of an individual census array is measured as the number of bits in the working memory space occupied by the census array. Alternatively, the memory size of the census array can be measured indirectly, for example, by calculating the amount of free space left in the working memory without directly measuring the memory size of the census array (e.g., the range of memory addresses left over from an allocated block of memory addresses). 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, to allow for a relatively short period of time when the memory limit is slightly exceeded if the space required for other values is negligible and/or if computing system 104 does not impose strict memory limits.

After an overflow condition is triggered, the program uses an overflow handling process to store some of the data needed to generate a complete census array in overflow storage space within storage device 110. The type of data stored in the overflow storage space depends entirely on the type of overflow handling process used. In the example overflow handling process described below, the program continues to perform a census matching operation for each standardized record processed after the overflow condition is triggered, and stores information associated with the results of the census matching operation (i.e., incremented counts in census entries, or new census entries) in the same set of census arrays in working memory or in a new set of census arrays in working memory, as described in detail below. If an overflow condition is triggered at some point during the normalization of a record in processing flow 208, some data will be stored in working memory space and some data will be stored in overflow storage space. In the example overflow handling process described below, the data in the two locations is combined in some manner to generate a complete census array. Each census array is output in its own census file 210 for processing by census handling module 204. Furthermore, the combining process used depends entirely on the type of overflow handling process used. A census file 210 may optionally be output from the census generation module 202 at a stage when the census array or set of census array entries is complete to be sent to an output port.

The two examples of overflow handling procedures described below can be used by the same survey generation module 202. In one mode, one procedure can be used, and in another mode, the other procedure can be used. The mode can be determined by the user, for example, through some initial analysis (e.g., an initial analysis performed on a subset of the profiled data set, or an initial analysis performed on historical profile information of the same or similar data set) to estimate which procedure will be most effective. These overflow handling procedures can be applied to other data operations in addition to survey matching operations. Data operations that allow for the merging of incomplete results will be compatible with combining results stored in the working memory space with results stored in the overflow storage space, as performed in the overflow handling procedures described below. Data operations that can be processed in-place in at least some cases will be compatible with in-place updates of data structures within the in-memory data structures, as performed in the overflow handling procedures described below. The efficiency of the overflow handling procedures is particularly useful for data operations (such as survey operations or other data profiling operations used to process potentially large amounts of input data) by avoiding the time spent storing some data in the overflow storage space before allowing the user to observe the results of the process or perform additional interactions dependent on the process.

FIG3 illustrates census generation with a first overflow handling process used in the context of census generation module 202 generating a census array. FIG4A-4C corresponds to a flow chart of census generation with a first overflow handling process. Referring to FIG3 and FIG4A, census generation module 202 receives a stream 300 of standardized records and, for each field parsed, generates a complete census array 302 at the end of the overflow handling process. As module 202 loops through each standardized record in stream 300 (starting with the first standardized record of the first iteration), module 202 reads 400 the next standardized record. Module 202 checks 402 the memory size of census array 304 generated in working memory space 306 to determine if an overflow threshold has been reached.

If the overflow threshold is not reached, the module 202 performs a census matching operation 404 on the normalized record. The census matching operation 404 includes searching (406) a key of an appropriate census array 304 (the census array for the field index in the normalized record) to match the data value in the normalized record. If there is a match for the key (which is the data value from the previous normalized record), the count corresponding to the key is incremented (408). If there is no match for the key, a new entry is added (409) to the appropriate census array 304, where the key is set to the data value and the count is set to 1.

If the overflow threshold has been reached, the module 202 performs a merge operation 412 on the census array 304 and the previous partial census array 308 (in the previous iteration) stored in the overflow storage space 310. The result of the merge operation 412 (described in more detail below) is a new set of partial census arrays 308, each containing entries corresponding to the union of the keys (i.e., data values) in the merged census arrays for a given field along with the sum of the counts for each key. Thus, the information in the partial census array 304 in the working memory space 306 is safely stored in the overflow storage space 310, and the partial census array 304 can now be removed from the working memory space 306 (414), freeing up more working memory space 306 to perform the census matching operation 404 on the next standardized record.

At the end of the iteration, module 202 determines (416) whether the end of stream 300 has been reached (which ends the loop iteration for each record in the stream). If the end has not been reached, another iteration begins by reading (400) the next normalized record. If the end has been reached, module 202 determines (418) whether an overflow has occurred during any iteration. If no overflow has occurred, module 202 sends (419) each complete census array 304 in working memory space 306 at that time to the output port. If an overflow has occurred, module 202 performs a modified version of a merge operation 412' on the partial census arrays 304 stored in working memory space 306 and the partial census arrays 308 stored in overflow storage space 310 to send the resulting merged census array to the output port. The merge operation 412 is described in more detail with reference to FIG. 4B and the merge operation 412' is described in more detail with reference to FIG. 4C.

4B , an example of a merge operation 412 is shown for merging a set of partial census arrays in the working memory space 306 (referred to as the "memory array") with a set of partial census arrays in the overflow storage space 310 (referred to as the "stored array"). The merge operation 412 includes an outer loop that iterates over the fields (i.e., using a loop counter that references the "current field" and runs from 1 to the number of fields), and an inner loop that iterates over the entries in the stored array for the fields of the current field iteration (i.e., using a loop counter that references the "current entry" and runs from 1 to the number of entries). The inner loop begins by searching (420) the stored array within the memory array for the data value of the current entry for the field of the current field iteration. If a match is found, the inner loop sums (422) the count of the current entry in the memory array and the count of the matching entry in the memory array, and stores the resulting total count in the matching entry in the memory array (overwriting the previous count). Because this new total count does not require any additional space in working memory, this operation will not cause an increase in the amount of working memory space used. In various implementations, either the memory array or the stored array can be searched and used to accumulate the total count, but by iterating over the stored array and searching the memory array, the search can be performed more efficiently (because memory device 108 can be accessed more efficiently than storage device 110). If no match is found, the inner loop adds (424) the current entry in the memory array to a new census array in overflow storage space 310 (which is part of the new census array set that will replace the previous stored array after the merge operation 412) and begins a new inner loop iteration by searching (420) the stored array within the memory array for the data value of the next entry. After reaching the last entry in the stored array, the inner loop ends (426). The outer loop includes appending (428) the updated memory array to the new census array so that the entire set of new census arrays will represent matching entries and non-matching entries for the merge operation 412. After reaching the last field, the outer loop ends (430).

FIG4C shows an example of a modified version of the merge operation 412′ that is performed to merge the last set of memory arrays with the stored array. In this example, the only difference is as follows. Instead of adding (424) the current entry in the stored array to a new census array in the overflow storage space 310, operation 412′ outputs (424′) the current entry in the stored array to the output port of module 202 (e.g., by writing to an output census file, which may also be stored in the overflow storage space 310). Instead of appending (428) the updated memory array to the stored array, operation 412′ sends (428′) the updated memory array to the output port of module 202 (e.g., by writing to an output census file, which may also be stored in the overflow storage space 310).

In short, the first overflow handling process handles overflow conditions of the working memory by moving the partial census array to overflow storage and continuing to process all new records (the new partial census array in the working memory will be merged with the partial census array moved to overflow storage). The first overflow handling process effectively manages overflows of the partial census array to overflow storage. The second overflow handling process will similarly handle overflow conditions while continuing to process all new records, but the second overflow handling process will be configured to effectively manage overflows of unmatched records rather than partial census arrays to overflow storage.

FIG5 illustrates census generation with a second overflow handling process used in the context of census generation module 202 generating a census array. FIG6 corresponds to a flow chart for census generation with a second overflow handling process. Referring to FIG5 and FIG6, census generation module 202 receives a stream 500 of standardized records and, for each field parsed, generates a complete census array 502 at the end of the overflow handling process. As module 202 iterates through each standardized record in stream 500 in a first pass, or as module 202 iterates through each set of standardized records (which are temporarily stored in temporary record storage 503 in overflow storage space 504) in one or more additional passes, module 202 reads (600) the next standardized record. The steps performed in one or more passes are described in more detail below, but essentially, each pass involves filling working memory space 306 until a threshold condition is met, and, after the threshold condition is met, processing all matching records in place and overflowing all non-matching records. Module 202 performs a census matching operation 602 on the standardized record.

The census matching operation 602 includes searching (604) a key of an appropriate census array 506 (the census array for the field index in the normalized record) generated in the working memory space 508 to match (605) the data value in the normalized record. If there is a match for the key (which is a data value from a previous normalized record), the count corresponding to the key is incremented (606). This increment (606) can occur without using more working memory space 508 (e.g., using an in-place operation to increment the count of the matching entry) and is therefore not dependent on whether an overflow threshold has been reached. If there is no match for the key, the next action depends on the result of checking (607) the memory size of the census array 506 to determine whether the overflow threshold has been reached. If the overflow threshold has not been reached, a new entry is added (608) to the appropriate census array 506 with the key set to the data value and the count set to 1. If the overflow threshold has been reached, the module 202 stores (609) the normalized record in a new temporary record storage 503 in the overflow storage space 504. Temporary record storage 503 can be a single file (or other data structure) storing standardized records, or can be multiple files (or other data structures) providing field index (or other features) to access standardized records. There are different temporary record stores 503, which have different sets of standardized records for different channels.

Module 202 determines (610) whether the end of the first pass of stream 500 has been reached (which ends the loop iteration for each record in the stream), or whether the end of the pass for a temporary record storage 503 has been reached. If the end of the pass has not been reached, another iteration begins by reading (600) the next normalized record. If the end of the pass has been reached, module 202 determines (611) whether an overflow has occurred in any previous iteration of the current pass. If no overflow has occurred, module 202 sends (613) each complete census array 506 in the working memory space 508 at this time to the output port. If an overflow has occurred, module 202 checks (612) to determine whether any temporary record storage 503 remains.

If at least one temporary record store 503 remains, the module 202 begins freeing space in the working memory to process the normalized record in that store 503 by iterating over the fields (i.e., using a loop counter from 1 to the number of fields that references the "current field") and appending (614) an appropriate partial census array 506 to the corresponding one (having the same field index) of any partial census array 510 stored in the overflow storage space 504 (in the previous iteration). After the last field has been reached, the loop ends (615). Thus, the information in the partial census array 506 in the working memory space 508 is safely stored in the overflow storage space 504, and the partial census array 506 can be removed (616) from the working memory space 508, freeing up more working memory space 508 to read (600) the next normalized record from the remaining temporary record store 503 and perform the census matching operation 602 on the normalized record.

Because any normalized records with data values that will match keys in the census arrays 510 will be processed when these census arrays 510 are generated in the working memory space 508, the partial census arrays 506 and partial census arrays 510 can be simply appended without performing a merge operation, and therefore none of these data values are present in any current census array 506 in the working memory space 508. The entries in the partial census arrays 506 and partial census arrays 510 can optionally be sorted or rearranged into one or more other data structures if helpful (e.g., for efficiency in accessing the entries), but the individual entries need not be joined to consolidate information about a particular data value.

In an example of how module 202 processes records through stream 500, after a first subset 512 of the normalized records of stream 500 has been processed, causing the memory size of census array 506 to expand to an overflow threshold, a second subset 514 of normalized records is processed to continue incrementing the count of data values for matching keys (from records shown as unshaded boxes) in census array 506, or the second subset 514 of normalized records is processed to store a third subset 516 of normalized records (shown as shaded boxes) as temporary record store 503. Note that third subset 516 is also a subset of second subset 514. This process continues, replacing stream 500 with temporary record store 503, creating a potentially new (smaller) temporary record store 503', while iterating over the current temporary record store 503.

If, after checking (612), no temporary record storage 503 remains, the module 202 iterates over the fields (i.e., from 1 to the number of fields), sending (618) the appropriate census array 506 from the working memory space 508 to the output port, and sending (620) the appropriate census array 510 from the overflow storage space 504 to the output port. After reaching the last field, the loop ends (622). This partial census generation sends the census arrays 506 and 510 to the output port, which allows the census arrays to be output in field index order (as opposed to outputting partial census arrays for different fields as soon as they are ready). This can be useful, for example, if there are downstream computations after the census processing module 204 that require the census arrays to be provided in field index order. Alternatively, other implementations of census generation that do not require ordered output may avoid storing the partial census array 506 in the working memory space 508 in the overflow storage space 504, and instead may simply output the partial census array 506 from the working memory space 508 directly to the output port (for the same reason that a merge operation need not be performed when appending the census arrays 506 and 510).

In short, the second overflow handling process handles overflow conditions of the working memory by moving unmatched records to the overflow storage and continuing to process all new records (updating the census array in the working memory for any matching records). The second overflow handling process effectively manages the overflow of unmatched records to the overflow storage.

There are some differences between the first and second overflow handling processes that may make one or the other more appropriate (i.e., more efficient) in some situations. The first overflow handling process does not require overflowing records to overflow storage, while the second overflow handling process does. However, the second overflow handling process does not require merging census arrays, while the first overflow handling process does. In addition, because the second overflow handling process holds the same census array in working memory, after the overflow condition, until all paths of records in the input stream have been read, the initial distribution of values determines which later values will be matched or not matched. Therefore, for situations where the distribution of duplicate values (if any) in a given field is relatively uniform across all records in the input stream, the second overflow handling process may have an efficient overflow. Each time the census array is overflowed to overflow storage, the first overflow handling process enables matching of a completely new set of values. Therefore, for situations where the distribution of duplicate values in one or more fields across all records in the input stream varies significantly, the first overflow handling process may have an efficient overflow.

Other overflow handling procedures are also possible. For example, a hybrid between the first and second procedures described above could begin handling an overflow condition by storing normalized records that do not match the census array in the overflow storage space (i.e., according to the second procedure). Then, if the fraction of stored normalized records that do not match becomes greater than a certain threshold, the procedure could move the portion of the census array in the working memory space to the overflow storage space (merging it with any previously stored portions of the census array) and continue processing normalized records in the current pass (i.e., according to the first procedure). After the first pass is complete, the procedure would continue by processing the normalized records stored in the overflow storage space using the same hybrid process (i.e., starting to store non-matching normalized records when an overflow condition is reached until the threshold is reached).

The above technology can be implemented using a computing system that performs appropriate software. For example, the software can include a program in one or more computer programs that are executed on one or more programmed or programmable computer systems (can have various architectures, such as distributed, client/server, or network format), each computer system including at least one processor, at least one data storage system (including volatility and/or non-volatile memory and/or storage element) and at least one user interface (for receiving input using at least one input device or port, and for providing output using at least one output device or port). The software can include one or more modules of a large program, for example, the large program provides the design, configuration, and execution-related services of a data flow graph. The module of the program (for example, the element of the data flow graph) can be implemented as a data structure or other organized data that conforms to the data model stored in the database. The module of the program can store array data of any various data structures, such as a hash table or a flat file, which can be optionally indexed and/or compressed.

The software may be provided on a tangible, permanent storage medium (e.g., which can be read by a general-purpose or special-purpose computer system or device) such as a CD-ROM or other computer-readable medium, or on a tangible, permanent medium delivered (e.g., encoded into a propagated signal) to a computer system executing the software via a communication medium of a network. 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 application-specific integrated circuit (ASIC). The processing may be implemented in a distributed manner in which different computational components specified by the software are performed by different computing elements. Each such computer program is preferably stored in or downloaded to a computer-readable storage medium (e.g., a solid-state memory or medium, or a magnetic or optical medium) of a storage device that can be read by a general-purpose or special-purpose programmable computer, for configuring and operating the computer when the computer reads the storage medium or device to perform the processing described herein. It is also contemplated that the system of the present invention may be implemented as a tangible, permanent storage medium configured with a computer program, wherein the storage medium so configured causes the computer to operate in a specific and predefined 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, not to limit, the scope of the present invention, which is defined by the following claims. Therefore, other embodiments are also 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 sequence-independent and, therefore, may be performed in an order different from that described.

Claims (17)

1. A computing system, comprising: Memory devices are used to provide working memory space; Storage devices used to provide overflow storage space; and At least one processor is configured to process multiple data units to produce result information, said processing including: Perform a data operation for each data unit of a first subset of data units of multiple data units. The data operation includes searching for a value in a data unit within at least one data structure of a first set of one or more data structures stored in the working memory space, and if the value is found, modifying the information in the at least one data structure of the first set, and if the value is not found, adding the information to the at least one data structure of the first set. After the overflow condition of the working memory space is met, information is stored in the overflow memory space and at least some of the working memory space is released. A data operation is performed on each data unit of the second subset of the plurality of data units. This data operation includes searching for a value within a data unit of at least one data structure in a second set of one or more data structures stored in the working memory space, and if the value is found, modifying the information in that at least one data structure of the second set. Multiple sets of one or more data structures, including the first set and the second set, are combined to produce the resulting information. 2. The computing system of claim 1, wherein the overflow condition of the working memory space is satisfied if the amount of the working memory space used by the first set of one or more data structures is greater than or equal to a predetermined threshold. 3. The computing system of claim 1, wherein the processing further comprises, after the overflow condition is satisfied and before performing the search for each data unit of the second subset of the data units, storing the first set of one or more data structures in the overflow storage space, and removing the first set of one or more data structures from the working memory space. 4. The computing system of claim 1, wherein combining multiple sets of one or more data structures includes merging at least one data structure of the first set with at least one data structure of the second set. 5. The computing system of claim 4, wherein merging at least one data structure of the first set with at least one data structure of the second set comprises matching a first key in the data structure of the first set of one or more data structures with a second key in the data structure of the second set of one or more data structures, and performing an aggregation operation on the value associated with the first key and the value associated with the second key. 6. The computing system of claim 1, wherein the processing further comprises, after the overflow condition is satisfied and before performing the search for each data unit of the second subset of data units, searching for a value in at least one data structure within the first set of one or more data structures stored in the working memory space for each data unit of the third subset of data units of the plurality of data units, and if the value is found, modifying the information in the at least one data structure of the first set. 7. The computing system according to claim 6, wherein the second subset of data units is a subset of the data units of the third subset of data units. 8. The computing system of claim 1, wherein modifying the information comprises performing an in-place memory operation, the in-place memory operation overwriting a value stored at a location in the working memory space with a different value stored at the same location in the working memory space. 9. The computing system of claim 1, wherein the processing further comprises generating the plurality of data units according to a data source, each data unit including an identifier of a field of the data source and a value appearing in the field within a record of the data source. 10. The computing system of claim 9, wherein the first set of one or more data structures comprises a plurality of associative arrays of key-value pairing entries. 11. The computing system of claim 10, wherein searching for the value within a data cell of at least one data structure of a first set of one or more data structures stored in the working memory space comprises searching for the value as a destination key within a selected key-value pairing entry associative array. 12. The computing system of claim 11, wherein the selected key-value pairing entry associative array corresponds to the identifier in the data unit. 13. The computing system of claim 11, wherein modifying information in at least one data structure of the first set includes adding the value of the found key-value pair entry. 14. The computing system of claim 11, wherein adding information to at least one data structure of the first set comprises adding a new key-value pair entry to the selected array, such that the key of the entry is the value in the data unit and the value of the entry is a count of 1. 15. The computing system of claim 1, wherein the memory device includes a volatile memory device and the storage device includes a non-volatile memory device. 16. A method for processing multiple data units to produce result information, comprising: Perform a data operation for each data unit of a first subset of data units of multiple data units, the data operation comprising searching for a value in a data unit within at least one data structure of a first set of one or more data structures stored in the working memory space of a memory device, and if the value is found, modifying information in the at least one data structure of the first set, and if the value is not found, adding information to the at least one data structure of the first set. After the overflow condition of the working memory space is met, information is stored in the overflow storage space of the storage device and at least some of the working memory space is released. A data operation is performed on each data unit of the second subset of data units of the plurality of data units. This data operation includes searching for a value in a data unit within at least one data structure of the second set of one or more data structures stored in the working memory space, and if the value is found, modifying the information in that at least one data structure of the second set. Multiple sets of one or more data structures, including the first set and the second set, are combined to produce the resulting information. 17. A computer-readable medium storing software for processing a plurality of data units to produce result information, the software including instructions for causing a computing system to execute: Perform a data operation for each data unit of a first subset of data units of multiple data units, the data operation comprising searching for a value in a data unit within at least one data structure of a first set of one or more data structures stored in the working memory space of a memory device, and if the value is found, modifying information in the at least one data structure of the first set, and if the value is not found, adding information to the at least one data structure of the first set. After the overflow condition of the working memory space is met, information is stored in the overflow storage space of the storage device and at least some of the working memory space is released. A data operation is performed on each data unit of the second subset of data units of the plurality of data units. This data operation includes searching for a value in a data unit within at least one data structure of the second set of one or more data structures stored in the working memory space, and if the value is found, modifying the information in at least one data structure of the second set. Multiple sets of one or more data structures, including the first set and the second set, are combined to produce the resulting information.