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 Helps Process Structured Text in Java - Sorting

It is simple for Java to sort data in text files of small size. But when big files are involved, you need to import data segmentally, write out the sorting result of each segment in temporary files and at last, merge these temporary files. The programming will be rather complicated. Even if the file is small enough to be loaded to the memory, you will have to parse the data type of the text file. The job is not difficult but the code is long.

However, these problems can be avoided by using esProc to help with programming in Java. Let’s look at in detail how this will happen. Now you are required to sort the employee data in the text file employee.txt by STATE in ascending order and by BIRTHDAY in descending order. It is assumed that the data size of the file is huge and exceeds the memory capacity.

employee.txt is of the following format:

EID   NAME       SURNAME        GENDER  STATE        BIRTHDAY        HIREDATE         DEPT         SALARY

1       Rebecca   Moore      F       California 1974-11-20       2005-03-11       R&D          7000

2       Ashley      Wilson      F       New York 1980-07-19       2008-03-16       Finance    11000

3       Rachel      Johnson   F       New Mexico     1970-12-17       2010-12-01       Sales         9000

4       Emily         Smith        F       Texas        1985-03-07       2006-08-15       HR    7000

5       Ashley      Smith        F       Texas        1975-05-13       2004-07-30       R&D          16000

6       Matthew Johnson   M     California 1984-07-07       2005-07-07       Sales         11000

7       Alexis        Smith        F       Illinois       1972-08-16       2002-08-16       Sales         9000

8       Megan     Wilson      F       California 1979-04-19       1984-04-19       Marketing        11000

9       Victoria    Davis        F       Texas        1983-12-07       2009-12-07       HR    3000

10     Ryan         Johnson   M     Pennsylvania    1976-03-12       2006-03-12       R&D          13000

11     Jacob        Moore      M     Texas        1974-12-16       2004-12-16       Sales         12000

12     Jessica     Davis        F       New York 1980-09-11       2008-09-11       Sales         7000

13     Daniel       Davis        M     Florida      1982-05-14       2010-05-14       Finance    10000

…

Implementation approach: call the esProc script with Java, import and compute the data, and then return the result in the form of ResultSet to Java. To perform sorting by STATE in ascending order and by BIRTHDAY in descending order, esProc will use an input parameter "sortBy" as the sorting expression, as shown in the following figure:

The value of "sortBy" is STATE,-BIRTHDAY. The field with a minus before it represents the opposite number, which is valid for string data, numerical data and date data.

The code in esProc is as follows:

A1：Define a file cursor object, with the first row being the title and tab being the field separator by default.

A2：Perform sorting according to the expression, using macro to realize parsing the expression dynamically. The "sortBy" in this process is an input parameter. In executing, esProc will first compute the expression enclosed by ${…}, then replace ${…} with the computed result acting as the macro string value and interpret and execute the code. The final code to be executed in this example is =A1.sortx(STATE,-BIRTHDAY;1000000).

A3：Return the result cursor to external program. While Java receives the returned result and traverses the data with ResultSet, esProc will automatically fetch the data corresponding to the cursor. If the sorted data are to be written into other files, the code in A3 should be modified into =file("D:/employee_result.txt").export@t(A2).

If the sorting fields and order are changed, you just modify sortBy– the parameter. For example, if the data are required to be sorted by NAME in ascending order and by STATE and BIRTHDAY in descending order, the value of sortBy will be written as NAME,-STATE,-BIRTHDAY.

sortx function performs sorting by importing data segmentally according to buffer rows, write the results of sorting each segment into temporary files, redistribute the memory usage and then merge these temporary files. Here the parameter 1000000 refers to buffer rows. The principle of assigning value to it is to make the best of the memory to reduce the number of temporary files as far as possible. The number of temporary files is related to the size of both the physical memory and the records, and should be evaluated during programming. Generally, the recommended number is between magnitudes of several hundred thousand to a magnitude of one million.

The code of calling this piece of code (which is saved as test.dfx) in Java with esProc JDBC is as follows:

          //create a connection using esProc JDBC

Class.forName("com.esproc.jdbc.InternalDriver");

con= DriverManager.getConnection("jdbc:esproc:local://");

//call the program in esProc (the stored procedure); test is the name of file dfx

st =(com.esproc.jdbc.InternalCStatement)con.prepareCall("call test(?)");

//set the parameters

st.setObject(1,"NAME,-STATE,-BIRTHDAY");

//execute the esProc stored procedure

st.execute();

//get the result set, which is the eligible set of employees

ResultSet set = st.getResultSet();

If the script is simple, the code can be written directly into the program in Java that calls the esProc JDBC. It won't be necessary to write a special esProc script file (test.dfx):

st=(com. esproc.jdbc.InternalCStatement)con.createStatement();

ResultSet set=st.executeQuery("=file(\"D:/employee.txt\").cursor@t().sortx(NAME,-STATE,BIRTHDAY;1000000)");

This piece of code in Java calls a line of code in esProc script directly, that is, get the data from the text file, compute them and return the result set to set– the object of ResultSet.

If the data in employee.txt can be loaded to the memory altogether, sort function can thus be used to perform all-in-memory sorting, in which esProc won't generate the temporary files. The computational speed will be much faster. The code is as follows:

Parameter sortBy can be written as STATE,-BIRTHDAY, or STATE:1,BIRTHDAY:-1. And it is no need to modify the calling program of Java.