Some obvious answers you probably covered first:
in reply to Performance quandary
- get more user time from cpu
- get a real db and maybe offload to another machine
- concentrate on raw writes within a guaranteed time rather than doing processing while writing, etc.
But it seemed like you must have something pathological happening if a 200/sec routine drops below 10/sec.
I'm curious, what happens when you don't use a DB at all and just use the current algorithm with an ordinary in memory hash?
The first thing to check is that you are not using 5 year old software. You should build DB_File against Berkeley version 4 or, better yet use the BerkeleyDB module. You still seem not to get all the functionality of Berkeley DB 4 as provided by Sleepycat. That said, see below some other things you could do including using a database like Mysql or PostgreSql which also provide some neat tricks.
There are new tables/functions in Mysql that might help. I wouldn't have said Mysql except this was brought to my attention when I had the great luck of having drinks with their David Atmark in Tokyo (Open Source Developers Conference at VA) two weeks ago. Anyway, It sounds like your extra processing and maybe some bugs in old BDB may push N log N so much closer to an exponential curve that it becomes unfeasible for million object tables at your current CPU level.
- you don't need to do locking because BDB will do page-level, InnoDB row-level locking for you.
- IN MEMORY table spec (maybe not such a big deal)
- use placeholders, prepare once exec many times
- batch adds (batch selects/inserts) via API, or as text file import from a file or pipe
- create a number of writer processes with a preforked server. This way you can add more than one at a time, and row locking could block as necessary.
- or, save up the adds that need to recurse and do them together. don't really know what you want.
- pretune table to data structure/size. BDB makes extra rows for you but needs to know size first. So make it give you a lot more extras.
- multiple indices. In particular, InnoDB maintains an insert buffer that is said to speed up similar databases 15 times. This reduces seeks created by the random distribution of secondary keys. Your current algorithm may actually be doing a seek every single time whereas a real DB caches primary index significantly.
- consider a table type like MyISAM that allows you to do concurrent selects and inserts, if you think this is slowing you down with Mysql.
- Use profiling/optimizing built into Mysql or other DBs
- You might be interested in trying an extremely cool database called Firebird (this is Interbase, bug fixed and open sourced). Actually if you use this, then Firebird 2 (now C++) will be out very soon and give you even more boost. It is very lightweight, dependable (used in aerospace for a long time), and self-tuning. Firebird/Interbase includes "Declarative Referential Integrity Constraints" which means it will synchronize parent-child relationships between tables. Download manual from Borland.
Other things that might help
- DB will keep a log for you anyway. If you really want log, make it a DB table maybe. Shouldn't be taking so much time. Are you autoflushing to disk?
- move processing into triggers, in Perl, Java, C, or PL/SQL
- more complex structures, multiple tables, more space for time tradeoffs
- Throw away all those joins and splits. No more strings, throw away all that "http" and "Inserting parent" etc. Too much Perl going on.
Some reading materials, might help you.
Insert speed mods - confirmed what I thought, that "The size of the table slows down the insertion of indexes by N log N (B-trees)." See tuning link.
Hope this helps. It would be easier to understand what is happening if we could see exactly what the data looks like. Can you define what these trees are anyway? Is it just two levels, with a parent that is a domain name, plus a number (max is what?) of children? Or are you translating paths or XML info into parent-child relationships? Could this data be described as a 2-dimensional (or n-dim) table?