Method for Preparing Numerous Data for Efficient Manipulation using Interning
A data-processing technique for increasing data-size capacity and improving query speed on large datasets where fields within records are replaced by integers representing distinct values of those fields, the integers drawn from a densely-populated range so that record selection, aggregation and other actions can be performed efficiently using bit sets and other data structures.
1 . A method of preparing a plurality of multi-field data records for improved query performance, comprising:
for each record of the plurality of multi-field data records:
reading the record;
interning a value of a data field of the record to obtain an integer representing the value of the data field; and
creating a memory structure to represent the record, said memory structure containing the representative integer and excluding the value of the data field.
2 . The method of claim 1 , further comprising:
repeating the interning operation for at least a value of one other data field of the record to obtain a second integer representing the value of the one other data field, wherein
the memory structure contains the second integer and excludes the value of the one other data field.
3 . The method of claim 1 wherein the integer representing the value of the data field is part of a densely-utilized range of integers, each representing a distinct value seen in a corresponding data field of at least one multi-field data record.
4 . The method of claim 3 wherein a numerical order of integers representing distinct data values is similar to an order of the distinct data values.
5 . The method of claim 4 wherein the order of the distinct data values is an alphabetical order.
6 . The method of claim 4 wherein the order of the distinct data values is a numerical order.
7 . The method of claim 4 wherein the order of the distinct data values is a temporal order.
8 . The method of claim 4 wherein the order of the distinct data values is a revenue order.
9 . The method of claim 1 , further comprising:
receiving a query specification including a value for comparing with a data field;
searching an interned-value structure to find an integer representing the value for comparing with the data field; and
identifying a subset of memory structures having a corresponding value of the representative integer.
10 . The method of claim 9 , further comprising:
interning the subset of memory structures to obtain an integer representing said subset of memory structures.
11 . A non-transitory computer-readable medium containing instructions and data to cause a programmable processor to perform operations comprising:
initializing data interning tables for a plurality of classes of data values;
processing a plurality of multi-field data records;
inserting entries in the data interning tables for each distinct value of each data class encountered during the processing operation;
constructing a memory structure to represent each multi-field data record of the plurality of multi-field data records, wherein
each memory structure includes an index of an entry in each of the data interning tables.
12 . The non-transitory computer-readable medium of claim 11 , containing additional data and instructions to cause the programmable processor to perform operations comprising:
13 . The non-transitory computer-readable medium of claim 11 , wherein distinct values in a data interning table are alphanumeric strings.
14 . The non-transitory computer-readable medium of claim 11 , wherein distinct values in a data interning table are timestamps.
15 . The non-transitory computer-readable medium of claim 11 , wherein distinct values in a data interning table are network addresses.
16 . The non-transitory computer-readable medium of claim 11 , wherein distinct values in a data interning table are partial Uniform Resource Names (“URNs”).
17 . The non-transitory computer-readable medium of claim 11 , wherein a numeric order of indices in a data interning table are similar to an alphabetical order of distinct data values inserted into the data interning table.
18 . The non-transitory computer-readable medium of claim 11 , wherein a numeric order of indices in a data interning table are similar to a numeric order of distinct data values inserted into the data interning table.
19 . The non-transitory computer-readable medium of claim 11 , wherein a numeric order of indices in a data interning table are similar to a temporal order of distinct data values inserted into the data interning table.