
![Load Testing of K6 in NebulaGraph](https://user-images.githubusercontent.com/90186547/143535019-c3271ff1-390d-4fad-8cc3-599fc42a6abb.png)

## Why Load Testing Matters in NebulaGraph?

The load testing for the database needs to be conducted usually so that the impact on the system can be monitored in different scenarios, such as query language rule optimization, storage engine parameter adjustment, etc.

The operating system in this article is the x86 CentOS 7.8.

The hosts where NebulaGraph is deployed are configured with 4C 16G memory, SSD disk, and 10G network.

## Tools Needed for the Load Testing

* [nebula-ansible](https://github.com/vesoft-inc/nebula-ansible) deploys NebulaGraph services.
* [nebula-importer](https://github.com/vesoft-inc/nebula-importer) imports data into NebulaGraph clusters.
* [k6-plugin](https://github.com/vesoft-inc/k6-plugin) is a K6 extension that is used to perform load testing against the NebulaGraph cluster. The extension integrates with the nebula-go client to send requests during the testing.
* [nebula-bench](https://github.com/vesoft-inc/nebula-bench) generates the LDBC dataset and then imports it into NebulaGraph.
* [ldbc_snb_datagen_hadoop](https://github.com/ldbc/ldbc_snb_datagen_hadoop) is a LDBC data generator.

## Load Testing Process Overview

The load testing conducted in this article uses the LDBC dataset generated by [ldbc_snb_datagen](https://github.com/ldbc/ldbc_snb_datagen_hadoop). The testing process is as follows. 

![Load Testing of K6 in NebulaGraph](https://user-images.githubusercontent.com/90186547/144202245-c82fc9c0-3e1d-4549-91bb-8b9a5797878d.png)

To deploy the topology, use one host as the load testing runner, and use three hosts to form a NebulaGraph cluster.

![Load Testing of K6 in NebulaGraph](https://user-images.githubusercontent.com/90186547/143535649-16fb5000-f850-47f5-85b3-4ab04b779a85.png)

To make monitoring easier, the load testing runner also deploys:

* Prometheus
* Influxdb
* Grafana
* node-exporter

The hosts where NebulaGraph is installed also deploy:

* node-exporter
* process-exporter

## Load Testing Steps

### Use nebula-ansible to deploy NebulaGraph

1. Set up SSH login without passwords
   a. Log in 192.168.8.60, 192.168.8.61, 192.168.8.62, and 192.168.8.63 respectively. Create a vesoft user and join in sudoer with NOPASSWD.
   b. Log in 192.168.8.60 to set up SSH.
```bash
ssh-keygen

ssh-copy-id vesoft@192.168.8.61
ssh-copy-id vesoft@192.168.8.62
ssh-copy-id vesoft@192.168.8.63
```

2. Download nebula-ansible, install Ansible, and modify the Ansible configuration.
```bash
sudo yum install ansible -y
git clone https://github.com/vesoft-inc/nebula-ansible
cd nebula-ansible/
```

The following is an example of inventory.ini.

```yaml
[all:vars]
# GA or nightly
install_source_type = GA
nebula_version = 2.0.1
os_version = el7
arc = x86_64
pkg = rpm

packages_dir = {{ playbook_dir }}/packages
deploy_dir = /home/vesoft/nebula
data_dir = {{ deploy_dir }}/data

# ssh user
ansible_ssh_user = vesoft

force_download = False

[metad]
192.168.8.[61:63]

[graphd]
192.168.8.[61:63]

[storaged]
192.168.8.[61:63]
```

3. Install and deploy NebulaGraph.
```bash
ansible-playbook install.yml
ansible-playbook start.yml
```

### Monitor hosts

Using docker-compose to deploy monitoring system is convenient. Docker and Docker-Compose need to be installed on the hosts first.

Log in 192.168.8.60

```bash
git clone https://github.com/vesoft-inc/nebula-bench.git

cd nebula-bench
cp -r third/promethues ~/.
cp -r third/exporter ~/.



cd ~/exporter/ && docker-compose up -d

cd ~/promethues
# Modify the exporter address of monitoring nodes
# vi prometheus.yml
docker-compose up -d

# Copy exporter to 192.168.8.61, 192.168.8.62, and 192.168.8.63, and then start docker-compose
```
Configure the Grafana data source and dashboard. For details, see [https://github.com/vesoft-inc/nebula-bench/tree/master/third](https://github.com/vesoft-inc/nebula-bench/tree/master/third).

### Generate the LDBC dataset

```bash
cd nebula-bench

sudo yum install -y git \
                    make \
                    file \
                    libev \
                    libev-devel \
                    gcc \
                    wget \
                    python3 \
                    python3-devel \
                    java-1.8.0-openjdk \
                    maven

pip3 install --user -r requirements.txt

# Using `snb.interactive.1` parameter in ldbc_snb_datagen_hadoop. For more infor, see https://github.com/ldbc/ldbc_snb_datagen_hadoop/wiki/Configuration

python3 run.py data

# Date generated by mv

mv target/data/test_data/ ./sf1
```

### Import data

```bash
cd nebula-bench
# Modify .evn
cp env .env
vi .env
```

The following is the example of .env

```bash
DATA_FOLDER=sf1
NEBULA_SPACE=sf1
NEBULA_USER=root
NEBULA_PASSWORD=nebula
NEBULA_ADDRESS=192.168.8.61:9669,192.168.8.62:9669,192.168.8.63:9669
#NEBULA_MAX_CONNECTION=100
INFLUXDB_URL=http://192.168.8.60:8086/k6
```

```bash
# Compile nebula-importer and K6
./scripts/setup.sh

# Import data
python3 run.py nebula importer
```
During the import process, you can focus on the following network bandwidth and disk IO writing.

![Import data](https://user-images.githubusercontent.com/90186547/143537054-5bab1ec9-13cb-4770-be7e-af94314f969f.png)

![Import data](https://user-images.githubusercontent.com/90186547/143537120-5bb9cf2b-f9d8-4a44-a6df-5dfd2e959ab3.png)


### Execute the load testing

```bash
python3 run.py stress run
```

According to the code source in the file `scenarios`, the js file will be automatically rendered and K6 will be used to test all scenarios.

After the execution is over, the js file and the result will be saved in the output folder.

Among them, `latency` is the latency time returned by the server, and `responseTime` is the time from initiating `execute` to `response` by the client. The measurement unit is `μs`.

```bash
[vesoft@qa-60 nebula-bench]$ more output/result_Go1Step.json
{
    "metrics": {
        "data_sent": {
            "count": 0,
            "rate": 0
        },
        "checks": {
            "passes": 1667632,
            "fails": 0,
            "value": 1
        },
        "data_received": {
            "count": 0,
            "rate": 0
        },
        "iteration_duration": {
            "min": 0.610039,
            "avg": 3.589942336582023,
            "med": 2.9560145,
            "max": 1004.232905,
            "p(90)": 6.351617299999998,
            "p(95)": 7.997563949999995,
            "p(99)": 12.121579809999997
        },
        "latency": {
            "min": 308,
            "avg": 2266.528722763775,
            "med": 1867,
            "p(90)": 3980,
            "p(95)": 5060,
            "p(99)": 7999
        },
        "responseTime": {
            "max": 94030,
            "p(90)": 6177,
            "p(95)": 7778,
            "p(99)": 11616,
            "min": 502,
            "avg": 3437.376111156418,
            "med": 2831
        },
        "iterations": {
            "count": 1667632,
            "rate": 27331.94978169588
        },
        "vus": {
            "max": 100,
            "value": 100,
            "min": 0
```

```bash
[vesoft@qa-60 nebula-bench]$ head -300 output/output_Go1Step.csv | grep -v USE
timestamp,nGQL,latency,responseTime,isSucceed,rows,errorMsg
1628147822,GO 1 STEP FROM 4398046516514 OVER KNOWS,1217,1536,true,1,
1628147822,GO 1 STEP FROM 2199023262994 OVER KNOWS,1388,1829,true,94,
1628147822,GO 1 STEP FROM 1129 OVER KNOWS,1488,2875,true,14,
1628147822,GO 1 STEP FROM 6597069771578 OVER KNOWS,1139,1647,true,30,
1628147822,GO 1 STEP FROM 2199023261211 OVER KNOWS,1399,2096,true,6,
1628147822,GO 1 STEP FROM 2199023256684 OVER KNOWS,1377,2202,true,4,
1628147822,GO 1 STEP FROM 4398046515995 OVER KNOWS,1487,2017,true,39,
1628147822,GO 1 STEP FROM 10995116278700 OVER KNOWS,837,1381,true,3,
1628147822,GO 1 STEP FROM 933 OVER KNOWS,1130,3422,true,5,
1628147822,GO 1 STEP FROM 6597069771971 OVER KNOWS,1022,2292,true,60,
1628147822,GO 1 STEP FROM 10995116279952 OVER KNOWS,1221,1758,true,3,
1628147822,GO 1 STEP FROM 8796093031179 OVER KNOWS,1252,1811,true,13,
1628147822,GO 1 STEP FROM 10995116279792 OVER KNOWS,1115,1858,true,6,
1628147822,GO 1 STEP FROM 6597069777326 OVER KNOWS,1223,2016,true,4,
1628147822,GO 1 STEP FROM 8796093028089 OVER KNOWS,1361,2054,true,13,
1628147822,GO 1 STEP FROM 6597069777454 OVER KNOWS,1219,2116,true,2,
1628147822,GO 1 STEP FROM 13194139536109 OVER KNOWS,1027,1604,true,2,
1628147822,GO 1 STEP FROM 10027 OVER KNOWS,2212,3016,true,83,
1628147822,GO 1 STEP FROM 13194139544176 OVER KNOWS,855,1478,true,29,
1628147822,GO 1 STEP FROM 10995116280047 OVER KNOWS,1874,2211,true,12,
1628147822,GO 1 STEP FROM 15393162797860 OVER KNOWS,714,1684,true,5,
1628147822,GO 1 STEP FROM 6597069770517 OVER KNOWS,2295,3056,true,7,
1628147822,GO 1 STEP FROM 17592186050570 OVER KNOWS,768,1630,true,26,
1628147822,GO 1 STEP FROM 8853 OVER KNOWS,2773,3509,true,14,
1628147822,GO 1 STEP FROM 19791209307908 OVER KNOWS,1022,1556,true,6,
1628147822,GO 1 STEP FROM 13194139544258 OVER KNOWS,1542,2309,true,91,
1628147822,GO 1 STEP FROM 10995116285325 OVER KNOWS,1901,2556,true,0,
1628147822,GO 1 STEP FROM 6597069774931 OVER KNOWS,2040,3291,true,152,
1628147822,GO 1 STEP FROM 8796093025056 OVER KNOWS,2007,2728,true,29,
1628147822,GO 1 STEP FROM 21990232560726 OVER KNOWS,1639,2364,true,9,
1628147822,GO 1 STEP FROM 8796093030318 OVER KNOWS,2145,2851,true,6,
1628147822,GO 1 STEP FROM 21990232556027 OVER KNOWS,1784,2554,true,5,
1628147822,GO 1 STEP FROM 15393162796879 OVER KNOWS,2621,3184,true,71,
1628147822,GO 1 STEP FROM 17592186051113 OVER KNOWS,2052,2990,true,5,
```

It is also possible to execute the load testing in one scenario and continuously adjust the configuration parameters for comparison.

#### Concurrent reading

```bash
# Run Go2Step with 50 virtual users and 300 seconds of duration
python3 run.py stress run -scenario go.Go2Step -vu 50 -d 300
```

```shell

INFO[0302] 2021/08/06 03:55:27 [INFO] finish init the pool

     ✓ IsSucceed

     █ setup

     █ teardown

     checks...............: 100.00% ✓ 1559930     ✗ 0
     data_received........: 0 B     0 B/s
     data_sent............: 0 B     0 B/s
     iteration_duration...: min=687.47µs avg=9.6ms       med=8.04ms max=1.03s  p(90)=18.41ms p(95)=22.58ms p(99)=31.87ms
     iterations...........: 1559930 5181.432199/s
     latency..............: min=398      avg=6847.850345 med=5736   max=222542 p(90)=13046   p(95)=16217   p(99)=23448
     responseTime.........: min=603      avg=9460.857877 med=7904   max=226992 p(90)=18262   p(95)=22429   p(99)=31726.71
     vus..................: 50      min=0         max=50
     vus_max..............: 50      min=50        max=50

```
Every metric can be monitored at the same time.

![Concurrent reading](https://user-images.githubusercontent.com/90186547/143537715-f4f404b6-e842-4904-94f6-51aaaf4ef129.png)


`checks` is to verify whether the request is executed successfully. If the execution fails, the failed message will be saved in the CSV file.

```bash
awk -F ',' '{print $NF}' output/output_Go2Step.csv|sort |uniq -c
```

```bash
# Execute Go2Step with 200 virtual users and 300 seconds of duration
python3 run.py stress run -scenario go.Go2Step -vu 200 -d 300
```

```shell

INFO[0302] 2021/08/06 04:02:34 [INFO] finish init the pool

     ✓ IsSucceed

     █ setup

     █ teardown

     checks...............: 100.00% ✓ 1866850    ✗ 0
     data_received........: 0 B     0 B/s
     data_sent............: 0 B     0 B/s
     iteration_duration...: min=724.77µs avg=32.12ms      med=25.56ms max=1.03s  p(90)=63.07ms p(95)=84.52ms  p(99)=123.92ms
     iterations...........: 1866850 6200.23481/s
     latency..............: min=395      avg=25280.893558 med=20411   max=312781 p(90)=48673   p(95)=64758    p(99)=97993.53
     responseTime.........: min=627      avg=31970.234329 med=25400   max=340299 p(90)=62907   p(95)=84361.55 p(99)=123750
     vus..................: 200     min=0        max=200
     vus_max..............: 200     min=200      max=200

```

K6 metrics to be monitored with Grafana

![The monitoring data of K6 in Grafana](https://user-images.githubusercontent.com/90186547/143537954-780fade2-ae2a-4882-a33e-3df47ad68402.png)


#### Concurrent writing

```bash

# Execute insert with 200 virtual users and 300 seconds of duration. By default, batchSize is 100.

python3 run.py stress run -scenario go.Go2Step -vu 200 -d 300
```

The js file can be modified manually to adjust batchSize

```bash
sed -i 's/batchSize = 100/batchSize = 300/g' output/InsertPersonScenario.js

# Run K6 manually

scripts/k6 run output/InsertPersonScenario.js -u 400 -d 30s --summary-trend-stats "min,avg,med,max,p(90),p(95),p(99)" --summary-export output/result_InsertPersonScenario.json --out influxdb=http://192.168.8.60:8086/k6
```

If the batchSize is 300 with 400 virtual users, an error will be returned.

```shell
INFO[0032] 2021/08/06 04:03:49 [INFO] finish init the pool

     ✗ IsSucceed
      ↳  96% — ✓ 31257 / ✗ 1103

     █ setup

     █ teardown

     checks...............: 96.59% ✓ 31257       ✗ 1103
     data_received........: 0 B    0 B/s
     data_sent............: 0 B    0 B/s
     iteration_duration...: min=12.56ms avg=360.11ms      med=319.12ms max=2.07s   p(90)=590.31ms p(95)=696.69ms p(99)=958.32ms
     iterations...........: 32360  1028.339207/s
     latency..............: min=4642    avg=206931.543016 med=206162   max=915671  p(90)=320397.4 p(95)=355798.7 p(99)=459521.39
     responseTime.........: min=6272    avg=250383.122188 med=239297.5 max=1497159 p(90)=384190.5 p(95)=443439.6 p(99)=631460.92
     vus..................: 400    min=0         max=400
     vus_max..............: 400    min=400       max=400

```
```bash

awk -F ',' '{print $NF}' output/output_InsertPersonScenario.csv|sort |uniq -c

```

```shell

  31660
   1103  error: E_CONSENSUS_ERROR(-16)."
      1 errorMsg 
```

If `E_CONSENSUS_ERROR` occurs, it should be that the appendlog buffer of raft is overflown when the concurrency is large, which can be solved by adjusting relevant parameters. 

## Summary

* The load testing uses the LDBC dataset standard to ensure data uniform. Even when bigger data volume, say one billion vertices, is generated, the graph schema is the same.
* K6 is more convenient than Jmeter for the load testing. For more details, please refer https://k6.io/docs/.
* You can easily find the bottleneck of the system resources by simulating various scenarios or adjust parameters in NebulaGraph with the mentioned tools.

If you encounter any problems in the process of using NebulaGraph, please refer to [NebulaGraph Database Manual](https://docs.nebula-graph.io/3.0.1/pdf/NebulaGraph-EN.pdf) to troubleshoot the problem. It records in detail the knowledge points and specific usage of the graph database and the graph database NebulaGraph.

Join our [Slack channel](https://join.slack.com/t/nebulagraph/shared_invite/zt-7ybejuqa-NCZBroh~PCh66d9kOQj45g) if you want to discuss with the rest of the NebulaGraph community!







Performance testing for the database needs to be conducted usually so that the impact on the system can be monitored in different scenarios.

How to Perform Load Testing against NebulaGraph with K6


![NebulaGraph Source Code Explained: fbthrift](https://user-images.githubusercontent.com/90186547/139801851-f51f169e-917a-4757-8461-4a7e62abf3a7.png)

# Overview

Nebula Clients provide users with APIs in multiple programming languages to interact with NebulaGraph and repackages the data structure returned by the server for better use.

Currently, Nebula Clients support C++, Java, Python, Golang, and Rust.

# Framework for service communication

Nebula Clients use `fbthrift` [https://github.com/facebook/fbthrift](https://github.com/facebook/fbthrift) as the RPC framework for service communication between servers and clients to implement cross-language interaction.

At a high level, fbthrift is:

1. A code generator: fbthrift has a code generator that generates data structures that can be serialized using Thrift in different languages.
2. A serialization framework: fbthrift has a set of protocols to serialize the generated structures created from the code generator.
3. An RPC framework: fbthrift has a framework to send messages between clients and servers and to call application-defined functions when receiving messages in different languages.

# Examples

Take the Golang client as an example to show the application of fbthrift in NebulaGraph.

1. The definition of the `Vertex` structure in servers:
```cpp
struct Vertex {
	Value vid;
	std::vector<Tag> tags;

	Vertex() = default;
};
``` 
2. Define some data structures in `src/interface/common.thrift`:

```cpp
struct Tag {
		1: binary name,
		// List of <prop_name, prop_value>
		2: map<binary, Value> (cpp.template = "std::unordered_map") props,
} (cpp.type = "nebula::Tag")

struct Vertex {
		1: Value     vid,
		2: list<Tag> tags,
} (cpp.type = "nebula::Vertex")
```

In the above example, we define a Vertex structure. `(cpp.type = "nebula::Vertex")` indicates this structure corresponds to the `nebula::Vertex` of the server.

3. fbthrift will automatically generate the data structure in Golang:
```golang
// Attributes:
//  - Vid
//  - Tags
type Vertex struct {
	Vid *Value `thrift:"vid,1" db:"vid" json:"vid"`
	Tags []*Tag `thrift:"tags,2" db:"tags" json:"tags"`
}

func NewVertex() *Vertex {
	return &Vertex{}
}

...

func (p *Vertex) Read(iprot thrift.Protocol) error { // Deserialization 
	...
}

func (p *Vertex) Write(oprot thrift.Protocol) error { // Serialization 
	...
}
```
4. In `MATCH (v:Person) WHERE id(v) == "ABC" RETURN v`, the client requests a vertex (`nebula::Vertex`) from the server. The server will **serialize** it after finding it. After the server finds this vertex, it will be **serialized** and sent to the client through the `transport` of the RPC communication framework. When the client receives this data, it will be **deserialized** to generate the corresponding data structure (`type Vertex struct`) defined in the client.

# Clients

In this section, we will take nebula-go as an example to introduce different modules of the client and their main interfaces.

1. **Configs** provides the whole configuration options.
```golang
type PoolConfig struct {
	// Set the timeout threshold. The default value 0 means it does not time out. Unit: ms
	TimeOut time.Duration
	// The maximum idle time of each connection. When the idle time exceeds this threshold, the connection will be disconnected and deleted. The default value 0 means permanently idle and the connection will not be disconnected
	IdleTime time.Duration
	// max_connection_pool_size: Set the maximum number of connections in the connection pool. The default value is 10
	MaxConnPoolSize int
	// The minimum number of idle connections. The default value is 0
	MinConnPoolSize int
}
```
2. **Session** provides an interface for users to call directly.
```golang
// Manage the specific information of Session
type Session struct {
	// Use for identity verification or message retry when executing commands
	sessionID  int64
	// Currently held connections
	connection *connection
	// Currently used connection pools
	connPool   *ConnectionPool
	// Log tools
	log        Logger
	// Use to save the time zone used by the current session
	timezoneInfo
}
```
- The definition of interfaces is as follows:
```golang
	// Execute nGQL. The return data type is ResultSet. This interface is non-thread-safe
	func (session *Session) Execute(stmt string) (*ResultSet, error) {...}
	// Re-acquire a connection from the connection pool for the current Session
	func (session *Session) reConnect() error {...}
	// Signout, release the Session ID, and return the connection to the pool
	func (session *Session) Release() {
```
3. **ConnectionPool** manages all connections. The main interfaces are as follows:
```golang
// Create a new connection pool and complete the initialization with the entered service address
func NewConnectionPool(addresses []HostAddress, conf PoolConfig, log Logger) (*ConnectionPool, error) {...}
// Validate and get the Session example
func (pool *ConnectionPool) GetSession(username, password string) (*Session, error) {...}
```

4. **Connection** packages the network of **thrift** and provides the following interfaces:
```golang
// Establish a connection with the specified ip and port
func (cn *connection) open(hostAddress HostAddress, timeout time.Duration) error {...}
// Authenticate the username and password
func (cn *connection) authenticate(username, password string) (*graph.AuthResponse, error) {
// Execute query
func (cn *connection) execute(sessionID int64, stmt string) (*graph.ExecutionResponse, error) {...}
// Generate a temp sessionID 0 and send the query "YIELD 1" to test if the connection is usable.
func (cn *connection) ping() bool {...}
// Release sessionId to the graphd process.
func (cn *connection) signOut(sessionID int64) error {...}
// Disconnect.
func (cn *connection) close() {...}
```
5. **LoadBalance** is used in the connection pool.
   - Policy: Polling

# Interaction of modules

![Interaction of modules](https://user-images.githubusercontent.com/90186547/139806844-7bbffd66-6161-40d4-9115-e7522f44538d.png)

1. Connection pool
   - Initialize:
     - When using it, the user needs to create and initialize a **connection pool**. During initialization, the connection pool will establish a **connection** at the address of the Nebula service specified by the user. If multiple Graph services are deployed in a cluster deployment method, the connection pool will use a **polling policy** to balance the load and establish a nearly equal number of connections for each address.
   - Manage connections:
     - Two queues are maintained in the connection pool, **idle connection queue** and **active Connection Queue**. The connection pool will periodically detect expired idle connections and close them. These two queues will use **read-write lock** to ensure the correctness of multi-thread execution when adding or deleting elements.
     - When Session requests a connection to the connection pool, it will check whether there are usable connections in the idle connection queue. If there are any usable connections, they will be directly returned to the Session for users to use. If there are no usable connections and the current total number of connections does not exceed the maximum number of connections defined in the configuration, a new connection is created to the Session. If it reaches the maximum number of connections, an error is returned.
   - Generally, the connection pool needs to be closed only when you close the program. All connections in the pool will be disconnected when the program is closed.
2. Session
   - **Session** is generated through the connection pool. The user needs to provide the password for authentication. After the authentication succeeds, the user will get a Session example and communicate with the server through the connection in the Session. The most commonly used interface is `execute()`. If an error occurs during execution, the client will check the error type. If it is a network error, it will **automatically reconnect** and try to execute the statement again.
   - Note that a Session **does not support being used by multiple threads at the same time**. The correct way is that multiple sessions are applied by multiple threads, and one session is used by each thread.
   - When the Session is released, the connection held by it will be put back into the **idle connection queue** of the connection pool so that it can be reused by other sessions later. 
3. Connection
   - Each connection example is equivalent and can be held by any Session. **The purpose of this design is to allow these connections to be reused by different Sessions**, reducing repeatedly enabling and disabling Transport.
   - The connection will send the client's request to the server and return the result to the Session.
4. Example
```golang
// Initialize connection pool
pool, err := nebula.NewConnectionPool(hostList, testPoolConfig, log)
if err != nil {
	log.Fatal(fmt.Sprintf("Fail to initialize the connection pool, host: %s, port: %d, %s", address, port, err.Error()))
}
// Close all connections in the pool when program exits
defer pool.Close()

// Create session
session, err := pool.GetSession(username, password)
if err != nil {
	log.Fatal(fmt.Sprintf("Fail to create a new session from connection pool, username: %s, password: %s, %s",
		username, password, err.Error()))
}
// Release session and return connection back to connection pool when program exits
defer session.Release()

// Excute a query
resultSet, err := session.Execute(query)
if err != nil {
	fmt.Print(err.Error())
}
```

# Returned data structure

The client packages the returned query results by part of the complex servers and adds an interface for convenience use.

| Basic type of returned results |          Packaged type        |
| :----------------------------: | :----------------------------:|
|       Null                     |
|       Bool                     |
|      Int64                     |
|      Double                    |
|      String                    |
|       Time                     |          TimeWrapper          |
|       Date                     |
|     DateTime                   |        DateTimeWrapper        |
|       List                     |
|       Set                      |
|       Map                      |
|      Vertex                    |              Node             |
|       Edge                     |          Relationship         |
|       Path                     |          PathWrraper          |
|     DateSet                    |           ResultSet           |
|        -                       | Record (For row operations of ResultSet)  |

`nebula::Value` will be packaged as `ValueWrapper` in the client and converted to other structures through interfaces. (i.g. `node = ValueWrapper.asNode()`)


## Analysis of data structure

For `MATCH p= (v:player{name:"Tim Duncan"})-[]->(v2) RETURN p`, the returned result is:
```
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| p                                                                                                                                                                                                                         |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| <("Tim Duncan" :bachelor{name: "Tim Duncan", speciality: "psychology"} :player{age: 42, name: "Tim Duncan"})<-[:teammate@0 {end_year: 2016, start_year: 2002}]-("Manu Ginobili" :player{age: 41, name: "Manu Ginobili"})> |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
Got 1 rows (time spent 11550/12009 us)
```
We can see that the returned result contains one row, and its type is a path. At this time, you can execute as follows to get the properties of the destination vertex of the path (v2).
```golang
// Excute a query
resultSet, _ := session.Execute("MATCH p= (v:player{name:"\"Tim Duncan"\"})-[]->(v2) RETURN p")

// Get the first row of the result. The index of the first row is 0
record, err := resultSet.GetRowValuesByIndex(0)
if err != nil {
	t.Fatalf(err.Error())
}

// Take the value of the cell in the first column from the first row
// At this time, the type of valInCol0 is ValueWrapper
valInCol0, err := record.GetValueByIndex(0)

// Convert ValueWrapper into PathWrapper objects.
pathWrap, err = valInCol0.AsPath()

// Get the destination vertex through pathWrap.GetEndNode()
node, err = pathWrap.GetEndNode()

// Get all properties through node.Properties()
// The type of props is map[string]*ValueWrapper
props, err = node.Properties()
```

# Address of clients

The GitHub addresses of clients are as follows:
- [https://github.com/vesoft-inc/nebula-cpp](https://github.com/vesoft-inc/nebula-cpp)
- [https://github.com/vesoft-inc/nebula-java](https://github.com/vesoft-inc/nebula-java)
- [https://github.com/vesoft-inc/nebula-python](https://github.com/vesoft-inc/nebula-python)
- [https://github.com/vesoft-inc/nebula-go](https://github.com/vesoft-inc/nebula-go)
- [https://github.com/vesoft-inc/nebula-rust](https://github.com/vesoft-inc/nebula-rust)

If you encounter any problems in the process of using NebulaGraph, please refer to [NebulaGraph Database Manual](https://docs.nebula-graph.io/2.6.0/pdf/NebulaGraph-EN.pdf) to troubleshoot the problem. It records in detail the knowledge points and specific usage of the graph database and the graph database NebulaGraph.

Join our [Slack channel](https://join.slack.com/t/nebulagraph/shared_invite/zt-7ybejuqa-NCZBroh~PCh66d9kOQj45g) if you want to discuss with the rest of the NebulaGraph community!

Nebula Clients provide users with APIs in multiple programming languages to interact with NebulaGraph and repackages the data structure returned by the server for better use.

NebulaGraph Source Code Explained: fbthrift


![NebulaGraph Source Code Explained: Variable-Length Pattern Matching](https://user-images.githubusercontent.com/90186547/138233442-7233ca4a-67d7-49ff-b8e3-644586a2460f.png)

At the very heart of openCypher, the `MATCH` clause allows you to specify simple query patterns to retrieve the relationships from a graph database. A variable-length pattern is commonly used to describe paths and it is NebulaGraph's first try to get nGQL compatible with openCypher in the `MATCH` clause. 

As can be seen from the previous articles of this series, an execution plan is composed of physical operators. Each operator is responsible for executing unique computational logics. To implement the `MATCH` clause, the operators such as `GetNeighbors`, `GetVertices`, `Join`, `Project`, `Filter`, and `Loop`, which have been introduced in the previous articles, are needed. Unlike the tree structure in a relational database, the execution process expressed by an execution plan in NebulaGraph is a cyclic graph. How to transform a variable-length pattern into a physical plan in NebulaGraph is the focus of the Planner. In this article, we will introduce how variable-length pattern matching is implemented in NebulaGraph.

# Problem Analysis

## Fixed-Length Pattern

In a `MATCH` clause, a fixed-length pattern is commonly used to search for a relationship. If a fixed-length pattern is considered a special case of the variable-length pattern, that is, a pattern describing a path of a specified length, the implementations of both can be unified. Here are the examples.

```shell
// Fixed-length pattern MATCH (v)-[e]-(v2)
// Variable-length pattern MATCH (v)-[e*1..1]-(v2)
```

The preceding examples differ from each other in the type of the `e` variable. In the fixed-length pattern, `e` represents an edge, while in the variable-length one, `e` represents a list of edges of length 1.  

## Connecting Variable-Length Patterns

According to the syntax of openCypher, a `MATCH` clause allows you to specify a combination of various patterns for describing complicated paths. For example, two variable-length patterns can be connected as follows. 

```shell
MATCH (v)-[e*1..3]-(v2)-[ee*2..4]-(v3)
```

The pattern combination in the preceding example is extendable, which means by connecting variable-length and fixed-length patterns in different ways, various complicated paths can be queried. Therefore, we must find a pattern to generate an execution plan to iterate the whole process recursively. The following conditions must be considered: 

1. The following variable-length path depends on the preceding one.
2. The variables in the following pattern depend on the preceding pattern.
3. Before the next traversal step, the starting vertex must be de-duplicated. 

From the following example, you can see that as long as an execution plan can be generated for the part of `()-[:like*m..n]-`, combinations and iterations may be applied to generate plans for the subsequent parts. 

```shell
()-[:like*m..n]- ()-[:like*k..l]- ()
 \____________/   \____________/   \_/
    Pattern1         Pattern2       Pattern3
```

# Execution Plan

In this section, we will introduce how the ()-[:like*m..n]- part in the preceding example is transformed into a physical execution plan in NebulaGraph. This pattern describes a graph of a minimum of `m` hops and a maximum of `n` hops. In NebulaGraph, a one-step traversal is completed by the `GetNeighbors` operator. To implement a multi-step traversal, each traversal step must call the `GetNeighbors` operator again on the basis of the previous step, and when the traversal of all the steps are completed, all the retrieved vertices and edges are connected end to end to form a single path. What users need is the paths of `m` to `n` relationships. However, in the execution process, paths of length 1 to length `n` are queried and are stored for output or for the next traversal, but only the paths of length `m` to `n` are retrieved. 

## One-Step Traversal

Let's see what the one-step traversal looks like. In NebulaGraph, the source vertex is stored together with its outgoing edges, so retrieving them does not need to access data across partitions. However, the destination vertex and its incoming edges are stored in different partitions, so `GetVertices` is necessary for retrieving the properties of the vertex. In addition, to avoid replicated scanning of Storage, the source vertices must be de-duplicated before the traversal. The execution plan of a one-step traversal is shown as follows. 

![One-Step Traversal](https://user-images.githubusercontent.com/90186547/138244211-8f1aaec3-b1f4-4e52-b74c-7d547b4f350f.png)

## Multi-Step Traversal

The process of a multi-step traversal is the repetition of one-step traversal. However, we can see that the `GetNeighbors` operator can retrieve the properties of an edge's source vertex, so the `GetVertices` operator can be omitted in the previous step. Here is an execution plan of a two-step traversal. 

![Multi-Step Traversal](https://user-images.githubusercontent.com/90186547/138244372-74619d76-8b10-481a-9dde-d065d801f847.png)

## Storing Paths

The paths retrieved in each traversal step may be needed at the end of the traversal, so all the paths must be stored. The paths for a two-step traversal are connected by the `Join` operator. In the result of the example `()-[e:like*m..n]-`, `e` represents a list of data (edges), so `Union` is needed to merge the results of each traversal step. The execution plan will be evolved further as follows.

![One-Step Traversal](https://user-images.githubusercontent.com/90186547/138245877-36d53b4a-0643-4058-8ffb-23502edc0901.png)

## Connecting Variable-Length Patterns

After the implementations of the preceding process, a physical plan will be generated for the `()-[e:like*m..n]-` pattern. If multiple similar patterns are connected together, such a process is iterated. However, before the iteration, the results of the previous process must be filtered to get the paths of length `m` to length `n`. The retrieved dataset of the previous process involves the paths of length 1 to length `n`, so filtering them by path length is needed. When the variable-length patterns are connected together, the execution plan becomes as follows. 

![One-Step Traversal](https://user-images.githubusercontent.com/90186547/138246601-acec9a6e-07b7-4f2d-ba0e-40850dabb63c.png)

After the step-by-step decomposition of the patterns, the expected execution plan for the `MATCH` clause is finally generated. As you can see, it takes a lot of effort to transform a complicated pattern into the underlying interfaces for a traversal. Of course, the execution plan can be optimized, such as the multi-step traversal can be encapsulated by using the Loop operator and the sub-plan of a one-step traversal can be reused, which will not be detailed in this article. If you are interested, please refer to [the source code of NebulaGraph] (https://github.com/vesoft-inc/nebula/blob/master/src/graph/planner/match/Expand.cpp).

# Summary

This article demonstrated the process of generating an execution plan for a `MATCH` clause with a variable-length pattern. While reading the article, you may have this question: Why such a basic and simple path query will generate such a complicated execution plan in NebulaGraph? It's not like Neo4j, where only a few operators are needed to complete the same job. In NebulaGraph, complicated directed acyclic graphs (DAG) are generated. 

The answer is that in NebulaGraph, the operators are closer to the underlying interfaces and there is a lack of semantic abstractions for higher-level graph operations. The operator granularity is too fine, so too many details need to be considered to implement the optimization of the upper layer. We will further study the execution operators to gradually improve the functionality and the performance of the `MATCH` clause.

If you encounter any problems in the process of using NebulaGraph, please refer to [NebulaGraph Database Manual](https://docs.nebula-graph.io/2.5.0/pdf/NebulaGraph-EN.pdf) to troubleshoot the problem. It records in detail the knowledge points and specific usage of the graph database and the graph database NebulaGraph.

Join our [Slack channel](https://join.slack.com/t/nebulagraph/shared_invite/zt-7ybejuqa-NCZBroh~PCh66d9kOQj45g) if you want to discuss with the rest of the NebulaGraph community!


In this article, we will introduce how variable-length pattern matching is implemented in NebulaGraph.

NebulaGraph Source Code Explained: Variable-Length Pattern Matching

In the last article, we mentioned that Validator will convert an AST generated by Parser to an execution plan. In this article, we will explain how an execution plan is generated. 

NebulaGraph Source Code Explained: Planner


![NebulaGraph Source Code Explained: Scheduler & Executor](https://user-images.githubusercontent.com/90186547/136525689-eae7ca90-1c6f-4dc3-b6ce-78a71bbd30f1.png)


You may have learned the optimizer of NebulaGraph's query engine in the last article. In this article, we will introduce how the Scheduler and the Executor, the last two modules of the query engine, are implemented. 

# Overview

In the execution phase, the execution engine uses the Scheduler to transform a physical execution plan, generated by the Planner, into a series of Executors to drive their execution. Each PlanNode in a physical execution plan has a corresponding Executor. 

# Structure of Source Files

The source code of the Scheduler is under the `src/scheduler` directory. 
```
src/scheduler
├── AsyncMsgNotifyBasedScheduler.cpp
├── AsyncMsgNotifyBasedScheduler.h
├── CMakeLists.txt
├── Scheduler.cpp
└── Scheduler.h
```
The Scheduler abstract class defines the common interfaces of the schedulers, which can inherit the features from the class to implement various types of schedulers. The `AsyncMsgNotifyBasedScheduler` scheduler has been implemented. By using the asynchronous message communication and breadth-first search algorithm, it can be prevented from stack overflow errors. 
The source code of the Executor is under the `src/executor` directory. 
```
src/executor
├── admin
├── algo
├── CMakeLists.txt
├── ExecutionError.h
├── Executor.cpp
├── Executor.h
├── logic
├── maintain
├── mutate
├── query
├── StorageAccessExecutor.cpp
├── StorageAccessExecutor.h
└── test
```

# Process

First, the Scheduler starts the traversal of the entire execution plan from its root node by using the breadth-first search algorithm and builds their notification mechanism according to the dependencies between nodes. During the execution phase, each node will be scheduled to be executed after being notified that all the nodes it depends on have been executed successfully. For a node, once executed, it will notify its dependent nodes until the entire plan is executed successfully.


```C++
void AsyncMsgNotifyBasedScheduler::runExecutor(
    std::vector<folly::Future<Status>>&& futures,
    Executor* exe,
    folly::Executor* runner,
    std::vector<folly::Promise<Status>>&& promises) const {
    folly::collect(futures).via(runner).thenTry(
        [exe, pros = std::move(promises), this](auto&& t) mutable {
            if (t.hasException()) {
                return notifyError(pros, Status::Error(t.exception().what()));
            }
            auto status = std::move(t).value();
            auto depStatus = checkStatus(std::move(status));
            if (!depStatus.ok()) {
                return notifyError(pros, depStatus);
            }
            // Execute in current thread.
            std::move(execute(exe)).thenTry(
                [pros = std::move(pros), this](auto&& exeTry) mutable {
                    if (exeTry.hasException()) {
                        return notifyError(pros, Status::Error(exeTry.exception().what()));
                    }
                    auto exeStatus = std::move(exeTry).value();
                    if (!exeStatus.ok()) {
                        return notifyError(pros, exeStatus);
                    }
                    return notifyOK(pros);
                });
        });
}
```

Each Executor goes through four phases: "create", "open", "execute", and then "close". 

## create

In the "create" phase, an appropriate Executor will be generated according to the node type. 

## open

In the "open" phase, before the execution starts, the Executor is initialized, the slow queries are terminated, and the memory watermark is checked. When using NebulaGraph, you can use `kill` to terminate a query, so the status of the current execution plan must be checked before the execution of each Executor. If the plan is in the `killed` status, the execution will be terminated. Before the execution of each query Executor, it is necessary to check whether the amount of free memory has fallen below the watermark. If the watermark is reached, the execution will be terminated, which may avoid OOM.

```C++
Status Executor::open() {
    if (qctx_->isKilled()) {
        VLOG(1) << "Execution is being killed. session: " << qctx()->rctx()->session()->id()
            << "ep: " << qctx()->plan()->id()
            << "query: " << qctx()->rctx()->query();
        return Status::Error("Execution had been killed");
    }
    auto status = MemInfo::make();
    NG_RETURN_IF_ERROR(status);
    auto mem = std::move(status).value();
    if (node_->isQueryNode() && mem->hitsHighWatermark(FLAGS_system_memory_high_watermark_ratio)) {
        return Status::Error(
            "Used memory(%ldKB) hits the high watermark(%lf) of total system memory(%ldKB).",
            mem->usedInKB(),
            FLAGS_system_memory_high_watermark_ratio,
            mem->totalInKB());
    }
    numRows_ = 0;
    execTime_ = 0;
    totalDuration_.reset();
    return Status::OK();
}
```

## execute

The input and output of a query Executor are in the form of tables (DataSet). The execution of an Executor is based on the iterator model, which means that for each calculation, the `next()` method of the iterator of the input table is called to retrieve a row of data and then the calculation is performed. Such a process is repeated until the traversal of the entire input table is done. The results of the calculations are constructed into a new table and output to the next Executor as its input. 

```C++
folly::Future<Status> ProjectExecutor::execute() {
    SCOPED_TIMER(&execTime_);
    auto* project = asNode<Project>(node());
    auto columns = project->columns()->columns();
    auto iter = ectx_->getResult(project->inputVar()).iter();
    DCHECK(!!iter);
    QueryExpressionContext ctx(ectx_);

    VLOG(1) << "input: " << project->inputVar();
    DataSet ds;
    ds.colNames = project->colNames();
    ds.rows.reserve(iter->size());
    for (; iter->valid(); iter->next()) {
        Row row;
        for (auto& col : columns) {
            Value val = col->expr()->eval(ctx(iter.get()));
            row.values.emplace_back(std::move(val));
        }
        ds.rows.emplace_back(std::move(row));
    }
    VLOG(1) << node()->outputVar() << ":" << ds;
    return finish(ResultBuilder().value(Value(std::move(ds))).finish());
}
``` 

If the input table of the current Executor cannot be used by the other Executors as their input, the memory occupied by the table will be dropped in the execution phase to reduce memory usage. 

```C++
void Executor::drop() {
    for (const auto &inputVar : node()->inputVars()) {
        if (inputVar != nullptr) {
            // Make sure use the variable happened-before decrement count
            if (inputVar->userCount.fetch_sub(1, std::memory_order_release) == 1) {
                // Make sure drop happened-after count decrement
                CHECK_EQ(inputVar->userCount.load(std::memory_order_acquire), 0);
                ectx_->dropResult(inputVar->name);
                VLOG(1) << "Drop variable " << node()->outputVar();
            }
        }
    }
}
```

## close

After the execution of an Executor is done, some collected execution information, such as execution time and the number of rows in the output table, is added to the profiling statistics. You can run a `PROFILE` statement and then view the statistics in the returned result. 

```

Execution Plan (optimize time 141 us)

-----+------------------+--------------+-----------------------------------------------------+--------------------------------------
| id | name             | dependencies | profiling data                                      | operator info                       |
-----+------------------+--------------+-----------------------------------------------------+--------------------------------------
|  2 | Project          | 3            | ver: 0, rows: 56, execTime: 147us, totalTime: 160us | outputVar: [                        |
|    |                  |              |                                                     |   {                                 |
|    |                  |              |                                                     |     "colNames": [                   |
|    |                  |              |                                                     |       "VertexID",                   |
|    |                  |              |                                                     |       "player.age"                  |
|    |                  |              |                                                     |     ],                              |
|    |                  |              |                                                     |     "name": "__Project_2",          |
|    |                  |              |                                                     |     "type": "DATASET"               |
|    |                  |              |                                                     |   }                                 |
|    |                  |              |                                                     | ]                                   |
|    |                  |              |                                                     | inputVar: __TagIndexFullScan_1      |
|    |                  |              |                                                     | columns: [                          |
|    |                  |              |                                                     |   "$-.VertexID AS VertexID",        |
|    |                  |              |                                                     |   "player.age"                      |
|    |                  |              |                                                     | ]                                   |
-----+------------------+--------------+-----------------------------------------------------+--------------------------------------
|  3 | TagIndexFullScan | 0            | ver: 0, rows: 56, execTime: 0us, totalTime: 6863us  | outputVar: [                        |
|    |                  |              |                                                     |   {                                 |
|    |                  |              |                                                     |     "colNames": [                   |
|    |                  |              |                                                     |       "VertexID",                   |
|    |                  |              |                                                     |       "player.age"                  |
|    |                  |              |                                                     |     ],                              |
|    |                  |              |                                                     |     "name": "__TagIndexFullScan_1", |
|    |                  |              |                                                     |     "type": "DATASET"               |
|    |                  |              |                                                     |   }                                 |
|    |                  |              |                                                     | ]                                   |
|    |                  |              |                                                     | inputVar:                           |
|    |                  |              |                                                     | space: 318                          |
|    |                  |              |                                                     | dedup: false                        |
|    |                  |              |                                                     | limit: 9223372036854775807          |
|    |                  |              |                                                     | filter:                             |
|    |                  |              |                                                     | orderBy: []                         |
|    |                  |              |                                                     | schemaId: 319                       |
|    |                  |              |                                                     | isEdge: false                       |
|    |                  |              |                                                     | returnCols: [                       |
|    |                  |              |                                                     |   "_vid",                           |
|    |                  |              |                                                     |   "age"                             |
|    |                  |              |                                                     | ]                                   |
|    |                  |              |                                                     | indexCtx: [                         |
|    |                  |              |                                                     |   {                                 |
|    |                  |              |                                                     |     "columnHints": [],              |
|    |                  |              |                                                     |     "index_id": 325,                |
|    |                  |              |                                                     |     "filter": ""                    |
|    |                  |              |                                                     |   }                                 |
|    |                  |              |                                                     | ]                                   |
-----+------------------+--------------+-----------------------------------------------------+--------------------------------------
|  0 | Start            |              | ver: 0, rows: 0, execTime: 1us, totalTime: 19us     | outputVar: [                        |
|    |                  |              |                                                     |   {                                 |
|    |                  |              |                                                     |     "colNames": [],                 |
|    |                  |              |                                                     |     "type": "DATASET",              |
|    |                  |              |                                                     |     "name": "__Start_0"             |
|    |                  |              |                                                     |   }                                 |
|    |                  |              |                                                     | ]                                   |
-----+------------------+--------------+-----------------------------------------------------+--------------------------------------  
```  
So far, the explanation of the query engine source code has been completed. Next time we will explain the implementation of some features of NebulaGraph. 

If you encounter any problems in the process of using NebulaGraph, please refer to [NebulaGraph Database Manual](https://docs.nebula-graph.io/2.5.0/pdf/NebulaGraph-EN.pdf) to troubleshoot the problem. It records in detail the knowledge points and specific usage of the graph database and the graph database NebulaGraph.


Join our [Slack channel](https://join.slack.com/t/nebulagraph/shared_invite/zt-7ybejuqa-NCZBroh~PCh66d9kOQj45g) if you want to discuss with the rest of the NebulaGraph community!


You may have learned the optimizer of NebulaGraph's query engine in the last article. In this article, we will introduce how the Scheduler and the Executor, the last two modules of the query engine, are implemented. 

NebulaGraph Source Code Explained: Scheduler & Executor


![NebulaGraph Source Code Explained: RBO](https://user-images.githubusercontent.com/90186547/133241098-582768eb-c296-4ce1-8f15-4554d668539a.png)

In the last article, we introduced how an execution plan is generated. In this article, we will explain how an execution plan is optimized.

# Overview

Optimizer is a component used to optimize execution plans. Database optimizers are usually divided into two categories: 

- Rule-based optimizer (RBO), which optimizes an execution plan according to the preset rules. All the conditions for matching and the optimization results are relatively fixed. 
- Cost-based optimizer (CBO), which calculates the cost of executing different plans based on the collected data statistics, and then chooses the least costly execution plan.

So far, only RBO has been implemented in NebulaGraph. Therefore, this article will focus on the implementation of RBO in NebulaGraph. 

# Structure of Source Files

You can find the source code of the optimizer in the src/optimizer directory. Here is the structure of the source files. 


```shell
.
├── CMakeLists.txt
├── OptContext.cpp
├── OptContext.h
├── OptGroup.cpp
├── OptGroup.h
├── Optimizer.cpp
├── Optimizer.h
├── OptimizerUtils.cpp
├── OptimizerUtils.h
├── OptRule.cpp
├── OptRule.h
├── rule
│   ├── CombineFilterRule.cpp
│   ├── CombineFilterRule.h
│   ├── EdgeIndexFullScanRule.cpp
│   ├── EdgeIndexFullScanRule.h
|    ....
|
└── test
    ├── CMakeLists.txt
    ├── IndexBoundValueTest.cpp
    └── IndexScanRuleTest.cpp
```

The `test`directory is for testing, the `rule` directory contains the preset rules, and the other source files are source code for implementing the optimizer.

In the `src/service/QueryInstance.cpp` file, you can find the entry into the query optimizer.

```C++
Status QueryInstance::validateAndOptimize() {
    auto *rctx = qctx()->rctx();
    VLOG(1) << "Parsing query: " << rctx->query();
    auto result = GQLParser(qctx()).parse(rctx->query());
    NG_RETURN_IF_ERROR(result);
    sentence_ = std::move(result).value();

    NG_RETURN_IF_ERROR(Validator::validate(sentence_.get(), qctx()));
    NG_RETURN_IF_ERROR(findBestPlan());

    return Status::OK();
}
```

The`findBestPlan` function will call the optimizer to perform optimization and then return an optimized execution plan. 

# Optimization Process

From a topological point of view, an execution plan in NebulaGraph is a directed acyclic graph. It consists of a series of nodes, and each node points to its dependent nodes. In theory, each node can specify the output of any node as input. However, it is meaningless to use the result of a node that has not been executed, so only the nodes that have been executed will be used as the input. Additionally, an execution plan can execute some special nodes such as loops and conditional branches. Figure 1 shows the execution plan of `GO 2 STEPS FROM 'Tim Duncan' OVER like`.

![NebulaGraph Source Code Explained: RBO](https://www-cdn.nebula-graph.com.cn/nebula-blog/optimizer-plan-generator.png)

Figure 1

Currently, the optimizer in NebulaGraph mainly aims to perform pattern matching on the execution plan. If the matching is successful, an appropriate function will be called to transform the matched part of the execution plan according to the preset rules. Let's take the `GetNeighbor` -> `Limit` part of the execution plan as an example. The `Limit` operator will be merged to the `GetNeighbors` operator, so as to implement the pushdown optimization to operators.

# Implementation

The optimizer does not operate directly on an execution plan, but transforms it to `OptGroup` and `OptGroupNode` first. `OptGroup` represents a single optimization group, which usually refers to one or more equivalent operators. `OptGroupNode` represents an independent operator and has pointers to dependencies and branches, which means that `OptGroupNode` retains the topological structure of an execution plan. Why is such a structural transformation needed? It mainly aims to abstract the topological structure of an execution plan, to shield some unnecessary details of execution such as loops and conditional branches, and to facilitate storing some contexts in the new structure for matching rules. 

The transformation process is a simple preorder traversal during which the operators are transformed into the corresponding `OptGroup` and `OptGroupNode`. To facilitate your understanding of the following content, we call the structure composed of `OptGroup` and `OptGroupNode` an optimization plan, which is distinguished from "execution plan".

After transformation, rule matching and optimization plan transformation will be started. In this process, all the pre-defined rules will be traversed, and for each rule, a Bottom-Up traversal will be performed on the optimization plan for matching, which means the traversal starts from `OptGroup` at the deepest leaf node and then to that in the root node, but in each `OptGroup` node, a Top-Down traversal is performed on `OptGroupNode` inside to match the rule pattern. 

As shown in Figure 2, the pattern for matching is `Limit` -> `Project` -> `GetNeighbors`. According to the Bottom-Up order, a Top-Down traversal is performed on the `Start` node first. Because `Start` is not `Limit`, matching fails. And then the similar matching failure occurs to the `GetNeighbors` node until `Limit`. When matching is successful, the `transform` function, defined according to the rules, will transform the part of the optimization plan that matches the rules. For example, in Figure 2, `Limit` and `GetNeighbors` will be merged. 

![NebulaGraph Source Code Explained: RBO](https://www-cdn.nebula-graph.com.cn/nebula-blog/optimizer-transform.jpeg)

Figure 2

Finally, the optimizer will transform the optimized optimization plan into a new execution plan. The process of the last step is opposite to that of the first step, but it is also a process of recursive traversal and transformation. 

# Adding New Rules

In the preceding sections, we introduced how the optimizer is implemented in NebulaGraph. However, if you want to add rules for optimization, understanding too many implementation details is not necessary, but the knowledge of how to define a new rule is required. In this section, we will take the `Limit` pushdown as an example to show how to add a new optimization rule. You can find the source code of the rule in `src/optimizer/rule/LimitPushDownRule.cpp`. 

```C++

std::unique_ptr<OptRule> LimitPushDownRule::kInstance =
    std::unique_ptr<LimitPushDownRule>(new LimitPushDownRule());

LimitPushDownRule::LimitPushDownRule() {
    RuleSet::QueryRules().addRule(this);
}

const Pattern &LimitPushDownRule::pattern() const {
    static Pattern pattern =
        Pattern::create(graph::PlanNode::Kind::kLimit,
                        {Pattern::create(graph::PlanNode::Kind::kProject,
                                         {Pattern::create(graph::PlanNode::Kind::kGetNeighbors)})});
    return pattern;
}
```

```C++
StatusOr<OptRule::TransformResult> LimitPushDownRule::transform(
    OptContext *octx,
    const MatchedResult &matched) const {
    auto limitGroupNode = matched.node;
    auto projGroupNode = matched.dependencies.front().node;
    auto gnGroupNode = matched.dependencies.front().dependencies.front().node;

    const auto limit = static_cast<const Limit *>(limitGroupNode->node());
    const auto proj = static_cast<const Project *>(projGroupNode->node());
    const auto gn = static_cast<const GetNeighbors *>(gnGroupNode->node());

    int64_t limitRows = limit->offset() + limit->count();
    if (gn->limit() >= 0 && limitRows >= gn->limit()) {
        return TransformResult::noTransform();
    }

    auto newLimit = static_cast<Limit *>(limit->clone());
    auto newLimitGroupNode = OptGroupNode::create(octx, newLimit, limitGroupNode->group());

    auto newProj = static_cast<Project *>(proj->clone());
    auto newProjGroup = OptGroup::create(octx);
    auto newProjGroupNode = newProjGroup->makeGroupNode(newProj);

    auto newGn = static_cast<GetNeighbors *>(gn->clone());
    newGn->setLimit(limitRows);
    auto newGnGroup = OptGroup::create(octx);
    auto newGnGroupNode = newGnGroup->makeGroupNode(newGn);

    newLimitGroupNode->dependsOn(newProjGroup);
    newProjGroupNode->dependsOn(newGnGroup);
    for (auto dep : gnGroupNode->dependencies()) {
        newGnGroupNode->dependsOn(dep);
    }

    TransformResult result;
    result.eraseAll = true;
    result.newGroupNodes.emplace_back(newLimitGroupNode);
    return result;
}

std::string LimitPushDownRule::toString() const {
    return "LimitPushDownRule";
}
```

To define a rule, the first thing is inheriting the `OptRule class`, and then implementing the `pattern` interface, where returning the pattern that needs to be matched is required. A pattern is a composition of operators and their dependencies such as `Limit`->`Project`->`GetNeighbors`. The next one to be implemented is the `transform` interface, which passes in an optimization plan for matching. This interface will analyze the matched optimization plan according to the pre-defined pattern and then optimize and transform the plan. For example, it merges the `Limit` operator and the `GetNeighbors` operator and then returns an optimized optimization plan. 

When these two interfaces are implemented correctly, the new optimization rule can work. 

This is all about RBO in NebulaGraph. 

If you encounter any problems in the process of using NebulaGraph, please refer to "NebulaGraph Database Manual" to troubleshoot the problem. It records in detail the knowledge points and specific usage of the graph database and the graph database NebulaGraph.

Here is the link:
[https://docs.nebula-graph.io/2.5.0/pdf/NebulaGraph-EN.pdf](https://docs.nebula-graph.io/2.5.0/pdf/NebulaGraph-EN.pdf)

Join our [Slack channel](https://join.slack.com/t/nebulagraph/shared_invite/zt-7ybejuqa-NCZBroh~PCh66d9kOQj45g) if you want to discuss with the rest of the NebulaGraph community!


In the last article, we introduced how an execution plan is generated. In this article, we will explain how an execution plan is optimized.

NebulaGraph Source Code Explained: RBO


![NebulaGraph Source Code Explained: Validator](https://user-images.githubusercontent.com/57335825/130582849-418baabf-9377-4736-bcfd-391030edf46c.png)

# Architecture 

NebulaGraph Query Engine consists of four major modules: Parser, Validator, Optimizer, and Executor.  

![NebulaGraph Query Engine Architecture](https://user-images.githubusercontent.com/57335825/130588147-0508a907-cc63-4f8e-b5d3-20d65104a43d.png)

Parser is responsible for performing lexical and syntax analysis on a statement and generating an AST (Abstract Syntax Tree). Validator aims to convert an AST into an execution plan. Optimizer optimizes the execution plan. And Executor is designed to perform computing on the data.

In this article, we will introduce how Validator is implemented.

# Structure of Source Files

The directories for the source code of Validator are `src/validator` and `src/planner`.

The `src/validator` directory contains the code for implementing the validators for the clauses, such as `OrderByValidator`, `LimitValidator`, and `GoValidator`.

``` 
validator/
├── ACLValidator.h
├── AdminJobValidator.h
├── AdminValidator.h
├── AssignmentValidator.h
├── BalanceValidator.h
├── DownloadValidator.h
├── ExplainValidator.h
├── FetchEdgesValidator.h
├── FetchVerticesValidator.h
├── FindPathValidator.h
├── GetSubgraphValidator.h
├── GoValidator.h
├── GroupByValidator.h
├── IngestValidator.h
├── LimitValidator.h
├── LookupValidator.h
├── MaintainValidator.h
├── MatchValidator.h
├── MutateValidator.h
├── OrderByValidator.h
├── PipeValidator.h
├── ReportError.h
├── SequentialValidator.h
├── SetValidator.h
├── TraversalValidator.h
├── UseValidator.h
├── Validator.h
└── YieldValidator.h 
```

The `src/planner/plan` directory defines the data structure of all the PlanNodes, aiming to generate the execution plans. For example, if a query statement contains aggregate functions, an `Aggregate` node will be generated in the execution plan, and the `Aggregate` class, defined in `Query.h`, specifies all the information necessary for the computation of the aggregate functions, including grouping keys and aggregate expressions. In NebulaGraph, more than 100 PlanNodes have been defined. For more information, see PlanNode∷kind in [PlanNode.h](https://github.com/vesoft-inc/nebula-graph/blob/master/src/planner/plan/PlanNode.h).

``` 
planner/plan/
├── Admin.cpp          
├── Admin.h             // administration related  nodes
├── Algo.cpp
├── Algo.h              // graph algorithm related nodes
├── ExecutionPlan.cpp
├── ExecutionPlan.h     // explain and profile nodes
├── Logic.cpp
├── Logic.h             // nodes introduced by the implementation layer
├── Maintain.cpp
├── Maintain.h          // schema related nodes
├── Mutate.cpp
├── Mutate.h            // DML related nodes
├── PlanNode.cpp
├── PlanNode.h          // plan node base classes
├── Query.cpp
├── Query.h             // DQL related nodes
└── Scan.h              // index related nodes
 ```

Additionally, the `src/planner` directory contains the code for implementing the planners of nGQL and `MATCH` statements. These planners are used to generate the execution plans of nGQL and `MATCH` statements.

# Explaining Source Code

The entry function of Validator is `Validator::validate(Sentence*, QueryContext*)`. It is responsible for converting the AST, generated by Parser, into an execution plan. `QueryContext` stores the root node of the execution plan. Here is the source code of this function.

```cpp 
Status Validator::validate(Sentence* sentence, QueryContext* qctx) {
    DCHECK(sentence != nullptr);
    DCHECK(qctx != nullptr);

    // Check if space chosen from session. if chosen, add it to context.
    auto session = qctx->rctx()->session();
    if (session->space().id > kInvalidSpaceID) {
        auto spaceInfo = session->space();
        qctx->vctx()->switchToSpace(std::move(spaceInfo));
    }

    auto validator = makeValidator(sentence, qctx);
    NG_RETURN_IF_ERROR(validator->validate());

    auto root = validator->root();
    if (!root) {
        return Status::SemanticError("Get null plan from sequential validator");
    }
    qctx->plan()->setRoot(root);
    return Status::OK();
} 
```

This function retrieves the graph space information of the current session, stores the information in ValidateContext, and then calls `Validator::makeValidator()` and `Validator::validate()`. 

`Validator::makeValidator()` aims to generate validators for clauses. It generates SequentialValidator, the entry of Validator. For each statement, SequentialValidator is generated first, and then a validator is recursively generated.

`SequentialValidator::validateImpl()` will call `Validator::makeValidator()` to generate an appropriate validator for each clause. Here is the source code of this function.

```cpp
Status SequentialValidator::validateImpl() {
    Status status;
    if (sentence_->kind() != Sentence::Kind::kSequential) {
        return Status::SemanticError(
                "Sequential validator validates a SequentialSentences, but %ld is given.",
                static_cast<int64_t>(sentence_->kind()));
    }
    auto seqSentence = static_cast<SequentialSentences*>(sentence_);
    auto sentences = seqSentence->sentences();

    seqAstCtx_->startNode = StartNode::make(seqAstCtx_->qctx);
    for (auto* sentence : sentences) {
        auto validator = makeValidator(sentence, qctx_);
        NG_RETURN_IF_ERROR(validator->validate());
        seqAstCtx_->validators.emplace_back(std::move(validator));
    }

    return Status::OK();
}
 ```

Similarly, PipeValidator, AssignmentValidator, and SetValidator will generate appropriate validators for the corresponding clauses.

`Validator::validate()` is responsible for generating an execution plan. The source code of this function is as follows.

```cpp
Status Validator::validate() {
    auto vidType = space_.spaceDesc.vid_type_ref().value().type_ref().value();
    vidType_ = SchemaUtil::propTypeToValueType(vidType);

    NG_RETURN_IF_ERROR(validateImpl());

    // Check for duplicate reference column names in pipe or var statement
    NG_RETURN_IF_ERROR(checkDuplicateColName());

    // Execute after validateImpl because need field from it
    if (FLAGS_enable_authorize) {
        NG_RETURN_IF_ERROR(checkPermission());
    }

    NG_RETURN_IF_ERROR(toPlan());

    return Status::OK();
}
```

This function does a check of the information of the graph space and authentication first, and then calls `Validator:validateImpl()` to validate the clauses. The `validateImpl()` function is a pure virtual function of the Validator class. It uses polymorphism to call different `validatorImpl()` functions for different clauses. Finally, the `Validator::toPlan()` function is called to generate an execution plan. The `toPlan()` function will generate subplans for the clauses and these subplans will be connected to form a complete execution plan for the statement. For example, for a MATCH statement, `MatchPlanner::connectSegments()` is called to connect all the subplans, but for an nGQL statement, `Validator::appendPlan()` is called for connection.

# An Example

In this section, we will take an nGQL statement as an example to show the procedure.

Here is the example statement.

```
GO 3 STEPS FROM "vid" OVER edge 
WHERE $$.tag.prop > 30 
YIELD edge._dst AS dst 
| ORDER BY $-.dst
```

In the Validator phase of this example statement, all these three steps are necessary:

## Generating validators for the clauses

Firstly, `Validator::makeValidator()` is called to generate SequentialValidator. In the `SequentialValidator::validateImpl()` function, PipeValidator will be generated, which produces validators for the clauses separated by the pipe symbol (|), that is, GoValidator and OrderByValidator.
 
## Validating the clauses

In this step, the GO and ORDER BY clauses are validated separately.

Let's take the GO clause as an example. Firstly, it is verified for the semantic errors, such as invalid aggregate functions and type mismatch in expressions. Secondly, the subclauses inside it are validated one by one. During the validation phase, all the intermediate results are stored in GoContext, which will be used as the basis for GoPlanner to generate its subplan. For example, validateWhere() stores the filter condition expressions to generate the Filter node. 

```cpp
    NG_RETURN_IF_ERROR(validateStep(goSentence->stepClause(), goCtx_->steps));  // Validate step clause
    NG_RETURN_IF_ERROR(validateStarts(goSentence->fromClause(), goCtx_->from)); // Validate from clause
    NG_RETURN_IF_ERROR(validateOver(goSentence->overClause(), goCtx_->over));   // Validate over clause
    NG_RETURN_IF_ERROR(validateWhere(goSentence->whereClause()));               // Validate where clause
    NG_RETURN_IF_ERROR(validateYield(goSentence->yieldClause()));               // Validate yield clause
``` 

## Generating the execution plan
  
The subplan of the GO statement is generated by GoPlanner∷transform(Astcontext*). Its source code is as follows.

```cpp
StatusOr<SubPlan> GoPlanner::transform(AstContext* astCtx) {
    goCtx_ = static_cast<GoContext *>(astCtx);
    auto qctx = goCtx_->qctx;
    goCtx_->joinInput = goCtx_->from.fromType != FromType::kInstantExpr;
    goCtx_->joinDst = !goCtx_->exprProps.dstTagProps().empty();

    SubPlan startPlan = QueryUtil::buildStart(qctx, goCtx_->from, goCtx_->vidsVar);

    auto& steps = goCtx_->steps;
    if (steps.isMToN()) {
        return mToNStepsPlan(startPlan);
    }

    if (steps.steps() == 0) {
        auto* pt = PassThroughNode::make(qctx, nullptr);
        pt->setColNames(std::move(goCtx_->colNames));
        SubPlan subPlan;
        subPlan.root = subPlan.tail = pt;
        return subPlan;
    }

    if (steps.steps() == 1) {
        return oneStepPlan(startPlan);
    }
    return nStepsPlan(startPlan);
}
```

This function calls `QueryUtil::buildStart()` to construct the Start node first. And then appropriate methods are used to generate plans for the four different steps. In this example statement, the nStepPlan strategy is used.

Here is the source code of `GoPlanner::nStepsPlan()`.

```cpp
SubPlan GoPlanner::nStepsPlan(SubPlan& startVidPlan) {
    auto qctx = goCtx_->qctx;

    auto* start = StartNode::make(qctx);
    auto* gn = GetNeighbors::make(qctx, start, goCtx_->space.id);
    gn->setSrc(goCtx_->from.src);
    gn->setEdgeProps(buildEdgeProps(true));
    gn->setInputVar(goCtx_->vidsVar);

    auto* getDst = QueryUtil::extractDstFromGN(qctx, gn, goCtx_->vidsVar);

    PlanNode* loopBody = getDst;
    PlanNode* loopDep = nullptr;
    if (goCtx_->joinInput) {
        auto* joinLeft = extractVidFromRuntimeInput(startVidPlan.root);
        auto* joinRight = extractSrcDstFromGN(getDst, gn->outputVar());
        loopBody = trackStartVid(joinLeft, joinRight);
        loopDep = joinLeft;
    }

    auto* condition = loopCondition(goCtx_->steps.steps() - 1, gn->outputVar());
    auto* loop = Loop::make(qctx, loopDep, loopBody, condition);

    auto* root = lastStep(loop, loopBody == getDst ? nullptr : loopBody);
    SubPlan subPlan;
    subPlan.root = root;
    subPlan.tail = startVidPlan.tail == nullptr ? loop : startVidPlan.tail;

    return subPlan;
}
```

Here is the subplan of the GO statement.

```
Start -> GetNeighbors -> Project -> Dedup -> Loop -> GetNeighbors -> Project -> GetVertices -> Project -> LeftJoin -> Filter -> Project
```

A GO statement aims to expand querying of a graph. GetNeighbors is the most important node in the execution plan. The GetNeighbors operator will access the storage service during the execution to retrieve the VID of the destination vertex according to the source vertex and the specified edge type. An expansion across multiple steps is implemented through the Loop node. Between the Start node and the Loop node, it is the subplans of Loop. When the condition is satisfied, the execution of these subplans will be looped. And then the last step of an expansion is executed outside Loop. The Project node aims to retrieve the VID of the destination vertex of such an expansion. The Dedup node is responsible for deduplicating the VIDs of the destination vertices, which will be used as the starting vertices of the next expansion. GetVertices is responsible for retrieving the tag properties of the destination vertices. The Filter node aims to filter vertices based on the conditions. The LeftJoin node works to connect the results of GetNeightbors and GetVertices.

The ORDER BY clause is designed to sort data. Its subplan generates the Sort node. After the plans for the clauses on the left and right sides of the pipe symbol (|) are generated, `PipeValidator::toPlan()` will call `Validator::appendPlan()` to connect these subplans to obtain the complete execution plan, which is shown as follows:

```
Start -> GetNeighbors -> Project -> Dedup -> Loop -> GetNeighbors -> Project -> GetVertices -> Project -> LeftJoin -> Filter -> Project -> Sort -> DataCollect 
```

## Relevant Questions

> Q: How can I get the parser/GraphParser.hpp file?

A: A .h file will be generated after compiling.

Stay tuned for the next piece of the source code reading series.

Join our [Slack channel](https://join.slack.com/t/nebulagraph/shared_invite/zt-7ybejuqa-NCZBroh~PCh66d9kOQj45g) if you want to discuss with the rest of the NebulaGraph community!

In this article, we will introduce how Validator is implemented.

NebulaGraph Source Code Explained: Validator


![NebulaGraph Source Code Explained: An Overview](https://user-images.githubusercontent.com/57335825/129310757-1a4e31b4-1ead-4c70-a17d-6d3afa96a182.png)

In [NebulaGraph Source Code Explained: Preface](https://nebula-graph.io/posts/nebula-graph-source-code-reading-00/), we introduced why this series of articles are being published. In this article, we will introduce the architecture of NebulaGraph, its source code repositories, the hierarchy of its code, and the development planning of the modules.

# 1. Architecture

NebulaGraph is an open-source, distributed graph database solution. In NebulaGraph, compute is separated from storage. Besides the graph database kernel, we also provide many tools for importing data, monitoring, deployment, visualization, graph compute, and so on.

For more information about the design of NebulaGraph, see [NebulaGraph Architecture — A Bird's Eye View](https://nebula-graph.io/posts/nebula-graph-architecture-overview/).  

Architecture of NebulaGraph:  

![Architecture of NebulaGraph](https://user-images.githubusercontent.com/57335825/129311075-e353aa39-7a69-49d1-bd11-a96996ed390c.png) 
  
For more information about the query engine, see [An Introduction to NebulaGraph's Query Engine](https://nebula-graph.io/posts/nebula-graph-query-engine-overview/) and [An Introduction to NebulaGraph 2.0 Query Engine](https://nebula-graph.io/posts/nebula-query-engine-introduction/).

The query engine has adopted stateless design, which enables horizontal scaling in/out easily. The engine is composed of Parser, Validator, Optimizer, and Executor.

Architecture of the query engine:  

![Architecture of the query engine](https://user-images.githubusercontent.com/57335825/129325703-0b3a614a-a003-4280-86b6-ac591570d07c.png)  

In NebulaGraph, two storage services are provided. One is for storing metadata, which is called the Meta Service, and the other is for storing business data, which is called the Storage Service.

In the Storage Service, there are three layers. The bottom layer is Store Engine, above it is the layer for implementing the consensus algorithm of multi-group Raft, and the top layer is the storage interfaces, that is, a set of graph-related APIs.  

For more information about the storage engine, see [An Introduction to NebulaGraph's Storage Engine](https://nebula-graph.io/posts/nebula-graph-storage-engine-overview/).  

Here is the architecture of the Storage Service.

![Architecture of the Storage Service](https://user-images.githubusercontent.com/57335825/129338297-cf0e7343-9ded-4f44-b56c-b0457b863b00.png)

# 2. Introduction to Repositories

Welcome to the [vesoft-inc]([vesoft](https://github.com/vesoft-inc)) project repositories. vesoft Inc. is the vendor of NebulaGraph, a distributed graph database solution.

So far, the vesoft-inc project repositories have covered the kernel of NebulaGraph, clients, tools, testing framework, compiling tools, visualization tools, monitoring product, and so on.

This article mainly focuses on the hierarchy of the major repositories of NebulaGraph and the basic functionalities of each module. More introductions to design details are coming. We hope that it could help you understand NebulaGraph better and make more contributions to the NebulaGraph community, such as submitting features, fixing bugs, and contributing to the documentation.  

The following is a list of major repositories under the vesoft-inc account on GitHub:

- [nebula](https://github.com/vesoft-inc/nebula): NebulaGraph kernel

- Nebula Clients
    - [nebula-java](https://github.com/vesoft-inc/nebula-java): Client in Java
    - [nebula-cpp](https://github.com/vesoft-inc/nebula-cpp): Client in CPP
    - [nebula-go](https://github.com/vesoft-inc/nebula-go): Client in Go
    - [nebula-python](https://github.com/vesoft-inc/nebula-python): Client in Python

- Nebula Tools
    - [nebula-importer](https://github.com/vesoft-inc/nebula-importer): A high-performance data importer based on the client in Go
    - [nebula-spark-utils](https://github.com/vesoft-inc/nebula-spark-utils): Spark applications, such as Nebula Spark Connector, Nebula Exchange, and Nebula Algorithm
    - [nebula-br](https://github.com/vesoft-inc/nebula-br): The backup and storage tool of NebulaGraph
    - [nebula-ansible](https://github.com/vesoft-inc/nebula-ansible), [nebula-operator](https://github.com/vesoft-inc/nebula-operator): The tool for automating the deployment of NebulaGraph clusters

- Nebula Testing
    - [nebula-bench](https://github.com/vesoft-inc/nebula-bench): Stress testing and performance testing of NebulaGraph
    - [nebula-chaos](https://github.com/vesoft-inc/nebula-chaos): Chaos framework for NebulaGraph

- Compiling
    - [nebula-third-party](https://github.com/vesoft-inc/nebula-third-party): All the third-party libraries that are necessary for compiling NebulaGraph
    - [nebula-gears](https://github.com/vesoft-inc/nebula-gears): Gears for NebulaGraph

- [nebula-graph-studio](https://github.com/vesoft-inc/nebula-graph-studio): The visualization tool of NebulaGraph
  
# 3. Structure of Source Files and Modules

## 3.1 NebulaGraph

The address of the nebula-graph repository is https://github.com/vesoft-inc/nebula-graph.

```
├── cmake
├── conf
├── LICENSES
├── package
├── resources
├── scripts
├── src
│   ├── context
│   ├── daemons
│   ├── executor
│   ├── optimizer
│   ├── parser
│   ├── planner
│   ├── scheduler
│   ├── service
│   ├── session
│   ├── stats
│   ├── util
│   ├── validator
│   └── visitor
└── tests
    ├── admin
    ├── bench
    ├── common
    ├── data
    ├── job
    ├── maintain
    ├── mutate
    ├── query
    └── tck
```  

- conf/: Contains the configuration files of the query engine.
- package/: Contains the packaging script of the Graph Service.
- resources/: Contains the resource files.
- scripts/: Contains the startup scripts.
- src/: Contains the source code of the query engine.
    - src/context/: The context of a query, including AST (Abstract Syntax Tree), Execution Plan, execution result, and other resources for computing
    - src/daemons/: The main process of the query engine
    - src/executor/: The executor, implementing all the operators
    - src/optimizer/: Implementing RBO (Rule Based Optimization) and providing rules for optimization
    - src/parser/: Lexical analysis and parsing. Defining the structure of AST
    - src/planner/: Operators and generating execution plans
    - src/scheduler/: Scheduler of the execution plans
    - src/service/: The service layer of the query engine, providing interfaces for authentication and executing queries
    - src/session/: Managing sessions
    - src/stats/: Performing statistics, such as P99 and statistics of slow queries
    - src/util/: Tool functions
    - src/validator/: Implementing semantic analysis, for validating the syntax and performing simple optimization
    - src/visitor/: Expression visitor, for extracting information from the expressions and optimizing the expressions
- tests/: BDD-based integration testing framework, for testing all the features of NebulaGraph.

## 3.2 Nebula Storage

```
├── cmake
├── conf
├── docker
├── docs
├── LICENSES
├── package
├── scripts
└── src
    ├── codec
    ├── daemons
    ├── kvstore
    ├── meta
    ├── mock
    ├── storage
    ├── tools
    ├── utils
    └── version
```  

- conf/: Contains the configuration files of the storage engine.
- package/: Contains the packaging script of the storage services.
- scripts/: Contains the startup scripts.
- src/: Contains the source code of the storage engine.
    - src/codec/: Tools for serialization and unserialization
    - src/daemons/: The main process of the storage engine and the metadata engine
    - src/kvstore/: Implementing a distributed KV store based on raft algorithm
    - src/meta/: Implementing the metadata management service based on KVStore, for managing the metadata, the clusters, and the long tasks
    - src/storage/: Implementing the storage engine based on KVStore
    - src/tools/: Implementing some widgets
    - src/utils/: Tool functions

## 3.3 Nebula Common

```
├── cmake
│   └── nebula
├── LICENSES
├── src
│   └── common
│       ├── algorithm
│       ├── base
│       ├── charset
│       ├── clients
│       ├── concurrent
│       ├── conf
│       ├── context
│       ├── cpp
│       ├── datatypes
│       ├── encryption
│       ├── expression
│       ├── fs
│       ├── function
│       ├── graph
│       ├── hdfs
│       ├── http
│       ├── interface
│       ├── meta
│       ├── network
│       ├── plugin
│       ├── process
│       ├── session
│       ├── stats
│       ├── test
│       ├── thread
│       ├── thrift
│       ├── time
│       ├── version
│       └── webservice
└── third-party
```  

The nebula-common repository has the toolkit of the NebulaGraph kernel code. All these tools are commonly used and their source code is of high efficiency. Developers may be familiar with some of these tools. In this section, only some subdirectories closely related to graph databases are listed:

- src/common/clients/: Implementing the meta and the storage clients in C++
- src/common/datatypes/: Defining the data type and computation in NebulaGraph, such as string, int, bool, float, Vertex, and Edge
- rc/common/expression/: Defining the expressions in nGQL
- src/common/function/: Defining functions in nGQL
- src/common/interface/: Defining the interfaces for the NebulaGraph, the Nebula Meta, and the Nebula Storage services.

Stay tuned for the next piece of the source code reading series.

Join our [Slack channel](https://join.slack.com/t/nebulagraph/shared_invite/zt-7ybejuqa-NCZBroh~PCh66d9kOQj45g) if you want to discuss with the rest of the NebulaGraph community!


In this article, we will introduce the architecture of NebulaGraph, its source code repositories, the hierarchy of its code, and the development planning of the modules.

NebulaGraph Source Code Explained: An Overview


![NebulaGraph Source Code Explained ｜ Vol.00 Preface](https://user-images.githubusercontent.com/57335825/128325420-b20e4cee-76f1-45be-8cdc-0a370a07e00e.png)

NebulaGraph is an open-source, distributed graph database solution developed by [Vesoft Inc.](https://www.vesoft.com/en/). The solution mainly aims to solve the new challenges in analyzing and mining connected data caused by the generation of massive data. Since it was open sourced in May 2019, NebulaGraph has gained much traction. Many companies, technical teams, and developers have adopted NebulaGraph in their businesses such as knowledge graph, risk control, data governance, anti-fraud, and real-time recommendations. In the NebulaGraph community, our users have been actively sharing their use cases of NebulaGraph and all of them help others understand the database better. 

Meanwhile, there is a growing voice in the community for how NebulaGraph is designed and implemented. Therefore, we have prepared a series of articles exlplaining the source code of NebulaGraph, hoping that by explaining the design and implementation of NebulaGraph in these articles you can understand and use NebulaGraph better. Besides, we hope that these articles will enable you to make NebulaGraph a better product together with our community.

# Agenda

This series is mainly about the architecture and the kernel of NebulaGraph. Additionally, the community members are concerned about the performance problems caused by the architecture limitations, and we will discuss them in the last article of this series.  It should be noted that this series aim to explain the source code, but it is not only about explaining how the functions and features are implemented. It more focuses on guiding you to master NebulaGraph from a designer's perspective by understanding the ideas behind it via explaining the source code. 

NOTE: NebulaGraph is still under continuous development and more features are being continuously merged to the master branch. Therefore, this series will not go into too many details of how these ongoing modules are implemented.

Here is the agenda of this series:

- NebulaGraph overview: Introduces the architecture of NebulaGraph, its source code repositories, the hierarchy of its code, and its development planning of the modules.
- Understanding the Kernel: Introduces parsing, optimization, scheduling, and other modules, as well as the implementations of the clients in Java, Python, and other languages.
- Communications between components: Introduces how NebulaGraph communicates internally.
- New features of NebulaGraph 2.0: Introduces how MATCH is implemented by introducing the implementation of two features of variable-length pattern matching and indexing.
- Architecture limitations and solutions: Introduces the solutions to the problems that are of general concern in the community, such as aborting slow queries and processing super vertices.

We hope this series of articles could help you understand NebulaGraph better, knowing how the new features are implemented, so that you can solve problems from an implementation perspective. Besides, we hope it will enable you to submit PRs more in line with the NebulaGraph design ideas to the NebulaGraph repositories. 

# A Complete Guide to NebulaGraph

This series focuses on how NebulaGraph is implemented, but [A Complete Guide to NebulaGraph](https://docs.nebula-graph.io/2.0.1/pdf/NebulaGraph-EN.pdf) is a complete manual of NebulaGraph. This guide starts with an introduction to graph database and then how to use nGQL and related parameters. It is a complete solution to using NebulaGraph.

# Technical Knowledge Requirements

This series try to introduce NebulaGraph for most people, but they would be more appropriate if you have the following technical knowledge:

- Database basics
- NebulaGraph architecture
- C++ language: NebulaGraph is implemented in C++ language. If you have learned C++, you can understand its source code more quickly

# Before the End

This is our first try of writing a series of articles to introduce the implementations of NebulaGraph. If you find a mistake or have a suggestion, please feel free to send your feedback to us on the social media platforms such as our forum and the Slack channel. All your feedback will help us improve the subsequent articles.  

Join our [Slack channel](https://join.slack.com/t/nebulagraph/shared_invite/zt-7ybejuqa-NCZBroh~PCh66d9kOQj45g) if you want to discuss with the rest of the NebulaGraph community!


This is a series trying to explain the source code of NebulaGraph to developers in the community.