Index bindings in v10 - Using H3 for bounding box query

[vfa]

I’m trying to implement a function in TypeScript where you pass in north-east, south-west lat/lng’s and you get back all documents between the two points (i.e. a bounding box query).

I can do this in Postgres easily using the PostGIS extension, but I want to try to implement the same using Fauna to compare.

Using this as a reference (which is a great post btw), I see that it looks possible using a somewhat involved index binding in FQLv4. However, I want to use FQLv10 and do not understand how to create index bindings in v10.

Firstly, how do you create an index binding in v10 (in general)?
How do you create a value or a term in an index from a value derived from the values in a document?

Secondly, how can I create an index similar to the one in the linked forum post?
This index (from its binding) needs to allow me to query if a given h3 hash is a parent hash (or the hash itself) of an h3 hash in a document.
(say the h3 hash is at document[‘location’][‘h3’])

Thirdly, how do I write the UDF that when called (in FQLv10):
allWithParentH3(<the h3 hash>)
Would return all documents that have <the h3 hash> as one of the parent hashes.

To go from north-east, south-west lat/lng’s to an array of h3 hashes, I’m doing the following on the client side (using h3-js):

const cells = polygonToCells(
	[
	  [northEast.lat, northEast.lng],
	  [northEast.lat, southWest.lng],
	  [southWest.lat, southWest.lng],
	  [southWest.lat, northEast.lng],
	],
	resFromZoomLvl,
);
//Minimise the number of h3 hashes
const cellsCompact = compactCells(cells);

(resFromZoomLvl uses some heuristic that converts the given zoom level to an appropriate h3 resolution, ideally, I wouldn’t need to pass this in, but that’s an h3 problem, nothing to do with Fauna)

Then iterate through each hash in cellsCompact calling the allWithParentH3 UDF. I’m not sure if there’s a better way. Maybe a UDF that accepts an array of h3 hashes?

The h3 hash for the lat/lng of a document is calculated by:
latLngToCell(lat, lng, 15)

[ptpaterson]

Hello @vfa and welcome!

1. Bindings are not available in v10. Bindings will be replaced with Computed Fields defined directly on the Collections, rather than indexes. However, we’ve not launched Computed Fields yet. In the mean time, any values you want to index on must be calculated and written to the documents within your own queries.
2. Translating the h3 hash function into v10 should make it MUCH clearer. The biggest thing is that FQL v10 has bitwise operators !!

updating the Put it all together section could be done like this

let getH3parents = (h3) => {
  // Define constants
  let RMASK = 67553994410557440
  let RCLEAR = 9155818042444218367
  let PARENT_CONSTS = [
    [63050394783186944, 7],
    [58546795155816448, 63],
    [54043195528445952, 511],
    [49539595901075456, 4095],
    [45035996273704960, 32767],
    [40532396646334464, 262143],
    [36028797018963968, 2097151],
    [31525197391593472, 16777215],
    [27021597764222976, 134217727],
    [22517998136852480, 1073741823],
    [18014398509481984, 8589934591],
    [13510798882111488, 68719476735],
    [9007199254740992, 549755813887],
    [4503599627370496, 4398046511103],
    [0, 35184372088831],
  ]

  // Filter the table
  let current_res = h3 & RMASK
  let parent_consts_filtered = PARENT_CONSTS.where(c => c[0] < current_res)

  // Calculate the parent indexes
  let h3_nores = h3 & RCLEAR
  let parents = parent_consts_filtered.map(c => {
    let res = c[0]
    let fill = c[1]

    h3_nores | res | fill
  })

  parents
}

// calculate for mock document
let doc = { h3: 644722037633318912 }
getH3parents(doc.h3)

For #3, I’m not familiar with the h3-js library and respective functions polygonToCells, compactCells, etc. Does this FQL v10 lambda help you out?

[vfa]

Hi @ptpaterson, thank you for your reply!

I think it would be a good idea to say something in the docs about Computed Fields being worked on and coming soon. It’s been incredibly frustrating not knowing this because you think you don’t understand something/you’re doing something wrong.

Wow yes, that is a lot cleaner!

Okay so say the docs in my collection have this structure:

{ location: { h3: <h3 hash>, h3_parents: getH3parents(<h3 hash>) }}

How do I get all docs that have a parent h3 (h3p) contained in the h3_parents array?
(i.e. something like all((doc) => h3p in doc['location']['h3_parents])

How do I write the index for that?
I want something like FooCollection.withH3Parent(h3p)

And then what would be the best to do this query if I had an array of parent h3 hashes?

I’m thinking of some kind of UDF that takes an array of hashes and iterates through them all, calling FooCollection.withH3Parent(h3p) on each.
But maybe there’s a better way (I’m also not sure if you can write a for loop in FQL)

I would like the full query (i.e. from an array of h3 hashes to an array of documents) to be executed by Fauna if possible.

[ptpaterson]

Our docs on index definitions can be found here: Indexes definition - Fauna Documentation

In FQL v10, the indexes are defined directly on the Collection. For example,

FooCollection.definition.update({
  indexes: {
    withH3Parent: {
      terms: [
        // Note the `mva: true` option
        { field: "location.h3_parents", mva: true },
      ],
      values: [
        { field: "location.h3" },
        { field: "location.h3_parents" },
        // ref is not required to be added in FQL v10
      ],
    },
  }
})

We specify mva: true to create an index entry for every array element. In FQL v4, the Index would always create an entry for each item in the array, but you can be more specific in FQL v10.

[vfa]

Thanks so much @ptpaterson! You’ve really helped.

I created the following UDF to process an array of incoming h3 hashes:

(h3ps) => {
    h3ps.fold([], (a, h3p) => a.append(FooCollection.withH3Parent(h3p)))
}

This works, but do you have any suggestions to make the function better?
Is there a way to make fauna process each item in the list in parallel?
Is there a way to clean up the data returned? (I tried FooCollection.withH3Parent(h3p).data to parse out the returned data field but an error to do with Set was thrown)

Also is there a way to create an index with a const term value?
Say the documents in a collection have an enabled (bool) field, can you create an index that only includes documents with enabled == True?

[ptpaterson]

map, flatMap and forEach execute concurrently. Note that Write operations are not permitted in map and flatMap

Since FooCollection.withH3Parent will itself return a Set, then flatMap will probably be most appropriate, i.e. you don’t need to manually concat (append only adds a single element to an Array) results together.

(h3ps) => h3ps.flatMap(h3p => FooCollection.withH3Parent(h3p))

If h3ps is a plain array and not a Set, then call toSet() first.

(h3ps) => h3ps.toSet().flatMap(h3p => FooCollection.withH3Parent(h3p))

[vfa]

That is truly incredible, thank you so much. Fauna and FQLX are seriously amazing.