justinborromeo commented on a change in pull request #7024: Time Ordering
Option on Small-Result-Set Scan Queries
URL: https://github.com/apache/incubator-druid/pull/7024#discussion_r258310723
##########
File path:
processing/src/main/java/org/apache/druid/query/scan/ScanQueryQueryToolChest.java
##########
@@ -131,4 +180,80 @@ public void cleanup(ScanQueryLimitRowIterator
iterFromMake)
}
};
}
+
+ @VisibleForTesting
+ Iterator<ScanResultValue>
sortAndLimitScanResultValues(Iterator<ScanResultValue> inputIterator, ScanQuery
scanQuery)
+ {
+ Comparator<ScanResultValue> priorityQComparator = new
ScanResultValueTimestampComparator(scanQuery);
+
+ // Converting the limit from long to int could theoretically throw an
ArithmeticException but this branch
+ // only runs if limit < MAX_LIMIT_FOR_IN_MEMORY_TIME_ORDERING (which
should be < Integer.MAX_VALUE)
+ int limit = Math.toIntExact(scanQuery.getLimit());
+ PriorityQueue<ScanResultValue> q = new PriorityQueue<>(limit,
priorityQComparator);
+
+ while (inputIterator.hasNext()) {
+ ScanResultValue next = inputIterator.next();
+ List<Object> events = (List<Object>) next.getEvents();
+ for (Object event : events) {
+ // Using an intermediate unbatched ScanResultValue is not that great
memory-wise, but the column list
+ // needs to be preserved for queries using the compactedList result
format
+ q.offer(new ScanResultValue(null, next.getColumns(),
Collections.singletonList(event)));
+ if (q.size() > limit) {
+ q.poll();
+ }
+ }
+ }
+ // Need to convert to a List because Priority Queue's iterator doesn't
guarantee that the sorted order
+ // will be maintained
+ final Deque<ScanResultValue> sortedElements = new ArrayDeque<>(q.size());
+ while (q.size() != 0) {
+ // We add at the front of the list because poll removes the tail of the
queue.
+ sortedElements.addFirst(q.poll());
Review comment:
Just want to double check but ArrayDeque#addFirst() is O(1), right?
Initially used a LinkedList but Forbidden APIs said no.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
[email protected]
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
