# US 12,118,041 B2 · Query execution on compressed in-memory data > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,118,041 B2 - Document ID: US12118041B2 - Status: Granted - Kind: B2 - Application number: 17/069,162 - Filed: 2020-10-13 - Published: 2021-04-15 - Granted: 2024-10-15 - Earliest claimed: 2019-10-13 - Assignees: ThoughtSpot, Inc. - Applicants: ThoughtSpot, Inc. - Inventors: Satyam Shekhar; Prateek Gaur; Amit Prakash; Abhishek Rai - Web page: https://patentgrep.com/patent/US12118041B2 ## CPC - G06F 16/2282: {Tablespace storage structures; Management thereof} - G06F 16/90335: {Query processing} - G06F 3/0608: {Saving storage space on storage systems} - G06F 3/0613: {in relation to throughput} - G06F 3/0631: {by allocating resources to storage systems} - G06F 3/064: {Management of blocks} - G06F 3/0673: {Single storage device} - G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Query execution on compressed in-memory data includes receiving, at a processor of an instance of a distributed in-memory database, a query for data from a table stored in the distributed in-memory database as compressed table data, obtaining results data responsive to the query from the table, and outputting the results data for presentation to a user. Obtaining results data includes allocating memory to identify allocated memory for decompressing the compressed table data, obtaining uncompressed table data by decompressing the compressed table data into the allocated memory, and obtaining the results data from the uncompressed table data. The allocated memory is deallocated in response to obtaining the results data. Compressing a table to form compressed table data is also described. ## Claims ### Claim 1 An apparatus for query execution on compressed in-memory data, comprising: a processor of an instance of a distributed in-memory database, the processor configured to: receive a query for data from a table stored in the distributed in-memory database as compressed table data; obtain results data responsive to the query from the table by: subsequent to receiving the query, allocating memory for decompressing the compressed table data; obtaining uncompressed table data by decompressing the compressed table data into the allocated memory based on a database schema of the distributed in-memory database by decompressing the compressed table data in response to a determination that the database schema indicates that the compressed table data corresponds to a fact table, wherein, to obtain the uncompressed table data, the processor is configured to decompress at least a subset of the compressed table data into a first temporary buffer of the allocated memory; and obtaining the results data from the uncompressed table data, wherein to obtain the results data, the processor is configured to access the first temporary buffer; and in response to obtaining the results data, deallocate the allocated memory; and output the results data for presentation to a user. ### Claim 2 (depends on 1) The apparatus of claim 1, wherein: the table comprises a set of rows within a column, the compressed table data comprises multiple compressed table data portions, each of the multiple compressed table data portions comprises a proper subset of the set of rows, and each proper subset is compressed independently of each other. ### Claim 3 (depends on 2) The apparatus of claim 2, wherein each proper subset comprises a same number of rows. ### Claim 4 (depends on 2) The apparatus of claim 2, wherein the table comprises multiple columns, and data values of each proper subset within a respective column are independently compressed based on a data type of the data values. ### Claim 5 (depends on 4) The apparatus of claim 4, wherein the processor is further configured to identify the data type based on a column type of the respective column, wherein the column type of a respective column comprises one of a measure column or a string column. ### Claim 6 (depends on 4) The apparatus of claim 4, wherein the processor is configured to decompress the compressed table data by: decompressing the data values using at least one of dictionary coding or variable-length coding based on the data type. ### Claim 7 (depends on 1) The apparatus of claim 1, wherein the processor is configured to decompress the compressed table data by: decompressing data values of the compressed table data that have a data type of measure data using variable-length coding; and decompressing data values of the compressed table data that have a data type of string data using at least one of dictionary coding or variable-length coding. ### Claim 8 (depends on 7) The apparatus of claim 7, wherein the processor is configured to decompress a dictionary for the dictionary coding using variable-length coding. ### Claim 9 (depends on 1) The apparatus of claim 1, wherein: the table comprises a set of rows within a column, the compressed table data comprises at least a first compressed table data portion and a second compressed table data portion compressed independently of each other, a first proper subset of the set of rows is stored as the first compressed table data portion, a second proper subset of the set of rows is stored as the second compressed table data portion, and the processor is configured to: obtain the uncompressed table data comprising the first proper subset by decompressing the first compressed table data portion into a first temporary buffer of the allocated memory; obtain intermediate results data from the first proper subset by accessing respective rows of the first proper subset according to the query; subsequent to obtaining the intermediate results data from the first proper subset: obtain the uncompressed table data comprising the second proper subset by decompressing the second compressed table data portion into the first temporary buffer of the allocated memory, replacing the uncompressed table data comprising the first proper subset; and obtain intermediate results data from the second proper subset by accessing respective rows of the second proper subset according to the query; obtain the results data from the uncompressed table data using the intermediate results data from the first proper subset and the intermediate results data from the second proper subset. ### Claim 10 (depends on 9) The apparatus of claim 9, wherein the query causes the processor to sequentially access all rows of the first proper subset and all rows of the second proper subset. ### Claim 11 (depends on 1) The apparatus of claim 1, wherein: the table comprises multiple columns, a first column is stored as multiple, independently-compressed first compressed table data portions, each comprising a compressed proper subset of rows within the first column, a second column is stored as multiple, independently-compressed second compressed table data portions, each comprising a compressed proper subset of rows within the second column, and the processor is configured to: obtain the uncompressed table data by decompressing the second compressed table data portions into a second temporary buffer of the allocated memory, wherein the subset includes the first compressed table data portions; and obtain the results data from the uncompressed table data by accessing the second temporary buffer. ### Claim 12 (depends on 11) The apparatus of claim 11, wherein the query causes the processor to non-sequentially access rows within the first column and rows within the second column. ### Claim 13 A method of query execution on compressed in-memory data, comprising: receiving, at a processor of an instance of a distributed in-memory database, a query for data from a table stored in the distributed in-memory database as compressed table data; obtaining results data responsive to the query from the table by: subsequent to receiving the query, allocating memory for decompressing the compressed table data; obtaining uncompressed table data by decompressing the compressed table data into the allocated memory based on a database schema of the distributed in-memory database by decompressing the compressed table data in response to a determination that the database schema indicates that the compressed table data corresponds to a fact table, wherein, obtaining the uncompressed table data includes decompressing at least a subset of the compressed table data into a first temporary buffer of the allocated memory; and obtaining the results data from the uncompressed table data, wherein obtaining the results data includes accessing the first temporary buffer; and in response to obtaining the results data, deallocating the allocated memory; and outputting the results data for presentation to a user. ### Claim 14 (depends on 13) The method of claim 13, wherein: the table comprises a set of rows, the compressed table data comprises multiple compressed table data portions compressed independently of each other, each of a plurality of proper subsets of the set of rows is stored as a respective compressed table data portion of the multiple compressed table data portions, and decompressing the compressed table data into the allocated memory comprises independently decompressing each of the compressed table data portions to obtain uncompressed table data portions. ### Claim 15 (depends on 14) The method of claim 14, further comprising: responsive to decompressing a compressed table data portion, changing an identifier to indicate that the compressed table data portion has been accessed by the query. ### Claim 16 (depends on 14) The method of claim 14, obtaining the results data from the uncompressed table data comprises: determining intermediate results data from each of the uncompressed table data portions; and applying a logical operator or a mathematical operator to the intermediate results data to obtain the results data. ### Claim 17 (depends on 14) The method of claim 14, obtaining the results data from the uncompressed table data comprises: determining intermediate results data from each of the uncompressed table data portions; and aggregating the intermediate results data to obtain the results data. ### Claim 18 An apparatus for compressing table data for query execution on compressed in-memory data, comprising: a processor of an instance of a distributed in-memory database configured to: receive, at the instance, a table, wherein the table comprises a plurality of columns and a set of rows; determine a table type of the table according to a database schema of the distributed in-memory database; responsive to the table type determined to be a fact table, compress the table to generate compressed table data, wherein the processor is configured to compress the table by: dividing the sets of rows into proper subsets of rows; determining a data type for each column of the plurality of columns; and for each column of the plurality of columns, independently compressing rows of the proper subsets of rows sharing the column independently from compressing rows of the proper subsets of rows sharing remaining columns of the plurality of columns, a compression technique used for the compressing based on the data type of the column; and store the compressed table data as the compressed in-memory data. ### Claim 19 (depends on 18) The apparatus of claim 18, wherein independently compressing the rows comprises: compressing data values of the rows using at least one of dictionary coding or variable-length coding based on the data type.