gortiz commented on code in PR #20002:
URL: https://github.com/apache/pinot/pull/20002#discussion_r4404325578
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/indexsegment/mutable/MutableSegmentImpl.java:
##########
@@ -1490,6 +1495,42 @@ private int[]
getSortedDocIdsWithInvertedIndex(IndexContainer indexContainer) {
return docIds;
}
+ /// Returns sorted docIds for a dictionary-encoded sorted column without an
inverted index. Sorts the dictionary
+ /// ids, ranks each dictionary id by its value order, then places the
documents by rank with a counting sort that
+ /// reads the dictionary ids from the forward index. Runs in O(n + k log k)
for n documents and k distinct values.
+ private int[] getSortedDocIdsWithDictIdForwardIndex(IndexContainer
indexContainer) {
+ MutableDictionary dictionary = indexContainer._dictionary;
+ MutableForwardIndex forwardIndex =
+ (MutableForwardIndex)
indexContainer._mutableIndexes.get(StandardIndexes.forward());
+ int numDocsIndexed = _numDocsIndexed;
+
+ // Sort all values in the dictionary, then compute the rank of each
dictionary id
+ int numValues = dictionary.length();
+ int[] sortedDictIds = new int[numValues];
+ for (int i = 0; i < numValues; i++) {
+ sortedDictIds[i] = i;
+ }
+ IntArrays.quickSort(sortedDictIds, dictionary::compare);
+ int[] ranks = new int[numValues];
+ for (int rank = 0; rank < numValues; rank++) {
+ ranks[sortedDictIds[rank]] = rank;
+ }
+
+ // Counting sort of the documents by rank. offsets[rank] is the next
position for a document with that rank.
+ int[] offsets = new int[numValues + 1];
+ for (int docId = 0; docId < numDocsIndexed; docId++) {
+ offsets[ranks[forwardIndex.getDictId(docId)] + 1]++;
+ }
+ for (int rank = 0; rank < numValues; rank++) {
+ offsets[rank + 1] += offsets[rank];
+ }
+ int[] docIds = new int[numDocsIndexed];
+ for (int docId = 0; docId < numDocsIndexed; docId++) {
+ docIds[offsets[ranks[forwardIndex.getDictId(docId)]]++] = docId;
Review Comment:
Thanks for checking this. I agree: it runs once at seal time, so I'll keep
the two reads and skip the extra int[].
--
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]
