FLEXIBLE SCHEMA COLUMN STORE

• US 20130311438A1
• Filed: 10/29/2012
• Published: 11/21/2013
• Est. Priority Date: 05/18/2012
• Status: Active Grant

• Current Assignee: Splunk Inc. (Cisco Systems, Inc.)
• Original Assignee: Splunk Inc. (Cisco Systems, Inc.)
• Inventors: Marquardt, David Ryan, Blank, Mitchell Neuman Jr., Sorkin, Stephen Phillip
• Granted Patent: US 9,753,974 B2
• Time in Patent Office: Days
• US Class Current: 707/706
• 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:

accessing an event, the event including machine data;

determining, for a field name, a field value included within the machine data in the event;

determining a posting value for the event that identifies a location in a datastore at which data for the event is stored;

identifying a lexicon record in a lexicon representing the field value for the field name, and

adding the posting value for the event to the lexicon record.

2. The method of claim 1, further comprising:

receiving a query directed to data stored in the datastore;

determining a result for the query using the lexicon;

presenting the result,

determining that the query includes an aggregation function; and

identifying at least one lexicon record in the lexicon that includes at least a field name that is associated with the aggregation function,

wherein the result is determined based on an iteration over field values corresponding to the identified at least one lexicon record.

6. The method of claim 1, further comprising ordering each lexicon record such that each lexicon record including a same field name is adjacent.

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

22. The method of claim 1, further comprising:

receiving a query directed to data stored in the datastore;

determining a result for the query using the lexicon; and

presenting the result.

23. The method of claim 1, further comprising:

receiving a query directed to data stored in the datastore;

determining a result for the query using the lexicon; and

presenting the result,

wherein determining the result comprises identifying a plurality of posting values associated with the lexicon record.

24. The method of claim 1, further comprising:

receiving a query directed to data stored in the datastore;

determining a result for the query using the lexicon; and

presenting the result,

wherein the result is determined without querying the datastore.

25. The method of claim 1, further comprising:

receiving a query directed to data stored in the datastore;

determining that the query includes an aggregation function;

identifying at least one lexicon record in the lexicon corresponding to a field name that is associated with the aggregation function; and

determining a result for the query using the lexicon record,

wherein the result is derived from an iteration over values for a second field in events identified by the posting values in the lexicon record.

26. The method of claim 1, further comprising:

receiving a query directed to data stored in the datastore;

determining that the query includes an aggregation function;

identifying at least one lexicon record in the lexicon corresponding to a field name that is associated with the aggregation function; and

determining a result for the query using the lexicon record,

wherein the result is derived from a calculation involving a number of posting values in the lexicon record.

27. The method of claim 1, further comprising

receiving a query directed to data stored in the datastore;

determining that the query includes an aggregation function;

identifying at least one lexicon record in the lexicon corresponding to a field name that is associated with the aggregation function;

identifying a plurality of first lexicon records in the lexicon, wherein each first lexicon record of the plurality of first lexicon records represents a different first field value for a first field name, the first field name being present in the query;

identifying, for each first lexicon record of the plurality of first lexicon records, a second lexicon record in the lexicon, wherein each of the first lexicon record and the second lexicon records represent a same event, and wherein the second lexicon record represents a second field value for a second field name, the second field name being present in the query; and

generating a helper array, wherein the helper array includes a plurality of entries, each entry of the plurality of entries corresponding to a first lexicon record of the plurality of first lexicon records, wherein each entry of the plurality of entries is further indicative of the second field value,

wherein determining the result for the query includes using the helper array.

28. The method of claim 1, further comprising:

receiving a query directed to data stored in the datastore;

determining that the query includes an aggregation function;

identifying at least one lexicon record in the lexicon corresponding to a field name that is associated with the aggregation function; and

determining a result for the query using the lexicon record,

wherein the result is derived from an iteration over values for a second field in events identified by the posting values in the lexicon record.

29. The method of claim 1, further comprising:

receiving a query directed to data stored in the datastore;

determining that the query includes an aggregation function;

identifying at least one lexicon record in the lexicon corresponding to a field name that is associated with the aggregation function; and

determining a result for the query using the lexicon record,

wherein the result is derived from a calculation involving a number of posting values in the lexicon record.

3-5. -5. (canceled)

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;

accessing an event, the event including machine data;

determining, for a field name, a field value included within the machine data in the event;

determining a posting value for the event that identifies a location in a datastore at which data for the event is stored;

identifying a lexicon record in a lexicon representing the field value for the field name, and

adding the posting value for the event to the lexicon record.

9. The network device of claim 8, wherein the actions further comprise:

receiving a query directed to data stored in the datastore;

determining a result for the query using the lexicon;

presenting the result,

determining that the query includes an aggregation function; and

identifying at least one lexicon record in the lexicon that includes at least a field name that is associated with the aggregation function,

wherein the result is determined based on an iteration over field values corresponding to the identified at least one lexicon record.

13. The network device of claim 8, wherein the actions further comprise ordering each lexicon record such that each lexicon record including a same field name is adjacent.

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

30. The network device of claim 8, wherein the actions further comprise:

receiving a query directed to data stored in the datastore;

determining a result for the query using the lexicon; and

presenting the result.

31. The method of claim 8, wherein the actions further comprise:

receiving a query directed to data stored in the datastore;

determining a result for the query using the lexicon; and

presenting the result,

wherein determining the result comprises identifying a plurality of posting values associated with the lexicon record.

32. The network device of claim 8, wherein the actions further comprise:

receiving a query directed to data stored in the datastore;

determining a result for the query using the lexicon; and

presenting the result,

wherein the result is determined without querying the datastore.

33. The network device of claim 8, wherein the actions further comprise:

receiving a query directed to data stored in the datastore;

determining a result for the query using the lexicon;

presenting the result;

identifying a plurality of first lexicon records in the lexicon, wherein each first lexicon record of the plurality of first lexicon records represents a different first field value for a first field name, the first field name being present in the query;

identifying, for each first lexicon record of the plurality of first lexicon records, a second lexicon record in the lexicon, wherein each of the first lexicon record and the second lexicon records represent a same event, and wherein the second lexicon record represents a second field value for a second field name, the second field name being present in the query; and

generating a helper array, wherein the helper array includes a plurality of entries, each entry of the plurality of entries corresponding to a first lexicon record of the plurality of first lexicon records, wherein each entry of the plurality of entries is further indicative of the second field value,

wherein determining the result for the query includes using the helper array.

34. The network device of claim 8, wherein the actions further comprise:

receiving a query directed to data stored in the datastore;

determining that the query includes an aggregation function;

identifying at least one lexicon record in the lexicon corresponding to a field name that is associated with the aggregation function; and

determining a result for the query using the lexicon record,

wherein the result is derived from an iteration over values for a second field in events identified by the posting values in the lexicon record.

35. The network device of claim 8, wherein the actions further comprise:

receiving a query directed to data stored in the datastore;

determining that the query includes an aggregation function;

identifying at least one lexicon record in the lexicon corresponding to a field name that is associated with the aggregation function; and

determining a result for the query using the lexicon record,

wherein the result is derived from a calculation involving a number of posting values in the lexicon record.

10-12. -12. (canceled)

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:

accessing an event, the event including machine data;

determining, for a field name, a field value included within the machine data in the event;

determining a posting value for the event that identifies a location in a datastore at which data for the event is stored;

identifying a lexicon record in a lexicon representing the field value for the field name, and

adding the posting value for the event to the lexicon record.

16. The media of claim 15, wherein the actions further comprise:

receiving a query directed to data stored in the datastore;

determining a result for the query using the lexicon;

presenting the result,

determining that the query includes an aggregation function; and

identifying at least one lexicon record in the lexicon that includes at least a field name that is associated with the aggregation function,

wherein the result is determined based on an iteration over field values corresponding to the identified at least one lexicon record.

20. The media of claim 15, wherein the actions further comprise ordering each lexicon record such that each lexicon record including a same field name is adjacent.

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

36. The media of claim 15, wherein the actions further comprise:

receiving a query directed to data stored in the datastore;

determining a result for the query using the lexicon; and

presenting the result.

37. The media of claim 15, wherein the actions further comprise:

receiving a query directed to data stored in the datastore;

determining a result for the query using the lexicon; and

presenting the result,

wherein determining the result comprises identifying a plurality of posting values associated with the lexicon record.

38. The media of claim 15, wherein the actions further comprise:

receiving a query directed to data stored in the datastore;

determining a result for the query using the lexicon; and

presenting the result,

wherein the result is determined without querying the datastore.

39. The media of claim 15, wherein the actions further comprise:

receiving a query directed to data stored in the datastore;

determining a result for the query using the lexicon;

presenting the result;

receiving a query directed to data stored in the datastore;

determining a result for the query using the lexicon;

presenting the result;

identifying a plurality of first lexicon records in the lexicon, wherein each first lexicon record of the plurality of first lexicon records represents a different first field value for a first field name, the first field name being present in the query;

identifying, for each first lexicon record of the plurality of first lexicon records, a second lexicon record in the lexicon, wherein each of the first lexicon record and the second lexicon records represent a same event, and wherein the second lexicon record represents a second field value for a second field name, the second field name being present in the query; and

generating a helper array, wherein the helper array includes a plurality of entries, each entry of the plurality of entries corresponding to a first lexicon record of the plurality of first lexicon records, wherein each entry of the plurality of entries is further indicative of the second field value,

wherein determining the result for the query includes using the helper array.

17-19. -19. (canceled)