On 6/20/07, Andrew Finkenstadt <[EMAIL PROTECTED]> wrote:
How difficult do you think it would be to support an alternative method of
indexing within SQLite specifically to support O(1) retrieval of the rowid
for a table, and then potentially O(1) retrieval of the row data for a
table, when in-order retrieval is undesired?
My database design is highly specialized to never, ever retrieve data except
by whole-key equality, and would benefit greatly from this optimization.
I'm willing to code it up myself, although I'm not quite set up to do SQL
syntax parser changes, preferring to use the amalgamation.
Would you be able to live with converting your primary key to a 64-bit
hash value? In development of fts2, I found that direct rowid -> row
access is pretty fast. It's still technically O(logN), but the log's
base is absurdly large, so it comes reasonably close to O(1). Then
you could do something like:
SELECT x FROM t WHERE rowid = hashfn(?0) AND real_primary = ?0
hashfn() would take a string and return a 64-bit rowid. The test
against real_primary is to guard against hash collisions, which you
may-or-may-not care to bother with (that said, it should be
essentially free, at least in disk I/O terms).
Since SQLite does varint-encoding, you'd get somewhat better
performance using a 32-bit or smaller key (so the interior nodes pack
more densely). Of course, that raises your chances of collision.
Not certain how to deal with collision. You could just have a second
table with real_primary as the actual primary key, and put a flag in
the main table. 99.999% of the time, the query will draw from the
main table, and the few remaining hits should be fast because the
secondary table should be very small.
BTW, this may be an example of a case where *dbm or bdb would be
justified. It would also be interesting for someone to build a
virtual table interface implementing this idiom.
-scott
-----------------------------------------------------------------------------
To unsubscribe, send email to [EMAIL PROTECTED]
-----------------------------------------------------------------------------
