search

Abstrct / Schemaverse

The Schemaverse is a space-based strategy game implemented entirely within a PostgreSQL database. Compete against other players using raw SQL commands to command your fleet. Or, if your PL/pgSQL-foo is strong, wield it to write AI and have your fleet command itself!
schemaverse.com
PostgreSQL License
356 stars 39 forks source link

Recommend having ships_near_ships managed purely in tic #20

Open cbbrowne opened 12 years ago

cbbrowne commented 12 years ago

Creation of new ships is frequently causing my scripts to time out, and this seems to fall from the insert into ships_near_ships.

https://github.com/cbbrowne/Schemaverse/commit/414228445f3dc73c965730de52fbb73098d4f08d

Abstrct commented 12 years ago

Looking at the create_ship() trigger, I realized that I didn't update this code when I optimized update_ships_near_ships(). This is the same code so it should hopefully benefit from the same idea.

I have changed this: where s1.id <> NEW.id and (s1.location <-> NEW.location) < s1.range; to: where s1.id <> NEW.id and CIRCLE(s1.location, s1.range) <@ CIRCLE(NEW.location,1);

This code uses some location indexes and seems to be quite a bit faster than the original code. Let me know if this fixes the slow ship creation issue you are experiencing. If it doesn't then I will just rip out the cache update as you suggested and use last_move_tic.

cbbrowne commented 12 years ago

Ah, interesting. I'll bet I ought to optimize some of my fleet queries to use CIRCLE() rather than distance calcs, although benchmarking has been showing the latter to seem quick enough. (My fleet scripts use temp tables pretty heavily.)

Ship creation seems to have sped up a bunch, so I think that has been helpful. Mind you, I gather that you reindexed tables, perhaps along with some vacuuming. It's possible that the latter did the job...

cbbrowne commented 12 years ago

Upon further reflection, I think that there's something rather ill-fated about having ships_near_ships.

It's a table that is enormously expensive in a war zone where there are two fleets of hundreds or possibly thousands of ships.

If both players have 1000 ships, then the table will have 1M tuples, and the addition of a ship will cost 1000 INSERTs into the underlying table. That seems entirely too expensive, particularly when you consider that any given ship can't possibly operate against more than 1 of its opponents.

If there's to be a table for this, it should list the opponents' ships once. It's the player's problem to correlate this against their own fleet. There's no fundamental problem in searching the result efficiently; a GIST index on the player's fleet can find ships nearby a specified opponent, and a GIST index on the revised table for this can efficiently find opponents that are in range of a specified "attack" ship's point.

I'm not sure how easy it is to populate such a table; let me think...

See patch...

https://github.com/cbbrowne/Schemaverse/commit/b9a25e6d64ef39407fbcd037bd9475fa1436136b

cbbrowne commented 12 years ago

The above patch should get looked at closely; I'm not at all sure it is correct.

ON THE OTHER HAND... I found missing piece in round_control()...

I noticed that the view on ships_near_ships was nigh unto unusable at the start of the new round today. Ah. Looking deeper... In Git, the definition of the table has ON DELETE CASCADE rules on the ship references. In production, there's no such FK, so the tuples don't go away at the end of each round. I imagine it's a good idea to DELETE/TRUNCATE from ships_near_ships before whacking the ships. That'll make the mass deletes cheaper, and survive the lack of FK...