“Too many matches” on lineage browser

sigmen4020 · 2019-05-16 06:13:20

Ok here is a change that has seemingly come out of nowhere, and that is this message popping up on the lineage browser when I search a name. The way it worked before was that you could search up a common first name like Jack, and you would get the recent people who died with that name pop up. But now you get no one pop up with that name, and instead the message “too many matches” and just the recent deaths in general. It seems funny, that if it had so many matches, why couldn’t it bother to show me any of them?

MultiLife · 2019-05-16 10:06:03

Yeah, that sounds silly. At least show the newest batch of Jacks and cut out the rest.

pein · 2019-05-16 10:34:28

you can go from game to family tree then bookmark the site it wont change

http://lineage.onehouronelife.com/serve … id=4474713

the format is same, just you need the id of the character which you can see the next day if it wasn't you or someone from your families then you got to search on the name and substitute ID to this link ID

sigmen4020 · 2019-05-17 09:21:43

Ok, just gonna bump this thread because the “too many matches” thing when searching for a full name. What is the point of using the search function on the lineage browser, when you just get “too many matches”, and then not bother show me a single one of these plentiful matches?

Edit: I searched up Eve Aaberg.

Last edited by sigmen4020 (2019-05-17 09:22:37)

jasonrohrer · 2019-05-17 16:18:43

Unfortunately, the lineage data has gotten so big that it had gotten painfully slow to search for very common names.

The problem is that the displays on the front page are sorted by another criteria (recentness). So in order for MySQL to do this, it needs to find all records that match the name (fast, because the names are indexed) and then SORT those records by the other criteria (really slow, if there are tons of records matching that name), before finally trimming off just the first page of records and showing it to you.

Essentially, this is a double-sort. Maybe there's a way to make this fast through compound indexes, but I haven't had time to figure it out yet.

There also may be a problem with the fact that there are multiple lists on the front page, each offering lives that match some criteria. So if we want to fast search those by names too, we'd need a compound index for names plus each of those criteria. I.e., it's pretty complicated.

The reason I finally fixed this was that searching for something like "Eve" was bringing the whole thing to its knees.

Maybe the cutoff is too low at 1000...

jasonrohrer · 2019-05-17 17:09:29

Here's an example from the MySQL Slow Query log:

Tcp port: 3306  Unix socket: /var/run/mysqld/mysqld.sock
Time                 Id Command    Argument
# Time: 2019-05-17T17:06:31.934547Z
# User@Host: jcr13_lineageU[jcr13_lineageU] @ localhost []  Id:  4242
# Query_time: 10.589970  Lock_time: 0.000291 Rows_sent: 5  Rows_examined: 245360
use jcr13_lineage;
SET timestamp=1558112791;
SELECT lives.id, display_id, player_id, name, age, generation, death_time, deepest_descendant_generation, servers.server FROM lineageServer_
lives as lives INNER JOIN lineageServer_users as users ON lives.user_id = users.id INNER JOIN lineageServer_servers as servers ON lives.serv
er_id = servers.id   WHERE lives.name LIKE 'Eve A%'  AND death_time >= DATE_SUB( NOW(), INTERVAL 1 DAY ) ORDER BY lineage_depth DESC, death_
time DESC LIMIT 5;
# Time: 2019-05-17T17:08:00.332541Z
# User@Host: jcr13_lineageU[jcr13_lineageU] @ localhost []  Id:  5740
# Query_time: 87.103440  Lock_time: 0.000221 Rows_sent: 5  Rows_examined: 2253602
SET timestamp=1558112880;
SELECT lives.id, display_id, player_id, name, age, generation, death_time, deepest_descendant_generation, servers.server FROM lineageServer_
lives as lives INNER JOIN lineageServer_users as users ON lives.user_id = users.id INNER JOIN lineageServer_servers as servers ON lives.serv
er_id = servers.id   WHERE lives.name LIKE 'Eve A%'  AND death_time >= DATE_SUB( NOW(), INTERVAL 1 DAY ) ORDER BY generation DESC, death_tim
e DESC LIMIT 5;

One of them took 87 seconds... you can see how that's a problem!

jasonrohrer · 2019-05-17 19:32:01

FYI, I'm working through the root of this problem here:

https://stackoverflow.com/questions/561 … here-match

sigmen4020 · 2019-05-17 19:37:10

jasonrohrer wrote:

FYI, I'm working through the root of this problem here:
https://stackoverflow.com/questions/561 … here-match

Glad to hear that this issue is being looked at.

jasonrohrer · 2019-05-17 19:48:01

Anyway, here's the fundamental problem, and I don't think there's a solution here. Look at this query:

SELECT name FROM lineageServer_lives WHERE  name LIKE 'Eve A%' ORDER BY generation DESC LIMIT 5;

There are 4 million lives records in the table. "Eve A" matches about 8000 of them. Here, we want to show the 5 people with matching names who have the deepest generation number.

There's an index on both the name column and the generation column, so sorting by either is fast.

The question: How should MySQL approach this query?

Either it sorts by name first (fast, using index), finds 8000 matching results, and then sorts the results by generation number (slow, not using index). Or it sorts by generation first (fast, using index), resulting in 4 million sorted records, and then searches through those for five matches for "Eve A". You can imagine that being slow too, if "Eve A" is rare, which it is. So, both approaches are slow.

If we search for a less common name, like "Eve Aa", it becomes much faster, because there are only 1400 matching records, and MySQL can easily sort those by generation (sorting 1400 is faster than sorting 8000).

On the other hand, if we search for something really common, like "Eve", we match hundreds of thousands of records. In that case, MySQL can sort by generation first, and then very quickly find the first five matches for Eve, because there are so many of them.

Actually, the REAL problem is that, when sorting by generation, all the "Eve A" records are at the bottom of the list. So we have to walk through a lot of records (millions) until we get there.

Thus, it's not all name searches that are bad... but Eve name searches in particular, because of the way they intersect with other aspects of the data.

jasonrohrer · 2019-05-17 20:32:44

By forcing the index on the name column, I improved performance for more common names, allowing me to up the limit to names that hit 30,000 lives. So name search is pretty much working normally again.

sigmen4020 · 2019-05-17 21:29:49

Nice Jason. Thanks for fixing the issue. I searched up Eve Aaberg again and can confirm that it’s been fixed.

One Hour One Life Forums

#1 2019-05-16 06:13:20

“Too many matches” on lineage browser

#2 2019-05-16 10:06:03

Re: “Too many matches” on lineage browser

#3 2019-05-16 10:34:28

Re: “Too many matches” on lineage browser

#4 2019-05-17 09:21:43

Re: “Too many matches” on lineage browser

#5 2019-05-17 16:18:43

Re: “Too many matches” on lineage browser

#6 2019-05-17 17:09:29

Re: “Too many matches” on lineage browser

#7 2019-05-17 19:32:01

Re: “Too many matches” on lineage browser

#8 2019-05-17 19:37:10

Re: “Too many matches” on lineage browser

#9 2019-05-17 19:48:01

Re: “Too many matches” on lineage browser

#10 2019-05-17 20:32:44

Re: “Too many matches” on lineage browser

#11 2019-05-17 21:29:49

Re: “Too many matches” on lineage browser

Board footer