General question: Is it possible to flatten "nested documents" for faceted search?

[sabine]

I have an app where, in Elasticsearch, I have a mapping with nested documents.

So, for some table A I have a mapping

{
  'properties': {
    [..]
    'B': {
      type': 'nested',
      'properties': {
        'x': {'type': 'integer'},
        'y': {'type': 'integer'},
        'z': {'type': 'integer'},
      }
   }
}

In my database, there is a one-to-many relation from A to B, and all of x, y, and z are actually arrays. I naively translated this to Elasticsearch nested values and actually got search to work as I expected, including the ability to facet on the individual fields of B.
However, Elasticsearch does feel complicated to run in production as a solo developer and, occasionally, it crashes.

I would love to have a fast and robust in-memory search.

The queries I make need to return A records and are a conjunction of
(a) one or more filters on fields ofA
(b) one or more filters of the shape "there exists a B for which some predicate P(B) holds"

There are two different ways I need to facet on x, y, and z:
(1) facet on x, y, z of those Bs that fulfill a specific P(B), where B belongs to on an A that fulfills (a) and (b)
(2) facet on x, y, z of all Bs that belong to an A that fulfills (a) and (b).

I'm aware that Typesense likely won't have the detailed cababilities of filtering that Elasticsearch has (like arbitrary OR-queries and aggregations), and that's fine with me. The ability to interactively drill down into a dataset of around 3 million As and around 45 million Bs with good performance and low resource usage is more important for the use case than the ability to make elaborate queries.

From what I read and tried so far, it seems that Solr and Elasticsearch are the only engines that do nested faceting out of the box.

The question from my side is: Is there some reasonable way I can encode/flatten my nested data in Typesense so that I can facet on the nested fields?

If someone is aware of other engines that provide nested faceting, I'm definitely interested in learning about them, too.

[kishorenc]

@sabine Can you please post a sample document that you store in Elasticsearch? I'm having a bit of trouble wrapping my head around this one, even though I know that you've provided a lot of details here 😄 You can maybe replace A and B with some type of real-life example and query that simulates your exact use case? That would help me visualize things better.

[sabine]

Sure! It is really dense with just letters.

(The following is not the exact thing I'm dealing with, but an accurate comparison if you can suspend your disbelief that people would actually want to record, and search this information, and be able to agree on the semantics of it all.)

Let's pretend the As are real estate listings and the Bs are features of these. And we want to do some really detailed filtering on the next big real estate service.

So, let's look at some listings as they can be pulled out of the database:

h = {
  'year_constructed': 2011,
  'size_of_lot_sqm': 567,
  'number_of_bedrooms': 3,

  'features': [
    {
      'attributes': ['large', 'oval', 'deep'],
      'thing': ['pool'],
      'location': ['back', 'yard'],
    },
    {
      'attributes': ['extremely large', 'square'],
      'thing': ['living room'],
      'location': ['ground floor'],
    },
    {
      'attributes': ['spiraling', 'concrete', 'designer'],
      'thing': ['stairs'],
      'location': ['center', 'ground floor'],
    },
  ],
}

i = {
  'year_constructed': 1965,
  'size_of_lot_sqm': 1223,
  'number_of_bedrooms': 3,

  'features': [
    {
      'attributes': ['old', 'healthy'],
      'thing': ['apple tree'],
      'location': ['back' 'yard'],
    },
    {
      'attributes': ['designer'],
      'thing': ['kitchen'],
      'location': ['west', 'living room'],
    },
    {
      'attributes': ['small', 'deep', 'square', 'saltwater'],
      'thing': ['pool'],
      'location': ['basement'],
    },
  ],
}

The goal is to let the user find listings by filtering on features and by filtering on the properties of the listings themselves. On average, every listing has 15 features.

Example query:

q = houses.number_of_bedrooms == 3 AND (EXISTS f IN features. f.thing CONTAINS 'pool')

(let's assume the two listings are the results for this query)

faceting on f.attributes, f.thing, f.location for f with f.thing CONTAINS 'pool' == true on the listings that fulfill q:

attributes
----------
deep      2
small     1
square    1
saltwater 1
large     1
oval      1

thing
-----
pool      2

location
--------
basement  1
yard      1
back      1

(the UI shows which attributes/things/locations we could add to the inner query f.thing CONTAINS 'pool' and still get that number of listings as a result)

faceting on attributes, thing, location for all the fs on the listings that fulfill query q

attributes
----------
deep      2
square    2 (the pool of listing i and the living room of listing h are both square)
designer  2 (kitchen vs stairs)
concrete  1
spiraling 1
small     1
saltwater 1
large     1
oval      1
old       1
healthy   1
extremely large 1

thing
-----
pool        2
kitchen     1
living room 1
stairs      1
apple tree  1

location
--------
back         2
yard         2 (one listing has a pool in the back yard, the other one has a tree in the back yard)
center       1
ground floor 1 (only listing i has features on ground floor)
west         1
living room  1
basement     1

(the UI shows which attributes/things/locations will yield results if we add another (EXISTS f IN features. [..]) to our query)

--

While in this example the values are strings, it's fine to assume that, before indexing, another service can turn all these strings into integers, and on querying, back from integers to strings.

The number of different words being used in attributes/thing/location can be assumed to be between 2000 and 4000 each.

It seems possible that we can limit the order in which new (EXISTS f IN features. [...]) subqueries can be added, by requiring the user to first query a thing, and then drill in on that via location or attributes.

--
I have not yet done experiments on how this data model will scale in Elasticsearch (which is something I definitely need to do!). It might be that this doesn't scale well, and that I need to find a simplified representation of the data. 🤷

Edited to add: I've been making the query language up here, hope it's clear enough.

[jasonbosco]

@sabine Thank you for the detailed example. Typesense doesn't support nested fields at the moment, so you'd want to flatten the data-structure like this, to achieve what you're looking to do:

{
  "year_constructed": 2011,
  "size_of_lot_sqm": 567,
  "number_of_bedrooms": 3,
  "features.things": ["pool", "living room", "stairs"],
  "features.pool.attributes": ["large", "oval", "deep"],
  "features.pool.location": ["back", "yard"],
  "features.living_room.attributes": ["extremely large", "square"],
  "features.living_room.location":  ["ground floor"],
  "features.stairs.attributes": ["spiraling", "concrete", "designer"],
  "features.stairs.location":  ["center", "ground floor"]
}

Then a query like this:

q = houses.number_of_bedrooms == 3 AND (EXISTS f IN features. f.thing CONTAINS 'pool')

would translate in Typesense to:

{
  "filter_by": "number_of_bedrooms:3 && features.things:=[pool]",
  "facet_by": "features.things,features.pool.attributes,features.pool.location,features.living_room.attributes,features.living_room.location,features.stairs.attributes,features.stairs.location"
}

Does that work?

[sabine]

Ok, that's interesting, thanks!

If I understand https://typesense.org/docs/0.19.0/api/collections.html#create-a-collection correctly, I will need to set up a collection like this

{
         "name": "listings",
         "fields": [
           {"name": "year_constructed", "type": "int32" },
           {"name": "size_of_lot_sqm", "type": "int32" },
           {"name": "number_of_bedrooms", "type": "int32" },

           {"name": "features.things", "type": "string[]", "facet": true },
           {"name": "features.pool.attributes", "type": "string[]", "facet": true },
           {"name": "features.pool.location", "type": "string[]", "facet": true },
           {"name": "features.living_room.attributes", "type": "string[]", "facet": true },
           {"name": "features.living_room.location", "type": "string[]", "facet": true },
           {"name": "features.stairs.attributes", "type": "string[]", "facet": true },
           {"name": "features.stairs.location", "type": "string[]", "facet": true },

           [.. and all the other features attributes/location lists for the possible values for things ..]
         ],
         "default_sorting_field": "num_employees"
       }

which means that all the words for things need to be known up-front, and whenever new ones are added, one must declare a new collection (that declares all the fields that faceting needs to work for) and reindex all data.

The approach looks like it can work for this usecase. I'm going to try that and benchmark some, with different amounts of things. 👍

[jasonbosco]

Correct, that's the schema you'd use as of v0.19.

In v0.20 (not yet publicly released), we've added support for regex field names, so you could use a schema like this:

{
  "name": "listings",
  "fields": [
    {"name": "year_constructed", "type": "int32" },
    {"name": "size_of_lot_sqm", "type": "int32" },
    {"name": "number_of_bedrooms", "type": "int32" },

    {"name": "features.things", "type": "string[]", "facet": true },
    {"name": 'features\..*\.attributes', "type": "string[]", "facet": true },
    {"name": 'features\..*\.location', "type": "string[]", "facet": true }
  ]
}

So new attributes you add will automatically be indexed, and you don't have re-index each time.

If you want to try it out, here's an RC build:

docker run -p 8108:8108 -v/tmp/typesense-data:/data typesense/typesense:0.20.0.rc31 --data-dir /data --api-key=xyz

[sabine]

Been playing around with 0.19. I very much love that this has been as simple as installing the .deb package and starting typesense and importing some data from jsonl via curl. Due to your laser-focus on making something that is simple yet powerful and easy to deploy, getting Typesense up and running and doing some things with it was super quick.

Things I've observed:

1. it's helpful on 0.19 to declare the features.[thing].attributes fields as optional: true. Then, I don't need to pad the documents to provide all these keys even if there are no values present. This significantly decreased the time needed to index documents. I've been indexing documents via curl from jsonl files.

2. On my development machine in basic experiments
   (with a wildcard query: faceting and filtering on features.things, features.[thing].attributes, features.[thing].location, with max_facet_values set so high that Typesense always returns all facets, and sorting by the default sort order)
   I see that the more filters I add, the faster Typesense responds. That's great, as this suggests that I could cache all the heavy queries (that have few filters) and then enjoy stellar response times serving many concurrent users on little resources as these users drill down into the dataset.

However, on the 32-million songs instant search at https://songs-search.typesense.org/, the response time seems to increase every time another filter is added. Which is the exact opposite behavior in terms of performance.

Why is the 32-million songs search getting slower with every added filter? Is this because the results are being ranked instead of returning results in the default order?

[kishorenc]

Why is the 32-million songs search getting slower with every added filter?

The reason is because of the query. A wildcard query is much simpler than a keyword query that the song search demo uses. For a given query, there are options that allow you to specify whether Typesense should drop tokens in the query and/or do typo correction to try and surface more results (check the typo_tokens_threshold and drop_tokens_threshold). The demo sets these thresholds, and so when more and more filters are added, it gets harder and harder for Typesense to locate enough records to satisfy these thresholds, so it needs to do more and more searches (e.g. dropping more tokens, looking for 2-char typos after exhausting 1-char typos) etc. This comes with additional performance impact.

[sabine]

Makes sense.

I'm more and more impressed by how many things Typesense can actually do out of the box.

Hope you folks are making good money or soon enough will be making good money off this.

Closing this now and very much looking forward to add my site to the showcase when it's ready for that. 🙂