bitflicker64 commented on code in PR #2994:
URL: https://github.com/apache/hugegraph/pull/2994#discussion_r4090877180
##########
hugegraph-server/hugegraph-test/src/main/java/org/apache/hugegraph/core/VertexCoreTest.java:
##########
@@ -9434,6 +10019,263 @@ public void testEnhanceTextMatch() {
Assert.assertTrue(vertices.contains(vertex4));
}
+ @Test
+ public void testPositiveLabelBeforeUnsafeChildUsesLabelQuery() {
+ HugeGraph graph = graph();
+ graph.schema().propertyKey("unindexedAge").asInt().create();
+ graph.schema().vertexLabel("sourceV").properties("unindexedAge")
+ .useAutomaticId().create();
+ graph.schema().vertexLabel("targetV").useAutomaticId().create();
+ graph.schema().vertexLabel("unrelatedV").useAutomaticId().create();
+ graph.schema().vertexLabel("withoutLabelIndex").useAutomaticId()
+ .enableLabelIndex(false).create();
+ graph.schema().edgeLabel("positiveLink").link("sourceV",
"targetV").create();
+ Vertex source = graph.addVertex(T.label, "sourceV", "unindexedAge",
18);
+ Vertex target = graph.addVertex(T.label, "targetV");
+ Vertex unindexed = graph.addVertex(T.label, "withoutLabelIndex");
+ Edge edge = source.addEdge("positiveLink", target);
+ for (int i = 0; i < 5; i++) {
+ graph.addVertex(T.label, "unrelatedV");
+ }
+ this.commitTx();
+ GraphTraversalSource g = graph.traversal();
+ Id label = graph.vertexLabel("sourceV").id();
+ for (P<?> predicate : new P<?>[]{P.eq("sourceV"), P.eq(label),
P.eq(label.asLong()),
+ P.within("sourceV", "targetV"), P.within(label, "sourceV")}) {
+ GraphTraversal<Vertex, Vertex> query = g.V().has(T.label,
predicate)
+ .has("unindexedAge", 18)
+ .where(__.out().hasLabel(P.neq("sourceV")));
+ query.asAdmin().applyStrategies();
+ HugeGraphStep<?, ?> step = (HugeGraphStep<?, ?>)
query.asAdmin().getStartStep();
+ Assert.assertEquals(1, step.getHasContainers().size());
Review Comment:
Important: This assertion now fails on every server lane at this head:
`VertexCoreTest.testPositiveLabelBeforeUnsafeChildUsesLabelQuery:10050
expected:<1> but was:<2>` on build-server memory, rocksdb and hbase, both
build-server-macos-rocksdb jobs, and hstore (for example job 107493698348). I
reproduced it on the memory backend at a480537.
The cause is the change to `hasUnsafeLabelInChildTraversal()` in this head.
`where(__.out().hasLabel(P.neq("sourceV")))` no longer counts as unsafe, so
`unindexedAge` is pushed into `HugeGraphStep` next to the label. The step now
has 2 containers. After the size check, `query.toList()` on line 10052 would
not return `[source]` either. `queryByUserprop()` finds no index for
`unindexedAge` under `sourceV` and throws `NoIndexException`. That matches the
new assertions at lines 10103-10108.
Please decide which behaviour this test should pin. It could use a child
that still triggers the fallback, such as a same-element
`where(__.hasLabel(P.neq(...)))` like the change made in
`TraversalUtilOptimizeTest` line 557. Or it could assert the new plan: two
containers and `NoIndexException`. The targeted validation in the latest reply
did not include this test.
##########
hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/optimize/TraversalUtil.java:
##########
@@ -645,14 +674,542 @@ private static boolean
extractHasContainers(HugeVertexStep<?> newStep,
private static boolean canExtractHasContainers(HugeGraph graph,
HasContainerHolder holder) {
- for (HasContainer has : holder.getHasContainers()) {
+ // Keep unsafe labels and their sibling properties for local filtering.
+ if (hasUnsafeLabelPredicate(holder)) {
+ return false;
+ }
+ List<HasContainer> hasContainers = holder.getHasContainers();
+ for (HasContainer has : hasContainers) {
if (!canExtractHasContainer(graph, has)) {
return false;
}
}
return true;
}
+ private static void prepareLocalHasContainers(
+ Step<?, ?> source, Traversal.Admin<?, ?> traversal) {
+ QueryHolder query = (QueryHolder) source;
+ Step<?, ?> step = source.getNextStep();
+ while (step instanceof HasStep || step instanceof NoOpBarrierStep) {
+ Step<?, ?> next = step.getNextStep();
+ if (step instanceof HasStep) {
+ HasContainerHolder holder = (HasContainerHolder) step;
+ for (HasContainer has : new
ArrayList<>(holder.getHasContainers())) {
+ // Paging is query metadata, never an element property
filter.
+ if (QueryHolder.SYSPROP_PAGE.equals(has.getKey())) {
+ query.addHasContainer(has);
+ holder.removeHasContainer(has);
+ continue;
+ }
+ if (T.id.getAccessor().equals(has.getKey())) {
+ // ID lookup is complete across labels. Existing source
+ // IDs and unsupported predicates still filter locally.
+ if (source instanceof HugeGraphStep &&
+ GraphStep.processHasContainerIds((HugeGraphStep<?,
?>) source, has)) {
+ holder.removeHasContainer(has);
+ continue;
+ }
+ holder.removeHasContainer(has);
+ holder.addHasContainer(new
LocalIdHasContainer(has.getPredicate()));
+ continue;
+ }
+ if (T.label.getAccessor().equals(has.getKey())) {
+ holder.removeHasContainer(has);
+ HasContainer label = new
LocalLabelHasContainer(has.getPredicate());
+ if (source instanceof HugeGraphStep &&
+ canPushPositiveLabel((HugeGraphStep<?, ?>) source,
has)) {
+ // A positive label conjunct uses the label index,
+ // independent of per-label property index
coverage.
+ // Keep the runtime label matcher for source-ID
queries.
+ query.addHasContainer(label);
+ } else {
+ // Keep unsupported candidates and adjacent-vertex
+ // labels local, including their paging boundary.
+ holder.addHasContainer(label);
+ }
+ continue;
+ }
+ if (keyForContainsKey(has.getKey()) ||
keyForContainsValue(has.getKey())) {
+ // Backend CONTAINS support varies and source IDs use
+ // local filtering too. Preserve HugeGraph's map query
+ // semantics without treating "key"/"value" as names.
+ holder.removeHasContainer(has);
+ traversal.addStep(traversal.getSteps().indexOf(step),
+ new LocalContainsStep<>(traversal,
has));
+ continue;
+ }
+ List<P<Object>> predicates = new ArrayList<>();
+ collectPredicates(predicates,
ImmutableList.of(has.getPredicate()));
+ if (predicates.stream().anyMatch(p ->
+ p.getBiPredicate() ==
Condition.RelationType.TEXT_CONTAINS)) {
+ // Child traversals can be unbound during optimization;
+ // the matcher resolves the graph from each runtime
element.
+ holder.removeHasContainer(has);
+ holder.addHasContainer(new LocalSearchHasContainer(
+ has.getKey(), has.getPredicate()));
+ }
+ }
+ if (holder.getHasContainers().isEmpty()) {
+ TraversalHelper.copyLabels(step, step.getPreviousStep(),
false);
+ traversal.removeStep(step);
+ }
+ }
+ step = next;
+ }
+ if (query.queryInfo().paging() && step instanceof RangeGlobalStep) {
+ // Bound the raw backend page even when local filters prevent
normal
+ // range extraction. Keep the range step to apply offset/limit
after
+ // those filters; a filtered page may contain fewer results.
+ query.setRange(0, ((RangeGlobalStep<?>) step).getHighRange());
+ }
+ }
+
+ private static boolean canPushPositiveLabel(HugeGraphStep<?, ?> source,
+ HasContainer has) {
+ if (!isEqInLabelPredicate(has)) {
+ return false;
+ }
+ HugeGraph graph = tryGetGraph(source);
+ if (graph == null) {
+ return false;
+ }
+ List<P<Object>> predicates = new ArrayList<>();
+ collectPredicates(predicates, ImmutableList.of(has.getPredicate()));
+ for (P<Object> predicate : predicates) {
+ Object value = predicate.getValue();
+ BiPredicate<?, ?> bp = predicate.getBiPredicate();
+ if (bp == Contains.within && !(value instanceof Collection)) {
+ return false;
+ }
+ Collection<?> values = bp == Contains.within ?
+ (Collection<?>) value :
Collections.singletonList(value);
+ for (Object candidate : values) {
+ if (!hasLabelIndex(graph, source.returnsVertex(), candidate)) {
+ return false;
+ }
+ }
+ }
+ return true;
+ }
+
+ private static boolean hasLabelIndex(HugeGraph graph, boolean vertex,
Object value) {
+ if (value instanceof Number) {
+ value = IdGenerator.of(((Number) value).longValue());
+ }
+ try {
+ SchemaLabel label;
+ if (value instanceof Id) {
+ Id id = (Id) value;
+ // Nonpositive IDs include internal schema objects that aren't
+ // user labels. Preserve their local matching behavior.
+ if (!id.number() || id.asLong() <= 0L) {
+ return false;
+ }
+ label = vertex ? graph.vertexLabel(id) : graph.edgeLabel(id);
+ } else if (value instanceof String) {
+ label = vertex ? graph.vertexLabel((String) value) :
graph.edgeLabel((String) value);
+ } else {
+ return false;
+ }
+ // Do not turn a working local filter into a missing-label/index
error.
+ return label != null && label.enableLabelIndex();
+ } catch (IllegalArgumentException | NotFoundException e) {
+ return false;
+ }
+ }
+
+ private static P<?> localIdPredicate(P<?> predicate) {
+ // Keep IDs local to preserve source-ID intersections and step
ordering.
+ // UUID/Element values need the same representation as
HugeElement.id(). Leave
+ // strings unchanged so HasContainer retains its string-ID comparison.
+ P<?> copy = predicate.clone();
+ List<P<Object>> leaves = new ArrayList<>();
+ collectPredicates(leaves, ImmutableList.of(copy));
+ for (P<Object> leaf : leaves) {
+ Object value = leaf.getValue();
+ if (value instanceof Collection) {
+ List<Object> values = new ArrayList<>();
+ for (Object item : (Collection<?>) value) {
+ values.add(localIdValue(item));
+ }
+ leaf.setValue(values);
+ } else {
+ leaf.setValue(localIdValue(value));
+ }
+ }
+ return copy;
+ }
+
+ private static Object localIdValue(Object value) {
+ if (value instanceof UUID || value instanceof Element) {
+ return HugeElement.getIdValue(HugeType.VERTEX, value);
+ }
+ return value;
+ }
+
+ private static final class LocalIdHasContainer extends HasContainer {
+
+ private static final long serialVersionUID = 1L;
+
+ private LocalIdHasContainer(P<?> predicate) {
+ super(T.id.getAccessor(), localIdPredicate(predicate));
+ }
+
+ @Override
+ protected boolean testId(Element element) {
+ return testLocalIdPredicate(this.getPredicate(), element.id());
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ private static boolean testLocalIdPredicate(P<?> predicate, Object id) {
+ if (predicate instanceof ConnectiveP) {
+ boolean and = predicate instanceof AndP;
+ for (P<?> child : ((ConnectiveP<?>) predicate).getPredicates()) {
+ if (testLocalIdPredicate(child, id) != and) {
+ return !and;
+ }
+ }
+ return and;
+ }
+ Object value = predicate.getValue();
+ Object first = value;
+ if (value instanceof Collection) {
+ Collection<?> values = (Collection<?>) value;
+ first = values.isEmpty() ? null : values.iterator().next();
+ }
+ // HasContainer decides string-ID comparison from only the top-level
+ // P value. ConnectiveP has no such value; decide separately per leaf.
+ Object actual = first instanceof String ? id.toString() : id;
+ return ((BiPredicate<Object, Object>)
predicate.getBiPredicate()).test(actual, value);
+ }
+
+ private static final class LocalLabelHasContainer extends HasContainer {
+
+ private static final long serialVersionUID = 1L;
+
+ private LocalLabelHasContainer(P<?> predicate) {
+ super(T.label.getAccessor(), predicate.clone());
+ }
+
+ @Override
+ protected boolean testLabel(Element element) {
+ // Resolve against the actual element, not a graph captured while
+ // strategies run. Child traversals may be unbound or later cloned.
+ return testLabelPredicate(this.getPredicate(), ((HugeElement)
element).schemaLabel());
+ }
+ }
+
+ private static final class LocalContainsStep<S extends Element> extends
HasStep<S> {
+
+ private static final long serialVersionUID = 1L;
+
+ private LocalContainsStep(Traversal.Admin<?, ?> traversal,
HasContainer has) {
+ super(traversal, has.clone());
+ E.checkArgument(has.getPredicate().getBiPredicate() == Compare.eq,
+ "CONTAINS query with relation '%s' is not
supported",
+ has.getPredicate().getBiPredicate());
+ }
+
+ @Override
+ protected boolean filter(Traverser.Admin<S> traverser) {
+ HugeElement element = (HugeElement) traverser.get();
+ // Adjacent vertices can be ID/label-only shells. Like
properties(),
+ // load their properties before evaluating the system property map.
+ element.getFilledProperties();
+ // Keep a HasStep boundary so count/range cannot bypass this
filter.
+ // Resolve schema from the runtime element; clone/reset must not
+ // retain a graph or transaction captured during optimization.
+ for (HasContainer has : this.getHasContainers()) {
+ boolean matches = keyForContainsKey(has.getKey()) ||
keyForContainsValue(has.getKey()) ?
+ convContains2Relation(element.graph(),
has).test(element) :
+ has.test(element);
+ if (!matches) {
+ return false;
+ }
+ }
+ return true;
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ private static boolean testLabelPredicate(P<?> predicate, SchemaLabel
label) {
+ if (predicate instanceof ConnectiveP) {
+ boolean and = predicate instanceof AndP;
+ for (P<?> child : ((ConnectiveP<?>) predicate).getPredicates()) {
+ if (testLabelPredicate(child, label) != and) {
+ return !and;
+ }
+ }
+ return and;
+ }
+ BiPredicate<?, ?> bp = predicate.getBiPredicate();
+ Object value = predicate.getValue();
+ if (bp == Contains.within || bp == Contains.without) {
+ for (Object item : (Collection<?>) value) {
+ if (testLabelValue(Compare.eq, label, item)) {
+ return bp == Contains.within;
+ }
+ }
+ return bp == Contains.without;
+ }
+ return testLabelValue((BiPredicate<Object, Object>) bp, label, value);
+ }
+
+ private static boolean testLabelValue(BiPredicate<Object, Object>
predicate,
+ SchemaLabel label, Object value) {
+ if (value instanceof Number) {
+ value = IdGenerator.of(((Number) value).longValue());
+ }
+ return predicate.test(value instanceof Id ? label.id() : label.name(),
value);
+ }
+
+ private static final class LocalSearchHasContainer extends HasContainer {
+
+ private static final long serialVersionUID = 1L;
+
+ private transient HugeGraph matcherGraph;
+ private transient P<?> matcherPredicate;
+ private transient Predicate<Object> matcher;
+
+ private LocalSearchHasContainer(String key, P<?> predicate) {
+ super(key, predicate.clone());
+ }
+
+ @Override
+ protected boolean testValue(Property property) {
+ // Keep the public P tree intact for strategies, hashing and Java
+ // serialization. Resolve the analyzer from the element's graph,
+ // including after cloning, deserialization or graph rebinding.
+ HugeGraph graph = (HugeGraph) property.element().graph();
+ if (this.matcherGraph != graph ||
+ !samePredicateValues(this.getPredicate(),
this.matcherPredicate)) {
+ P<?> predicate = this.getPredicate().clone();
+ this.matcher = localSearchMatcher(predicate, graph);
+ this.matcherPredicate = predicate;
+ this.matcherGraph = graph;
+ }
+ return this.matcher.test(property.value());
+ }
+
+ @Override
+ public LocalSearchHasContainer clone() {
+ LocalSearchHasContainer clone = (LocalSearchHasContainer)
super.clone();
+ clone.matcherGraph = null;
+ clone.matcherPredicate = null;
+ clone.matcher = null;
+ return clone;
+ }
+ }
+
+ private static boolean samePredicateValues(P<?> current, P<?> cached) {
+ // P.equals() compares originalValue, not the value changed by
setValue().
+ if (cached == null || current.getClass() != cached.getClass()) {
+ return false;
+ }
+ if (current instanceof ConnectiveP) {
+ List<? extends P<?>> children = ((ConnectiveP<?>)
current).getPredicates();
+ List<? extends P<?>> oldChildren = ((ConnectiveP<?>)
cached).getPredicates();
+ if (children.size() != oldChildren.size()) {
+ return false;
+ }
+ for (int i = 0; i < children.size(); i++) {
+ if (!samePredicateValues(children.get(i), oldChildren.get(i)))
{
+ return false;
+ }
+ }
+ return true;
+ }
+ return current.getBiPredicate().equals(cached.getBiPredicate()) &&
+ Objects.equals(current.getValue(), cached.getValue());
+ }
+
+ @SuppressWarnings("unchecked")
+ private static Predicate<Object> localSearchMatcher(P<?> predicate,
HugeGraph graph) {
+ if (predicate instanceof ConnectiveP) {
+ List<Predicate<Object>> children = new ArrayList<>();
+ for (P<?> child : ((ConnectiveP<?>) predicate).getPredicates()) {
+ children.add(localSearchMatcher(child, graph));
+ }
+ boolean and = predicate instanceof AndP;
+ return value -> {
+ for (Predicate<Object> child : children) {
+ if (child.test(value) != and) {
+ return !and;
+ }
+ }
+ return and;
+ };
+ }
+ if (predicate.getBiPredicate() !=
Condition.RelationType.TEXT_CONTAINS) {
+ return (P<Object>) predicate;
+ }
+ // Match SEARCH terms in place, preserving range and side-effect
ordering.
+ return graph.searchPredicate((String) predicate.getValue());
+ }
+
+ private static boolean hasUnsafeLabelInTraversal(
+ Traversal.Admin<?, ?> traversal, Step<?, ?> sourceStep) {
+ // Partial pushdown can lose candidates before local label filtering.
+ // Scan the remaining traversal, its children and each ancestor's
+ // remaining steps for filters on child output. Arbitrary extension
+ // steps don't reliably expose element identity, so stay conservative.
+ // FIXME(#3201): Restore selective pushdown when every candidate
schema label
+ // has compatible index coverage for extracted property predicates.
+ // Outside proven root and child suffixes, negative labels can disable
+ // property pushdown even across element changes (including ancestors
+ // and unknown extension steps), potentially requiring a full scan.
+ List<Step> steps = traversal.getSteps();
+ int start = 0;
+ while (start < steps.size() && steps.get(start) != sourceStep) {
+ start++;
+ }
+ start++;
+ for (int i = start; i < steps.size(); i++) {
+ Step<?, ?> step = steps.get(i);
+ if (changesCurrentElement(step) &&
+ traversal.getParent() instanceof EmptyStep &&
+ onlyCurrentElementSuffix(steps.subList(i, steps.size()))) {
+ return false;
+ }
+ if (step instanceof HasStep) {
+ HasContainerHolder holder = (HasContainerHolder) step;
+ if (hasUnsafeLabelPredicate(holder)) {
+ return true;
+ }
+ }
+ if (hasUnsafeLabelInChildren(step)) {
+ return true;
+ }
+ }
+ TraversalParent parent = traversal.getParent();
+ if (parent instanceof Step && !(parent instanceof EmptyStep)) {
+ Step<?, ?> parentStep = (Step<?, ?>) parent;
+ // RepeatStep's until/emit siblings can filter this child's output.
+ // This helper only descends, so revisiting the owning step's
children
+ // cannot recurse back into this ancestor walk.
+ if (hasUnsafeLabelInChildren(parentStep)) {
+ return true;
+ }
+ return hasUnsafeLabelInTraversal(parentStep.getTraversal(),
parentStep);
+ }
+ return false;
+ }
+
+ private static boolean changesCurrentElement(Step<?, ?> step) {
Review Comment:
Important: `changesCurrentElement()` counts every `EdgeVertexStep` as
leaving the source, but `outE().outV()` and `inE().inV()` return to the source
vertex. The new child check in `hasUnsafeLabelInChildTraversal()` (line 1172)
and the root check in `hasUnsafeLabelInTraversal()` both depend on this helper.
As a result, a negative label on the source element can still lose matches,
which the PR description says stays conservative.
I ran a probe on the `testQueryByIndexedPropertyAndNonEqLabel` fixture (city
indexed on `person` only, plus a `fan` with city Beijing) on the memory backend
at a480537. I added one `fan -> person` edge. Results:
- `g.V().has("city","Beijing").where(__.hasLabel(P.neq("author")))` returns
the 3 persons and `unindexed-city-fan`.
-
`g.V().has("city","Beijing").where(__.outE().outV().hasLabel(P.neq("author")))`
returns `[]`. Only the fan has an out edge, and the label filter applies to the
fan itself, so the answer should be `[unindexed-city-fan]`.
- `g.V().has("city","Beijing").outE().outV().hasLabel(P.neq("author"))` also
returns `[]`.
Please count an `EdgeVertexStep` as an element change only when it moves to
the far end of the preceding edge step. For example, accept `outE().inV()` and
`inE().outV()`, but not `outE().outV()`, `inE().inV()` or `bothV()`. Please
also add these shapes to `testChildElementChangeKeepsSourceIndexPlan` on the
conservative side.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
