Pruning techniques for processing top K queries

1 . A method comprising:

receiving a top K query directed at a table, the top K query comprising a first clause to sort a result set in an order and a second clause that specifies that the result set is limited to a specific number of rows from the table;

generating a query plan for the top K query, the query plan comprising a table scan operator and a top K operator positioned downstream of the table scan operator;

based on the query plan, configuring a set of execution nodes to comprise the table scan operator and the top K operator positioned downstream of the table scan operator, each execution node in the set of execution nodes comprising at least one hardware processor;

identifying, by the table scan operator, a first set of rows from the table, the first set of rows having the specific number of rows;

determining, by the top K operator, a current boundary based on the first set of rows;

generating, by the table scan operator, a pruned scan set based on the current boundary determined by the top K operator;

identifying, by the table scan operator, a second set of rows from the table based on the pruned the scan set; and

providing the result set responsive to the top K query based on the first and second set of rows, the result set being limited to the specific number of rows specified by the second clause of the top K query.

2 . The method of claim 1 , comprising:

identifying an updated boundary based on the second set of rows; and

pruning the pruned scan set further based on the updated boundary.

3 . The method of claim 1 , wherein the determining of the current boundary comprises identifying an extrema value from the first set of rows.

4 . The method of claim 1 , comprising sorting a scan set for the top K query in ascending or descending order based on the first clause of the top K query.

5 . The method of claim 1 , comprising loading a portion of the table.

6 . The method of claim 5 , wherein the pruning of the scan set comprises:

accessing metadata associated with the portion of the table; and

discarding the portion based on the metadata and the current boundary.

7 . The method of claim 6 , wherein:

the metadata specifies an extrema value stored in the portion of the table;

the current boundary comprises a boundary value; and

the generating of the pruned scan set further comprises:

performing a comparison of the boundary value to the extrema value; and

discarding the portion of the table based on the comparison.

8 . The method of claim 7 , wherein:

the portion of the table comprises a storage unit from among multiple storage units of the table; and

discarding the portion of the table from the scan set comprises discarding the storage unit.

9 . The method of claim 7 , wherein the identifying of the second set of rows comprises:

identifying a third set of rows based on the pruned scan set; and

filtering the third set of rows by removing one or more rows from the third set of rows based on the current boundary, the filtering of the third set of rows resulting in the second set of rows.

10 . The method of claim 1 , wherein:

the first clause comprises an ORDER BY clause in structured query language (SQL); and

the second clause comprises a LIMIT clause in SQL.

11 . A system comprising:

one or more hardware processors; and

at least one memory storing instructions that cause the one or more hardware processors to perform operations comprising:

receiving a top K query directed at a table, the top K query comprising a first clause to sort a result set in an order and a second clause that specifies that the result set is limited to a specific number of rows from the table;

generating a query plan for the top K query, the query plan comprising a table scan operator and a top K operator positioned downstream of the table scan operator;

based on the query plan, configuring a set of execution nodes to comprise the table scan operator and the top K operator positioned downstream of the table scan operator, each execution node in the set of execution nodes comprising at least one of the one or more hardware processors;

identifying, by the table scan operator, a first set of rows from the table, the first set of rows having the specific number of rows;

determining, by the top K operator, a current boundary based on the first set of rows;

generating, by the table scan operator, a pruned scan set based on the current boundary determined by the top K operator;

identifying, by the table scan operator, a second set of rows from the table based on the pruned the scan set; and

providing the result set responsive to the top K query based on the first and second set of rows, the result set being limited to the specific number of rows specified by the second clause of the top K query.

12 . The system of claim 11 , wherein the operations comprise:

identifying an updated boundary based on the second set of rows; and

pruning the pruned scan set further based on the updated boundary.

13 . The system of claim 11 , wherein the determining of the current boundary comprises identifying an extrema value from the first set of rows.

14 . The system of claim 11 , wherein the operations comprise:

sorting the pruned scan set in ascending or descending order based on the first clause of the top K query.

15 . The system of claim 11 , further comprising loading a portion of the table.

16 . The system of claim 15 , wherein the pruning of the scan set comprises:

accessing metadata associated with the portion of the table; and

discarding the portion based on the metadata and the current boundary.

17 . The system of claim 16 , wherein:

the metadata specifies an extrema value stored in the portion of the table;

the current boundary comprises a boundary value; and

the generating of the pruned scan set further comprises:

performing a comparison of the boundary value to the extrema value; and

discarding the portion of the table based on the comparison.

18 . The system of claim 17 , wherein:

the portion of the table comprises a storage unit from among multiple storage units of the table; and

discarding the portion of the table from the scan set comprises discarding the storage unit.

19 . The system of claim 17 , wherein the identifying of the second set of rows comprises:

identifying a third set of rows based on the pruning of the scan set; and

filtering the third set of rows by removing one or more rows from the third set of rows based on the current boundary, the filtering of the third set of rows resulting in the second set of rows.

20 . A computer-storage medium comprising instructions that, when executed by one or more processors of one or more machines, configure the one or more machines to perform operations comprising:

receiving a top K query directed at a table, the top K query comprising a first clause to sort a result set in an order and a second clause that specifies that the result set is limited to a specific number of rows from the table;

generating a query plan for the top K query, the query plan comprising a table scan operator and a top K operator positioned downstream of the table scan operator;

based on the query plan, configuring a set of execution nodes to comprise the table scan operator and the top K operator positioned downstream of the table scan operator, each execution node of the set of execution nodes comprising at least one of the one or more processors;

identifying, by the table scan operator, a first set of rows from the table, the first set of rows having the specific number of rows;

determining, by the top K operator, a current boundary based on the first set of rows;

generating, by the table scan operator, a pruned scan set based on the current boundary determined by the top K operator;

identifying, by the table scan operator, a second set of rows from the table based on the pruned the scan set; and

providing the result set responsive to the top K query based on the first and second set of rows, the result set being limited to the specific number of rows specified by the second clause of the top K query.