Compression scheme for improving cache behavior in database systems
View Patent ↗The apparatuses and methods described herein may operate to identify, from an index structure stored in memory, a reference minimum bounding shape that encloses at least one minimum bounding shape. Each of the at least one minimum bounding shape may correspond to a data object associated with a leaf node of the index structure. Coordinates of a point of the at least one minimum bounding shape may be associated with a set of first values to produce a relative representation of the at least one minimum bounding shape. The set of first values may be calculated relative to coordinates of a reference point of the reference minimum bounding shape such that each of the set of first values comprises a first number of significant bits fewer than a second number of significant bits representing a second value associated with a corresponding one of absolute coordinates of the point.
1. A method, comprising:
identifying, from an index structure stored in memory, a reference minimum bounding shape that encloses a minimum bounding shape, the minimum bounding shape corresponding to a data object associated with a leaf node of the index structure;
associating, using one or more processors, coordinates of a point of the minimum bounding shape with a set of first values to produce a relative representation of the minimum bounding shape, the set of first values being calculated relative to coordinates of a reference point of the reference minimum bounding shape by calculating a difference between an absolute coordinate of the point of the minimum bounding shape and an absolute coordinate of the reference point; and
compressing the relative representation using a finite level of quantization by cutting off trailing insignificant bits to produce a quantized representation of the minimum bounding shape and storing the compressed relative representation in one or more nodes, the one or more nodes having a node size calculated dynamically based on historical query selectivity, wherein query selectivity is a measure of how much data is expected to be returned by a given query.
2. The method of claim 1 , wherein the higher the historical query selectivity, the larger the node size.
3. The method of claim 2 , wherein the greater the number of entries in the index structure, the larger the node size.
4. The method of claim 1 , wherein the node size is further calculated dynamically based upon number of entries in the index structure.
5. The method of claim 1 , wherein the compressing comprises:
choosing the finite level of quantization from a set of quantization levels.
6. The method of claim 1 , wherein the index structure comprises at least one of an R-tree, an R*-tree, an R+-tree or a Hilbert R-tree.
7. The method of claim 1 , further comprising:
responsive to a query, searching the index structure using the quantized representation.
8. A system, comprising:
memory to store an index structure; and
one or more processors configured to execute a compression engine, the compression engine configured to:
identify, from an index structure stored in memory, a reference minimum bounding shape that encloses a minimum bounding shape, the minimum bounding shape corresponding to a data object associated with a leaf node of the index structure;
associate, using one or more processors, coordinates of a point of the minimum bounding shape with a set of first values to produce a relative representation of the minimum bounding shape, the set of first values being calculated relative to coordinates of a reference point of the reference minimum bounding shape by calculating a difference between an absolute coordinate of the point of the minimum bounding shape and an absolute coordinate of the reference point; and
compress the relative representation using a finite level of quantization by cutting off trailing insignificant bits to produce a quantized representation of the minimum bounding shape and store the compressed relative representation in one or more nodes, the one or more nodes having a node size calculated dynamically based on historical query selectivity, wherein query selectivity is a measure of how much data is expected to be returned by a given query.
9. The system of claim 8 , wherein the higher the historical query selectivity, the larger the node size.
10. The system of claim 8 , wherein the node size is further calculated dynamically based upon number of entries in the index structure.
11. The system of claim 10 , wherein the greater the number of entries in the index structure, the larger the node size.
12. The system of claim 8 , wherein the compressing comprises: choosing the finite level of quantization from a set of quantization levels.
13. The system of claim 8 , wherein the index structure comprises at least one of an R-tree, an R*-tree, an R+-tree or a Hilbert R-tree.
14. The system of claim 8 , wherein the compression engine is further configured to:
responsive to a query, search the index structure using the quantized representation.
15. A non-transitory computer-readable storage device storing instructions that, when executed by one or more processors, cause the one or more processor to perform operations comprising:
identifying, from an index structure stored in memory, a reference minimum hounding shape that encloses a minimum bounding shape, the minimum bounding shape corresponding to a data object associated with a leaf node of the index structure;
associating, using one or more processors, coordinates of a point of the minimum bounding shape with a set of first values to produce a relative representation of the minimum bounding shape, the set of first values being calculated relative to coordinates of a reference point of the reference minimum bounding shape by calculating a difference between an absolute coordinate of the point of the minimum bounding shape and an absolute coordinate of the reference point; and
compressing the relative representation using a finite level of quantization by cutting of trailing insignificant hits to produce a quantized representation of the minimum bounding shape and storing the compressed relative representation in one or more nodes, the one or more nodes having a node size calculated dynamically based on historical query selectivity, wherein query selectivity is a measure of how much data is expected to be returned by a given query.
16. The non-transitory computer-readable storage device of claim 15 , wherein the higher the historical query selectivity, the larger the node size.
17. The non-transitory computer-readable storage device of claim 15 , wherein the node size is further calculated dynamically based upon number of entries in the index structure.
18. The non-transitory computer-readable storage device of claim 17 , wherein the greater the number of entries in the index structure, the larger the node size.
19. The non-transitory computer-readable storage device of claim 15 , wherein the compressing comprises: choosing the finite level of quantization from a set of quantization levels.
20. The non-transitory computer-readable storage device of claim 15 , wherein the index structure comprises at least one of an R-tree, an R*-tree, an R+-tree or a Hilbert k-tree.