Eric, You should reduce your demonstration case to something you'd be willing to post the code for. Probably using synthetic data (preferably generated data). There's something missing in the thread right now, and it's unlikely to be exposed by random shots in the dark.
-scott On Tue, Jun 22, 2010 at 3:01 PM, Eric Smith <eas....@gmail.com> wrote: > Richard Hipp wrote: > >> When there are no indices, SQLite can put the rows into the database in >> any order it wants, and it chooses to put them in ascending order. Thus, >> each insert becomes a constant-time append. (Approximately - the truth is >> a little more complicated, but by waving our arms vigorously, we can still >> claim constant time per row.) But if there are indices, each row must be >> inserted in index order, which involves a b-tree search to find the right >> spot and possible a rebalancing operation - O(logN) per row. > > Again, my observation is that you are *not* doing constant-time inserts > when there are no indices. > > What do you mean, "ascending order"? > > The only constraint on the relevant table is a foreign-key ref to a tiny > table. But the asymptotic behavior is the same with pragma foreign_keys > off or on. > > I double-checked sqlite_master and there are no indices (not even > auto-indices) on the table. > > Inserts are *faster* at high row counts when there *are* indices. > > I am using 3.6.23.1. I haven't tested earlier versions (waiting on a > reply in another thread to find out where to get them). > > How vigorously are you waving? Can you describe the real algorithm, or > at least a second-order approximation? > > Eric > > -- > Eric A. Smith > > What the hell is it good for? > -- Robert Lloyd (engineer of the Advanced Computing Systems > Division of IBM), to colleagues who insisted that the > microprocessor was the wave of the future, c. 1968 > _______________________________________________ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
