Skip to content

Instantly share code, notes, and snippets.

@zslayton
Last active February 28, 2023 15:57
Show Gist options
  • Save zslayton/0d876024618c81f911b0cfc676c44549 to your computer and use it in GitHub Desktop.
Save zslayton/0d876024618c81f911b0cfc676c44549 to your computer and use it in GitHub Desktop.
`isRelevant` and `nextJumpIn`

Blog post: https://aws.amazon.com/blogs/database/z-order-indexing-for-multifaceted-queries-in-amazon-dynamodb-part-1/

Original question: http://disq.us/p/2t9jcp5

All examples are pseudocode.

Imagine that you have a method called from_z_address that will take a Z-address and give you back the dimensions you used to create it in the first place.

z_address = to_z_address(x, y)
(x, y) = from_z_address(z_address)

The is_relevant method would look something like this:

def is_relevant(query_min_z_address,
                query_max_z_address,
                z_address_to_test):
   (min_x, min_y) = from_z_address(query_min_z_address)
   (max_x, max_y) = from_z_address(query_max_z_address)
   (test_x, test_y) = from_z_address(z_address_to_test)
   # Make sure that each of the test address's dimensions are within the min/max's respective dimensions
   return (test_x >= min_x 
           && test_x <= max_x
           && test_y >= min_y
           && test_y <= max_y)

A fully optimized implementation would achieve the same effect by examining the bits of the z-addresses in-place, without the intermediate step of converting them back to the individual dimensions.

The implementation of next_jump_in is much more complex. It goes by different names in academic papers that discuss it (nextJumpIn, BIGMIN, GetNextZAddress, etc), and none of the papers make it very easy to digest. I believe I used the description found on page 267 (section 4.2) of Integrating the UB-Tree into a Database System Kernel when I was running my benchmarks for the blog post.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment