Filtern Sie nach Array-Text [] und sortieren Sie nach Zeitstempel

7

Beschreibung

PostgreSQL 9.6 unter Linux, tags_tmpTabellengröße ~ 30 GB (10 Millionen Zeilen), tagsist a text[]und hat nur 6 Werte.

tags_tmp(id int, tags text[], maker_date timestamp, value text)
id  tags        maker_date      value
1   {a,b,c}     2016-11-09      This is test 
2   {a}         2016-11-08      This is test 
3   {b,c}       2016-11-07      This is test 
4   {c}         2016-11-06      This is test 
5   {d}         2016-11-05      This is test 

Ich brauche auf Daten mit Filter abzurufen tagssowie order byauf maker_date desc. Kann ich für beide tags & maker_date descSpalten einen Index erstellen ?

Wenn nicht, könnten Sie andere Ideen vorschlagen?

Abfragebeispiel

select id, tags, maker_date, value
from tags_tmp
where  tags && array['a','b']
order by maker_date desc
limit 5 offset 0

SQL-Code:

create index idx1 on tags_tmp using gin (tags);
create index idx2 on tags_tmp using btree(maker_date desc);

explain (analyse on, costs on, verbose)
select id, tags, maker_date, value
from tags_tmp
where tags && array['funny','inspiration']
order by maker_date desc
limit 5 offset 0 ;

Ergebnis erklären:

Limit  (cost=233469.63..233469.65 rows=5 width=116) (actual time=801.482..801.483 rows=5 loops=1)
  Output: id, tags, maker_date, value
  ->  Sort  (cost=233469.63..234714.22 rows=497833 width=116) (actual time=801.481..801.481 rows=5 loops=1)
        Output: id, tags, maker_date, value
        Sort Key: tags_tmp.maker_date DESC
        Sort Method: top-N heapsort  Memory: 25kB
        ->  Bitmap Heap Scan on public.tags_tmp  (cost=6486.58..225200.81 rows=497833 width=116) (actual time=212.982..696.650 rows=366392 loops=1)
              Output: id, tags, maker_date, value
              Recheck Cond: (tags_tmp.tags && '{funny,inspiration}'::text[])
              Heap Blocks: exact=120034
              ->  Bitmap Index Scan on idx1  (cost=0.00..6362.12 rows=497882 width=0) (actual time=171.742..171.742 rows=722612 loops=1)
                    Index Cond: (tags_tmp.tags && '{funny,inspiration}'::text[])
Planning time: 0.185 ms
Execution time: 802.128 ms

Mehr Informationen

Ich habe mit der Verwendung eines Teilindex für nur ein Tag getestet, natürlich ist es schneller. Aber ich habe viele Tags , zum Beispiel : create index idx_tmp on tags_tmp using btree (maker_date desc) where (tags && array['tag1') or tags && array['tag2'] or ... or tags && array['tag6']. Und ich habe zwischen tags && array['tag1']und getestet 'tag1' = any(tags), die Leistung ist gleich.

  1. text[]hat nur 6 Werte = a, b, c, d, e, f. Zum Beispiel: tags={a,b,c}, tags={a}, tags={a,c}, tags={a,b,c,d,e,f}, tags={b,f}und so weiter. Aber es kann keinen Wert haben g->z, A-Zund so weiter.

  2. create table tags_tmp(id int primary key not null, tags text[] not null, maker_date timestamp not null, value text)

  3. In Bezug auf distinctArray-Werte nimmt das, tagswas enthält, a20% Tabellenzeilen where 'a' = any(tags), b = 20% where 'b' = any(tags), c = 20% where 'c' = any(tags), d = 20% where 'd' = any(tags), e = 10% where 'e' = any(tags), f = 10% where 'f' = any(tags).

  4. Darüber hinaus (tags, maker_date)ist nicht eindeutig.

  5. Diese Tabelle ist nicht schreibgeschützt.

  6. Es ist sort on timestamp, aber mein Beispiel zeigt Daten, tut mir leid.

Aktuelle Situation: tags = 'a' or tags = 'b' or tags = 'c'und mehr

(1) Mit GIN indexoder Konvertieren text[] to int[]sowie Konvertieren text[] to intund mehr wird der Bitmap-Index für mehrere Tags verwendet. Schließlich entschied ich mich nach dem Testen, eine alte Lösung zu verwenden und ORin viele UNIONKlauseln zu wechseln , die jeweils UNIONdie Anzahl der Daten begrenzen. Natürlich werde ich partial indexfür jeden Tag einen Wert erstellen, den ich mit (1) oben kombinieren kann. In Bezug auf OFFSETwird WHEREstattdessen eine oder mehrere Bedingungen in Klausel verwendet.

Beispiel

EXPLAIN (ANALYSE ON, costs ON, VERBOSE)
SELECT rs.*
FROM (
        (SELECT tags,
                id,
                maker_date
         FROM tags_tmp
         WHERE 'a' = any(tags)
           AND maker_date <= '2016-03-28 05:43:57.779528'::TIMESTAMP
         ORDER BY maker_date DESC LIMIT 5)
      UNION
        (SELECT tags,
                id,
                maker_date
         FROM tags_tmp
         WHERE 'b' = any(tags)
           AND maker_date <= '2016-03-28 05:43:57.779528'::TIMESTAMP
         ORDER BY maker_date DESC LIMIT 5)
      UNION
        (SELECT tags,
                id,
                maker_date
         FROM tags_tmp
         WHERE 'c' = any(tags)
           AND maker_date <= '2016-03-28 05:43:57.779528'::TIMESTAMP
         ORDER BY maker_date DESC LIMIT 5)) rs
ORDER BY rs.maker_date DESC LIMIT 5 ;
Luan Huynh
quelle
1
Ich habe seit einigen Tagen mit dem gleichen Problem zu kämpfen , und ich habe die einfachste Lösung wäre, einen B-Baum mit mehreren Schlüsseln für jeden Datensatz gefunden: zum Beispiel des B-Baum würde a:2016-11-09, b:2016-11-09, c:2016-11-09 als Baumknoten und alle von ihnen Fügen Sie einen Zeiger auf die Zeile hinzu #1. MongoDB unterstützt tatsächlich zusammengesetzte Multikey-Indizes ... PostgreSQL tut dies leider nicht, und das ist sehr ärgerlich. Sie müssten eine separate Tabelle mit id_ref | tag | date erstellen, um einen ähnlichen B-Baum zu erstellen.
Collimarco

Antworten:

5

Allgemeine Überlegungen

Index - Optimierung hängt immer von der kompletten Bild. Tabellengröße, Zeilengröße, Kardinalitäten, Wertehäufigkeiten, Selektivität typischer Abfragen, Postgres-Version, typische Zugriffsmuster usw.

Ihr Fall ist aus zwei Gründen besonders schwierig:

  1. Verschiedene Spalten in WHEREund ORDER BY.
  2. Das Filtern nach Arrays ist mit dem GIN- oder GiST-Index am effizientesten, aber keiner der Indextypen erzeugt eine sortierte Ausgabe. Das Handbuch:

    Von den derzeit von PostgreSQL unterstützten Indextypen kann nur der B-Baum eine sortierte Ausgabe erzeugen. Die anderen Indextypen geben übereinstimmende Zeilen in einer nicht angegebenen, implementierungsabhängigen Reihenfolge zurück.

Sie können einen mehrspaltigen GIN-Index für (tags, maker_date)oder für mehrere Spalten erstellen (die Reihenfolge der Indexspalten ist für GIN-Indizes irrelevant). Sie müssen jedoch das zusätzliche Modul btree_gininstalliert haben. Anleitung:

Und es wird nicht für die ORDER BYKomponente Ihres Problems helfen .

Noch eine Klarstellung: Ist OFFSET m LIMIT nin der Regel fast so teuer wie LIMIT m+n.

Lösung für zusätzliche Spezifikationen

Sie haben klargestellt: Nur 6 verschiedene Tags möglich. Das ist entscheidend.

Ihr Tisch ist groß und Ihre Tabellendefinition lässt Raum für Verbesserungen. Size matters für große Tabellen. Ihre Zahlen (30 GB, 10 Millionen Zeilen) deuten ebenfalls auf einen großen Durchschnitt hin. Zeilengröße von ~ 3 KB. Entweder haben Sie mehr Spalten als Sie anzeigen oder die Tabelle aufblähen und benötigen einen VACUUM FULLLauf (oder ähnliches), oder Ihre valueSpalte ist groß und geröstet, was meine Verbesserungen noch effektiver machen würde, da die Hauptbeziehung damit auf die Hälfte ihrer Größe oder weniger reduziert wird ::

CREATE TABLE tags_tmp (
  id         int PRIMARY KEY -- assuming PK
, tags       int NOT NULL    -- also assuming NOT NULL
, value      text
, maker_date timestamp NOT NULL  -- NOT NULL!
);

Die Reihenfolge der Spalten ist aufgrund der Ausrichtungsauffüllung relevant. Einzelheiten:

Noch wichtiger ist : tags int. Warum?

Arrays haben einen beträchtlichen Overhead von 24 Byte (ähnlich einer Zeile) plus tatsächliche Elemente.

Ein text[]mit 1-6 Elementen wie Sie demonstrieren ('lustig', 'Inspiration', ...) belegt also durchschnittlich ~ 56 Bytes . Und 6 verschiedene Werte können durch nur 6 Informationsbits dargestellt werden (vorausgesetzt, die Sortierreihenfolge des Arrays ist irrelevant). Wir könnten noch mehr komprimieren, aber ich habe den praktischen integerTyp gewählt (belegt 4 Bytes ), der Platz für bis zu 31 verschiedene Tags bietet. Dadurch bleibt Platz für spätere Ergänzungen ohne Änderungen am Tabellenschema. Detaillierte Begründung:

Ihre Tags werden Bits in einer Bitmap zugeordnet, 'a'wobei es sich um das niedrigstwertige Bit handelt (rechts):

tag:       a | b | c | d |  e |  f
position:  0 | 1 | 2 | 3 |  4 |  5
int value: 1 | 2 | 4 | 8 | 16 | 32

Das Tag-Array '{a,d,f}'ist also zugeordnet 41. Sie können beliebige Zeichenfolgen anstelle von 'a' - 'f' verwenden, spielt keine Rolle.

Um die Logik zu kapseln, schlage ich zwei Hilfsfunktionen vor , die leicht erweiterbar sind:

Tags -> Ganzzahl:

CREATE OR REPLACE FUNCTION f_tags2int(text[])
  RETURNS int AS
$func$
SELECT bit_or(CASE x
            WHEN 'a' THEN  1
            WHEN 'b' THEN  2
            WHEN 'c' THEN  4
            WHEN 'd' THEN  8
            WHEN 'e' THEN 16
            WHEN 'f' THEN 32
            -- more?
           END)
FROM    unnest ($1) x
$func$  LANGUAGE SQL IMMUTABLE;

Ganzzahl -> Tags:

CREATE OR REPLACE FUNCTION f_int2tags(int)
  RETURNS text[] AS
$func$
SELECT array_remove(ARRAY [CASE WHEN $1 &  1 > 0 THEN 'a' END
                         , CASE WHEN $1 &  2 > 0 THEN 'b' END
                         , CASE WHEN $1 &  4 > 0 THEN 'c' END
                         , CASE WHEN $1 &  8 > 0 THEN 'd' END
                         , CASE WHEN $1 & 16 > 0 THEN 'e' END
                         , CASE WHEN $1 & 32 > 0 THEN 'f' END], NULL)
                         -- more? 
$func$  LANGUAGE SQL IMMUTABLE;

Grundlagen hier:

Zur Vereinfachung können Sie eine Ansicht hinzufügen , um Tags wie gewünscht als Textarray anzuzeigen:

CREATE VIEW tags_tmp_pretty AS
SELECT id, tags
     , f_int2tags(tags) AS tags_pretty
     , maker_date, value
FROM   tags_tmp;

Jetzt kann Ihre grundlegende Abfrage sein:

SELECT id, tags, maker_date, value
FROM   tags_tmp
WHERE  tags & f_tags2int('{a,b}') > 0  -- any of the tags matched
ORDER  by maker_date DESC
LIMIT  5;

Verwenden des binären UND-Operators& . Es gibt mehr Operatoren , um die Spalte zu bearbeiten. get_bit()und set_bit()von den binären Zeichenfolgenoperatoren sind auch bequem.

Die obige Abfrage sollte bereits schneller sein, nur für die kleineren und billigeren Betreiber, aber noch nichts Revolutionäres. Um es schnell zu machen, brauchen wir Indizes, und die oben genannten können noch keinen Index verwenden.

Ein Teilindex für jedes Tag:

CREATE INDEX foo_tag_a ON tags_tmp(maker_date DESC) WHERE tags & 1 > 0;
CREATE INDEX foo_tag_b ON tags_tmp(maker_date DESC) WHERE tags & 2 > 0;
...
CREATE INDEX foo_tag_f ON tags_tmp(maker_date DESC) WHERE tags & 32 > 0;

Diese Abfrage entspricht der obigen, kann jedoch die folgenden Indizes verwenden:

SELECT *
FROM   tags_tmp_pretty
WHERE (tags & f_tags2int('{a}') > 0   -- same as tags & 1
    OR tags & f_tags2int('{e}') > 0)  -- same as tags & 32
ORDER  BY maker_date DESC
LIMIT  10;

Postgres kann mehrere Bitmap-Index-Scans in einem BitmapOrSchritt sehr effizient kombinieren - wie in dieser SQL-Geige gezeigt .

Sie können eine weitere Indexbedingung hinzufügen, um die Indizes auf maker_dateeinen konstanten Zeitstempel zu beschränken (und die wörtliche Bedingung in Abfragen wiederholen), um ihre Größe (massiv) zu verringern. Zugehöriges Beispiel:

Anspruchsvoller:

Andere verwandte Antworten:

Oder nur 6 booleanSpalten ...

Einfach 6 boolesche Spalten könnten eine noch bessere Wahl sein. Beide Lösungen haben einige Vor- und Nachteile ...

CREATE TABLE tags_tmp (
  id         int PRIMARY KEY -- assuming PK
, tag_a      bool 
, tag_b      bool 
  ...
, tag_f      bool 
, value      text
, maker_date timestamp NOT NULL  -- NOT NULL!
);

Sie können die Flags NOT NULLabhängig von Ihrem vollständigen Anwendungsfall definieren.

Erwägen:

Teilindizes einfach:

CREATE INDEX foo_tag_a ON tags_tmp(maker_date DESC) WHERE tag_a;
CREATE INDEX foo_tag_b ON tags_tmp(maker_date DESC) WHERE tag_b;

Usw.

Alternative für Ihren Sonderfall

Denken Sie noch etwas darüber nach, da all Ihre wenigen Tags so häufig sind und das Kombinieren mehrerer Tags mit OR noch weniger selektiv ist, ist es am schnellsten, nur einen btree-Index zu haben maker_date DESC. Postgres kann den Index durchlaufen und qualifizierende Zeilen nach Tags filtern. Dies funktioniert in Kombination mit separaten booleschen Spalten anstelle des Arrays oder der codierten Ganzzahl, da Postgres nützlichere Spaltenstatistiken für separate Spalten enthält.

CREATE INDEX tags_tmp_date ON tags_tmp(maker_date DESC);

Und dann:

SELECT *
FROM   tags_tmp_pretty
WHERE  tag_a
   OR  tag_b
ORDER  BY maker_date DESC
LIMIT  10;

Paging

Sie benötigen eine eindeutige Sortierreihenfolge für Ergebnismengen, damit das Paging funktioniert. Ich habe mich nicht um diese Antwort gekümmert, sie ist schon zu lang. Normalerweise fügen Sie weitere Spalten hinzu ORDER BY. So funktioniert Paging effizient:

Erwin Brandstetter
quelle
1

Verschiedene Probleme mit Ihrem Testfall:

  1. idist int8jetzt. Sie haben es wie intin Ihrer ursprünglichen Frage erklärt. Kein großer Unterschied, aber warum die Verwirrung am Anfang? Dies ist wichtig für die Zeilengröße und die Ausrichtung. Bitte denken Sie daran, bei Fragen Ihre tatsächliche, genaue und vollständige Tabellendefinition anzugeben.

  2. Die Datenverteilung in Ihren Testdaten ist unrealistisch. Sie haben nur 6 verschiedene Kombinationen von Tags und * alle Zeilen haben Tags '1'. Ich gehe davon aus, dass Sie alle 63 möglichen Kombinationen in Ihrer Live-Tabelle haben, wobei die Tags so verteilt sind, wie Sie sie in der Frage hinzugefügt haben.

  3. Ihre Testtabelle enthält alte und neue Tag-Spalten, wodurch die Auswirkung auf die Speichergröße, nach der ich gesucht habe, negiert wird. Jetzt ist die Zeilengröße noch größer. Ihre Zeilengröße beträgt 124 - 164 Byte, in meinem Test nur 68 Byte (inkl. Auffüllung und Artikelkennung). Mehr als die doppelte Größe macht einen Unterschied.

  4. Sie schreiben Größe = 4163 MB . Welche Größe?

  5. Sie haben order by random()für die Testdaten. Ist Ihre produktive Tabelle wirklich so zufällig? In der Regel werden Daten grob nach Zeitstempel sortiert. Wie ist Ihre aktuelle Situation?

  6. Um zu sehen, welcher Plan ausgewählt wird, testen Sie EXPLAINnur mit, um den Abfrageplan anzuzeigen, bevor Sie die Abfrage tatsächlich ausführen. Spart viel Zeit mit großen Tischen. Aber immer die Ausgabe von EXPLAIN (ANALYZE, BUFFERS)hier bereitstellen . In Ihrer Antwort (im Gegensatz zur Frage) cost=fehlen Schätzungen. Das macht es schwierig, das Problem zu erraten.

Aber keines dieser Probleme kann erklären, warum Sie einen sequentiellen Scan auch mit sehen enable_seqscan = off; Ein schneller Test auf meinem Laptop mit Postgres 9.5 funktioniert . Gleiches sollte für S. 9.6 gelten.

CREATE TABLE tags_tmp(
   id         bigserial PRIMARY KEY, 
   maker_date timestamp NOT NULL,
   tags       int NOT NULL,
   value      text
);

INSERT INTO tags_tmp (tags, maker_date, value)
SELECT EXTRACT('minute' FROM ts)::int    -- int between 1 and 60 (no 61,62,63), pretty good.
     , ts + random() * interval '5 min'  -- some limited randomness
     , 'This is test on ' || EXTRACT('minute' FROM ts)
FROM   generate_series(timestamp '2016-01-01 00:00'
                     , timestamp '2016-01-13 00:00', '10 second') ts;
-- 103681 rows affected, 836 msec execution time.

-- create adapted function f_tags2int
-- create adapted function f_int2tags

CREATE INDEX tags_tmp_1 ON tags_tmp(maker_date DESC) WHERE tags &  1 > 0;
CREATE INDEX tags_tmp_2 ON tags_tmp(maker_date DESC) WHERE tags &  2 > 0;
CREATE INDEX tags_tmp_3 ON tags_tmp(maker_date DESC) WHERE tags &  4 > 0;
CREATE INDEX tags_tmp_4 ON tags_tmp(maker_date DESC) WHERE tags &  8 > 0;
CREATE INDEX tags_tmp_5 ON tags_tmp(maker_date DESC) WHERE tags & 16 > 0;
CREATE INDEX tags_tmp_6 ON tags_tmp(maker_date DESC) WHERE tags & 32 > 0;

SELECT id, tags, maker_date, value
FROM   tags_tmp
WHERE (tags & f_tags2int(array['5']) > 0 OR
       tags & f_tags2int(array['6']) > 0)
ORDER  BY maker_date DESC
LIMIT  5;
QUERY PLAN
Limit  (cost=3811.93..3811.94 rows=5 width=38) (actual time=46.586..46.586 rows=5 loops=1)
  Buffers: shared hit=1132
  ->  Sort  (cost=3811.93..3955.93 rows=57601 width=38) (actual time=46.584..46.585 rows=5 loops=1)
        Sort Key: maker_date DESC
        Sort Method: top-N heapsort  Memory: 25kB
        Buffers: shared hit=1132
        ->  Bitmap Heap Scan on tags_tmp  (cost=607.78..2855.20 rows=57601 width=38) (actual time=13.699..27.674 rows=76032 loops=1)
              Recheck Cond: (((tags & 16) > 0) OR ((tags & 32) > 0))
              Heap Blocks: exact=864
              Buffers: shared hit=1132
              ->  BitmapOr  (cost=607.78..607.78 rows=69121 width=0) (actual time=13.549..13.549 rows=0 loops=1)
                    Buffers: shared hit=268
                    ->  Bitmap Index Scan on tags_tmp_5 cost=0.00..289.49 rows=34560 width=0) (actual time=8.745..8.745 rows=48384 loops=1)
                          Buffers: shared hit=134
                    ->  Bitmap Index Scan on tags_tmp_6 (cost=0.00..289.49 rows=34560 width=0) (actual time=4.800..4.800 rows=48384 loops=1)
                          Buffers: shared hit=134
Planning time: 3.976 ms
Execution time: 46.653 ms

Genau wie ich es bereits in der SQL Fiddle demonstriert habe .

Sind Sie sicher, dass Sie alle Indizes ordnungsgemäß erstellt haben?

Erwin Brandstetter
quelle