Optimized materialization in top-k queries

1 . 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.

2 . The method of claim 1 , wherein the selectively materializing the first value from the first value identifier only materializes the first value corresponding to the first field and does not materialize the second value corresponding to the second field.

3 . The method of claim 1 , wherein the reading further comprises reading a row position of the second field.

4 . The method of claim 3 , wherein the selectively materializing the second value corresponding to the second field comprises using the row position to identify a second value identifier and materializing, based on the second value identifier and a second dictionary, the second value.

5 . The method of claim 1 , wherein the selectively materializing the first value from the first value identifier comprises using the first value identifier to materialize, based a first dictionary, the first value.

6 . The method of claim 1 , wherein the query request is received from a client device.

7 . The method of claim 1 , further comprising:

before executing the first program code, executing third program code configured to perform a heap creation algorithm for creating the heap and storing the heap in the memory, wherein the heap is empty at creation; and

in response to the heap not being full, executing fourth program code configured to perform a heap insertion algorithm for inserting the first value and the second value into the heap,

wherein the first program code is executed in response to the heap being full.

8 . 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.

9 . The system of claim 8 , wherein the selectively materializing the first value from the first value identifier only materializes the first value corresponding to the first field and does not materialize the second value corresponding to the second field.

10 . The system of claim 8 , wherein the reading further comprises reading a row position of the second field.

11 . The system of claim 10 , wherein the selectively materializing the second value corresponding to the second field comprises using the row position to identify a second value identifier and materializing, based on the second value identifier and a second dictionary, the second value.

12 . The system of claim 8 , wherein the selectively materializing the first value from the first value identifier comprises using the first value identifier to materialize, based a first dictionary, the first value.

13 . The system of claim 8 , wherein the query request is received from a client device.

14 . The system of claim 8 , wherein in response to the heap not being full, a database execution engine reads the first value identifier of the first field and a second value identifier of the second field, materializes, based on the first value identifier and the second value identifier, the first value and the second value, and inserts the first value and the second value into the heap.

15 . 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.

16 . The non-transitory computer-readable storage medium of claim 15 , wherein the selectively materializing the first value from the first value identifier only materializes the first value corresponding to the first field and does not materialize the second value corresponding to the second field.

17 . The non-transitory computer-readable storage medium of claim 15 , wherein the reading further comprises reading a row position of the second field.

18 . The non-transitory computer-readable storage medium of claim 17 , wherein the selectively materializing the second value corresponding to the second field comprises using the row position to identify a second value identifier and materializing, based on the second value identifier and a second dictionary, the second value.