Range queries in Impala

[#1]

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.

[#2]

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.

[#3 · Accepted solution]

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