Efficient multi-tenant spatial and relational indexing

Patent metadata

Field	Value
Publication number	US-10242051-B2
Application number	US-201615213726-A
Country	US
Kind code	B2
Filing date	Jul 19, 2016
Priority date	May 13, 2013
Publication date	Mar 26, 2019
Grant date	Mar 26, 2019

Abstract

Methods, computer systems, and computer-storage media are provided for increasing the efficiency of a multi-tenant geospatial data index. Efficiency is increased by using a multi-tenant model for storing and serving the data, processing raw geospatial data received from tenants into a runtime-optimized format, and by partitioning tenant geospatial data into a processor memory portion and a file system memory portion. Efficiency is also increased by executing a staged upload of the processor memory portion and the file system memory portion to a subset of host machines in order to check for invalid data before uploading the data to the remaining host machines. Additionally, efficiency is increased by optimizing geospatial search queries using query filters stored in a query filter cache, and executing the query filters initially against the processor memory.

First claim

What is claimed is:

1. One or more computer-storage media having computer-executable instructions embodied thereon that, when executed, perform a method of optimizing queries for geospatial data and executing the optimized queries first against processor memory of a host machine, the method comprising:
receiving a geospatial search query from a tenant having a set of geospatial data stored in association with a file system memory of the host machine and a subset of the set of geospatial data stored in association with the processor memory of the host machine, wherein the subset of the set of geospatial data represents geospatial data frequently utilized by the tenant, and wherein the file system memory comprises non-volatile memory and the processor memory comprises non-persistent memory;
generating a parsed structured query from the geospatial search query;
determining whether a query filter cache contains a query filter corresponding to the parsed structured query;
when it is determined that the query filter cache contains the query filter corresponding to the parsed structured query, retrieving from the query filter cache the query filter corresponding to the parsed structured query;
when it is determined that the query filter cache does not contain the query filter corresponding to the parsed structured query, dynamically generating the query filter corresponding to the parsed structured query and storing the query filter in association with the query filter cache;
executing the query filter against the subset of the tenant's set of geospatial data stored in association with the processor memory of the host machine to retrieve a first set of geospatial data index entries satisfying the query filter, wherein the first set of geospatial data index entries represents the subset of the set of geospatial data; and
using the first set of geospatial data index entries to retrieve a second set of full geospatial data index entries from the tenant's set of geospatial data stored in association with the file system memory of the host machine, wherein the second set of full geospatial data index entries represents the set of geospatial data.

2. The media of claim 1 , wherein the host machine stores a plurality of sets of geospatial data associated with a plurality of tenants.

3. The media of claim 1 , further comprising:
filtering the second set of full geospatial data index entries based on the geospatial search query to produce a set of geospatial search results; and
returning to the tenant the set of geospatial search results.

4. The media of claim 1 , wherein the parsed structured query is generated based on parameters specified by the tenant.

5. The media of claim 1 , wherein the query filter cache contains tenant-specific query filters.

6. A computerized method carried out by a host machine having at least one processor for optimizing queries for geospatial data and executing the optimized queries first against processor memory of a host machine, the method comprising:
receiving a geospatial search query from a tenant having a set of geospatial data stored in association with a file system memory of the host machine and a subset of the set of geospatial data stored in association with the processor memory of the host machine, wherein the subset of the set of geospatial data represents geospatial data frequently utilized by the tenant, and wherein the file system memory comprises non-volatile memory and the processor memory comprises non-persistent memory;
generating a parsed structured query from the geospatial search query;
determining whether a query filter cache contains a query filter corresponding to the parsed structured query;
when it is determined that the query filter cache contains the query filter corresponding to the parsed structured query, retrieving from the query filter cache the query filter corresponding to the parsed structured query;
when it is determined that the query filter cache does not contain the query filter corresponding to the parsed structured query, dynamically generating the query filter corresponding to the parsed structured query and storing the query filter in association with the query filter cache;
executing the query filter against the subset of the tenant's set of geospatial data stored in association with the processor memory of the host machine to retrieve a first set of geospatial data index entries satisfying the query filter, wherein the first set of geospatial data index entries represents the subset of the set of geospatial data; and
using the first set of geospatial data index entries to retrieve a second set of full geospatial data index entries from the tenant's set of geospatial data stored in association with the file system memory of the host machine, wherein the second set of full geospatial data index entries represents the set of geospatial data.

7. The method of claim 6 , wherein the host machine stores a plurality of sets of geospatial data associated with a plurality of tenants.

8. The method of claim 6 , further comprising:
filtering the second set of full geospatial data index entries based on the geospatial search query to produce a set of geospatial search results; and
returning to the tenant the set of geospatial search results.

9. The method of claim 6 , wherein the parsed structured query is generated based on parameters specified by the tenant.

10. The method of claim 6 , wherein the query filter cache contains tenant-specific query filters.

11. A system for optimizing queries for geospatial data and executing the optimized queries first against processor memory of a host machine, the system comprising:
a first computing device associated with a host machine, the computing device having one or more processors and one or more computer-storage media;
a file system memory associated with the host machine, the file system memory comprising non-volatile memory; and
a processor memory associated with the host machine, the processor memory comprising non-persistent memory,
wherein the host machine:
receives a geospatial search query from a tenant having a set of geospatial data stored in association with the file system memory of the host machine and a subset of the set of geospatial data stored in association with the processor memory of the host machine, wherein the subset of the set of geospatial data represents geospatial data frequently utilized by the tenant;
generates a parsed structured query from the geospatial search query;
determines whether a query filter cache contains a query filter corresponding to the parsed structured query;
when it is determined that the query filter cache contains the query filter corresponding to the parsed structured query, retrieves from the query filter cache the query filter corresponding to the parsed structured query;
where it is determined that the query filter cache does not contain the query filter corresponding to the parsed structured query, dynamically generates the query filter corresponding to the parsed structured query and stores the query filter in association with the query filter cache;
executes the query filter against the subset of the tenant's set of geospatial data stored in association with the processor memory of the host machine to retrieve a first set of geospatial data index entries satisfying the query filter, wherein the first set of geospatial data index entries represents the subset of the set of geospatial data; and
uses the first set of geospatial data index entries to retrieve a second set of full geospatial data index entries from the tenant's set of geospatial data stored in association with the file system memory of the host machine, wherei

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Shinn Eugene
• Jayanti Harish
• Prateek Abhishek

Classifications

• G06F17/30241

  Physics · mapped topic

• G06F17/30312

  Physics · mapped topic

• G06F17/3087

  Physics · mapped topic

• G06F17/30867

  Physics · mapped topic

• G06F17/30457 Primary

  Physics · mapped topic