Flexible schema column store

• US 9,753,974 B2
• Filed: 10/29/2012
• Issued: 09/05/2017
• Est. Priority Date: 05/18/2012
• Status: Active Grant

• Current Assignee: Splunk Inc.
• Original Assignee: Splunk Inc.
• Inventors: Marquardt, David Ryan, Blank, Jr., Mitchell Neuman, Sorkin, Stephen Phillip
• Primary Examiner(s): LE, THU NGUYET T
• Application Number:
  US13/662,984
• Publication Number:
  US 20130311438A1
• Time in Patent Office: 1,772 Days
• Field of Search: 707609, 707802, 707713, 707715, 707755
• 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 comprising:

providing a datastore comprising a plurality of time-stamped, searchable events, each event having a portion of raw data and a timestamp extracted from the portion of raw data, the portion of raw data produced by at least one hardware system;

providing a data structure that contains a plurality of field names, each field name among the plurality of field names associated with a set of pointers to time-stamped, searchable events having a value for a field referred to by the field name;

receiving an incoming search query that references one or more field names among the plurality of field names contained in the data structure and a time range criteria; and

in response to the incoming search query, servicing the incoming search query by;

(i) executing the incoming search query across the data structure, wherein one or more values from the data structure are used to create a search result; and

(ii) supplementing the search result by executing a search comprising the time range criteria of the incoming search query across the time-stamped searchable events, independent of the data structure.

2. The method of claim 1, further comprising:

determining that the incoming search query comprises an aggregation function;

identifying at least one field name in the data structure that is associated with the aggregation function;

determining a result based on field values in the data structure; and

causing display of the result.

3. The method of claim 1, further comprising sorting the pointers in each set of pointers associated with a field name based on a stored position of the associated time-stamped, searchable events in the datastore.

4. The method of claim 1, further comprising:

identifying a plurality of pointers associated with the one or more field names among the plurality of field names.

5. The method of claim 1, wherein the field referred to by the field name is defined by an extraction rule, and further comprising extracting the field value for the field from the raw machine data in the time-stamped, searchable event using the extraction rule.

6. The method of claim 1, wherein a field referred to by a field name is defined by an extraction rule in a configuration file having a plurality of extraction rules that define fields.

7. The method of claim 1, wherein a field referred to by a field name is defined by an extraction rule in a configuration file having a plurality of extraction rules that define fields, wherein the extraction rule is a regular expression.

8. The method of claim 1, wherein one or more incoming search queries is serviced without querying the datastore.

9. The method of claim 1, further comprising:

searching raw data in time-stamped, searchable events referred to by pointers associated with the referenced one or more field names.

10. The method of claim 1, further comprising:

while creating the data structure, searching the time-stamped searchable events for a value for a field using an extraction rule.

11. A network device 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;

providing a datastore comprising a plurality of time-stamped, searchable events, each event having a portion of raw data and a timestamp extracted from the portion of raw data, the portion of raw data produced by at least one hardware system;

providing a data structure that contains a plurality of field names, each field name among the plurality of field names associated with a set of pointers to time-stamped, searchable events having a value for a field referred to by the field name;

receiving an incoming search query that references one or more field names among the plurality of field names contained in the data structure and a time range criteria; and

in response to the incoming search query, servicing the incoming search query by;

(i) executing the incoming search query across the data structure, wherein one or more values from the data structure are used to create a search result; and

(ii) supplementing the search result by executing a search comprising the time range criteria of the incoming search query across the time-stamped searchable events, independent of the data structure.

12. The network device of claim 11, wherein the actions further comprise:

determining that the incoming search query comprises an aggregation function;

identifying at least one field name in the data structure that is associated with the aggregation function;

determining a result based on field values in the data structure; and

causing display of the result.

13. The network device of claim 11, wherein the processor device is further operative to execute instructions that enable actions, comprising:

sorting the pointers in each set of pointers associated with a field name based on a stored position of the associated time-stamped, searchable events in the datastore.

14. The network device of claim 11, wherein the actions further comprise:

identifying a plurality of pointers associated with the one or more field names among the plurality of field names.

15. The network device of claim 11, wherein the field referred to by the field name is defined by an extraction rule, and the actions further comprise extracting the field value for the field from the raw machine data in the time-stamped, searchable event using the extraction rule.

16. The network device of claim 11, wherein a field referred to by a field name is defined by an extraction rule in a configuration file having a plurality of extraction rules that define fields.

17. The network device of claim 11, wherein a field referred to by a field name is defined by an extraction rule in a configuration file having a plurality of extraction rules that define fields, wherein the extraction rule is a regular expression.

18. The network device of claim 11, one of or more incoming search queries is serviced without querying the datastore.

19. The network device of claim 11, wherein the actions further comprise:

searching raw data in time-stamped, searchable events referred to by pointers associated with the referenced one or more field names.

20. The network device of claim 11, further comprising:

while creating the data structure, searching the time-stamped searchable events for a value for a field using the extraction rule.

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

providing a datastore comprising a plurality of time-stamped, searchable events, each event having a portion of raw data and a timestamp extracted from the portion of raw data, the portion of raw data produced by at least one hardware system;

providing a data structure that contains a plurality of field names, each field name among the plurality of field names associated with a set of pointers to time-stamped, searchable events having a value for a field referred to by the field name;

receiving an incoming search query that references one or more field names among the plurality of field names contained in the data structure and a time range criteria; and

in response to the incoming search query, servicing the incoming search query by;

(i) executing the incoming search query across the data structure, wherein one or more values from the data structure are used to create a search result; and

(ii) supplementing the search result by executing a search comprising the time range criteria of the incoming search query across the time-stamped searchable events, independent of the data structure.

22. The media of claim 21, wherein the actions further comprise:

determining that the incoming search query comprises an aggregation function;

identifying at least one field name in the data structure that is associated with the aggregation function;

determining a result based on field values in the data structure; and

causing display of the result.

23. The media of claim 21, wherein the actions further comprise sorting the pointers in each set of pointers associated with a field name based on a stored position of the associated time-stamped, searchable events in the datastore.

24. The media of claim 21, wherein the actions further comprise:

identifying a plurality of pointers associated with the one or more field names among the plurality of field names.

25. The media of claim 21, wherein the field referred to by the field name is defined by an extraction rule, and further comprising extracting the field value for the field from the raw machine data in the time-stamped, searchable event using the extraction rule.

26. The media of claim 21, wherein a field referred to by a field name is defined by an extraction rule in a configuration file having a plurality of extraction rules that define fields.

27. The media of claim 21, wherein a field referred to by a field name is defined by an extraction rule in a configuration file having a plurality of extraction rules that define fields, wherein the extraction rule is a regular expression.

28. The media of claim 21, wherein one or more incoming search queries is serviced without querying the datastore.

29. The media of claim 21, further comprising:

searching raw data in time-stamped, searchable events referred to by pointers associated with the referenced one or more field names.

30. The media of claim 21, further comprising:

while creating the data structure, searching the time-stamped searchable events for a value for a field using an extraction rule.