RedisGraph is a Redis module that adds Graph database capabilities to Redis and enables organizations to process any kind of connected data faster compared to traditional relational or Graph databases. RedisGraph is also the first queryable Property Graph database to use sparse matrices to represent the adjacency matrix in graph, and linear algebra to query the graph.
Technology behind RedisGraph
In traditional graph databases, operations are typically based on data structures like the hexastore or adjacency list, which require developers to write less efficient code in order to execute graph traversal operations. For example, see this approach to “find the next BFS (Breadth-First-Search) level” below:
Instead, GraphBLAS (Basic Linear Algebra Subprograms), a highly optimized library for sparse matrix operations, represents graphs with an intuitive adjacency matrix: a square table with all nodes along each axis, and a value of ‘1’ for each connected pair. Our new engine uses linear algebra of matrices to execute graph traversal operations, which makes query processing much more efficient. For example, the matrix below represents the connected graph from the example above, in which each column (1-7) represents a source node and each row (1-7) represents a destination node:
Naively implemented, the traditional approach scales very poorly for graphs that model real-world problems, which tend to be very sparse. Space and time complexity for a matrix is governed by its dimensions (O(n²) for square matrices), making alternatives like adjacency lists more appealing for most practical applications with scaling requirements.
Benefits of Using GraphBLAS
GraphBLAS defines a core set of matrix-based graph operations that can be used to implement a wide class of graph algorithms in many different programming environments. The principal benefits of using matrices for graph algorithms are space efficiency and performance.
The GraphBLAS library gives developers the benefits of matrix representations while optimizing for sparse data sets. GraphBLAS encodes matrices in Compressed Sparse Column (CSC) form, which has a cost determined by the number of non-zero elements contained. In total, the space complexity of a matrix is:
(# of columns + 1) + (2 * # of non-zero elements)
This encoding is highly space-efficient, and also allows us to treat graph matrices as mathematical operands. As a result, database operations can be executed as algebraic expressions without needing to first translate data out of a form (like a series of adjacency lists). For example, finding the next BFS on the graph from above is as simple as joining the 1’s of column #1 with column #3, or in matrices algebra terms – multiplying the graph matrix with a filter vector for column #1 & #3:
The RedisGraph module, based on GraphBLAS engine, shows significant performance advantages over existing graph databases. Recently, Tiger Graph conducted a benchmark performance test where it came out significantly faster than all other existing Graph database solutions. So we decided to benchmark data loading and query performance of RedisGraph against Tiger. The results below show how RedisGraph is faster than Tiger and consequently all other Graph database that Tiger tested against.
Solving Graph problems with linear algebra
With GraphBLAS, the library invocations are direct mathematical operations, such as matrix multiplications and transposes. These calls implement a lazy evaluation and execution strategy to reduce computation time and the calls are optimized behind the scenes.
Additionally, with the adoption of the CSC approach, RedisGraph allows indexed access to a column of the matrix. Non-zero vector stores the non-zero elements of each column of the matrix and the column vector stores the pointer to the first non-zero element of each column. This significantly accelerates complex query response times, with multiple hops, on large data sets.
Support for a declarative query language
Cypher is a very popular declarative pattern matching language created for the purposes of querying graph data representations effectively. RedisGraph implements and supports the Cypher language (the industry standard and widely adopted query language for graph databases) and automatically translates them to linear algebraic expressions. Learn more about our Cypher coverage here.
In addition, Redis Labs is working closely with other Graph database vendors on the Graph Query Language (GQL) taskforce to create a standardized declarative language for Graph database.
How to Get Started