SebastianGruza opened a new issue, #3191:
URL: https://github.com/apache/hugegraph/issues/3191

   ### Bug Type (问题类型)
   
   rest-api / gremlin (结果不合预期) — paginated results contain duplicates
   
   ### Before submit
   
   - [x] 我已经确认现有的 Issues 与 FAQ 中没有相同 / 重复问题 (I have confirmed and searched that 
there are no similar problems in the historical issue and documents)
   
   ### Environment (环境信息)
   
   - Server Version: 1.7.0 built from `master` `98477f0` (also reproduced on 
master + #3184 + #3182 + #2994)
   - Backend: **RocksDB (single node) and HStore (PD + 3 store nodes) — 
identical behaviour**, so this is server-side code, not a backend
   - OS: Debian 13 VMs, Temurin 11 (server) / 17 (PD, store)
   - Data Size: any vertex with ≥ 500 edges, or any vertex label with ≥ 500 
vertices (tested with 1 222 edges on one vertex and 3 000 vertices under one 
label)
   
   ### Expected & Actual behavior (期望与实际表现)
   
   **Expected:** following the `page` token, every element is returned exactly 
once.
   
   **Actual:** when `limit` is a multiple of 500 (500, 1000, …), the **last 
element of page *k* is returned again as the first element of page *k+1*** — 
one duplicate per page boundary. No error is raised. With `limit` = 100, 250, 
333, 400 or 600 there are no duplicates.
   
   Matrix for one vertex `a` with 1 222 out-edges (1 212 of them with sort key 
`asset=ETC`), REST `GET 
/graph/edges?vertex_id="a"&direction=OUT&label=flow[&properties=…]&limit=N&page=…`,
 all pages followed to the end (`n` = elements returned, `uniq` = distinct ids):
   
   ```
   query                        limit   pages            n     uniq  dups  
last-of-page == first-of-next
   no condition                 400     [400,400,400,22] 1222  1222  0
   no condition                 500     [500,500,224]    1224  1222  2     
pages 0->1, 1->2
   no condition                 600     [600,600,22]     1222  1222  0
   no condition                 1000    [1000,223]       1223  1222  1     page 
 0->1
   asset=ETC (sort-key prefix)  500     [500,500,214]    1214  1212  2     
pages 0->1, 1->2
   asset=ETC & epoch>=150       500     [500,500,209]    1209  1207  2     
pages 0->1, 1->2
   ```
   
   Vertices by label (3 000 `person` vertices, label index): `GET 
/graph/vertices?label=person&limit=500&page=…` → 3 006 returned, 3 000 distinct 
(6 boundaries, 6 duplicates). Not affected: queries through a secondary/range 
index (`label=person&properties={"age":"P.gte(30)"}`, 2 332 / 2 332 at every 
page size) and a full scan without label (3 505 / 3 505).
   
   Same result through Gremlin: `g.V(a).outE('flow').has('~page', 
page).limit(500)`.
   
   #### Minimal reproduction
   
   ```groovy
   // gremlin: one vertex with 1200 out-edges (any >= 500 works)
   graph.schema().propertyKey('epoch').asLong().ifNotExist().create()
   
graph.schema().vertexLabel('node').useCustomizeStringId().ifNotExist().create()
   
graph.schema().edgeLabel('flow').sourceLabel('node').targetLabel('node').properties('epoch').multiTimes().sortKeys('epoch').ifNotExist().create()
   a = graph.addVertex(T.label, 'node', T.id, 'a'); b = 
graph.addVertex(T.label, 'node', T.id, 'b')
   (0..<1200).each { a.addEdge('flow', b, 'epoch', it) }
   graph.tx().commit()
   ```
   
   ```bash
   # REST (prefix /graphspaces/DEFAULT on 1.7 with graphspaces; responses are 
gzipped regardless of Accept-Encoding)
   
B='http://localhost:8080/graphs/hugegraph/graph/edges?vertex_id="a"&direction=OUT&label=flow&limit=500'
   curl -s --compressed "$B&page="            | jq -r '.edges[-1].id, .page'    
  # last id of page 1 + token
   curl -s --compressed "$B&page=<token>"     | jq -r '.edges[0].id'            
  # == last id of page 1  <-- duplicate
   # repeat with limit=400: the ids differ, as expected
   ```
   
   A stand-alone probe that runs the whole matrix against any live server 
(Python 3, stdlib only) is here:
   
https://github.com/SebastianGruza/hugegraph-oracle-suite/blob/main/suite/page_probe.py
 — it prints the duplicated ids and the page boundaries they sit on.
   
   ### Root cause
   
   `BinaryEntryIterator.fetch()` 
(`hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/backend/serializer/BinaryEntryIterator.java`,
 lines 69–96 on `98477f0`) merges store records into the current `BackendEntry` 
and leaves the loop in three ways:
   
   1. the next record belongs to a new entry → it is buffered in `this.next`; 
`position()` points at an unread key ✔
   2. the limit is reached → the loop deliberately reads `limit + 1` records 
and calls `removeLastRecord()` (lines 89–95, comment *"Need remove last one 
because fetched limit + 1 records"*) ✔
   3. the current entry holds `INLINE_BATCH_SIZE` columns → `break` (lines 
76–81) — **after** the record that triggered the check has been merged into the 
entry that is about to be emitted ✘
   
   `INLINE_BATCH_SIZE` is `Query.COMMIT_BATCH` = 500 
(`BackendEntryIterator.java:36`, `Query.java:47`; it is *not* 
`query.page_size`, the two just share the value). The backend iterator advances 
`position()` in `hasNext()` to the key of the record it is about to hand out 
(`RocksDBStdSessions.java:1133-1136`), so after exit 3 the position is the key 
of an **emitted** record. `BinaryEntryIterator.pageState()` (lines 117–123) 
builds `PageState(position, 0, count)` with the offset hard-coded to 0, and the 
next page restarts **inclusively** from that position 
(`BinarySerializer.prefixQuery` → `IdPrefixQuery(inclusive = true)`, 
`BinarySerializer.java:946-963`; sort-key range queries force `includeStart = 
true` at `:704-713`). Hence the duplicate.
   
   Why only multiples of 500: with `limit = L`, exit 2 fires on record `L+1` 
and removes it — clean. When `L mod 500 == 0`, exit 3 fires on record `L` 
*before* record `L+1` is read; the consumer then stops on `reachLimit()` 
without calling `fetch()` again, so the position is never refreshed. 
`QueryList.OptimizedQuery.iterator()` (`QueryList.java:166-183`) passes the 
user limit straight to the store (*"Not set limit to pageSize due to 
PageEntryIterator.remaining"*), so `query.page_size` never splits the scan and 
changing it cannot fix the edge case. For the label-index path the sub-query 
limit **is** `query.page_size` (`IdHolder.java:124-138`, 
`GraphIndexTransaction.doIndexQueryOnce` `:736-761`), but a label index keeps 
all element ids under one index key — one huge entry, same stale position.
   
   Not related to #3190 (query-batch boundaries in 
`QueryResults`/`InputOrderIterator`): the batch here is the 500-record chunk of 
a single backend entry inside `BinaryEntryIterator`, and the defect is the page 
position it leaves behind.
   
   Related: the four `// FIXME` blocks in `BinarySerializer.java` (708-711, 
824-827, 856-859, 954-957) that disable the lower-bound assertion *"due to the 
inconsistency in the definition of `position` of RocksDB scan iterator and 
Hstore"*, and the `// QUESTION: Resetting the position` comments in 
`HstoreSessionsImpl.ColumnIterator` (`:245-254`, `:318-328`). The existing 
paging tests (`EdgeCoreTest.testQuery*EdgesOfVertexInPaging`) use `limit(1)` on 
18 edges and never cross a batch boundary; the REST default `limit=100` hides 
it in everyday use.
   
   ### Fix
   
   Check the full batch **before** merging the record and start the next entry 
with it (`this.next = this.merger.apply(null, elem)`), so that `position()` 
never points at an emitted record — the same invariant the limit path keeps via 
`removeLastRecord()`. ~24 lines in `BinaryEntryIterator`, plus a core test 
(`EdgeCoreTest#testQueryOutEdgesOfVertexInPagingAtBatchBoundary`: 1 200 edges, 
page limits 400 / 500 / 600 / 1 000, asserts count and distinct count). On 
unpatched core the test fails with `limit 500 expected:<1200> but was:<1202>`; 
with the fix it passes. With the patched `hugegraph-core` deployed to both a 
RocksDB and an HStore server the matrix above is `dups=0` for every size, and a 
174-query cross-backend regression run differs from the pre-fix run in exactly 
one case (1 214 → 1 212, same set of distinct ids).
   
   I will open a PR with the fix and the test. Full analysis and before/after 
data: 
https://github.com/SebastianGruza/hugegraph-oracle-suite/blob/main/docs/findings.md#f1
 (found by comparing id sets between RocksDB and HStore on the same server: 
both backends carried the bug, `distinct < returned` on the reference side gave 
it away).
   
   ### Vertex/Edge example (问题点 / 边数据举例)
   
   ```javascript
   // limit=500 over 1212 edges a->b (sort keys asset, epoch); page 1 last id 
== page 2 first id, page 2 last id == page 3 first id
   GET 
/graphspaces/DEFAULT/graphs/hugegraph/graph/edges?vertex_id="a"&direction=OUT&label=flow&properties={"asset":"ETC"}&limit=500&page=
   // duplicated ids observed (positions 500 and 1000 of the concatenated 
pages):
   "Sa>1>1>ETC!2NI>Sb", "Sa>1>1>ETC!2V5>Sb"
   // limit=400 / 600 over the same data: 1212 ids, all distinct
   ```
   
   ### Schema [VertexLabel, EdgeLabel, IndexLabel] (元数据结构)
   
   ```javascript
   // GET /graphspaces/DEFAULT/graphs/hugegraph/schema/edgelabels/flow
   
{"name":"flow","source_label":"node","target_label":"node","frequency":"MULTIPLE","sort_keys":["asset","epoch"],
    
"properties":["asset","epoch","amount"],"nullable_keys":[],"enable_label_index":false}
   // vertexlabel node: id_strategy CUSTOMIZE_STRING; property keys asset TEXT, 
epoch LONG, amount DOUBLE
   // the vertex-label variant used vertexlabel person (CUSTOMIZE_STRING, 
enable_label_index true) with 3000 vertices
   ```
   


-- 
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]

Reply via email to