On 3/21/2010 5:22 PM, Max Vlasov wrote: > On Sun, Mar 21, 2010 at 3:50 PM, Tim Romano<tim.rom...@yahoo.com> wrote: > > >> For someone who doesn't read C, could someone who knows please describe >> the SQLite INTERSECT algorithm? What optimizations are available to it? >> Does INTERSECT have to assume that neither vector is pre-sorted? Here's >> the background of my question: >> >> >> > Tim, > maybe drh answer on my question regarding INTERSECT could help? > > http://www.mail-archive.com/sqlite-users@sqlite.org/msg49646.html > > Max > _______________________________________________ >
Thanks, Max. What I was wondering, in particular, is whether an intersection using some form of "minimal perfect hashing" [for those who, like me, are novices at this, here's some discussion: http://en.wikipedia.org/wiki/Perfect_hash_function] of two vectors of rowids would be less expensive than a single index read (against index on Latitude, say) followed by a base table read to compare the longitude values of each of the candidate rows. Assuming a table where Latitude column and Longitude column each have their own index: perform select #1 which returns the rowids of rows whose latitude meets criteria INTERSECT perform select #2 which returns the rowids of rows whose longitude meets criteria You could build a perfect hash from one of the vectors, then iterate the other vector and ask the hash whether it contains the current iterator value; if yes, add value to the intersection set. I do not have any idea of the costliness (RAM, CPU, DISK I/O) of such an approach. Regards Tim Romano _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
