Row mit engstenem Spaltenwert

Question

Ich habe die folgende Tabelle:

CREATE TABLE items (
    id serial 
    timestamp bigint 
    CONSTRAINT id_pkey PRIMARY KEY (id), 
); 

Diese Tabelle wird in einer Append-only-Mode verwendet wird, so dass die timestamp Werte steigen mit den id. Ich muss die Zeile finden, die timestamp am nächsten zu einer bestimmten $value ist.

Abfrage 1: Dies erfordert zwei vollständige Tabellen-Scans.

SELECT id FROM 
    (
     (
      SELECT id, timestamp 
      FROM records 
      WHERE timestamp < $value 
      ORDER BY timestamp DESC 
      LIMIT 1 
    ) 
     UNION ALL 
     (
      SELECT id, timestamp 
      FROM items 
      WHERE timestamp >= $value 
      ORDER BY timestamp ASC 
      LIMIT 1 
    ) 
) AS tmp 
ORDER BY abs($value - timestamp) 
LIMIT 1 

Abfrage 2: Dies scheint, wie es schneller sein sollte, aber aus irgendeinem Grunde ist es nicht

SELECT id 
FROM items 
WHERE scan.gpstimestamp >= $value 
ORDER BY id ASC 
LIMIT 1 

Frage 3: Ich bin mit einem benutzerdefinierten Aggregate zu experimentieren, die eine vollständige Tabellen-Scan erfordert, Sie müssen jedoch nichts sortieren oder Indizes laden.

create function closest_id_sfunc(
    agg_state bigint[2], 
    id bigint, 
    timestamp bigint, 
    target_timestamp bigint 
) 
returns bigint[2] 
immutable 
language plpgsql 
as $$ 
declare 
    difference bigint; 
begin 
    difference := abs(timestamp - target_timestamp); 
    if agg_state is null or difference < agg_state[0] then 
    agg_state[0] = difference; 
    agg_state[1] = id; 
    end if; 
    return agg_state; 
end; 
$$; 

create function closest_id_finalfunc(agg_state bigint[2]) 
returns bigint 
immutable 
strict 
language plpgsql 
as $$ 
begin 
    return agg_state[1]; 
end; 
$$; 

create aggregate closest_id (bigint, bigint, bigint) 
(
    stype  = bigint[2], 
    sfunc  = closest_id_sfunc, 
    finalfunc = closest_id_finalfunc 
); 


SELECT closest_id(id, timestamp, $value) as id FROM items 

Warum würde Abfrage 2 langsamer als Abfrage 1 sein?

Answer 1

Ihre zweite Abfrage wird nicht funktionieren, weil es möglicherweise durch eine Zeile vor dem angegebenen Zeitstempel, der näher an dem bereitgestellten Wert ist. Und Genauigkeit ist nicht das einzige Problem: Es gibt möglicherweise keine Zeile, die größer ist als der angegebene Zeitstempel (und gleichzeitig existiert ein niedrigerer Wert).

Ihre erste Abfrage sieht effizient aus (wenn Sie auch limit 1 in den Unterabfragen verwenden). Aber ja, es erfordert zwei Tabellen-Scans, wenn Sie keinen Index haben, aber Sie können nicht umgehen. Sie benötigen Indizes für enorme Leistungssteigerungen. Es gibt jedoch ein paar Tricks, die verwendet werden können.

Meine ursprüngliche Idee war, dass Sie Kosten für die äußere Abfrage Art vermeiden können, durch conditionals stattdessen mit:

(Anmerkung: Ich ts als Spaltennamen verwenden werden, wie timestamp ein Schlüsselwort & ist, sollte nicht als Spaltenname verwendet wird, es sei denn, es entgangen ist.)

with l as (
    select id, ts 
    from  items 
    where ts < $value 
    order by ts desc 
    limit 1 
), 
g as (
    select id, ts 
    from  items 
    where ts >= $value 
    order by ts asc 
    limit 1 
) 
select case 
      when abs($value - l.ts) < abs($value - g.ts) 
      then l.id 
      else coalesce(g.id, l.id) 
      end id 
from  l 
full join g on true 

dies ist jedoch nur einen winzigen Performance-Gewinn in meinen Tests verursacht (es scheint, PostgreSQL über das Sortieren zwei Reihen ziemlich klug ist nur).

Sie können Ihre Abfragen beschleunigen, indem Sie eine direkte "Entfernungs" -Berechnung für einige geometrische Typen von PostgreSQL verwenden. Hinweis: Diese Typen verwenden normalerweise double precision für Werte und können daher Rundungsfehler enthalten. Dies ist höchstwahrscheinlich kein Problem, wenn Ihre Werte wirklich Unix-Zeitstempel sind (in bigint).

Hier ist die Abfrage der immer zur Verfügung point Typ der Abstand des Bedieners <-> auf point(ts, 0) (so die zweite Koordinate wird immer Null sein) zu verwenden:

select id 
from  items 
order by point(ts, 0) <-> point($value, 0) 
limit 1 

In meinen Tests, das kostet ~ 70% Ihrer ursprünglichen Abfrage (oder die CTE-Variante).

Sie können auch die cube module'scube Typ & seine (euklidische) Abstand Operator <-> (9 verwenden.6+ Funktion) auf cube(ts) (so wird der Würfel immer ein eindimensionaler Punkt):

select id 
from  items 
order by cube(ts) <-> cube($value) 
limit 1 

Dies ist auf die point Variante in der Geschwindigkeit vergleichbar. Es wird einige Unterschiede geben, wenn Sie einen Index dafür verwenden.

(Anmerkung:. Sie das Modul mit create extension cube; initialisieren)

Indizes

So ist der interessante Teil (e):

Ihre ursprüngliche Abfrage (oder der CTE-Variante) kann Verwenden Sie den folgenden (deckenden) Index:

create index idx_items_ts_id on items (ts, id) 

Mit dieser Ihre ursprüngliche Abfrage (und die CTE var iant) verwendet Index-Only-Scans, die ~ 1,5% derselben Abfrage (ohne Index) kosten.

Die point Variante die folgende GiST Index verwenden:

(Anmerkung:.. Das btree_gist Modul ist erforderlich für id Teil des Index werden Sie das Modul mit create extension btree_gist; initialisieren)

create index idx_items_point_gist on items using gist (point(ts, 0), id) 

Damit kostet die point Variante ~ 1% der ursprünglichen Abfrage (ohne einen Index).

Die cube Variante können die folgenden GiST Index verwenden:

. (Anmerkung: dies erfordert auch die btree_gist Modul)

create index idx_items_cube_gist on items using gist (cube(ts), id) 

Auch dies auf die point Variante noch vergleichbar ist.

Schlussfolgerung (siehe bearbeiten später)

Sie können mit der Verwendung von point oder cube die beste Leistung erzielen (letzteres erfordert 9.6+). Auch Indizes können Ihnen sehr helfen.

Weitere Hinweise:

• Die point Variante war tatsächlich manchmal schneller (als die cube Variante)
• PostgreSQL hat eine wirklich lange Zeit, um den cube Index zu bauen & Ich weiß nicht genau, warum
• In der Theorie sollte der cube Index kleiner sein, da er keine unnötigen Nullen enthält. Aber weil sie allgemeiner sind (N-dimensional), könnte ich damit nicht recht haben. Ich schlage vor, sowohl & Maßnahme (beide Indexgrößen & Leistung) auszuprobieren.

http://rextester.com/KNY52367 (die Abfragen für cube auch hier sind, aber werden nicht ausgeführt, weil rextester 9.5 jetzt verwendet).

Auch ich testete eine benutzerdefinierte Aggregatlösung auch (im Grunde Ihre Version, aber ich language sql Funktionen verwendet, um ein wenig zu beschleunigen, aber immer noch), war es ~ 10 mal langsamer als Ihre ursprüngliche Abfrage. IMHO, es ist überhaupt nicht wert. http://rextester.com/PLG94853

bearbeiten: Just bemerkt, dass die btree_gist Modulträger für den Abstand Betreiber <-> für die Grundtypen (wie bigint) hinzufügt.

So wird diese Abfrage übertreffen sogar die point und die cube Variante auch (mit etwas):

select id 
from  items 
order by ts <-> $value 
limit 1 

Und dieser Index wird oben am besten mit der Abfrage arbeiten:

create index idx_items_ts_gist on items using gist (ts, id) 

http://rextester.com/XUF56126