File format for accessing data quickly and efficiently

A method comprising:

• receiving a request to create a file for storing data from a table comprising a plurality of rows, each row in the plurality of rows divided into a set of columns, each column in the set of columns configured to store a type of data;
• dividing the plurality of rows into a plurality of blocks of rows, each block of rows in the plurality of blocks of rows comprising a portion of the plurality of rows;
• for at least one column in the set of columns of each block of rows in the plurality of blocks of rows:
• encoding the data in the column of the block of rows based on the type of data stored in the column,
• storing the encoded data in the file as a page of data;
• and
• determining a minimum value and a maximum value for the data in the column of the block of rows;
• producing a set of data metadata comprising the determined minimum value and the determined maximum value for the data in the at least one column in the set of columns of each block of rows in the plurality of blocks of rows;
• generating a tree data structure for the at least one column in the set of columns using the set of data metadata, wherein each leaf node of a plurality of leaf nodes of the tree data structure stores a minimum value and a maximum value of the set of data metadata, and wherein the tree data structure is generated based on a calculation of:
• a total number of leaf nodes in the tree data structure based on a number of blocks of rows, a height of the tree data structure based on the number of blocks of rows, and a number of leaf nodes in a penultimate level of the tree data structure based on the height of the tree data structure and the number of blocks of rows;
• serializing the tree data structure;
• storing the serialized tree data structure, including the data metadata of the plurality of leaf nodes, in the file as a separate page of data.

A system comprising:

• a set of processing units;
• and
• a non-transitory machine-readable medium storing instructions that when executed by at least one processing unit in the set of processing units cause the at least one processing unit to:
• receiving a request to create a file for storing data from a table comprising a plurality of rows, each row in the plurality of rows divided into a set of columns, each column in the set of columns configured to store a type of data;
• dividing the plurality of rows into a plurality of blocks of rows, each block of rows in the plurality of blocks of rows comprising a portion of the plurality of rows;
• for at least one column in the set of columns of each block of rows in the plurality of blocks of rows:
• encode the data in the column of the block of rows based on the type of data stored in the column,
• store the encoded data in the file as a page of data;
• and
• determine a minimum value and a maximum value for the data in the column of the block of rows;
• produce a set of data metadata comprising the determined minimum value and the determined maximum value for the data in the at least one column in the set of columns of each block of rows in the plurality of blocks of rows;
• generate a tree data structure for the at least one column in the set of columns using the set of data metadata, wherein each leaf node of a plurality of leaf nodes of the tree data structure stores a minimum value and a maximum value of the set of data metadata, and wherein the tree data structure is generated based on a calculation of:
• a total number of leaf nodes in the tree data structure based on a number of blocks of rows, a height of the tree data structure based on the number of blocks of rows, and a number of leaf nodes in a penultimate level of the tree data structure based on the height of the tree data structure and the number of blocks of rows;
• serialize the tree data structure;
• store the serialized tree data structure, including the data metadata of the plurality of leaf nodes, in the file as a separate page of data.