[bknr-devel] Fwd: searching intervals, sorting and invalid-store-random-state signaled when opening a store
Dear,
First of all thank you for splitting off bknr-datastore. Whilst playing around with it, some questions arose.
Searching Intervals: Is there some sort of index or a common idiom to search for all objects in which a specified property's value lies within a certain interval? For instance: listing/mapping over all widgets which have been created between monday and wednesday. Or all exams of a particular pupil which were scored between 35 and 56. Or should I create filters based on the index-mapvalues and index-values? Sorting: Does an index's index-reader (for instance a string-unique-index (but I'd like to know for others as well)) guarantee something with respect to the order in which the results are mapped/listed? If not: is there some idiom to receive a sorted list or should I create a custom index to limit the amount of sorting?
Condition Signaled: Whenever I restart my lisp image in slime and open a previously used store, I receive an invalid-store-random-state in SBCL 1.0.37. Two meaningful restarts are given, being initialize-store-random-state and ignore-store-random-state. Is there something obvious I'm doing wrong or is this a bug of some sort?
Thank you,
mad
On Mon, Apr 26, 2010 at 08:07, madnificent@gmail.com wrote:
Searching Intervals: Is there some sort of index or a common idiom to search for all objects in which a specified property's value lies within a certain interval? For instance: listing/mapping over all widgets which have been created between monday and wednesday. Or all exams of a particular pupil which were scored between 35 and 56. Or should I create filters based on the index-mapvalues and index-values?
There is the skip-list-index which has been designed to deal with ranges and sparse integer valued slots. The skip-list has a skip-list-range-cursor class that can be used to iterate over value ranges. It is not exposed by the store itself, though, so you'll need to get the index instance from the class that you want to query and then call the skip-list-range-index gf on that object.
Sorting: Does an index's index-reader (for instance a string-unique-index (but I'd like to know for others as well)) guarantee something with respect to the order in which the results are mapped/listed? If not: is there some idiom to receive a sorted list or should I create a custom index to limit the amount of sorting?
The order is determined by the underlying index, i.e. hash tables do not provide ordering, but array indices and skip lists do.
Condition Signaled: Whenever I restart my lisp image in slime and open a previously used store, I receive an invalid-store-random-state in SBCL 1.0.37. Two meaningful restarts are given, being initialize-store-random-state and ignore-store-random-state. Is there something obvious I'm doing wrong or is this a bug of some sort?
This is a bug, and I think I briefly saw it a few months ago but did not have the time to fix it. As far as I remember, SBCL's random state can no longer be serialized/deserialized with read/write (see data/txn.lisp). I'd welcome a patch.
Thanks, Hans
On Mon, Apr 26, 2010 at 11:13, Hans Hübner hans.huebner@gmail.com wrote:
On Mon, Apr 26, 2010 at 08:07, madnificent@gmail.com wrote:
Condition Signaled: Whenever I restart my lisp image in slime and open a previously used store, I receive an invalid-store-random-state in SBCL 1.0.37. Two meaningful restarts are given, being initialize-store-random-state and ignore-store-random-state. Is there something obvious I'm doing wrong or is this a bug of some sort?
This is a bug, and I think I briefly saw it a few months ago but did not have the time to fix it. As far as I remember, SBCL's random state can no longer be serialized/deserialized with read/write (see data/txn.lisp). I'd welcome a patch.
I think this is an SBCL bug:
CL-USER> (with-standard-io-syntax (write-to-string *random-state*)) "#S(RANDOM-STATE :STATE #.(MAKE-ARRAY (627) :ELEMENT-TYPE (QUOTE (UNSIGNED-BYTE 32)) :INITIAL-CONTENTS (QUOTE (0 2567483615 624 5489 1301868182 2938499221 ...
As you can see, the array dimensions are written without a quote, so they can't be read (and they can't be read with *READ-EVAL* set to NIL in any case, but I'd rather not get into discussing whether this is allowed as per the spec). Can you please file a bug with SBCL and get them to fix it our help you to find a workaround?
The BKNR datastore supplies transaction code with a random state that is identical during initial execution and rollback so that transaction code yields the same result in both cases even if it makes use of the CL:RANDOM function. This is why the random state is serialized.
Thanks, HAns
Hello,
I just confirmed the bugfix Paul-Virak Khuong for SBCL. I guess the commit will make it through the next release of SBCL, you can playtest it through clbuild.
With respect to the indices, can a skiplist return a range of objects? Or would it be best to do that by mapping over the objects in the index? (eg: show the posts for a particular user if there'd be an index on post-date). If there currently isn't anything like this: Have you thought about this and found it useless or would it be a good thing to have? Have you thought about a syntax which you'd prefer for sorted results?
thanks,
the madnificent
On Mon, Apr 26, 2010 at 11:13 AM, Hans Hübner hans.huebner@gmail.com wrote:
On Mon, Apr 26, 2010 at 08:07, madnificent@gmail.com wrote:
Searching Intervals: Is there some sort of index or a common idiom to search for all objects in which a specified property's value lies within a certain interval? For instance: listing/mapping over all widgets which have been created between monday and wednesday. Or all exams of a particular pupil which were scored between 35 and 56. Or should I create filters based on the index-mapvalues and index-values?
There is the skip-list-index which has been designed to deal with ranges and sparse integer valued slots. The skip-list has a skip-list-range-cursor class that can be used to iterate over value ranges. It is not exposed by the store itself, though, so you'll need to get the index instance from the class that you want to query and then call the skip-list-range-index gf on that object.
Sorting: Does an index's index-reader (for instance a string-unique-index (but I'd like to know for others as well)) guarantee something with respect to the order in which the results are mapped/listed? If not: is there some idiom to receive a sorted list or should I create a custom index to limit the amount of sorting?
The order is determined by the underlying index, i.e. hash tables do not provide ordering, but array indices and skip lists do.
Condition Signaled: Whenever I restart my lisp image in slime and open a previously used store, I receive an invalid-store-random-state in SBCL 1.0.37. Two meaningful restarts are given, being initialize-store-random-state and ignore-store-random-state. Is there something obvious I'm doing wrong or is this a bug of some sort?
This is a bug, and I think I briefly saw it a few months ago but did not have the time to fix it. As far as I remember, SBCL's random state can no longer be serialized/deserialized with read/write (see data/txn.lisp). I'd welcome a patch.
Thanks, Hans
On Wed, May 5, 2010 at 16:46, madnificent madnificent@gmail.com wrote:
With respect to the indices, can a skiplist return a range of objects? Or would it be best to do that by mapping over the objects in the index? (eg: show the posts for a particular user if there'd be an index on post-date). If there currently isn't anything like this: Have you thought about this and found it useless or would it be a good thing to have? Have you thought about a syntax which you'd prefer for sorted results?
I usually do not use indices for such applications, but rather collect the data into the right objects when it is created. In your application, every user object would contain a list of posts that the user made, propably sorted by reverse post date or similar. To read all posts made by a particular user in a certain time period, the post list would just be scanned. Given that the number of posts per user is relatively small, there is not much to be gained by an index.
Indices make sense when you have a very large database that can't be meaningfully split into smaller pieces in advance. The ID slot of persistent objects is such a case. I also successfully used indices to organize access to 2D data that is access by geocoordinates.
Note that often, you can achieve a better design when you abandon the idea of indices as being a service of the database and instead think about the data structures that you want to use to organize your data. With traditional, disk based databases, indices are complementary to storage and often form the architectural foundation for the database. With the bknr datastore, indices play a more specific role inside the storage layer and often offer no advantage when (ab-)used to build the application.
Let me know if you still think that you want to use store indices. I may come up with an example how a skip list could be used, but it is not entirely straightforward.
-Hans
-
Hans Hübner -
madnificent -
madnificent＠gmail.com