Granted Patent B2

US 10,866,940 · App. 15/164,287 · Granted Dec 15, 2020

Inventors: Sattam Alsubaiee (Riyadh, SA); Vinayak Borkar (San Jose, CA)

Assignee: FireEye, Inc.

G06F16/221G06F16/81G06F16/86

Abstract

Claims (95)

1. A method executed by one or more computing devices for efficiently transforming, without prior knowledge of a schema, non-columnar semi-structured data into a columnar format that is able to be queried, the method comprising:

storing, by at least one of the one or more computing devices, a current schema corresponding to any previously parsed data records in a current row group, wherein the current schema comprises one or more current fields having one or more corresponding current data types and wherein the one or more current fields and the one or more corresponding current data types are based on any previously parsed data records in the current row group;

parsing, by at least one of the one or more computing devices, a new data record, wherein the new data record comprises semi-structured data including one or more data fields and one or more data values corresponding to the one or more data fields;

generating, by at least one of the one or more computing devices, a new schema corresponding to the new data record based on the parsed new data record, wherein the new schema comprises the one or more data fields and one or more data types corresponding to the one or more data fields;

determining, by at least one of the one or more computing devices, whether the new schema corresponding to the new data record is homogenous with the current schema corresponding to any previously parsed data records in the current row group by comparing the one or more data fields and the one or more data types to the one or more current fields and the one or more current data types, wherein the new schema is homogenous with the current schema when there is no data field that matches a current data field while having a corresponding data type that is different than a corresponding current data type; and

storing, by at least one of the one or more computing devices, the data record as a new record in the current row group based at least in part on a determination that the schema corresponding to the data record is homogenous with the schema corresponding to a current row group, wherein the current row group comprises a set of rows stored in a columnar format that is able to be queried, the set of rows being organized in one or more columns corresponding to the one or more data fields and having one or more column types corresponding to the one or more data types.

2. The method of claim 1 , wherein the current row group has a maximum size and wherein storing the data record as a new record in the current row group comprises:

storing the data record in the current row group based at least in part on a determination that the schema corresponding to the data record is homogenous with the current schema and a determination that a combined size of the current row group and the data record does not exceed a maximum size.

3. The method of claim 1 , further comprising:

generating, by at least one of the one or more computing devices, a new row group based at least in part on a determination that the schema corresponding to the data record is not homogenous with the current schema, wherein the new row group comprises a second set of rows stored in a columnar format that is able to be queried, the second set of rows being organized in one or more new columns corresponding to the one or more fields and one or more new column types corresponding to the one or more data types;

updating by at least one of the one or more computing devices, the current schema to correspond to the new schema corresponding to the data record; and

storing, by at least one of the one or more computing devices, the data record as a new record in the new row group.

4. The method of claim 1 , further comprising:

identifying, by at least one of the one or more computing devices, at least one new field in the one or more data fields which does not appear in the one or more current fields; and

updating, by at least one of the one or more computing devices, the current schema to include the at least one new field and at least one new field type corresponding to the at least one new field.

5. The method of claim 4 , wherein the current row group comprises one or more column chunks corresponding to the one or more columns and wherein storing the data record as a new record in the current row group comprises:

adding, by at least one of the one or more computing devices, at least one column chunk corresponding to the at least one new field to the one or more column chunks in the current row group;

storing, by at least one of the one or more computing devices, the one or more data values in corresponding column chunks in the one or more column chunks; and

storing, by at least one of the one or more computing devices, a NULL value in the at least one new column chunk for any existing records in the current row group.

6. The method of claim 5 , wherein storing the data record as a new record in the current row group further comprises:

identifying, by at least one of the one or more computing devices, at least one missing field corresponding to at least one current field in the one or more current fields which does not appear in the one or more data fields; and

storing, by at least one of the one or more computing devices, a NULL value in at least one column chunk corresponding to the at least one missing field for the new record.

7. The method of claim 1 , wherein the current row group comprises one or more column chunks, wherein the data record comprises one or more entries, and further comprising:

encoding, by at least one of the one or more computing devices, repetition and definition levels of the one or more entries for each column chunk in the one or more column chunks.

8. The method of claim 1 , further comprising:

determining, by at least one of the one or more computing devices, whether the new schema corresponding to the data record is homogenous with a previous schema corresponding to a previous row group stored in a buffer, wherein the buffer stores one or more previous row groups which have not reached a predetermined size threshold; and

storing, by at least one of the one or more computing devices, the data record as a new record in the previous row group based at least in part on a determination that the new schema corresponding to the data record is homogenous with the schema corresponding to the previous row group.

9. The method of claim 1 , further comprising:

receiving, by at least one of the one or more computing devices, a query identifying one or more query data fields and one or more corresponding query data types;

identifying, by at least one of the one or more computing devices, a schema in one or more schemas which is homogenous with the one or more query data fields and the one or more corresponding query data types, wherein the identified schema has a corresponding row group; and

executing, by at least one of the one or more computing devices, the query on the corresponding row group to return data responsive to the query.

10. An apparatus for efficiently transforming, without prior knowledge of a schema, non-columnar semi-structured data into a columnar format that is able to be queried, the apparatus comprising:

one or more processors; and

one or more memories operatively coupled to at least one of the one or more processors and having instructions stored thereon that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to:

store a current schema corresponding to any previously parsed data records in a current row group, wherein the current schema comprises one or more current fields having one or more corresponding current data types and wherein the one or more current fields and the one or more corresponding current data types are based on any previously parsed data records in the current row group;

parse a new data record, wherein the new data record comprises semi-structured data including one or more data fields and one or more data values corresponding to the one or more data fields;

generate a new schema corresponding to the new data record based on the parsed new data record, wherein the new schema comprises the one or more data fields and one or more data types corresponding to the one or more data fields;

determine whether the new schema corresponding to the new data record is homogenous with the current schema corresponding to any previously parsed data records in the current row group by comparing the one or more data fields and the one or more data types to the one or more current fields and the one or more current data types, to a current row group, wherein the new schema is homogenous with the current schema when there is no data field that matches a current data field while having a corresponding data type that is different than a corresponding current data type; and

store the data record as a new record in the current row group based at least in part on a determination that the schema corresponding to the data record is homogenous with the schema corresponding to a current row group, wherein the current row group comprises a set of rows stored in a columnar format that is able to be queried, the set of rows being organized in one or more columns corresponding to the one or more data fields and having one or more column types corresponding to the one or more data types.

11. The apparatus of claim 10 , wherein the current row group has a maximum size and wherein the instructions that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to store the data record as a new record in the current row group further cause at least one of the one or more processors to:

store the data record in the current row group based at least in part on a determination that the schema corresponding to the data record is homogenous with the current schema and a determination that a combined size of the current row group and the data record does not exceed a maximum size.

12. The apparatus of claim 10 , wherein at least one of the one or more memories has further instructions stored thereon that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to:

generate a new row group based at least in part on a determination that the schema corresponding to the data record is not homogenous with the current schema, wherein the new row group comprises a second set of rows stored in a columnar format that is able to be queried, the second set of rows being organized in one or more new columns corresponding to the one or more fields and one or more new column types corresponding to the one or more data types;

update the current schema to correspond to the new schema corresponding to the data record; and

store the data record as a new record in the new row group.

13. The apparatus of claim 10 , wherein at least one of the one or more memories has further instructions stored thereon that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to:

identify at least one new field in the one or more data fields which does not appear in the one or more current fields; and

update the current schema to include the at least one new field and at least one new field type corresponding to the at least one new field.

14. The apparatus of claim 13 , wherein the current row group comprises one or more column chunks corresponding to the one or more columns and wherein the instructions that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to store the data record as a new record in the current row group further cause at least one of the one or more processors to:

add at least one column chunk corresponding to the at least one new field to the one or more column chunks in the current row group;

store the one or more data values in corresponding column chunks in the one or more column chunks; and

store a NULL value in the at least one new column chunk for any existing records in the current row group.

15. The apparatus of claim 14 , wherein the instructions that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to store the data record as a new record in the current row group further cause at least one of the one or more processors to:

identify at least one missing field corresponding to at least one current field in the one or more current fields which does not appear in the one or more data fields; and

store a NULL value in at least one column chunk corresponding to the at least one missing field for the new record.

16. The apparatus of claim 10 , wherein the current row group comprises one or more column chunks, wherein the data record comprises one or more entries, and wherein at least one of the one or more memories has further instructions stored thereon that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to:

encode repetition and definition levels of the one or more entries for each column chunk in the one or more column chunks.

17. The apparatus of claim 10 , wherein at least one of the one or more memories has further instructions stored thereon that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to:

determine whether the new schema corresponding to the data record is homogenous with a previous schema corresponding to a previous row group stored in a buffer, wherein the buffer stores one or more previous row groups which have not reached a predetermined size threshold; and

store the data record as a new record in the previous row group based at least in part on a determination that the new schema corresponding to the data record is homogenous with the schema corresponding to the previous row group.

18. The apparatus of claim 10 , wherein at least one of the one or more memories has further instructions stored thereon that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to:

receive a query identifying one or more query data fields and one or more corresponding query data types;

identify a schema in one or more schemas which is homogenous with the one or more query data fields and the one or more corresponding query data types, wherein the identified schema has a corresponding row group; and

execute the query on the corresponding row group to return data responsive to the query.

19. At least one non-transitory computer-readable medium storing computer-readable instructions that, when executed by one or more computing devices, cause at least one of the one or more computing devices to:

store a current schema corresponding to any previously parsed data records in a current row group, wherein the current schema comprises one or more current fields having one or more corresponding current data types and wherein the one or more current fields and the one or more corresponding current data types are based on any previously parsed data records in the current row group;

parse a new data record, wherein the new data record comprises semi-structured data including one or more data fields and one or more data values corresponding to the one or more data fields;

generate a new schema corresponding to the new data record based on the parsed new data record, wherein the new schema comprises the one or more data fields and one or more data types corresponding to the one or more data fields;

determine whether the new schema corresponding to the new data record is homogenous with the current schema corresponding to any previously parsed data records in the current row group by comparing the one or more data fields and the one or more data types to the one or more current fields and the one or more current data types, wherein the new schema is homogenous with the current schema when there is no data field that matches a current data field while having a corresponding data type that is different than a corresponding current data type; and

store the data record as a new record in the current row group based at least in part on a determination that the schema corresponding to the data record is homogenous with the schema corresponding to a current row group, wherein the current row group comprises a set of rows stored in a columnar format that is able to be queried, the set of rows being organized in one or more columns corresponding to the one or more data fields and having one or more column types corresponding to the one or more data types.

20. The at least one non-transitory computer-readable medium of claim 19 , wherein the current row group has a maximum size and wherein the instructions that, when executed by at least one of the one or more computing devices, cause at least one of the one or more computing devices to store the data record as a new record in the current row group further cause at least one of the one or more computing devices to:

store the data record in the current row group based at least in part on a determination that the schema corresponding to the data record is homogenous with the current schema and a determination that a combined size of the current row group and the data record does not exceed a maximum size.

21. The at least one non-transitory computer-readable medium of claim 19 , further storing computer-readable instructions that, when executed by at least one of the one or more computing devices, cause at least one of the one or more computing devices to:

generate a new row group based at least in part on a determination that the schema corresponding to the data record is not homogenous with the current schema, wherein the new row group comprises a second set of rows stored in a columnar format that is able to be queried, the second set of rows being organized in one or more new columns corresponding to the one or more fields and one or more new column types corresponding to the one or more data types;

update the current schema to correspond to the new schema corresponding to the data record; and

store the data record as a new record in the new row group.

22. The at least one non-transitory computer-readable medium of claim 19 , further storing computer-readable instructions that, when executed by at least one of the one or more computing devices, cause at least one of the one or more computing devices to:

identify at least one new field in the one or more data fields which does not appear in the one or more current fields; and

update the current schema to include the at least one new field and at least one new field type corresponding to the at least one new field.

23. The at least one non-transitory computer-readable medium of claim 22 , wherein the current row group comprises one or more column chunks corresponding to the one or more columns and wherein the instructions that, when executed by at least one of the one or more computing devices, cause at least one of the one or more computing devices to store the data record as a new record in the current row group further cause at least one of the one or more computing devices to:

add at least one column chunk corresponding to the at least one new field to the one or more column chunks in the current row group;

store the one or more data values in corresponding column chunks in the one or more column chunks; and

store a NULL value in the at least one new column chunk for any existing records in the current row group.

24. The at least one non-transitory computer-readable medium of claim 23 , wherein the current row group comprises one or more column chunks, wherein the data record comprises one or more entries, and wherein the instructions that, when executed by at least one of the one or more computing devices, cause at least one of the one or more computing devices to store the data record as a new record in the current row group further cause at least one of the one or more computing devices to:

identify at least one missing field corresponding to at least one current field in the one or more current fields which does not appear in the one or more data fields; and

store a NULL value in at least one column chunk corresponding to the at least one missing field for the new record.

25. The at least one non-transitory computer-readable medium of claim 19 , further storing computer-readable instructions that, when executed by at least one of the one or more computing devices, cause at least one of the one or more computing devices to:

encode repetition and definition levels of the one or more entries for each column chunk in the one or more column chunks.

26. The at least one non-transitory computer-readable medium of claim 19 , further storing computer-readable instructions that, when executed by at least one of the one or more computing devices, cause at least one of the one or more computing devices to:

determine whether the new schema corresponding to the data record is homogenous with a previous schema corresponding to a previous row group stored in a buffer, wherein the buffer stores one or more previous row groups which have not reached a predetermined size threshold; and

store the data record as a new record in the previous row group based at least in part on a determination that the new schema corresponding to the data record is homogenous with the schema corresponding to the previous row group.

27. The at least one non-transitory computer-readable medium of claim 19 , further storing computer-readable instructions that, when executed by at least one of the one or more computing devices, cause at least one of the one or more computing devices to:

receive a query identifying one or more query data fields and one or more corresponding query data types;

identify a schema in one or more schemas which is homogenous with the one or more query data fields and the one or more corresponding query data types, wherein the identified schema has a corresponding row group; and

execute the query on the corresponding row group to return data responsive to the query.

Assignments (14)

Continuity (2)

Cited By (1)

US 12,531,575