8000 Fixed inconsistency in BFS when using filters on vertices (#4586) · Sandychuang/arangodb@027a1e1 · GitHub
[go: up one dir, main page]
Skip to content

Commit 027a1e1

Browse files
mchackimchacki
authored
Fixed inconsistency in BFS when using filters on vertices (arangodb#4586)
1 parent 756c0da commit 027a1e1

File tree

8 files changed

+102
-24
lines changed

8 files changed

+102
-24
lines changed

‎CHANGELOG

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -322,9 +322,6 @@ v3.3.beta1 (2017-11-07)
322322
arangosh1> db.test.insert({}); // shell1 is not aware of the collection created
323323
// in shell2, so the insert will fail
324324

325-
* enable JEMalloc background thread for purging and returning unused memory
326-
back to the operating system (Linux only)
327-
328325
* incremental transfer of initial collection data now can handle partial
329326
responses for a chunk, allowing the leader/master to send smaller chunks
330327
(in terms of HTTP response size) and limit memory usage
@@ -426,6 +423,9 @@ v3.2.7 (2017-11-13)
426423
In some cases breadth first search in combination with vertex filters
427424
yields wrong result, the filter was not applied correctly.
428425

426+
* enable JEMalloc background thread for purging and returning unused memory
427+
back to the operating system (Linux only)
428+
429429
* fixed some undefined behavior in some internal value caches for AQL GatherNodes
430430
and SortNodes, which could have led to sorted results being effectively not
431431
correctly sorted.

‎arangod/Cluster/ClusterTraverser.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -65,7 +65,7 @@ void ClusterTraverser::setStartVertex(std::string const& vid) {
6565
}
6666
}
6767

68-
if (!vertexMatchesConditions(idSlice, 0)) {
68+
if (!vertexMatchesConditions(StringRef(vid), 0)) {
6969
// Start vertex invalid
7070
_done = true;
7171
return;

‎arangod/Graph/BreadthFirstEnumerator.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -142,7 +142,7 @@ bool BreadthFirstEnumerator::next() {
142142
}
143143
}
144144

145-
if (_traverser->getSingleVertex(e, nextVertex, _currentDepth, vId)) {
145+
if (_traverser->getSingleVertex(e, nextVertex, _currentDepth + 1, vId)) {
146146
_schreier.emplace_back(
147147
std::make_unique<PathStep>(nextIdx, std::move(eid), vId));
148148
if (_currentDepth < _opts->maxDepth - 1) {

‎arangod/Graph/NeighborsEnumerator.cpp

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,6 @@ bool NeighborsEnumerator::next() {
5959
// We are finished.
6060
return false;
6161
}
62-
TRI_ASSERT(!_opts->vertexHasFilter(_searchDepth));
6362

6463
_lastDepth.swap(_currentDepth);
6564
_currentDepth.clear();
@@ -94,8 +93,10 @@ bool NeighborsEnumerator::next() {
9493
}
9594

9695
if (_allFound.find(v) == _allFound.end()) {
97-
_currentDepth.emplace(v);
98-
_allFound.emplace(v);
96+
if (_traverser->vertexMatchesConditions(v, _searchDepth + 1)) {
97+
_currentDepth.emplace(v);
98+
_allFound.emplace(v);
99+
}
99100
} else {
100101
_opts->cache()->increaseFilterCounter();
101102
}

‎arangod/Graph/SingleServerTraverser.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -55,7 +55,7 @@ void SingleServerTraverser::setStartVertex(std::string const& vid) {
5555
_startIdBuilder->add(VPackValue(vid));
5656
VPackSlice idSlice = _startIdBuilder->slice();
5757

58-
if (!vertexMatchesConditions(idSlice, 0)) {
58+
if (!vertexMatchesConditions(StringRef(vid), 0)) {
5959
// Start vertex invalid
6060
_done = true;
6161
return;

‎arangod/Graph/Traverser.cpp

Lines changed: 15 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -44,10 +44,10 @@ bool Traverser::VertexGetter::getVertex(VPackSlice edge, std::vector<StringRef>&
4444
if (result.back() == StringRef(res)) {
4545
res = transaction::helpers::extractToFromDocument(edge);
4646
}
47-
TRI_ASSERT(res.isString());
4847
}
48+
TRI_ASSERT(res.isString());
4949

50-
if (!_traverser->vertexMatchesConditions(res, result.size())) {
50+
if (!_traverser->vertexMatchesConditions(StringRef(res), result.size())) {
5151
return false;
5252
}
5353
result.emplace_back(_traverser->traverserCache()->persistString(StringRef(res)));
@@ -67,7 +67,7 @@ bool Traverser::VertexGetter::getSingleVertex(arangodb::velocypack::Slice edge,
6767
TRI_ASSERT(resSlice.isString());
6868
}
6969
result = _traverser->traverserCache()->persistString(StringRef(resSlice));
70-
return _traverser->vertexMatchesConditions(resSlice, depth);
70+
return _traverser->vertexMatchesConditions(result, depth);
7171
}
7272

7373
void Traverser::VertexGetter::reset(StringRef const&) {
@@ -92,13 +92,12 @@ bool Traverser::UniqueVertexGetter::getVertex(VPackSlice edge, std::vector<Strin
9292
_traverser->traverserCache()->increaseFilterCounter();
9393
return false;
9494
} else {
95+
if (!_traverser->vertexMatchesConditions(toAddStr, result.size())) {
96+
return false;
97+
}
9598
_returnedVertices.emplace(toAddStr);
9699
}
97100

98-
if (!_traverser->vertexMatchesConditions(toAdd, result.size())) {
99-
return false;
100-
}
101-
102101
result.emplace_back(toAddStr);
103102
return true;
104103
}
@@ -120,10 +119,14 @@ bool Traverser::UniqueVertexGetter::getSingleVertex(arangodb::velocypack::Slice
120119
// This vertex is not unique.
121120
_traverser->traverserCache()->increaseFilterCounter();
122121
return false;
123-
} else {
124-
_returnedVertices.emplace(result);
125122
}
126-
return _traverser->vertexMatchesConditions(resSlice, depth);
123+
124+
if (!_traverser->vertexMatchesConditions(result, depth)) {
125+
return false;
126+
}
127+
128+
_returnedVertices.emplace(result);
129+
return true;
127130
}
128131

129132
void Traverser::UniqueVertexGetter::reset(arangodb::StringRef const& startVertex) {
@@ -159,11 +162,10 @@ bool arangodb::traverser::Traverser::edgeMatchesConditions(VPackSlice e,
159162
return true;
160163
}
161164

162-
bool arangodb::traverser::Traverser::vertexMatchesConditions(VPackSlice v, uint64_t depth) {
163-
TRI_ASSERT(v.isString());
165+
bool arangodb::traverser::Traverser::vertexMatchesConditions(StringRef v, uint64_t depth) {
164166
if (_opts->vertexHasFilter(depth)) {
165167
// We always need to destroy this vertex
166-
aql::AqlValue vertex = fetchVertexData(StringRef(v));
168+
aql::AqlValue vertex = fetchVertexData(v);
167169
if (!_opts->evaluateVertexExpression(vertex.slice(), depth)) {
168170
vertex.destroy();
169171
return false;

‎arangod/Graph/Traverser.h

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -290,7 +290,7 @@ class Traverser {
290290
bool edgeMatchesConditions(arangodb::velocypack::Slice edge, StringRef vid,
291291
uint64_t depth, size_t cursorId);
292292

293-
bool vertexMatchesConditions(arangodb::velocypack::Slice, uint64_t);
293+
bool vertexMatchesConditions(StringRef vid, uint64_t depth);
294294

295295
void allowOptimizedNeighbors();
296296

‎js/server/tests/aql/aql-graph.js

Lines changed: 76 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -629,7 +629,7 @@ function ahuacatlQueryNeighborsTestSuite () {
629629
var v6 = "UnitTestsAhuacatlVertex/v6";
630630
var v7 = "UnitTestsAhuacatlVertex/v7";
631631
var createQuery = function (start, filter) {
632-
return `WITH ${vn} FOR n, e IN OUTBOUND "${start}" UnitTestsAhuacatlEdge OPTIONS {bfs: true} ${filter} SORT n._id RETURN n._id`;
632+
return `WITH ${vn} FOR n, e IN OUTBOUND "${start}" UnitTestsAhuacatlEdge OPTIONS {bfs: true, uniqueVertices: true} ${filter} SORT n._id RETURN n._id`;
633633
};
634634

635635
// An empty filter should let all edges through
@@ -656,7 +656,82 @@ function ahuacatlQueryNeighborsTestSuite () {
656656
// Should be able to handle internal attributes
657657
actual = getQueryResults(createQuery(v3, `FILTER e._to == "${v4}"`));
658658
assertEqual(actual, [ v4 ]);
659+
},
660+
661+
testNeighborsWithVertexFilters : function () {
662+
let actual;
663+
const v1 = "UnitTestsAhuacatlVertex/v1";
664+
var v3 = "UnitTestsAhuacatlVertex/v3";
665+
var v4 = "UnitTestsAhuacatlVertex/v4";
< F987 /td>
666+
var v6 = "UnitTestsAhuacatlVertex/v6";
667+
var v7 = "UnitTestsAhuacatlVertex/v7";
668+
var createQuery = function (start, filter) {
669+
return `WITH ${vn} FOR n, e, p IN 2 OUTBOUND "${start}" UnitTestsAhuacatlEdge OPTIONS {bfs: true, uniqueVertices: 'global'} ${filter} SORT n._id RETURN n._id`;
670+
};
671+
672+
// It should filter on the start vertex
673+
actual = getQueryResults(createQuery(v1, "FILTER p.vertices[0].name == 'v1'"));
674+
assertEqual(actual, [v4, v6, v7]);
675+
676+
actual = getQueryResults(createQuery(v1, "FILTER p.vertices[0].name != 'v1'"));
677+
assertEqual(actual, []);
678+
679+
// It should filter on the first vertex
680+
actual = getQueryResults(createQuery(v1, "FILTER p.vertices[1].name == 'v3'"));
681+
assertEqual(actual, [v4, v6, v7]);
682+
683+
actual = getQueryResults(createQuery(v1, "FILTER p.vertices[1].name != 'v3'"));
684+
assertEqual(actual, [v3]);
685+
686+
// It should filter on the second vertex
687+
actual = getQueryResults(createQuery(v1, "FILTER p.vertices[2].name == 'v4'"));
688+
assertEqual(actual, [v4]);
689+
690+
actual = getQueryResults(createQuery(v1, "FILTER p.vertices[2].name != 'v4'"));
691+
assertEqual(actual, [v6, v7]);
692+
693+
// It should filter on all vertices
694+
actual = getQueryResults(createQuery(v1, "FILTER p.vertices[*].name ALL IN ['v1', 'v3', 'v4', 'v6']"));
695+
assertEqual(actual, [v4, v6]);
696+
},
697+
698+
testNonUniqueBFSWithVertexFilters : function () {
699+
let actual;
700+
const v1 = "UnitTestsAhuacatlVertex/v1";
701+
var v3 = "UnitTestsAhuacatlVertex/v3";
702+
var v4 = "UnitTestsAhuacatlVertex/v4";
703+
var v6 = "UnitTestsAhuacatlVertex/v6";
704+
var v7 = "UnitTestsAhuacatlVertex/v7";
705+
var createQuery = function (start, filter) {
706+
return `WITH ${vn} FOR n, e, p IN 2 OUTBOUND "${start}" UnitTestsAhuacatlEdge OPTIONS {bfs: true} ${filter} SORT n._id RETURN n._id`;
707+
};
708+
709+
// It should filter on the start vertex
710+
actual = getQueryResults(createQuery(v1, "FILTER p.vertices[0].name == 'v1'"));
711+
assertEqual(actual, [v3, v4, v6, v7]);
712+
713+
actual = getQueryResults(createQuery(v1, "FILTER p.vertices[0].name != 'v1'"));
714+
assertEqual(actual, []);
715+
716+
// It should filter on the first vertex
717+
actual = getQueryResults(createQuery(v1, "FILTER p.vertices[1].name == 'v3'"));
718+
assertEqual(actual, [v4, v6, v7]);
719+
720+
actual = getQueryResults(createQuery(v1, "FILTER p.vertices[1].name != 'v3'"));
721+
assertEqual(actual, [v3]);
722+
723+
// It should filter on the second vertex
724+
actual = getQueryResults(createQuery(v1, "FILTER p.vertices[2].name == 'v4'"));
725+
assertEqual(actual, [v4]);
726+
727+
actual = getQueryResults(createQuery(v1, "FILTER p.vertices[2].name != 'v4'"));
728+
assertEqual(actual, [v3, v6, v7]);
729+
730+
// It should filter on all vertices
731+
actual = getQueryResults(createQuery(v1, "FILTER p.vertices[*].name ALL IN ['v1', 'v3', 'v4', 'v6']"));
732+
assertEqual(actual, [v4, v6]);
659733
}
734+
660735
};
661736
}
662737

0 commit comments

Comments
 (0)
0