Saving Alphanueric Ranges and Searching it

[gelinger777]

Let me first of all thank you very much for the hard work you are doing for building this great product.

Summary

Currently we are building a private blockchain, where we need to save alphanumeric serial numbers which consist of following structure

1-2 Char Letters (A, AB, AC, BC etc ) and number which can be from 1-1.000.000.000

We always have a sequence like this

AA0000000001-AA0000000124 for example . So always in our stored data there is Start and End .

So when a new range is added, we have to check existing database of assigned ranges and make sure that it has never been used before.

Problem Definition

How to define number ranges? How to make search on existing ranges and forbid already used numbers to be used again? Is there a way exists with current situation?

[gelinger777]

probably related to #871

[alexanderbez]

Hi @gelinger777. What is the concrete type you're saving here? Is a range a string? e.g. AA0000000001-AA0000000124 or is it a concrete type? Why can't you just query if a given range exists? In any case, you might be able to leverage IAVL prefix queries/scans. The issue you posted doesn't seem related to this I think.

[gelinger777]

@alexanderbez we are open to change the way it is saved if needed . We could theoretically save the range for example as
{"series":"AB","start":"1","end":"128"} .
The question is that if somebody comes in and whants to save
{"series":"AB","start":"15","end":"888"}
or
{"series":"AB","start":"77","end":"79"}
the transaction should fail, because those numbers are already issued and used. Where can I see some examples of IAVL prefix queries ?

[alexanderbez]

the transaction should fail, because those numbers are already issued and used.

Because there is an overlap?

Where can I see some examples of IAVL prefix queries ?

Almost every single module uses prefix queries and iterators.

e.g (prefix: KeyPrefixEvidence).

func (k Keeper) IterateEvidence(ctx sdk.Context, cb func(exported.Evidence) bool) {
	store := prefix.NewStore(ctx.KVStore(k.storeKey), types.KeyPrefixEvidence)
	iterator := sdk.KVStorePrefixIterator(store, nil)

	defer iterator.Close()
	for ; iterator.Valid(); iterator.Next() {
		evidence := k.MustUnmarshalEvidence(iterator.Value())

		if cb(evidence) {
			break
		}
	}
}

---

If you simply want an operation to fail if the series overlaps/intersects with an existing one, you can leverage several approaches and data structures.

e.g.

1. Store all series as a sorted array and do a binary search for the new series and see if it overlaps.
2. Store entries by series/start/end and leverage prefix scans

[gelinger777]

@alexanderbez thank you for your detailed response. Last question, thought. What would be faster and more robust approach , sorted arrays or prefix scans?

[alexanderbez]

Option (1) would require you load the entire set at once, depending on if this set is small, this could be fine. (2) would require less IO, but might be more complicated?

[github-actions]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[gelinger777]

@alexanderbez thank you very much