You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by "upadhyay-prashant (via GitHub)" <gi...@apache.org> on 2026/10/13 21:14:05 UTC
[PR] Fix CountStrategy returning capped counts when the count is observed [tinkerpop]
upadhyay-prashant opened a new pull request, #3717:
URL: https://github.com/apache/tinkerpop/pull/3717
## Summary
`CountStrategy` rewrites `count().is(P)` to `limit(n).count().is(P)`. When `P` accepts `n`, the capped value is emitted in place of the real count, so anything that observes it gets a wrong result:
- `g.V().where(outE().count().is(gt(1)).is(lt(3)))` keeps vertices with more than 2 edges
- `g.V().outE().count().is(gt(2))` returns `3` instead of `6`
- `g.V().map(outE().count().is(gt(1)))` returns `2` instead of `3`
The limit is now only added when:
1. `P` rejects the cap (e.g. `lt`, `lte`, `within`), so any count that passes is exact; or
2. the count is used purely as a filter (`where`/`filter`, `not`, `and`/`or`, `sideEffect`, `repeat().until()/emit()`) with no following step and no labels.
Otherwise the traversal is left unchanged. The existing `not()` / filter-removal rewrites are untouched.
## Testing
- `CountStrategyTest`: added 20 cases covering shapes that must not be limited and shapes that must stay optimized; updated 5 expectations that encoded the incorrect rewrite. 428 tests pass.
- `CountStrategy.feature`: added 4 scenarios. 3 failed before the fix and all pass after.
- TinkerGraph feature suites (`TinkerMemoryGraphFeatureTest`, `TinkerMemoryGraphComputerFeatureTest`, `TinkerShuffleGraphFeatureTest`): 5,742 tests, 0 failures.
- Regenerated `translations.json` and the Go/Python/.NET/JS translation files (additions only). GLV feature tests were not run locally.
## Notes
- Root-level and value-consuming usages such as `count().is(gt(n))` no longer get the early `limit()`. That is required for correctness.
- This bug likely also exists on `3.7-dev`/`3.8-dev`; this PR targets `master`.
--
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: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CountStrategy returning capped counts when the count is observed [tinkerpop]
Posted by "Cole-Greer (via GitHub)" <gi...@apache.org>.
Cole-Greer commented on code in PR #3717:
URL: https://github.com/apache/tinkerpop/pull/3717#discussion_r4331671550
##########
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java:
##########
@@ -84,15 +88,59 @@ public static Iterable<Object[]> generateTestParameters() {
{__.filter(__.out().out().count().is(0)), __.not(__.out().out())},
{__.local(aggregate("x")).count().is(0).as("a"), __.local(aggregate("x")).limit(1).count().is(0).as("a")},
{__.out().count().as("a").is(0), __.out().limit(1).count().as("a").is(0)},
- {__.out().count().is(neq(4)), __.out().limit(5).count().is(neq(4))},
+ {__.out().count().is(neq(4)), __.out().count().is(neq(4))}, // root: the count value is returned
+ {__.where(__.out().count().is(neq(4))), __.where(__.out().limit(5).count().is(neq(4)))},
+ {__.out().where(__.count().is(neq(4))), __.out().where(__.limit(5).count().is(neq(4)))},
{__.out().count().is(lte(3)), __.out().limit(4).count().is(lte(3))},
{__.out().count().is(lt(3)), __.out().limit(3).count().is(lt(3))},
- {__.out().count().is(gt(2)), __.out().limit(3).count().is(gt(2))},
- {__.out().count().is(gte(2)), __.out().limit(2).count().is(gte(2))},
+ {__.out().count().is(gt(2)), __.out().count().is(gt(2))}, // root: the count value is returned
+ {__.filter(__.out().count().is(gt(2))), __.filter(__.out().limit(3).count().is(gt(2)))},
+ {__.out().count().is(gte(2)), __.out().count().is(gte(2))}, // root: the count value is returned
+ {__.filter(__.out().count().is(gte(2))), __.filter(__.out().limit(2).count().is(gte(2)))},
{__.out().count().is(inside(2, 4)), __.out().limit(4).count().is(inside(2, 4))},
- {__.out().count().is(outside(2, 4)), __.out().limit(5).count().is(outside(2, 4))},
+ {__.out().count().is(outside(2, 4)), __.out().count().is(outside(2, 4))}, // root: the count value is returned
+ {__.where(__.out().count().is(outside(2, 4))), __.where(__.out().limit(5).count().is(outside(2, 4)))},
{__.out().count().is(within(2, 6, 4)), __.out().limit(7).count().is(within(2, 6, 4))},
{__.out().count().is(without(2, 6, 4)), __.out().limit(6).count().is(without(2, 6, 4))},
+ // a capped count that passes is() must not be observed by later steps or the parent
+ {__.where(__.out().count().is(gt(1)).is(lt(3))), __.where(__.out().count().is(gt(1)).is(lt(3)))},
+ {__.where(__.out().count().is(gte(2)).is(lte(2))), __.where(__.out().count().is(gte(2)).is(lte(2)))},
+ {__.filter(__.out().count().is(neq(1)).is(lt(5))), __.filter(__.out().count().is(neq(1)).is(lt(5)))},
Review Comment:
I think theoretically these cases could be optimized as
```suggestion
{__.where(__.out().count().is(gt(1)).is(lt(3))), __.where(__.out().count().limit(3).is(gt(1)).is(lt(3)))},
{__.where(__.out().count().is(gte(2)).is(lte(2))), __.where(__.out().count().limit(3).is(gte(2)).is(lte(2)))},
{__.filter(__.out().count().is(neq(1)).is(lt(5))), __.filter(__.out().count().limit(5).is(neq(1)).is(lt(5)))},
```
I think the strategy is only looking at the `count().is(gt/gte/neq).<some other step>` pattern, which misses the context that the full chain of `is()` steps are all collectively constraining the `count()` in a way which could be optimized. It's probably ok if we limit the scope of the strategy to the singular `count().is()` pattern, although I don't think these cases are necessarily warranted as they could be optimized further.
--
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: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CountStrategy returning capped counts when the count is observed [tinkerpop]
Posted by "Cole-Greer (via GitHub)" <gi...@apache.org>.
Cole-Greer commented on code in PR #3717:
URL: https://github.com/apache/tinkerpop/pull/3717#discussion_r4276111902
##########
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java:
##########
@@ -71,7 +71,7 @@ public static Iterable<Object[]> generateTestParameters() {
{__.count().is(-2023), __.limit(0).count().is(-2023)},
{__.count().is(P.between(0, 10)), __.limit(10).count().is(P.between(0, 10))},
{__.count().is(P.between(5, 10)), __.limit(10).count().is(P.between(5, 10))},
- {__.count().is(P.gt(10).or(lt(5))), __.limit(11).count().is(P.gt(10).or(lt(5)))},
+ {__.count().is(P.gt(10).or(lt(5))), __.count().is(P.gt(10).or(lt(5)))}, // capped count of 11 would pass and be returned
Review Comment:
I find it surprising that the changes result in this case dropping the `limit()`, but the limit is retained in all of the above cases:
```
{__.count().is(-2023), __.limit(0).count().is(-2023)},
{__.count().is(P.between(0, 10)), __.limit(10).count().is(P.between(0, 10))},
{__.count().is(P.between(5, 10)), __.limit(10).count().is(P.between(5, 10))},
```
My expectation would be that the limit no longer gets added in all of these basic `count().is(...)` cases.
--
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: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CountStrategy returning capped counts when the count is observed [tinkerpop]
Posted by "Cole-Greer (via GitHub)" <gi...@apache.org>.
Cole-Greer commented on code in PR #3717:
URL: https://github.com/apache/tinkerpop/pull/3717#discussion_r4331671550
##########
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java:
##########
@@ -84,15 +88,59 @@ public static Iterable<Object[]> generateTestParameters() {
{__.filter(__.out().out().count().is(0)), __.not(__.out().out())},
{__.local(aggregate("x")).count().is(0).as("a"), __.local(aggregate("x")).limit(1).count().is(0).as("a")},
{__.out().count().as("a").is(0), __.out().limit(1).count().as("a").is(0)},
- {__.out().count().is(neq(4)), __.out().limit(5).count().is(neq(4))},
+ {__.out().count().is(neq(4)), __.out().count().is(neq(4))}, // root: the count value is returned
+ {__.where(__.out().count().is(neq(4))), __.where(__.out().limit(5).count().is(neq(4)))},
+ {__.out().where(__.count().is(neq(4))), __.out().where(__.limit(5).count().is(neq(4)))},
{__.out().count().is(lte(3)), __.out().limit(4).count().is(lte(3))},
{__.out().count().is(lt(3)), __.out().limit(3).count().is(lt(3))},
- {__.out().count().is(gt(2)), __.out().limit(3).count().is(gt(2))},
- {__.out().count().is(gte(2)), __.out().limit(2).count().is(gte(2))},
+ {__.out().count().is(gt(2)), __.out().count().is(gt(2))}, // root: the count value is returned
+ {__.filter(__.out().count().is(gt(2))), __.filter(__.out().limit(3).count().is(gt(2)))},
+ {__.out().count().is(gte(2)), __.out().count().is(gte(2))}, // root: the count value is returned
+ {__.filter(__.out().count().is(gte(2))), __.filter(__.out().limit(2).count().is(gte(2)))},
{__.out().count().is(inside(2, 4)), __.out().limit(4).count().is(inside(2, 4))},
- {__.out().count().is(outside(2, 4)), __.out().limit(5).count().is(outside(2, 4))},
+ {__.out().count().is(outside(2, 4)), __.out().count().is(outside(2, 4))}, // root: the count value is returned
+ {__.where(__.out().count().is(outside(2, 4))), __.where(__.out().limit(5).count().is(outside(2, 4)))},
{__.out().count().is(within(2, 6, 4)), __.out().limit(7).count().is(within(2, 6, 4))},
{__.out().count().is(without(2, 6, 4)), __.out().limit(6).count().is(without(2, 6, 4))},
+ // a capped count that passes is() must not be observed by later steps or the parent
+ {__.where(__.out().count().is(gt(1)).is(lt(3))), __.where(__.out().count().is(gt(1)).is(lt(3)))},
+ {__.where(__.out().count().is(gte(2)).is(lte(2))), __.where(__.out().count().is(gte(2)).is(lte(2)))},
+ {__.filter(__.out().count().is(neq(1)).is(lt(5))), __.filter(__.out().count().is(neq(1)).is(lt(5)))},
Review Comment:
I think theoretically these cases could be optimized as
```suggestion
{__.where(__.out().count().is(gt(1)).is(lt(3))), __.where(__.out().limit(3).count().is(gt(1)).is(lt(3)))},
{__.where(__.out().count().is(gte(2)).is(lte(2))), __.where(__.out().limit(3).count().is(gte(2)).is(lte(2)))},
{__.filter(__.out().count().is(neq(1)).is(lt(5))), __.filter(__.out().limit(5).count().is(neq(1)).is(lt(5)))},
```
I think the strategy is only looking at the `count().is(gt/gte/neq).<some other step>` pattern, which misses the context that the full chain of `is()` steps are all collectively constraining the `count()` in a way which could be optimized. It's probably ok if we limit the scope of the strategy to the singular `count().is()` pattern, although I don't think these cases are necessarily warranted as they could be optimized further.
--
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: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CountStrategy returning capped counts when the count is observed [tinkerpop]
Posted by "Cole-Greer (via GitHub)" <gi...@apache.org>.
Cole-Greer commented on PR #3717:
URL: https://github.com/apache/tinkerpop/pull/3717#issuecomment-6324135330
Thanks @upadhyay-prashant, the updates look good to me.
That `MatchTest`/`HadoopGraphProcessStandardTest` does sound like a problem, I'd like to take some time to think about it. I don't think it should block this PR though, it should be addressed independently. That old form of `match()` is deprecated in master, and HadoopGremlin is slated for removal following [a recent devlist post](https://lists.apache.org/thread.html/96gshjnssd8llqhyqyn14qvxy03cysv4). For these reasons dropping the test might be the easiest solution.
VOTE +1
--
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: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CountStrategy returning capped counts when the count is observed [tinkerpop]
Posted by "upadhyay-prashant (via GitHub)" <gi...@apache.org>.
upadhyay-prashant commented on code in PR #3717:
URL: https://github.com/apache/tinkerpop/pull/3717#discussion_r4340381869
##########
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java:
##########
@@ -84,15 +88,59 @@ public static Iterable<Object[]> generateTestParameters() {
{__.filter(__.out().out().count().is(0)), __.not(__.out().out())},
{__.local(aggregate("x")).count().is(0).as("a"), __.local(aggregate("x")).limit(1).count().is(0).as("a")},
{__.out().count().as("a").is(0), __.out().limit(1).count().as("a").is(0)},
- {__.out().count().is(neq(4)), __.out().limit(5).count().is(neq(4))},
+ {__.out().count().is(neq(4)), __.out().count().is(neq(4))}, // root: the count value is returned
+ {__.where(__.out().count().is(neq(4))), __.where(__.out().limit(5).count().is(neq(4)))},
+ {__.out().where(__.count().is(neq(4))), __.out().where(__.limit(5).count().is(neq(4)))},
{__.out().count().is(lte(3)), __.out().limit(4).count().is(lte(3))},
{__.out().count().is(lt(3)), __.out().limit(3).count().is(lt(3))},
- {__.out().count().is(gt(2)), __.out().limit(3).count().is(gt(2))},
- {__.out().count().is(gte(2)), __.out().limit(2).count().is(gte(2))},
+ {__.out().count().is(gt(2)), __.out().count().is(gt(2))}, // root: the count value is returned
+ {__.filter(__.out().count().is(gt(2))), __.filter(__.out().limit(3).count().is(gt(2)))},
+ {__.out().count().is(gte(2)), __.out().count().is(gte(2))}, // root: the count value is returned
+ {__.filter(__.out().count().is(gte(2))), __.filter(__.out().limit(2).count().is(gte(2)))},
{__.out().count().is(inside(2, 4)), __.out().limit(4).count().is(inside(2, 4))},
- {__.out().count().is(outside(2, 4)), __.out().limit(5).count().is(outside(2, 4))},
+ {__.out().count().is(outside(2, 4)), __.out().count().is(outside(2, 4))}, // root: the count value is returned
+ {__.where(__.out().count().is(outside(2, 4))), __.where(__.out().limit(5).count().is(outside(2, 4)))},
{__.out().count().is(within(2, 6, 4)), __.out().limit(7).count().is(within(2, 6, 4))},
{__.out().count().is(without(2, 6, 4)), __.out().limit(6).count().is(without(2, 6, 4))},
+ // a capped count that passes is() must not be observed by later steps or the parent
+ {__.where(__.out().count().is(gt(1)).is(lt(3))), __.where(__.out().count().is(gt(1)).is(lt(3)))},
+ {__.where(__.out().count().is(gte(2)).is(lte(2))), __.where(__.out().count().is(gte(2)).is(lte(2)))},
+ {__.filter(__.out().count().is(neq(1)).is(lt(5))), __.filter(__.out().count().is(neq(1)).is(lt(5)))},
Review Comment:
Good call, implemented. For a chain of `is()` steps the limit is now the largest limit needed by any predicate in the chain. Each predicate gives the same result for every count at or above its own limit, so with that cap the capped count passes the whole chain exactly when the real count does. The limit is then added if the chain rejects the cap (any count that passes is exact, so this works at the root too), or if the count is only used as a filter. Your three cases now get `limit(3)`, `limit(3)` and `limit(5)`. There are also tests for chains that accept the cap (`where(...is(gt(1)).is(neq(2)))` gets `limit(3)`, but the root form is left alone) and for a traversal-valued predicate later in the chain, which disables it.
Working through this turned up two existing off-by-one limits, both fixed here with unit tests and feature scenarios:
- `without()` needs max + 1, not max. `without(2, 6, 4)` used `limit(6)`, so a real count of 7 was capped to 6 and rejected.
- `not(lte(n))` is `gt(n)` and needs n + 1. It used `limit(n)`, which rejected every count.
##########
CHANGELOG.asciidoc:
##########
@@ -29,6 +29,7 @@ image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima
* Fixed `gremlin-go` to report a malformed or truncated GraphBinary response as a deserialization error rather than a bare decoder message.
* Made `TinkerGraph` an interface and renamed the in-memory implementation to `TinkerMemoryGraph`; `TinkerGraph.open()` and `gremlin.graph=...TinkerGraph` behave as before. *(breaking)*
* Renamed `TinkerTransactionGraph` to `TinkerStorageGraph`. *(breaking)*
+* Fixed `CountStrategy` so that it no longer adds a `limit()` before `count().is(P)` when the capped count can pass the predicate and is then observed downstream, e.g. `where(out().count().is(gt(1)).is(lt(3)))` or `out().count().is(gt(2))`, or when `P` contains a traversal, e.g. `is(gt(1).and(lt(__.constant(3))))`.
Review Comment:
Done, I used your wording.
--
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: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CountStrategy returning capped counts when the count is observed [tinkerpop]
Posted by "Cole-Greer (via GitHub)" <gi...@apache.org>.
Cole-Greer merged PR #3717:
URL: https://github.com/apache/tinkerpop/pull/3717
--
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: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CountStrategy returning capped counts when the count is observed [tinkerpop]
Posted by "Cole-Greer (via GitHub)" <gi...@apache.org>.
Cole-Greer commented on PR #3717:
URL: https://github.com/apache/tinkerpop/pull/3717#issuecomment-6304982812
Thanks for all the updated @upadhyay-prashant. It looks great.
I've just got the one comment where I think we could optimize further by inspecting chains of `is()` steps, although I'm not sure that case really warrants the added complexity of the strategy. I'll defer to you whether you wish to implement that case.
VOTE +1
--
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: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CountStrategy returning capped counts when the count is observed [tinkerpop]
Posted by "upadhyay-prashant (via GitHub)" <gi...@apache.org>.
upadhyay-prashant commented on code in PR #3717:
URL: https://github.com/apache/tinkerpop/pull/3717#discussion_r4290151978
##########
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java:
##########
@@ -71,7 +71,7 @@ public static Iterable<Object[]> generateTestParameters() {
{__.count().is(-2023), __.limit(0).count().is(-2023)},
{__.count().is(P.between(0, 10)), __.limit(10).count().is(P.between(0, 10))},
{__.count().is(P.between(5, 10)), __.limit(10).count().is(P.between(5, 10))},
- {__.count().is(P.gt(10).or(lt(5))), __.limit(11).count().is(P.gt(10).or(lt(5)))},
+ {__.count().is(P.gt(10).or(lt(5))), __.count().is(P.gt(10).or(lt(5)))}, // capped count of 11 would pass and be returned
Review Comment:
The difference is whether the capped count can pass the predicate. If it can't, any count that does pass is below the cap and therefore exact, so the limit is harmless even at the root:
- `is(-2023)`: `limit(0)` gives a count of 0, which fails the predicate (and a count can never be negative anyway).
- `between(0, 10)` / `between(5, 10)`: the upper bound is exclusive, so the cap of 10 fails.
- `gt(10).or(lt(5))`: the cap of 11 passes `gt(10)`, so a traversal of 20 elements would return 11. That's the case the PR fixes.
Dropping the limit for every root-level case would be simpler, but it would throw away optimizations that are always safe. I've added a comment above these cases in the test to explain this.
##########
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java:
##########
@@ -84,15 +84,46 @@ public static Iterable<Object[]> generateTestParameters() {
{__.filter(__.out().out().count().is(0)), __.not(__.out().out())},
{__.local(aggregate("x")).count().is(0).as("a"), __.local(aggregate("x")).limit(1).count().is(0).as("a")},
{__.out().count().as("a").is(0), __.out().limit(1).count().as("a").is(0)},
- {__.out().count().is(neq(4)), __.out().limit(5).count().is(neq(4))},
Review Comment:
Agreed, and done. Every case whose expectation changed now has a counterpart that is still limited:
- `out().count().is(neq(4))` -> `where(out().count().is(neq(4)))` and your `out().where(count().is(neq(4)))`, both `limit(5)`
- `is(gt(2))` -> `filter(out().count().is(gt(2)))`, `limit(3)`
- `is(gte(2))` -> `filter(out().count().is(gte(2)))`, `limit(2)`
- `is(outside(2, 4))` -> `where(out().count().is(outside(2, 4)))`, `limit(5)`
- `is(gt(10).or(lt(5)))` -> `where(count().is(gt(10).or(lt(5))))`, `limit(11)`
- `LazyBarrierStrategyTest` root `is(gt(10))` -> a `where()` version that keeps `limit(11)`
##########
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java:
##########
@@ -84,15 +84,46 @@ public static Iterable<Object[]> generateTestParameters() {
{__.filter(__.out().out().count().is(0)), __.not(__.out().out())},
{__.local(aggregate("x")).count().is(0).as("a"), __.local(aggregate("x")).limit(1).count().is(0).as("a")},
{__.out().count().as("a").is(0), __.out().limit(1).count().as("a").is(0)},
- {__.out().count().is(neq(4)), __.out().limit(5).count().is(neq(4))},
+ {__.out().count().is(neq(4)), __.out().count().is(neq(4))}, // root: the count value is returned
{__.out().count().is(lte(3)), __.out().limit(4).count().is(lte(3))},
{__.out().count().is(lt(3)), __.out().limit(3).count().is(lt(3))},
- {__.out().count().is(gt(2)), __.out().limit(3).count().is(gt(2))},
- {__.out().count().is(gte(2)), __.out().limit(2).count().is(gte(2))},
+ {__.out().count().is(gt(2)), __.out().count().is(gt(2))}, // root: the count value is returned
+ {__.out().count().is(gte(2)), __.out().count().is(gte(2))}, // root: the count value is returned
{__.out().count().is(inside(2, 4)), __.out().limit(4).count().is(inside(2, 4))},
- {__.out().count().is(outside(2, 4)), __.out().limit(5).count().is(outside(2, 4))},
+ {__.out().count().is(outside(2, 4)), __.out().count().is(outside(2, 4))}, // root: the count value is returned
{__.out().count().is(within(2, 6, 4)), __.out().limit(7).count().is(within(2, 6, 4))},
{__.out().count().is(without(2, 6, 4)), __.out().limit(6).count().is(without(2, 6, 4))},
+ // a capped count that passes is() must not be observed by later steps or the parent
+ {__.where(__.out().count().is(gt(1)).is(lt(3))), __.where(__.out().count().is(gt(1)).is(lt(3)))},
+ {__.where(__.out().count().is(gte(2)).is(lte(2))), __.where(__.out().count().is(gte(2)).is(lte(2)))},
+ {__.filter(__.out().count().is(neq(1)).is(lt(5))), __.filter(__.out().count().is(neq(1)).is(lt(5)))},
+ {__.where(__.out().count().is(gt(1)).as("a")), __.where(__.out().count().is(gt(1)).as("a"))},
+ {__.where(__.out().count().as("a").is(gt(1))), __.where(__.out().count().as("a").is(gt(1)))},
Review Comment:
You're right. Treating labels as "observed" was overly conservative, and I've removed that check. In a filter-only child, labels can't be read from outside it, so `where(out().count().as("a").is(gt(1)))` and both `filter(...)` label cases now get the limit.
The one exception is a label at the end of the `where()` child, e.g. `where(out().count().is(gt(1)).as("a"))`. That makes `where()` build a `WhereTraversalStep`, which appends a `WhereEndStep` that compares the count to the path value `"a"`, so the capped value would be observed. That case is still caught by the existing "a step follows `is()`" check, so no label-specific logic is needed.
The cases that still must not be limited inside `where()`/`filter()` are the ones with a following `is()`, e.g. `where(out().count().is(gt(1)).is(lt(3)))`. The second `is()` sees the capped value. The new `CountStrategy.feature` scenarios show the wrong results this caused on the modern graph.
Looking at where a label could actually be read from also turned up one more case: the `is()` predicate itself can hold a traversal (`P.gt(__.constant(29))`), and that traversal runs inside the child. For example, `filter(outE().count().is(gt(1).and(lt(__.constant(3)))))` returned marko as well as josh, and `outE().count().as("a").is(gt(1).and(lte(__.select("a"))))` returned 2 instead of 6. The strategy only sees the literal part of the predicate, so it can't derive a safe limit. `CountStrategy` now leaves `count().is(P)` alone whenever `P` contains a traversal. This was already broken before this PR, but it's the same class of bug, so I've included the fix and two feature scenarios for it here. A narrower rule (keep the limit when an `and()` has a literal part that rejects the cap) would be possible as a follow-up, but it needs careful handling of `and`/`or`/`not` with unknown values, so I kept it simple here.
--
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: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CountStrategy returning capped counts when the count is observed [tinkerpop]
Posted by "Cole-Greer (via GitHub)" <gi...@apache.org>.
Cole-Greer commented on code in PR #3717:
URL: https://github.com/apache/tinkerpop/pull/3717#discussion_r4331671550
##########
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java:
##########
@@ -84,15 +88,59 @@ public static Iterable<Object[]> generateTestParameters() {
{__.filter(__.out().out().count().is(0)), __.not(__.out().out())},
{__.local(aggregate("x")).count().is(0).as("a"), __.local(aggregate("x")).limit(1).count().is(0).as("a")},
{__.out().count().as("a").is(0), __.out().limit(1).count().as("a").is(0)},
- {__.out().count().is(neq(4)), __.out().limit(5).count().is(neq(4))},
+ {__.out().count().is(neq(4)), __.out().count().is(neq(4))}, // root: the count value is returned
+ {__.where(__.out().count().is(neq(4))), __.where(__.out().limit(5).count().is(neq(4)))},
+ {__.out().where(__.count().is(neq(4))), __.out().where(__.limit(5).count().is(neq(4)))},
{__.out().count().is(lte(3)), __.out().limit(4).count().is(lte(3))},
{__.out().count().is(lt(3)), __.out().limit(3).count().is(lt(3))},
- {__.out().count().is(gt(2)), __.out().limit(3).count().is(gt(2))},
- {__.out().count().is(gte(2)), __.out().limit(2).count().is(gte(2))},
+ {__.out().count().is(gt(2)), __.out().count().is(gt(2))}, // root: the count value is returned
+ {__.filter(__.out().count().is(gt(2))), __.filter(__.out().limit(3).count().is(gt(2)))},
+ {__.out().count().is(gte(2)), __.out().count().is(gte(2))}, // root: the count value is returned
+ {__.filter(__.out().count().is(gte(2))), __.filter(__.out().limit(2).count().is(gte(2)))},
{__.out().count().is(inside(2, 4)), __.out().limit(4).count().is(inside(2, 4))},
- {__.out().count().is(outside(2, 4)), __.out().limit(5).count().is(outside(2, 4))},
+ {__.out().count().is(outside(2, 4)), __.out().count().is(outside(2, 4))}, // root: the count value is returned
+ {__.where(__.out().count().is(outside(2, 4))), __.where(__.out().limit(5).count().is(outside(2, 4)))},
{__.out().count().is(within(2, 6, 4)), __.out().limit(7).count().is(within(2, 6, 4))},
{__.out().count().is(without(2, 6, 4)), __.out().limit(6).count().is(without(2, 6, 4))},
+ // a capped count that passes is() must not be observed by later steps or the parent
+ {__.where(__.out().count().is(gt(1)).is(lt(3))), __.where(__.out().count().is(gt(1)).is(lt(3)))},
+ {__.where(__.out().count().is(gte(2)).is(lte(2))), __.where(__.out().count().is(gte(2)).is(lte(2)))},
+ {__.filter(__.out().count().is(neq(1)).is(lt(5))), __.filter(__.out().count().is(neq(1)).is(lt(5)))},
Review Comment:
I think theoretically these cases could be optimized as
```suggestion
{__.where(__.out().count().is(gt(1)).is(lt(3))), __.where(__.out().limit(3).count().is(gt(1)).is(lt(3)))},
{__.where(__.out().count().is(gte(2)).is(lte(2))), __.where(__.out().limit(3).count().is(gte(2)).is(lte(2)))},
{__.filter(__.out().count().is(neq(1)).is(lt(5))), __.filter(__.out().limit(5).count().is(neq(1)).is(lt(5)))},
```
I think the strategy is only looking at the `count().is(gt/gte/neq).<some other step>` pattern, which misses the context that the full chain of `is()` steps are all collectively constraining the `count()` in a way which could be optimized (the subsequent `lt` filter drops anything which would've exceeded the `limit()`). It's probably ok if we limit the scope of the strategy to the singular `count().is()` pattern, although I don't think these cases are necessarily warranted as they could be optimized further.
--
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: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CountStrategy returning capped counts when the count is observed [tinkerpop]
Posted by "upadhyay-prashant (via GitHub)" <gi...@apache.org>.
upadhyay-prashant commented on PR #3717:
URL: https://github.com/apache/tinkerpop/pull/3717#issuecomment-6323318889
Thanks @Cole-Greer! I pushed a new revision, rebased on `master`, with the `is()` chain optimization, the changelog nit, and two off-by-one limit fixes (`without()` and `not(lte())`). Details are in the review threads.
One thing to flag: with the limit removed from `match(as("a").out("followedBy").count().is(gt(10)).as("b"), ...)` in `MatchTest`, `HadoopGraphProcessStandardTest` gets much slower in a full local build. `GreedyMatchTraversals` now counts every `followedBy` edge on the Grateful Dead graph, and `hadoop-gremlin` took several hours for me. Removing the limit is correct there: `b` is joined on the count, and the old cap made vertices with different counts above 10 match each other. But the test may want a smaller graph or a different predicate. I'm happy to look at that here or in a follow-up, whichever you prefer.
Local validation used `mvn clean install -DskipIntegrationTests=false` with all GLVs enabled. Two things couldn't run locally, and both pass in CI: `GremlinServerConfigIntegrateTest` (port 8182 is held by another service on my machine) and the Go integration tests (the test container couldn't reach `proxy.golang.org`).
--
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: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CountStrategy returning capped counts when the count is observed [tinkerpop]
Posted by "Cole-Greer (via GitHub)" <gi...@apache.org>.
Cole-Greer commented on code in PR #3717:
URL: https://github.com/apache/tinkerpop/pull/3717#discussion_r4276178680
##########
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java:
##########
@@ -84,15 +84,46 @@ public static Iterable<Object[]> generateTestParameters() {
{__.filter(__.out().out().count().is(0)), __.not(__.out().out())},
{__.local(aggregate("x")).count().is(0).as("a"), __.local(aggregate("x")).limit(1).count().is(0).as("a")},
{__.out().count().as("a").is(0), __.out().limit(1).count().as("a").is(0)},
- {__.out().count().is(neq(4)), __.out().limit(5).count().is(neq(4))},
+ {__.out().count().is(neq(4)), __.out().count().is(neq(4))}, // root: the count value is returned
{__.out().count().is(lte(3)), __.out().limit(4).count().is(lte(3))},
{__.out().count().is(lt(3)), __.out().limit(3).count().is(lt(3))},
- {__.out().count().is(gt(2)), __.out().limit(3).count().is(gt(2))},
- {__.out().count().is(gte(2)), __.out().limit(2).count().is(gte(2))},
+ {__.out().count().is(gt(2)), __.out().count().is(gt(2))}, // root: the count value is returned
+ {__.out().count().is(gte(2)), __.out().count().is(gte(2))}, // root: the count value is returned
{__.out().count().is(inside(2, 4)), __.out().limit(4).count().is(inside(2, 4))},
- {__.out().count().is(outside(2, 4)), __.out().limit(5).count().is(outside(2, 4))},
+ {__.out().count().is(outside(2, 4)), __.out().count().is(outside(2, 4))}, // root: the count value is returned
{__.out().count().is(within(2, 6, 4)), __.out().limit(7).count().is(within(2, 6, 4))},
{__.out().count().is(without(2, 6, 4)), __.out().limit(6).count().is(without(2, 6, 4))},
+ // a capped count that passes is() must not be observed by later steps or the parent
+ {__.where(__.out().count().is(gt(1)).is(lt(3))), __.where(__.out().count().is(gt(1)).is(lt(3)))},
+ {__.where(__.out().count().is(gte(2)).is(lte(2))), __.where(__.out().count().is(gte(2)).is(lte(2)))},
+ {__.filter(__.out().count().is(neq(1)).is(lt(5))), __.filter(__.out().count().is(neq(1)).is(lt(5)))},
+ {__.where(__.out().count().is(gt(1)).as("a")), __.where(__.out().count().is(gt(1)).as("a"))},
+ {__.where(__.out().count().as("a").is(gt(1))), __.where(__.out().count().as("a").is(gt(1)))},
Review Comment:
I may be missing some important detail here, but in my mind this sort of `where()`/`filter()` nesting is the classic example in which the `limit()` injection optimization is safe. The `where()`/`filter()` steps are only testing whether the child traversal is productive, so the specific value of the returned count has no impact on if the filter is true or false.
--
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: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CountStrategy returning capped counts when the count is observed [tinkerpop]
Posted by "Cole-Greer (via GitHub)" <gi...@apache.org>.
Cole-Greer commented on code in PR #3717:
URL: https://github.com/apache/tinkerpop/pull/3717#discussion_r4276147797
##########
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java:
##########
@@ -84,15 +84,46 @@ public static Iterable<Object[]> generateTestParameters() {
{__.filter(__.out().out().count().is(0)), __.not(__.out().out())},
{__.local(aggregate("x")).count().is(0).as("a"), __.local(aggregate("x")).limit(1).count().is(0).as("a")},
{__.out().count().as("a").is(0), __.out().limit(1).count().as("a").is(0)},
- {__.out().count().is(neq(4)), __.out().limit(5).count().is(neq(4))},
Review Comment:
For each test case we are updating by removing the `limit()`, I think I'd like to reintroduce a new case with a similar traversal and predicate, but where we still expect a limit to be added. In this case, it could be something like this:
```
{__.out().where(__.count().is(neq(4))), __.out().where(__.limit(5).count().is(neq(4)))},
```
I'd like to retain decent coverage of "positive" cases where CountStrategy is still productive following this change.
--
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: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CountStrategy returning capped counts when the count is observed [tinkerpop]
Posted by "Cole-Greer (via GitHub)" <gi...@apache.org>.
Cole-Greer commented on code in PR #3717:
URL: https://github.com/apache/tinkerpop/pull/3717#discussion_r4331800136
##########
CHANGELOG.asciidoc:
##########
@@ -29,6 +29,7 @@ image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima
* Fixed `gremlin-go` to report a malformed or truncated GraphBinary response as a deserialization error rather than a bare decoder message.
* Made `TinkerGraph` an interface and renamed the in-memory implementation to `TinkerMemoryGraph`; `TinkerGraph.open()` and `gremlin.graph=...TinkerGraph` behave as before. *(breaking)*
* Renamed `TinkerTransactionGraph` to `TinkerStorageGraph`. *(breaking)*
+* Fixed `CountStrategy` so that it no longer adds a `limit()` before `count().is(P)` when the capped count can pass the predicate and is then observed downstream, e.g. `where(out().count().is(gt(1)).is(lt(3)))` or `out().count().is(gt(2))`, or when `P` contains a traversal, e.g. `is(gt(1).and(lt(__.constant(3))))`.
Review Comment:
Nit: Shorter changelog entries are preferred, perhaps:
```suggestion
* Fixed `CountStrategy` so that it no longer adds a `limit()` before `count().is(P)` when the capped count can pass the predicate and is then observed downstream, e.g. `out().count().is(gt(2))`.
```
--
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: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CountStrategy returning capped counts when the count is observed [tinkerpop]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #3717:
URL: https://github.com/apache/tinkerpop/pull/3717#issuecomment-6160715168
## [Codecov](https://app.codecov.io/gh/apache/tinkerpop/pull/3717?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:white_check_mark: All modified and coverable lines are covered by tests.
:white_check_mark: Project coverage is 80.17%. Comparing base ([`a28cd1f`](https://app.codecov.io/gh/apache/tinkerpop/commit/a28cd1f2f1f10c140030a56de44c5c6c045af5f0?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`1b32af4`](https://app.codecov.io/gh/apache/tinkerpop/commit/1b32af492048549508fb31e018ae57fb54d7c073?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 722 commits behind head on master.
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## master #3717 +/- ##
============================================
+ Coverage 76.35% 80.17% +3.81%
============================================
Files 1012 32 -980
Lines 60341 6950 -53391
Branches 7075 0 -7075
============================================
- Hits 46076 5572 -40504
+ Misses 11548 1050 -10498
+ Partials 2717 328 -2389
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/tinkerpop/pull/3717?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
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: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org