426166 - Search results change their order after pressing space or further typing

Status: RESOLVED FIXED

(Toolkit :: Places, defect)

Description

[Robert [minotaur 11]]

User-Agent:       Mozilla/5.0 (X11; U; Linux i686; de; rv:1.8.1.13) Gecko/20080325 Ubuntu/7.10 (gutsy) Firefox/2.0.0.13
Build Identifier: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9pre) Gecko/2008033103 Minefield/3.0pre

Sometimes search results in the location bar dropdown list change their order after pressing space to enter a further search term. Not all search results are affected, this seems to happen only for entries with identical frecency. The behavior is especially noticeable if results on positon 1 to 6 (visible without scrolling) change their place with results on position 7 to 12.

Reproducible: Always

Steps to Reproduce:
1.Create two bookmarks: http://a1/, http://a2/
2.Type a
3.Press space
Actual Results:  
The order in step 2 is: a2, a1. After step 3: a1, a2.


Regression range:
20080322_2244_firefox-3.0b5pre.en-US.linux-i686.tar.bz2 works
20080322_2340_firefox-3.0b5pre.en-US.linux-i686.tar.bz2 fails

Bonsai query:
http://bonsai.mozilla.org/cvsquery.cgi?module=PhoenixTinderbox&date=explicit&mindate=1206251040&maxdate=1206254399

Comment 1

[Robert [minotaur 11]]

It's not restricted to pressing space, i've also seen this if previous search results with identical frecency are reused for the first time during further typing.

STR:
1.Create two bookmarks: http://aaa1/, http://aaa2/
2.Type a (a): aaa2, aaa1
3.Type a (aa): aaa1, aaa2
4.Type a (aaa): aaa1, aaa2

Comment 2

[Ed Lee :Mardak]

This is related to the adaptive learning. It probably learned that you previously selected "aaa2" when typing "a", but when you type "aa", it doesn't know anything about it, so it doesn't give adaptive learning preference to "aaa2" anymore.

Comment 3

[Robert [minotaur 11]]

I deleted the inputhistory with "DELETE FROM moz_inputhistory;" before i tried to reproduce it. The regression range indicates that it is related to the incremental search updates.

Comment 4

[Robert [minotaur 11]]

I tried it in a new profile again and it seems to depend on the order of the entries in the places.sqlite file. I only see it if i create first the bookmark aaa1 and then aaa2 (or a1 and a2).

Comment 6

[Kyle Huey (Exited; not receiving bugmail, old account, do not use)]

Attachment: Make places query stable

This bug is caused by the fact that a sort in SQL is not guaranteed to be stable w/r/t fields not in the ORDER BY clause.  By using the primary key in the ORDER BY clause we can guarantee that the sort is stable w/r/t everything.  This fixes the non-deterministic behavior in the Location Bar seen in this bug.

Comment 7

[Dietrich Ayala (:dietrich)]

Comment on attachment 405972 [details] [diff] [review]
Make places query stable

id should be fine for a tie-breaker, thanks for the fix! can you add a test, or update an existing test to cover this case, and re-request review?

Comment 8

[Shawn Wilsher :sdwilsh]

Can you attach a patch with more context too?

Comment 9

[Kyle Huey (Exited; not receiving bugmail, old account, do not use)]

(In reply to comment #7)
> (From update of attachment 405972 [details] [diff] [review])
> id should be fine for a tie-breaker, thanks for the fix! can you add a test, or
> update an existing test to cover this case, and re-request review?

(In reply to comment #8)
> Can you attach a patch with more context too?

Yeah, no problem.

Comment 10

[Marco Bonardo [:mak] (Away Apr 25 - May 5)]

have you tested this against a big database to be sure it is not a perf killer like bug 412736?

Comment 11

[Kyle Huey (Exited; not receiving bugmail, old account, do not use)]

Attachment: Patch w/test

Addressing comments 7 and 8.

Comment 12

[Kyle Huey (Exited; not receiving bugmail, old account, do not use)]

(In reply to comment #10)
> have you tested this against a big database to be sure it is not a perf killer
> like bug 412736?

I have not tested it on a large database but, at least in theory, there is no reason why sorting by the primary key should have s significant impact on performance.  The reason that bug 412736 was a perf killer is because there are no indexes on the columns that were being used in that sort.  E.g.

EXPLAIN SELECT * FROM moz_places h ORDER BY h.frecency DESC
[28 opcodes returned]

EXPLAIN SELECT * FROM moz_places h ORDER BY h.frecency DESC, h.id DESC
[28 opcodes returned]

EXPLAIN SELECT * FROM moz_places h ORDER BY h.frecency DESC, h.typed DESC
[49 opcodes returned]

Comment 13

[Marco Bonardo [:mak] (Away Apr 25 - May 5)]

i was mostly concerned by the UNION, but being a union all should not make a difference. ok fine by me, the explain is quite clear.

Comment 14

[Dietrich Ayala (:dietrich)]

Comment on attachment 406431 [details] [diff] [review]
Patch w/test

r=me, thanks. sorry for long wait.

Comment 15

[Kyle Huey (Exited; not receiving bugmail, old account, do not use)]

(In reply to comment #14)
> (From update of attachment 406431 [details] [diff] [review])
> r=me, thanks. sorry for long wait.

Thanks!

Comment 16

[Dão Gottwald [:dao]]

http://hg.mozilla.org/mozilla-central/rev/7f76978080a1

Comment 17

[Marco Bonardo [:mak] (Away Apr 25 - May 5)]

Comment on attachment 406431 [details] [diff] [review]
Patch w/test

i think the change is small enough to be considered for 1.9.2, giving back more consistent results is a polish win for the awesomebar.

Comment 18

[:Gavin Sharp [email: [e-mail]]]

Comment on attachment 406431 [details] [diff] [review]
Patch w/test

approval1.9.2 requests aren't currently being monitored, since we're nearing RC freeze and there are too many outstanding requests, so I'm clearing this request. Feel free to re-request approval if you are confident that it's worth drivers' time to consider whether this non-blocker needs to land for 1.9.2 at this stage.

Comment 19

[Mike Beltzner [:beltzner, not reading bugmail]]

Comment on attachment 406431 [details] [diff] [review]
Patch w/test

a192=beltzner, small change, big test.

Comment 20

[Marco Bonardo [:mak] (Away Apr 25 - May 5)]

http://hg.mozilla.org/releases/mozilla-1.9.2/rev/b437bbc7f874