esProc External Memory Computing: Principle of Sorting

It is common to sort records in the table during data analysis and computing. In esProc, sort function is used to sort data in the sequence or the table sequence. External memory sorting is required when data being sorted are massive and cannot be loaded into memory all together, for the ordinary sorting method cannot handle this situation.

1. Massive data sorting with external memory

In data statistics, cursors are usually used to fetch massive data. This applies in esProc, which also processes big data with the cursor. In esProc, the function of a cursor, which reads one or more records each time according to the position(s) marked by it and won’t return all data all at once, is similar to that in a database stored procedure.

A cursor can only fetch part of the data every time, thus operations like sorting and grouping all data in the cursors cannot be executed directly. esProc uses external memory to handle these operations on massive data. Each time it reads some of the data for computing and records the result temporarily in the external memory. Later it will merge all the sub-results into a cursor and works out the final result.

Let’s create a data table with huge data in which the dates and 8-digit phone numbers (the first and the last digit should not be zero) are generated arbitrarily. The data table will be stored in the format of a binary file for convenience. 

Altogether 100,000 rows of data are generated. Read data from the 50,001^th row to the 51,000^th row using the cursor. The result can be seen in C10 as follows:

We’ll take PhoneRecord, the generated data file, as an example to explore how to perform external sorting in esProc.

Using cs.sortx(x…;n) function in external memory sorting, we can sort the data in cursor cs in ascending order according to the computed result of expression x… and set the number of rows in buffer area by defining n to determine the number of records fetched each time for generating a temporary file. For example:

In order to understand how the external memory is used in esProc to sort data, we click

 in the debug area on the toolbar to execute the code step by step until A5. A2 uses the binary data file PhoneRecord to create cursors. A3 uses sortx function to sort data of the cursors. The sorting result, in fact, will be a large cursor merged orderly by many temporary cursor files. The result of A3 is as follows:

A4 fetches the first 1,000 records from this result cursor as follows:

While the code in A3 is executed, external files, which are also called as temporary files, are generated in the directory of temporary files:

Because the number of rows in buffer area was set as 20,000 while using sortx function, five temporary files have been generated for the 100,000 records in the cursor. The data of one of them will be imported:

A2 imports the data as follows:

A3 works out the number of rows in this temporary file as follows:

By comparing the data in A2 with the final sorting result previously obtained, we can see that the former is, actually, the result obtained by sorting a part of the data. This indicates that each temporary file is the sorting result of some data fetched according to the number of rows in buffer area.

Then go on to execute the previous cellset file. We may find that the temporary files will be deleted automatically when the cursor is closed.

sortx function can also be used to sort multiple fields. For example:

A3 sorts data by Date and –PhoneNum , meaning sorting data by date in ascending order, and then sorting those of the same date by phone number in descending order. In programming, it is common to precede an expression for sorting data in descending order by a negative sign. A4 fetches the first 1,000 records from the result as follows:

2. Applications of external memory sorting

In fact, from the operation of external memory sorting we can see one of the uses of the cursor-style sorting, that is, the sorted data can be used in orderly merging. The operation of orderly merging gets data from multiple cursors and computes the sorting expression. Records will be fetched from the cursor that currently has the smallest (or biggest) result. Apparently, this method can only be used when the data of every cursor are properly ordered. In addition, joining records of cursors in alignment with join@x() function also requires that data in every cursor be sorted. About the usage of join@x() function, please refer to esProc External Memory Sorting: Merge and Join Cursor Data.

When the data of a cursor are properly ordered, it can be specified that we fetch data continuously from the cursor until the expression is changed. For example:

A4 fetches data from the cursor in A3 until the Date is changed, meaning the data of the first day will be fetched; A5 skips data of consecutive three days; A6 fetches the data of the fifth day. The results of A4 and A6 are as follows:

esProc External Memory Computing : Principle of Grouping

After data are imported from a data table, we often need to group them as required, or work out grouping and summarizing result. In esProc, groups function is used to compute the result of data grouping and summarizing; or group function can be used to first group the data, then perform further analysis and computation.

But the case will be different in processing huge data, for the records cannot be loaded to the memory all together and distributed into each group. Other times the number of groups is huge and the grouping and summarizing result cannot even be returned all at once. In these two occasions, the external memory grouping is required.

1. Grouping with cursor by directly specifying group numbers

Let’s create a big, simple data table containing employee information, which includes three fields: employee ID, state and birthday. The employee IDs are generated in order and the states are written in abbreviations obtained arbitrarily from the STATES table of demo database; birthdays are the dates selected arbitrarily within 10,000 days before 1994-1-1.The data table will be stored as a binary file for convenience. 

Altogether 1,000,000 rows of data are generated. The result of reading the 50,001^th ~51,000^th rows of data with cursor can be seen in C10 as follows:

In the following, we’ll take the generated data file, BirthStateRecord, as an example to explore how to group data in cursor computing by directly specifying group numbers. Because the data of the big data table cannot be loaded all together into the memory, we cannot group them as we do with the data from an ordinary table sequence. To solve this problem, esProc offers cs.groupn(x) function which can distribute the records in cursor cs according to the computed results of expression x into groups with specified serial numbers and return a sequence of cursors. For example:

To explain the way in which cs.groupn(x) function performs grouping by using external memory to specify group numbers, Click in the debug area of the toolbar to execute the code step by step until A6. A2 creates a cursor with the binary data file BirthStateRecord. A4 creates a sequence using the states’ abbreviations in STATES table.A5 uses groupn function to group data of the cursor; in this process, we need to find the corresponding serial numbers of the states in A4 and make them the group numbers. During the execution of groupn function in A5, a temporary file will be generated for each group to store the grouping result and a sequence of temporary file cursors will be returned as follows:

While the code in A5 is executed, external files are generated in the directory of temporary files:

In the execution of groupn function, the number of temporary files equals that of the groups of records. We can import data from one of the temporary files in another cellset:

The data A2 imports are as follows:

It can be seen that the data of a temporary file is, in fact, the employee information of a state. Here it is the employee information of the state of Missouri. The name of a temporary file is generated arbitrarily by the esProc program and managed by it.

Click  on the toolbar in the previous cellset file and go on with the execution of this cellset. In A8, when all file cursors are closed, the temporary files will be deleted automatically. A6 fetches from the first file cursor the employee information of the state of Alabama as follows:

A7 works out the grouping and summarizing result of the 22^nd group using groups function, that is, the number of employees from the state of Michigan:

Actually A6 and A7 fetch data from two groups respectively. When the data of a file cursor have been fetched, the corresponding temporary file will be deleted automatically.

It is thus clear that a sequence consisting of temporary file cursors will be returned in grouping records of cursors using directly specified group numbers. Each file cursor contains the records of a group which can be further processed.

2. Grouping and summarizing result sets of huge data

When grouping data of cursors, most of the time we needn’t to get the detailed data of each group. What we only need is the grouping and summarizing result. To get the number of employees of each state from BirthStateRecord, for example, we use groups function to compute the grouping and summarizing result: 

Thus we can get the result in A3:

Here we notice that the groups function for grouping and summarizing will return a table sequence as the result after the computation is completed. In processing massive data, sometimes they need to be divided into a lot of groups and the result set of grouping and summarizing is too big to be returned all at once. This includes the following cases: the telecom company makes statistics of each customer’s bill; online shopping malls make statistics by categories about the sales of each kind of commodity, and the like. In these cases, the use of groups function may result in a memory overflow. We can use groupx(x:F,…;y:F,…;n) function instead to perform grouping and summarizing by making use of external memory. In the function, n represents the number of rows in buffer area. For example:

Still, the code is executed step by step until A4. In A3, groupx function uses external memory to perform grouping and summarizing. In cursor computing, groupx function is used in the operations of both grouping and summarizing with external memory and grouping by directly specified group numbers. The difference of the two operations lies in the parameters. A3 performs grouping by employees’ birthdays, then summate the number of employees born on each of the dates. During the computation, the number of rows in buffer area is set as 1,000. The result returned by A3 is a cursor as follows:

After the code in A3 is executed, external files will be generated in the directory of temporary files:

The data of one of the temporary files can be imported:

The data A2 imports are as follows:

The data of A3 is as follows:

It can be seen that each temporary file is the result of grouping and summarizing a part of the data according to employees’ birthdays. A larger cursor composed of all temporary files will be merged and returned by esProc. When the temporary files are generated, esProc will select a group number suitable for computing, so the rows of data in the temporary files will be a little more than the number of rows we set in buffer area. Special attention is needed in this point.

Go on with the execution of the cellset in the previous cellset file. When cursors are closed in A5, the temporary files will be automatically deleted. A4 fetches the first 1,000 birthdays from the cursor generated in A3 and counts the number of employees born on each birth date, as shown below: