RedisGraph

RedisGraph is a graph database built on Redis. Technically, it is a Redis module that extends graph database capabilities, including the property graph data model and graph query processing. RedisGraph exposes Cypher as its query language.

Graphs in RedisGraph are represented as sparse adjacency matrices. RedisGraph uses SuiteSparse, a package conforming GraphBLAS, a community-led project defining a linear algebraic interface for implementing graph algorithms, to represent sparse matrices and implement some physical query operators, such as Conditional Traverse.

History

RedisGraph was created in 2018. One of the first official presentations by Redis Labs was published on YouTube in the same year.

RedisGraph v.1.0, the earliest version on the website, was published in November 2018. Parallely, RedisGraph also released their benchmarking result on their system. Later, RedisGraph updated its benchmarking result according to TigerGraph's requests.

RedisGraph v.2.0 was released in January 2020 (2 years later) with a full-text search, more Cypher language coverages, and performance improvement. The performance improvement and Cypher coverages were described in their blog.

Data Model

Graph

RedisGraph supports the property graph data model. Specifically, the data model defines nodes and edges. Nodes can have multiple labels, and edges can have a relationship type. Every node and edge can have multiple properties (i.e., attributes).

Foreign Keys

Not Supported

According to their source code, RedisGraph does not support any foreign key constraints.

Checkpoints

Non-Blocking

According to their source code, RedisGraph does not provide additional checkpointing/snapshotting methods over the original Redis. Please refer to Redis for more details.

Compression

Delta Encoding Null Suppression

Graphs in RedisGraph can be stored in sparse representations supported by GraphBLAS.

According to the GraphBLAS v.2.0.0's document, it supports Compressed Sparse Row (CSR), Compressed Sparse Column (CSC), and Coordinate List (COO) to compress matrices. The key idea of all the sparse representations is to suppress zero/undefined values in matrices by storing only indices of non-zero elements.

Otherwise, there is no specific compression scheme for properties and attributes from both RedisGraph (according to their source code) and its original system, Redis. However, RedisGraph uses RediSearch to store graphs and their nodes/edges, which provides delta encoding.

Indexes

Patricia/Radix Trie

RedisGraph provides full-text indexes for querying nodes or edges by texts.

Specifically, RedisGraph uses RediSearch, which is an open-source Redis module. RediSearch uses Compact Prefix Tree (Radix Tree) and Trie (Prefix Tree) data structures.

Joins

Sort-Merge Join

RedisGraph provides a physical operator, Value Hash Join, which is used to join the records (i.e., tuples) from two child operators.

Although the name sounds like a hash join operator, the actual implementation is more similar to a sort-merge join. Their join operator starts with creating an array of the left operator's records. The array of the left operator's records will be sorted. The operator will iteratively probe the sorted array with the records from the right operator using a binary search algorithm.

Logging

Command Logging

RedisGraph does not implement any additional logging mechanism. Please refer to AOF, a Redis logging mechanism, in Redis instead.

Query Compilation

Not Supported

RedisGraph does not support query compilation according to its source code.

Query Execution

Tuple-at-a-Time Model

Based on their source code, RedisGraph uses the tuple-at-a-time query processing model to process queries.

When RedisGraph receives a query, RedisGraph will generate and then optimize a query plan according to the query. The query plan consists of physical query operators. All the query operators share the same interface, called Op. The tuple-at-a-time query processing engine will then process the query plan by calling the Consume function at the root of the query plan. The Consume function for every query operator commonly calls its children's Consume function recursively.

The implementations of graph-specific operators (such as Conditional Traverse) are mainly implemented with SuiteSparse, a linear algebra package for implementing graph algorithms conforming the GraphBLAS specification. The Conditional Traverse operator, which is used SuiteSparse, contains a breadth-first search (BFS) algorithm. The breadth-first search algorithm is implemented with a matrix-matrix multiplication in SuiteSparse.

Some operators allow a number of records to be batched before executing the operators' logic; for instance, the Conditional Traverse operator allows 16 (by default) records to be batched before calling a matrix-matrix multiplication.

Query Interface

Stored Procedures Cypher Command-line / Shell

RedisGraph exposes 9 commands:

  1. GRAPH.CONFIG stores/retrieves the current value of a RedisGraph configuration parameter.

  2. GRAPH.CONSTRAINT creates/drops graph constraints.

  3. GRAPH.DELETE deletes a graph specified.

  4. GRAPH.LIST lists all graphs managed by RedisGraph.

  5. GRAPH.EXPLAIN explains a query plan generated from a Cypher query.

  6. GRAPH.PROFILE profiles the time/records spent/produced by the query process of a Cypher query.

  7. GRAPH.QUERY executes a Cypher query.

  8. GRAPH.RO_QUERY executes a read-only Cypher query.

  9. GRAPH.SLOWLOG lists the 10 slowest queries of a specific graph.

The query must be specified in Cypher with limited coverage. The Cypher coverage of RedisGraph is specified on the website.

Users can use Redis client interfaces to interact with RedisGraph on Redis servers. Alternatively, users can use existing libraries to interact with RedisGraph. Those libraries are written in Java, Python, Node.JS, .NET. Ruby, Go, JavaScript, PHP, Elixir, Rust, C#, and Julia. RedisGraph also exposes scripts for bulk inserting a graph in their GitHub repository.

Storage Architecture

In-Memory

RedisGraph utilizes Redis, which is in-memory. Specifically, RedisGraph will load all graphs and their nodes/edges from persistent storage into memory before listening to clients. Please refer to Redis for more details.

Storage Model

Custom

Based on their source code, RedisGraph stores a node or an edge by treating it as a document and indexing it into Redis using RediSearch. The document is physically stored in Redis's managed hash tables. Different labels or relationship types create different indexes in RediSearch, which are Radix Tree (the rax implementation). Given a node has more than one label, the node is indexed across multiple indexes. The document treats properties in a node or an edge as fields.

Stored Procedures

Supported

RedisGraph allows users to provide their stored procedures written in C. Each stored procedure must be provided and registered before compiling the RedisGraph module. The registration must be currently done in this C file and must be exposed in this header file.

The valid stored procedure must contain a stored procedure name, a number of input arguments, an output specification (i.e., output data types, output field names), and three main routines. The three main routines include Invoke, Step, and Free.

  1. Invoke will be called first after the stored procedure is called.

  2. Step will be called multiple times to produce a result tuple per Step call.

  3. Free will be called to clean up allocated memory.

Users may store the state of each procedure call using the private_data pointer shared across these routines.

System Architecture

Shared-Nothing

RedisGraph does not have any design choices in its architecture. Please refer to Redis which uses the shared-nothing architecture.

Views

Not Supported

Based on their source code, RedisGraph does not support views.

RedisGraph Logo
Website

https://redisgraph.io/

Source Code

https://github.com/RedisGraph/RedisGraph

Tech Docs

https://redis.io/docs/stack/graph/

Twitter

@Redisinc

Developer

Redis Ltd.

Country of Origin

US

Start Year

2018

Project Type

Commercial, Open Source

Written in

C

Supported languages

C

Embeds / Uses

Redis

Operating Systems

Linux

Licenses

Server Side Public License