Accelerated operations on compressed data stores
A data operations system receives compressed data and a search term. The data operations system completes a modified decoding of the compressed data, resulting in distinguishable data terms that are smaller than the corresponding data terms, and loads modified decoded terms into a data register. The data operations system generates a truncated search term and loads instances of the truncated search term into a query register. The data operations system performs a parallel data operation, such as a query operation, by comparing each of the modified decoded terms to an instance of the truncated search term. The data operations system returns the results of the operation.
1. A method of performing a query operation on compressed data, comprising:
receiving, at a query system comprising a query register and a data register, each having a bit-width, and a plurality of selectable bit-width operations:
from a data compression system, a plurality of prefix terms;
from the data compression system, a delta compressed data block corresponding to an uncompressed data block, the uncompressed data block comprising a plurality of numerically ordered terms, wherein the delta compressed data block comprises a plurality of numerically ordered delta terms, wherein each of the numerically ordered delta terms corresponds to a difference between one of the plurality of prefix terms and one of the plurality of the numerically ordered terms; and
from a requesting system, a search term;
determining, by the query system, that the search term is present in the uncompressed data block, the determining comprising:
determining a target word size based on a range corresponding to the delta compressed data block and on the plurality of selectable bit-width operations;
generating a plurality of truncated prefix terms based on the plurality of prefix terms;
generating a plurality of modified decoded terms, each of the plurality of modified decoded terms based on a corresponding delta term and on one of the plurality of truncated prefix terms;
generating a truncated search term based on the search term and on the target word size;
determining a load count based on the target word size and on the data register bit-width;
loading the data register with the load count number of modified decoded terms;
loading the query register with the load count number of instances of the truncated search term; and
performing a parallel compare operation comparing each modified decoded term in the data register with a corresponding truncated search term in the query register; and
responsive to determining that the search term is present in the uncompressed data block, returning a result of the compare operation to the requesting system.
2. The method of claim 1 , wherein the uncompressed data block comprises a plurality of entity identifiers, and wherein the search term is a specific entity identifier.
3. The method of claim 1 , wherein the target word size corresponds to a smallest of the selectable bit-width operations that is at least as large as a minimum number of bits required to represent the range.
4. The method of claim 1 , wherein determining a target word size based on the range further comprises determining the range.
5. The method of claim 1 , wherein each of the plurality of modified decoded terms, the truncated prefix term, and the truncated search term comprises a number of least significant bits corresponding to the target word size.
6. The method of claim 1 , wherein returning the result comprises returning an uncompressed data term corresponding to a modified decoded term which matches the truncated search term.
7. The method of claim 1 , wherein the delta compressed data block is a first delta compressed data block, the uncompressed data block is a first uncompressed data block, the plurality of numerically ordered delta terms is a first plurality of numerically ordered delta terms, the target word size is a first target word size, the range is a first range, the plurality of prefix terms is a first plurality of prefix terms, the plurality of truncated prefix terms is a first plurality of truncated prefix terms, the truncated search term is a first truncated search term, the load count is a first load count, and the compare operation is the first compare operation, and further comprising:
receiving, at the query system:
from the data compression system, a second plurality of prefix terms;
from the data compression system, a second delta compressed data block corresponding to a second uncompressed data block, the second uncompressed data block comprising a second plurality of numerically ordered terms, wherein the second delta compressed data block comprises a second plurality of numerically ordered delta terms, wherein each of the second plurality of numerically ordered delta terms corresponds to a difference between one of the second plurality of prefix terms and one of the second plurality of numerically ordered terms, wherein a second range corresponding to the second delta compressed data block is different than the first range;
determining, by the query system, that the search term is present in the second uncompressed data block, the determining comprising:
determining a second target word size based on the second range and on the plurality of selectable bit-width operations, wherein the second target word size is different than the first target word size;
generating a second plurality of truncated prefix terms based on the second plurality of prefix terms;
generating a second plurality of modified decoded terms, each of the second plurality of modified decoded terms based on a corresponding delta term of the second plurality of delta terms and on one of the second plurality of truncated prefix terms;
generating a second truncated search term based on the search term and on the second target word size;
determining a second load count based on the second target word size and on the data register bit-width;
loading the data register with the second load count number of the second plurality of modified decoded terms;
loading the query register with the second load count number of instances of the second truncated search term; and
performing a second parallel compare operation comparing each of the second plurality of modified decoded terms in the data register with a corresponding second truncated search term in the query register; and
responsive to determining that the search term is present in the second uncompressed data block, returning a result of the compare operation to the requesting system, wherein the result of the compare operation comprises a result based on the first compare operation and the second compare operation.
8. A non-transitory computer-readable storage medium storing processor-executable computer program instructions that, when executed, cause a computer processor to perform a method, the method comprising:
receiving, at a query system comprising a query register and a data register, each having a bit-width, and a plurality of selectable bit-width operations:
from a data compression system, a plurality of prefix terms;
from the data compression system, a delta compressed data block corresponding to an uncompressed data block, the uncompressed data block comprising a plurality of numerically ordered terms, wherein the delta compressed data block comprises a plurality of numerically ordered delta terms, wherein each of the numerically ordered delta terms corresponds to a difference between one of the plurality of prefix terms and one of the plurality of the numerically ordered terms; and
from a requesting system, a search term;
determining, by the query system, that the search term is present in the uncompressed data block, the determining comprising:
determining a target word size based on a range corresponding to the delta compressed data block and on the plurality of selectable bit-width operations;
generating a plurality of truncated prefix terms based on the plurality of prefix terms;
generating a plurality of modified decoded terms, each of the plurality of modified decoded terms based on a corresponding delta terms and on one of the plurality of truncated prefix terms;
generating a truncated search term based on the search term and on the target word size;
determining a load count based on the target word size and on the data register bit-width;
loading the data register with the load count number of modified decoded terms;
loading the query register with the load count number of instances of the truncated search term; and
performing a parallel compare operation comparing each modified decoded term in the data register with a corresponding truncated search term in the query register; and
responsive to determining that the search term is present in the uncompressed data block, returning a result of the compare operation to the requesting system.
9. The medium of claim 8 , wherein the uncompressed data block comprises a plurality of entity identifiers each corresponding to an entity, and wherein the search term is a specific entity identifier.
10. The medium of claim 8 , wherein the target word size corresponds to a smallest of the selectable bit-width operations that is at least as large as a minimum number of bits required to represent the range.
11. The medium of claim 8 , wherein determining a target word size based on the range further comprises determining the range.
12. The medium of claim 8 , wherein each of the plurality of modified decoded terms, the truncated prefix term, and the truncated search term comprises a number of least significant bits corresponding to the target word size.
13. The medium of claim 8 , wherein returning the result comprises returning an uncompressed data term corresponding to a modified decoded term which matches the truncated search term.
14. The medium of claim 8 , wherein the delta compressed data block is a first delta compressed data block, the uncompressed data block is a first uncompressed data block, the plurality of numerically ordered delta terms is a first plurality of numerically ordered delta terms, the target word size is a first target word size, the range is a first range, the prefix term is a first prefix term, the truncated prefix term is a first truncated prefix term, the truncated search term is a first truncated search term, the load count is a first load count, and the compare operation is the first compare operation, and the method further comprising:
receiving, at the query system:
from the data compression system, a second plurality of prefix terms;
from the data compression system, a second delta compressed data block corresponding to a second uncompressed data block, the second uncompressed data block comprising a second plurality of numerically ordered terms, wherein the second delta compressed data block comprises a second plurality of numerically ordered delta terms, wherein each of the second plurality of numerically ordered delta terms corresponds to a difference between one of the second plurality of prefix terms and one of the second plurality of numerically ordered terms, wherein a second range corresponding to the second delta compressed data block is different than the first range;
determining, by the query system, that the search term is present in the second uncompressed data block, the determining comprising:
determining a second target word size based on the second range and on the plurality of selectable bit-width operations, wherein the second target word size is different than the first target word size;
generating a second plurality of truncated prefix terms based on the second plurality of prefix terms;
generating a second plurality of modified decoded terms, each of the second plurality of modified decoded terms based on a corresponding delta term of the second plurality of delta terms and on one of the second plurality of truncated prefix terms;
generating a second truncated search term based on the search term and on the second target word size;
determining a second load count based on the second target word size and on the data register bit-width;
loading the data register with the second load count number of the second plurality of modified decoded terms;
loading the query register with the second load count number of instances of the second truncated search term; and
performing a second parallel compare operation comparing each of the second plurality of modified decoded terms in the data register with a corresponding second truncated search term in the query register; and
responsive to determining that the search term is present in the second uncompressed data block, returning a result of the compare operation to the requesting system.wherein the result of the compare operation comprises a result based on the first compare operation and the second compare operation.
15. A system comprising:
a processor; and
a non-transitory computer-readable storage medium storing processor-executable computer program instructions that, when executed, cause a computer processor to perform a method, the method comprising:
receiving, at a query system comprising a query register and a data register, each having a bit-width, and a plurality of selectable bit-width operations:
from a data compression system, a plurality of prefix terms;
from the data compression system, a delta compressed data block corresponding to an uncompressed data block, the uncompressed data block comprising a plurality of numerically ordered terms, wherein the delta compressed data block comprises a plurality of numerically ordered delta terms, wherein each of the numerically ordered delta terms corresponds to a difference between one of the plurality of prefix terms and one of the plurality of the numerically ordered terms; and
from a requesting system, a search term;
determining, by the query system, that the search term is present in the uncompressed data block, the determining comprising:
determining a target word size based on a range corresponding to the delta compressed data block and on the plurality of selectable bit-width operations;
generating a plurality of truncated prefix terms based on the plurality of prefix terms;
generating a plurality of modified decoded terms, each of the plurality of modified decoded terms based on the corresponding delta terms and on one of the plurality of truncated prefix terms;
generating a truncated search term based on the search term and on the target word size;
determining a load count based on the target word size and on the data register bit-width;
loading the data register with the load count number of modified decoded terms;
loading the query register with the load count number of instances of the truncated search term; and
performing a parallel compare operation comparing each modified decoded term in the data register with a corresponding truncated search term in the query register; and
responsive to determining that the search term is present in the uncompressed data block, returning a result of the compare operation to the requesting system.
16. The system of claim 15 , wherein the uncompressed data block comprises a plurality of entity identifiers each corresponding to an entity, and wherein the search term is a specific entity identifier.
17. The system of claim 15 , wherein the target word size corresponds to a smallest of the selectable bit-width operations that is at least as large as a minimum number of bits required to represent the range.
18. The system of claim 15 , wherein determining a target word size based on the range further comprises determining the range.
19. The system of claim 15 , wherein each of the plurality of modified decoded terms, the truncated prefix term, and the truncated search term comprises a number of least significant bits corresponding to the target word size.
20. The system of claim 15 , wherein returning the result comprises returning an uncompressed data term corresponding to a modified decoded term which matches the truncated search term.
21. The system of claim 15 , wherein the delta compressed data block is a first delta compressed data block, the uncompressed data block is a first uncompressed data block, the plurality of numerically ordered delta terms is a first plurality of numerically ordered delta terms, the target word size is a first target word size, the range is a first range, the prefix term is a first prefix term, the truncated prefix term is a first truncated prefix term, the truncated search term is a first truncated search term, the load count is a first load count, and the compare operation is the first compare operation, and the method further comprising:
receiving, at the query system:
from the data compression system, a second plurality of prefix terms;
from the data compression system, a second delta compressed data block corresponding to a second uncompressed data block, the second uncompressed data block comprising a second plurality of numerically ordered terms, wherein the second delta compressed data block comprises a second plurality of numerically ordered delta terms, wherein each of the second plurality of numerically ordered delta terms corresponds to a difference between one of the second plurality of prefix terms and one of the second plurality of numerically ordered terms, wherein a second range corresponding to the second delta compressed data block is different than the first range;
determining, by the query system, that the search term is present in the second uncompressed data block, the determining comprising:
determining a second target word size based on the second range and on the plurality of selectable bit-width operations, wherein the second target word size is different than the first target word size;
generating a second plurality of truncated prefix terms based on the second plurality of prefix terms;
generating a second plurality of modified decoded terms, each of the second plurality of modified decoded terms based on a corresponding delta term of the second plurality of delta terms and on one of the second plurality of truncated prefix terms;
generating a second truncated search term based on the search term and on the second target word size;
determining a second load count based on the second target word size and on the data register bit-width;
loading the data register with the second load count number of the second plurality of modified decoded terms;
loading the query register with the second load count number of instances of the second truncated search term; and
performing a second parallel compare operation comparing each of the second plurality of modified decoded terms in the data register with a corresponding second truncated search term in the query register; and
responsive to determining that the search term is present in the second uncompressed data block, returning a result of the compare operation to the requesting system, wherein the result of the compare operation comprises a result based on the first compare operation and the second compare operation.