[KPhotoAlbum] Idea for quick search feature
shawn-kimdaba at willden.org
Wed Apr 25 16:39:41 CEST 2007
On Wednesday 25 April 2007 02:12:35 am Jesper K. Pedersen wrote:
> I like the idea, but do have a few concerns/ideas/whatever.
> - First, It might be usefull with some way to specify wheather searching
> should be incremental, or when enter is pressed (in the case for searching
> taking 20 sec :-)
I've been struggling with that as well. My current thought is that I'd like
it always to be incremental, but to see if we can apply enough cleverness (uh
oh!) to keep it responsive.
I think even a fairly straightforward implementation will be pretty fast for
the XML backend, especially since I expect once the SQL backend is fully
functional, everyone with large databases will move to it.
Still, I do have a couple of ideas about making the queries fast for XMLDB.
The first, and most obvious, is that the in-memory incremental searches will
be a process of successive refinement. Adding another character to the
search string will only narrow the search, so there's no need to search the
whole database again. This means that, usually, only the first few
characters you type will be slow.
To address this slowness, I'm thinking that the search engine should run in a
separate thread. Obviously, that poses some potentially serious
concurrent-access issues. I haven't yet looked into what locking
infrastructure is in place to avoid them.
(Aside: As a future refinement, it might be good to look into the possibility
of searching in multiple threads. Search is easily parallelizable, and given
the trend towards multi-core machines, in a few years it could be a big help.
Both of my computers now, laptop and desktop, are dual-core, and I wouldn't
be surprised to have a quad-core by 2010).
Another possibility I'm experimenting with is to use a patricia trie to
accelerate tag searches. Constructing the trie would take a little time, but
I'm more concerned about how much memory it would consume, so that's what I'm
fiddling with now. It's also possible that using a trie rather than a
standard tree won't gain much. In any case, if those approaches prove
workable, they should make searching the tags very fast. One downside of
using a trie (or a tree) is that it will search tags by prefix. That's not
so bad, though, and it's what the search bar currently does for
Anyway, I'm fairly confident that as-you-type searching for in-memory
databases is feasible, although the thumbnails/counts displayed may be slow
to update for the first few letters.
SQL databases are another can of worms, both because they're going to be a lot
bigger, and because of the nature of SQL queries. Allowing interactive,
incremental searching with a SQL database is either easier or harder
depending on your point of view, because there's just not very much you can
The only things I can see that we can do are:
1. Run queries in a separate thread. Pleasantly, there are no concurrency
issues with this.
2. Delay execution of queries. Perhaps we can wait until the user stops
typing (more precisely, hasn't typed a character for some period of time) or
hits enter before initiating the query. The delay could be automatically
tuned based on how long queries take, because there's little point in having
a delay that's significantly longer than the query would have taken.
3. Try to optimize the queries, by structuring them well and by making sure
that all applicable indexes are in place.
Any other ideas?
> - Imagine this use case:
> I type June in the search bar.
> I then see I have 2000 images from June, and want to start drilling
> I therefore press persons
> Will the search bar still say June? and if so, can I now not search in the
> persons list?
Good point, and a blindingly obvious one that I somehow missed. I'm liking
Angel's idea about adding the click-selected criteria to the search bar more
In that case, your scenario would go like this:
1. You type June, and see you have 2000 images.
2. You click "People"and the list of people categories comes up. The search
bar contains "June People:" and your cursor is positioned after the colon.
3. You type "s" and the list is narrowed to names beginning with s.
4. You click on "Shawn Willden" and the search bar contains 'June
People:"Shawn Willden"' and you get back to the "counts" view, with the
Obviously, you could also have just typed the search string to begin with. As
a power user and fast typist, that's probably what I would have done. For
novices and those who prefer the mouse, they can construct queries by
clicking -- and in the process the app will teach them how to construct query
strings, leading them towards power-userhood.
> Jesper (Who still only have internet when he goes to a bar)
Well, that should make for some interesting posts!
Shawn (currently sitting on a beach in Daytona Beach, Florida)
More information about the KPhotoAlbum