Show HN: Fist – Persistent Full Text Search and Indexing Server Written in C | Hacker News Reader

Show HN: Fist – Persistent Full Text Search and Indexing Server Written in C

github.com

124 pointsmax056362 comments

This seems to be a bit of a stretch in calling it "full-text search" engine: I only casually browsed the code from my phone so I might have missed it, but I don't see any support for stemming, which is a critical piece of any FTS engine (with support for many languages, which further complicates stuff).

This seems to be a simple word indexer instead, which is quite a different proposition to FTS.

I'm not overly familiar with search as a field - why is stemming "critical to FTS" rather than a nice enhancement? I would have thought the defining criterion for "full text search" was that it searched the full text of the database?

The key is "with support for many languages". For many languages (other than English) with heavy use of suffixes and/or prefixes, FTS without stemming is kind of useless.

For many languages, it is even useless with stemming, you would want lemmatization plus a certain amount of fuzzy matching.

I didn’t quite understand what you meant. I saw your comma and thought you were developing another sentence and thought entirely. I understood you meant FTS search needs stemming to be useful after skipping he comma. Just FYI.

Yes, you understood correctly. English is not my native, sorry.

I used to be a heavy comma user. Still am. But try being ‘radical’ and not using a comma more often. (It’s not actually radical at all)

you don't need stemming for full text search, although it is a benefit for some text data.

Hey all, Fist project creator here. Just wanted to thank everyone for the support and the comments. I’ve been working on this project for a few months now mainly as a passion project. It’s awesome to see some people taking an interest.

I could definitely use some help on this. Whether it be giving advice or writing actual code.

If anyone would like to chat more about this I have setup a slack channel for be project. Here is the invite link

https://join.slack.com/t/fist-global/shared_invite/enQtNjcyN...

Thank you again for all the support, I’m excited to continue development.

As others have pointed out there are some features considered essential in this space that would be good additions to the code:

Stemming: (removing prefix/suffixes walked, walking, walker -> walk) The snowball library contains many language stemmers https://snowballstem.org

Stopping: removing many common words like the/and that almost every document will surely match anyway. Again, per language.

Relevance ranking: Generally some variant of TF/IDF like BM25. The book "Managing Gigabytes" is an excellent intro to the subject and information retrieval in general: https://people.eng.unimelb.edu.au/ammoffat/mg/

A Document/Term/Value model, this is how Lucence, Xapian, and other IR systems model the store. It's worth sticking with that same pattern.

Good luck!

This is very helpful. I am working on all of this, but summarizing it all here helped me a lot. Thank you.

Pretty much everyone here knows Lucene as the primary text-search engine these days, but there's a competitor Sphinx Search which is written in C or C++ and is much lighter, to the point of being feasible as bundled with desktop software. It however has a bit weird database structure since text indexing is the primary use-case―this is being corrected in the third version with support for secondary indexes, but v3 isn't open-source yet.

Not to be confused with Sphinx the documentation builder.

Looks like the project is still under development but I think that having a http based interface would make this much more accessible to be used easily from multiple languages.

Disclosure: I work on a similar open source search engine (https://github.com/typesense/typesense)

This is an interesting assertion. Aside from JavaScript from the browser, which is tied to HTTP, what language can't use a TCP interface but can use an HTTP one?

I was merely highlighting the convenience of a HTTP based RESTish API. It will be a familiar pattern instead of a custom text based protocol over tcp.

HTTP is so much more convenient at this point, easy to consume by tools, routing, load balancing etc.

Very good idea. Can't say I haven't also thought about this. I was also thinking about doing what Tile38 (https://github.com/tidwall/tile38) does and using the REDIS protocol. HTTP is a better option though. Or just both.

Honestly I would use ucspi for this and chain the needed programs together.

https://github.com/tantivy-search/tantivy - Lucene in Rust (I have no idea about API or feature parity)

Thanks for the publicity :)

If the acronym is Fist, shouldn’t you change order of words to:

Fist - (F)ull - (i)ndex (s)erver for (t)ext

I look forward to the day I can stop googling and start fisting.

This is one hell of a comment. Thank you, sir.

Or: [F]ist [i]ndexes [s]earchable [t]ext

A recursive acronym, like GNU (GNU's Not Unix), GOD, EINE, ZWEI, SPARKS (tail recursive :), LAME, PINE, PIP, TIARA (!), WINE, YAML, JINI and many more:

https://en.wikipedia.org/wiki/Recursive_acronym

Also see backronym:

https://en.wikipedia.org/wiki/Backronym

Oh damn, this is a good idea. I just really wanted to call this project Fist and couldn't figure out how to do that. I see that you are more clever than I am. I am going to use this, I think. Ty

Fist Isn't STemming

For simple full text search I like to use SQLite fts3 and Xapian which is a feature rich and mature full text search engine. https://xapian.org/

Similar: https://github.com/apache/attic-lucy (recently archived)

Surely “sift” would’ve been a better anogram?

“Search (and) index full text”

https://sift-tool.org

Would using an event handler make this faster?

http://libevent.org/ http://www.kegel.com/c10k.html

Very cool project. Which algorithm do you use for indexing/retrieval?

Thanks for this!

Right now it is not very complicated. An inverted index of the text that is sent over is created and added to the database. The DB is just a big hash map. Searching right now is just an O(1) lookup in this hash map of the text being searched in this hash map.

I have plans to improve this of course. There is a lot of room for improvement. I am also planning on adding scoring using TF-IDF, but it's not done yet.

Any help with this would be more than appreciated!

There is also Groonga:

https://github.com/groonga/groonga

But this looks like it intends to be a lot simpler.

I've been using http://sphinxsearch.com for many years. Why should I consider Fist?

There's also Manticore, an actively developed fork of the last open-source version of Sphinx: https://manticoresearch.com/about/

Didn't know about this, thanks! I guess Sphinx has worked so well for me that I haven't explored other options lately (except for a brief test of ElasticSearch to see what the buzz was about).

I rather keep using xapian. That's a proper indexing and search-engine (C++), much better than sphinx or Elasticsearch. Elasticsearch just has better client integration for things like MS Word or PDF, if you want to jump to the highlighted line in the document.

I haven't looked at Xapian in many years and I can't remember the reason I originally picked Sphinx instead of it. In what ways do you think it is "much better"?

That was my conclusion when I implemented our company search engine. Lucene/Sole was nice, had better frontends, but a horrible backend in Java needing too much memory. Sphinx was small and fast, but lacked all the important additional functionality I needed. Eg. customized ranking, aliases, language detection and stemming, a good Google-like query parser. I probably forgot most, this was 20 years ago.

It is irresponsible to the point of professional negligence to write new software in C.

Isn't C the fastest, most energy efficient and has a very small code footprint?

see : https://thenewstack.io/which-programming-languages-use-the-l...

You'd think that something like a text search would benefit from being as fast as possible.

Aren't most of the other languages written in C because it is fast? (Except for Rust, of course, which now appears to be a very reasonable alternative ).

C is fast, small, and energy efficient. It is also impossible to write safe, exploit-free code in C by hand. The juice ain’t worth the squeeze.

It is more irresponsible to make a comment like this. People should write software in a language that A) can do the job B) they're proficient in. For example, I would much rather have a C program written by someone proficient in C than a C# program written by someone new to the language.

The point I’m making is that nobody is actually proficient in C; it’s not possible to write safe software in it.

Yep, not to bash the author but just to show how easy it is to write unsafe C. First function i started reading i already found a memory leak within a minute: indexer calls dsplit which calls dcreatea which calls malloc, this value is never freed inside indexer or anywhere on the way down. It might be that the buffer gets shared with index so by coincidence it's eventually freed but the fact that i have to think so hard and juggle all those buffers in my head for such a simple function just makes my head hurt.

dsplit(), an even simpler function also calls dcreate() which allocates memory into the variable called 'new' that never gets freed. This is schoolbook example of a memory leak, showing the guy didn't choose C because he's already proficient in it. Or even worse, if he is proficient and the language still allows such serious mistakes to slip through so easily.

Edit: the code is actually completely full of memory leaks the more i read, stuff like else if(dequals(commands.values[0], dcreate(SEARCH))) where dcreate returns a buffer from malloc which would have to be freed.

Haha here you have the right title song for this thread: https://www.youtube.com/watch?v=4dXc4ilXOLA

* sorry stupid word-play

Hahaha, I love this! Got me fired up xD

I find it hard to believe that this is "fast" as advertised when it isn't even compiled with optimizations: https://github.com/f-prime/fist/blob/9049066e8d49ff41f2272ec...

Do you realize that this is open source and being offered to you as a gift? The license allows you to compile this tool with whatever compiler and flags you want. Please do that if you care about the optimizations. But please do not post dismissive comments when someone is putting themselves in a vulnerable position willingly by sharing their hard work for free with the community. If you have feedback to offer, do it constructively with kindness and acceptance, not with reproach and snide.

Project Dev here, if you'd be willing to help me with that part I would be greatful. When I talk about "fast" I mean all searches are O(1) due to the magic of hash maps.

Fast FTS use reverse indices with trigrams, not primitive hash maps.

Any links to papers or docs about that? Interested.

Using plain makefiles with "gcc" hardcoded in is atrocious, at least use $(CC). This also raises in me the suspicion that it hasn't been tested with no compiler other than GCC at whatever version the developer had installed on his machine, which is bad.

It's a two line Makefile.

I was able to compile this with no issues using "Apple clang version 11.0.0 (clang-1100.0.20.17)". If you're staying within the standard I don't see why you really need to do a whole lot of testing to make sure your project works with other compilers?

Stop! Just stop this! This is a "Show HN" post. Someone out there is trying to develop something useful and share it with the community. By doing so, the author is willingly putting themselves in a vulnerable position where the author's work could be examined critically. The project is also open source. Don't forget that it means that it is being given to you as a gift!

If you think this needs more testing, do it yourself. The author of this project does not owe you any testing. If the Makefile works for author, that's good enough for the author. If it isn't good enough for you, fix it. The license allows you to do that. Then consider being nice and giving that fix back to the community with a pull request.

Don't come here on your high horse and post vile comments on something that is being shared with you as a gift! If you come here with your pull requests, code, or even better--your own projects, you would be welcome!

Really? Do you distribute your project binaries in different versions compiled in various compilers? If not, why is it necessary a bad thing?

Project developer here: Would gladly accept some help with this if you'd be willing to offer it.

I just submitted a PR #4 which changes your Makefile to work a little better. Hopefully it makes the parent commenter stop crying too :)

You can frame a critique in a way that doesn't make the subject feel targeted.

Some tips:

* Rather than call their way atrocious, try something like "Use $(CC) instead of hard coding gcc to avoid a lot of headaches down the road."

* Instead of:

>> "This also raises in me the suspicion that it hasn't been tested with no compiler other than GCC at whatever version the developer had installed on his machine, which is bad."

Consider:

"Test on other machines to make sure you don't depend on quirks of your local gcc installation."

Don't tear down. Build up.

Reply on news.ycombinator.com