Flexible schema column store

• US 8,516,008 B1
• Filed: 05/18/2012
• Issued: 08/20/2013
• Est. Priority Date: 05/18/2012
• Status: Active Grant

• Current Assignee: Splunk Inc.
• Original Assignee: Splunk Inc.
• Inventors: Blank, Mitchell Neuman Jr., Sorkin, Stephen Phillip, Marquardt, David Ryan
• Primary Examiner(s): LE, THU NGUYET T
• Application Number:
  US13/475,798
• Time in Patent Office: 459 Days
• Field of Search: 707/609, 707/802
• US Class Current: 707/802
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/33 Querying
• CPC Class Codes: G06F 16/338 Presentation of query results

Abstract

Embodiments are directed towards receiving and processing search queries directed towards relatively large sets of data. The data is stored in a record based datastore. From the stored data, field names, corresponding field values, and posting values may be determined. Posting values may be employed to locate records in the datastore that include the field names and field values. The field names, field values, and posting values may be employed to generate a lexicon. If queries are received, a lexicon query processor may employ the lexicon separate from the datastore to generate responses to the received queries. Queries may include clauses that may be processed using the lexicon separate from the datastore, such as, where clause expressions, group-by clause expressions, aggregation functions, or the like. A time values array may be used to enable queries to process group-by-time expressions that may return results grouped into sub-sets based on time ranges.

Claims

1. A method for searching data using a network device that is operative to perform actions, comprising:

storing data into at least one datastore;

generating at least one field name that corresponds to at least one field value from the data;

determining at least one posting value associated with the at least one field name that corresponds to the at least one field value, wherein the at least one posting value at least identifies a location of a record in the at least one datastore that includes the at least one field name that corresponds to the at least one field value;

generating at least one lexicon that includes at least one lexicon record that comprises the at least one field name, the at least one field value, and the at least one posting value which correspond to each other;

receiving a query directed to data stored in the at least one datastore;

generating at least one result for the query based on at least a portion of the lexicon separate from the at least one datastore;

if the at least one query includes at least one aggregation function, performing further actions, including;

locating the at least one lexicon record for at least a first lexicon record that includes at least a field name that is associated with the at least one aggregation function; and

generating at least one aggregated result by iterating over each lexicon record that includes the at least one field name and incorporating the corresponding at least one field value into the aggregated result; and

projecting the at least one result into at least one row in at least one table.

2. The method of claim 1, wherein generating at least one result further comprises, if the at least one query includes the at least one aggregation function:

and if a where clause exists, employing a list indicated by at least one helper array for generating the at least one aggregated result.

3. The method of claim 1, wherein generating at least one result further comprises:

if the at least one query includes at least one of group-by expressions, perform further actions, including;

generating at least one helper array;

determining each lexicon record that includes at least a field name associated with each group-by expression;

iterating through each posting value corresponding to each determined lexicon record based on at least one other helper array associated with the processing of a where clause;

employing the at least one lexicon to determine a group-by value and a group-by bin that is associated with each posting value;

if the group-by bin for the group-by value is absent, generating a new group-by bin;

if the new group-by bin has a parent group-by bin, associating the new group-by bin with the parent group-by bin;

projecting each posting value into the group-by bin by storing a pointer in the at least one helper array;

if an aggregation function exists in the query, generating at least one aggregated result by iterating over each lexicon record that includes the at least one field name and incorporating the corresponding at least one field value into the aggregated result by using the at least one helper array to determine which group by bin to store the aggregated result; and

generating each result row by traversing the group-by bins based on an order in which the group-by bins are generated.

4. The method of claim 1, wherein generating at least one result further comprises:

if the at least one query includes at least one where clause that includes at least one where clause expression, perform further actions, including;

generating at least one helper array for each where clause expression;

determining each lexicon record that includes at least one field name associated with the at least one where clause expression;

evaluating each where clause expression for each determined lexicon record and storing the result in the at least one helper array;

assigning a value in the at least one helper array based on at least the generated result, wherein the at least one helper array corresponds to the where clause expression associated with the generated result; and

generating at least one result row based on the at least one helper array, wherein if there is a plurality of helper arrays, the at least one result row is further determined based on at least one logical operand that is included in the at least one where clause.

5. The method of claim 1, wherein generating at least one result further comprises:

if the at least one query includes at least one of group-by-time expressions, perform further actions, including;

generating at least one helper array;

iterating through a time values array to determine a time value entry, wherein the time value entry is used to determine a group-by-time value;

if the group-by bin for the group-by-time value is absent, generating a new group-by bin;

if the new group-by bin has a parent group-by bin, associating the new group-by bin with the parent group-by bin;

projecting a posting value that corresponds to the time value entry into the group-by bin by storing a pointer in the at least one helper array;

if a time snap function is operative, project each posting value that is bounded by the time snap function into the at least one helper array and advance the time values array to the time snap boundary;

if an aggregation function exists in the query, generating at least one aggregated result by iterating over each lexicon record that includes the at least one field name and incorporating the corresponding at least one field value into the aggregated result by using the at least one helper array to determine which group by bin to store the aggregated result; and

generating each result row by traversing the group-by bins based on an order the group-by bins are generated.

6. The method of claim 1, wherein generating at least one lexicon further comprises ordering each lexicon record such that each lexicon record including a same field name is adjacent.

7. The method of claim 1, wherein generating at least one lexicon further comprises, sorting each posting value included in each lexicon record based on a position of the located records within in the datastore.

8. A network device that is operative for searching data comprising:

a transceiver that is operative to communicate over a network;

a memory that is operative to store at least instructions; and

a processor device that is operative to execute instructions that enable actions, including;

storing data into at least one datastore;

generating at least one field name that corresponds to at least one field value from the data;

determining at least one posting value associated with the at least one field name that corresponds to the at least one field value, wherein the at least one posting value at least identifies a location of a record in the at least one datastore that includes the at least one field name that corresponds to the at least one field value;

generating at least one lexicon that includes at least one lexicon record that comprises the at least one field name, the at least one field value, and the at least one posting value which correspond to each other;

receiving a query directed to data stored in the at least one datastore;

generating at least one result for the query based on at least a portion of the lexicon separate from the at least one datastore;

if the at least one query includes at least one aggregation function, performing further actions, including;

locating the at least one lexicon record for at least a first lexicon record that includes at least a field name that is associated with the at least one aggregation function; and

generating at least one aggregated result by iterating over each lexicon record that includes the at least one field name and incorporating the corresponding at least one field value into the aggregated result; and

projecting the at least one result into at least one row in at least one table.

9. The network device of claim 8, wherein generating at least one result further comprises,

if the at least one query includes the at least one aggregation function,

and if a where clause exists, employing a list indicated by at least one helper array for generating the at least one aggregated result.

10. The network device of claim 8, wherein generating at least one result further comprises:

if the at least one query includes at least one of group-by expressions, perform further actions, including;

generating at least one helper array;

determining each lexicon record that includes at least a field name associated with each group-by expression;

iterating through each posting value corresponding to each determined lexicon record based on at least one other helper array associated with the processing of a where clause;

employing the at least one lexicon to determine a group-by value and a group-by bin that is associated with each posting value;

if the group-by bin for the group-by value is absent, generating a new group-by bin;

if the new group-by bin has a parent group-by bin, associating the new group-by bin with the parent group-by bin;

projecting each posting value into the group-by bin by storing a pointer in the at least one helper array;

if an aggregation function exists in the query, generating at least one aggregated result by iterating over each lexicon record that includes the at least one field name and incorporating the corresponding at least one field value into the aggregated result by using the at least one helper array to determine which group by bin to store the aggregated result; and

generating each result row by traversing the group-by bins based on an order in which the group-by bins are generated.

11. The network device of claim 8, wherein generating at least one result further comprises:

if the at least one query includes at least one where clause that includes at least one where clause expression, perform further actions, including;

generating at least one helper array for each where clause expression;

determining each lexicon record that includes at least one field name associated with the at least one where clause expression;

evaluating each where clause expression for each determined lexicon record and storing the result in the at least one helper array;

assigning a value in the at least one helper array based on at least the generated result, wherein the at least one helper array corresponds to the where clause expression associated with the generated result; and

generating at least one result row based on the at least one helper array, wherein if there is a plurality of helper arrays, the at least one result row is further determined based on at least one logical operand that is included in the at least one where clause.

12. The network device of claim 8, wherein generating at least one result further comprises:

if the at least one query includes at least one of group-by-time expressions, perform further actions, including;

generating at least one helper array;

iterating through a time values array to determine a time value entry, wherein the time value entry is used to determine a group-by-time value;

if the group-by bin for the group-by-time value is absent, generating a new group-by bin;

if the new group-by bin has a parent group-by bin, associating the new group-by bin with the parent group-by bin;

projecting a posting value that corresponds to the time value entry into the group-by bin by storing a pointer in the at least one helper array;

if a time snap function is operative, project each posting value that is bounded by the time snap function into the at least one helper array and advance the time values array to the time snap boundary;

if an aggregation function exists in the query, generating at least one aggregated result by iterating over each lexicon record that includes the at least one field name and incorporating the corresponding at least one field value into the aggregated result by using the at least one helper array to determine which group by bin to store the aggregated result; and

generating each result row by traversing the group-by bins based on an order the group-by bins are generated.

13. The network device of claim 8, wherein generating at least one lexicon further comprises ordering each lexicon record such that each lexicon record including a same field name is adjacent.

14. The network device of claim 8, wherein generating at least one lexicon further comprises, sorting each posting value included in each lexicon record based on a position of the located records within in the datastore.

15. A processor readable non-transitive storage media that includes instructions for searching data, wherein execution of the instructions by a processor device enables actions, comprising:

storing data into at least one datastore;

generating at least one field name that corresponds to at least one field value from the data;

determining at least one posting value associated with the at least one field name that corresponds to the at least one field value, wherein the at least one posting value at least identifies a location of a record in the at least one datastore that includes the at least one field name that corresponds to the at least one field value;

generating at least one lexicon that includes at least one lexicon record that comprises the at least one field name, the at least one field value, and the at least one posting value which correspond to each other;

receiving a query directed to data stored in the at least one datastore;

generating at least one result for the query based on at least a portion of the lexicon separate from the at least one datastore;

if the at least one query includes at least one aggregation function, performing further actions, including;

locating the at least one lexicon record for at least a first lexicon record that includes at least a field name that is associated with the at least one aggregation function; and

generating at least one aggregated result by iterating over each lexicon record that includes the at least one field name and incorporating the corresponding at least one field value into the aggregated result; and

projecting the at least one result into at least one row in at least one table.

16. The media of claim 15, wherein generating at least one result further comprises,

if the at least one query includes the at least one aggregation function

and if a where clause exists, employing a list indicated by at least one helper array for generating the at least one aggregated result.

17. The media of claim 15, wherein generating at least one result further comprises:

if the at least one query includes at least one of group-by expressions, perform further actions, including;

generating at least one helper array;

determining each lexicon record that includes at least a field name associated with each group-by expression;

iterating through each posting value corresponding to each determined lexicon record based on at least one other helper array associated with the processing of a where clause;

employing the at least one lexicon to determine a group-by value and a group-by bin that is associated with each posting value;

if the group-by bin for the group-by value is absent, generating a new group-by bin;

if the new group-by bin has a parent group-by bin, associating the new group-by bin with the parent group-by bin;

projecting each posting value into the group-by bin by storing a pointer in the helper array;

if an aggregation function exists in the query, generating at least one aggregated result by iterating over each lexicon record that includes the at least one field name and incorporating the corresponding at least one field value into the aggregated result by using the at least one helper array to determine which group by bin to store the aggregated result; and

generating each result row by traversing the group-by bins based on an order in which the group-by bins are generated.

18. The media of claim 15, wherein generating at least one result further comprises:

if the at least one query includes at least one where clause that includes at least one where clause expression, perform further actions, including;

generating at least one helper array for each where clause expression;

determining each lexicon record that includes at least one field name associated with the at least one where clause expression;

evaluating each where clause expression for each determined lexicon record and storing the result in the at least one helper array;

assigning a value in the at least one helper array based on at least the generated result, wherein the at least one helper array corresponds to the where clause expression associated with the generated result; and

generating at least one result row based on the at least one helper array, wherein if there is a plurality of helper arrays, the at least one result row is further determined based on at least one logical operand that is included in the at least one where clause.

19. The media of claim 15, wherein generating at least one result further comprises:

if the at least one query includes at least one of group-by-time expressions, perform further actions, including;

generating at least one helper array;

iterating through a time values array to determine a time value entry, wherein the time value entry is used to determine a group-by-time value;

if the group-by bin for the group-by-time value is absent, generating a new group-by bin;

if the new group-by bin has a parent group-by bin, associating the new group-by bin with the parent group-by bin;

projecting a posting value that corresponds to the time value entry into the group-by bin by storing a pointer in the at least one helper array;

if a time snap function is operative, project each posting value that is bounded by the time snap function into the at least one helper array and advance the time values array to the time snap boundary;

if an aggregation function exists in the query, generating at least one aggregated result by iterating over each lexicon record that includes the at least one field name and incorporating the corresponding at least one field value into the aggregated result by using the at least one helper array to determine which group by bin to store the aggregated result; and

generating each result row by traversing the group-by bins based on an order the group-by bins are generated.

20. The media of claim 15, wherein generating at least one lexicon further comprises ordering each lexicon record such that each lexicon record including a same field name is adjacent.

21. The media of claim 15, wherein generating at least one lexicon further comprises, sorting each posting value included in each lexicon record based on a position of the located records within in the datastore.