Support Questions
Find answers, ask questions, and share your expertise
Announcements
Alert: Welcome to the Unified Cloudera Community. Former HCC members be sure to read and learn how to activate your account here.

Range queries in Impala

Solved Go to solution
Highlighted

Range queries in Impala

New Contributor

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.

1 ACCEPTED SOLUTION

Accepted Solutions

Re: Range queries in Impala

Master Collaborator

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

 

 

2 REPLIES 2

Re: Range queries in Impala

New Contributor

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

Master Collaborator

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