Batch Query Partitioning for Multi-engine Execution

Patent metadata

Field	Value
Publication number	US-2026003872-A1
Application number	US-202418814808-A
Country	US
Kind code	A1
Filing date	Aug 26, 2024
Priority date	Jun 27, 2024
Publication date	Jan 1, 2026
Grant date	—

Abstract

Techniques are disclosed relating to partitioning batch queries for multi-engine execution. A system receives a batch query specifying query data and including a request for geospatial data for regions corresponding to the query data. Based on locations corresponding to the query data, the system partitions the query data into subsets. The system may assign the subsets of query data to query engines corresponding to the locations of the subsets. The system may cause the engines to retrieve geographic region data corresponding to the locations included in the subsets, where the retrieving is performed by a given query engine for a corresponding subset by accessing an in-memory index of the given engine that stores geographic region data for a geographic partition within which the corresponding subset of query data is located. The system may store region data retrieved by the engines for the subsets in an aggregated data store.

First claim

What is claimed is:

1 . A method, comprising:
receiving, by a computer system, a batch query, wherein the batch query specifies a set of query data and includes a request for geospatial data for one or more regions corresponding to the set of query data; partitioning, by the computer system based on geographic locations corresponding to the set of query data specified in the batch query, the set of query data into subsets of query data; assigning, by the computer system, the subsets of query data to a plurality of query engines corresponding to the geographic locations of the subsets of query data; and causing, by the computer system, the plurality of query engines to retrieve geographic region data corresponding to the geographic locations included in respective subsets of query data, wherein the retrieving is performed by a given query engine for a corresponding subset of query data by:
accessing an in-memory index of the given query engine that stores geographic region data for a geographic partition within which the corresponding subset of query data is located; and
storing, by the computer system, geographic region data retrieved by the plurality of query engines for the subsets of query data in an aggregated data store.

2 . The method of claim 1 , wherein prior to receiving the batch query, the computer system builds in-memory indexes for each of the plurality of query engines based on previously received batch queries.

3 . The method of claim 2 , wherein building the in-memory indexes includes:
dividing the surface of the earth into a plurality of cells with equal dimensions; mapping the cells to a plurality of geographic regions with one or more portions encompassed by the cells; and storing, in an in-memory index for respective ones of the cells, geographic data for regions having one or more portions encompassed by the respective ones of the cells.

4 . The method of claim 3 , wherein the plurality of geographic regions include areas encompassing one or more of the following: a town, city, a state, a country, and a continent.

5 . The method of claim 1 , wherein the set of query data included in the batch query includes a plurality of geographic coordinates, and wherein the geographic region data retrieved for the corresponding subset of query data includes data for a geographic region that encompasses a point specified by geographic coordinates included in the batch query.

6 . The method of claim 1 , further comprising:
transmitting, by the computer system to a computing device from which the batch query was received, a file path corresponding to the geographic region data stored in the aggregated data store for the batch query.

7 . The method of claim 1 , wherein the aggregated data store is an online database cache.

8 . The method of claim 1 , wherein the geographic region data includes one or more types of the following types of geographic variables: index number, creation timestamp, modification timestamp, region identifier, boundary type, and boundary coordinates.

9 . The method of claim 1 , wherein the computer system is a distributed computing system, wherein the partitioning and the assigning are performed via a mapping procedure of the distributed computing system, wherein the causing the plurality of query engines to retrieve geographic region data is performed via a summary procedure of the distributed computing system, and wherein a number of query engines executed by the distributed computing system is determined based on an amount of data included in the set of query data specified in the batch query.

10 . A non-transitory computer-readable medium having instructions stored thereon that are executable by a computing device to perform operations comprising:
receiving a batch query requesting geospatial data for one or more geographic regions corresponding to locations specified by a set of geographic coordinates; partitioning, based on the locations specified by the set of geographic coordinates specified in the batch query, the set of geographic coordinates into subsets of geographic coordinates; assigning the subsets of geographic coordinates to a plurality of query engines corresponding to the locations specified by the set of geographic coordinates; and causing the plurality of query engines to retrieve geographic region data corresponding to the locations specified by the subsets of geographic coordinates, wherein the retrieving is performed by a given query engine for a given subset of geographic coordinates by: accessing an in-memory index of the given query engine that stores geographic region data for a geographic partition within which the given subset of geographic coordinates is located; and storing geographic region data retrieved by the plurality of query engines for the subsets of geographic coordinates in an aggregated data store.

11 . The non-transitory computer-readable medium of claim 10 , wherein the geographic region data retrieved by one or more of the plurality of query engines includes one or more types of the following types of geographic variables: city, state, population, population per square mile, region shape area, and region shape length.

12 . The non-transitory computer-readable medium of claim 10 , wherein the operations further comprise:
prior to receiving the batch query, receiving a plurality of batch queries; generating, by a plurality of query engines, a plurality of in-memory indexes, wherein generating a given in-memory index includes:
partitioning the plurality of batch queries into subsets of query data;
assigning a first subset of query data to a first query engine;
retrieving, by the first query engine from one or more non-relational distributed databases, region data for a plurality of regions corresponding to geographic coordinates included in the first subset of query data; and
storing, by the first query engine, the region data for the plurality of regions in an in-memory index of the first query engine.

13 . The non-transitory computer-readable medium of claim 10 , wherein the operation further comprise:
transmitting, to another computing device from which the batch query was received, a file path corresponding to the geographic region data stored in the aggregated data store for the batch query.

14 . The non-transitory computer-readable medium of claim 10 , wherein the geographic region data retrieved for the given subset of query data includes data for a geographic region that encompasses a point specified by geographic coordinates included in the batch query.

15 . The non-transitory computer-readable medium of claim 10 , wherein the computing device is a distributed computing system, wherein the partitioning and the assigning are performed via a mapping procedure of the distributed computing system, wherein the causing the plurality of query engines to retrieve geographic region data is performed via a summary procedure of the distributed computing system, and wherein a number of query engines executed by the distributed computing system is determined based on an amount of data included in the set of query data specified in the batch query.

16 . A system, comprising:
a processor; and a non-transitory computer-readable medium having stored thereon instructions that are executable by the processor to cause the system to perform operations comprising:
receiving a batch query, wherein the batch query specifies a set of query data and includes a request for geospatial data for one or more regions corresponding to the set of query data;
partitioning, based on geographic

Assignees

• Paypal Inc

Inventors

• Yuan Yichao
• Yue Ying
• Liu Delin
• Luan Xiaojun
• Zhang Pengshan

Classifications

• G06F16/29 Primary

  Geographical information databases · CPC title

• G06F16/2228

  Indexing structures · CPC title

• G06F16/2471

  Distributed queries · CPC title

• G06F16/24556 Primary

  Aggregation; Duplicate elimination · CPC title