1596d5287SAndreas Gohr====== Search Indexing ====== 2596d5287SAndreas Gohr 38ae94493SAndreas GohrThis 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. 4596d5287SAndreas Gohr 5596d5287SAndreas Gohr===== Uses ===== 6596d5287SAndreas Gohr 7596d5287SAndreas GohrThe 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. 8596d5287SAndreas Gohr 9596d5287SAndreas Gohr===== Collections ===== 10596d5287SAndreas Gohr 11596d5287SAndreas GohrA 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. 12596d5287SAndreas Gohr 13596d5287SAndreas GohrPlease 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. 14596d5287SAndreas Gohr 15596d5287SAndreas GohrThere are basically two different complexities of collections 16596d5287SAndreas Gohr 17596d5287SAndreas Gohr * 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. 188ae94493SAndreas Gohr * lookup collections - Basically the same as frequency collection, 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 198ae94493SAndreas Gohr * direct collections - Here a 1:1 relation between the entity and a token exists. For example a page has exactly one title. 20596d5287SAndreas Gohr 21596d5287SAndreas GohrA collection works on four indexes: 22596d5287SAndreas Gohr 23596d5287SAndreas Gohr * entity - This is the main entity that will be the result of a search. Eg. a page 24596d5287SAndreas Gohr * token - This is the actual information strewn across the entities. Eg. words 258ae94493SAndreas Gohr * can be split into several files (usally based on token length) 26596d5287SAndreas Gohr * frequency - This maps tokens to entities and records their frequency. Eg. freq(words)->page 278ae94493SAndreas Gohr * if tokens are split into several files, this is too 28596d5287SAndreas Gohr * reverse - This records which tokens are on a specific entities. This is mostly used for internal index cleanup. Eg. page-words 29596d5287SAndreas Gohr 308ae94493SAndreas GohrThe latter two index files do not exist for direct collections 31596d5287SAndreas Gohr 32596d5287SAndreas GohrCollections 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. 33596d5287SAndreas Gohr 348ae94493SAndreas Gohr==== List of Collections ===== 358ae94493SAndreas Gohr 368ae94493SAndreas Gohr^ Name ^ Entity ^ Token ^ Frequency ^ Reverse ^ Uses split Tokens? ^ 378ae94493SAndreas Gohr| FullText | page | w* | i* | pageword | yes | 388ae94493SAndreas Gohr| MetaRelationMedia | page | relation_media_w | relation_media_i | relation_media_p | no | 398ae94493SAndreas Gohr| MetaRelationReferences | page | relation_references_w | relation_references_i | relation_references_p | no | 408ae94493SAndreas Gohr 418ae94493SAndreas Gohr 428ae94493SAndreas Gohr 438ae94493SAndreas Gohr 448ae94493SAndreas Gohr==== Terms ==== 458ae94493SAndreas Gohr 468ae94493SAndreas GohrA ''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. 478ae94493SAndreas Gohr 488ae94493SAndreas Gohr**Wildcard Support:** 498ae94493SAndreas Gohr 508ae94493SAndreas GohrTerms can include wildcards using the ''*'' character: 518ae94493SAndreas Gohr * ''wiki'' - matches exactly "wiki" 528ae94493SAndreas Gohr * ''wiki*'' - matches tokens starting with "wiki" (e.g., "wiki", "wikitext", "wikipedia") 538ae94493SAndreas Gohr * ''*wiki'' - matches tokens ending with "wiki" (e.g., "wiki", "dokuwiki") 548ae94493SAndreas Gohr * ''*wiki*'' - matches tokens containing "wiki" anywhere (e.g., "wiki", "dokuwiki", "wikitext") 558ae94493SAndreas Gohr 568ae94493SAndreas GohrThe Term class internally handles these wildcards by: 578ae94493SAndreas Gohr * Storing the original term with wildcards 588ae94493SAndreas Gohr * Extracting the base term (without wildcard characters) 598ae94493SAndreas Gohr * Converting wildcards into a regular expression pattern for matching 608ae94493SAndreas Gohr * Tracking which type of wildcard is used (none, start, end, or both) 618ae94493SAndreas Gohr 628ae94493SAndreas Gohr**Length-Based Organization:** 638ae94493SAndreas Gohr 648ae94493SAndreas GohrTerms organize their matching tokens by length. This is crucial for working with split indexes: 65*7f394dd6SAndreas Gohr * 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. 668ae94493SAndreas Gohr * Each length group can be looked up in the corresponding suffixed token index 678ae94493SAndreas Gohr * This allows efficient searching across split indexes without loading irrelevant files 688ae94493SAndreas Gohr 698ae94493SAndreas Gohr**Token and Frequency Tracking:** 708ae94493SAndreas Gohr 718ae94493SAndreas GohrDuring a search operation, Terms: 728ae94493SAndreas Gohr 1. Collect all token IDs that match the term pattern (organized by token length) 738ae94493SAndreas Gohr 2. Look up which entities contain those tokens 748ae94493SAndreas Gohr 3. Aggregate the frequencies across all matching tokens 758ae94493SAndreas Gohr 4. Map entity IDs to entity names for the final result 768ae94493SAndreas Gohr 778ae94493SAndreas GohrFor example, searching for ''wiki*'' might find: 788ae94493SAndreas Gohr * Token "wiki" (ID 42) appears 5 times on page "start" (ID 10) 798ae94493SAndreas Gohr * Token "wikitext" (ID 87) appears 3 times on page "start" (ID 10) 808ae94493SAndreas Gohr * Term result: "start" matches with total frequency 8 818ae94493SAndreas Gohr 828ae94493SAndreas Gohr**Validation:** 838ae94493SAndreas Gohr 848ae94493SAndreas GohrTerms are validated on creation: 858ae94493SAndreas Gohr * Minimum length requirements are enforced (except for numeric terms) 868ae94493SAndreas Gohr * Terms that are too short throw a SearchException 878ae94493SAndreas Gohr * The base term (without wildcards) must meet the minimum token length configured in the Tokenizer 88596d5287SAndreas Gohr 89596d5287SAndreas Gohr===== Indexes ====== 90596d5287SAndreas Gohr 91596d5287SAndreas GohrIndexes 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. 92596d5287SAndreas Gohr 93596d5287SAndreas GohrIndexes 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. 94596d5287SAndreas Gohr 95596d5287SAndreas GohrIndex files can be accessed through two classes: 96596d5287SAndreas Gohr 97596d5287SAndreas Gohr * \dokuwiki\Search\Index\FileIndex 98596d5287SAndreas Gohr * \dokuwiki\Search\Index\MemoryIndex 99596d5287SAndreas Gohr 100596d5287SAndreas GohrBoth classes expose the same API, the only difference is their way of accessing the data. 101596d5287SAndreas Gohr 102596d5287SAndreas GohrA 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. 103596d5287SAndreas Gohr 104596d5287SAndreas GohrThe 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. 105596d5287SAndreas Gohr 106596d5287SAndreas GohrWhich method to use depends mostly on the size of the file. 107596d5287SAndreas Gohr 108596d5287SAndreas GohrUsually indexes are not accessed directly but through a collection. That collection will manage which type of access to use. 109596d5287SAndreas Gohr 110596d5287SAndreas GohrWithin an index two kinds of data can be stored per row: 111596d5287SAndreas Gohr 112596d5287SAndreas Gohr * A single value. Eg. an entity or a token 113596d5287SAndreas Gohr * A list of tuples. Eg. a list of pageIDs and frequencies 114596d5287SAndreas Gohr 115596d5287SAndreas GohrThe 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. 116596d5287SAndreas Gohr 1178ae94493SAndreas Gohr==== Index Types ==== 1188ae94493SAndreas Gohr 1198ae94493SAndreas GohrA Collection consists of 4 (or 2 for direct collections) index types: 1208ae94493SAndreas Gohr 1218ae94493SAndreas GohrThe **entity** index lists the main entity the index will return as a result. entity.RID -> entity 1228ae94493SAndreas Gohr 1238ae94493SAndreas GohrThe **token** index contains the tokens used to search (eg. words). token.RID -> token 1248ae94493SAndreas Gohr 1258ae94493SAndreas GohrThe **frequency** index contains tuples of entity.RIDs and usage frequencies. token.RID -> entity.RID*frequency:... 1268ae94493SAndreas Gohr 1278ae94493SAndreas GohrThe **reverse** index contains tuples of token.RIDs and usage frequencies. entity.RID -> token.RID*frequency:... 1288ae94493SAndreas Gohr 1298ae94493SAndreas GohrDirect collections only use entity and token index files with entity.RID === token.RID 1308ae94493SAndreas Gohr 1318ae94493SAndreas Gohr 1328ae94493SAndreas Gohr==== Index File Splitting ==== 1338ae94493SAndreas Gohr 1348ae94493SAndreas GohrTo improve memory efficiency and access speed, a single token index can be split into multiple physical files using suffixes. This is particularly useful for indexes that would otherwise grow too large to handle efficiently. 1358ae94493SAndreas Gohr 1368ae94493SAndreas GohrWhen creating an index, you can specify a suffix parameter that gets appended to the base index name to create the actual filename. For example: 1378ae94493SAndreas Gohr 1388ae94493SAndreas Gohr * Base name: ''w'' (for word tokens) 1398ae94493SAndreas Gohr * Suffix: ''3'' (for 3-letter words) 1408ae94493SAndreas Gohr * Resulting file: ''w3.idx'' 1418ae94493SAndreas Gohr 1428ae94493SAndreas GohrA common use case is splitting token indexes by word length. In a fulltext collection: 1438ae94493SAndreas Gohr 1448ae94493SAndreas Gohr * ''w3.idx'' - stores all 3-letter words 1458ae94493SAndreas Gohr * ''w4.idx'' - stores all 4-letter words 1468ae94493SAndreas Gohr * ''w5.idx'' - stores all 5-letter words 1478ae94493SAndreas Gohr * and so on... 1488ae94493SAndreas Gohr 1498ae94493SAndreas GohrWhen 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). 1508ae94493SAndreas Gohr 1518ae94493SAndreas Gohr==== Tuple Data Format ==== 1528ae94493SAndreas Gohr 1538ae94493SAndreas GohrTuple-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: 1548ae94493SAndreas Gohr 1558ae94493SAndreas Gohr<code> 1568ae94493SAndreas Gohrkey*count:key*count:key*count 1578ae94493SAndreas Gohr</code> 1588ae94493SAndreas Gohr 1598ae94493SAndreas GohrWhere: 1608ae94493SAndreas Gohr * ''key'' - Usually the RID from another index (e.g., a page ID) 1618ae94493SAndreas Gohr * ''count'' - A numeric value (e.g., how many times a word appears on that page) 1628ae94493SAndreas Gohr * '':'' - Separates individual tuples 1638ae94493SAndreas Gohr * ''*'' - Separates the key from its count within a tuple 1648ae94493SAndreas Gohr 1658ae94493SAndreas Gohr**Example:** A frequency index row for a word might look like: 1668ae94493SAndreas Gohr<code> 1678ae94493SAndreas Gohr42*5:17*3:98*12 1688ae94493SAndreas Gohr</code> 1698ae94493SAndreas Gohr 1708ae94493SAndreas GohrThis means: 1718ae94493SAndreas Gohr * Entity with RID 42 contains this word 5 times 1728ae94493SAndreas Gohr * Entity with RID 17 contains this word 3 times 1738ae94493SAndreas Gohr * Entity with RID 98 contains this word 12 times 1748ae94493SAndreas Gohr 1758ae94493SAndreas GohrFrequencies of 1 are not stored in the index. For example: 1768ae94493SAndreas Gohr 1778ae94493SAndreas Gohr<code> 1788ae94493SAndreas Gohr42*5:17:98 1798ae94493SAndreas Gohr</code> 1808ae94493SAndreas Gohr 1818ae94493SAndreas GohrIn the above case would be interpreted as 1828ae94493SAndreas Gohr 1838ae94493SAndreas Gohr * Entity with RID 42 contains this word 5 times 1848ae94493SAndreas Gohr * Entity with RID 17 contains this word 1 times 1858ae94493SAndreas Gohr * Entity with RID 98 contains this word 1 times 1868ae94493SAndreas Gohr 1878ae94493SAndreas GohrThe ''TupleOps'' class provides utility methods for working with tuple records: 1888ae94493SAndreas Gohr * ''updateTuple()'' - Insert or update a specific key->count pair 1898ae94493SAndreas Gohr * ''parseTuples()'' - Parse a record into an array of key->count associations 1908ae94493SAndreas Gohr * ''aggregateTupleCounts()'' - Sum all counts in a record 1918ae94493SAndreas Gohr 192596d5287SAndreas Gohr===== Locking ===== 193596d5287SAndreas Gohr 194596d5287SAndreas GohrOnly one process may write to an index at any time. To ensure this, a locking mechanism has to be employed. 195596d5287SAndreas Gohr 196596d5287SAndreas GohrIndexes 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. 197596d5287SAndreas Gohr 198596d5287SAndreas GohrThe ''Lock'' class is used to acquire the needed locks. 199