Fast Query Processing by Distributing an Index over CPU Caches

Details Fast Query Processing by Distributing an Index over CPU Caches Fast Query Processing by Distributing an Index over CPU Caches

2004-10-25

arxiv.org/abs/cs/0410066v2

Computer Science

Distributed, Parallel, and Cluster Computing

New version published at IEEE Cluster Computing 2005

Scientific paper

Data intensive applications on clusters often require requests quickly be sent to the node managing the desired data. In many applications, one must look through a sorted tree structure to determine the responsible node for accessing or storing the data. Examples include object tracking in sensor networks, packet routing over the internet, request processing in publish-subscribe middleware, and query processing in database systems. When the tree structure is larger than the CPU cache, the standard implementation potentially incurs many cache misses for each lookup; one cache miss at each successive level of the tree. As the CPU-RAM gap grows, this performance degradation will only become worse in the future. We propose a solution that takes advantage of the growing speed of local area networks for clusters. We split the sorted tree structure among the nodes of the cluster. We assume that the structure will fit inside the aggregation of the CPU caches of the entire cluster. We then send a word over the network (as part of a larger packet containing other words) in order to examine the tree structure in another node's CPU cache. We show that this is often faster than the standard solution, which locally incurs multiple cache misses while accessing each successive level of the tree.

Affiliated with

Also associated with

No associations

Rating

Fast Query Processing by Distributing an Index over CPU Caches does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast Query Processing by Distributing an Index over CPU Caches, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Query Processing by Distributing an Index over CPU Caches will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-498127