EDGE STORE COMPRESSION IN GRAPH DATABASES
The disclosed embodiments provide a system for processing and storing data. During operation, the system obtains a set of records sorted by a first integer value, with each record containing the first integer value and one or more additional integer values. The system sets, for each integer value in each record, a delta encoding bit that indicates whether the integer value is delta encoded with respect to at least one other integer value in the records. Next, the system uses a delta encoding state represented by the delta encoding bit to calculate an encoded value from the integer value. The system then encodes a length of the encoded value in a length tag for the integer value and replaces the integer value in the record with an encoded version containing the delta encoding bit, the length tag, and the encoded value.
1 . A method, comprising:
obtaining, in a store maintained on a computer system, a set of records sorted by a first integer value, wherein each record in the set of records comprises the first integer value and one or more additional integer values; and
reducing an amount of memory used to store the records by performing, for each record in the set of records, the following operations on the computer system:
setting, for each integer value in the record, a delta encoding bit that indicates whether the integer value is delta encoded with respect to at least one other integer value in the set of records;
using a delta encoding state represented by the delta encoding bit to calculate an encoded value from the integer value;
encoding a length of the encoded value in a length tag for the integer value; and
replacing the integer value in the record with an encoded version comprising the delta encoding bit, the length tag, and the encoded value.
2 . The method of claim 1 , further comprising:
using one or more additional bits in the record to specify one or more write operations associated with the record.
3 . The method of claim 2 , wherein the one or more write operations comprise:
an addition; and
a deletion.
4 . The method of claim 1 , wherein using the delta encoding state represented by the delta encoding bit to calculate the encoded value from the integer value comprises:
when the delta encoding state indicates delta encoding of the first integer value, calculating the encoded value from a difference between the first integer value in the record and the first integer value in an adjacent record in the set of records.
5 . The method of claim 1 , wherein using the delta encoding state represented by the delta encoding bit to calculate the encoded value from the integer value comprises:
when the delta encoding state indicates delta encoding of an additional integer value that follows the first integer value in the record, calculating the encoded value from a difference between the additional integer value and the first integer value.
6 . The method of claim 1 , wherein the length tag comprises three bits representing a number of bytes in the encoded value.
7 . The method of claim 1 , wherein the encoded version is generated in descending order of the first integer value in the set of records.
8 . The method of claim 1 , further comprising:
using the delta encoding bit and the length tag to generate a decoded value from the encoded value; and
using the decoded value to process a query of a graph database.
9 . The method of claim 8 , wherein the decoded value is associated with at least one of:
a subject;
a predicate;
an object;
an offset; and
an edge.
10 . The method of claim 8 , wherein:
the first integer value comprises an identifier for an edge in the graph database; and
the one or more additional integer values comprise a linkage value for resolving the edge.
11 . The method of claim 8 , wherein the integer value comprises a first byte to an eighth byte of a 64-bit memory address in the graph database.
12 . An apparatus, comprising:
one or more processors; and
memory storing instructions that, when executed by the one or more processors, cause the apparatus to:
obtain a set of records sorted by a first integer value, wherein each record in the set of records comprises the first integer value and one or more additional integer values; and
for each record in the set of records:
set, for each integer value in the record, a delta encoding bit that indicates whether the integer value is delta encoded with respect to at least one other integer value in the set of records;
use a delta encoding state represented by the delta encoding bit to calculate an encoded value from the integer value;
encode a length of the encoded value in a length tag for the integer value; and
replace the integer value in the record with an encoded version comprising the delta encoding bit, the length tag, and the encoded value.
13 . The apparatus of claim 12 , wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:
use one or more additional bits in the record to specify one or more write operations associated with the record.
14 . The apparatus of claim 12 , wherein using the delta encoding state represented by the delta encoding bit to calculate the encoded value from the integer value comprises:
when the delta encoding state indicates delta encoding of the first integer value, calculating the encoded value from a difference between the first integer value in the record and the first integer value in an adjacent record in the set of records.
15 . The apparatus of claim 14 , wherein using the delta encoding state represented by the delta encoding bit to calculate the encoded value from the integer value further comprises:
when the delta encoding state indicates delta encoding of an additional integer value that follows the first integer value in the record, calculating the encoded value from a difference between the additional integer value and the first integer value.
16 . The apparatus of claim 12 , wherein the encoded version is generated in descending order of the first integer value in the set of records.
17 . The apparatus of claim 12 , wherein:
the first integer value comprises an identifier for an edge in the graph database; and
the one or more additional integer values comprise a linkage value for resolving the edge.
18 . The apparatus of claim 17 , wherein the linkage value is at least one of:
a subject;
a predicate; and
an object.
19 . A system, comprising:
a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates; and
an encoding module comprising a non-transitory computer-readable medium comprising instructions that, when executed, cause the system to:
obtain, for storage in the graph database, a set of records sorted by a first integer value, wherein each record in the set of records comprises the first integer value and one or more additional integer values; and
for each record in the set of records:
set, for each integer value in the record, a delta encoding bit that indicates whether the integer value is delta encoded with respect to at least one other integer value in the set of records;
use a delta encoding state represented by the delta encoding bit to calculate an encoded value from the integer value;
encode a length of the encoded value in a length tag for the integer value; and
replace the integer value in the record with an encoded version comprising the delta encoding bit, the length tag, and the encoded value.
20 . The system of claim 19 , further comprising:
a decoding module comprising a non-transitory computer-readable medium comprising instructions that, when executed, cause the system to:
use the delta encoding bit and the length tag to generate a decoded value from the encoded value; and
use the decoded value to process a query of the graph database.