Verkleinerung der Sudoku Datenbank

Ausgangslage

Im 2006 habe ich eine Javascript Lösungshilfe auf Heuscher.ch erstellt. Teil davon ist die Generierung von Sudokus und deren Speicherung in der Datenbank auf devzone.ch.

Am 25. August 2019 hat Daniel mir eine Mail geschrieben mit der Anfrage bez. Grösse der Datenbank

2012 habe ich die Datenbank letztmals angepasst und die Spalte Sudoku-Solution gelöscht um Platz zu schaffen.

Ziel

Die Datenbank soll so klein wie möglich werden, bei Erhalt der Daten und der Funktionalität der Sudoku Seite auf Heuscher.ch.

Kurzfristige Massnahmen

  1. 26. Aug 2019: client (IP, VARCHAR(15), 16 Bytes) und creation_timestamp (Timestamp, 8 Bytes) auf Tabelle sudokus gelöscht.
  2. Daniel darüber informiert plus, dass der freie Platz nicht zugenommen hat (es braucht noch Aufräum-Arbeiten mit postgres) und ich mich an die Verkleinerung der Datenbank mache.

Analyse

Alle Sudoku-Daten sind in der Tabelle sudokus mit 114'445'716 Rows:
heuscher=# \d sudokus
Table "public.sudokus"
    Column    |          Type          |               Modifiers
--------------+------------------------+----------------------------------------
 sudoku_start | character varying(200) | not null
 random_id    | double precision       | default random()
 difficulty   | integer                |
 sudoku_id    | integer                | default nextval('sudoku_id_seq'::text)
Indexes:
    "sudokus_pkey" primary key, btree (sudoku_start)
    "difficulty_index" btree (difficulty)
    "random_id_index" btree (random_id)
    "sudoku_id_index" btree (sudoku_id)
    "sudoku_start_index" btree (sudoku_start)

Pro Row braucht es ca. 82, 8, 4 und 4 Bytes = 98 Bytes (gemäss Speicherbedarf Doku https://www.postgresql.org/docs/9.1/datatype.html ). Die erwartete Grösse ist daher etwa 11 GB --> Faktor 5 kleiner als Daniels Info.

--> Erst mal ein "vacuum sudokus;" machen um zu schauen, ob das nützt. --> Indexe löschen, die nicht nötig sind: "sudokus_pkey", "sudoku_start_index"

Primary key und Index droppen (geht zu lange)

Wie codiere ich ein Sudoku mit möglichst wenig Speicherplatz?

Startend vom https://cs.stackexchange.com/questions/165/efficient-encoding-of-sudoku-puzzles (81 + 4n) Bits habe ich das auf (81 + 3n + 7m) reduziert, da jedes Bit anzeigt, ob die Zelle besetzt ist und dann (wenn ja) mit welcher Zahl, wobei 8 unterschiedliche Zahlen (= 3 bits) möglich sind. Die Speicherorte der 9 werden am Ende angezeigt (wobei die 9 mit der Zahl, die am wenigsten vorkommt getauscht wird).

Minimale Tabelle

    Column    |          Type          |               Modifiers
--------------+------------------------+----------------------------------------
 sudoku_id    | integer                | default nextval('sudoku_id_seq'::text)
 sudoku_start | bit varying (405)      | not null
 difficulty   | smallint               |
Indexes:
    "sudokus_id_pkey" primary key, btree (sudoku_start)
    "difficulty_index" btree (difficulty)
    "sudoku_id_index" btree (sudoku_id)

Die Definition der Länge ist konservativ für ein vollständig ausgefülltes Sudoku ausgelegt. Die "normale" Row mit 30 definierten Zahlen ist ~22.5B + 6.5B Overhead für bit varying, 4, 2 plus 4 Bytes = 39 Bytes --> 60% weniger Platz

Vorgehen

  1. Neue Tabelle erstellen ohne index auf sudoku_start
  2. Neue Tabelle füllen mit letzten 10k Einträgen
  3. Datenverbrauch analysieren
  4. PHP-Zugriffe umstellen
  5. Überflüssige Indexe auf der Original-Tabelle löschen
  6. Datenverbrauch analysieren
  7. Weiteres Vorgehen definieren

Neue Tabelle erstellen ohne index auf sudoku_start

CREATE TABLE SUDOKUS_mig (                                                        
   sudoku_id integer unique PRIMARY KEY DEFAULT nextval('sudoku_id_seq'),
   sudoku_start VARCHAR(81),
   difficulty  smallint
);  

\d SUDOKUS_mig

                               Table "public.sudokus_mig"
    Column    |         Type          |                    Modifiers             
--------------+-----------------------+-------------------------------------------------
 sudoku_id    | integer               | not null default nextval('sudoku_id_seq'::text)
 sudoku_start | character varying(81) |
 difficulty   | smallint              |
Indexes:
    "sudokus_mig_pkey" primary key, btree (sudoku_id)

Neue Tabelle füllen mit letzten 10k Einträgen

insert into SUDOKUS_mig (sudoku_id, sudoku_start, difficulty)  select sudoku_id, sudoku_start, difficulty from SUDOKUS where sudoku_id <= 114465191 AND sudoku_id > 114455191 ;
INSERT 0 9956

Datenverbrauch analysieren

Vor 10k Einträgen 61361282829 Bytes, nachher 61362798349 Bytes: plus 1'515'520 Bytes (erwartet 10k * (82+ 4 + 2) = 880'000 Bytes, Faktor 1.7). Das ist OK;

PHP-Zugriffe umstellen

OK jedoch nur für ajaxRandomSudoku.php (Generierung ist sowieso gestoppt)

Überflüssige Indexe auf der Original-Tabelle löschen

Primary key und Index droppen (in "screen")

Weiteres Vorgehen definieren

  1. OK Encoding/Decoding implementieren
  2. OK Tabelle sudoku aufbohren, Sudokus parallel komprimiert speichern
  3. OK Langsame Migration, pro neues Sudoku x (100?) Sudokus migrieren
  4. ca. Nov 2019 Wenn 10 Mio migriert -> random sudoku umstellen auf auslesen
  5. Wenn alles migriert: Testen, z.B. wo sudoku_start_encoded = null?
  6. Kolonne sudoku_start und Tabelle sudoku_mig droppen und PHPs anpassen
  7. Messen und dokumentieren
  8. Feiern!

Encoding/Decoding implementieren

Tabelle sudoku aufbohren, Sudokus parallel komprimiert speichern

Langsame Migration, pro neues Sudoku x (100) Sudokus migrieren

Idee: bei jeder Speicherung eines Sudoku x Sudokus migrieren

Umsetzung: Zufällig x Sudokus mit encoded = null migrieren bei jedem neuen Sudoku. Die Tests laufen auf Tabelle sudokus_mig

Tests OK. Migration startet am 8. Sept. 2019 ~22:22 Uhr -> wird ca. 1 Mio Sudokus für Migration brauchen (start bei sudkoku_id 114707298, Speicher: 26'452'033'293). 10. Sept. 109'680'063 von 114'154'616 noch leer -> 4 Mio migriert (Speicher 28'288'630'541). Nach "DROP INDEX difficulty_index;" -> 25'641'803'533 Speicher.

Wenn 10 Mio migriert -> random sudoku umstellen auf auslesen

Tests OK. 29'512'556'301 Bytes, 90'560'363 noch nicht encoded, 17. Sept 2019

http://devzone.ch/~twiki/Main/Heuscher/Steve/Public/WebHome/SudokuRegister/ajaxRandomSudoku.php

Durchschnittliche Länge eines codierten Sudokus: "select avg(length(sudoku_start_encoded)) from sudokus where sudoku_start_encoded is not null and sudoku_id <9700;" -> 169.7475000000000000

Wenn wir nur encodete ausliefern können wir sudoku_start ab sofort als NULL speichern -> "ALTER TABLE sudokus_mig ALTER sudoku_start DROP NOT NULL;" -> letzte sudoku_id mit sudoku_start ist 114943089

Und bei der Migration können wir sudoku_start ab sofort als NULL speichern -> weniger Daten (sudoku_start ab sofort als NULL speichern (ca. 30 GB 17. Sept 2019 abends -> "VACUUM sudokus;"

FileAttachment: Action: Size: Date: Who: Comment:
icon 2019_Sudoku-Encoding.xlsx view update 32818 17 Sep 2019 - 02:03 StephanHeuscher
add
Wie würden Sie diese Seite verbessern? Teilen Sie Ihre Ideen!
Zum Menu