# LWS Full Text Search ## Introduction  The general approach is to scan one or more UTF-8 input text "files" (they may only exist in memory) and create an in-memory optimized trie for every token in the file. This can then be serialized out to disk in the form of a single index file (no matter how many input files were involved or how large they were). The implementation is designed to be modest on memory and cpu for both index creation and querying, and suitable for weak machines with some kind of random access storage. For searching only memory to hold results is required, the actual searches and autocomplete suggestions are done very rapidly by seeking around structures in the on-disk index file. Function|Related Link ---|--- Public API|[include/libwebsockets/lws-fts.h](https://libwebsockets.org/git/libwebsockets/tree/include/libwebsockets/lws-fts.h) CI test app|[minimal-examples/api-tests/api-test-fts](https://libwebsockets.org/git/libwebsockets/tree/minimal-examples/api-tests/api-test-fts) Demo minimal example|[minimal-examples/http-server/minimal-http-server-fulltext-search](https://libwebsockets.org/git/libwebsockets/tree/minimal-examples/http-server/minimal-http-server-fulltext-search) Live Demo|[https://libwebsockets.org/ftsdemo/](https://libwebsockets.org/ftsdemo/) ## Query API overview Searching returns a potentially very large lwsac allocated object, with contents and max size controlled by the members of a struct lws_fts_search_params passed to the search function. Three kinds of result are possible: ### Autocomplete suggestions These are useful to provide lists of extant results in realtime as the user types characters that constrain the search. So if the user has typed 'len', any hits for 'len' itself are reported along with 'length', and whatever else is in the index beginning 'len'.. The results are selected using and are accompanied by an aggregated count of results down that path, and the results so the "most likely" results already measured by potential hits appear first. These results are in a linked-list headed by `result.autocomplete_head` and each is in a `struct lws_fts_result_autocomplete`. They're enabled in the search results by giving the flag `LWSFTS_F_QUERY_AUTOCOMPLETE` in the search parameter flags. ### Filepath results Simply a list of input files containing the search term with some statistics, one file is mentioned in a `struct lws_fts_result_filepath` result struct. This would be useful for creating a selection UI to "drill down" to individual files when there are many with matches. This is enabled by the `LWSFTS_F_QUERY_FILES` search flag. ### Filepath and line results Same as the file path list, but for each filepath, information on the line numbers and input file offset where the line starts are provided. This is enabled by `LWSFTS_F_QUERY_FILE_LINES`... if you additionally give `LWSFTS_F_QUERY_QUOTE_LINE` flag then the contents of each hit line from the input file are also provided. ## Result format inside the lwsac A `struct lws_fts_result` at the start of the lwsac contains heads for linked- lists of autocomplete and filepath results inside the lwsac. For autocomplete suggestions, the string itself is immediately after the `struct lws_fts_result_autocomplete` in memory. For filepath results, after each `struct lws_fts_result_filepath` is - match information depending on the flags given to the search - the filepath string You can always skip the line number table to get the filepath string by adding .matches_length to the address of the byte after the struct. The matches information is either - 0 bytes per match - 2x int32_t per match (8 bytes) if `LWSFTS_F_QUERY_FILE_LINES` given... the first is the native-endian line number of the match, the second is the byte offset in the original file where that line starts - 2 x int32_t as above plus a const char * if `LWSFTS_F_QUERY_QUOTE_LINE` is also given... this points to a NUL terminated string also stored in the results lwsac that contains up to 255 chars of the line from the original file. In some cases, the original file was either virtual (you are indexing a git revision) or is not stored with the index, in that case you can't usefully use `LWSFTS_F_QUERY_QUOTE_LINE`. To facilitate interpreting what is stored per match, the original search flags that created the result are stored in the `struct lws_fts_result`. ## Indexing In-memory and serialized to file When creating the trie, in-memory structs are used with various optimization schemes trading off memory usage for speed. While in-memory, it's possible to add more indexed filepaths to the single index. Once the trie is complete in terms of having indexed everything, it is serialized to disk. These contain many additional housekeeping pointers and trie entries which can be optimized out. Most in-memory values must be held literally in large types, whereas most of the values in the serialized file use smaller VLI which use more or less bytes according to the value. So the peak memory requirements for large tries are much bigger than the size of the serialized trie file that is output. For the linux kernel at 4.14 and default indexing list on a 2.8GHz AMD threadripper (using one thread), the stats are: Name|Value ---|--- Files indexed|52932 Input corpus size|694MiB Indexing cpu time|50.1s (>1000 files / sec; 13.8MBytes/sec) Peak alloc|78MiB Serialization time|202ms Trie File size|347MiB To index libwebsockets main branch under the same conditions: Name|Value ---|--- Files indexed|489 Input corpus size|3MiB Indexing time|123ms Peak alloc|3MiB Serialization time|1ms Trie File size|1.4MiB Once it's generated, querying the trie file is very inexpensive, even when there are lots of results. - trie entry child lists are kept sorted by the character they map to. This allows discovering there is no match as soon as a character later in the order than the one being matched is seen - for the root trie, in addition to the linked-list child + sibling entries, a 256-entry pointer table is associated with the root trie, allowing one- step lookup. But as the table is 2KiB, it's too expensive to use on all trie entries ## Structure on disk All explicit multibyte numbers are stored in Network (MSB-first) byte order. - file header - filepath line number tables - filepath information - filepath map table - tries, trie instances (hits), trie child tables ### VLI coding VLI (Variable Length Integer) coding works like this [b7 EON] [b6 .. b0 DATA] If EON = 0, then DATA represents the Least-significant 7 bits of the number. if EON = 1, DATA represents More-significant 7-bits that should be shifted left until the byte with EON = 0 is found to terminate the number. The VLI used is predicated around 32-bit unsigned integers Examples: - 0x30 = 48 - 0x81 30 = 176 - 0x81 0x80 0x00 = 16384 Bytes | Range ---|--- 1|<= 127 2|<= 16K - 1 3|<= 2M -1 4|<= 256M - 1 5|<= 4G - 1 The coding is very efficient if there's a high probabilty the number being stored is not large. So it's great for line numbers for example, where most files have less that 16K lines and the VLI for the line number fits in 2 bytes, but if you meet a huge file, the VLI coding can also handle it. All numbers except a few in the headers that are actually written after the following data are stored using VLI for space- efficiency without limiting capability. The numbers that are fixed up after the fact have to have a fixed size and can't use VLI. ### File header The first byte of the file header where the magic is, is "fileoffset" 0. All the stored "fileoffset"s are relative to that. The header has a fixed size of 16 bytes. size|function ---|--- 32-bits|Magic 0xCA7A5F75 32-bits|Fileoffset to root trie entry 32-bits|Size of the trie file when it was created (to detect truncation) 32-bits|Fileoffset to the filepath map 32-bits|Number of filepaths ### Filepath line tables Immediately after the file header are the line length tables. As the input files are parsed, line length tables are written for each file... at that time the rest of the parser data is held in memory so nothing else is in the file yet. These allow you to map logical line numbers in the file to file offsets space- and time- efficiently without having to walk through the file contents. The line information is cut into blocks, allowing quick skipping over the VLI data that doesn't contain the line you want just by following the 8-byte header part. Once you find the block with your line, you have to iteratively add the VLIs until you hit the one you want. For normal text files with average line length below 128, the VLIs will typically be a single byte. So a block of 200 line lengths is typically 208 bytes long. There is a final linetable chunk consisting of all zeros to indicate the end of the filepath line chunk series for a filepath. size|function ---|--- 16-bit|length of this chunk itself in bytes 16-bit|count of lines covered in this chunk 32-bit|count of bytes in the input file this chunk covers VLI...|for each line in the chunk, the number of bytes in the line ### Filepaths The single trie in the file may contain information from multiple files, for example one trie may cover all files in a directory. The "Filepaths" are listed after the line tables, and referred to by index thereafter. For each filepath, one after the other: size|function ---|--- VLI|fileoffset of the start of this filepath's line table VLI|count of lines in the file VLI|length of filepath in bytes ...|the filepath (with no NUL) ### Filepath map To facilitate rapid filepath lookup, there's a filepath map table with a 32-bit fileoffset per filepath. This is the way to convert filepath indexes to information on the filepath like its name, etc size|function ---|--- 32-bit...|fileoffset to filepath table for each filepath ### Trie entries Immediately after that, the trie entries are dumped, for each one a header: #### Trie entry header size|function ---|--- VLI|Fileoffset of first file table in this trie entry instance list VLI|number of child trie entries this trie entry has VLI|number of instances this trie entry has The child list follows immediately after this header #### Trie entry instance file For each file that has instances of this symbol: size|function ---|--- VLI|Fileoffset of next file table in this trie entry instance list VLI|filepath index VLI|count of line number instances following #### Trie entry file line number table Then for the file mentioned above, a list of all line numbers in the file with the symbol in them, in ascending order. As a VLI, the median size per entry will typically be ~15.9 bits due to the probability of line numbers below 16K. size|function ---|--- VLI|line number ... #### Trie entry child table For each child node size|function ---|--- VLI|file offset of child VLI|instance count belonging directly to this child VLI|aggregated number of instances down all descendent paths of child VLI|aggregated number of children down all descendent paths of child VLI|match string length ...|the match string