xref: /dokuwiki/inc/Search/concept.txt (revision f2bbffb509f37291c31c023167b8aeb383079d6d)

====== Search Indexing ======

This document is meant to describe the various concepts behind the indexing mechanism. It's work in progress and will be moved to the wiki once the new index code is merged.

===== Uses =====

The indexing mechanism is meant to make information that is normally distributed over several locations (eg. words on pages) available through a central, faster mechanism. The primary goal is to cover fulltext search, but it is also used for other things like page meta data and possibly more in the future.

===== Collections =====

A collection describes how data is aggregated into multiple indexes to make it accessible for a specific use case. Eg. fulltext search for page contents is a usecase covered by a collection.

Please note: because index has a specific meaning in our context (see below) you should avoid using that word, when you're actually talking about a collection. There is no "fulltext index" - that functionality is only achieved by using multiple indexes in a collection.

Collections have two independent properties:

=== Collection Types ===

The collection type determines how tokens relate to entities:

  * frequency collections - The same token can appear multiple times in the same entity and searches are usually interested in the number of times it appears. This is the words on pages use case.
  * lookup collections - Basically the same as frequency collections, but each token appears only once per entity thus all frequencies are 1. Searches do not care for the frequency but are only interested if a token appears for the entity or not. Internally the same mechanisms are used; only the way tokens are processed on input differs (deduplication instead of counting).
  * direct collections - Here a 1:1 relation between the entity and a token exists. For example a page has exactly one title.

=== Index File Splitting ===

Independently of the collection type, a collection can use split or non-split token indexes. When split, the token and frequency indexes are distributed across multiple files based on token length. This also affects the reverse index format (see below). Any collection type can use either mode.

=== Indexes ===

A collection works on four indexes:

  * entity - This is the main entity that will be the result of a search. Eg. a page
  * token - This is the actual information strewn across the entities. Eg. words
    * can be split into several files based on token length (see Index File Splitting below)
  * frequency - This maps tokens to entities and records their frequency. Eg. freq(words)->page
    * if tokens are split into several files, this is too
  * reverse - This records which tokens are assigned to a specific entity. This is used for updating: when an entity is re-indexed, the old reverse record provides the list of tokens to clean up. The format depends on whether the collection uses split indexes or not.

The latter two index files do not exist for direct collections

Collections can be searched for one or more ''terms'' via a CollectionSearch class. In the most simple case a term is a single token. But it is also possible to use wildcards signifiers ''*'' at the start and end of a term. In that case, the term refers to a list of tokens. A CollectionSearch will return the frequency with which each term occurs on each entity.

==== List of Collections =====

^ Name                   ^ Type      ^ Split? ^ Entity ^ Token                 ^ Frequency             ^ Reverse               ^
| FullText               | frequency | yes    | page   | w*                    | i*                    | pageword              |
| MetaRelationMedia      | lookup    | no     | page   | relation_media_w      | relation_media_i      | relation_media_p      |
| MetaRelationReferences | lookup    | no     | page   | relation_references_w | relation_references_i | relation_references_p |




==== Terms ====

A ''Term'' is a representation of a single search query component that can match one or more tokens in an index. The Term class is used by CollectionSearch implementations to handle wildcard searches and track which entities contain matching tokens.

**Wildcard Support:**

Terms can include wildcards using the ''*'' character:
  * ''wiki'' - matches exactly "wiki"
  * ''wiki*'' - matches tokens starting with "wiki" (e.g., "wiki", "wikitext", "wikipedia")
  * ''*wiki'' - matches tokens ending with "wiki" (e.g., "wiki", "dokuwiki")
  * ''*wiki*'' - matches tokens containing "wiki" anywhere (e.g., "wiki", "dokuwiki", "wikitext")

The Term class internally handles these wildcards by:
  * Storing the original term with wildcards
  * Extracting the base term (without wildcard characters)
  * Converting wildcards into a regular expression pattern for matching
  * Tracking which type of wildcard is used (none, start, end, or both)

**Length-Based Organization:**

Terms organize their matching tokens by length. This is crucial for working with split indexes:
  * A term like ''*wiki*'' might match 4-letter words (wiki), 8-letter words (dokuwiki), and 9-letter words (wikilinks) but never 3-letter words, because the base term "wiki" is 4 letters long.
  * Each length group can be looked up in the corresponding suffixed token index
  * This allows efficient searching across split indexes without loading irrelevant files

**Token and Frequency Tracking:**

During a search operation, Terms:
  1. Collect all token IDs that match the term pattern (organized by token length)
  2. Look up which entities contain those tokens
  3. Aggregate the frequencies across all matching tokens
  4. Map entity IDs to entity names for the final result

For example, searching for ''wiki*'' might find:
  * Token "wiki" (ID 42) appears 5 times on page "start" (ID 10)
  * Token "wikitext" (ID 87) appears 3 times on page "start" (ID 10)
  * Term result: "start" matches with total frequency 8

**Validation:**

Terms are validated on creation:
  * Minimum length requirements are enforced (except for numeric terms)
  * Terms that are too short throw a SearchException
  * The base term (without wildcards) must meet the minimum token length configured in the Tokenizer

===== Indexes ======

Indexes refer to individual index files that store one kind of information. E.g. a list of all page names or a list of page-word frequencies.

Indexes are row based. The line number is important information of the index. The lines are counted from zero and referred to as ''rid'' in the code.

Index files can be accessed through two classes:

  * \dokuwiki\Search\Index\FileIndex
  * \dokuwiki\Search\Index\MemoryIndex

Both classes expose the same API, the only difference is their way of accessing the data.

A FileIndex will read through the index file line-by-line without ever loading the full file into memory. Each modification will directly write back to the index.

The MemoryIndex loads the whole file into an internal array. Changes are only written back when explicitly calling the ''save()'' method. A memory index is faster but requires more memory.

Which method to use depends mostly on the size of the file.

Usually indexes are not accessed directly but through a collection. That collection will manage which type of access to use.

Within an index two kinds of data can be stored per row:

  * A single value. Eg. an entity or a token
  * A list of tuples. Eg. a list of pageIDs and frequencies

The former is straight forward, it's a simple ''rid -> value'' store.  The latter maps to ''rid -> [key -> value, ...]'' where key is usally the ''rid'' in another index.

==== Index Types ====

A Collection consists of 4 (or 2 for direct collections) index types:

The **entity** index lists the main entity the index will return as a result. entity.RID -> entity

The **token** index contains the tokens used to search (eg. words). token.RID -> token

The **frequency** index contains tuples of entity.RIDs and usage frequencies. token.RID -> entity.RID*frequency:...

The **reverse** index records which tokens are assigned to each entity. Its format depends on whether the collection uses split indexes:

  * **Split collections**: Each entry is a ''tokenLength*tokenId'' pair because the token length is needed to locate the correct split index file. Format: ''tokenLength*tokenId:tokenLength*tokenId:...''
  * **Non-split collections**: Only the token ID is needed since all tokens live in a single file. Format: ''tokenId:tokenId:...''

The reverse index does not store frequencies. It is used internally when updating an entity: the old reverse record provides the set of previously assigned tokens so they can be cleaned up (see the addEntity description in the Collection Types section above).

Direct collections only use entity and token index files with entity.RID === token.RID


==== Index File Splitting ====

To improve memory efficiency and access speed, a collection can split its token and frequency indexes into multiple physical files using suffixes based on token length. This is configured per collection and is independent of the collection type (frequency or lookup).

When splitting is enabled, both the token index and the frequency index are distributed across files. A suffix parameter is appended to the base index name to create the actual filename. For example:

  * Base name: ''w'' (for word tokens)
  * Suffix: ''3'' (for 3-letter tokens)
  * Resulting file: ''w3.idx''

In a fulltext collection with splitting enabled:

  * ''w3.idx'' / ''i3.idx'' - stores all 3-letter tokens and their frequencies
  * ''w4.idx'' / ''i4.idx'' - stores all 4-letter tokens and their frequencies
  * ''w5.idx'' / ''i5.idx'' - stores all 5-letter tokens and their frequencies
  * and so on...

When splitting is disabled, a single file is used for each index (eg. ''relation_media_w.idx'').

When an index uses suffixes, the ''max()'' method can be used to find the highest numeric suffix currently in use. This is useful for operations that need to iterate over all splits of an index (eg. when a Term is using a wildcard).

==== Tuple Data Format ====

Tuple-based index rows store associations between keys (typically RIDs from another index) and numeric values (typically frequency counts). The internal format uses a compact string representation:

<code>
key*count:key*count:key*count
</code>

Where:
  * ''key'' - Usually the RID from another index (e.g., a page ID)
  * ''count'' - A numeric value (e.g., how many times a word appears on that page)
  * '':'' - Separates individual tuples
  * ''*'' - Separates the key from its count within a tuple

**Example:** A frequency index row for a word might look like:
<code>
42*5:17*3:98*12
</code>

This means:
  * Entity with RID 42 contains this word 5 times
  * Entity with RID 17 contains this word 3 times
  * Entity with RID 98 contains this word 12 times

Frequencies of 1 are not stored in the index. For example:

<code>
42*5:17:98
</code>

In the above case would be interpreted as

  * Entity with RID 42 contains this word 5 times
  * Entity with RID 17 contains this word 1 times
  * Entity with RID 98 contains this word 1 times

The ''TupleOps'' class provides utility methods for working with tuple records:
  * ''updateTuple()'' - Insert or update a specific key->count pair
  * ''parseTuples()'' - Parse a record into an array of key->count associations
  * ''aggregateTupleCounts()'' - Sum all counts in a record

===== Locking =====

Only one process may write to an index at any time. To ensure this, a locking mechanism has to be employed.

Indexes can be read in write or readonly mode according to the acquired locks. However, managing locks has to be done outside the index. Usually within a collection.

The ''Lock'' class is used to acquire the needed locks.