Back to results
US 12,711,135 B2Granted
Optimized materialization in top-k queries
AssigneeSap SE
InventorsAlexander Ostertag, Paul Willems
Life of this patent
Estimating the term…
Abstract
In some implementations, there is provided query execution optimization for a top k query that includes in response to a first value being less than a first heap value, selectively materializing a second value corresponding to a second field and inserting the first value and the second value into the heap, and in response to the first value not being less that the first heap value, skipping the first incoming element and proceeding, when available, to another incoming element. Related systems, methods and articles of manufacture are also disclosed.
Claims18
A method comprising:
- receiving a query request including a top k query operator over at least two fields comprising a first field and a second field, wherein k defines a threshold limit of query results for the top k query operator;
- reading a first incoming element as a first value identifier of the first field;
- selectively materializing a first value from the first value identifier;
- executing first program code configured to perform to a heap updating algorithm for updating data stored in a heap, wherein the heap is a data structure stored in a memory, the heap updating algorithm comprising steps of comparing a top element of the heap to the first incoming element by at least:
- comparing the first value materialized from the first value identifier to a first heap value of the top element of the heap,
- in response to the first value being less than the first heap value, selectively materializing a second value corresponding to the second field and inserting the first value and the second value into the heap,
- in response to the first value being equal to the first heap value, materializing the second field to provide the second value and comparing the second value to a second heap value of the top element of the heap, and
- in response to the first value being greater than the first heap value, skipping the first incoming element and proceeding, when available, to another incoming element;
- in response to completing the heap updating algorithm, executing second program code configured to perform a heap sorting algorithm for sorting the data stored in the heap;
- and
- in response to completing the heap sorting algorithm, responding to the query request by providing the heap including a top k set of query results.
8 more elements
A system comprising:
- at least one processor;
- and
- at least one memory comprising instructions which when executed by the at least one processor causes operations comprising:
- receiving a query request including a top k query operator over at least two fields comprising a first field and a second field, wherein k defines a threshold limit of query results for the top k query operator;
- reading a first incoming element as a first value identifier of the first field;
- selectively materializing a first value from the first value identifier;
- executing first program code configured to perform to a heap updating algorithm for updating data stored in a heap, wherein the heap is a data structure stored in a memory, the heap updating algorithm comprising steps of comparing a top element of the heap to the first incoming element by at least:
- comparing the first value materialized from the first value identifier to a first heap value of the top element of the heap,
- in response to the first value being less than the first heap value, selectively materializing a second value corresponding to the second field and inserting the first value and the second value the heap,
- in response to the first value being equal to the first heap value, materializing the second field to provide the second value and comparing the second value to a second heap value of the top element of the heap, and
- in response to the first value being greater than the first heap value, skipping the first incoming element and proceeding, when available, to another incoming element;
- in response to completing the heap updating algorithm, executing second program code configured to perform a heap sorting algorithm for sorting the data stored in the heap;
- and
- in response to completing the heap sorting algorithm, responding to the query request by providing the heap including a top k set of query results.
11 more elements
A non-transitory computer-readable storage medium comprising at least one memory comprising instructions which when executed by at least one processor causes operations comprising:
- receiving a query request including a top k query operator over at least two fields comprising a first field and a second field, wherein k defines a threshold limit of query results for the top k query operator;
- reading a first incoming element as a first value identifier of the first field;
- selectively materializing a first value from the first value identifier;
- executing first program code configured to perform to a heap updating algorithm for updating data stored in a heap, wherein the heap is a data structure stored in a memory, the heap updating algorithm comprising steps of comparing a top element of the heap to the first incoming element by at least:
- comparing the first value materialized from the first value identifier to a first heap value of the top element of the heap,
- in response to the first value being less than the first heap value, selectively materializing a second value corresponding to the second field and inserting the first value and the second value into the heap,
- in response to the first value being equal to the first heap value, materializing the second field to provide the second value and comparing the second value to a second heap value of the top element of the heap, and
- in response to the first value being greater than the first heap value, skipping the first incoming element and proceeding, when available, to another incoming element;
- in response to completing the heap updating algorithm, executing second program code configured to perform a heap sorting algorithm for sorting the data stored in the heap;
- and
- in response to completing the heap sorting algorithm, responding to the query request by providing the heap including a top k set of query results.
8 more elements
Dependencies are inferred from the claim text.