Introduction

Copy Markdown

Refine is an Elixir library for implementing fast faceted search.

Features

  • Fast faceted search - Search performance comparable to established faceted search solutions.
  • Works with existing queries – Faceted search can be applied to existing Ecto queries.
  • Flexible configuration – Facet values and labels can be extracted from source data, including scalar values, arrays, and JSON objects. Source data can also be read from joined tables.
  • Backend for frontend - All data required to build facet form inputs can be stored in the facets table.
  • Simplicity - Provide faceted search as a simple add-on to your existing database, without requiring Docker, an external search service, or a paid search provider.

Motivation

Faceted search is a common feature in data-heavy web applications such as ecommerce sites and catalogs. By offering multi-select filters such as categories and price ranges, users can quickly narrow results to find the most relevant items.

Implementing faceted search, however, quickly runs into computationally expensive filter counts. A standard PostgreSQL setup is not well suited for this workload ↓.

Search engines such as Apache Lucene, Solr, and Elasticsearch solve this problem using bitmaps ↓. For each facet option, matching records are represented as sets of integers. Facets aggregation can then be performed efficiently using bitwise operations.

Refine brings this same approach to Elixir, enabling fast faceted search for PostgreSQL-backed applications.

Implementation

Refine implements bitmaps using the PostgreSQL extension pg_roaringbitmap ➚. The bitmaps are stored in a sibling facets table, alongside facet option values and labels.

Changes to the source table (or joined tables) are tracked in a sibling facets_deltas table, which is automatically generated.

Requirements

  • Elixir
  • PostgreSQL
  • PostgreSQL extension pg_roaringbitmap - see Installation

Notes

Facet calculations

To collect all available facet options for a search query, all rows matching the query must be processed (not just the paginated results). In addition, this aggregation must be repeated for each facet that has an active selection, excluding that facet's selected options from the query. So both the table size and the number of facets contribute to the high cost of faceted search queries.

Solutions that rely on PostgreSQL ts_stat ➚ do not scale well once the table exceeds 10,000 rows.

Bitmaps

A bitmap is a sequence of bits. A bit value of 1 at a position n indicates that an object with sequence value n is active. A large bitmap with many zeroes can consume a lot of unnecessary space. To address memory issues, compressed Roaring bitmaps ➚ were created.