Method, apparatus, and computer-readable medium for encoding repetition and definition level values for semi-structured data

Abstract

An apparatus, computer-readable medium, and computer-implemented method for encoding repetition and definition level values for a semi-structured data record, including identifying a leaf of an entry in a data record, the entry specifying one or more data fields in the data record and the leaf corresponding to a last data field in the entry, storing a value of the leaf in a column which corresponds to a nesting path of the leaf within the data record, the column being in a current row group, determining a repetition level of the entry for the column, determining a definition level of the entry for the column based at least in part on a nesting level of the leaf in the data record, and storing the repetition level and definition level of the entry for the column in a table of repetition and definition levels for the current row group.

What is claimed is: 
     
         1 . A method executed by one or more computing devices for encoding repetition and definition level values for a semi-structured data record while storing the semi-structured data in columnar format, the method comprising:
 identifying, by at least one of the one or more computing devices, a leaf of an entry in a data record, wherein the entry specifies one or more data fields in the data record and wherein the leaf corresponds to a last data field in the entry;   storing, by at least one of the one or more computing devices, a value of the leaf in a column which corresponds to a nesting path of the leaf within the data record, wherein the column is in a current row group;   determining, by at least one of the one or more computing devices, a repetition level of the entry for the column, wherein the repetition level of the entry for the column is based at least in part on a determination of whether a previous entry occurs prior to the entry in the data record and whether the previous entry includes a previous leaf which shares at least a portion of the nesting path of the leaf;   determining, by at least one of the one or more computing devices, a definition level of the entry for the column based at least in part on a nesting level of the leaf in the data record; and   storing, by at least one of the one or more computing devices, the repetition level and definition level of the entry for the column in a table of repetition and definition levels for the current row group.   
     
     
         2 . The method of  claim 1 , further comprising:
 determining, by at least one of the one or more computing devices, one or more repetition levels of the entry for one or more other columns in the current row group;   determining, by at least one of the one or more computing devices, one or more definition levels of the entry for the one or more other columns in the current row group; and   storing, by at least one of the one or more computing devices, the one or more repetition levels and the one or more definition levels of the entry for the one or more other columns in the current row group in the table of repetition and definition levels for current row group.   
     
     
         3 . The method of  claim 2 , wherein determining one or more repetition levels of the entry for the one or more other columns in the current row group comprises, for each other column in the one or more other columns:
 determining whether the entry is a first entry in the data record; and   setting a repetition level of the entry for the other column to zero based at least in part on a determination that the entry is a first entry in the data record.   
     
     
         4 . The method of  claim 2 , wherein determining one or more repetition levels of the entry for the one or more other columns in the current row group comprises, for each other column in the one or more other columns:
 determining whether the entry is a first entry in the data record; and   responsive to determining that the entry is not a first entry in the data record:
 determining a longest common prefix between one or more data fields in the other column and one or more data fields in the nesting path of the leaf; 
 determining a first data field which is common to both the entry and the longest common prefix; and 
 setting a repetition level of the entry for the other column to be a level of nesting of the first data field within the longest common prefix. 
   
     
     
         5 . The method of  claim 2 , wherein determining one or more definition levels of the entry for the one or more other columns in the current row group comprises, for each other column in the one or more other columns:
 determining a longest common prefix between one or more data fields in the other column and one or more data fields in the nesting path of the leaf;   determining a last data field of the longest common prefix; and   setting a definition level of the entry for the other column to be a level of nesting of the last data field within the longest common prefix.   
     
     
         6 . The method of  claim 1 , wherein storing a value of the leaf in a column which corresponds to a nesting path of the leaf within the data record comprises:
 determining whether a column which corresponds to a nesting path of the leaf within the data record exists in the current row group;   creating a new column in the current row group which corresponds to a nesting path of the leaf within the data record based at least in part on a determination that the column does not exist; and   storing the value of the leaf in the new column which corresponds to a nesting path of the leaf within the data record.   
     
     
         7 . The method of  claim 6 , further comprising:
 determining, by at least one of the one or more computing devices, one or more repetition levels of one or more other entries for the new column;   determining, by at least one of the one or more computing devices, one or more definition levels of the one or more other entries for the new column; and   storing, by at least one of the one or more computing devices, the one or more repetition levels and the one or more definition levels of the one or more other entries for the new column in the table of repetition and definition levels for current row group.   
     
     
         8 . The method of  claim 7 , wherein determining one or more repetition levels of one or more other entries for the new column comprises:
 comparing one or more data fields in the new column with one or more data fields in each of one or more prior columns to identify a prior column which has a longest common prefix with the new column; and   for each other entry in the one or more other entries:
 determining whether a repetition level corresponding to the other entry for the identified prior column is greater than a maximum repetition level; and 
 setting a repetition level corresponding to the other entry for the new column to be equal to the repetition level corresponding to the other entry for the identified prior column based at least in part on a determination that the repetition level corresponding to the other entry for the identified prior column is not greater than a maximum repetition level. 
   
     
     
         9 . The method of  claim 8 , wherein the maximum repetition level comprises a highest possible repetition level for a longest shared prefix between fields of the new column and fields of the identified prior column. 
     
     
         10 . The method of  claim 7 , wherein determining one or more definition levels of one or more other entries for the new column comprises:
 comparing one or more data fields in the new column with one or more data fields in each of one or more prior columns to identify a prior column which has a longest common prefix with the new column; and   for each other entry in the one or more other entries:
 determining whether a repetition level corresponding to the other entry for the identified prior column is greater than a maximum repetition level; 
 determining whether a definition level corresponding to the other entry for the identified prior column is greater than a maximum definition level; and either
 setting a definition level corresponding to the other entry for the new column to be equal to the definition level corresponding to the other entry for the identified prior column based at least in part on a determination that the definition level corresponding to the other entry for the identified prior column is not greater than a maximum definition level and a determination that the repetition level corresponding to the other entry for the identified prior column is not greater than a maximum repetition level; or 
 setting a definition level corresponding to the other entry for the new column to be equal to the maximum definition level based at least in part on a determination that the definition level corresponding to the other entry for the identified prior column is greater than a maximum definition level and a determination that the repetition level corresponding to the other entry for the identified prior column is not greater than a maximum repetition level. 
 
   
     
     
         11 . The method of  claim 8 , wherein the maximum repetition level comprises a highest possible repetition level for a longest shared prefix between fields of the new column and fields of the identified prior column and wherein the maximum definition level comprises a highest possible definition level for a longest shared prefix between fields of the new column and fields of the identified prior column. 
     
     
         12 . The method of  claim 1 , wherein identifying a leaf of an entry in a data record, wherein the entry specifies one or more data fields in the data record and wherein the leaf corresponds to a last data field in the entry comprises:
 determining whether the last field of the entry comprises a primitive data type; and   setting the last field of the entry as the leaf based at least in part on a determination that the last field of the entry comprises a primitive data type.   
     
     
         13 . The method of  claim 1 , wherein identifying a leaf of an entry in a data record, wherein the entry specifies one or more data fields in the data record and wherein the leaf corresponds to a last data field in the entry comprises:
 determining whether the last field of the entry comprises a primitive data type; and   responsive to determining that the last field of the entry does not comprise a primitive data type:
 adding a new Boolean field to the entry after the last data field; 
 setting the new Boolean field to true; and 
 setting the new Boolean field as the leaf. 
   
     
     
         14 . An apparatus for encoding repetition and definition level values for a semi-structured data record while storing the semi-structured data in columnar format, 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:
 identify a leaf of an entry in a data record, wherein the entry specifies one or more data fields in the data record and wherein the leaf corresponds to a last data field in the entry; 
 store a value of the leaf in a column which corresponds to a nesting path of the leaf within the data record, wherein the column is in a current row group; 
 determine a repetition level of the entry for the column, wherein the repetition level of the entry for the column is based at least in part on a determination of whether a previous entry occurs prior to the entry in the data record and whether the previous entry includes a previous leaf which shares at least a portion of the nesting path of the leaf; 
 determine a definition level of the entry for the column based at least in part on a nesting level of the leaf in the data record; and 
 store the repetition level and definition level of the entry for the column in a table of repetition and definition levels for the current row group. 
   
     
     
         15 . 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:
 identify a leaf of an entry in a data record, wherein the entry specifies one or more data fields in the data record and wherein the leaf corresponds to a last data field in the entry;   store a value of the leaf in a column which corresponds to a nesting path of the leaf within the data record, wherein the column is in a current row group;   determine a repetition level of the entry for the column, wherein the repetition level of the entry for the column is based at least in part on a determination of whether a previous entry occurs prior to the entry in the data record and whether the previous entry includes a previous leaf which shares at least a portion of the nesting path of the leaf;   determine a definition level of the entry for the column based at least in part on a nesting level of the leaf in the data record; and   store the repetition level and definition level of the entry for the column in a table of repetition and definition levels for the current row group.