scd
commented
11 years ago On 9/08/2013 6:28 PM, Brendan Heywood wrote:
On Fri, Aug 9, 2013 at 4:13 PM, Simon Dale scd@thecrag.com wrote:
On 9/08/2013 2:32 PM, Brendan Heywood wrote:I think it's pretty important that the new server is up to date, prod's age seems to be holding back a lot of possibilities. I know. To do this safely it means we have to have another server. Remember how it took 3 days to get your dev operational again when we upgraded.Basically I had expected to have done this by now, but I also expected the iphone app to have been out and the facebook stuff to have been done months ago. I think I have found a more cost effective provider in Germany.These are definitely low hanging fruit, but I'd also like to know the roughly gap of time between 4.5 seconds and 13.8 seconds in apache land. Perl land shouldn't be doing that much processing, so I'm guessing the rest is also in the DB but probably split between a bunch of smaller queries. In prod did you know what the background load was? ie do you think that 13.8 seconds is due to load from others, or load from the same page doing other stuff? I think the key here is setting the slow log threshold on prod to something like 200ms and collecting it for a while. It's also useful to set it to zero, and take a black box approach to seeing what a page load actually does, often you find a lot of redundant stuff that can be culled back. Still even with all of this it's still a long way from snappy. Ideally I'd want to keep focusing on making the initial query faster rather than just looking into more caching options. One possibility is having TLC level stats, ie each TLC has a tick count for each climber. Under TLC level we use the normal query which seems to run in quite acceptable times for these. Then above TLC only join the collector table down the TLC's and then join to the summary stat. It would be good to get a feel for how many nodes and how many ticks that query can handle before it gets above say 200ms, it might be better to collect roughly at bottom level crags instead of TLC's. Or instead of linking it to node type but collect it whenever a node gets to X ticks which would be more efficient and robust and independent of type changes. If we are going to do TLC stats we might as well roll it up to all areas. On average for every route there are about 8 collector nodes. I already have a mechanism to manage this, with the statistics package. It will be able to handle incremental updates to account/node stats. There is a bit of configuring to do. We would also have to consider how we would segment - eg ticks, onsights, boulders, etc as each could be leaderboards in their own right.If that's easier then great, I was thinking in terms of the most bang for buck vs DB size. For now pragmatically the most important page is the climbers tab as it has to be super quick and we're only interested in totals, not the details. Facets are a different matter though but I'm sure benefit heaps from just that total stat first, as you could filter on it, and then filter that result set to get say just onsights.
We are really talking star schema design here which I think leads to a very involved discussion. Let's have this discussion sometime after the next release.The other thought it to add an index order to the collector nodes so that join can be much quicker. Ie give every leaf node a global ordered number, each node above stores the range of nodes. The numbering would be fairly sparse so it means reparents often don't need major re-allocations. This could also be stacked on top of the previous speedup.You can skip most of this if you want and jump to the last bit, most of it is my brain dump as I read and explored... There are about 3-4 major ways of working with tree data in SQL, Adjaceny list, Modified Preorder Tree Traversal, blah etc and they have different trade off's for insert vs read vs reparent. Oracle has a built in hierarchical query and index type which is super fast. I'm not sure which model it used internally. As a bit of history, when I build my own tree node DB for the first Beulah using Cake I used the TreeBehaviour which implements the MPTT one: http://book.cakephp.org/2.0/en/core-libraries/behaviors/tree.html What I had in mind is similar but more flexible, instead of the sets being continuous they are sparse so that it is much easier to work with reparents. Imagine that we had a simple business rule like no node could have more than 256 characters. Then we could represent any node as a string of bytes from the world to it. Australia was the first in the world it could be 1 NSW might be 2nd in Aus so it is 12 New England could be 7th in NSW so it is 127 A boulder in gara could be 127432 An the actual route could be 1274325 Now to find all routes under Gara it is simply a "like '1274%' which using a btree index is super fast. It completely removes the whole collector table and join which is the expensive one. The key thing is that the collector table isn't ordered, so it has to use the index O(n) times while the path method is O(1) Reparents would mostly involve just swapping out the substring of a set of routes which is pretty quick. If this is slightly out of date it's not the end of the world and there is currently a bit of lag of weird stats after big reparents, we can live with that. By sparse I mean that we purposefully make lots of gaps so that most reparents don't require changing any other routes or nodes. So in a cliff with only 20 routes their numbers could be 1,4,7,10 etc so you can insert new routes without changing the others, so most inserts will be instant. If you do insert say 5 routes it's not too much juggling to push the adjacent ones over. We could even have a process could comes along and respaces them as needed to keep them balanced. Routes could be sparse vertically too, so we could set some conservative rules around regions and TLC depths, for example: World Region level 1 Region level 2 Country Region level 3 Region level 4 Region level 5 TLC Whatever Lets say Asia is '3' and Thailand is its 5 child, instead of being 35 it would be 305. Because we always know which slot a country is in we can speed up certain country live lookups, and the same applies to TLC's. But the real flexibility here comes from a country being able to have quite a lot of internal region creation and reparenting done with less impact on it's siblings and cousins. After a bit of digging I found an oracle article which calls this idea a Materialized Path, I think it's also called path enumeration. But I think my idea is slightly different as I was thinking of using the order value at each position rather than the id of the ancestor node. To me the whole point of the path is to directly index it using a B-tree, you can't do that if you use the id method. From a maths point of view I think my string / path method is actually very close to a nested set, if you think of each char in the path as another decimal place of precision. We'd be just using a decimal number instead of rational fraction. This is the best summary of the big picture options I've found so far: http://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database So you collector table is called a 'closure table' in some places I've been reading. This slide deck gives a pretty good comparison on them all, especially slide 69: http://www.slideshare.net/billkarwin/models-for-hierarchical-data ... God, I've just read a paper by some dude at Oracle on Nested Interval Trees with Continued Fractions. That is NOT something we want to hand roll. I guess one great thing about oracle and friends is that they can swap out these with increasingly faster implementations and we just don't know and get the benefit for free. So I'm still thinking that something like the path is the simplest to understand and has the most power. If we reparent a tree, the really critical thing is that afterwards we also propagate the new path values to the ascents table and other tables that we have facet queries for. This was the ascents facet query won't have any joins at all needed to do the /at/1234/ filtering which is what's killing us.
Can't picture what you mean here for leaderboards, but maybe useful for faceted search. Leaderboard is essentially and ordered list on accounts, if we have some star schema using some sort of node/account table then there is little to join. If we then have an index on each of the leaderboard stats then this should be fairly snappy. The table may look something like: AccountNodeStatistics: Account Node Ascents KarmaI think stopping here is enough
Onsights Trads Boulders The problem with this approach is that we have to predefine all the the account/node statistics we are rolling up. For ascent and route faceted search I would suggest a different approach where maybe each route and ascent has say 16 ancestor nodes as separate fields on each record. This would mean there would be no collector join for the facets and hence much faster. For example a route search in Australia would be a search trigger a search for Level1 nodes (World is level 0, and Australia is level 1).Ok only just got down to reading this. Essentially this solves the exactly same problem as the path above and in almost the same way. It means we'd introduce a hard limit of the depth of the node tree, but that's ok. I like that we've both more or less come up with the same solution, to me that's a signal we're on the right track. I don't there there is much between then, both would take about the same space. I prefer your solution because it's also got referential integrity, so it would be easier to find all grade 6 climbs under Australia, and then find their TLC. My way will have a slightly awkward join with a string subset. For this reason I think we should also combine this with the predefined slots idea, so country is always slot 2, and TLC is always slot 6, and unneeded slots are null as needed.
For both faceted search and leaderboard search the bottleneck is the AncestorCollector join. Maybe this is a common problem and there is some sort of index I am not doing right. This seems to be a common theme which comes up: http://en.wikipedia.org/wiki/Nested_set_model The nested interval model may actually be even more helpful. http://en.wikipedia.org/wiki/Nested_intervals Which ever way we go there is potentially a lot of work, so we really need to nut it out and agree on a path forward then test and demonstrate the improvement. The last thing I want is for one of us to do heaps of work and the other say why did you do it that way.cheers Brendan http://thecrag.com/ http://github.com/brendanheywood http://www.thecrag.com/climber/brendanheywood
No virus found in this message. Checked by AVG - www.avg.com Version: 2013.0.3392 / Virus Database: 3209/6562 - Release Date: 08/08/13
brendanheywood
Lot's of details to fill in here (eg delete, merge & reparent nodes).