imbajin commented on code in PR #2994:
URL: https://github.com/apache/hugegraph/pull/2994#discussion_r3421363329
##########
hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/backend/tx/GraphIndexTransaction.java:
##########
@@ -657,6 +664,266 @@ private IdHolder doIndexQuery(IndexLabel indexLabel,
ConditionQuery query) {
}
}
+ private boolean needMaterializedHstoreRangeOrder(IndexLabel indexLabel,
+ ConditionQuery query) {
+ return this.store().provider().isHstore() &&
+ indexLabel.indexType().isRange() &&
+ (query.paging() || !query.noLimitAndOffset());
+ }
+
+ private IdHolder doMaterializedHstoreRangeIndexQuery(IndexLabel indexLabel,
+ ConditionQuery query)
{
+ if (!query.paging()) {
+ Set<Id> ids = this.querySortedRangeIndexIds(indexLabel, query);
+ return this.newSortedRangeIndexBatchHolder(query, ids);
+ }
+ return new SortedRangePagingIdHolder(query, q -> {
+ return this.querySortedRangeIndexPage(indexLabel, q);
+ });
+ }
+
+ private BatchIdHolder newSortedRangeIndexBatchHolder(ConditionQuery query,
+ Set<Id> ids) {
+ return new SortedRangeBatchIdHolder(query, ids);
+ }
+
+ private Set<Id> querySortedRangeIndexIds(IndexLabel indexLabel,
+ ConditionQuery query) {
+ List<HugeIndex> indexes = this.querySortedRangeIndexes(indexLabel,
+ query);
+ Set<Id> ids = InsertionOrderUtil.newSet();
+ for (HugeIndex index : indexes) {
+ ids.addAll(index.elementIds());
+ Query.checkForceCapacity(ids.size());
+ }
+ return ids;
+ }
+
+ private PageIds querySortedRangeIndexPage(IndexLabel indexLabel,
+ ConditionQuery query) {
+ List<HugeIndex> indexes = this.querySortedRangeIndexes(indexLabel,
+ query);
+ Set<Id> allIds = InsertionOrderUtil.newSet();
+ for (HugeIndex index : indexes) {
+ allIds.addAll(index.elementIds());
+ Query.checkForceCapacity(allIds.size());
+ }
+ if (allIds.isEmpty()) {
+ return PageIds.EMPTY;
+ }
+
+ int start = 0;
+ if (!query.page().isEmpty()) {
+ start = PageState.fromString(query.page()).offset();
+ }
+ if (start >= allIds.size()) {
+ return PageIds.EMPTY;
+ }
+
+ long total = allIds.size();
+ long end = query.noLimit() ? total :
+ Math.min(total, (long) start + query.limit());
+ Set<Id> pageIds = CollectionUtil.subSet(allIds, start, (int) end);
+ if (pageIds.isEmpty()) {
+ return PageIds.EMPTY;
+ }
+
+ int next = (int) end;
+ PageState pageState;
+ if (next < total) {
+ pageState = new PageState(new byte[]{1}, next, pageIds.size());
+ } else {
+ pageState = new PageState(PageState.EMPTY_BYTES, 0,
+ pageIds.size());
+ }
+ return new PageIds(pageIds, pageState);
+ }
+
+ private List<HugeIndex> querySortedRangeIndexes(IndexLabel indexLabel,
+ ConditionQuery query) {
+ List<HugeIndex> indexes = new ArrayList<>();
+ Iterator<BackendEntry> entries = null;
+ String spaceGraph = this.params()
+ .graph().spaceGraphName();
+ LockUtil.Locks locks = new LockUtil.Locks(spaceGraph);
+ ConditionQuery scanQuery = query.copy();
+ scanQuery.page(null);
+ scanQuery.offset(0L);
+ scanQuery.limit(Query.NO_LIMIT);
Review Comment:
‼️ **Avoid full-range materialization for bounded HStore range-index
queries**
This path is still risky because it preserves correctness by clearing the
backend bounds and materializing the whole matched range before applying
`limit` / `offset` / `page` in the graph layer.
Some Gremlin examples that can trigger the issue on HStore range indexes:
```groovy
g.V().hasLabel('software').has('price', P.between(1, 1000000)).limit(10)
g.V().hasLabel('person').has('birth', P.between(start, end)).range(20, 40)
g.V().hasLabel('event').has('timestamp', P.gte(dayStart)).has('~page',
'').limit(20)
```
The user asks for a bounded page, but this fallback can behave like:
```text
range-index query + limit/page
|
v
clear page + offset + limit
|
v
scan the full matched HStore range
|
v
sort everything in memory
|
v
slice the requested page
```
On a large HStore deployment, a query that appears to request only 10 or 20
rows can scan and sort a very large range under index-label read locks. That is
a significant hidden performance risk and does not match the expected behavior
of paged range queries.
I think the preferred fix is **option B**: keep the ordering fix in the
HStore/store-client layer with a bounded ordered merge of partition iterators,
then stop as soon as enough rows are collected for `offset + limit` or the
requested page size:
```text
partition iterator A
partition iterator B
partition iterator C
\ | /
ordered k-way merge
|
v
stop after the requested page is satisfied
```
If that is too large for this PR, please consider removing this graph-layer
materialized fallback from the current PR, leave a clear FIXME near the HStore
range scan path, and handle globally ordered HStore range-index paging in a
separate follow-up. I don't think we should merge a correctness fix that
silently turns bounded range-index queries into potential full-range scans.
--
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]
