[Bug] Paging returns the page-boundary record twice when limit is a multiple of 500 (BinaryEntryIterator; RocksDB and HStore)

[SebastianGruza]

Bug Type (问题类型)

rest-api / gremlin (结果不合预期) — paginated results contain duplicates

Before submit

• 我已经确认现有的 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 + fix(hstore): don't push sysprop-only range queries down to the store #3184 + fix(server): filter index results before input ordering #3182 + fix(server): clarify condition resolution semantics for label queries #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

// 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()

# 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 (问题点 / 边数据举例)

// 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] (元数据结构)

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