Back to results
US 12,182,079 B1Granted
System and method for storing and reading a database on flash memory or other degradable storage
AssigneeYellowbrick Data, Inc.
InventorJim Peterson
Life of this patent
Estimating the term…
Abstract
A system and method stores a database file into Flash memory or other write-constrained storage. The system and method can decompress the data to use to process a request by only decompressing data it determines, via metadata, might correspond to a criteria in the request.
Claims18
A computer-implemented method of providing portions of a computer database file, the method comprising:
- (A) providing, by at least one hardware processor, in computer storage at least a part of the computer database file as a set of a plurality of buffers, each buffer in the plurality of buffers containing a variable number of one or more compression units, at least one compression unit of the one or more compression units containing a number of rows of at least one column of the computer database file, each compression unit of the one or more compression units in a given buffer corresponding to a same at least one column of the computer database file as any other at least one compression unit in said given buffer, each said buffer having an ending row that corresponds to a largest-indexed row of at least one column held by said buffer, the computer database file comprising a plurality of the rows and a plurality of columns;
- (B) providing in the computer storage, by the at least one hardware processor, metadata for each said buffer in the at least the part of the computer database file;
- (C) identifying, by the at least one hardware processor, the plurality of columns that are applicable to a request;
- (D) selecting, by the at least one hardware processor, an analysis point that is one row before a beginning row of the at least the part of the computer database file;
- (E) selecting, by the at least one hardware processor, one buffer of the plurality of buffers for each column applicable to the request that contains one of the plurality of rows immediately following the analysis point;
- (F) using, by the at least one hardware processor, the metadata for the selected one buffer for each column applicable to the request and a criteria to determine whether the criteria either (i) cannot be met, or (ii) can be met by data in the computer database file by comparing the data in the computer database file corresponding to the selected one buffer for each column applicable to the request;
- (G) responsive to a determination that the criteria can be met by the data in the computer database file corresponding to the selected one buffer for each column applicable to the request, adding, by the at least one hardware processor, to a list of applicable rows, a range having a beginning row immediately following the analysis point and an ending row equal to a smallest-indexed ending row among the selected one buffer for each column applicable to the request, and moving the analysis point to the ending row of the added range;
- (H) identifying, by the at least one hardware processor, the analysis point as the ending row of the added range and, responsive to a determination that the criteria cannot be met by the data in the computer database file corresponding to the selected one buffer for each column applicable to the request, moving the analysis point to the largest ending row among the selected one buffer for each column applicable to the request;
- (I) repeating, by the at least one hardware processor, a plurality of times, steps E-H using the analysis point most recently selected in steps G or H;
- (J) receiving, by the at least one hardware processor, identifiers of the compression units corresponding to at least some of the ranges of the list of applicable rows and the plurality of columns that are applicable to the request and decompressing at least some of the compression units corresponding to the identifiers of the compression units and to the list of applicable rows for each column of the plurality of columns that are applicable to the request;
- and
- (K) providing, by the at least one hardware processor, at least a portion of each decompressed compression unit of the decompressed compression units.
9 more elements
A system for providing portions of a computer database file, comprising a database comprising a plurality of rows and a plurality of columns, the system comprising:
- a computer storage for providing at an output at least a part of the computer database file as a set of a plurality of buffers, each buffer in the plurality of buffers containing a variable number of one or more compression units, at least one of the compression units containing a number of the rows of at least one of the columns of the computer database file, each compression unit of the one or more compression units in a given buffer of the plurality corresponding to a same at least one column of the computer database file as any other at least one compression unit in said given buffer, each said buffer in the plurality of buffers having an ending row that corresponds to a largest-indexed row of the at least one column held by said buffer, the computer storage additionally for providing at the computer storage output metadata for each said buffer in the at least the part of the computer database file, and for providing at the computer storage output information of each column of the plurality of columns;
- an applicable column analyzer having an input for receiving a criteria and coupled to the computer storage output for receiving the information of each said column of the plurality of columns, the applicable column analyzer for providing at an output identifiers of the plurality of columns that are applicable to a request;
- a buffer metadata analyzer comprising a hardware computer processor and having an input coupled for receiving the criteria, coupled to the applicable column analyzer output for receiving the identifiers of the plurality of columns that are applicable to the request, and coupled the computer storage output for receiving the metadata for each said buffer corresponding to the identifiers of the plurality of columns that are applicable to the request, the buffer metadata analyzer for:
- selecting an analysis point that is one row before a beginning row of the at least the part of the computer database file,
- selecting one buffer of the plurality of buffers for each column in the plurality applicable to the criteria that contains one of the plurality of rows immediately following the analysis point,
- using the metadata for the selected one buffer for each column applicable to the request and the criteria to determine whether the criteria either (i) cannot be met, or (ii) can be met by data in the computer database file corresponding to the selected one buffer of the plurality of buffers for each column in the plurality applicable to the criteria, and responsive to a determination that the criteria can be met by the data in the computer database file corresponding to the selected one buffer for each column applicable to the request, providing at an output to an input of an applicable list manager that adds it via an output of the applicable list manager to a list of applicable rows, a range having a beginning row immediately following the analysis point and an ending row equal to a smallest-indexed ending row among the selected one buffer for each column applicable to the request and moving the analysis point to the ending row of the added range, thereby identifying the analysis point as the ending row of the added range and
- responsive to a determination that the criteria cannot be met by the data in the computer database file corresponding to the selected one buffer for each column applicable to the request, identifying the analysis point as a largest-indexed ending row among the selected one buffer of the plurality of buffers for each column in the plurality applicable to the criteria buffers and
- repeating an operation, starting from the selecting the one buffer of the plurality of buffers for each column, using the newly selected analysis point;
- and
- a decompression manager having an input for receiving identifiers of compression units corresponding to at least some of the ranges of the list of applicable rows and the plurality of the columns that are applicable to the request, and to the computer storage output for receiving the compression units corresponding to said identifiers, the decompression manager for decompressing at least some of the compression units corresponding to the identifiers of the compression units and to the list of applicable rows for each column of the plurality of columns that are applicable to the request and for providing at an output at least a portion of each decompressed compression unit of the decompressed compression units.
7 more elements
The system of 7, wherein:
- each compression unit is at least partly compressed;
- and
- the decompression manager decompresses at least a part of at least one of the at least some of the compression units responsive to a dictionary that applies to less than all of the at least one column corresponding to said at least one compression unit.
A computer program product embodied in a nontransitory computer useable medium having computer readable program code for providing portions of a computer database file, the computer program product comprising computer readable program code devices configured to cause a computer system to:
- (A) provide at least a part of the computer database file as a set of a plurality of buffers, each buffer in the plurality of buffers containing a variable number of one or more compression units, at least one compression unit of the one or more compression units containing a number of rows of at least one column of the computer database file, each said compression unit of the one or more compression units in a given buffer corresponding to a same at least one column of the computer database file as any other at least one compression unit in said given buffer, each said buffer having an ending row that corresponds to largest-indexed row of at least one column held by said buffer, the computer database file comprising a plurality of the rows and a plurality of columns;
- (B) provide in the computer storage metadata for each said buffer in the at least the part of the computer database file;
- (C) identify the plurality of columns that are applicable to a request;
- (D) select an analysis point that is one row before a beginning row of the at least the part of the computer database file;
- (E) select one buffer of the plurality of buffers for each column applicable to the request that contains one of the plurality of rows immediately following the analysis point;
- (F) use the metadata for the selected one buffer for each column applicable to the request and a criteria to determine whether the criteria either (i) cannot be met, or (ii) can be met by data in the computer database file by comparing the data in the computer database file corresponding to the selected one buffer for each column applicable to the request;
- (G) responsive to a determination that the criteria can be met by the data in the computer database file corresponding to the selected one buffer for each column applicable to the request, add to a list of applicable rows, a range having a beginning row immediately following the analysis point and an ending row equal to a smallest-indexed ending row among the selected one buffer for each column applicable to the request, and move the analysis point to the ending row of the added range;
- (H) identify the analysis point as the ending row of the added range and, responsive to a determination that the criteria cannot be met by the data in the computer database file corresponding to the selected one buffer for each column applicable to the request, move the analysis point to the largest ending row among the selected one buffer for each column applicable to the request;
- (I) repeat, a plurality of times, operation of the computer readable program code devices E-H using the analysis point most recently selected by computer readable code devices G or H;
- (J) receive identifiers of compression units corresponding to at least some of at least one of the ranges of the list of applicable rows and the plurality of columns that are applicable to the request and decompress at least some of the compression units corresponding to the list of applicable rows for each column of the plurality of columns that are applicable to the request;
- and
- (K) provide at least a portion of each decompressed compression unit of the decompressed compression units.
9 more elements
Dependencies are inferred from the claim text.