Abstracting away underlying storage

[ccleve]

The MapBuilder will accept a struct that implements io::Write. This is cool, it means that the fst can be written anywhere.

Is it possible for Map::new() to accept a struct that implements io:Read instead of &[u8]? What would it take to make that happen?

My need is this: I will have a very large fst, possible larger than available memory. It will be stored in a file that, under the hood, is broken into pages, and the pages are in a cache. If the fst needs to access a part of memory, I'll have to fetch it on the fly from the page cache.

In practice, this will be reasonably fast if most pages are in memory, and it should degrade gracefully if they're not. But I would need a layer of abstraction to do it.

[BurntSushi]

Nope. Random access is pretty baked into the implementation. Even in theory, I don't know how it would be implemented with just an io::Read. You would at least also need an io::Seek.

You haven't explained, AFAIK, why the obvious solution of memory maps doesn't work for you. It's even mentioned in the docs for precisely your use case: traversing large FSTs that don't fit into memory.

[BurntSushi]

In theory, an abstraction could be introduced that gave more control how bytes are fetched. It would just need to be stronger than io::Read.

I'm not sure I personally have the bandwidth to maintain or even review the patches necessary to achieve such a feat though unfortunately.

[ccleve]

I'd like to store the data in native Postgres page files. I'm creating an new type of Postgres index that would use an fst. Unfortunately, pages have page headers, and I can't get around that problem. So even if I could mmap the file directly, I'd still have parts of the file that were inaccessible.

[BurntSushi]

Yeah you should have lead with that. :P Otherwise the XY problem is at work here by asking for io::Read.

In any case, your best bet is to fork and patch it yourself. It likely won't be too easy. The current code is pretty tightly coupled to &[u8]. But it will probably be easier than starting from scratch completely.

[ellenhp]

I found this: https://github.com/phiresky/tantivy-fst Which is used here: https://github.com/quickwit-oss/tantivy/pull/1067 Demo: https://demo.phiresky.xyz/tmp-ytccrzsovkcjoylr/dist/index.html

I'm forking it to see if it will accomplish what I need, but I thought I would also leave it here in case it might help others.

[claudius108]

Hi,

Another very nice project, that uses the fst crate in WASM, is https://github.com/mcuelenaere/porigon. I tested it, and works briliantly. The wasm file is around 300 kB. I also added regex search to it (the size increased to 700 kB).

But tantivy-fst has a very nice feature: the index is only loaded partially, on demand.

Best regards, Claudius Teodorescu

On Wed, 8 Jun 2022, 01:30 Ellen Poe, @.***> wrote:

I found this: https://github.com/phiresky/tantivy-fst Which is used here: quickwit-oss/tantivy#1067 https://github.com/quickwit-oss/tantivy/pull/1067 Demo: https://demo.phiresky.xyz/tmp-ytccrzsovkcjoylr/dist/index.html

I'm forking it to see if it will accomplish what I need, but I thought I would also leave it here in case it might help others.

— Reply to this email directly, view it on GitHub https://github.com/BurntSushi/fst/issues/138#issuecomment-1149236580, or unsubscribe https://github.com/notifications/unsubscribe-auth/AANKHHWUUOWU2VMTWB4T6DLVN7EQPANCNFSM5OWEDI6A . You are receiving this because you are subscribed to this thread.Message ID: @.***>