Re: [sqlite] Clarification on file locking in web-served apps
Okay, I think I figured out one piece that I was forgetting Check me on this: SQLite locks the DB during the Open only so long as it takes to read through the DB file. I seem to recall running across that fact somewhere in the FAQs or on this user list I know the general SQL theory on transactions, sorry if I didn't get that across correctly earlier. So in other SQL engines, accessing a table can be done concurrently by several processes, and the granularity for updates and inserts is generally record-only, unless one uses a transaction. I'm sure that slightly over-simplified, but it should be about accurate I know from an earlier email by Richard Hipp... >>> 1. Everytime you call sqlite_open(), SQLite must read and parse the entire database schema. This is surprisingly quick, but you still might want to keep your schema small if you are calling sqlite_open() a lot. 2. SQLite uses course-grained locking. While most client-server database engines lock a table or row of data at a time, SQLite locks the entire database. So if concurrency is an issue for you, it is better to break the data up into separate files so that you can have more (and finer grained) locks. <<< ...that sqlite_open() does have a bite to take from the processing time. I think I see now where I got confused I must have taken statements 1 and 2 and rolled them together in my mind > sqlite_open does not lock the database. You can keep the database open as > long as you like, and whenever you're not actually executing SQL the file > will be unlocked. But I would like to ask a follow up question regarding your comment about keeping SQLite open On a web server, can this be done and shared by all users? Put another way, can I have my web server spawn off a sort of pseudo server for my couldn't-help-but-make-it-huge database so that it only gets "opened" once during the day or week and shares the instance with every web user that hits any of several pages? Thanks so much for taking the time to answer! -- Vania Smrkovski http://www.pandorasdream.com On Wed, 2004-01-14 at 21:36, [EMAIL PROTECTED] wrote: > Vania, > > > > > > Vania Smrkovski <[EMAIL PROTECTED]> > 15/01/2004 12:14 PM > Please respond to vania > > > To: "SQLite-Users (E-mail)" <[EMAIL PROTECTED]> > cc: > Subject:[sqlite] Clarification on file locking in web-served apps > > - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [sqlite] Clarification on file locking in web-served apps
Vania, Vania Smrkovski <[EMAIL PROTECTED]> 15/01/2004 12:14 PM Please respond to vania To: "SQLite-Users (E-mail)" <[EMAIL PROTECTED]> cc: Subject:[sqlite] Clarification on file locking in web-served apps > Why the heck would anyone even need Transactions in the first place? If the DB file is locked, no changes can be made, right? The database file is only locked while a transaction is active. Since a transaction is implicitly started and ended every time you do an update if one's not already running this means that whenever you're modifying the data the whole file is locked. When your transaction ends the file is unlocked again. Likewise, when you query the database the file is read-locked for the duration of the query. In this instance multiple programs (or threads) can query the database at the same time, but if any query is active updates have to wait. sqlite_open does not lock the database. You can keep the database open as long as you like, and whenever you're not actually executing SQL the file will be unlocked. Note that the other thing transactions will give you is a guarantee of atomicity. Either the whole transaction gets written or none of it does. If your program crashes (or your machine loses power) before the end of the transaction, the partial updates will be reversed next time you open the database. > So I'm wondering if I am missing a few pieces Is the database file locked more than once during a process? That is, does it get locked as the Update statement is getting a collection of rows with which to apply the intended actions? Does it then release the lock as it prepares the update on this subset of data, and then re-lock when it prepares to write? If so, that would explain the need for a Transacction, as it leaves gaps of access during the transaction. If you do these as separate SQL statements without a transaction its possible that someone else can get a write in, in-between your own query and update. > Ignoring Transactions for a second, if I have such a Select, will every user ben locked behind a wall until the Select for user 1 is complete? > And if this is not the case for Select, will it be so for Update/Insert of this lenth? Other selects can operate concurrently, but updates will have to wait until all selects have finished. Benjamin - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [sqlite] SQLite Browser (Mac OS 10.3)
[EMAIL PROTECTED] wrote: ...on Mac OS 10.3? What error you get? None. That's what's strange about it. It won't even launch. It starts in the dock but dies one second (literally) later. I can run it on MacOSX 10.3.2. However the version of Qt used to compile the binaries does not support Panther officially, so the widgets do not look correct, specially buttons. There might be other subtle issues with Panther. I will try to find time to compile a newer version against the latest Qt, but please post a request directly to the sourceforge foruns if you have not done so. If you are not using the binaries and have compiled from source you probably do not have Qt setup correctly for static compilation, or your environment is not setup correctly to use Qt shared libraries from the Finder. Since this list is dedicated to SQLite I would recommend checking the Qt forums, or posting to the sqlitebrowser message boards. Regards, Mauricio Piacentini - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
[sqlite] Clarification on file locking in web-served apps
Hello, Been reading through the Wiki and FAQ documentation on the SQLite site, and I have one point of confusion In an earlier email, I was given some great numbers indicating that, although SQLite locks an entire DB file, the speeds were pretty impressive (given my read of the numbers you gave me) and would be fine. But I then read some info on the use of Transactions and some detail on the locking behavior, and I'm confused As I read it, SQLite locks the database file as a whole, thus encouraging the use of several DB files to minimize multi-user delays. But then I put that in context of the notes on using Transactions Why the heck would anyone even need Transactions in the first place? If the DB file is locked, no changes can be made, right? So I'm wondering if I am missing a few pieces Is the database file locked more than once during a process? That is, does it get locked as the Update statement is getting a collection of rows with which to apply the intended actions? Does it then release the lock as it prepares the update on this subset of data, and then re-lock when it prepares to write? If so, that would explain the need for a Transacction, as it leaves gaps of access during the transaction. If not, then I am mystified My concern stems from my experience with my day job's T-SQL server where there are occasional Select stored procedures and some stored procedures with both Select and Update/Insert blocks that take as long as a minute or two to process. We have some clients represented in our database with years of clientele, and with hundreds of customers per week or even per day. Ignoring Transactions for a second, if I have such a Select, will every user ben locked behind a wall until the Select for user 1 is complete? And if this is not the case for Select, will it be so for Update/Insert of this lenth? My uses of SQLite, via the upcoming PHP5, are not intended for any such huge database extremes, but as in my earlier email, I do want to get a better grasp of its limitations. Since no public server is yet serving PHP5 pages (still in Beta), I can't really test it myself. Thanks for taking the time to help, ___ Vania Smrkovski -- Vania Smrkovski http://www.pandorasdream.com - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
[sqlite] compression
Has anyone implemented compression for sqlite? If so can you give me some tips on where/how? At this point I am guessing it would need to be done at the page level - but other than that - I am sort of lost. -David - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [sqlite] SQLite Browser (Mac OS 10.3)
At 12:27 PM -0700 1/14/04, Wade Preston Shearer wrote: >Yes... in OS X, everything that happens is written on in an app called Console. I >write the author a while back too and he asked that I attempt to launch it again with >Console running and then send him whatever errors/messages appear, but... >strangely... I am still getting nothing in the Console... as I did then. I use a Mac myself, though currently it is on 10.2.6. To my knowledge, Console doesn't report *everything* that happens. I believe it shows the text that is "printed to stderr" by applications. Or at least it shows a lot of OS-detected problems. For example, if the application you are launching dies because it can't find a shared library it needs, that will report in the console. Or it did with a different app I tried. As strange as it sounds, there is something else you should check, and that is whether any *other* applications also die on launch, especially ones that worked fine before. If you come to the point where anything you open tends to die immediately, that indicates an OS problem (I use this term broadly); usually saving changes in already open apps and then doing a normal restart will restore stability and let things launch then. Whereas, if only one app fails but the others are fine, then the app would be the one with the problem. -- Darren Duncan - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
[sqlite] Close() and file locks...
After the 2.8.10 release ... "This version fixes a critical locking bug in Unix. It turns out that any call to close() clears all locks on file that was closed (who knew?) which then left the database vulnerable to corruption from other processes. That bug has been cleared by embargoing all close() calls until all locks of been released." I have made some investigation... From "Advanced Programming in the UNIX Environment" by R. Stevens: Section 3.5 on page 51 "close Function": ... Closing a file also releases any locks that the process may have on the file. Section 12.3 on page 373 "Implied Inheritance ad Release of Locks": ... Locks are associated with a process and a file. This has two implications. The first is obvious: when a process terminate all its locks are released. The second is far from obvious: whenever a descriptor is closed, any locks on the file referenced by that descriptor for that process are released. This means that if we do the following four steps: fd1 = open(pathname, ...); read_lock(fd1, ...); fd2 = dup(fd1); close (fd2); after the close (fd2) the lock that was obtained on fd1 is released. The same thing would happen if we replaced the dup with open, as in: fd1 = open(pathname, ...); read_lock(fd1, ...); fd2 = open(pathname, ...); close (fd2); to open the same file on another descriptor. Hope this can help to better understand this not very know "bug". Regards, Marco Bambini - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
RE: [sqlite] web-based admin utilities
Hi, I've done one in VB.NET and it's here http://sourceforge.net/projects/dotnetsqliteadm/ Regards Greg -Original Message- From: Wade Preston Shearer [mailto:[EMAIL PROTECTED] Sent: Thursday, 15 January 2004 6:01 AM To: [EMAIL PROTECTED] Subject: [sqlite] web-based admin utilities Is anyone aware of a web-based admin utility for SQLite similar to phpMyAdmin? I found one... .http://sqlitemanager.sourceforge.net/ ...but it is not in English and doesn't look very impressive. wade - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED] - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
[sqlite] sqlite command-line utility (was: manual? documentation?)
Jon, you're awesome. Thank you! Wade, although your question isn't phrased like this, it seems to be "Where can I find good documentation on using SQL?" Whether you use the command-line, or are connecting to SQLite through PHP is irrelevant. The syntax for adding, deleting, modifying and viewing data is identical--you have to use basic SQL commands. The command-line utility simply lets you type your SQL statements directly. Ah! Okay... that makes sense now. I never imagined that the command-line utility used the same commands. One more question if I may: What does the... "(one varchar(10), two smallint)" ...in the following example... "sqlite> create table tbl1(one varchar(10), two smallint);" ...mean/do? wade - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [sqlite] SQLite Browser (Mac OS 10.3)
> Yes... in OS X, everything that happens is written on in an > app called Console. I write the author a while back too and he > asked that I attempt to launch it again with Console running > and then send him whatever errors/messages appear, but... > strangely... I am still getting nothing in the Console... as I > did then. Then I suggest to send a detailed error description the QtForum guys. There are also Trolltech employees around there... I dont know what to do now. sorry. Greets -- Linux is like a wigwam - no gates, no windows and an apache inside. - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [sqlite] manual? documentation?
See: http://sqlzoo.net/ A Gentle Introduction to SQL e Wednesday, January 14, 2004, 2:22:23 PM, you wrote: > Been all through the wiki and didn't find any > first-time-get-you-started-basic-how-to. Thanks though. - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [sqlite] manual? documentation?
Are there any manuals or further documentation for SQLite than what is found on sqlite.org? I assume that most the database interaction stuff is pretty straight forward for individuals with database administration experience, but SQLite is my first database. Most of the documentation is for advanced and/or special operations. I am looking for a tutorial that simply lists the "how-to" of adding, manipulating, purging data from a database. I have successfully created databases with tables and rows and am making my way around the command-line access program. Hello, you can use any SQL '92 tutorial. "SQlite ... Implements most of SQL92." You only have to lookup this page [1] and compare it with the stuff you have learned ;) I just realized that I could phrase my question better. I am looking for a tutorial and/or how-to for using the sqlite command-line utility, not for writing scripts that use the SQLite engine to work with a database. - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [sqlite] SQLite Browser (Mac OS 10.3)
> None. That's what's strange about it. It won't even launch. It > starts in the dock but dies one second (literally) later. I am not really familar with Macstuff. In Qt there is something like qDebug. QDebug sends Debugmessages to stderr. Perhaps you start sqlitebrowser from the commandline and give us the output. The author of the programm is away I think. I wrote him a email for ages and got no answer... Greets -- Linux is like a wigwam - no gates, no windows and an apache inside. - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [sqlite] SQLite Browser (Mac OS 10.3)
Has anyone successfully run SQLite Browser... http://sqlitebrowser.sourceforge.net ...on Mac OS 10.3? What error you get? None. That's what's strange about it. It won't even launch. It starts in the dock but dies one second (literally) later. - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [sqlite] manual? documentation?
> Are there any manuals or further documentation for SQLite than > what is found on sqlite.org? > > I assume that most the database interaction stuff is pretty > straight forward for individuals with database administration > experience, but SQLite is my first database. Most of the > documentation is for advanced and/or special operations. I am > looking for a tutorial that simply lists the "how-to" of > adding, manipulating, purging data from a database. > > I have successfully created databases with tables and rows and > am making my way around the command-line access program. > > Hello, you can use any SQL '92 tutorial. "SQlite ... Implements most of SQL92." You only have to lookup this page [1] and compare it with the stuff you have learned ;) greets [1] http://sqlite.org/omitted.html -- Linux is like a wigwam - no gates, no windows and an apache inside. - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [sqlite] manual? documentation?
If you haven't already, go to the bottom of the main page at sqlite.org and click on the link to the wiki; then click on contents. - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [sqlite] SQLite Browser (Mac OS 10.3)
> Has anyone successfully run SQLite Browser... > > http://sqlitebrowser.sourceforge.net > > > ...on Mac OS 10.3? Hi, not but you could ask there: www.qtforum.org. SqliteBrowser is written with the Qt toolkit. So the people there will help you. There are also a few guys from the macside. What error you get? Greets -- Linux is like a wigwam - no gates, no windows and an apache inside. - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [sqlite] looking for help
correct example:
##
F::FSqlite sql;
sql.sqliteConnect( "testdb" );
sql.sqliteQuery( "SELECT * FROM table" );
while( mySqlObject.dataSetIsLeft( ) ) {
cout << sql.result[ "col_1" ]
cout << sql.result[ "col_2" ]
}
##
Greets Christian
--
Linux is like a wigwam - no gates, no windows and an apache
inside.
-
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
[sqlite] web-based admin utilities
Is anyone aware of a web-based admin utility for SQLite similar to phpMyAdmin? I found one... .http://sqlitemanager.sourceforge.net/ ...but it is not in English and doesn't look very impressive. wade - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
[sqlite] SQLite Browser (Mac OS 10.3)
Has anyone successfully run SQLite Browser... http://sqlitebrowser.sourceforge.net ...on Mac OS 10.3? - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
[sqlite] looking for help
Hello,
perhaps you know: At the moment I am developing a CGI framework
with C++. Now I have implemented a sqlite class. You can do
something like this:
##
F::FSqlite sql;
sql.sqliteConnect( "testdb" );
sql.sqliteQuery( "SELECT * FROM table" );
while( mySqlObject.dataSetIsLeft( ) ) {
cout << mySqlObject.result[ "col_1" ]
cout << mySqlObject.result[ "col_2" ]
}
##
I think this is a very simple database handling. There are also
many other classes like:
The FFile class for the filehandling.
The FCookie class for the cookiehandling.
The FApplication class for parsing the query string and for some
string functions.
The FSearch class for searching the own homepage.
If you are interested - especially in featuring the sqlite class
together with mine let me know.
Greets Christian
--
Linux is like a wigwam - no gates, no windows and an apache
inside.
-
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
[sqlite] Re: random record
On Wednesday 14 January 2004 09:32 am, Caleb Groom wrote: > Does sqlite have some way to fetch a random record? I'm looking for > something similar to MySQL's 'select * from tbl order by rand() limit > 1'. Same thing: SELECT * FROM tbl ORDER BY random() LIMIT 1; works for me. - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
[sqlite] SQLite - VB
Hi all, I am a quite new user of SQLite; I liked it since the first day that I tryed some examples, and after reading the documentation about it; The reason why I'm asking for help is the following: I am getting learning C++ step by step, because that is the language that I will use in the future, but at the moment I am still developing using VB6. I have seen that there are more possibilities to interact SQLite with VB6: 1 - ODBC drivers, 2 - AGS_SQlite, 3 - API 4 - ? I will ask you: can you tell me please which are the different advantages or difficulties between those different ways, using them to interact SQLite with with VB6? I have to do a lot of work on converting my projects from Access to SQLite, and I would like to begin in the right way. So I thought that this will be the right place where to ask such important details. Many thanks in advance, regards Giuliano Isacchi Firenze - Italy - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
[sqlite] Optimizing a query
Michael Hunley wrote: At 11:12 AM 1/14/2004 -0500, D. Richard Hipp wrote: SELECT count(*) FROM table WHERE col1>'abc' AND col1<'xyz'; In the original query, the result was indeed a count(*) so no access to the data we required there. But access to the data was required in order to evaluate the WHERE clause. So it is still O(NlogN). What is different between his where clause and the one you cite as an example that only takes O(N)? Is it just that in your example col1 is (part of) the index? So, wouldn't Ken be able to do the same, except that he needs to step through two indices? In the example above, both terms of the WHERE clause are satisfied by an index and are removed from the WHERE clause. In Ken's code, he had an additional term: (p.stop!=o.stop OR pstart!=o.start) That additional term cannot be satisfied by the index and must be evaluated by looking up the record in the main table. Without that additional term, it would be possible, in theory, to run the join in O(N) time. But it would require a new join execution strategy which SQLite does not support at this time. -- D. Richard Hipp -- [EMAIL PROTECTED] -- 704.948.4565 - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [sqlite] Re: [inbox] Re: [sqlite] Optimizing a query
At 11:12 AM 1/14/2004 -0500, D. Richard Hipp wrote: SELECT count(*) FROM table WHERE col1>'abc' AND col1<'xyz'; In the original query, the result was indeed a count(*) so no access to the data we required there. But access to the data was required in order to evaluate the WHERE clause. So it is still O(NlogN). What is different between his where clause and the one you cite as an example that only takes O(N)? Is it just that in your example col1 is (part of) the index? So, wouldn't Ken be able to do the same, except that he needs to step through two indices? That, it seems to me, is the crux of the issue. I don't mean to belabor this issue, but I am curious as to the workings. michael - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [sqlite] Re: [inbox] Re: [sqlite] Optimizing a query
Michael Hunley wrote: At 10:37 AM 1/14/2004 -0500, D. Richard Hipp wrote: In some cases you can avoid the O(logN) lookup of the main table entry and just use the index. For example: SELECT count(*) FROM table WHERE col1>'abc' AND col1<'xyz'; Wasn't that the original question, Ken? Except it was a count(*) on a JOIN. Dr Hipp, would the same optimization apply if it is stepping through two indices? In which case Ken should see a huge speed improvement to his original question by adding an index and updating to the latest SQLite (after you release 2.8.11, that is ;). In the original query, the result was indeed a count(*) so no access to the data we required there. But access to the data was required in order to evaluate the WHERE clause. So it is still O(NlogN). But it is also still really fast. Do this: Run the same query on SQLite, PostgreSQL, MySQL, and Oracle and see which one finishes first. I've not tried it so I don't know what will happen. But I'm guessing SQLite will be the clear winner. Somebody please correct me if my guess is wrong. -- D. Richard Hipp -- [EMAIL PROTECTED] -- 704.948.4565 - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
[sqlite] Re: [inbox] Re: [sqlite] Optimizing a query
At 10:37 AM 1/14/2004 -0500, D. Richard Hipp wrote: In some cases you can avoid the O(logN) lookup of the main table entry and just use the index. For example: SELECT count(*) FROM table WHERE col1>'abc' AND col1<'xyz'; Wasn't that the original question, Ken? Except it was a count(*) on a JOIN. Dr Hipp, would the same optimization apply if it is stepping through two indices? In which case Ken should see a huge speed improvement to his original question by adding an index and updating to the latest SQLite (after you release 2.8.11, that is ;). Just trying to keep track. michael - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [sqlite] Optimizing a query
Williams, Ken wrote: So, no way to make it O(N)? If the two indexes could be Retrieving a single record from a BTree is an O(logN) operation. Doing so N times gives O(NlogN). Oh, I thought it was also possible to step straight through an index, You can step straight through the index in linear time. But for each index entry you encounter, you have to look up a record in the main table in order to get the data. It's the second step, the table lookup, that takes O(logN). In some cases you can avoid the O(logN) lookup of the main table entry and just use the index. For example: SELECT count(*) FROM table WHERE col1>'abc' AND col1<'xyz'; In this case, since you are never using any data from the table, just counting entries, it is sufficient to step through through the index and the operation runs in linear time. As recently as 2 weeks ago, SQLite would go ahead and look up the main table entry even though the data was needed. That extra lookup was optimized out with check-in [1165]. http://www.sqlite.org/cvstrac/chngview?cn=1165 After check-in [1165], queries such as the above are about 10x faster on large tables. -- D. Richard Hipp -- [EMAIL PROTECTED] -- 704.948.4565 - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
RE: [sqlite] Optimizing a query
> -Original Message- > From: D. Richard Hipp [mailto:[EMAIL PROTECTED] > Sent: Wednesday, January 14, 2004 9:22 AM > To: Williams, Ken > Cc: [EMAIL PROTECTED] > Subject: Re: [sqlite] Optimizing a query > > > Williams, Ken wrote: > > > > So, no way to make it O(N)? If the two indexes could be > iterated together, > > as in the following pseudocode, it would seem to be an O(N) > operation. > > > > Retrieving a single record from a BTree is an O(logN) operation. > Doing so N times gives O(NlogN). Oh, I thought it was also possible to step straight through an index, but I guess I was mistaken. -Ken - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [sqlite] Optimizing a query
Williams, Ken wrote: CREATE INDEX whatever ON output(verb_id,tag); That will make it O(NlogN) instead of O(N**2). So, no way to make it O(N)? If the two indexes could be iterated together, as in the following pseudocode, it would seem to be an O(N) operation. Retrieving a single record from a BTree is an O(logN) operation. Doing so N times gives O(NlogN). O(N) would be possible if you were to step straight through both tables in native order (INTEGER PRIMARY KEY order) without having to do a search for each record using an index. But that would only work, of course, if the join was on the INTEGER PRIMARY KEY of both tables. And even then, SQLite doesn't do that particular optimization. -- D. Richard Hipp -- [EMAIL PROTECTED] -- 704.948.4565 - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
RE: [sqlite] Optimizing a query
> -Original Message-
> From: D. Richard Hipp [mailto:[EMAIL PROTECTED]
> Sent: Tuesday, January 13, 2004 6:17 PM
> To: [EMAIL PROTECTED]
> Subject: Re: [sqlite] Optimizing a query
>
>
> > Can anyone suggest a good way to optimize the following query?
> >
> > SELECT count(*) FROM propositions p, output o
> > WHERE p.verb_id=o.verb_id
> >AND p.tag=o.tag
> >AND (p.stop!=o.stop OR p.start!=o.start);
> >
>
> CREATE INDEX whatever ON output(verb_id,tag);
>
> That will make it O(NlogN) instead of O(N**2).
So, no way to make it O(N)? If the two indexes could be iterated together,
as in the following pseudocode, it would seem to be an O(N) operation.
P_INDEX:
while ($p_entry = p_index.next) {
while ($o_entry = o_index.next) {
if ($o_entry == $p_entry) {
...do the rest of the query criteria...
} elsif ($o_entry > $p_entry {
next P_INDEX;
}
}
}
-Ken
-
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
