question Re: Range queries in Impala in Archives of Support Questions (Read Only)

Range queries in Impala

MickeyMouse — Fri, 16 Sep 2022 09:19:19 GMT

Greetings. Is there an efficient way to do range queries in Impala? For example, I have a column called latitude of type Double. I'd like to find all rows whose latitude is between the range x-5 and x+5, where x is a double. I can scan all rows, but that's O(n). Is there a more efficient way, one that can give results in real-time with a billion rows? Thanks.

Re: Range queries in Impala

MickeyMouse — Fri, 16 Jan 2015 18:48:28 GMT

Hi, I'd like to make the question more specific. Here's my use-case:

I have to store a huge number of latitute (lat) and longitude (long) values. And i have to find the nearest lats and longs to a given lat-long. Is there an efficient way to do this in Impala? Thanks.

Re: Range queries in Impala

alex.behm — Sat, 31 Jan 2015 00:51:58 GMT

Hi MickeyMouse,

my understanding is that you are looking to answer k-neirest neighbour (kNN) queries, i.e., given a query lat/long, find the k nearest lat/long in the dataset.

You'd be able to answer such queries in Impala by tranforming the kNN query into a swries of range queries (keep increasing the range until you've found at least k answers).

One way to make the range queries effficient could be to partition your table based on lat and/or long. Of course, there are many distinct lat/long values, so you'd probably need to create buckets in the space of lat/long values (e.g. a grid structure). Then you'd need to transform the original lat/long values given in the query into the grid space. This way Impala's partition pruning will ick in and you'd be restricted to searcing data in those grid cells that overlap with the specified range. Just a high-level idea, hope it makes sense.

I'm afraid there is no easy and efficient wayto directly answer kNN queries in Impala today.

Alex