You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pinot.apache.org by GitBox <gi...@apache.org> on 2022/06/06 15:18:18 UTC
[GitHub] [pinot] richardstartin opened a new issue, #8837: `order by DESC limit N` queries are not optimised at segment level
richardstartin opened a new issue, #8837:
URL: https://github.com/apache/pinot/issues/8837
A query like
```sql
SELECT *
FROM table
WHERE filter
ORDER BY sorted_col DESC
LIMIT 10;
```
is not optimised and hits the generic `SelectionOrderByOperator.computePartiallyOrdered()` which inserts up to 10k elements into a priority queue to discard all but the last 10. For ascending order, the query below is roughly 3-4x faster per segment.
```sql
SELECT *
FROM table
WHERE filter
ORDER BY sorted_col ASC
LIMIT 10;
```
--
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: commits-unsubscribe@pinot.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] chenboat commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1587807837
@Jackie-Jiang @gortiz O(n) is still not as good as O(k) for small K on a sorted segment. What is the issue with using reverseIterator as mentioned in this thread earlier? We can help to contribute on fixing this issue.
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] gortiz commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by GitBox <gi...@apache.org>.
gortiz commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1163143093
I think we need to invest some time optimizing sorted by, as there are too many cases where the optimizations can be applied but they are not. One example:
```
SELECT *
FROM table
WHERE filter
ORDER BY sorted_col ASC, any_other_thing
LIMIT 10;
```
Where `any_other_thing` may be a column, an operation or even a literal!
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] richardstartin commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by GitBox <gi...@apache.org>.
richardstartin commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1147747514
> We will maintain a priority queue of size 10, and insert all the matching docs (instead of up to 10k) to the priority queue.
All 10k records will be inserted into the PQ, regardless of whether the insertion results in the removal of another or not. 9990 records will be removed from the PQ. This is clearly wasteful.
Reverse iteration is supported by RoaringBitmap for this exact purpose.
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] gortiz commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by "gortiz (via GitHub)" <gi...@apache.org>.
gortiz commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1571593283
That is the PR that originally had a partial implementation that optimized the order by desc, but we decided to drop these changes and only optimize the order by asc case because we weren't sure about the correctness of the order by desc optimization.
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] Jackie-Jiang commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1147742796
We will maintain a priority queue of size 10, and insert all the matching docs (instead of up to 10k) to the priority queue. For the first case, the new inserted value is always the top value, we we need to heapify the heap for every insert.
We should optimize the engine so that when we order by a sorted column (either DESC or ASC), we do not insert all the matching docs, but only the first N or last N based on the sorting order. One challenge here is that we don't support iterating the matching docs in the reverse order currently.
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] ashishkf commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by GitBox <gi...@apache.org>.
ashishkf commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1311292041
In addition, we should push the limit down to the filter - especially, scan based filters as these can be quite expensive.
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] Jackie-Jiang commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1150190308
We are actually talking about the same thing. For descending order case, all values will be inserted into the priority queue once, then removed after new value comes.
The confusion is from the "10K elements" because the cost of the current algorithm should not be related to the values per block. I see you are referring the cost of `SelectionOrderByOperator.computePartiallyOrdered()` which is per block, and I was referring the cost of processing the whole segment.
- Document count: N (10k per block, millions per segment)
- Query LIMIT: m
- Time complexity of the algorithm: O(Nlogm)
I agree this is very not efficient (actually the worst case scenario). We should be able to optimize the algorithm for both ascending and descending order case, and early terminate when enough documents are collected instead of processing all the blocks. For descending order case, we need to scan the matched docs in the reverse order
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] gortiz commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by GitBox <gi...@apache.org>.
gortiz commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1311976772
I think we are already pushing that whenever we can. Did you find a case where we do not?
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] Jackie-Jiang commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1322553942
@ashishkf Good call! Created #9839 to track various improvements for AND operator
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] richardstartin commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by GitBox <gi...@apache.org>.
richardstartin commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1150292646
Exactly, reverse doc id iteration makes this easy to optimise.
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] chenboat commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1570933700
Thanks. Is there a plan to add reversed cursor?
BTW, The PR #8979 is titled "optimize order by sorted ASC, unsorted and order by DESC cases". Does it mean there is still no optimization over **_ORDER BY sorted_col DSC_** cases?
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] gortiz commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by "gortiz (via GitHub)" <gi...@apache.org>.
gortiz commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1588669490
The main issue with reverse iterator is that there are a lot of places where it is assumed the cursors are ascending. Therefore adding a reverse iterator seems very intrusive and may have deep lateral implications in the code. We discovered that problem very fast and therefore didn't dedicate much time thinking on the actual implications these new reverse iterators may have, moving the focus to other task that have higher priority for our use cases.
Feel free to try to add that your self, but I think it would be great to have a PEP trying to describe the impact these iterators may have, including in V2 engine.
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] richardstartin commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by GitBox <gi...@apache.org>.
richardstartin commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1149520182
> > All 10k records will be inserted into the PQ, regardless of whether the insertion results in the removal of another or not. 9990 records will be removed from the PQ. This is clearly wasteful.
>
> Not sure if we are referring to the same thing. In `SelectionOperatorUtils.addToPriorityQueue()`, we insert the value into the query only when it is larger than the top value. The PQ size will be up to 10 all the time
I think the communication gap here is because you may have missed that the scope if this issue is strictly _descending order over sorted columns_ so you have jumped to assuming I don't understand the algorithm.
_When the values are sorted and the comparator is descending_, the next value is always greater than the smallest element in the PQ. This means the next value always added, and the smallest value is removed after the limit is reached. E.g. imagine the limit is 2, this table shows the state of the PQ for each docId.
| docId | Value | PQ |
| ------ | ------ | ----------------------- |
| 0 | 10 | [10] |
| 1 | 15 | [10, 15] |
| 2 | 30 | [15, 30] |
| 3 | 400 | [30, 400] |
The PQ never grows beyond the size of 2, but that claim hasn't actually been made. After the first two values, for descending order over a sorted column, the second condition below is always true. Every value is added to the PQ once, and all but the last 2 values are eventually removed from the PQ.
```java
public static <T> void addToPriorityQueue(T value, PriorityQueue<T> queue, int maxNumValues) {
if (queue.size() < maxNumValues) {
queue.add(value);
} else if (queue.comparator().compare(queue.peek(), value) < 0) {
queue.poll();
queue.offer(value);
}
}
```
That is, for each block, the algorithm _"inserts up to 10k elements into a priority queue to discard all but the last 10"_.
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] gortiz commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by "gortiz (via GitHub)" <gi...@apache.org>.
gortiz commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1570819446
No, it is not optimized. We had a partial implementation, but decided to postpone it until we have reversed cursors.
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] Jackie-Jiang commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by "Jackie-Jiang (via GitHub)" <gi...@apache.org>.
Jackie-Jiang commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1574365874
@gortiz We did optimize order by desc right? It is not as optimized as asc because we still need to scan all the values, but within each block, we don't put values into heap any more, so the algorithm is O(n) instead of O(nlogk) where k is the limit
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] Jackie-Jiang commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1149322559
> All 10k records will be inserted into the PQ, regardless of whether the insertion results in the removal of another or not. 9990 records will be removed from the PQ. This is clearly wasteful.
Not sure if we are referring to the same thing. In `SelectionOperatorUtils.addToPriorityQueue()`, we insert the value into the query only when it is larger than the top value. The PQ size will be up to 10 all the time
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] ashishkf commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by GitBox <gi...@apache.org>.
ashishkf commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1312080456
> I think we are already pushing that whenever we can. Did you find a case where we do not?
For scan based filters, I don't see where the limit is pushed down. When SVScanDocIdIterator.applyAnd is invoked, it goes through all the docs from docIds parameters and tries to match value.
Ideally, caller of the applyAnd (AndDocIdSet) should call applyAnd with limit and if multiple scan based child filters are present, it should keep looping till limit is reached.
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] gortiz commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by "gortiz (via GitHub)" <gi...@apache.org>.
gortiz commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1577221027
You are right Jackie, as usual!
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] chenboat commented on issue #8837: `order by DESC limit N` queries are not optimised at segment level
Posted by "chenboat (via GitHub)" <gi...@apache.org>.
chenboat commented on issue #8837:
URL: https://github.com/apache/pinot/issues/8837#issuecomment-1570703937
@Jackie-Jiang @gortiz Is this issue resolved now? It is still OPEN. We also experienced slow query perf for this type of queries.
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org