公开(公告)号：US11514047B2

公开(公告)日：2022-11-29

申请号：US17389804

申请日：2021-07-30

Applicant: Snowflake Inc.

Inventor： Matthias Carl Adams ,  Simon Holm Jensen ,  Spyridon Triantafyllis

IPC: G06F16/00 ,  G06F7/00 ,  G06F16/2453

Abstract: In an embodiment, a database platform receives query instructions for a query on a database, where the query instructions include instructions for a geospatial-function join that includes a geospatial-function predicate. The database platform generates a query-execution plan based on the query instructions, including replacing the geospatial-function join with one or more interval joins that each include one or more predicates implied by the geospatial-function predicate. The database platform inserts, into the query-execution plan above the one or more interval joins, a filter operator that applies the geospatial-function predicate. The database platform obtains results of the query at least in part by executing the query-execution plan, and returns the query results in response to the query.

公开(公告)号：US20210374139A1

公开(公告)日：2021-12-02

申请号：US17334339

申请日：2021-05-28

Applicant: Snowflake Inc.

Inventor： Matthias Carl Adams ,  Simon Holm Jensen ,  Spyridon Triantafyllis

IPC: G06F16/2453

Abstract: Disclosed herein are systems and methods for performing a geospatial-function join using an implied interval join. In an embodiment, a database platform receives a query that includes a geospatial-function join, which applies a geospatial-function predicate to a first geography data object of a first relation and a second geography data object of a second relation. The database platform processes the first and second relations through an interval join that applies an interval-join predicate that is implied by the geospatial-function predicate. The database platform obtains query results at least in part by implementing a filter that applies the geospatial-function predicate to an output of the interval join, and outputs the query results.

公开(公告)号：US11036738B1

公开(公告)日：2021-06-15

申请号：US16941236

申请日：2020-07-28

Applicant: Snowflake Inc.

Inventor： Matthias Carl Adams ,  Simon Holm Jensen ,  Spyridon Triantafyllis

IPC: G06F16/00 ,  G06F7/00 ,  G06F16/2453

Abstract: A database platform receives query instructions for a query on a database, where the query instructions include a geospatial-function join that applies a geospatial-function predicate to a first relation that includes a first join key and a second relation that includes at least one row in which a second join key is a point. The database platform generates a query-execution plan by replacing the geospatial-function join with a one-sided interval join of at least a first portion of the first relation and the at least one row of the second relation in which the second join key is a point, and by also inserting a filter above the one-sided interval join to apply the geospatial-function predicate. The database platform executes the query-execution plan, and returns query results in response to the query.

公开(公告)号：US12050605B2

公开(公告)日：2024-07-30

申请号：US17804248

申请日：2022-05-26

Applicant: Snowflake Inc.

Inventor： Matthias Carl Adams ,  Mahmud Allahverdiyev ,  Ismail Oukid ,  Peter Popov ,  Alejandro Salinger

IPC: G06F16/22 ,  G06F16/2455 ,  G06F16/28 ,  G06F16/9035 ,  G06F17/18

CPC classification number: G06F16/24557 ,  G06F16/2272 ,  G06F16/283 ,  G06F16/9035 ,  G06F17/18

Abstract: Provided herein are systems and methods for indexed geospatial predicate search. An example method performed by at least one hardware processor includes decoding a query with a geospatial predicate. The geospatial predicate is configured between a geography data column and a constant geography object. The method further includes computing a first covering for a data value of a plurality of data values in the geography data column. The first covering includes a first set of cells in a hierarchical grid representation of a geography. The first set of cells represents a surface of the geography associated with the data value. A second covering is computed for the constant geography object. A determination is made on whether to prune at least one partition of a database organized into a set of partitions and including the geography data column based on a comparison between the first covering and the second covering.

公开(公告)号：US11537614B2

公开(公告)日：2022-12-27

申请号：US17454899

申请日：2021-11-15

Applicant: Snowflake Inc.

Inventor： Matthias Carl Adams ,  Spyridon Triantafyllis ,  Lars Volker ,  Kevin Wang

IPC: G06F16/00 ,  G06F16/2453 ,  G06F16/2455 ,  G06F16/2458

Abstract: In an embodiment, a data platform receives a query that includes a two-sided N dimensional interval join of first and second input relations. The data platform samples, with respect to each of one or more of the N dimensions, one or both of the first input relation and the second input relation with respect to an interval size of an interval determined from the input relation. The data platform demarcates the N dimensional input domain into non-overlapping N dimensional input-domain cells based on the sampling. The data platform implements the interval join using a query-execution plan that includes an equality join that is keyed on input-domain-cell identifiers of input-domain cells that at least partially overlap bounding polygons of the intervals determined from the first and second input relations. The equality join is followed in the query-execution plan by a filter that applies the interval-join predicate. The data platform obtains results of the query by executing the query-execution plan.

公开(公告)号：US11036739B1

公开(公告)日：2021-06-15

申请号：US16944049

申请日：2020-07-30

Applicant: Snowflake Inc.

Inventor： Matthias Carl Adams ,  Simon Holm Jensen ,  Spyridon Triantafyllis

IPC: G06F16/00 ,  G06F7/00 ,  G06F16/2453

Abstract: A database platform receives query instructions for a query on a database, where the query instructions include a geospatial-function join that includes a geospatial-function predicate. The database platform generates a query-execution plan by replacing the geospatial-function join with a single interval join that has an interval-join predicate that is implied by the geospatial-function predicate, and by also inserting a filter above the single interval join to apply the geospatial-function predicate. The database platform executes the query-execution plan, and returns query results in response to the query.

公开(公告)号：US20240330300A1

公开(公告)日：2024-10-03

申请号：US18738252

申请日：2024-06-10

Applicant: Snowflake Inc.

Inventor： Matthias Carl Adams ,  Mahmud Allahverdiyev ,  Ismail Oukid ,  Peter Popov ,  Alejandro Salinger

IPC: G06F16/2455 ,  G06F16/22 ,  G06F16/28 ,  G06F16/9035 ,  G06F17/18

CPC classification number: G06F16/24557 ,  G06F16/2272 ,  G06F16/283 ,  G06F16/9035 ,  G06F17/18

Abstract: A method to perform an indexed geospatial search includes retrieving, by at least one hardware processor, a query specifying a geography data column and a constant geography object. A first plurality of hash functions of a first set of cells covering a surface associated with the geography data column is determined. A search index of a database including the geography data column is updated based on the first plurality of hash functions to obtain an updated search index. The query is executed on a reduced scan set of the database. The reduced scan set is based on the updated search index.

公开(公告)号：US11494379B2

公开(公告)日：2022-11-08

申请号：US17239529

申请日：2021-04-23

Applicant: Snowflake Inc.

Inventor： Matthias Carl Adams ,  Spyridon Triantafyllis ,  Lars Volker ,  Kevin Wang

IPC: G06F16/00 ,  G06F16/2453 ,  G06F16/2455 ,  G06F16/2458

Abstract: Disclosed herein are systems and methods for pre-filter deduplication for multidimensional two-sided interval joins. In an embodiment, a data platform receives query instructions for a two-sided N dimensional interval join, where N is an integer greater than 1. The two-sided N dimensional interval join has an interval-join predicate that compares intervals determined from the input relations in each of N dimensions. The data platform implements the two-sided N dimensional interval join as a query-plan section that includes an N dimensional band join that is followed by a deduplication operator that is followed by a filter that applies the interval-join predicate. The N dimensional band join includes a hash join keyed to N dimensional domain cells overlapped at least in part by intervals determined from the input relations in each of the N dimensions. The deduplication operator removes duplicate rows from a potential-duplicates subset of the output of the N dimensional band join.

公开(公告)号：US11216464B1

公开(公告)日：2022-01-04

申请号：US17239515

申请日：2021-04-23

Applicant: Snowflake Inc.

Inventor： Matthias Carl Adams ,  Spyridon Triantafyllis ,  Lars Volker ,  Kevin Wang

IPC: G06F16/00 ,  G06F16/2455 ,  G06F16/28 ,  G06F16/22 ,  G06F16/248 ,  G06F16/2453

Abstract: Disclosed herein are systems and methods for implementing multidimensional two-sided interval joins on a distributed hash-based-equality-join infrastructure. In an embodiment, a data platform receives, for a query on a database, query instructions that include a two-sided N-dimensional interval join of a first input relation and a second input relation, where N is an integer greater than 1. The two-sided N-dimensional interval join has an interval-join predicate that, in each of N dimensions, compares an interval determined from the first input relation with an interval determined from the second input relation. The data platform generates a query-execution plan that implements the two-sided N-dimensional interval join as a query-plan section that includes an N-dimensional band join followed by a filter that applies the interval-join predicate to a band-join output of the N-dimensional band join. The data platform obtains results of the query at least in part by executing the query-execution plan.

公开(公告)号：US20210374140A1

公开(公告)日：2021-12-02

申请号：US17389804

申请日：2021-07-30

Applicant: Snowflake Inc.

Inventor： Matthias Carl Adams ,  Simon Holm Jensen ,  Spyridon Triantafyllis

IPC: G06F16/2453

Abstract: In an embodiment, a database platform receives query instructions for a query on a database, where the query instructions include instructions for a geospatial-function join that includes a geospatial-function predicate. The database platform generates a query-execution plan based on the query instructions, including replacing the geospatial-function join with one or more interval joins that each include one or more predicates implied by the geospatial-function predicate. The database platform inserts, into the query-execution plan above the one or more interval joins, a filter operator that applies the geospatial-function predicate. The database platform obtains results of the query at least in part by executing the query-execution plan, and returns the query results in response to the query.