Find max/min value of column in Mnesia in constant time

Question

How can I in constant time (or closest possible) find the maximum or minimum value on an indexed column in an Mnesia table?

Uranous

Answer 1

I would do it outside the Mnesia database. Keep an explicit-min and explicit-max by having a process which learns about these values whenever there is an insert into the table. This gives you awfully fast constant time lookup on the values.

If you can do with O(lg n) time then you can make the table an ordered_set. From there, first/1 and last/1 should give you what you want, given that the key contains the thing you are ordering by. But this also slows down other queries in general to O(lg n).

A third trick is to go by an approximate value. Once in a while you scan the table and note the max and min values. This then materializes into what you want, but the value might not be up to do date if it was a long time since you last scanned.

Flat

Good answer! You give three separate ways of dealing with this. A question though on your first suggestion, is there an easy way of transparently "listen" to inserts into an Mnesia table, or would I have to make a wrapper that I would call instead? – Uranous

You will need a wrapper. Or you would need to place it on the inside of a transaction. – Flat

Answer 2

Good question but I don't think it is possible. A quick look through mnesia and qlc documentation did not give me any clues on the subject.

It seems for me that secondary keys facility in mnesia is incomplete and thus is very limited in features. Not to mention horrible mnesia startup times while loading indexed tables.

I think the most reliable solution in your case would be to do explicit indexing. E.g. creating and keeping in sync alongside table with ordering on primary keys which are in fact the values you have wanted to index by.

Boundless

I think you may be right, but it feels horrible if that's the case! – Uranous