Can't TRAVERSE through LINKMAP

[mmacfadden]

OrientDB Version: 3.0.26

Java Version: OpenJDK 11

OS: Linux

Expected behavior

Ability to use TRAVERSE in the Document API through a LINKMAP.

Actual behavior

Only the initial entry point node is returned.

Steps to reproduce

1. Create the DataValue class

CREATE CLASS DataValue;
CREATE PROPERTY DataValue.id String;
CREATE PROPERTY DataValue.children LINKMAP DataValue;

2. Insert Data and then TRAVERSE

LET r1 = INSERT INTO DataValue SET id="r1", children={};
LET r2 = INSERT INTO DataValue SET id="r2", children={};

LET r1c1 = INSERT INTO DataValue SET id="r1c1", children={};
LET r1c2 = INSERT INTO DataValue SET id="r1c2", children={};
LET r1c2c1 = INSERT INTO DataValue SET id="r1c2c1", children={};
LET r1c2c2 = INSERT INTO DataValue SET id="r1c2c2", children={};

LET r2c1 = INSERT INTO DataValue SET id="r2c1", children={};
LET r2c2 = INSERT INTO DataValue SET id="r2c2", children={};

UPDATE DataValue SET children.c1 = $r1c1[0] WHERE id = "r1";
UPDATE DataValue SET children.c2 = $r1c2[0] WHERE id = "r1";

UPDATE DataValue SET children.c1 = $r1c2c1[0] WHERE id = "r1c2";
UPDATE DataValue SET children.c2 = $r1c2c2[0] WHERE id = "r1c2";

UPDATE DataValue SET children.c1 = $r2c1[0] WHERE id = "r2";
UPDATE DataValue SET children.c2 = $r2c2[0] WHERE id = "r2";

TRAVERSE children FROM (SELECT FROM DataValue WHERE id = "r1");

Only the r1 element is returned.

{
    "result": [
        {
            "@type": "d",
            "@rid": "#40:0",
            "@version": 3,
            "@class": "DataValue",
            "children": {
                "c1": "#34:1",
                "c2": "#35:1"
            },
            "id": "r1"
        }
    ],
    "notification": "Query executed  in 0.021 sec. Returned 1 record(s)"
}

Is it not possible to TRAVERSE through links in a LINKMAP? I have not gone back and verified, but I thought this was possible in a previous 3.0.X version.

[mmacfadden]

Also, I checked a similar use case with a LINKLIST, and it worked as expected. Here is the reproduction:

1. Create DataValue class with LINKLIST

CREATE CLASS DataValue;
CREATE PROPERTY DataValue.id String;
CREATE PROPERTY DataValue.children LINKLIST DataValue;

2. Insert data and TRAVERSE:

LET r1 = INSERT INTO DataValue SET id="r1", children={};
LET r2 = INSERT INTO DataValue SET id="r2", children={};

LET r1c1 = INSERT INTO DataValue SET id="r1c1", children={};
LET r1c2 = INSERT INTO DataValue SET id="r1c2", children={};
LET r1c2c1 = INSERT INTO DataValue SET id="r1c2c1", children={};
LET r1c2c2 = INSERT INTO DataValue SET id="r1c2c2", children={};

LET r2c1 = INSERT INTO DataValue SET id="r2c1", children={};
LET r2c2 = INSERT INTO DataValue SET id="r2c2", children={};

UPDATE DataValue SET children = [$r1c1[0], $r1c2[0]] WHERE id = "r1";
UPDATE DataValue SET children = [$r1c2c1[0], $r1c2c2[0]] WHERE id = "r1c2";

UPDATE DataValue SET children = [$r2c1[0], $r2c2[0]] WHERE id = "r2";

TRAVERSE children FROM (SELECT FROM DataValue WHERE id = "r1");

The traversal now seems to work as I would have expected:

{
    "result": [
        {
            "@type": "d",
            "@rid": "#33:0",
            "@version": 2,
            "@class": "DataValue",
            "children": [
                "#35:0",
                "#36:0"
            ],
            "id": "r1",
            "@fieldTypes": "children=z"
        },
        {
            "@type": "d",
            "@rid": "#36:0",
            "@version": 2,
            "@class": "DataValue",
            "children": [
                "#37:0",
                "#38:0"
            ],
            "id": "r1c2",
            "@fieldTypes": "children=z"
        },
        {
            "@type": "d",
            "@rid": "#38:0",
            "@version": 1,
            "@class": "DataValue",
            "children": [
                
            ],
            "id": "r1c2c2",
            "@fieldTypes": "children=z"
        },
        {
            "@type": "d",
            "@rid": "#37:0",
            "@version": 1,
            "@class": "DataValue",
            "children": [
                
            ],
            "id": "r1c2c1",
            "@fieldTypes": "children=z"
        },
        {
            "@type": "d",
            "@rid": "#35:0",
            "@version": 1,
            "@class": "DataValue",
            "children": [
                
            ],
            "id": "r1c1",
            "@fieldTypes": "children=z"
        }
    ],
    "notification": "Query executed  in 0.026 sec. Returned 5 record(s)"
}

[mmacfadden]

Investigating more, it seems like the issue might be in the following class:

orientdb/core/src/main/java/com/orientechnologies/orient/core/sql/executor/DepthFirstTraverseStep.java

Line 110 in 3ccd061

private void addNextEntryPoints(Object nextStep, int depth, List<OIdentifiable> path, List<OIdentifiable> stack,

private void addNextEntryPoints(Object nextStep, int depth, List<OIdentifiable> path, List<OIdentifiable> stack,
      OCommandContext ctx) {
    if (nextStep instanceof OIdentifiable) {
      addNextEntryPoint(((OIdentifiable) nextStep), depth, path, stack, ctx);
    } else if (nextStep instanceof Iterable) {
      addNextEntryPoints(((Iterable) nextStep).iterator(), depth, path, stack, ctx);
    } else if (nextStep instanceof OResult) {
      addNextEntryPoint(((OResult) nextStep), depth, path, stack, ctx);
    }
  }

What gets passed in here is an instance of ORecordLazyMap. This is not an instance of OIdentifiable, Iterable, or OResult. In the case of children being a LINKLIST, then the argument passed in is an ORecordLazyList, which IS an instance of Iterable. So it seems that LINKLIST the elements are iterated over and addes as entry points. The LINKMAP is just being ignored.

[mmacfadden]

I created a PR for this which may fix the issue.

[mmacfadden]

A workaround right now for my particular use case seems to be to use the values method. For both a List and a Map it will return the correct value. For the List it just returns the list. For he Map it returns the values. This extra step will degrade performance a bit, but at least is correct.

TRAVERSE children.values() FROM (SELECT FROM DataValue WHERE id = "r1");

[mmacfadden]

Actually, oddly enough.. using children.values() in the LINKLIST variety seems to skip some values, and actually adds other outgoing links that are not actually in the "children" LINKLIST.

I spent quite some time replicating this more accurately. I suspect this is a separate issue, so I will open one. In the mean time the workaround for me ultimately involved doing this:

SELECT FROM  (
  TRAVERSE children, children.values() 
  FROM (SELECT FROM DataValue WHERE id = "root")
) 
WHERE @class INSTANCEOF "DataValue";

[mmacfadden]

@luigidellaquila I think this was released in 3.0.27. I am testing that out tomorrow. If it works as expected, we can close this!

[tglman]

Hi @mmacfadden,

Could you test the last release, can we close this ?

Regards

[mmacfadden]

@tglman I will take a look in the next day or so and report back.