Add undirected query

[andyfengHKU]

Goal

The goal of this issue is to support undirected query in a similar fashion as Neo4j.

Neo4j supports 3 types of relationship

• Left-to-right, e.g.(a)-[e]->(b)
• Right-to-left, e.g. (a)<-[e]-(b)
• Undirected, e.g. (a)-[e]-(b)

Currently we support left-to-right and right-to-left in the system and missing the undirected one.

Design Details

The semantic of undirected is simply the union of left-to-right and right-to-left and should be implemented by solely changing the extend operator.

In query compilation, we should change query edge to be able to take UNDIRECTED as a direction and propagate this change to logic extend.

In query processing, recall that we have implemented a GenericScanRelTable which takes one adjList from each rel table and scan them one by one. Undirected extend should further modify GenericScanRelTable such that it takes both fwd and bwd adjList from each rel table. From a high level view, GenericScanRelTable still scans multiple adjList. Undirected extend simply adds more adjList to scan.

TODOs

• Add undirected query edge and propagate this change to logical extend. Changes include but not limit to parser, binder, logical extend and cardinality estimator.
• Modify GenericScanRelTable to take fwd and bwd adjList from a single rel table. (Example test query (a:Person)-[:knows]->(b:Person))
• Modify GenericScanRelTable to take fwd and bwd adjColumn from a single rel table. (Example test query (a:Person)-[:meets]->(b:Person))
• Modify GenericScanRelTable to take fwd and bwd adjList/Column from multiple rel tables. (Example test query (a:Person)-[:meets|:knows]->(b:Person))