TWI825305B - Transcoder and method and article for transcoding - Google Patents

Abstract

A transcoder, a method and an article for transcoding are disclosed. The transcoder may comprise a buffer to store input encoded data. An index mapper may map an input dictionary to an output dictionary. A current encode buffer may store a modified current encoded data, which may be responsive to the input encoded data, the input dictionary, and the map from the input dictionary to the output dictionary. A previous encode buffer may store a modified previous encoded data, which may be responsive to the input encoded data, the input dictionary, and the map from the input dictionary to the output dictionary. A rule evaluator may generate an output stream responsive to the modified current encoded data in the current encode buffer, the modified previous encoded data in the previous encode buffer, and transcoding rules.

Description

Conversion encoders and methods and products for conversion encoding

The inventive concepts generally relate to storage devices, and more specifically, to transcoding data within the storage devices.

[Relevant application information]

This application claims U.S. Provisional Patent Application No. 62/834,900 filed on April 16, 2019, U.S. Provisional Patent Application No. 62/945,877 filed on December 9, 2019, and U.S. Provisional Patent Application No. 62/945,877 filed on December 9, 2019. No. 62/945,883 filed on September 9, all of which are hereby incorporated by reference for all purposes.

This application is related to co-pending U.S. Patent Application No. 16/820,665, filed on March 16, 2020, which is hereby incorporated by reference for all purposes.

Storage devices such as solid state drives (SSDs) can store relatively large amounts of data. The host processor can request data from the SSD to process the data Perform actions. Depending on the specific architecture connecting the host processor to the SSD, transferring this data to the host processor may take a relatively large amount of time. For example, if the host processor and the SSD are connected using the 4 lanes (lanes) of the third generation Peripheral Component Interconnect Express (PCIe), the maximum amount of data that can be carried between the SSD and the host processor The data volume is approximately 4 billion bytes (GB) per second.

There is still a need to reduce the amount of data sent to the host and take advantage of the benefits of columnar format.

According to an exemplary embodiment, a transcoder includes: a buffer for storing input encoded data; an index mapper for mapping from an input dictionary to an output dictionary; currently An encoding buffer used to store modified currently encoded data in response to the input encoded data, the input dictionary, and the input dictionary to the output dictionary. Mapping; a previously encoded buffer for storing modified previously encoded data in response to previously input encoded data, the input dictionary, and the step from the input dictionary to the previously encoded data. a mapping of the output dictionary; and a rule evaluator for responding to the modified currently encoded data in the current encoding buffer, the modified previously encoded data in the previous encoding buffer and convert encoding rules to generate output streams.

According to an exemplary embodiment, a method of transcoding includes: receiving, at a transcoder, a first data chunk from a storage device from input encoded data; determining whether a host computer is aware of the first data chunk; interest; generating first encoded data from the first data chunk based at least in part on the host computer's interest in the first data chunk; receiving at the transcoder from the storage device Determining that the host computer is not interested in the second data chunk; determining that the host computer is not interested in the second data chunk; determining that the host computer is not interested in the second data chunk; The second data chunk generates second encoded data; and the first encoded data and the second encoded data are output to the host computer.

According to an exemplary embodiment, an article for transcoding includes a non-transitory storage medium having instructions stored thereon that, when executed by a machine, cause: at a transcoder receiving a first chunk of data from an input encoded data from a storage device; determining that a host computer is interested in the first chunk of data; The first data chunk generates first encoded data; receiving a second data chunk from the input encoded data at the conversion encoder from the storage device; determining the host computer's response to the first encoded data. two chunks of data are not of interest; generating second encoded data from the second chunk of data based at least in part on the host computer's lack of interest in the second chunk of data; and converting the first encoded data to and outputting the second encoded data to the host computer.

105:Host computer/machine

110: Processor

115:Memory

120:Storage device/SSD

125:Memory controller

130:Device driver

205:Clock

210:Network connector

215:Bus

220:User interface

225:Input/output engine

305, 515: Storage

310, 320: Arrow

315: In-memory processor/in-memory computing

405: Compressed data

410:Decompressor

415: Data has been decompressed

420:Convert encoder

425: Converted data

430:Decoder

435:Filtered general data

505: Host Interface Layer (HIL)

510:SSD controller/storage device controller

515-1, 515-2, 515-3, 515-4, 515-5, 515-6, 515-7, 515-8: Flash memory chip

520-1, 520-2, 520-3, 520-4: Channel

525: Translation layer

530: File to block mapping

605: Circular buffer/buffer

610:Stream splitter

615:Index mapper

620: Current encoding buffer

625: Previous encoding buffer

630:Conversion encoding rules

635: Rule evaluator

705-1, 705-2, 705-3: Chunking

805:Input dictionary

810: Output dictionary

905:File metadata

910-1, 910-2, 910-3: Row chunking

915: File to block mapping

920, 925: Dictionary page

930-1, 930-2, 930-3: Information page

1005: In-memory computing controller

1010: Row chunking processor

1105:Input buffer

1110: Output buffer

1115:Predicate evaluator

1120: "Ignore" evaluator

1205,1210,1215,1220,1225,1230,1235,1240,1245,1250,1255,1260,1265,1270,1275,1280,1285,1290,1295,1305,1310,1315,1405,1410,142 0. 1425,1430,1440,1445,1505,1510,1515,1520,1525,1605,1610,1615,1620,1625,1630,1635,1640,1645,1650,1655,1660,1665,1670: Square

1415, 1435: dashed line

FIG. 1 illustrates a system including a storage device (eg, a solid state drive (SSD)) that can support transcoding of encoded data in accordance with an embodiment of the present invention.

Figure 2 shows some further details of the machine shown in Figure 1.

FIG. 3 shows that the storage device shown in FIG. 1 and the processor shown in FIG. 1 use different methods to communicate the same data.

FIG. 4 shows the storage device shown in FIG. 1 and the processor shown in FIG. 1 communicating converted encoded data according to a conceptual embodiment of the present invention.

FIG. 5 shows details of the storage device shown in FIG. 1 according to an embodiment of the present invention.

FIG. 6 shows details of the transform encoder shown in FIG. 4 according to an embodiment of the present invention.

FIG. 7 illustrates the stream splitter shown in FIG. 6 dividing input encoded data into chunks according to a conceptual embodiment of the present invention.

FIG. 8 illustrates the index mapper shown in FIG. 6 mapping an input dictionary to an output dictionary according to a conceptual embodiment of the present invention.

Figure 9 shows an exemplary file stored in line format.

FIG. 10 illustrates the storage device shown in FIG. 1 configured to implement transform encoding according to an embodiment of the present invention, wherein data is stored in a row format.

FIG. 11 illustrates the row chunking processor of FIG. 10 configured to implement transform encoding in which data is stored in a row format according to an embodiment of the present invention.

12A to 12C illustrate conceptual embodiments according to the present invention. The figures shown in FIGS. 4 and 6 A flowchart showing an exemplary procedure for a transcoder to transcode material.

FIG. 13 is a flowchart illustrating an exemplary procedure for dividing input encoded data into chunks by the stream demultiplexer shown in FIG. 6 .

14A to 14B illustrate the flow of an exemplary program for converting and encoding data stored in a row format by the line chunking processor shown in FIG. 10 and/or the conversion encoder shown in FIG. 4 according to an embodiment of the present invention. Figure.

15 illustrates a flowchart of an exemplary procedure for mapping an input dictionary to an output dictionary by the index mapper shown in FIG. 6, according to a conceptual embodiment of the present invention.

16A-16B illustrate the in-storage computing controller of FIG. 10 managing predicates received from the host computer of FIG. 1 and potentially performing acceleration on transcoded data, in accordance with embodiments of the present invention. Functional flowchart of an example program.

Reference will now be made in detail to the embodiments of the inventive concept, examples of which are illustrated in the accompanying drawings. In the following detailed description, numerous specific details are set forth to provide a thorough understanding of the inventive concept. However, it will be understood that one of ordinary skill in the art may practice the inventive concepts without these specific details. In other instances, well-known methods, procedures, components, circuits, and networks have not been described in detail in order to avoid unnecessarily obscuring aspects of the embodiments.

It should be understood that although terms such as “first” and “second” may be used herein to describe various elements, these elements should not be limited by these terms. these terms Only used to distinguish individual components. For example, a first module may be referred to as a second module, and similarly, the second module may be referred to as a first module, without departing from the scope of the inventive concept.

The terminology used in the description of the inventive concept herein is for the purpose of describing specific embodiments only and is not intended to limit the inventive concept. As used in the description of the inventive concept and the appended claims, the singular forms "a/an" and "the" are intended to include the plural forms as well, unless the context clearly dictates otherwise. It should also be understood that the term "and/or" as used herein refers to and includes any and all possible combinations of one or more of the associated listed items. It should be further understood that when the word "comprises and/or comprising" is used in this specification, it refers to the presence of stated features, integers, steps, operations, elements, and/or components, but does not exclude the presence of one or more The presence or addition of other features, integers, steps, operations, elements, components, and/or groups thereof. Components and features in the drawings are not necessarily drawn to scale.

Place a certain processing capability closer to the SSD (for example, using Field Programmable Gate Array (FPGA), Application-Specific Integrated Circuit (ASIC), graphics processing unit (Graphics Processing Unit, GPU) or some other processor) will bring some advantages. First, the connection between the SSD and the near-processor can support higher bandwidth than the connection between the SSD and the host processor, allowing for faster data transfer. Second, by freeing the host processor from having to process data, the host processor can perform other functions while the proximal processor handles data processing.

However, near-storage processing of data has potential drawbacks when the data is compressed or encoded. To operate on raw data, some near-memory processors may decompress or decode the data before they can operate on it. Additionally, the near-memory processor can report results back to the host processor. If the resulting amount of data sent to the host processor is greater than the original amount of data, the benefits gained by using a near-memory processor may be lost, or in the worst case, the amount of data sent to the host processor may be contains more compressed or encoded data than was originally sent to the host processor.

Additionally, although the data can be transcoded generally, when the data is stored in row format, some adaptations can be made to take advantage of the row format.

Near-data processing of data in compressed format may negate some of the benefits of offload. If the connection between the SSD and the host processor supports the transfer of X bytes/second, the data is compressed using a compression ratio Y, and the amount of data selected for transfer is Z, then the The amount of data may be X * Y * Z. If this product is less than X, that is if Y * Z < 1, speedup (near processing) can be beneficial.

In some embodiments of the inventive concept, row-based storage may use data encoding (eg, Run Length Encoding (RLE)) and/or compression (Compression (High Speed)) to reduce storage footprint. Encoding, not compression, provides the major entropy reduction. The compression ratio after encoding is often small (about less than 2).

In some embodiments of the inventive concept, for example, based at least in part on an encoding algorithm, the results can be generated without enlarging the result (i.e., without causing it to be sent to the host for processing). Processing of encoded data when the result of the processor is larger than the original encoded data originally sent to the host processor). Encoding algorithms that can be used without expanding the results may include, but are not limited to, dictionary compression, prefix encoding (Prefix Encoding), run length encoding (RLE), cluster encoding (Cluster Encoding), sparse encoding (Sparse Encoding) and indirection. Encoding (Indirect Encoding): Other encoding algorithms can also be used in conjunction with embodiments of the concept of the present invention. Although the embodiments of the inventive concept described below may focus on RLE and bit packing (Bit Packing), the embodiments of the inventive concept may be extended to cover other encoding algorithms.

There is also the additional problem of how to teach the transform encoder what data to filter. This is particularly problematic in cases where the dictionary that reduces the size of the stored data may be stored somewhere other than where the data is stored. Row storage, an example of this storage format, simplifies locating data of interest. However, since the dictionary may be stored somewhere separate from the data, the system may need to be able to locate the dictionary as well as the data in question to perform the transcoding.

Embodiments of the inventive concept enable filtering of encoded data without expanding the data. Filtered data can be re-encoded using transformation rules, using the encoding information embedded in the encoded data. The transcoder in an embodiment of the present invention can filter the encoded data and modify the encoding sent to the host. Therefore, rather than the host having to process normal data (which can be very large relative to the encoded/compressed data depending on the compression algorithm and/or the effectiveness of the encoded data), the host can receive and Process coded data. Since the bandwidth between the host and the storage device can be limited, this will essentially affect the time it takes to transmit data, so it is different from sending ordinary Compared with data (filtered or unfiltered), sending encoded data saves processing time.

A Circular Buffer can store enough data for one processing. Embodiments of the inventive concept may replace the circular buffer with a buffer using other structures.

An index mapper provides a mapping from an input dictionary to a simplified dictionary to be used with the output stream.

The current encoding buffer stores data read from the input stream according to the appropriate encoding. Using information from the conversion encoding rules, the current encoding buffer, and the previous encoding buffer, the rule evaluator determines how to process the data in the current encoding buffer. Depending on whether the data in the current encoding buffer can be combined with the data in the previous encoding buffer, the rule evaluator can update the previous encoding buffer based on the data in the current encoding buffer, output the previous encoding buffer (and replace the previous encoding buffer with buffer with the current encoding buffer), or take some other action. For example, if the converting encoder has identified values in the current encoding buffer that are considered "don't care" values (discussed further below), then those values can be compared with existing values in the previous encoding buffer. "Ignore" value combination.

Stream splitters can be used to identify different parts (streams) of an input stream that are encoded using different encodings. If a single encoding scheme is used, the encoding scheme can be passed as a parameter (ie, encoding type). Otherwise, if multiple encoding schemes are used (i.e., no encoding type is used), the encoding scheme for a given stream is determined by examining the input stream itself. For example, the first tuple of data stored in row storage format encoding may contain encoding type information. For a mix of RLE and bit packing, if least significant If the Least Significant Bit (LSB) is 0, the encoding type = RLE; if the LSB is 1, the encoding type = bit packing.

As examples of how various encoding forms work, consider RLE and Bit Packing (BP). In RLE, a variable unsigned integer is used to represent how often a value is repeated, and then a fixed-length value is given. So, for example, instead of sending 00000011 00000011 00000011 00000011 00000011 00000011 00000011 00000011 00000011 (9 copies of the decimal value 3), the data could be encoded as 00001001 (the decimal value 9)0000 0011 (decimal value 3), which in turn indicates that 00000011 should be repeated 9 times.

In BP, data determined to occupy less space can be combined with other values. For example, if data typically uses 8 bits to store, storing 4 values would take up a total of 32 bits. However, if the values are known to occupy no more than 4 bits each, then the two values can be stored in a single byte: in short, this is bit packing. Since there is some overhead in indicating what data is packed and what is not packed, the space savings are a little less than in the case described, but still beneficial.

The encoding consists of the number of groups in unsigned bytes, followed by a list of packed values in one or more bytes. The maximum number of values in a group can be 8, and the maximum number of groups can be 63. So, for example, to represent the data 00000000 00000001 00000000 00000001 00000000 00000001 00000000 00000001 (decimal value 0 1 0 1 0 1 0 1), the group would be defined as 0000001 (Group 1) 00010000 (0,1)00010000(0, 1)00010000(0, 1)00010000(0, 1).

As mentioned above, RLE (and other encodings) can use mutable unsigned integers. Variable unsigned integers can also be encoded. In each octet, the most significant bit indicates whether the current byte is the last byte in the value or whether there is at least one subsequent byte. Where multiple bytes are used, the least significant byte is presented first, and the most significant byte is presented last. So, for example, the decimal value 1 can be represented as 00000001, the decimal value 2 can be represented as 00000010, and so on, up to 01111111 (the decimal value 127). The decimal value 128 can be represented as 10000000 00000001, the decimal value 129 can be represented as 10000000 00000010, and so on. Essentially, a binary value is divided into groups of 7 bits, with each group of 7 bits preceded by a 1 except for the most significant group. For example, the decimal value 16,384 can be represented as 10000000 10000000 00000001.

When using a transcoder to process encoded data, some data may be considered "don't care" data. That is, there may be some data that is of no value to the operation being performed. As a result of the transformation encoder's operation, data considered "don't care" data can be mapped to different values.

Consider a situation in which a database stores citizenship information for various people. Citizenship status can be stored using strings (such as "China", "Korea", "India", "United States", etc.). However, since the possible values of citizenship are derived from a finite set, a dictionary can be used to reduce the amount of data stored in the database. So, for example, a value of "0" could represent China, a value of "1" could represent India, a value of "2" could represent Korea, and a value of "3" could represent the United States. Representative values (indexes) are stored in the database instead of country names. due to There are 195 countries (as of July 19, 2019), so one byte per character can be used to store the index, which is far less than would be used if one byte per character were used to store a string of country names. group.

However, the acceleration operation being performed may be of interest to US citizens: for example, the operation may be to count the number of US citizens in the database. Therefore, citizens of other countries have nothing to do with the operation: they "don't care" about the value. Transformation encoders map dictionaries and indexes to reflect the data to which the operation applies.

Line format can use RLE or bit packing to encode information. Given that part of a value string is stored in row storage format, one bit can be used to indicate whether the data is stored using RLE or bit packing; the rest of the data can then be interpreted accordingly.

To understand how a transform encoder according to embodiments of the present invention can provide a replacement dictionary for encoded data, consider a situation in which the data includes citizenship information for a large number of people. Since the names of countries of which each person is a citizen are very long, the number of country names is relatively small (even representing 200 countries would only take up about 8 bits, compared to one byte per character in the country name). This is still a significant savings in terms of storing the country name string for each citizen), so the dictionary provides a meaningful reduction in the amount of data stored. This encoding can use any desired encoding scheme: for example, RLE encoding, dictionary compression, prefix encoding, bit packing, cluster encoding, sparse encoding, and indirect encoding.

Now, if the applied predicate (data filter) only locates citizens of the United States, data related to other citizens will not be of interest. For example, the host might Know how many US citizens are interested in the database. As a result of the transformation, the dictionary can be reduced to a single entry for US citizens (there may also be implicit or explicit entries for "ignore" entries), and the RLE encoding can be "compressed" to combine individual entries for non-US citizens. Adjacent RLE entries for citizens of the country. Therefore, the encoding of the data is compressed into a dictionary consisting of 1 (or 2) columns. The actual coded data can also be reduced because data related to non-U.S. citizens can be indexed to a single entry in the new dictionary. Therefore, by pushing down predicates into the transform encoder, already encoded data can be filtered and new encodings provided, reducing the amount of data ultimately sent to the host. Dictionary mapping can represent the mapping from the original dictionary to the converted encoding dictionary.

The transcoder (as well as other features) may be implemented using a Field Programmable Gate Array (FPGA), however embodiments of the inventive concepts may include other implementations including, for example, Application Specific Integrated Circuits (ASICs), graphics processing unit (GPU) or some other processor that executes the software. Additionally, an in-storage compute (ISC) controller can be separate from the FPGA, or it can be implemented as part of the FPGA.

Given a specific file for which an acceleration function (such as filtering) is to be performed, the ISC controller can use a File2Block Map to identify the blocks on the file that store the file data and their order. The ISC controller may be implemented as a component within the host (separate from the storage device itself), or may be a controller that is part of the storage device. These blocks are accessed to provide an input stream that can be input into the transcoder (via the input buffer).

When the file is stored in row format, the data unit can be row chunks, row The chunk itself can contain several data pages. That is, the input buffer may receive the row chunks from the storage module in the storage device so that the transcoder can operate on the row chunks. In general, each row chunk may include its own metadata, which may specify the encoding scheme used for the row chunk and/or the dictionary to be applied to the data in the row chunk. However, not all storage formats use this arrangement: for example, row storage formats can store metadata in separate areas of the file (rather than within each row chunk): this metadata can specify the data used by the entire file. encoding and dictionary. Therefore, when storing a file using this row storage format, the ISC controller can retrieve the encoding and dictionary from the file's metadata area (located using the file 2 block map) and provide this information to the conversion encoding encoder, rather than assuming that the transcoder will block itself to receive any desired information. (Of course, when using a row storage format, there may not be dictionary pages in the row chunks.) Note that although the same encoding scheme can be applied to each row chunk, the encoding scheme itself can be a hybrid scheme, that is, using Two or more different encoding schemes and switching between them as appropriate. For example, a hybrid encoding scheme may combine RLE encoding with bit packing.

In addition to determining the dictionary and encoding scheme, the ISC controller may also extract predicates to be applied to the encoded data and may push the predicates down to the conversion coder. All this information can then be used by the transcoder in various ways. For example, information about the encoding used with the file can be used to select transformation encoding rules to be used with the data, and dictionaries and predicates can be used to generate transformation encoding dictionaries and dictionary maps.

The Predicate Evaluator can use predicates to determine which entries in the dictionary are of interest and which entries are not of interest, generating A transformation encoding dictionary that stores the values of interest (and possibly values representing "ignore" entries), and a dictionary map that maps indices from the original dictionary to the transformation encoding dictionary.

If the converted encoding dictionary includes an entry for a "don't care" value, then this operation is technically adding an entry to the dictionary (because the original dictionary does not include such a value). Adding such an entry can create new problems. Adding a "don't care" entry to a transformation encoding dictionary usually occurs at the first entry in the transformation encoding dictionary (index 0) and is intended to represent a value that does not match the predicate. However, creating new values for "don't care" entries can be expensive: the disclosed system can scan and remap the entire dictionary (since all existing indexes differ by 1). Adding "ignore" entries may also cause memory reallocation or cause a bit width overflow: for example, if every possible value of a given number of bits has been used as a dictionary index, adding to the dictionary The "ignore" entry increases the number of bits used to represent the index by one. If the data page uses part of the dictionary, the data page can have a smaller bit width, and adding a "don't care" entry to the conversion encoding dictionary means that a valid value may not be used in the data page. For example, if the bit width is 1, adding a "don't care" entry may involve more values than can be represented using a single bit, while if the bit width is 2, there may be room for a "don't care" entry , without overflowing the bit width.

The solution to this problem is to determine whether predicate pushdown will result in any reduction in dictionary size. If the dictionary would be reduced by at least one entry, there is room to "ignore" the entries without worrying about bit width overflow. If the dictionary will not be reduced by at least one entry, the encoded data can be sent directly to the ISC controller/host without performing transcoding, thereby avoiding the possibility that transcoding would increase the amount of data.

Note that the output of the transcoder can be sent back to the ISC controller (via the output buffer). This serves two purposes. First, although pushing down predicates into a transcoder produces transcoded data, there may still be operations that are intended to be performed on the transcoded data. For example, if the host attempts to count the number of US citizens in the archive, the transcoded data will identify those citizens but not count them: this operation can be performed by the ISC controller as an acceleration function. Second, the transcoded data can be sent back to the host for further manipulation. The ISC controller communicates with the host and therefore provides a path for the transcoded data to be sent to the host.

FIG. 1 illustrates a system including a solid-state drive (SSD) that can support transcoding of encoded data according to an embodiment of the present invention. In FIG. 1 , a machine 105 that may serve as a host computer may include a processor 110 , a memory 115 and a storage device 120 . Processor 110 may be any kind of processor. Although Figure 1 illustrates a single processor 110, machine 105 may include any number of processors, each of which may be a single-core or multi-core processor, and may be mixed in any desired combination.

Processor 110 may be coupled to memory 115 . The memory 115 can be any type of memory, such as flash memory, dynamic random access memory (Dynamic Random Access Memory, DRAM), static random access memory (Static Random Access Memory, SRAM), persistent random access memory, etc. access memory, ferroelectric random access memory (Ferroelectric Random Access Memory, FRAM), or non-volatile random access memory (Non-Volatile Random Access Memory, NVRAM) (such as magnetoresistive random access memory (Magnetoresistive Random Access Memory, MRAM), etc.). Memory 115 may also be any desired combination of different memory types and may be managed by memory controller 125 . Memory 115 may be used to store what may be termed "short-term" data: that is, data that is not expected to be stored for a long period of time. Examples of short-lived data may include temporary files, data used locally by the application (which may have been copied from other storage locations), etc.

The processor 110 and the memory 115 can also support an operating system under which various applications can run. These applications may issue requests to read data from or write data to memory 115 or storage device 120 . While memory 115 may be used to store what may be termed "short-term" data, storage device 120 may be used to store data that is considered "long-term": that is, data intended to be stored for a long period of time. Storage device 120 may be accessed using device driver 130 . Storage device 120 may be in any desired form, such as a hard disk drive, a solid state drive (SSD), and any other desired form.

Figure 2 shows details of the machine shown in Figure 1. In Figure 2, generally, machine 105 may include one or more processors 110, which may include a memory controller 125 and a clock 205, which may be used to coordinate the operation of the components of the machine. Processor 110 may also be coupled to memory 115, which may include, as examples, random access memory (RAM), read-only memory (ROM), or other state-maintaining media. (state preserving media). The processor 110 may also be coupled to a storage device 120 and a network connector 210 , which may be, for example, an Ethernet connector or a wireless connection. device. Processor 110 may also be connected to bus 215 , which may have attached user interface 220 , input/output interface ports, and other components that may be managed using input/output engine 225 .

FIG. 3 shows that the storage device 120 shown in FIG. 1 and the processor 110 shown in FIG. 1 use different methods to communicate the same data. In one approach (the traditional approach), the storage 305 in the storage device 120 (eg, which can be a platter on a hard drive or a flash memory storage device (eg, an SSD) flash memory chip) reads the data and sends the data directly to the processor 110. If the total data (encoded and/or compressed) stored on the storage device 120 is X bytes, then this is the amount of data to be sent to the processor 110 . Please note that this analysis considers the amount of storage used to store encoded and/or compressed data: unencoded and uncompressed data would likely be a larger number of bytes (otherwise the data would be encoded and/or compressed) There may be no benefit). So, for example, if data can use approximately 10GB of storage when unencoded and uncompressed, but can use approximately 5GB of storage when encoded and/or compressed, then approximately 5GB of data can be used instead of approximately 10GB of data. transmitted from storage device 120 to processor 110 .

The transfer of data from storage device 120 to processor 110 may also be considered in terms of the bandwidth provided for transferring the data (and therefore the time taken to accomplish the transfer). If the data stored on the storage device 120 is encoded and/or compressed, then the data stored on the storage device 120 may be sent directly to the processor 110 (shown by arrow 310). B bytes may be The total data stored on the storage device 120 is sent at an effective rate of /second. Continuing with the earlier example, consider the case where the connection between storage device 120 and processor 110 includes a bandwidth of approximately 1 GB/sec. Since the encoded and/or compressed data can occupy approximately 5GB of space, the encoded and/or compressed data can be sent in a total of 5 seconds over a connection of approximately 1GB/sec. However, since the total data stored (before encoding and/or compression) is approximately 10GB, the effective data transfer rate B is approximately 2GB/second (due to approximately 10GB of unencoded and uncompressed data being sent in approximately 5 seconds ).

In contrast, if the in-memory processor 315 is used to preprocess the data in an attempt to reduce the amount of data sent to the processor 110, less raw data may be sent (because the in-memory processor 315 may have control over what data to send). more selective). On the other hand, the in-storage processor 315 may decompress the data to process the data (and may also decode the data). Thus, the amount of data to be sent from the in-memory processor 315 to the processor 110 may be reduced by data selection, but may also be increased by the amount of compression (and possibly encoding): Algebraically, the amount of data to be sent from the in-memory processor 315 to the processor 110 may be reduced by data selection The amount of data sent by processor 315 to processor 110 (shown by arrow 320) may be expressed as X * Y * Z gigabytes (Gbytes), where The amount of space, Y is the compression ratio (how much data storage is reduced using compression (and possibly encoding)), and Z is the selection rate (how much data is selected from uncompressed data). Similarly, the effective rate at which data can be sent from in-storage processor 315 to processor 110 becomes B * Y * Z bytes/second.

A simple comparison of the two formulas shows that when X * Y * Z < X (or B * Y * Z < B), that is, when Y * Z < 1, the in-memory processor 315 is used to select The information of processor 110 is superior. Otherwise, even if the in-memory processor 315 applies its selectivity, the amount of data to be sent after pre-processing by the in-memory processor 315 is greater than the amount of encoded and/or compressed data: only the original encoded and /or compressing the data will be more efficient than having the in-storage processor 315 attempt to select data to send to the processor 110.

FIG. 4 shows the storage device 120 shown in FIG. 1 and the processor 110 shown in FIG. 1 communicating converted encoded data according to a conceptual embodiment of the present invention. In Figure 4, encoded and/or compressed data is stored in storage 305 (again, storage 305 may represent a platter in a hard drive, a flash memory in a flash memory storage device (such as an SSD) memory chip, or some other physical data storage). This data—compressed data 405—can be passed to decompressor 410 , which can decompress the data to produce decompressed data 415 . Decompression can be performed using hardware or by decompression in appropriate circuits such as general purpose processors, field programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), graphics processing units (GPUs), or general purpose GPUs. , GPU)) to implement the decompressor 410 (also referred to as a decompression engine). The decompressed data 415 can still be encoded because encoding and compression can be separate processes. The decompressed data 415 may then be passed to transcoder 420, which may perform transcoding on the data. Transcoding can be thought of as the process of converting data from one encoding to another.

All of the above processes can occur within storage device 120 . However, once the transcoder 420 has processed the decompressed data 415 and produced the transcoded data 425, the transcoded data 425 can be provided to the host computer 105. The decoder 430 may then decode the converted-encoded data 425 to generate Filtered general data 435. The filtered normal data 435 may then be provided to the processor 110 , which may then perform any desired operations on the filtered normal data 435 .

Note that, for the decoder 430, decoding the transcoded material 425 may involve knowing information about the encoding applied to the transcoded material 425. This information may include, for example, the specific encoding scheme used in the transcoded data 425 or the dictionary used in the transcoded data 425 . Although FIG. 4 does not show this information being transferred from the storage device 120 to the host computer 105 , this information may be transferred to the host computer 105 in parallel with (or as part of) the transcoded data 425 . . Of course, this may occur if the transcoded data 425 is actually uncoded and uncompressed (if the result of transcoding the encoder 420 would be to send a larger number of actual bytes than if the uncoded and uncompressed data were sent) case), the converted-encoded data 425 may omit any information about the encoding scheme or dictionary.

At this point, it's worth discussing the differences between encoding and compression. The two concepts are related—both involve trying to reduce the amount of storage used to store data—but there are some differences. Encoding typically involves the use of a dictionary that provides an index for material that, if included directly, would be lengthy and have a relatively low number of distinct values. For example, approximately 195 different countries exist. If the data stores information about the citizenship of a large number of people, directly including each person's nationality would use a lot of space: at least a few bytes (assuming one byte per character in the name of the country). On the other hand, values 1 to 195 can be represented using a single byte. Use a dictionary to represent countries (Country) and storing an index with the appropriate country name in the data can significantly reduce the amount of data to be stored without losing any information. For example, the information "United States of America, United States of America, Korea, Korea, Korea, Korea, China, India, China, China, China, China, China, United States of America" can be replaced by the dictionary shown in Table 1 representation, thereby causing the information to be represented as "3,3,2,2,2,2,0,1,0,0,0,0,0,3": reduced from 153 characters to 40 characters characters. Even taking into account the dictionary's 52 characters, there are significant savings from simply using a dictionary.

The value of a dictionary can decrease as the number of values in the dictionary becomes larger. For example, if there are 1,000,000 different possible values, each index may use 20 bits to store the index. Of course, this may still be less than the number of bits used to store the value directly, but the benefits of encoding (versus storing unencoded data) may be reduced. Also, if the value stored for each entry in the data can be unique, or if the amount of space used to store the index is approximately the same as the amount of space used to store the value, then using dictionary encoding can actually increase the amount of data to be stored. quantity. Continuing with the example of data about people, using a dictionary to store their age is no more efficient than storing the age directly.

On the other hand, compression typically uses a coding scheme such as Huffman code. The data can be analyzed to determine the relative frequency of each data, with shorter codes assigned to more frequent data and longer codes assigned to less frequent data. Morse code, although not a Huffman code, is a well-known example of a code that uses shorter sequences for more frequent data and longer sequences for less frequent data. For example, the letter "E" can be represented by the sequence "dot" (followed by a space), while the letter "J" can be represented by the sequence "dash-dash-dash-dash-dash" (followed by a space). (Since Morse code uses spaces to indicate where one symbol ends and another begins, a sequence of one symbol can be the prefix of a sequence of another symbol (note that "E" is represented by a dot, and "J" Starting with a dot but including other symbols). Morse code is not a proper Huffman code. However, many people are familiar with Morse code to some extent, which makes it a shorter code for more frequent data. and a more generally useful example of using longer codes for less frequent data.)

Returning to the coding scheme, once the dictionary is established, there are several different coding schemes that can be used to further code the material. Examples of such encoding schemes include run length encoding (RLE), bit packing, prefix encoding, cluster encoding, sparse encoding, and indirect encoding: other encoding schemes may also be used with embodiments of the inventive concept. Run-length encoding and bit packing are discussed here because they are used in various examples later; information on other encoding schemes can be easily found.

Run-length encoding (RLE) relies on the premise that values often appear in groups. Rather than storing each value individually, a single copy of the value can be stored along with a number that represents how often that value occurs in the data. For example, if the value "2" appears four times in a column, instead of storing the value "2" four times (which would use four bytes of storage), the value "2" can be stored together with the number of occurrences of the value ("4") Storage (this can use two bytes of storage). Therefore, continuing the above example, the sequence "3,3,2,2,2,2,0,1,0,0,0,0,0,3" can be represented by "[2,RLE],3,[4,RLE ]2,[1,RLE]0,[1,RLE],1,[5,RLE],0,[1,RLE],3". The encoding "[2,RLE],3" can be understood to mean that there is information encoded using RLE: the value is "3", and the value is repeated twice; other RLE encodings are similar. (The reason why the representation includes an indicator that RLE encoding was used has to do with the potential use of hybrid encoding schemes discussed below with reference to Figure 7.) This sequence can use a total of 12 bytes: for each encoding, one A byte stores the number of times the next value is repeated, and a byte stores the value to be repeated.

Compared with the 14 bytes used to store the original sequence, 12 bytes does not significantly reduce the amount of space used to store data. But proportionally, this encoding represents about 14% less storage required for this data. Even a 14% reduction in storage usage for data occupying approximately 5GB is a significant savings: approximately 700 million bytes (MB).

As an alternative to the number of occurrences of each value, the starting position of each group can be stored. When using the starting position instead of counting the occurrences of each value, the data can be represented as "[0,RLE],3,[2,RLE]2,[6,RLE]0,[7,RLE], 1,[8,RLE],0,[13,RLE],3".

The above discussion describes the case where RLE repeated values are assembled into a single byte. What if this is not the case: for example, what if the repeated value is "1000" ("1000" can be stored using 10 bits)? In this case, RLE can The value is serialized into groups of seven bits. The eighth bit in each byte, which may be the most significant bit in the byte, may indicate whether the byte continues in another byte.

As an example, consider the value "1000". In binary, the value "1000" can be represented as "11 1110 1000". Since this representation uses 10 bits, the value may be too large to be stored in a single byte. Therefore, the value can be broken down into groups of seven bits (leading zeros are added so that each group contains seven bits): "0000111 1101000". The first byte in the sequence can now be prepended with a '1' to indicate that the value it represents continues in the next byte, and the second byte in the sequence can be prepended with a '0' to indicate that the value ends with the byte. Therefore, the bit sequence becomes "10000111 01101000". When the system reads this sequence of bits, the system knows to look at the most significant bit in each byte to determine whether the value continues beyond the byte or ends with the byte, and The bits are removed when the sequence of bits is reassembled into a value. Therefore, "10000111 01101000" becomes "0000001111101000" (two additional leading zeros are added to bring the representation to a full two bytes), allowing the original value "1000" to be restored.

Of course, if one bit in each byte is used to identify whether the byte is a continuation of a value, then that bit may not be used as part of the value. Therefore, even though a value may fit into a single byte, additional bits may be included to indicate that the value does not continue in another byte. Additionally, if the value is to be assembled in 8 bits instead of 7 bits (for example, a value between 128 and 255), then when using the indicated value it is Two bytes can be used to represent the complete value if the byte is continued in the next byte (because the most significant bit of the value will be shifted to the next 7 bits in the encoding group formed).

When using RLE, bits and/or groups of bytes can be presented in any desired order. For example, the bits may be presented from most significant bit to least significant bit or from least significant bit to most significant bit; the bytes may be similarly ordered in either of these ways. So, for example, use a continuation when bytes are presented from least significant byte to most significant byte but the bits in each byte are presented from most significant byte to least significant byte. bit (continuation bit), the value "16384" can be encoded as "10000000 10000000 00000001". This bit sequence can be interpreted as follows: the first bit in each byte is a continuation bit (where a "1" indicates that the next byte continues the value, and a "0" indicates that the value not continued in the next byte). After removing the continuation bits, what remains is "0000000 0000000 0000001". When the bytes are reordered from most significant byte to least significant byte (and reconstructed into traditional groups of eight bits, thus discarding leading zeros), the value becomes "01000000 00000000", this is the binary value of the value "16384".

Bit packing, on the other hand, exploits the idea that a value can use fewer bits than an entire byte. For example, if the values to be stored include 0, 1, 2, and 3, two bits can be used to represent each value. Although a complete byte can be used to store each value, using a complete byte means that 75% of the storage is actually unused. Bit packing facilitates the storage of more than one value in a single byte (or sequence of bytes). Use this phenomenon. Bit packing is particularly beneficial when sequences of values are repeated rather than individual values.

As an example, consider the sequence "0,1,0,1,0,1,0,1" and consider that it uses about four bits to uniquely identify each value (i.e., no values greater than 15 are used) condition. Rather than storing each value individually (requiring a total of eight bytes), the encoding "[4,BP]0,1" can be used. This encoding means that a single byte stores four bits representing the value "0" and four bits representing the value "1", and then the byte is repeated four times. (Like RLE encoding, bit-packed encoding may include an indicator that the data is encoded using bit-packing for use in hybrid encoding schemes.) The first byte indicates the number of times the data in the group is to be repeated. ;The second byte stores the value in the group itself. This encoding can use about two bytes to store data, thus reducing the amount of storage used for the sequence by about 75%.

When using bit packing, data can be packed in any desired way. For example, when each value is packed using a sequence of four bits "0,1", the sequence may be represented as "00010000" (values are packed from least significant bit to most significant bit) or "00000001" (the value is packed from the most significant bit to the least significant bit). Some implementations of bit packing may use either strategy, but then reverse the order in which the bits are placed into the stream (so that what is actually the least significant bit gets passed first). Other techniques can also be used to pack bits in bit packing.

Of course, bit packing does not limit the groups that can fit into a single byte. Like RLE, values in bit packing can use bits to identify whether the value continues in the next byte.

Since both encoding and compression attempt to reduce the amount of space used to store data representations, the benefits are not multiplied. Encoding and compression both attempt to reduce the amount of space used to store data. However, once the data has been compacted in one way (such as encoding), applying further compression schemes (such as compression) may not be so useful. Compression can be applied to the data after it has been encoded and still reduce the amount of storage space used to some extent, but the impact of compression on encoded data may be less than the benefit of compression on unencoded data. (If every scheme for compressing data could be applied with equal benefit, regardless of the data being compressed, then one might wish to reduce any data to a ridiculously small size simply by applying repeated compression schemes. . It should be easy to understand with a little thought that this result is unrealistic in the real world.)

FIG. 5 shows details of the storage device 120 shown in FIG. 1 . In FIG. 5, the storage device 120 is shown as an SSD, however embodiments of the inventive concepts may support other forms of storage devices 120 with appropriate modifications. In FIG. 5, the storage device 120 may include a host interface layer (HIL) 505, an SSD controller 510, and various flash memory chips 515-1 to 515-8 (also known as "flash memory chips"). memory"), the flash memory chips 515-1 to 515-8 may be organized into various channels 520-1 to 520-4. The host interface layer 505 manages communications between the storage device 120 and the machine 105 shown in FIG. 1 . These communications may include read requests to read data from the storage device 120 and write requests to write data to the storage device 120 . SSD controller 510 may use a flash memory controller (not shown in Figure 5) to manage read and write operations and garbage collection of flash memory dies 515-1 through 515-8. Collection (garbage collection) and other operations.

The SSD controller 510 may include a translation layer 525 (also known as a flash translation layer (FTL)). The translation layer 525 can perform the function of translating the logical block address (LBA) provided by the machine 105 shown in FIG. 1 into the physical block address (PBA) of the actual data stored on the SSD 120. In this way, the machine 105 shown in FIG. 1 can use its own address space to reference data without having to know the physical address on the storage device 120 where the data is actually stored. This can be beneficial when, for example, data is updated: since storage 120 may not update the data in-place, storage 120 can invalidate the existing data and write the updates to a new PBA on storage 120 . Alternatively, if the data is stored in a block selected for garbage collection, the data can be written to a new block on storage device 120 before the block is erased. By updating the translation layer 525, the machine 105 shown in Figure 1 is isolated when data is moved to different PBAs regardless of where the data is actually stored.

SSD controller 510 may also include a file to block map 530. File-to-block mapping 530 may specify which blocks are used to store data for which files. For example, file-to-block mapping 530 may be used when data is stored in row format. File-to-block map 530 may be part of translation layer 525 (in which case file-to-block map 530 may not be considered a separate component of storage device 120 ), or file-to-block map 530 may supplement translation layer 525 (For example, translation layer 525 may be used for data that uses a relatively small number of blocks, while file-to-block mapping may be used for data that occupies a relatively larger number of blocks), or file-to-block mapping 530 may completely replace translation layer 525 (in which case translation layer 525 may not exist in SSD controller 510).

SSD controller 510 may also include transcoder 420. However, embodiments of the inventive concept may include having the transform encoder 420 located elsewhere within the storage device 120 (e.g., a general purpose processor (running appropriate software), FPGA, ASIC, GPU may be used somewhere within the storage device 120 or GPGPU and other possible solutions to implement the transform encoder 420) or even a configuration external to the storage device 120.

Storage device 120 may also include an in-storage processor 315 shown in FIG. 3 (not shown in FIG. 5), which may execute instructions that govern how data stored on storage device 120 is used. The in-memory processor 315 shown in FIG. 3 may also be used for in-memory computing functions to perform operations locally on the storage device 120 rather than on the processor 110 shown in FIG. 1 . Like transcoder 420, Figure 3 can be implemented somewhere within storage device 120 using a general purpose processor (running appropriate software), FPGA, ASIC, GPU or GPGPU, among other possibilities, or even external to storage device 120 In-memory processor 315 is shown.

Although FIG. 5 shows storage device 120 as including eight flash memory dies 515-1 through 515-8 organized into four channels 520-1 through 520-4, embodiments of the inventive concept may support organized Any number of flash memory chips into any number of channels. Similarly, although FIG. 5 illustrates that SSD controller 510 may include transcoder 420 and/or in-memory processor 315 as shown in FIG. 3 , embodiments of the inventive concept may be configured other than as shown in FIG. 5 There is a transcoder 420 or an in-memory processor 315 as shown in Figure 3 .

FIG. 6 shows details of transform encoder 420 shown in FIG. 4 . In FIG. 6 , the transform encoder 420 may receive various inputs (eg, input dictionary, input stream, and encoding type), and generate various outputs (eg, output dictionary, and output stream). Briefly, transcoder 420 can operate to obtain an input stream that can be encoded using the encoding scheme specified by the encoding type, and can produce an output stream. (Although the input stream can be encoded, the following discussion considers the case where the input stream is uncompressed: if the input stream is compressed, the input stream can be decompressed before further processing.) The output stream can be used with The input stream may be encoded with the same encoding scheme, or the output stream may be encoded with a different encoding scheme (or both: as discussed below, when using mixed encoding schemes, some data may be changed from one encoding scheme to another). an encoding scheme).

Additionally, even if the encoding scheme does not change between the input stream and the output stream, the encoding itself can change. For example, if a particular value is assigned to a different index in the input dictionary than in the output dictionary, the dictionary changes should be reflected in the values used in the actual data. To this end, transform encoder 420 may also obtain an input dictionary and map it to an output dictionary.

As an example of these last two points, consider again the dictionary shown in Table 1 above. Now consider one of the 105 pairs of host computers shown in Figure 1 regarding the United States of America (United States). States of America) citizens' information is of interest. Table 1 can be considered an input dictionary because it represents the data received in the input stream. On the other hand, Table 2 can be an output dictionary, representing the data in the output stream. Regarding Table 2, there are at least three points to note. First, Table 2 includes two entries compared to the four entries shown in Table 1. Second, Table 2 includes entries labeled "Don't Care" (but any other name could be used because the host computer 105 shown in Figure 1 is not interested in the data represented by the corresponding value at this time) . Third, although "United States of America" has ID 3 in Table 1, "United States of America" has ID 1 in Table 2. This last bit implies that any reference to ID 3 in the input stream can be changed to reference ID 1 in the output stream (otherwise the data might be meaningless).

To accomplish these operations, transcoder 420 may include various components. Transform encoder 420 may include a circular buffer 605, a stream splitter 610, an index mapper 615, a current encoding buffer 620, a previous encoding buffer 625, transform encoding rules 630, and a rule evaluator 635.

The circular buffer 605 can receive the data stream from the storage 305 shown in FIG. 3 in the storage device 120 shown in FIG. 1 . Since the entire data to be processed can be large (for example, gigabytes or terabytes of data), an attempt is made to load all the data at once and as a unit in a certain Processing within one storage may be impractical. Therefore, the input stream can be received as a stream and buffered, allowing the data to be processed in smaller units than the entire data set. Although Figure 6 shows buffer 605 as a circular buffer, implementation of the inventive concept Examples can use any type of buffer to store data received from the input stream.

Stream separator 610 may obtain data from circular buffer 605 and divide the data into chunks. The chunks may then be passed to index mapper 615. Chunks may represent units of data to be processed by other components within transform encoder 420 and should not be confused with the term "chunk" which may be used in other contexts (e.g., see the term "rows" used in Figure 9 below. "column chunk").

FIG. 7 shows that the stream splitter 610 shown in FIG. 6 divides the input encoded data into chunks, and the input encoded data may be part (or all) of the input stream. In Figure 7, the input data is shown to include, among other things, three pieces of encoded data: "[1,BP],3,3, [4,RLE],2, [5,RLE],0". As discussed above, these chunks represent data encoded using bit packing and RLE encoding schemes. This encoding represents the following (uncoded) sequence of values: "3,3,2,2,2,2,0,0,0,0,0". For each individual code, the host computer 105 shown in Figure 1 may be interested in the material (or a portion of the material), or the host computer 105 shown in Figure 1 may not be interested in the material. Whether the host computer 105 of FIG. 1 may be interested in the values in each encoding may depend on the conversion encoding rules 630: the demultiplexer 610 of FIG. 6 may not know what data the host computer 105 of FIG. 1 may be interested in. Interest. Therefore, the stream splitter 610 shown in FIG. 6 can divide the input data stream into chunks, where each chunk includes a different piece of encoded data. Thus, chunk 705-1 may include encoding "[1,BP],3,3", chunk 705-2 may include encoding "[4,RLE],2", and chunk 705-3 may include encoding " [5,RLE],0".

There are at least two additional points worth noting regarding Figure 7. First, also note that In the exemplary input stream shown in Figure 7, some data is encoded using bit packing, and some data is encoded using RLE. If all the data is encoded using a single encoding scheme (eg, RLE), then destreamer 610 of FIG. 6 can determine this fact from the encoding type input to transform encoder 420 of FIG. 6 . However sometimes mixed encoding schemes are used. In a mixed encoding scheme, some data can be encoded using one encoding scheme (e.g., RLE) and some data can be encoded using another encoding scheme (e.g., bit-packing) (the concept can also be generalized to use in mixed encodings). scheme uses more than two encoding schemes). In a hybrid encoding scheme, the transform encoder 420 shown in FIG. 6 may not receive an encoding type as input because the information alone does not tell the deserializer 610 shown in FIG. 6 what data is encoded in which encoding scheme. Instead, destreamer 610 shown in Figure 6 can determine what encoding scheme was used for each chunk by looking at the chunk itself.

One way to determine the encoding scheme used to encode a specific chunk may be by checking the value of specific bits in the chunk. For example, a row storage format can use the least significant bit in the first tuple to indicate whether a particular chunk of data can be encoded using RLE or bit packing: if the value of the bit can be "0", then RLE can be used, and bit packing can be used if the bit can have a value of '1'. This bit is then removed from the byte and the remaining bits are logically shifted right by one bit to produce the value used for encoding.

For example, consider block 705-1. Block 705-1 will include the bit sequence "00000011 00110011". When the demultiplexer 610 shown in Figure 6 reads the first byte "00000011", the demultiplexer 610 shown in Figure 6 can check the least significant Bit (last "1"). Since the least significant bit can be "1", the destreamer 610 shown in Figure 6 can determine that this chunk can be encoded using bit packing. The least significant bit is removed and the remaining bits in the first byte are logically shifted to the right by one bit, resulting in the byte "00000001". Since the first (most significant) bit of this byte can be "0", the demultiplexer 610 shown in Figure 6 can determine that the byte can only be "00000001" (the indicator value can be removed A "0" bit that may not be continued in the next byte and another leading zero is added), thereby indicating that the group (still to be determined) may be repeated once. Then, the demultiplexer 610 shown in FIG. 6 can read the next byte "00110011". Since the most significant bit of this byte may be "0", the demultiplexer 610 shown in FIG. 6 knows that this value will not be carried over to the next byte. The continuation bits can be removed and leading zeros added, resulting in the value "00110011", which represents the values "3" and "3". Therefore, the demultiplexer 610 shown in FIG. 6 can determine that the encoding uses bit packing to represent that the value "3" can be repeated twice.

On the other hand, consider block 705-2. Block 705-2 will include the bit sequence "00001000 00000010". When the demultiplexer 610 shown in Figure 6 reads the first byte "00001000", the demultiplexer 610 shown in Figure 6 can check the least significant bit (the last "0"). Since the least significant bit can be "0", the demultiplexer 610 shown in Figure 6 can determine that this chunk can be encoded using RLE. The least significant bit is removed and the remaining bits in the first byte are logically shifted right by one bit, resulting in the byte "00000100". Since the first (most significant) bit of this byte can be "0", the demultiplexer 610 shown in Figure 6 can determine that the byte can only be "00000100" (the indicator value can be removed But not in the next position continuation of "0" bits in the tuple and adding another leading zero), thereby indicating that the value (still to be determined) can be repeated four times. Then, the demultiplexer 610 shown in FIG. 6 can read the next byte "00000010". Since the most significant bit of this byte may be "0", the demultiplexer 610 shown in FIG. 6 knows that this value will not be carried over to the next byte. The continuation bits are removed and leading zeros are added, resulting in the value "00000010". Therefore, the stream demultiplexer 610 shown in FIG. 6 can determine that the encoding using RLE to represent the value "2" can be repeated four times.

Of course, the stream separator 610 shown in FIG. 6 may not perform all of this analysis on any bit sequence. All the demultiplexer 610 shown in Figure 6 can do will be to read bytes until it encounters a byte with a "0" as the most significant bit (this sequence of bytes will indicate the encoding scheme and the upcoming the number of repetitions of the incoming value), and then reads the bytes until it encounters another byte with "0" as the most significant bit (this sequence of bytes will represent the encoded value). Destreamer 610 of FIG. 6 may then pass those read bits (representing the entire encoded chunk) to index mapper 615 of FIG. 6 (and used later by the rules of FIG. 6 Evaluator 635 processing): Index mapper 615 shown in Figure 6 (and/or rule evaluator 635 shown in Figure 6) can perform the analysis illustrated to determine what encoding scheme was used for the chunk and what values were So coded. However, if the destreamer 610 of Figure 6 (or the index mapper 615 of Figure 6 or any other component of the inventive concept) performs analysis to determine the encoding scheme for encoding a particular data chunk, then Figure Stream separator 610 shown in Figure 6 (or index mapper 615 or other component shown in Figure 6) can pass the encoding type down the line to other components to avoid repeating this analysis. exist This can be particularly important in cases where bits identifying the encoding scheme are removed from the chunk when processing the chunk: without an encoding type, components that later process the encoded data may not be able to handle the encoded data correctly.

Second, note that chunks 705-2 and 705-3 represent consecutive chunks that are both encoded using RLE. It is expected that the stream splitter 610 shown in Figure 6 will treat all consecutive RLE encodings as a single chunk (based on using different encoding schemes to separate the chunks). But recall that the goal is to transform-encode the input stream so that all data of no interest is combined into a single "don't care" value. Recall that the stream demultiplexer 610 shown in FIG. 6 may not have information about what data the host computer 105 shown in FIG. 1 is interested in. If the stream separator 610 shown in FIG. 6 believes that all encodings using the same encoding scheme are the same block, the stream separator 610 shown in FIG. 6 can finally combine the data that the host computer 105 shown in FIG. 1 is interested in with the data of FIG. 1 The host computer 105 is shown not interested in the data mix. Additionally, if all data in the input stream is encoded using the same encoding scheme, the entire input stream will be considered a single chunk, which will eliminate the stream splitter 610 shown in Figure 6 as the transform encoding shown in Figure 6 part of the device 420.

Third, although the above discussion focuses on a hybrid coding scheme that uses one bit to distinguish two different coding schemes, embodiments of the inventive concept can be generalized to hybrid coding schemes that use more than two different coding schemes. Of course, if more than two encoding schemes are used, more than one bit can be used to distinguish the different encoding schemes. For example, if three or four encoding schemes are used, two bits can be used to distinguish the encoding schemes, and if five, six, seven, or eight different encoding schemes are used, Three bits can be used to distinguish between different encoding schemes, and so on.

(Also note that the bits used to distinguish encoding schemes can be used for other purposes. For example, consider the case where three encoding schemes are used. If the least significant bit of the first byte has a specific value (such as "0") , then an encoding scheme such as RLE can be used, in which the next least significant bit is used to represent the value. However, if the least significant bit of the first byte has another specific value (such as "1"), then The next least significant bit can be used to differentiate between the remaining two encoding schemes (such as bit-packing and cluster encoding).)

Returning to FIG. 6 , index mapper 615 may receive chunks from destreamer 610 . Index mapper 615 may then map the encoded values from the input dictionary to the encoded values in the output dictionary. For example, consider again the dictionaries shown in Tables 1 and 2 above. Since the value corresponding to "United States of America" may be of interest, when the value "3" is encountered in an encoded chunk, the value "3" can be replaced with the value "1"; All other values may be replaced with the value "0" when encountered in the encoded chunk.

Figure 8 shows the index mapper shown in Figure 6 mapping the input dictionary to the output dictionary. In Figure 8, index mapper 615 is shown receiving an input dictionary 805 and generating an output dictionary 810. Given information about the material of interest to host computer 105 shown in Figure 1, index mapper 615 may generate output dictionary 810. The index mapper may also generate a mapping from input dictionary 805 to output dictionary 810. Continuing with the example above, this mapping could specify the mapping shown in Table 3. As can be seen, index "3" can be mapped to index "1"; all other indexes can be mapped to index "0".

There are several points worth noting regarding index mapper 615. First, although index mapper 615 is shown as a separate component of transform encoder 420 shown in Figure 6, index mapper 615 can work in conjunction with (or be implemented as a function of) rule evaluator 635 shown in Figure 6. part). Second, how index mapper 615 may generate output dictionary 810 (and the mapping shown in Table 3) may depend on what data host computer 105 shown in FIG. 1 is interested in. The following is a discussion of how the index mapper can learn what data the host computer 105 shown in FIG. 1 is interested in with reference to FIG. 11 . Third, transcoding the data may involve an index mapper 615 that maps the input dictionary 805 to the output dictionary 810 and a transcoding rule 630 shown in FIG. 6: The transcoding rule 630 shown in FIG. 6 may depend from the input dictionary 805 to Output dictionary 810 mapping. The converse is not true: the mapping from the input dictionary 805 to the output dictionary 810 (and thus the operation of the index mapper 615) can be generated without reference to the transformation encoding rules 630 shown in Figure 6.

The fourth point about index mapper 615 is more subtle. Note that the index mapper 615 effectively adds a new entry to the output dictionary 810: the "ignore" value. To keep the implementation simple, make the index mapper 615 always use the same index for the "don't care" value is meaningful. Since the size of the input dictionary 805 can vary depending on the data set, the index "0" can always be used.

However, what happens if it turns out that the host computer 105 shown in Figure 1 is interested in all the data in the data set? In this situation, index mapper 615 has added entries to output dictionary 810, but no entries have been removed from output dictionary 810. The combination of these two facts means that the output dictionary 810 can be larger (one entry) than the input dictionary 805. Consider the case where the input dictionary 805 has exactly 2 ⁿ entries for some value n . This fact means that n bits can be used to represent each index in the input dictionary 805. Adding the "ignore" entry to the output dictionary 810 means that there are now 2 ⁿ +1 entries in the output dictionary 810 , which means that n +1 bits are now used to represent all possible values in the data set: This question is This is called bit overflow. This additional bit can affect the encoded data, requiring new bits to be added to properly represent the data. Therefore, a single small change to the output dictionary 810 can have a large ripple effect on the data representation, and can significantly increase the amount of storage used to represent the encoded data.

Although the above example focuses on the case where introducing a "don't care" entry adds new bits to represent all possible indexes in the output dictionary 810, even when the size of the output dictionary 810 is increased to use new bits to represent all Similar problems can occur when indexing is possible. Consider again the input dictionary shown in Table 1, and consider the case where the host computer 105 shown in Figure 1 is interested in Chinese and Indian citizens (indexes "0" and "1" in Table 1). A single bit can be used to represent these indices (because one bit can be used to represent the values "0" and "1"). If so Values are encoded using bit packing, so eight such values can be packed into a single byte. However, if index "0" is assigned to the "don't care" value in output dictionary 810, then the indexes for China and India will map to other values (eg, "1" and "2"). Since the value '2' uses two bits, it may no longer be possible to pack the eight values into a single byte: a bit overflow has occurred.

There are several possible solutions to the bit overflow problem. One is to check to see if any index in the input dictionary 805 represents material that is not of interest to the host computer 105 shown in Figure 1 . If it turns out that the host computer 105 is interested in all the data in the input dictionary 805, then there is no need to transcode the input stream at all, and the input stream can be mapped directly to the output stream without modification.

However, although this solution is useful, it may not be sufficient because bit overflow problems may still occur during bit packing. To avoid bit overflow in bit packing, a solution may be to ensure that the number of bits used to represent any index in the output dictionary 810 is no greater than the number of bits used to represent any index in the input dictionary 805 . Two possible solutions are described here. One solution could be to assign the highest possible index in the output dictionary 810 to the "don't care" value: that is, first map all the indexes of interest in the input dictionary 805 to the output dictionary 810, and then use The lowest unused index. Another solution may be to identify indexes in the input dictionary 805 that are of no interest to the host computer 105 shown in Figure 1 and use those indexes as "don't care" values. In both solutions, any index in the input dictionary 805 will not be replaced with a larger index in the output dictionary 810, which avoids bit overflow problems. The disadvantage of this type of solution is that it may not be possible to select a separate Index to input dictionary 805.

Returning to FIG. 6 again, the current chunk (possibly processed by index mapper 615) may be stored in current encoding buffer 620. From there, the rules evaluator 635 can evaluate the encoded data in the current encoding buffer 620 and the encoded data in the previous encoding buffer 625 and determine whether the encoding should be changed and what data should be output to the output stream. Briefly, the rule evaluator 635 can determine whether the encoded material in the current encoding buffer 620 can be combined with the encoded material in the previous encoding buffer 625. If so, the encoded data in the current encoding buffer 620 can be added to the encoded data in the previous encoding buffer 625; otherwise, the encoded data in the previous encoding buffer 625 can be output to the output stream, and can The encoded data in the current encoding buffer 620 is moved to the previous encoding buffer 625 . (This analysis considers the situation in which there is data in the previous code buffer 625. If the previous code buffer 625 does not contain data, as may happen for the first data chunk, then there is no need to consider trying to convert the current code buffer to The encoded data in 620 is combined with the transcoded data in the previously encoded buffer 625.)

This leads to the next question: When can the encoded data be combined? The short answer is that the encoded data chunks may be combined when either the chunks represent material of interest to the host computer 105 shown in Figure 1 or both represent material of no interest to the host computer 105. Some examples may help illustrate how rule evaluator 635 operates. In both instances, the input streams include the same data: "[1,BP],3,3,[4,RLE],2,[1,BP],0,1,[5,RLE],1 ,[1,BP],3", and the input dictionary is shown in Table 1. In both examples, the columns represent the values in the current encoding buffer 620 and the previous encoding buffer 625 's content and a "snapshot" of the content that has been output to the output stream at that time.

In a first example, host computer 105 shown in Figure 1 has requested information about citizens of the United States of America. As can be seen in Table 1, the index of "United States of America" is "3". Therefore, the output dictionary can be as shown in Table 2.

As shown in column 1 of Table 4, the first chunk processed by rule evaluator 635 is "[1,BP],3,3". Since this chunk may include the data of interest (the value "3"), the rule evaluator 635 may use the mapping from the input dictionary 805 shown in Figure 8 to the output dictionary 810 shown in Figure 8 to replace the value "3" with Value "1". This converted-encoded chunk may then be moved to the previous encoding buffer 625 (as shown in column 2 of Table 4).

In column 2 of Table 4, the second chunk processed by rule evaluator 635 is "[4,RLE],2". Since this chunk may not include the data of interest (the value "2"), the rule evaluator 635 may use the mapping from the input dictionary 805 shown in Figure 8 to the output dictionary 810 shown in Figure 8 to replace the value "2" with A value of '0' (indicates that this data is "ignore" data). Since this chunk may contain "don't care" data, but the previously encoded buffer 625 may contain interesting data, the data in the previously encoded buffer 625 may be output to the output stream (as shown in column 3 of Table 4 as shown), and the currently converted-encoded chunks may be moved to the previous encoding buffer 625 (as shown in column 3 of Table 4).

In column 3 of Table 4, the third chunk processed by rule evaluator 635 is "[1,BP],0,1". Since this chunk may not include the data of interest (values "0" and "1"), the rule evaluator 635 can use the mapping from the input dictionary 805 shown in Figure 8 to the output dictionary 810 shown in Figure 8 to change the value " 0" and "1" are replaced with the value "0" (indicating that this data is "ignore" data).

Since this chunk may contain "don't care" data, and the previous encoding buffer 625 may have contained "don't care" data, these two chunks may be combined. Since this chunk uses bit packing, but the previous chunk in encoding buffer 625 used RLE, one of the two encoding schemes can be replaced with the other encoding scheme. In this example, RLE may be used to trans-encode the bit-packed encoded data. (If two or more values are stored in a single value using bit packing, the entire group can be copied, which means that the number of copied values can be a multiple of the number of packed values. On the other hand, RLE copy single value.) Therefore, the previously encoded buffer 625 can now store Store "[6,RLE],0" (shown in column 4 of Table 4), which combines the four "Ignore" values in the second block with the two "Ignore" values in the third block. ” value combination.

In column 4 of Table 4, the fourth chunk processed by rule evaluator 635 is "[5,RLE],1". Since this chunk may not include the data of interest (the value "1"), the rule evaluator 635 may use the mapping from the input dictionary 805 shown in Figure 8 to the output dictionary 810 shown in Figure 8 to replace the value "1" with A value of '0' (indicates that this data is "ignore" data).

Since this chunk may contain "don't care" data, and the previous encoding buffer 625 may have contained "don't care" data, these two chunks may be combined. Both chunks use RLE as the encoding scheme to encode the same "don't care" value, so the rule evaluator 635 can combine the two chunks by adding the copied values from the previously encoded chunk in the buffer 625 chunks. Therefore, the previous encoding buffer 625 can now store "[11,RLE],0" (as shown in column 5 of Table 4), which combines the four "don't care" values in the second chunk, the third A combination of the two "Ignore" values in the block and the five "Ignore" values in the fourth block.

In column 5 of Table 4, the second chunk processed by rule evaluator 635 is "[1,BP],3". Since this chunk may include the data of interest (the value "3"), the rule evaluator 635 may use the mapping from the input dictionary 805 shown in Figure 8 to the output dictionary 810 shown in Figure 8 to replace the value "3" with Value "1". Note that since this transcoded chunk may contain data of interest and previously encoded buffer 625 may contain "don't care" data, this transcoded chunk may not be combined with the group in previously encoded buffer 625 Block combination.

At this time, typically the transcoded data in the previous encoding buffer 625 will be output to the output stream, and the currently transcoded chunks will be moved to the previous encoding buffer 625 . However, since the currently transcoded chunk is the last chunk in the input stream, two transcoded chunks may be output (of course, the chunk in the previous encoding buffer 625 is output first). Column 6 of Table 4 shows the final output.

In a second example, the host computer 105 shown in Figure 1 has requested information on Korean citizens. As can be seen in Table 1, the index of "Korea (South Korea)" is "2". Therefore, the output dictionary is shown in Table 5.

As shown in column 1 of Table 6, the first chunk processed by rule evaluator 635 is "[1,BP],3,3". Since this chunk may include uninteresting data (the value "3"), the rule evaluator 635 may use the mapping from the input dictionary 805 shown in Figure 8 to the output dictionary 810 shown in Figure 8 to replace the value "3" with A value of '0' (indicates that this data is "ignore" data). This converted-encoded chunk may then be moved to the previous encoding buffer 625 (as shown in column 2 of Table 6).

In column 2 of Table 6, the second chunk processed by rule evaluator 635 is "[4,RLE],2". Since this chunk may include the data of interest (the value "2"), the rule evaluator 635 may use the mapping from the input dictionary 805 shown in Figure 8 to the output dictionary 810 shown in Figure 8 to replace the value "2" with Value "1". Since this chunk may contain interesting data, but previously encoded buffer 625 may contain uninteresting data, the data in previously encoded buffer 625 may be output to the output stream (as shown in column 3 of Table 6 shown), and the currently transcoded chunk may be moved to the previous encoding buffer 625 (shown in column 3 of Table 6).

In column 3 of Table 6, the third chunk processed by rule evaluator 635 is "[1,BP],0,1". Since this chunk may not include the data of interest (values "0" and "1"), the rule evaluator 635 can use the mapping from the input dictionary 805 shown in Figure 8 to the output dictionary 810 shown in Figure 8 to change the value " 0" and "1" are replaced with the value "0" (Indicates that this data is "ignore" data). Since this chunk may contain uninteresting data, but previously encoded buffer 625 may contain interesting data, the data in previously encoded buffer 625 may be output to the output stream (as shown in column 4 of Table 6 shown), and the currently transcoded chunk may be moved to the previous encoding buffer 625 (shown in column 4 of Table 6).

In column 4 of Table 6, the fourth chunk processed by rule evaluator 635 is "[5,RLE],1". Since this chunk may not include the data of interest (the value "1"), the rule evaluator 635 may use the mapping from the input dictionary 805 shown in Figure 8 to the output dictionary 810 shown in Figure 8 to replace the value "1" with A value of '0' (indicates that this data is "ignore" data).

Since this chunk may contain "don't care" data, and the previous encoding buffer 625 may contain "don't care" data, these two chunks may be combined. Since this chunk uses RLE, but the previous chunk in encoding buffer 625 used bit packing, one of the two encoding schemes can be replaced with the other encoding scheme. In this example, RLE may be used to trans-encode the bit-packed encoded data. (Again, RLE may be chosen because individual values, rather than groups of values, can be copied.) Therefore, previously encoded buffer 625 now stores "[7,RLE],0" (as shown in column 5 of Table 6) , which combines the two "Ignore" values from the third block with the five "Ignore" values from the fourth block.

In column 5 of Table 6, the second chunk processed by the rule evaluator 635 is "[1,BP],3". Since this chunk may not include the data of interest (value "3"), the rule evaluator 635 may use the input dictionary 805 shown in FIG. 8 to the Output dictionary 810 mapping to replace the value "3" with the value "0" (the "ignore" value).

Since this chunk may contain "don't care" data, and the previous encoding buffer 625 may contain "don't care" data, these two chunks may be combined. Since this chunk uses bit packing, but the previous chunk in encoding buffer 625 used RLE, one of the two encoding schemes can be replaced with the other encoding scheme. In this example, RLE may be used to trans-encode the bit-packed encoded data. Therefore, the previous encoding buffer 625 now stores "[8,RLE],0", which combines the 2 "don't care" values in the third block, the five "don't care" values in the fourth block, and the A "don't care" value combination in a block of five.

Finally, since the fifth chunk is the last chunk of the input stream, the rule evaluator 635 may output the converted-encoded data in the previous encoding buffer 625 . Column 6 of Table 6 shows the final output.

Neither of the above two examples shows a situation where consecutive chunks include the material of interest. Embodiments of the inventive concept may handle such situations in different ways. In one embodiment of the inventive concept, when the current encoding buffer 620 contains the data of interest, any chunks in the previous encoding buffer 625 may be output to the output stream (i.e., if the current encoding buffer 620 contains data of interest, no attempt is made to combine the data in the current encoding buffer 620 with the data in the previous encoding buffer 625). In another embodiment of the inventive concept, chunks in the current encoding buffer 620 and chunks in the previous encoding buffer 625 may be combined. However, in such embodiments of the inventive concept, whether such a combination is possible may depend on whether the values of interest are the same. For example, if one chunk includes data about Chinese citizens and another A set of chunks including data on Korean citizens may or may not be combined depending on the embodiment of the inventive concept. On the other hand, if both chunks include information on Korean citizens, then it may be feasible to combine the two chunks.

Rule evaluator 635 may use transform encoding rules 630 to determine what data is of interest and what data is not of interest, what data may be output and what data may be stored in previously encoded buffer 625, and whether the chunks Can be converted from one encoding scheme to another encoding scheme. The exact rules may vary depending on the encoding scheme available for the material.

As mentioned above, rule evaluator 635 may also include index mapper 615. In an embodiment of the inventive concept in which the rule evaluator 635 includes an index mapper 615, the rule evaluator 635 may apply the index mapper 615 to the contents of the current encoding buffer 620 before applying the conversion encoding rules 630.

Table 7 shows some rules that can be used when the encoding scheme used can be RLE or bit packing. In embodiments of the inventive concept where other encoding schemes may be used, the rules may vary accordingly: all such variations are considered embodiments of the inventive concept. Additionally, embodiments of the inventive concept may include rules governing the conversion encoding of material between more than two different types of encoding schemes. For example, a hybrid encoding scheme may use three different encoding schemes: When the current encoding buffer 620 shown in FIG. 6 and the previous encoding buffer 625 shown in FIG. 6 contain data encoded using any pair of different encoding schemes, FIG. 6 Encoding rules 630 are shown to specify how the data is to be encoded.

g

63，x mod G=0，y mod G=0，z mod G=0，y≠0，且y

16除以每一已打包值的位元數目。最後，PEB(在輸出行中)可指示，當規則被選擇來應用時儲存於先前編碼緩衝器625中的任何內容可被輸出至輸出串流。表7亦考量其中任何資料已被索引映射器615映射且因此包含與圖8所示輸出字典810對應的值的情況。 In Table 7, P represents the information that the host computer 105 shown in FIG. 1 may be interested in, and DC represents the information that the host computer 105 may not be interested in. (How data may be identified as being of interest or not of interest is discussed further below with reference to Figure 11.) Where variables (such as x , y , or z ) are used, these variables may represent the host computer 105 shown in Figure 1 A count of the number of interesting or uninteresting values. For example, the expression "[ g ,BP]P( x ),DC( y ),P( z )" (as used in rules 7 and 9) may indicate that the data is encoded using bit packing: the group includes x interesting values at the beginning of the group, y uninteresting values in the middle of the group, and z interesting values at the end of the group. It can be expected that x , y , z , g and G satisfy the following constraints: g * G= x + y + z , 1

g

63, x mod G=0, y mod G=0, z mod G=0, y ≠0, and y

16 divided by the number of bits per packed value. Finally, the PEB (in the output line) may indicate that any content stored in the previous encoding buffer 625 when the rule was selected for application may be output to the output stream. Table 7 also considers the case where any data has been mapped by index mapper 615 and therefore contains values corresponding to output dictionary 810 shown in FIG. 8 .

The discussion above illustrates how transformation encoding can generally be performed on data. However, when the data is stored in line format, the line format can be used to facilitate encoding conversion. Before this effect can be explained, it is useful to understand line format. For ease of explanation, the row format is described with reference to an SSD, however embodiments of the inventive concepts may include other storage devices that may utilize the row format.

Figure 9 shows an exemplary file stored in line format. In Figure 9, an archive is shown. The file may include file metadata 905 and row chunks 910-1, 910-2, and 910-3. Although FIG. 9 shows three row chunks 910-1 through 910-3, embodiments of the inventive concept may include any number (zero or more) of chunks without limitation.

Archive metadata 905 may include metadata related to the archive. Although other metadata may be stored, Figure 9 shows file metadata 905 as including file-to-block mapping 915 and dictionary page 920. Dictionary page 920 may be used for archival information within A dictionary that encodes values, such as the one shown in Table 1 above. Dictionary page 920 can also store multiple dictionaries that can be used to encode different data within the file: for example, one dictionary can store country names, while another dictionary can store last names.

File-to-block mapping 915 may identify the blocks that store individual row chunks 910-1, 910-2, and 910-3 and their relative order. File-to-block mapping 915 may also specify the order of data pages within each row chunk 910-1, 910-2, and 910-3, or may be specified within row chunks 910-1, 910-2, and 910-3 Page order. The file-to-block mapping 915 may be similar to the file-to-block mapping 530 shown in FIG. 5 , except that the file-to-block mapping 530 may provide information about which blocks are used to store each file stored on the storage device 120 shown in FIG. 1 . Information about a file, and file-to-block mapping 915 may provide information about which blocks are used to store the file shown in Figure 9. (Of course, the two file-to-block mappings can be used together: the file-to-block mapping 530 shown in Figure 5 can be used to locate the block storing file metadata 905 for each file, and then the files in the file metadata 905 are Block map 915 may be used to locate blocks that store row chunks for the file.)

In general, a single row chunk can span multiple blocks, and a single block can store multiple row chunks. As long as there is some way to identify where the data is stored and what the data represents (eg, what file contains the data), there is little difficulty in more general data storage solutions. To facilitate this discussion, however, consider the case where row chunks can be assembled into a single block and row chunks are not shared between blocks. Therefore, each of row chunks 910-1, 910-2, and 910-3 may be stored in a separate block.

Within row chunk 910-1 (row chunks 910-2 and 910-3 are similar), There may be a dictionary page 925 and data pages 930-1, 930-2 and 930-3. Although FIG. 9 shows three data pages, embodiments of the inventive concept may include any number (zero or more) of data pages in row chunks. A data page can store the actual data of a file, divided into units that can be assembled into separate pages.

Dictionary page 925 may store a dictionary for data within row chunk 910-1. Like dictionary page 920, dictionary page 925 can store multiple dictionaries that can be used to encode different data within the file.

Questions may arise as to why Figure 9 shows dictionary page 920 and dictionary page 925. The reason is that dictionary pages 920 and 925 can be used in different implementations of line format. For example, a row storage format may use a single dictionary for the entire file, which may be stored in dictionary page 920. However, another line format could use a separate dictionary page 925 in each line block 910-1, 910-2, and 910-3. The advantage of using the dictionary page 925 is that if a dictionary is not used for a particular row chunk or certain values are not used in the data within the specific row chunk, this information can be omitted from the dictionary page 925, thus reducing the dictionary page size size of 925 (or even eliminate dictionary page 925 entirely). On the other hand, however, multiple dictionary pages 925 in different row chunks may result in duplication of data: the same dictionary entry can be used in multiple row chunks. This is why dictionary pages 920 and 925 are shown in dashed lines: either may be omitted depending on the line storage format used. (In fact, it may even be the case that the file does not use a dictionary at all, in which case dictionary pages 920 and 925 can both be omitted.)

Now that row format has been explained, it can be explained that when using row format storage The adaptation is performed in the storage device using the transform encoder 420 shown in Figure 4. Figure 10 shows the storage device 120 of Figure 1 configured to implement transform encoding, where data is stored in a row format. In Figure 10, storage device 120 may include a host interface layer 505, a storage device controller 510, and storage 515 that function similarly to those described above with reference to Figure 5 (again, storage device 120 may be an SSD, a hard disk drive, or Any other storage device in line format can be used).

Storage device 120 may also include an in-memory compute controller 1005, a row chunking processor 1010, and an in-memory compute 315. The in-memory compute controller 1005 can manage what information is sent to the in-memory compute 315 and the row chunking processor 1010. For example, when the host computer 105 shown in FIG. 1 requests the storage device 120 to perform a certain accelerated function (such as counting the number of citizens of a particular country), the in-storage computing controller 1005 may provide the row chunking processor 1010 with the described information. word (identifies the country of interest). In-memory compute controller 1005 may also access data (specifically, row chunks) from storage 515 and provide the data to row chunk processor 1010 . In-storage compute controller 1005 may also determine the encoding scheme used in the data (assuming a single encoding scheme is used for the row chunks or the entire file, rather than a mixed encoding scheme) and provide the encoding type to the row chunking processor 1010. Finally, upon request from the host computer 105 shown in Figure 1, the in-storage computing controller 1005 can process the converted coded data returned by the chunking processor and can pass the converted coded data back to Figure 1. 1 illustrates host computer 105 (via host interface layer 505) or in-storage computing 315. The structure and operation of row chunking processor 1010 are discussed below with reference to FIG. 11 .

In-memory compute controller 1005 and row tile processor 1010 may be implemented using a suitably programmed general purpose processor, FPGA, ASIC, GPU or GPGPU, among other possibilities. In-memory compute controller 1005 and row chunk processor 1010 may be implemented using the same hardware or different hardware (e.g., in-memory compute controller 1005 may be implemented as an ASIC and row chunk processor 1010 may be implemented using the same hardware or different hardware). 1010 may be implemented as an FPGA), and it may be implemented as a single unit or separate component.

Figure 11 illustrates the row chunking processor 1010 of Figure 10 configured to implement transform encoding where data is stored in a row format. In Figure 11, row chunking processor 1010 may receive an input stream, encoding type, and predicate as input, and may generate an output stream as output. The input stream may be stored in input buffer 1105. The input stream can be a single page of data in a row chunk, or it can be all data in a row chunk. The data from the input buffer 1105 may then be provided as an input stream to the transcoder 420 (as described above with reference to FIG. 6 ): the transcoder 420 may also receive the code from the in-memory computing controller 1005 shown in FIG. 10 Type, as discussed with reference to Figure 10. Note that since the transcoder 420 may include the circular buffer 605 shown in FIG. 6, the input buffer 1105 may be omitted: data may be stored in the circular buffer 605 shown in FIG. 6, and the stream demultiplexer 610 shown in FIG. 6 may Perform operations on said data. However, in some embodiments of the inventive concept, the circular buffer 605 shown in Figure 6 may not be large enough to store an entire page or row chunk of data (or the input stream may provide data faster than shown in Figure 6 Circular buffer 605 removes data faster), in which case input buffer 1105 may serve as a temporary repository for data that may not be immediately populated in circular buffer 605 shown in FIG. 6 .

The output of the transcoder 420, the output stream described above with reference to FIG. 6, may be stored in the output buffer 1110. Again, although the data may be sent directly to its destination as produced by transform encoder 420, it may be useful to send the data in specific units (eg, complete pages of data or chunks of rows). In such cases, the output buffer 1110 may store the output stream until the appropriate data unit is generated. At this time, based on the requested conversion encoding operation, the row chunking processor 1010 may send the output stream to the in-memory computing controller 1005 shown in FIG. 10 or the host computer 105 shown in FIG. 1 .

Index mapper 615 (shown in Figure 11 as external to transform encoder 420, but index mapper 615 may be part of transform encoder 420 as shown in Figure 6) can self-describe word evaluator 1115 and "ignore" Evaluator 1120 receives information. Predicate evaluator 1115 may receive predicates from in-storage computing controller 1005 shown in Figure 10 and use the predicates to determine what data is of interest. The predicate evaluator 1115 may use comparison operators to identify which values in the input dictionary 805 shown in FIG. 8 (which may be any of the dictionary pages 920 and 925 shown in FIG. 9 ) by the host computer 105 shown in FIG. 1 Interested. The "don't care" evaluator 1120 may operate similarly (but in mirror form) to identify what data is not of interest. Note that since the predicate evaluator 1115 and the "ignore" evaluator 1120 are operationally complementary, either of the two evaluators can be used (any data that does not meet the criteria of one evaluator is therefore suitable for the other). one evaluator criterion): Therefore, one of the predicate evaluator 1115 and the "ignore" evaluator 1120 may be omitted. This information may be provided to the index mapper 615 by the predicate evaluator 1115 and the "don't care" evaluator 1120, causing the index mapper 615 is capable of establishing a mapping from the input dictionary 805 shown in Figure 8 to the output dictionary 810 shown in Figure 8 .

As an example, consider again a query from the host computer 105 shown in Figure 6 to count the number of entries in a data set that include citizens of the United States of America. When this query arrives, the predicate can be extracted (e.g., "citizenship=United States of America": the exact format of the predicate can depend on the format of the dataset and the application used to submit the query) . The input dictionary 805 shown in Figure 8, such as the dictionary shown in Table 1, may be checked to replace "United States of America" with the value "3". Thus, the predicate provided to index mapper 615 may specify "citizenship=3", and index mapper 615 may then generate output dictionary 810 shown in Figure 8 (eg, the dictionary shown in Table 2) and Table 3 The mapping shown in .

Note that the results of the predicate evaluator 1115 may also be provided to the transform encoder 420 for constructing the transform encoding rules 630 shown in FIG. 6 . Since the transformation encoding rules 630 shown in FIG. 6 may depend on knowing what material the host computer 105 shown in FIG. 1 is interested in, the results of the predicate evaluator 1115 may be used to adapt the transformation encoding rules 630 shown in FIG. 6 . For example, consider again the rule shown in Table 7. The results of the predicate evaluator 1115 (or even a mapping from the input dictionary 805 shown in Figure 8 to the output dictionary 810 shown in Figure 8 (such as the mapping shown in Table 3)) can be used to establish for P and DC in various rules appropriate value.

Note also that in Figure 11, the predicate applies to any data input to transcoder 420 as an input stream. While asserting that the predicate will be applied as shown in Figure 1 It is reasonable for the host computer 105 to submit the entire data set of the query to it, whereas the transcoder 420 treats the input stream as complete even though the input stream may represent a portion of the data set. For example, row chunking processor 1010 may use transform encoder 420 to process each data page 930-1, 930-2, and 930-3 shown in FIG. 9 as its own "input stream." Since the transcoder 420 does not know what the input stream represents, there is no problem with this process.

12A to 12C illustrate a flow chart of an exemplary procedure for converting and encoding data by the converting encoder 420 shown in FIGS. 4 and 6 according to a conceptual embodiment of the present invention. In Figure 12A, at block 1205, transcoder 420 of Figure 6 may check to see if there is still any data to be received from the input stream. Generally speaking, this input stream can come from any source, but as discussed above with reference to Figures 9-11, when the data is stored in row format, this input stream can be pages of data in row chunks. If there is no remaining data to receive from the input stream, then at block 1210, the transcoder 420 of FIG. 6 may check to see whether the previous code buffer 625 of FIG. 6 or the current code buffer of FIG. 6 Whether any transcoded data remains in the processor 620. If any converted-encoded data remains in the previous encoding buffer 625 shown in FIG. 6 or the current encoding buffer 620 shown in FIG. 6 , the converted-encoded data in the previous encoding buffer 625 shown in FIG. 6 is output to output stream, and then output the converted coded data in the current encoding buffer 625 shown in FIG. 6 to the output stream. In most cases, there should be no data in the current encoding buffer 620 shown in FIG. 6 because the rule evaluator 635 can operate on the data in the current encoding buffer 620 shown in FIG. 6 . Even in which due to the application of the transformation shown in Figure 6 If encoding rules 630 (eg, as shown in rules 6 to 9 of Table 7) can leave data in the current encoding buffer 620 shown in FIG. 6, the rule evaluator 635 shown in FIG. 6 will also first After operating on the data, the transform encoder 420 shown in Figure 6 will look for new data from the input stream (via the circular buffer 605 shown in Figure 6 and the stream separator 610 shown in Figure 6): Figure 6 The transcoder 420 shown may wait for the current encoding buffer 620 shown in FIG. 6 to be cleared before attempting to process the next data chunk from the input stream. However, if there is still converted-encoded data in the current encoding buffer 620 shown in FIG. 6 , the converted-encoded data can be output to the output stream. Once all data has been output to the output stream at block 1215, processing may end (until transcoder 420 of Figure 6 is expected to process a new input stream).

Assuming that there is still data to be processed in the input stream, at block 1220, the circular buffer 605 shown in Figure 6 can receive the next encoded data from the input stream, after which the stream demultiplexer 610 shown in Figure 6 can The first chunk in the encoded material is identified and forwarded to index mapper 615 shown in Figure 6. (In embodiments of the inventive concept in which the index mapper 615 shown in Figure 6 is actually part of the rule evaluator 635 shown in Figure 6, the stream demultiplexer 610 shown in Figure 6 can place the encoded data chunks in In the current encoding buffer 620 shown in Figure 6.) At block 1225, the index mapper 615 shown in Figure 6 (or the rule evaluator 635 shown in Figure 6) can determine whether the data chunk is of interest: More specifically , whether the data chunk includes the data requested by the host computer 105 shown in FIG. 1 (eg, based on the predicate).

If the encoded data chunk includes the host computer 105 shown in Figure 1 that is of interest data, then at block 1230 (FIG. 12B), the index mapper 615 shown in FIG. 6 (or the rule evaluator 635 shown in FIG. 6) may use the input dictionary 805 shown in FIG. 8 to the output dictionary 810 shown in FIG. Map to recode any data in the chunk. At block 1235, the rule evaluator 635 of FIG. 6 may check to see if the host computer 105 of FIG. 1 is interested in any transcoded material in the previous encoding buffer 625 of FIG. 6. If not (and recall that the host computer 105 of FIG. 1 is interested in the current chunk as determined at block 1225 of FIG. 12A), then at block 1240, the transcoder 420 of FIG. 6 may convert the The transcoded data in the previously encoded buffer 625 is output to the output stream, and at block 1245 , the transcoder 420 in FIG. 6 may store the currently transcoded chunk in the previously encoded chunk in FIG. 6 In encoding buffer 625, processing may then return to block 1205 shown in Figure 12A.

On the other hand, if, as determined at block 1235, the previous encoding buffer 625 of FIG. 6 also stores data of interest to the host computer 105 of FIG. 1, then at block 1250, the rule evaluator 635 of FIG. 6 may It is determined whether the current chunk uses the same encoding scheme as the converted-encoded chunk in the previous encoding buffer 625 shown in FIG. 6 . If not, then at block 1255, the rule evaluator 635 shown in FIG. 6 may change the code generated by one of the chunks (the chunk in the current encoding buffer 620 shown in FIG. 6 or the previous encoding buffer 625 shown in FIG. 6 The coding scheme used for chunks in . (In cases where more than two encoding schemes are used, the rule evaluator 635 shown in FIG. 6 may change the chunks from the current encoding buffer 620 shown in FIG. 6 and the previous encoding buffer 625 shown in FIG. 6. The encoding scheme used for chunking.) Then, knowing that Figure 6 In the case where the chunks in the current encoding buffer 620 shown in FIG. 6 use the same encoding scheme as the chunks in the previous encoding buffer 625 shown in FIG. 6, at block 1260, the rule evaluator 635 shown in FIG. 6 may compare the two The chunks are combined into a single chunk, which may be stored in the previous encoding buffer 625 shown in FIG. 6, after which processing may return to block 1205 shown in FIG. 12A.

Note that Figure 12B shows that the current chunk may be transcoded twice: once in block 1230 (when the values are updated to correspond to the output dictionary 810 shown in Figure 8) and once in block 1255 (if the current chunk's The encoding scheme is changed when changing from one encoding scheme to another). Although these two operations can be performed separately, they can also be combined: that is, changing the encoding scheme and updating the values simultaneously. Embodiments of the inventive concept include performing these two operations separately and as a single step.

Recall that Figure 12B illustrates the operations performed when the host computer 105 of Figure 1 is interested in the current chunk (as determined at block 1225 of Figure 12A). If the host computer 105 of FIG. 1 is not interested in the current chunk (again, as determined at block 1225 of FIG. 12A), then at block 1265 (FIG. 12C), the index mapper 615 of FIG. 6 (or FIG. The rule evaluator 635 shown in Figure 6) may recode any data in the chunk (specifically, recode it to "ignore" using the mapping from the input dictionary 805 shown in Figure 8 to the output dictionary 810 shown in Figure 8 value). At block 1270, the rule evaluator 635 of FIG. 6 may check to see if the host computer 105 of FIG. 1 is interested in any converted-encoded material in the previous encoding buffer 625 of FIG. If so (and recall that block 1225 as shown in Figure 12A (determined that the host computer 105 shown in FIG. 1 is not interested in the current chunk), then at block 1275, the converted encoder 420 shown in FIG. 6 may convert the converted encoded data in the previous encoding buffer 625 shown in FIG. output to the output stream, and at block 1280, the transcoder 420 of FIG. 6 may store the currently transcoded chunk in the previous encoding buffer 625 of FIG. 6, and then processing may return to that of FIG. 12A. Block 1205 is shown.

On the other hand, if, as determined at block 1270, the previous encoding buffer 625 of FIG. 6 also stores data that is not of interest to the host computer 105 of FIG. 1, then at block 1285 the rule evaluator 635 of FIG. 6 may It is determined whether the current chunk uses the same encoding scheme as the converted-encoded chunk in the previous encoding buffer 625 shown in FIG. 6 . If not, then at block 1290 , the rule evaluator 635 of FIG. 6 may change the block from one of the blocks (the block in the current encoding buffer 620 of FIG. 6 or the block in the previous encoding buffer 625 of FIG. 6 block) the encoding scheme used. (In cases where more than two encoding schemes are used, the rule evaluator 635 shown in FIG. 6 may change the chunks from the current encoding buffer 620 shown in FIG. 6 and the previous encoding buffer 625 shown in FIG. 6. The encoding scheme used by the chunk.) Then, knowing that the chunks in the current encoding buffer 620 shown in Figure 6 and the chunks in the previous encoding buffer 625 shown in Figure 6 use the same encoding scheme, in block At 1295, the rule evaluator 635 shown in Figure 6 can combine the two chunks into a single chunk, which can be stored in the previous encoding buffer 625 shown in Figure 6, and then processing can return to Figure 12A. Block 1205 is shown.

Note that Figure 12C shows that the current chunk can be transcoded twice: once in in block 1265 (when the values are updated to correspond to the output dictionary 810 shown in Figure 8) and once in block 1290 (when changing from one encoding scheme to another if the encoding scheme of the current chunk is changed) . Although these two operations can be performed separately, they can also be combined: that is, changing the encoding scheme and updating the values simultaneously. Embodiments of the inventive concept include performing these two operations separately and as a single step.

In Figures 12A-12C, there is an implicit assumption that there is some data in the previous encoding buffer 625 shown in Figure 6. For example, blocks 1235 and 1270 illustrate the situation where there is some data in the previous encoding buffer 625 shown in Figure 6. This is generally a reasonable assumption because the transcoded data can be buffered in the previous encoding buffer 625 shown in Figure 6 to support combining data chunks that can be combined if the data has been output to the output stream. It will be too late to try to combine chunks). However, there may be situations where no data is stored in the previous encoding buffer 625 shown in FIG. 6 . As an example, when the first chunk of the input stream is processed, there is no data in the previous encoding buffer 625 (because no data has been previously processed in the input stream). As a second example, there may be encoding schemes that do not support data chunk combining, in which case there is little value in storing previous chunks in the previous encoding buffer 625 shown in FIG. 6 . If there is no data in the previous encoding buffer 625 shown in Figure 6, there is no need to compare the current chunk with the (non-existent) chunk in the previous encoding buffer 625 shown in Figure 6 or from the previous encoding buffer 625 shown in Figure 6 The previously encoded buffer 625 outputs (non-existing) chunks. The simple solution is that if there is no data in the previous encoding buffer 625 shown in Figure 6, then nothing will depend on it. For operations where data exists in the previous encoding buffer 625. Thus, for example, in Figure 12B, if there is no data in the previous encoding buffer 625, processing may jump directly from block 1230 to block 1245 (to buffer the currently converted encoding in the previous encoding buffer 625 shown in Figure 6 chunks), and in Figure 12C, processing may jump directly from block 1265 to block 1280 (to buffer the currently transcoded chunks in the previous code buffer 625 shown in Figure 6).

A closer inspection of Figure 12B and Figure 12C will reveal that there are relatively small differences between the two. Some differences worth noting are blocks 1230 and 1265, and the different branches leaving from blocks 1235 and 1270. In fact, even these differences are relatively minor: Blocks 1230 and 1265 are both about recoding based on the output dictionary 810 shown in Figure 8 (Block 1265 just specifies the use of "ignore" values). Also, although the branches leaving blocks 1235 and 1270 are labeled differently, the reason is that blocks 1235 and 1270 are both about determining whether the current block can be combined with the previous block. Therefore, Figures 12B-12C could theoretically be combined, but at the expense of some degree of loss of clarity regarding the sequence of operations.

FIG. 13 is a flowchart illustrating an exemplary procedure for dividing input encoded data into chunks by the demultiplexer 610 shown in FIG. 6 . In FIG. 13, at block 1305, the stream demultiplexer 610 of FIG. 6 may receive input encoded data (which may originate from the storage 305 of FIG. 3 within the storage device 120 of FIG. 1), The input encoded data may be buffered in a buffer such as input buffer 1105 shown in Figure 11 or circular buffer 605 shown in Figure 6. At block 1310, stream splitter 610 shown in Figure 6 may divide the input encoded data into chunks. At block 1315, the stream shown in Figure 6 Separator 610 may send the chunks to transform encoder 420 shown in Figure 6 (or to index mapper 615 shown in Figure 6 or current encoding buffer 620 shown in Figure 6).

14A to 14B illustrate how the row chunking processor 1010 shown in FIG. 10 and/or the transform encoder 420 shown in FIGS. 4 and 6 performs transform encoding on data stored in a row format according to a conceptual embodiment of the present invention. Flowchart of an exemplary program. In at least one embodiment, FIGS. 14A-14B may also be viewed as extending how destreamer 610 of FIG. 6 may receive input encoded data, as described in block 1305 of FIG. 13 .

In Figure 14A, at block 1405, the row chunking processor 1010 shown in Figure 10 can access the file's file-to-block map 915 shown in Figure 9 (or alternatively or additionally map the file-to-block map 915 shown in Figure 5 Block mapping 530). At block 1410 , the row chunking processor 1010 of FIG. 10 may use the file-to-block mapping 915 of FIG. 9 to locate the file metadata 905 of FIG. 9 and thereby identify the input dictionary 920 of FIG. 9 . If each row block 910-1, 910-2, and 910-3 shown in Figure 9 includes its own dictionary page 925 shown in Figure 9, the dictionary page shown in Figure 9 can be omitted from the file metadata 905 shown in Figure 9 920, in which case block 1410 may be omitted, as shown by dashed line 1415. Then, using the file-to-block mapping 915 of FIG. 9 , at block 1420 , the row chunking processor 1010 of FIG. 10 may identify the row chunks of the file (which may be stored on the storage device 120 of FIG. 1 data block).

At block 1425 (FIG. 14B), the row chunk processor 1010 shown in FIG. 10 may determine whether there are more row chunks (blocks) to be accessed. If not, processing is complete. Otherwise, at block 1430, row chunking processor 1010 shown in Figure 10 may Row block 910-1, 910-2 or 910-3 shown in Figure 9 accesses dictionary page 925 shown in Figure 9 . If the file metadata 905 shown in Figure 9 stores the dictionary page 920 shown in Figure 9, then the row blocks 910-1, 910-2 and 910-3 shown in Figure 9 can omit the dictionary page 925 shown in Figure 9. In this case In this case, block 1430 may be omitted, as shown by dashed line 1435. At block 1440, the row chunk processor 1010 shown in Figure 10 can access the data pages 930-1, 930-2 shown in Figure 9 from the row chunks 910-1, 910-2 and 910-3 shown in Figure 9 and 930-3. At block 1445, the row chunking processor 1010 of FIG. 10 may process the input dictionary 805 of FIG. 8 and the row chunking data pages 930-1, 930-2, and 930-3 of FIG. 9 (in that order) Forwarded to the conversion encoder 420 shown in FIG. 6, the stream separator 610 shown in FIG. 6, or the index mapper 615 shown in FIG. 6.

15 illustrates a flowchart of an exemplary procedure by which the index mapper 615 of FIG. 6 maps the input dictionary 805 of FIG. 8 to the output dictionary 810 of FIG. 8 according to a conceptual embodiment of the present invention. In FIG. 15, at block 1505, the index mapper 615 of FIG. 6 may receive the input dictionary 805 of FIG. 8 (eg, from the row chunking processor 1010 of FIG. 10). At block 1510, the index mapper 615 shown in FIG. 6 may determine what information in the input dictionary 805 shown in FIG. 8 is of interest. Index mapper 615 of FIG. 6 makes this determination using predicates received, for example, from host computer 105 of FIG. 1 , possibly via in-memory computing controller 1005 of FIG. 10 . At block 1515, the index mapper 615 shown in Figure 6 may generate the output dictionary 810 shown in Figure 8. The output dictionary 810 may include all entries that are of interest to the host computer 105 of FIG. 1, but may combine all entries that are not of interest to the host computer 105 of FIG. 1 into a single "don't care" value. At block 1520, the index mapper 615 shown in Figure 6 may convert Values from the input dictionary 805 shown in FIG. 8 are mapped to the output dictionary 810 shown in FIG. 8 . Finally, at block 1525, the index mapper 615 shown in Figure 6 may output the output dictionary 810 shown in Figure 8.

16A-16B illustrate the in-storage computing controller 1005 of FIG. 10 managing predicates received from the host computer 105 of FIG. 1 and potentially performing acceleration functions on the encoded data, in accordance with an embodiment of the present invention. Flowchart of an exemplary program. In FIG. 16A, at block 1605, the in-storage computing controller 1005 of FIG. 10 may receive a predicate from the host computer 105 of FIG. 1. At block 1610, the in-memory computing controller 1005 of Figure 10 may access the input dictionary 805 of Figure 8 of the encoded data covered by the query. At block 1615, the in-storage computing controller 1005 of FIG. 10 may identify the entry covered by the predicate in the input dictionary 805 of FIG. 8 (i.e., the host computer 105 of FIG. 1 in the input dictionary 805 of FIG. 8 items of interest). At block 1620, the in-storage computing controller 1005 of FIG. 10 may create the output dictionary 810 of FIG. 8 that contains the entries covered by the predicates. At block 1625, the in-memory computing controller 1005 of FIG. 10 may map the entries covered by the predicates in the input dictionary 805 of FIG. 8 to entries in the output dictionary 810 of FIG. 8.

At block 1630, the in-storage computing controller 1005 of FIG. 10 may identify entries in the input dictionary 805 of FIG. 8 that are not covered by the predicate (i.e., the host computer of FIG. 1 in the input dictionary 805 of FIG. 8 105 entries not of interest). At block 1635, the in-memory compute controller 1005 of FIG. 10 may add a "Ignore" entry to the output dictionary 810 of FIG. 8. At block 1640 (Figure 16B), In-memory computation controller 1005 shown in FIG. 10 may map entries in the input dictionary that are not covered by predicates to "ignore" entries in output dictionary 810 shown in FIG. 8 .

At block 1645, the rule evaluator 635 of FIG. 6 (within the transform encoder 420 of FIG. 6) may use the predicates to adapt the transform encoding rules 630 of FIG. 6 to the query from the host computer 105 of FIG. . At block 1650, the index mapper 615 of FIG. 6 and the rule evaluator 635 of FIG. 6 (both potentially within the transform encoder 420 of FIG. 6) may use the input dictionary 805 of FIG. The mapping of the output dictionary 810 shown and the transcoding rules 630 shown in Figure 6 are used to transcode the encoded data from the input stream to the output stream (as discussed above with reference to Figures 12A-12C).

At this point, various options exist. As shown in block 1655, the in-storage computing controller 1005 of FIG. 10 may receive an output stream from the transcoder 420 of FIG. 6 and may forward the transcoded data to the host computer 105 of FIG. 1, And at block 1660, the in-memory computing controller 1005 of FIG. 10 may send the output dictionary 810 of FIG. 8 to the host computer 105 of FIG. 1. Alternatively, at block 1665, the in-memory compute controller 1005 of Figure 10 may apply an acceleration function to the data in the output stream, and at block 1670, the in-memory compute controller 1005 of Figure 10 The results of the acceleration function may be sent to the host computer 105 shown in Figure 1 .

In Figures 12A-16B, some embodiments of the inventive concept are shown. However, those skilled in the art will recognize that the inventive concept may have other aspects by changing the order of the blocks, by omitting blocks, or by including links not shown in the figures. Other examples. All such changes to the flow diagrams, whether expressly stated or not, are considered embodiments of the inventive concept.

Embodiments of the inventive concept provide technical advantages over prior art. In a conventional system, the decoded data is sent to the host computer 105 shown in Figure 1. Even if the data sent to the host computer 105 of FIG. 1 is selective (i.e., the data sent to the host computer 105 of FIG. 1 includes data of interest), the data is still uncompressed or unencoded. is sent, which means that space savings are achieved through selectivity. In contrast, because most storage reduction is achieved by encoding rather than compression, sending encoded data to the host computer 105 of FIG. 1 typically involves sending more decoded data to the host computer 105 of FIG. 1 Less data. Additionally, because data can be trans-encoded from one encoding scheme to another, using transcoder 420 shown in Figure 6 can be more efficient than decoding the data and re-encoding the data as separate operations.

The following discussion is intended to provide a brief general description of one or more suitable machines in which certain aspects of the present concepts may be implemented. The one or more machines may be controlled, at least in part, by input from traditional input devices such as keyboards and mice; as well as instructions received from another machine; and virtual reality (VR). Interaction with the environment, biometric feedback, or other input signals. As used herein, the term "machine" is intended to broadly include a single machine, a virtual machine, or multiple devices that are communicatively coupled to operate together, virtual machines, or collective operations. Exemplary machines include: computing devices such as personal computers, workstations, servers, portable computers, handheld devices, electronic phones, tablets, etc.; and transportation devices, such as private or public transportation (e.g. cars, trains, taxis, etc.).

The one or more machines may include embedded controllers, such as programmable or non-programmable logic devices or arrays, Application Specific Integrated Circuits (ASICs), embedded computers, smart cards, etc. The one or more machines may utilize one or more connections to one or more remote machines (eg, via a network interface, modem, or other communicative coupling). Machines may be interconnected through physical and/or logical networks such as an intranet, the Internet, a local area network, a wide area network, etc. Those familiar with this technology will understand that network communications may utilize a variety of wired and/or wireless short-range or long-range carriers and protocols, including radio frequency (RF), satellite, microwave, IEEE (Institute of Electrical and Electronics Engineers) Institute of Electrical and Electronics Engineers (IEEE) 802.11, Bluetooth®, optical, infrared, cable, laser, etc.

Embodiments of the inventive concepts may be illustrated by reference to or in conjunction with associated information, including functionality that, when accessed by a machine, causes the machine to perform tasks or define abstract data types or low-level hardware contexts, Programs, data structures, applications, etc. The associated data may be stored in, for example, volatile and/or non-volatile memory (e.g., RAM, ROM, etc.), or may be stored in devices including hard drives, floppy disks, optical storage, and tapes. , flash memory, memory stick, digital video disk, biological memory and other storage devices and their associated storage media. Related data may be transmitted in the form of packets, serial data, parallel data, propagation signals, etc. via physical and/or logical networks. environment and can be used in compressed or encrypted formats. The associated data may be used in a distributed environment and may be stored locally and/or remotely for machine access.

Embodiments of the inventive concepts may include tangible, non-transitory, machine-readable medium containing instructions executable by one or more processors, including instructions for performing the inventive concepts described herein. Element instructions.

The various operations of the methods described above may be performed by any suitable means capable of performing the operations (eg, various hardware and/or software components, circuits and/or modules). The software may include an ordered list of executable instructions for implementing logical functions, and may be implemented on any "processor-readable medium" for instruction execution system, apparatus or device (e.g., single-core or multi-core). A core processor or a system containing a processor) is used by or in conjunction with an instruction execution system, device or device.

Blocks or steps of methods or algorithms and functions described in conjunction with the embodiments disclosed herein may be implemented directly in hardware, in software modules executed by a processor, or in a combination of the two. If implemented in software, the functions may be stored on or transmitted over a tangible non-transitory computer-readable medium as one or more instructions or code. Software modules can reside in random access memory (RAM), flash memory, read-only memory (ROM), electrically programmable ROM (Electrically Programmable ROM, EPROM), electrically erasable programmable ROM (Electrically Erasable Programmable ROM, EEPROM), scratchpad, hard disk, removable disk, Compact Disc Read Only Memory (Compact Disc Read Only Memory, CD ROM) or any other form known in the art storage media in the body.

Having described and illustrated the principles of the inventive concept with reference to the illustrated embodiments, it will be recognized that the illustrated embodiments may be modified in arrangement and detail and may be modified in any desired manner without departing from such principles. ways to combine. Also, although the above discussion focuses on specific embodiments, other configurations are contemplated. Specifically, although phrases such as "embodiments according to the inventive concept" or similar phrases are used herein, these phrases are intended to refer to embodiment possibilities in general and are not intended to limit the inventive concept to specific embodiments. configuration. As used herein, these terms may refer to the same or different embodiments that may be combined into other embodiments.

The foregoing illustrative embodiments should not be considered as limiting the inventive concept. Although several embodiments have been described, those skilled in the art will readily appreciate that many modifications may be made to the embodiments without materially departing from the novel teachings and advantages of the invention. Accordingly, all such modifications are intended to be included within the scope of the inventive concept as defined by the claims.

Embodiments of the inventive concept may be extended to the following statements and are not limited thereto:

Statement 1. Embodiments of the inventive concept include a transform encoder including: a buffer for storing input encoded data; an index mapper for mapping from an input dictionary to an output dictionary; a current encoding buffer A device configured to store modified currently encoded data in response to the input encoded data, the input an input dictionary and a mapping from the input dictionary to the output dictionary; a previously encoded buffer to store modified previously encoded data in response to previously input encoded data, the input dictionary and the mapping from the input dictionary to the output dictionary; and a rule evaluator to respond to the modified currently encoded data in the current encoding buffer, the previously The modified previously encoded data in the encoding buffer and the conversion encoding rules are used to generate an output stream.

Statement 2. An embodiment of the inventive concept includes a transform encoder as described in Statement 1, wherein said index mapper is responsive to said transform encoding rules.

Statement 3. Embodiments of the inventive concept include the transform encoder of Statement 1, wherein the transform encoding rules are responsive to the index mapper.

Statement 4. An embodiment of the inventive concept includes a transform encoder as described in Statement 1, wherein the index mapper is responsive to a selected subset of entries in the input dictionary.

Statement 5. Embodiments of the inventive concept include the transform encoder of Statement 1, wherein the rule evaluator includes a processor, a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), a graphics At least one of a processing unit (GPU) or a general purpose GPU (GPGPU).

Statement 6. Embodiments of the inventive concept include the transform encoder of Statement 5, wherein the rule evaluator further includes software for implementing the transform encoding rules and a table listing the transform encoding rules. At least one of the storages.

Statement 7. Embodiments of the inventive concept include transcoding as described in Statement 5 device, wherein the rule evaluator further includes a circuit system for implementing the conversion encoding rule.

Statement 8. An embodiment of the inventive concept includes the transform encoder of Statement 1, wherein the rule evaluator operates to generate the modified currently encoded data from the input encoded material using the transform encoding rules. material.

Statement 9. An embodiment of the inventive concept includes the transcoder of Statement 8, wherein the rule evaluator operates to add the modified previously encoded material to the output stream.

Statement 10. Embodiments of the inventive concept include the transform encoder of Statement 9, wherein the rule evaluator is further operative to move the modified currently encoded data from the current encoding buffer to the The modified previously encoded material in the previously encoded buffer.

Statement 11. An embodiment of the inventive concept includes the transform encoder of Statement 8, wherein the rule evaluator operates to modify the modified previously encoded material to include the modification using the transform encoding rules The current encoded data after.

Statement 12. Embodiments of the inventive concept include the transform encoder of Statement 11, wherein the rule evaluator is further operative to convert a third of the input encoded data when generating the modified currently encoded data. One encoding scheme is changed to a second encoding scheme.

Statement 13. Embodiments of the inventive concept include the transform encoder of Statement 11, wherein the rule evaluator is further operative to generate the modified currently encoded When encoding the data, the modified first encoding scheme of the previously encoded data is changed into a second encoding scheme.

Statement 14. An embodiment of the inventive concept includes the transform encoder of Statement 8, wherein the rule evaluator operates to determine a first encoding scheme for the input encoded data from the input encoded data, said The first encoding scheme is one of at least two encoding schemes used by the input encoded data.

Statement 15. Embodiments of the inventive concept include the transcoder of Statement 1, further comprising a stream separator configured to identify a first bit of the input encoded data using a first encoding scheme. Chunks and a second chunk of the input encoded data using a second encoding scheme.

Statement 16. An embodiment of the inventive concept includes the transform encoder of Statement 1, wherein the index mapper operates to map at least one entry in the input dictionary to a "don't care" in the output dictionary value.

Statement 17. An embodiment of the inventive concept includes the transform encoder of Statement 1, wherein the index mapper operates to add a "don't care" value to the output dictionary.

Statement 18. Embodiments of the inventive concept include the transcoder of Statement 1, wherein: the input encoded data is compressed input encoded data; and the transcoder further includes a decompression engine.

Statement 19. Embodiments of the inventive concept include a transcoder as described in Statement 1, wherein said transcoder operates to operate without encoding said input encoded data. Decoding produces the output stream from the input encoded data.

Statement 20. Embodiments of the inventive concept include the transcoder of Statement 1, wherein the transcoder is included in a solid state drive (SSD) storage device.

Statement 21. Embodiments of the inventive concept include the transcoder of Statement 20, wherein the input encoded data is received from storage within the SSD storage device.

Statement 22. An embodiment of the inventive concept includes a method comprising: receiving a first data chunk from input encoded data from a storage device at a transcoder; determining a host computer's response to the first data chunk interested; generating first encoded data from the first data chunk based at least in part on the host computer's interest in the first data chunk; receiving from the storage device at the transcoder a second chunk of data from the input encoded data; determining that a host computer is not interested in the second chunk of data; and deriving from the second chunk of data based at least in part on the host computer not being interested in the second chunk of data. Chunking generates second encoded data; and outputs the first encoded data and the second encoded data to the host computer.

Statement 23. Embodiments of the inventive concept include the method of Statement 22, wherein a second data chunk is generated from the second data chunk based at least in part on the host computer not being interested in the second data chunk. Encoding information includes converting said first encoded The values in the data are changed to "ignore" values.

Statement 24. Embodiments of the inventive concept include the method of Statement 23, wherein a second data chunk is generated from the second data chunk based at least in part on the host computer having no interest in the second data chunk. Encoding the data further includes combining the second encoded data with third encoded data including the "don't care" value.

Statement 25. Embodiments of the inventive concept include the method of Statement 24, wherein a second data chunk is generated from the second data chunk based at least in part on the host computer not being interested in the second data chunk. Encoding the data further includes changing a first encoding scheme of at least one of the second data chunk and the third encoded data to a second encoding scheme.

Statement 26. Embodiments of the inventive concept include the method of Statement 25, wherein the first encoding scheme of at least one of the second chunk of data and the third encoded data is changed to a second encoding The scheme includes changing a first coding scheme of the second chunk of data to a second coding scheme in the second encoded material.

Statement 27. Embodiments of the inventive concept include the method of Statement 25, wherein the first encoding scheme of at least one of the second chunk of data and the third encoded data is changed to a second encoding The scheme includes changing the first encoding scheme of the third encoded material to a second encoding scheme.

Statement 28. Embodiments of the inventive concept include the method of Statement 22, wherein a first data chunk is generated from the first data chunk based at least in part on the host computer's interest in the first data chunk. Encoding data includes combining the first encoded data and third encoded data.

Statement 29. Embodiments of the inventive concept include the method of Statement 28, wherein a first data chunk is generated from the first data chunk based at least in part on the host computer's interest in the first data chunk. Encoding the data further includes changing a first encoding scheme of at least one of the first data chunk and the third encoded data to a second encoding scheme.

Statement 30. Embodiments of the inventive concept include the method of Statement 29, wherein a first encoding scheme of at least one of the first chunk of data and the third encoded data is changed to a second encoding The scheme includes changing a first coding scheme of the first chunk of data to a second coding scheme in the first encoded material.

Statement 31. Embodiments of the inventive concept include the method of Statement 29, wherein a first encoding scheme of at least one of the first chunk of data and the third encoded data is changed to a second encoding The scheme includes changing the first encoding scheme of the third encoded material to a second encoding scheme.

Statement 32. Embodiments of the inventive concept include the method of Statement 22, wherein a first data chunk is generated from the first data chunk based at least in part on the host computer's interest in the first data chunk. Encoding the material includes generating the first encoded material from the first chunk of data based at least in part on a transformation encoding rule; and generating the first encoded material based at least in part on the host computer having no interest in the second chunk of data. Generating second encoded material from the second chunk of data includes generating the second encoded material from the second chunk of data based at least in part on the transform encoding rules.

Statement 33. Embodiments of the inventive concept include the method of Statement 22, wherein Receiving the first data chunk from the input encoded data at the conversion encoder from the storage device includes: receiving the input encoded data at a stream demultiplexer; The first data chunk and the second data chunk are identified in the data, the first data chunk is encoded using a first encoding scheme, and the second data chunk is encoded using a second encoding scheme. Encoding; and receiving a first data chunk from the input encoded data from the destreamer.

Statement 34. Embodiments of the inventive concept include the method of Statement 22, further comprising: receiving an input dictionary from the storage device; based at least in part on information that is of interest to the host computer and information that is not of interest to the host computer. data to map the input dictionary to an output dictionary; and output the output dictionary to the host computer.

Statement 35. Embodiments of the inventive concept include the method of Statement 34, wherein the input dictionary is mapped to an output dictionary based at least in part on information that is of interest to the host computer and information that is not of interest to the host computer. Includes mapping the input dictionary to an output dictionary based at least in part on a transformation encoding rule.

Statement 36. Embodiments of the inventive concept include the method of Statement 34, wherein the input dictionary is mapped to an output dictionary based at least in part on information that is of interest to the host computer and information that is not of interest to the host computer. including at least in part The input dictionary is mapped to an output dictionary based on a selected subset of entries in the input dictionary.

Statement 37. Embodiments of the inventive concept include the method of Statement 22, wherein the transcoder operates to generate the first encoded data from the input encoded data without decoding the input encoded data. one encoded data and said second encoded data.

Statement 38. Embodiments of the inventive concept include the method of Statement 22, wherein the transcoder is included in a solid state drive (SSD) storage device.

Statement 39. Embodiments of the inventive concept include the method of Statement 38, wherein receiving the first data chunk from the input encoded data at the transform encoder from the storage device includes receiving at the transform encoder from the storage device. Storage within the SSD storage device receives the first chunk of data from the input encoded data; and receiving second data from the storage device at the transcoder from the input encoded data Chunking includes receiving, at the transcoder, the second data chunk from the input encoded data from the storage within the SSD storage device.

Statement 40. Embodiments of the inventive concept include an article of manufacture including a non-transitory storage medium having instructions stored thereon that, when executed by a machine, cause: at a transcoder receiving a first data chunk from the input encoded data from the storage device; determining that the host computer is interested in the first data chunk; generating first encoded data from the first data chunk based at least in part on the host computer's interest in the first data chunk; in the converting receiving at an encoder a second data chunk from the input encoded data from the storage device; determining that the host computer is not interested in the second data chunk; based at least in part on the host computer's interest in the second data chunk The second data chunk is not of interest and second encoded data is generated from the second data chunk; and the first encoded data and the second encoded data are output to the host computer.

Statement 41. An embodiment of the inventive concept includes the article of Statement 40, wherein a second data chunk is generated from the second data chunk based at least in part on the host computer not being interested in the second data chunk. Encoding data includes changing values in the first encoded data to "don't care" values.

Statement 42. Embodiments of the inventive concept include the article of Statement 41, wherein a second data chunk is generated from the second data chunk based at least in part on the host computer having no interest in the second data chunk. Encoding the data further includes combining the second encoded data with third encoded data including a "don't care" value.

Statement 43. Embodiments of the inventive concept include the article of Statement 42, wherein a second data chunk is generated from the second data chunk based at least in part on the host computer having no interest in the second data chunk. Encoding the data further includes changing the first encoding scheme of at least one of the second data chunk and the third encoded data to Second coding scheme.

Statement 44. Embodiments of the inventive concept include the article of Statement 43, wherein the first encoding scheme of at least one of the second chunk of data and the third encoded data is changed to a second encoding The scheme includes changing a first coding scheme of the second chunk of data to a second coding scheme in the second encoded material.

Statement 45. Embodiments of the inventive concept include the article of Statement 43, wherein the first encoding scheme of at least one of the second chunk of data and the third encoded data is changed to a second encoding The scheme includes changing the first encoding scheme of the third encoded material to a second encoding scheme.

Statement 46. An embodiment of the inventive concept includes the article of statement 40, wherein a first data chunk is generated from the first data chunk based at least in part on the host computer's interest in the first data chunk. Encoding data includes combining the first encoded data and third encoded data.

Statement 47. An embodiment of the inventive concept includes the article of Statement 46, wherein a first data chunk is generated from the first data chunk based at least in part on the host computer's interest in the first data chunk. Encoding the data further includes changing a first encoding scheme of at least one of the first data chunk and the third encoded data to a second encoding scheme.

Statement 48. Embodiments of the inventive concept include the article of Statement 47, wherein a first encoding scheme of at least one of the first chunk of data and the third encoded data is changed to a second encoding The scheme includes changing a first coding scheme of the first chunk of data to a second coding scheme in the first encoded material.

Statement 49. Embodiments of the inventive concept include the article of Statement 47, wherein a first encoding scheme of at least one of the first chunk of data and the third encoded data is changed to a second encoding The scheme includes changing the first encoding scheme of the third encoded material to a second encoding scheme.

Statement 50. An embodiment of the inventive concept includes the article of Statement 40, wherein a first data chunk is generated from the first data chunk based at least in part on the host computer's interest in the first data chunk. Encoding the material includes generating the first encoded material from the first chunk of data based at least in part on a transformation encoding rule; and generating the first encoded material based at least in part on the host computer having no interest in the second chunk of data. Generating second encoded material from the second chunk of data includes generating the second encoded material from the second chunk of data based at least in part on the transform encoding rules.

Statement 51. Embodiments of the inventive concept include the article of statement 40, wherein receiving the first data chunk from the input encoded data at the transcoder from the storage device includes: receiving at the destreamer the Input encoded data; the stream demultiplexer identifies the first data chunk and the second data chunk in the input encoded data, the first data chunk using a first encoding scheme is encoded, and the second data chunk is encoded using a second encoding scheme; and receiving the first data chunk from the input encoded data from the destreamer.

Statement 52. Embodiments of the inventive concept include the article of statement 40, the non-transitory storage medium having further instructions stored thereon that, when executed by a machine, cause: receiving an input dictionary from the storage device ; Mapping the input dictionary to an output dictionary based at least in part on information that is of interest to the host computer and information that is not of interest to the host computer; and outputting the output dictionary to the host computer.

Statement 53. An embodiment of the inventive concept includes the article of Statement 52, wherein the input dictionary is mapped to an output dictionary based at least in part on information that is of interest to the host computer and information that is not of interest to the host computer. Includes mapping the input dictionary to an output dictionary based at least in part on a transformation encoding rule.

Statement 54. An embodiment of the inventive concept includes the article of statement 52, wherein the input dictionary is mapped to an output dictionary based at least in part on information that is of interest to the host computer and information that is not of interest to the host computer. Includes mapping the input dictionary to an output dictionary based at least in part on a selected subset of entries in the input dictionary.

Statement 55. Embodiments of the inventive concept include the article of Statement 40, wherein the transcoder operates to generate the first encoded data from the input encoded data without decoding the input encoded data. one encoded data and said second encoded data.

Statement 56. Embodiments of the inventive concept include the article of statement 40, wherein the transcoder is included in a solid state drive (SSD) storage device.

Statement 57. Embodiments of the inventive concept include the article of statement 56, wherein receiving the first data chunk from the input encoded data at the transform encoder from the storage device includes receiving at the transform encoder from the storage device. Storage within the SSD storage device receives the first chunk of data from the input encoded data; and receiving second data from the storage device at the transcoder from the input encoded data Chunking includes receiving, at the transcoder, the second data chunk from the input encoded data from the storage within the SSD storage device.

Statement 58. Embodiments of the inventive concept include a storage device including: a storage for inputting encoded data; a controller for processing read requests from a host computer on the storage; and a write request; an in-storage computing (ISC) controller to receive a predicate from the host computer that is to be applied to the input encoded data stored in the memory; and a transform encoder comprising an index mapper for mapping from an input dictionary of said input encoded material to an output dictionary, said input dictionary including at least one first entry and at least one second entry, The at least one first entry maps to at least a third entry in the output dictionary, and the at least one second entry maps to a "ignore" entry in the output dictionary.

Statement 59. An embodiment of the inventive concept includes the storage device of Statement 58, wherein the transcoder includes a processor, a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), a graphics processing unit At least one of a unit (GPU) or a general-purpose GPU (GPGPU).

Statement 60. An embodiment of the inventive concept includes the storage device of Statement 58, wherein the ISC controller operates to apply an acceleration function to output encoded data from the transform encoder.

Statement 61. An embodiment of the inventive concept includes the storage device of Statement 60, wherein the ISC controller is further operative to convert a result of the acceleration function on the output encoded data from the transcoder output to the host computer.

Statement 62. An embodiment of the inventive concept includes the storage device of Statement 58, wherein the ISC controller operates to forward output encoded data of the transcoder to the host computer.

Statement 63. An embodiment of the inventive concept includes the storage device of Statement 62, wherein the ISC controller is further operative to forward the output dictionary to the host computer.

Statement 64. An embodiment of the inventive concept includes the storage device of Statement 58, wherein the transform encoder operates to operate based at least in part on the input encoded data and the conversion from the input dictionary to the output dictionary Mapping to generate output encoded data.

Statement 65. An embodiment of the inventive concept includes the storage device of Statement 64, wherein the transcoder includes: a buffer for storing the input encoded data; the index mapper; a current encoding buffer for storing modified currently encoded data, the modified currently encoded data being in response to the input Encoded data and the mapping from the input dictionary to the output dictionary; a previously encoded buffer to store modified previously encoded data in response to the previously input Encoded data and the mapping from the input dictionary to the output dictionary; and a rule evaluator to respond to the modified currently encoded data in the current encoding buffer, the previous encoding buffer The modified previously encoded data in the processor and the conversion encoding rules are used to generate an output stream.

Statement 66. Embodiments of the inventive concept include the storage device of Statement 65, wherein the conversion encoding rules are based at least in part on the predicates.

Statement 67. An embodiment of the inventive concept includes the storage device of Statement 65, wherein the rule evaluator responds to the current encoding buffer without decoding the input encoded data. The modified current encoded data, the modified previously encoded data in the previous encoding buffer, and the conversion encoding rule generate the output stream.

Statement 68. An embodiment of the inventive concept includes the storage device of Statement 64, wherein: the input encoded data uses a first encoding scheme; the output encoded data uses a second encoding scheme; and The second encoding scheme is different from the first encoding scheme.

Statement 69. An embodiment of the inventive concept includes the storage device of Statement 58, wherein the input encoded data is stored in the memory in a row format.

Statement 70. An embodiment of the inventive concept includes the storage device of Statement 69, wherein the input encoded data includes an input file stored using the Apache Parquet storage format.

Statement 71. An embodiment of the inventive concept includes the storage device of Statement 69, further comprising a row chunking processor for processing row chunks including the input encoded data and converting the row chunks. The input encoded data is forwarded to the conversion encoder.

Statement 72. An embodiment of the inventive concept includes the storage device of Statement 71, wherein the row chunking processor includes the transcoder.

Statement 73. An embodiment of the inventive concept includes the storage device of Statement 71, wherein the row block processor includes a processor, a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), At least one of a graphics processing unit (GPU) or a general purpose GPU (GPGPU).

Statement 74. An embodiment of the inventive concept includes the storage device of Statement 58, wherein the transform encoder operates to generate transform encoding rules to be applied to the input encoded data based at least in part on the predicate , thereby producing output encoded data.

Statement 75. Embodiments of the inventive concept include a storage device as described in Statement 74, wherein the transcoder operates to operate without performing any processing on the input encoded data. Decoding the output produces the encoded data.

Statement 76. An embodiment of the inventive concept includes a method comprising: receiving at a transform encoder a predicate to be applied to input encoded data; accessing an input dictionary of the input encoded data; identifying the at least one first entry in the input dictionary that is covered by the predicate and at least one second entry in the input dictionary that is not covered by the predicate; generating an output dictionary that excludes the input dictionary the at least one second entry not covered by the predicate, the conversion encoding dictionary including at least a third entry and a "ignore" entry; and the conversion encoder generates a dictionary map, the dictionary map converts The at least one first entry in the input dictionary is mapped to the at least one third entry in the output dictionary and the at least one first entry in the input dictionary that is not covered by the predicate Two entries map to the "ignore" entry in the output dictionary.

Statement 77. Embodiments of the inventive concept include the method of Statement 76, wherein the input encoded data is stored in a line format.

Statement 78. Embodiments of the inventive concept include the method of Statement 77, wherein the input encoded data includes an input file stored using the Apache Parquet storage format.

Statement 79. Embodiments of the inventive concept include the method of Statement 76, wherein the input encoded data includes row chunks stored in a row format.

Statement 80. Embodiments of the inventive concept include the method of Statement 76, further comprising: Converting the input encoded data into output encoded data using the dictionary mapping; and outputting the output encoded data.

Statement 81. Embodiments of the inventive concept include the method of Statement 80, wherein trans-encoding the input encoded material into output encoded material using the dictionary map includes: receiving at the transcoder from the said inputting a first data chunk of encoded data; determining said first data chunk is covered by said predicate; using said dictionary mapping, based at least in part on said host computer computer's mapping of said first data chunk generating first encoded data from the first data chunk of interest; receiving a second data chunk from the input encoded data at the transcoder from the storage device; determining the second a chunk of data is not covered by the predicate; using the dictionary mapping, a second encoded chunk is generated from the second chunk of data based at least in part on the host computer not being interested in the second chunk of data data; and outputting the first encoded data and the second encoded data.

Statement 82. Embodiments of the inventive concept include the method of Statement 81, wherein receiving at the transcoder a first chunk of data from the input encoded data includes: At the row chunking processor, a chunk identifier (ID) list is received from an in-storage compute (ISC) controller; the row chunking processor accesses a region including the chunk ID list. row chunks of block IDs; retrieving the input encoded data from the row chunks by the row chunk processor; and forwarding the input encoded data from the row chunk processor to the Conversion encoder.

Statement 83. Embodiments of the inventive concept include the method of Statement 81, further comprising generating transform encoding rules to be applied to the input encoded data based at least in part on the predicates.

Statement 84. Embodiments of the inventive concept include the method of Statement 80, wherein transcoding the input encoded material into output encoded material using the dictionary map includes performing decoding of the input encoded material without decoding the input encoded material. In this case, the dictionary mapping is used to convert and encode the input encoded data into output encoded data.

Statement 85. Embodiments of the inventive concept include the method of Statement 80, wherein: the input encoded material uses a first encoding scheme; the output encoded material uses a second encoding scheme; and the second encoding The scheme is different from the first encoding scheme.

Statement 86. Embodiments of the inventive concept include the method of Statement 80, wherein outputting the output encoded data includes outputting the output encoded data to ISC controller.

Statement 87. Embodiments of the inventive concept include the method of Statement 86, wherein outputting the output encoded data to the ISC controller further includes outputting the output dictionary to the ISC controller.

Statement 88. Embodiments of the inventive concept include the method of Statement 87, further comprising forwarding the output encoded data and the output dictionary from the ISC controller to a host computer.

Statement 89. Embodiments of the inventive concept include the method of Statement 87, further comprising performing, by the ISC controller, an acceleration function on the output encoded data to generate accelerated data.

Statement 90. Embodiments of the inventive concept include the method of Statement 89, further comprising outputting the accelerated data from the ISC controller to a host computer.

Statement 91. Embodiments of the inventive concept include the method of Statement 76, further comprising outputting the output dictionary.

Statement 92. Embodiments of the inventive concept include the method of Statement 76, wherein receiving a predicate to be applied to input encoded data includes receiving the predicate to be applied to the input encoded data from an ISC controller .

Statement 93. Embodiments of the inventive concept include the method of Statement 92, further comprising receiving the input dictionary from the ISC controller.

Statement 94. Embodiments of the inventive concept include the method of Statement 76, further comprising: determining that there are no entries in the input dictionary that are not covered by the predicate; and The input encoded data is output without converting the encoding into output encoded data.

Statement 95. An embodiment of the inventive concept includes an article comprising a non-transitory storage medium having instructions stored thereon that, when executed by a machine, cause: at a transcoder receiving a predicate to be applied to the input encoded data; accessing an input dictionary of the input encoded data; identifying at least a first entry in the input dictionary covered by the predicate and an entry in the input dictionary that is not at least one second entry covered by the predicate; generating an output dictionary excluding the at least one second entry in the input dictionary that is not covered by the predicate, converting the encoding dictionary including at least The third entry and the "ignore" entry; and generating, by the transform encoder, a dictionary map mapping the at least one first entry in the input dictionary to all entries in the output dictionary. and mapping the at least one second entry in the input dictionary that is not covered by the predicate to the "ignore" entry in the output dictionary.

Statement 96. Embodiments of the inventive concept include the article of statement 95, wherein the input encoded data is stored in a line format.

Statement 97. Embodiments of the inventive concept include the article of statement 96, wherein the input encoded data includes an input file stored using the Apache Parquet storage format.

Statement 98. Embodiments of the inventive concept include the article of statement 95, wherein The input encoded data described in includes row chunks stored in row format.

Statement 99. Embodiments of the inventive concept include the article of statement 95, the non-transitory storage medium having further instructions stored thereon that, when executed by a machine, cause: using the dictionary map to convert the converting input encoded data into output encoded data; and outputting the output encoded data.

Statement 100. Embodiments of the inventive concept include the article of statement 99, wherein transcoding the input encoded material into output encoded material using the dictionary map includes: receiving at the transcoder from the Describing inputting a first data chunk of encoded data; determining that the first data chunk is covered by the predicate; using the dictionary mapping, based at least in part on the host computer's sense of the first data chunk generating first encoded data from the first data chunk; receiving at the transcoder from the storage device a second data chunk from the input encoded data; determining the second data a chunk is not covered by the predicate; generating second encoded material from the second chunk of data based at least in part on the host computer not being interested in the second chunk of data using the dictionary mapping; and outputting the first encoded data and the second encoded data.

Statement 101. Embodiments of the inventive concept include the article of statement 100, wherein receiving at the transform encoder a first chunk of data from the input encoded data includes: at a row chunk processor, receiving a list of block identifiers (IDs) from an in-storage compute (ISC) controller; accessing, by the row chunk processor, a row chunk that includes a chunk ID in the list of row chunks; by the row chunk processor A block processor retrieves the input encoded data from the row chunks; and forwards the input encoded data from the row chunk processor to the transform encoder.

Statement 102. Embodiments of the inventive concept include the article of statement 100, the non-transitory storage medium having further instructions stored thereon that, when executed by a machine, cause Transform encoding rules are generated to be applied to the input encoded data.

Statement 103. Embodiments of the inventive concept include the article of statement 99, wherein using the dictionary mapping to trans-encode the input encoded material into output encoded material includes without decoding the input encoded material. In this case, the dictionary mapping is used to convert and encode the input encoded data into output encoded data.

Statement 104. Embodiments of the inventive concept include the article of statement 99, wherein: the input encoded material uses a first encoding scheme; The output encoded data uses a second encoding scheme; and the second encoding scheme is different from the first encoding scheme.

Statement 105. Embodiments of the inventive concept include the article of statement 99, wherein outputting the output encoded data includes outputting the output encoded data to an ISC controller.

Statement 106. Embodiments of the inventive concept include the article of statement 105, wherein outputting the output encoded data to the ISC controller further includes outputting the output dictionary to the ISC controller.

Statement 107. Embodiments of the inventive concept include the article of statement 106, the non-transitory storage medium having further instructions stored thereon that, when executed by a machine, cause the output encoded data and the The output dictionary is forwarded from the ISC controller to the host computer.

Statement 108. Embodiments of the inventive concept include the article of statement 106, the non-transitory storage medium having further instructions stored thereon that, when executed by a machine, cause the ISC controller to Outputting the encoded data performs an acceleration function to produce accelerated data.

Statement 109. Embodiments of the inventive concept include the article of statement 108, the non-transitory storage medium having further instructions stored thereon that, when executed by a machine, cause the accelerated data to be transferred from the The ISC controller outputs to the host computer.

Statement 110. Embodiments of the inventive concept include the article of Statement 95, the non-transitory storage medium having further instructions stored thereon, the instructions being processed by a machine When executed, causes the output dictionary to be output.

Statement 111. Embodiments of the inventive concept include the article of Statement 95, wherein receiving a predicate to be applied to input encoded data includes receiving from an ISC controller the predicate to be applied to the input encoded data. .

Statement 112. Embodiments of the inventive concept include the article of statement 111, the non-transitory storage medium having further instructions stored thereon, the instructions, when executed by a machine, cause receiving the Enter dictionary.

Statement 113. Embodiments of the inventive concept include the article of Statement 95, the non-transitory storage medium having further instructions stored on the non-transitory storage medium, the instructions, when executed by a machine, cause: determining that the input dictionary does not exist items not covered by the predicate; and outputting the input encoded data without converting the encoding into output encoded data.

Therefore, this detailed description and accompanying materials are intended to be illustrative only and should not be construed as limiting the scope of the inventive concept in view of various modifications of the embodiments described herein. Therefore, the patentable scope claimed as the concept of the present invention is all the above modifications, and the above modifications can be attributed to the scope and spirit of the following patentable scope and its equivalents.

420:Convert encoder

605: Circular buffer/buffer

610:Stream splitter

615:Index mapper

620: Current encoding buffer

625: Previous encoding buffer

630:Conversion encoding rules

635: Rule evaluator

Claims (20)

A conversion encoder includes: a buffer for storing input encoded data; an index mapper for mapping from an input dictionary to an output dictionary; a current encoding buffer for storing modified current encoded data, said The modified currently encoded data is in response to the input encoded data, the input dictionary, and the mapping from the input dictionary to the output dictionary; a previously encoded buffer is used to store the modified previously encoded data. encoding data, said modified previously encoded data being responsive to previously input encoded data, said input dictionary, and said mapping from said input dictionary to said output dictionary; and a rule evaluator configured to respond to The modified current encoded data in the current encoding buffer, the modified previously encoded data in the previous encoding buffer and the conversion encoding rule generate an output stream. The conversion encoder of claim 1, wherein the rule evaluator includes at least one of a processor, a field programmable gate array, an application special integrated circuit, a graphics processing unit, or a general graphics processing unit. The transform encoder of claim 1, wherein the rule evaluator operates to generate the modified current encoded data from the input encoded data using the transform encoding rules. The transform encoder of claim 3, wherein the rule evaluator operates to use the transform encoding rules to modify the modified previously encoded material to include the modified currently encoded material. The transform encoder of claim 4, wherein the rule evaluator is further operative to change a first encoding scheme of at least one of the input encoded data and the modified previously encoded data to a first encoding scheme. Two coding schemes. The conversion encoder of claim 1, further comprising a stream separator, the stream separator being used to identify the first chunk of the input encoded data using the first encoding scheme and the input encoded data. A second chunk using a second encoding scheme. The transform encoder of claim 1, wherein the index mapper operates to map at least one entry in the input dictionary to a "don't care" value in the output dictionary. The transcoder of claim 1, wherein the transcoder operates to generate the output stream from the input encoded data without decoding the input encoded data. A method of transcoding, comprising: receiving at a transcoder from a storage device a first chunk of data from input encoded data; determining that a host computer is interested in said first chunk of data; based at least in part on said A host computer is interested in the first data chunk and generates first encoded data from the first data chunk; receiving a third input encoded data from the storage device at the transcoder. two data chunks; determining that the host computer is not interested in the second data chunk; generating second encoded data from the second data chunk based at least in part on the host computer not being interested in the second data chunk; and combining the first encoded data and the second encoded data Data is output to the host computer. The method of claim 9, wherein generating the second encoded data from the second data chunk based at least in part on the host computer having no interest in the second data chunk includes converting the second data chunk to A value in encoded data is changed to a "don't care" value. The method of claim 10, wherein generating the second encoded data from the second data chunk based at least in part on the host computer not being interested in the second data chunk further includes converting the second data chunk to The second encoded data is combined with the third encoded data including the "don't care" value. The method of claim 11, wherein generating the second encoded data from the second data chunk based at least in part on the host computer not being interested in the second data chunk further includes converting the second data chunk to The first encoding scheme of at least one of the second data chunk and the third encoded data is changed to a second encoding scheme. The method of claim 9, wherein generating the first encoded data from the first data chunk based at least in part on the host computer's interest in the first data chunk includes converting the first data chunk to The first coded data is combined with the third coded data. The method of claim 13, based at least in part on The host computer is interested in the first data chunk and generates the first encoded data from the first data chunk further including combining the first data chunk and the third encoded data. The first encoding scheme of at least one of is changed to the second encoding scheme. The method of claim 9, wherein generating the first encoded material from the first data chunk based at least in part on the host computer's interest in the first data chunk includes based at least in part on converting encoding rules to generate the first encoded data from the first data chunk; and generating from the second data chunk based at least in part on the host computer not being interested in the second data chunk The second encoded material includes generating the second encoded material from the second chunk of data based at least in part on the transform encoding rules. The method of claim 9, wherein receiving the first data chunk from the input encoded data at the transcoder from the storage device includes receiving the input at a destreamer Encoded data; identifying the first data chunk and the second data chunk in the input encoded data by the stream separator, the first data chunk being encoded using a first encoding scheme encoding, and the second data chunk is encoded using a second encoding scheme; and receiving the first data chunk from the input encoded data from the destreamer. The method described in request item 9 further includes: receiving an input dictionary from the storage device; mapping the input dictionary to an output dictionary based at least in part on information of interest to the host computer and information of interest to the host computer; and outputting the output dictionary to the Describe the host computer. The method of claim 9, wherein the transcoder operates to generate the first encoded data and the second encoded data from the input encoded data without decoding the input encoded data. Encoded data. An article of manufacture for conversion encoding, comprising a non-transitory storage medium having instructions stored thereon that, when executed by a machine, cause: receiving at a conversion encoder input encoded data from a storage device a first data chunk; determining that a host computer is interested in the first data chunk; and generating a third data chunk from the first data chunk based at least in part on the host computer's interest in the first data chunk. an encoded data; receiving a second data chunk from the input encoded data from the storage device at the conversion encoder; determining that the host computer is not interested in the second data chunk; at least in part Generating second encoded data from the second data chunk based on the host computer not being interested in the second data chunk; and outputting the first encoded data and the second encoded data to the host computer. The article of claim 19, wherein generating the second encoded data from the second data chunk based at least in part on the host computer having no interest in the second data chunk includes converting the second data chunk to A value in encoded data is changed to a "don't care" value.

Images