Based on recent discussions about ridding Python of bsddb I decided to
see how hard it would be to implement a barebones dbm.sqlite module.
Turns out, not very hard.

No docs.  No test cases.  Caveat emptor.  But I think it can serve as
at least a proof of concept, maybe as the basis for a new module in
3.1.

Attaching corrected module.

Attaching test cases based on dumbdbm tests.

Another slight revision to the module.

Trivial doc diffs against 3.0b3 doc.

Another tweak - add values()

Updated test cases

It would be more efficient to base keys() on iterkeys() than the
reverse, IMO.
Other than that, why not open a branch or at least upload full-fledged
patch files? :)

Antoine> It would be more efficient to base keys() on iterkeys() than the
    Antoine> reverse, IMO.

True.  I was just modifying the dumbdbm implementation.

    Antoine> Other than that, why not open a branch or at least upload
    Antoine> full-fledged patch files? :)

Well, I only intended to create the initial proof of concept, but then last
night I couldn't sleep so I cobbled the test module and docs from the
existing stuff ... ;-)

When I get a couple minutes free I'll try and condense it into a more
suitable form.  Probably not until the weekend though.

Skip

OK, I made a sandbox project out of it:

svn+ssh://pythondev@svn.python.org/sandbox/trunk/dbm_sqlite

Hack away!

I would like to see something like this go into 3.0 so that shelves
don't become useless for Windows users.

Here's an alternate version with most of bsddb's interface intact.

sq_dict review:

have sqlite quote/escape self._mtn before using it with a python %s
substitution.  or pass it into the sql query function as a positional ?
parameter like you do for keys and values.  (avoid sql injection)

raise a TypeError rather than a ValueError when you don't like the key
or value type.

also, to test the type, isinstance(val, str) is better than using type(val).

I tried passing the db name as a parameter with '?', it doesn't always 
work.  Also, there shouldn't be any SQL injection issues here unless 
someone designed their system wrong (if a third party is allowed to pass 
the name of a db table into the open/create function, then they can do 
much worse than mangle or hide data in a sqlite database).

With regards to isinstance being better than type; it's only better if 
you want to support subclasses.  When writing the module, I had no 
interest in supporting subclasses (though supporting both str and buffer 
in 2.x, and bytes and memoryview in 3.x seems reasonable).

I like Skip's version better, because it's closer to the dbm
"specification" instead of trying to mimic bsddb (first, last, etc.).
I'd like to keep such things out.

I've made a few changes to the sandbox project which I will check in
later today. The most important change is support for a "fast mode",
which doesn't commit changes until you call the synch() method. synch()
is also called on close().

Perhaps we should do automatic commits every n (like 1000) changes, too?

What's all this ORDER BY in both your implementations about? The dbm
"spec" says nothing about keys being ordered AFAIC. Can we get rid of these?

One question about Josiah's _check_value(). SQLite is less crippled than
other simplistic databases and also supports integers, reals and blobs
in addition to strings.

Shouldn't we make this accessible to users? Or is compatibility with
other dbm implementations more important?

Gerhard> What's all this ORDER BY in both your implementations about?
    Gerhard> The dbm "spec" says nothing about keys being ordered AFAIC. Can
    Gerhard> we get rid of these?

I'd like to guarantee that zip(db.keys(), db.values() == db.items().

Skip

Le jeudi 11 septembre 2008 à 12:46 +0000, Skip Montanaro a écrit :
> Gerhard> What's all this ORDER BY in both your implementations about?
>     Gerhard> The dbm "spec" says nothing about keys being ordered AFAIC. Can
>     Gerhard> we get rid of these?
> 
> I'd like to guarantee that zip(db.keys(), db.values() == db.items().

It doesn't sound very useful, and it may hurt performance on big tables.

> I'd like to guarantee that zip(db.keys(), db.values() == db.items().

Ok. If that isn't guaranteed elsewhere just drop it here?

FWIW that will also work without the ORDER BY, because you're getting
the rows back in the same ORDER. Something cheaper would also be "ORDER
BY ROWID". I still propose to just do without the ORDER BY.

>> I'd like to guarantee that zip(db.keys(), db.values() == db.items().

    Antoine> It doesn't sound very useful, and it may hurt performance on
    Antoine> big tables.

Actually, I think Python guarantees (for dicts at least - other mappings
should probably follow suit) that if you call keys() then call values()
without making any changes to the dict that their orders match, e.g., that

    zip(d.keys(), d.values()) == d.items()

Skip

Gerhard> FWIW that will also work without the ORDER BY, because you're
    Gerhard> getting the rows back in the same ORDER. Something cheaper
    Gerhard> would also be "ORDER BY ROWID". I still propose to just do
    Gerhard> without the ORDER BY.

As long as SQLite guarantees that the ordering is identical, then sure, dump
the ORDER BY clause.

Skip

Skip Montanaro wrote:
> Skip Montanaro <skip@pobox.com> added the comment:
> 
> Gerhard> FWIW that will also work without the ORDER BY, because you're
>     Gerhard> getting the rows back in the same ORDER. Something cheaper
>     Gerhard> would also be "ORDER BY ROWID". I still propose to just do
>     Gerhard> without the ORDER BY.
> 
> As long as SQLite guarantees that the ordering is identical, then sure, dump
> the ORDER BY clause.

It doesn't guarantee it, but the implementation behaves like this.

-- Gerhard

Le jeudi 11 septembre 2008 à 13:48 +0000, Skip Montanaro a écrit :
> Actually, I think Python guarantees (for dicts at least - other mappings
> should probably follow suit) that if you call keys() then call values()
> without making any changes to the dict that their orders match, e.g., that
> 
>     zip(d.keys(), d.values()) == d.items()

Perhaps. I've never written any code that relies this, though, and it
doesn't sound like an useful guarantee since you can just use the
items() method anyway. It probably dates back to an era when list
comprehensions didn't exist, and extracting keys or values from the
items list required several lines of code and costly method calls.

Also, the point is that Python dicts can make that guarantee without
being any slower. It may not be the same for an RDBMS backend. Why?
Because, depending on the backend, index and data can be stored in
separate areas with different storage layouts (e.g. keys are in a B tree
while values are just dumped sequentially). If you only ask for
unordered keys, they will be read in optimal (sequential) index order,
and if you only ask for unordered values, they will be read in optimal
(sequential) data order, which is not the same. This is true for e.g.
MySQL.

(also, IMO this discussion proves that the module shouldn't be included
in Python 3.0. It's too young, its API hasn't even settled down)

I might add that calling keys() then values() is suboptimal, because it
will issue two SQL queries while calling items() will issue just one.

> I like Skip's version better, because it's closer to the dbm
> "specification" instead of trying to mimic bsddb (first, last, etc.).
> I'd like to keep such things out.

dbm.sqlite is meant as a potential replacement of dbm.bsddb.  Since 
people do use the extra methods (.first(), .last(), etc.), not having 
them could lead to breakage.

Separating them out into a subclass (regular open doesn't have it, but 
btopen does), along with all of the other order guarantees (the ORDER BY 
clauses in the SQL statements), could keep it fast for people who don't 
care about ordering, and keep it consistent for those who do care about 
ordering.

Attached you will find an updated version.

>> As long as SQLite guarantees that the ordering is identical, then
    >> sure, dump the ORDER BY clause.

    Gerhard> It doesn't guarantee it, but the implementation behaves like
    Gerhard> this.

If the behavior isn't guaranteed, I think you need to retain ORDER BY.

Skip

Antoine> I might add that calling keys() then values() is suboptimal,
    Antoine> because it will issue two SQL queries while calling items()
    Antoine> will issue just one.

Well, sure, but heaven only knows what an application programmer will do...

S

> Well, sure, but heaven only knows what an application programmer will do...

If the docs clearly explain that there is no guarantee, we don't need
heaven.
I would find it strange to potentially ruin performance just for a
guarantee which has no useful purpose.

> I would find it strange to potentially ruin performance just for a
> guarantee which has no useful purpose.

Benchmarks to prove or disprove performance changes?  Subclasses to 
offer different order by semantics (see the version I uploaded for an 
example)?  Consistent behavior wrt dictionaries?

> Benchmarks to prove or disprove performance changes?

Agreed, benchmarks should be run.

> Subclasses to 
> offer different order by semantics (see the version I uploaded for an
> example)?

If you like, but "ordering semantics" is something which is just as
easily done in Python, so I don't understand the point of integrating it
in the dbm layer...

> Consistent behavior wrt dictionaries?

It sounds like an example of foolish consistency to me. The performance
characteristics are certainly too different to consider dbm.anything a
transparent replacement for standard dicts. And dbm.sqlite only accepts
strings, not the wide range of datatypes that dicts accept as keys and
values... so, given the big picture, I don't see why you care about such
a mostly pointless detail.

>> Well, sure, but heaven only knows what an application programmer will
    >> do...

    Antoine> If the docs clearly explain that there is no guarantee, we
    Antoine> don't need heaven.  I would find it strange to potentially ruin
    Antoine> performance just for a guarantee which has no useful purpose.

From <http://docs.python.org/lib/typesmapping.html>:

    If items(), keys(), values(), iteritems(), iterkeys(), and itervalues()
    are called with no intervening modifications to the dictionary, the
    lists will directly correspond. This allows the creation of (value, key)
    pairs using zip(): "pairs = zip(a.values(), a.keys())". The same
    relationship holds for the iterkeys() and itervalues() methods: "pairs =
    zip(a.itervalues(), a.iterkeys())" provides the same value for
    pairs. Another way to create the same list is "pairs = [(v, k) for (k,
    v) in a.iteritems()]".

While the emphasis is on dictionaries, it seems to me that page describes
the notation and properties of mappings in general, not specifically
dictionaries.

I think it might be worthwhile to get a verdict from Guido on this one.

Skip

> If you like, but "ordering semantics" is something which is just as
> easily done in Python, so I don't understand the point of integrating
> it in the dbm layer...

Actually, the db layer is *exactly* where it should be implemented, 
especially when an index can already exist (as is the case with the 
implementation I provided), especially when the total size of keys can 
easily overflow memory.  Implementing ordering semantics in Python would 
be a waste of what the db is good at: storing and ordering data.

> It sounds like an example of foolish consistency to me. The 
> performance characteristics are certainly too different to consider 
> dbm.anything a transparent replacement for standard dicts. And 
> dbm.sqlite only accepts strings, not the wide range of datatypes that 
> dicts accept as keys and values... so, given the big picture, I don't 
> see why you care about such a mostly pointless detail.

No one here has ever claimed that dbm should be a replacement for dicts, 
even if shelve attempts to do so.  This module should provide a shelve 
interface that mirrors bsddb's interface.  One of the things that was 
offered earlier was that since sqlite can store ints, floats, etc., as 
keys, maybe we should offer that ability.  I think that the base should 
act like a regular dbm object.  I think that a key-ordering should be 
available.  And if we are to offer arbitrary keys (ints, floats, unicode 
strings, byte strings, or None), it should be unordered like the base 
version.

I've uploaded a new copy of sq_dict that offers unordered shelve and 
arbitrary keys in a shelve db.

Here's a version with views from Python 3.0 for keys, values, and items 
:) .  I know that no one hear likes my particular implementation (though 
it offers more or less the full interface), but the Keys, Values, and 
Items classes in the following version are quite generic (they only 
require that the base class implement __iter__, _itervalues, and 
_iteritems), and reasonably optimized.  They could probably be moved 
into the generic dbm stuff and used by everyone.

Josiah> I know that no one hear likes my particular implementation
    Josiah> (though it offers more or less the full interface)...

I think implementing as much of the bsddb interface as you can is fine.  I
agree people used first, next, last, etc and having them present is a good
idea.  My initial aim was to get a replacement for use with shelve.  Its
limitations shouldn't deter people from extending it (or the other dbm.*
modules) in other ways.

Even if all the modules aren't going to be widely cross-platform I see no
reason they can't strive to be more-or-less API-compatible.

Skip

I'm looking for a bsddb-shelve replacement (because of we bsddb
corruption problems), and decided to give this a try. Don't overlook
the free locking you get from sqlite when evaluating this for inclusion!

A small bug:

>>> from sq_dict import shelve
>>> shelve('zz', 'c')[42] = 2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "sq_dict.py", line 144, in __setitem__
    key = self._check_key(key)
  File "sq_dict.py", line 287, in _check_key
    (", ".join(i.__name__ for i in self._allowed_keys), type(key)))
NameError: global name 'self' is not defined

Thank you for the report (fixed in the newly attached version) :) .

Hopefully I'm not picking at a scab here.  I updated the dbm.sqlite
module in the sandbox.  It now orders by rowid instead of by key.
(I saw no performance penalty for the small table sizes I was using
to ordering.  I switched from ordering by key to ordering by rowid
based on Gerhard's comment.

I got a big performance boost on writes by only committing once every
100 calls to __setitem__.  I still commit when deleting keys and 
explicitly commit when closing.

The main performance bottleneck now appears to be keys() and iterkeys().
I don't see how to make them any simpler.  Oddly enough, it seems
that iterkeys() is slower than keys().  Maybe it's just lack of sleep
but I can't see why this is so.

Am also working on a patch for this and would like to coordinate.  My
first draft is attached:

Some comments on tmp_dev_shelver.py...

Regarding SQLhash.__init__, it would be better to avoid relying on the
"sqlite_master" table by using the CREATE TABLE IF NOT EXISTS form of
table creation.

Setting the isolation_level in __init__ will have essentially no effect
on this code because there is currently no transaction management in the
code.  However, the rest of the code also has almost no effect, because
there are no commits anywhere in SQLhash.  All the data is always lost
when the connection is closed.

Regarding the XXX in SQLhash.__len__, there is no faster way using
"sqlite_master".  There is basically just one way to make COUNT(*) fast.
 Keep track of the count in the database (update it on inserts and
deletes).  Then, use that instead of using COUNT(*).

Once there is some use of transactions, it will indeed be important, in
DBhash.__setitem__, to make sure the delete and the insert are in the
same transaction.  Actually, a different approach would be better,
though.  INSERT OR REPLACE INTO will let you replace a row's value with
one statement.  It's also faster, since the row only has to be found once.

Additionally, an index on the key column will assist performance
substantially for large data sets.

Thanks for looking at this.  I'll do an update in the next few days.

Unassigning myself.  I don't have time for this.  I've taken my sandbox
version about as far as I can, and the subject of this ticket has
gone a bit far afield from just adding a sqlite module to the dbm pkg.

Here's an updated patch (it's also in the sandbox):

* Added a sync() method to support shelves.
* Removed commits on granular sets and gets.
* Optimized __len__ and __contains__.

I think issuing 'SELECT MAX(ROWID)' to compute the length of the table
is not correct if some rows get deleted in the table.
I've found a thread about it here:
http://osdir.com/ml/db.sqlite.general/2004-03/msg00329.html
In that thread someone suggested caching the length in another table and
updating it through a trigger each time the main table is modified.

That's a bummer.  Changing this method to __bool__ and then setting
__len__ back to "count(*)".

FWIW, I put an alternative in the sandbox /dbm_sqlite/alt/dbdict.py and
am attaching a copy here.  The idea is to emulate gdbm's fast mode and
delay all writes until closing.  That lets us subclass from dict and get
high-speed lookups, sets, and deletions.  Freeing ourselves from an DB
also gets us a choice of ultra-portable file formats (json, csv, pickle,
eval).

Unassigning.  The code works but no one seems to be pushing for or
caring about inclusion in Py3.1.  

If commits are delayed, then you might as well adopt the dbdict.py
approach instead (reading the file in once at the beginning, operating
directly on a dict subclass, and atomically writing it out at the end).

is there any chance for inclusion in 3.1?

By utilizing triggers on inserts and deletes it is possible to
keep track of the size and speed up __len__ by 10 x.

SQL:

CREATE TABLE IF NOT EXISTS info
   (key TEXT UNIQUE NOT NULL,
    value INTEGER NOT NULL);

INSERT OR IGNORE INTO info (key,value) VALUES ('size',0);

CREATE TABLE IF NOT EXISTS shelf
    (key TEXT UNIQUE NOT NULL,
     value TEXT NOT NULL);

CREATE TRIGGER IF NOT EXISTS insert_shelf
    AFTER INSERT ON shelf
    BEGIN
         UPDATE info SET value = value + 1 WHERE key = 'size';
    END;

CREATE TRIGGER IF NOT EXISTS delete_shelf
    AFTER DELETE ON shelf
    BEGIN
         UPDATE info SET value = value - 1 WHERE key = 'size';
    END;

On my laptop this increase the speed of 'len' about 10x

I have a slightly modified version of dbsqlite.py for
running on python 2.5 utilizing the triggers for 
keep track of the size:

http://dpaste.com/hold/122439/

It would be nice to try to advance this at PyCon, or at another time.

Multi threading:

According to http://www.sqlite.org/cvstrac/wiki?p=MultiThreading
we need to keep a connection for each thread to support multi threaded
access to the database. 

I came across this when deploying an application in a multi threaded
environment. Solution is to keep the connection in the thread local-data.

Also note that a memory database is not shared between threads and
a hairy workaround with a separate working thread with queues for access
is needed. A memory database could perhaps be disallowed as the dbm is file only?

import threading

class SQLhash(collections.MutableMapping):
    def __init__(self, filename=':memory:', flags='r', mode=None):
        self.__filename = filename
        self.__local = threading.local()
        
        MAKE_SHELF = 'CREATE TABLE IF NOT EXISTS shelf (key TEXT PRIMARY KEY, value TEXT NOT NULL)'
        self.conn.execute(MAKE_SHELF)
        self.conn.commit()
    
    @property
    def conn(self):
        try:
            conn = self.__local.conn
        except AttributeError:
            conn = self.__local.conn = sqlite3.connect(self.__filename)
            self.conn.text_factory = bytes
            
        return conn

This wiki page is out of date. It appears that SQlite is now threadsafe by default: http://www.sqlite.org/threadsafe.html