Database system with improved methods for radix sorting

• US 5,924,091 A
• Filed: 08/28/1996
• Issued: 07/13/1999
• Est. Priority Date: 08/28/1996
• Status: Expired due to Term

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Burkhard, Neil A.
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US08/704,069
• Time in Patent Office: 1,049 Days
• Field of Search: 707/7, 707/1, 707/2
• US Class Current: 1/1
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

System and methods are described for improved sorting of information records. The system provides radix sorting on native data types--that is, without the resource-expensive approach of converting data types into character representations. A correct interpretation of a group of bits under examination is provided by the system at the point of examination by a radixsort engine. "Sort plan" information is provided to the radixsort engine instructing it how a particular set of bits should be interpreted for purposes of comparison. The knowledge includes a "comparison type" for a set of bits under exam. This is employed by the engine to determine an appropriate "weighting" of each group of bits--how each group should be treated at the point of comparison. The engine itself operates generically: it simply operates on the set of bits as specified by the sort plan entries, regardless of the particular data types which comprise the bits or the one or more keys from which the bits are derived. In this manner, the system can enable the radixsort engine to properly interpret groups of bits, for undertaking a comparison operation for different types, thereby avoiding the undesirable task of converting data types into character representations.

Claims

1. In a computer system storing a database comprising a plurality of data records, an improved method for sorting data records, the method comprising:

specifying a sort order which the data records are to be sorted according to, said sort order indicating at least one field of the data records which the data records are to be sorted by, wherein said at least one field is capable of storing a data type having an arbitrary bit ordering;

setting a radix value indicating how contiguous bits from said at least one field are to be grouped into bit sets regardless of data types which comprise said at least one field, each bit set serving as a unit for comparison during the sort;

creating sort plan information specifying a particular sequence of bit sets from said at least one field which are to be compared during the sort and specifying a comparison type for each particular bit set, said sort plan information being capable of specifying an arbitrary sequence of said bit sets to be compared during the sort, said comparison type indicating how each bit set is to be interpreted upon comparison; and

sorting the data records by performing at least a radixsort on the data records based on said sort plan information.

2. The method of claim 1, wherein said radix value is a pre-selected value selected from a range of 8 to 11.

3. The method of claim 2, wherein said radix value is set equal to 8.

4. The method of claim 1, wherein said at least one field includes information having a non-character data type.

5. The method of claim 1, wherein the sort order comprises ordering the data records according to key values stored by a single field.

6. The method of claim 1, wherein the sort order comprises ordering the data records according to key values stored by multiple fields.

7. The method of claim 1, wherein the sort order specifies an ascending sort order.

8. The method of claim 1, wherein the sort order specifies a descending sort order.

9. The method of claim 1, wherein said sort plan information references additional information which allows the system to determine an appropriate weighting for particular bit sets.

10. The method of claim 9, wherein said additional information comprises a two'"'"'s complement lookup table.

11. The method of claim 9, wherein additional information comprises a signed magnitude lookup table.

12. The method of claim 1, wherein said sorting step includes:

examining successive bit sets from the data records and applying an appropriate weighting to each particular bit set.

13. The method of claim 1, wherein said at least one field comprises a non-character data type and wherein the sort is completed without converting values from said at least one field into a character data type.

14. The method of claim 1, wherein said method includes sorting said data records into a plurality of bins according to a bit set histogram determined at a particular bit set position within said at least one field.

15. The method of claim 14, wherein each bin is further sorted according to a radixsort until a pre-selected threshold value of data records remaining in the bin is reached, whereupon data records which remain in the bin are sorted by performing an insertsort.

16. The method of claim 1, wherein said comparison type is a selected one of an unsigned key, a two'"'"'s complement key, a sign-magnitude key, and a character array key.

17. The method of claim 1, wherein said radix value is set equal to 32.

18. The method of claim 1, wherein said sorting method is performed by the first swapping pointers which point to said data records.

19. The method of claim 1, wherein the radix value is selected as a value based on how machine words are aligned in memory for the computer system.

20. The method of claim 1, wherein said sort plan information includes an array of entries describing how the system is to treat sets of bits from said at least one field at comparison time, said array being ordered from most-significant bits to least-significant bits of each said at least one field.

21. In a data processing system, an improved method for sorting data records according to at least one sort key, each sort key comprising key values derived from a particular field of the data records, said particular field comprising a data type capable of having an arbitrary bit ordering, the method comprising:

based on said at least one sort key, constructing a sort plan specifying sets of bits from said at least one sort key which are to undergo comparison as a group and specifying how each set of bits is to be interpreted at the point of comparison, based on underlying data types which comprise said at least one sort key, said sort plan being capable of specifying an arbitrary sequence of said bit sets to be compared during the sort; and

performing a sort by examining successive sets of bits and ordering each data record according to how the bits which the bit sets each comprise are interpreted at the point of comparison.

22. The method of claim 21, wherein said sort plan indicates where bits for the bit sets are located in said at least one sort key.

23. The method of claim 22, wherein where bit sets are located is indicated as an offset value pointing to where a particular bit set occurs within a sort key.

24. The method of claim 22, wherein each bit set comprises a number of bits fixed at a particular radix value.

25. The method of claim 24, wherein said radix value is set equal to 8.

26. The method of claim 21, wherein said at least one sort key includes a non-character data type.

27. The method of claim 21, wherein said at least one sort key includes a variable-length character data type.

28. The method of claim 21, wherein said sort plan references information indicating a particular weighting which a particular set of bits is accorded, based on an underlying data type for the sort key which the particular set of bits is taken from.

29. The method of claim 21, wherein said weighting is further based on a bit position of the particular set of bits relative to other bits of that underlying data type.

30. The method of claim 21, wherein said sort plan indicates a comparison type for each bit set, each comparison type indicating how a particular set of bits is to be interpreted at the point of comparison based on underlying data type.

31. In a computer-implemented radixsort process, an improved method for performing comparisons during radix sorting of data records, said data records storing at least one data field to sort on that comprises a data type capable of having an arbitrary bit ordering, the method comprising:

determining a comparison type and weighting for indicating how each particular set of bits is to be interpreted during comparison operations of the radixsort, said step specifying a particular sequence for comparing sets of bits for a data type capable of having an arbitrary bit ordering; and

performing comparison operations on original bits taken from the data records, each comparison operation interpreting the original bits according to said specified particular sequence and said determined comparison type and weighting which indicates how each particular set of bits is to be sorted.

32. The method of claim 31, wherein the radixsort is a radix 8 sort and wherein each set of bits comprises 8 bits.

33. The method of claim 31, wherein original bits employed during comparison operations are ones which are taken without conversion from corresponding bits in the data records.

34. The method of claim 31, further comprising:

determining a location of each bit set relative to the beginning of a data field from which the bit set is derived.

35. The method of claim 34, further comprising:

storing sequence information allowing bit sets to be taken from arbitrary locations of a data field which the data records are to be sorted by.

36. A system for sorting data records comprising:

a computer storing a database of data records;

means for sorting data records by at least one field, said means comprising;

means for selecting original bit sets from said at least one field, said bit sets having a fixed length and an arbitrary ordering,

means for indicating how each original bit set is to be interpreted upon comparison during the sort, including indicating a particular sequence in which the original bit sets are to be compared, and

means for ordering the data records according to interpretation of individual bit sets at the point of comparison.

37. The system of claim 36, wherein said radix value is a pre-selected value selected from a range of 8 to 11.

38. The system of claim 36, wherein said radix value is set equal to 8.

39. The system of claim 36, wherein said at least one field includes information having a non-character data type.

40. The system of claim 36, wherein said interpreting means includes lookup means for determining a particular weighting for a set of bits being compared.

41. The system of claim 40, wherein said lookup means comprises a two'"'"'s complement lookup table.

42. The system of claim 40, wherein lookup means comprises a signed magnitude lookup table.