Granted Patent B2

US 12,748,757 · App. 18/830,346 · Granted Sep 29, 2026

Inventors: Jonathan Christian Nitisastro (San Mateo, CA); Zhaohui Zhang (Redwood City, CA)

Assignee: Snowflake Inc.

G06F16/24549

Abstract

Claims (117)

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 based on a column of the table and a second clause that specifies a limit on a number of results provided in the result set;

initiating execution of the top K query on the table, the initiating of the execution of the top K query comprising:

generating a query plan for processing the top K query, the query plan comprising a top K node and a table scan node;

determining run-time pruning is applicable to the top K query based on whether the table scan node is a child node or dependent child node of the top K node; and

based on determining run-time pruning is applicable to the top K query, adding a reference to the top K node in the table scan node, the reference enabling the table scan node to request a current boundary from the top K node at run-time;

determining, by the top K node, the current boundary based on a set of values identified by the table scan node in scanning the table;

performing the run-time pruning during execution of the top K query on the table using the current boundary, the performing of the run-time pruning comprising:

performing read-version pruning on a scanset of the table scan node using the current boundary during the scanning of the scanset, the scanset comprising multiple versions of the table, the performing of the read-version pruning comprising pruning data from one or more older versions of the table from the scanset;

generating a filter using the current boundary; and

using the filter to:

remove one or more scanning ranges from the scanset of the table scan node based on the column being a key column of the table; or

filter values scanned by the table scan node based on the column being a non-key column of the table; and

returning the result set based on the run-time pruning performed during execution of the top K query on the table.

2 . The method of claim 1 , wherein:

the column is the key column of the table; and

the performing of the run-time pruning comprises generating, by the table scan node, a filter based on the current boundary; and

the removing of the one or more scanning ranges comprising applying, by the table scan node, the filter to the scanset during the scanning of the table to remove the one or more scanning ranges from the scanset.

3 . The method of claim 1 , wherein:

the set of values is a first set of values identified by the table scan node in scanning the table;

the column is a non-key column of the table; and

the performing of the run-time pruning comprises generating, by the table scan node, a filter based on the current boundary; and

the filtering of values comprises applying the filter to a second set of values identified in scanning the table, the applying of the filter to the second set of values comprising discarding at least one value from the second set of values;

the method comprises providing, by the table scan node, the filtered second set of values to the top K node.

4 . The method of claim 1 , wherein the run-time pruning comprises skipping a scan of a range of values in the scanset based on metadata describing the table.

5 . The method of claim 1 , wherein:

the set of values is a first set of values identified by the table scan node in scanning the table;

the performing of the run-time pruning comprises:

determining, by the top K node, an updated boundary based on a second set of values identified by the table scan node in scanning the table; and

applying, by the table scan node, the updated boundary to further prune data during the scanning of the table.

6 . The method of claim 5 , wherein the table scan node filters the second set of values based on the current boundary prior to sending the second set of values to the top K node.

7 . The method of claim 1 , wherein:

the scanset comprises scanning ranges from multiple versions of the table;

performing the read-version pruning comprises:

comparing the current boundary against metadata for each scanning range in the scanset;

determining, based on the comparing, that all data in a particular older version of the table is outside a range of potentially relevant results; and

pruning scanning ranges from the particular older version of the table from the scanset based on the determining that all the data in the particular older version of the table is outside the range of potentially relevant results.

8 . The method of claim 7 , wherein the performing of the read-version pruning comprises pruning corresponding scanning ranges from versions of the table that are older than the particular older version of the table.

9 . The method of claim 1 , comprising sorting the scanning ranges of the scanset prior to performing the run-time pruning.

10 . The method of claim 9 , wherein sorting the scanning ranges comprises sorting the scanning ranges based on the key column of the table and the first clause of the query.

11 . The method of claim 1 , wherein the determining of the current boundary comprises:

maintaining a heap of top-K values in the top K node, the heap of top-K values storing values scanned from the table by the table scan node; and

determining the current boundary based on an extrema value in the heap of top-K values.

12 . The method of claim 1 , wherein the initiating of the execution of the top K query comprises: constructing column metadata for the column.

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

14 . A system comprising:

at least one hardware processor; and

at least one memory storing instructions that cause the at least one hardware processor 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 based on a column of the table and a second clause that specifies a limit on a number of results provided in response to the query;

initiating execution of the top K query on the table, the initiating of the execution of the top K query comprising:

generating a query plan for processing the top K query, the query plan comprising a top K node and a table scan node;

determining run-time pruning is applicable to the top K query based on whether the table scan node is a child node or dependent child node of the top K node; and

based on determining run-time pruning is applicable to the top K query, adding a reference to the top K node in the table scan node, the reference enabling the table scan node to request a current boundary from the top K node at run-time;

determining, by the top K node, the current boundary based on a set of values identified by the table scan node in scanning the table;

performing the run-time pruning during execution of the top K query on the table using the current boundary, the run-time pruning comprising:

performing read-version pruning on a scanset of the table scan node using the current boundary during the scanning of the scanset, the scanset comprising multiple versions of the table, the performing of the read-version pruning comprising pruning data from one or more older versions of the table from the scanset;

generating a filter using the current boundary; and

using the filter to:

remove one or more scanning ranges from the scanset of the table scan node based on the column being a key column of the table; or

filter values scanned by the table scan node based on the column being a non-key column of the table; and

returning the result set based on the run-time pruning performed during execution of the top K query on the table.

15 . The system of claim 14 , wherein:

the column is the key column of the table; and

the performing of the run-time pruning comprises generating, by the table scan node, a filter based on the current boundary; and

the removing of the one or more scanning ranges comprising applying, by the table scan node, the filter to the scanset during the scanning of the table to remove the one or more scanning ranges from the scanset.

16 . The system of claim 14 , wherein:

the set of values is a first set of values identified by the table scan node in scanning the table;

the column is a non-key column of the table; and

the performing of the run-time pruning comprises generating, by the table scan node, a filter based on the current boundary; and

the filtering of values comprises applying the filter to a second set of values identified in scanning the table, the applying of the filter to the second set of values comprising discarding at least one value from the second set of values;

the operations comprise providing, by the table scan node, the filtered second set of values to the top K node.

17 . The system of claim 14 , wherein the run-time pruning comprises skipping a scan of a range of values in the scanset based on metadata describing the table.

18 . The system of claim 14 , wherein:

the set of values is a first set of values identified by the table scan node in scanning the table;

the performing of the run-time pruning comprises:

determining, by the top K node, an updated boundary based on a second set of values identified by the table scan node in scanning the table; and

applying, by the table scan node, the updated boundary to further prune data during the scanning of the table.

19 . The system of claim 18 , wherein the table scan node filters the second set of values based on the current boundary prior to sending the second set of values to the top K node.

20 . The system of claim 14 , wherein:

the scanset comprises scanning ranges from multiple versions of the table;

performing the read-version pruning comprises:

comparing the current boundary against metadata for each scanning range in the scanset;

determining, based on the comparing, that all data in a particular older version of the table is outside a range of potentially relevant results; and

pruning scanning ranges from the particular older version of the table from the scanset based on the determining that all the data in the particular older version of the table is outside the range of potentially relevant results.

21 . The system of claim 20 , wherein the performing of the read-version pruning comprises pruning corresponding scanning ranges from versions of the table that are older than the particular older version of the table.

22 . The system of claim 14 , wherein the operations comprise sorting the scanning ranges of the scanset prior to performing the run-time pruning.

23 . The system of claim 22 , wherein sorting the scanning ranges comprises sorting the scanning ranges based on a key column of the table and the first clause of the query.

24 . A computer-storage medium comprising instructions that, when executed by one or more processors of a machine, configure the machine 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 based on a column of the table and a second clause that specifies a limit on a number of results provided in response to the query;

initiating execution of the top K query on the table, the initiating of the execution of the top K query comprising:

generating a query plan for processing the top K query, the query plan comprising a top K node and a table scan node;

determining run-time pruning is applicable to the top K query based on whether the table scan node is a child node or dependent child node of the top K node; and

based on determining run-time pruning is applicable to the top K query, adding a reference to the top K node in the table scan node, the reference enabling the table scan node to request a current boundary from the top K node at run-time;

determining, by the top K node, the current boundary based on a set of values identified by the table scan node in scanning the table;

performing the run-time pruning during execution of the top K query on the table using the current boundary, the run-time pruning comprising:

performing read-version pruning on a scanset of the table scan node using the current boundary during the scanning of the scanset, the scanset comprising multiple versions of the table, the performing of the read-version pruning comprising pruning data from one or more older versions of the table from the scanset; and

generating a filter using the current boundary and using the filter to:

remove one or more scanning ranges from a scanset of the table scan node based on the column being a key column of the table; or

filter values scanned by the table scan node based on the column being a non-key column of the table; and

returning the result set based on the run-time pruning performed during execution of the top K query on the table.

25 . The computer-storage medium of claim 24 , wherein:

the set of values is a first set of values identified by the table scan node in scanning the table;

the column is a non-key column of the table; and

the filtering of values comprises applying the filter to a second set of values identified in scanning the table, the applying of the filter to the second set of values comprising discarding at least one value from the second set of values;

the operations comprise providing, by the table scan node, the filtered second set of values to the top K node.

26 . The computer-storage medium of claim 24 , wherein the performing the run-time pruning comprises skipping a scan of a range of values in the scanset based on metadata describing the table.

27 . The computer-storage medium of claim 24 , wherein:

the scanset comprises scanning ranges from multiple versions of the table;

performing the read-version pruning comprises:

comparing the current boundary against metadata for each scanning range in the scanset;

determining, based on the comparing, that all data in a particular older version of the table is outside a range of potentially relevant results; and

pruning scanning ranges from the particular older version of the table from the scanset based on the determining that all the data in the particular older version of the table is outside the range of potentially relevant results.

28 . The computer-storage medium of claim 27 , wherein the performing of the read-version pruning comprises pruning corresponding scanning ranges from versions of the table that are older than the particular older version of the table.

29 . The computer-storage medium of claim 24 , wherein the operations comprise sorting the scanning ranges of the scanset prior to performing the run-time pruning.

30 . The computer-storage medium of claim 29 , wherein sorting the scanning ranges comprises sorting the scanning ranges based on the key column of the table and the first clause of the query.

Assignments (1)

Continuity (1)

References Cited (229)