Performance von Bitstrings schlechter als Arrays

Fragen und Probleme rund um die Abfragespache SQL.
Antworten
katenum
Neuer Benutzer
Beiträge: 2
Registriert: Do 5. Sep 2019, 12:19

Performance von Bitstrings schlechter als Arrays

Beitrag von katenum » Do 5. Sep 2019, 12:49

Hallo,

ich habe eine Tabelle, deren Zugriff ich über Row Level Security Policies einschränken möchte.
Dafür hat diese Tabelle eine Spalte, die angibt, welcher Nutzer auf die aktuelle Zeile zugreifen darf.
Folgende zwei Ideen:
Die Spalte "rights" ist vom Typ Bit/Integer-Array der Länge 16 bei 16 Nutzern und jeder Nutzer bekommt einen Index zugewiesen.
Hat das Array an dieser Stelle den Wert 1, so kann ein Nutzer die Zeile lesen. Die Policy dafür sieht wie folgt aus:

Code: Alles auswählen

CREATE POLICY policy_testdata_select ON testdata
        FOR SELECT TO PUBLIC
        USING (rights[(select array_pos from account where username = current_user)] > 0);
Die zweite Möglichkeit nutzt Bitstrings. Dabei hat jeder User einen Bitstring der Länge 16 (bei 16 Usern) zugewiesen, der nur an einer Stelle eine Eins hat und sonst Nullen. Die Spalte in der Tabelle ist auch ein Bitstring der Länge 16, der mehrere Einsen haben kann. Eine Zeile der Tabelle kann dann von einem User gelesen werden, wenn der Wert der Zeile binär verundet mit dem Bitstring des Nutzers nicht der Nullstring ist.
Beispiel:
Wert in der Tabelle: 1001010
User1-Bitstring: 0001000
User2-Bitstring: 0000100
1001010 & 0001000 = 0001000 -> User1 hat Zugriff
1001010 & 0000100 = 0000000 -> User2 hat keinen Zugriff

Die Policy sieht dann so aus:

Code: Alles auswählen

CREATE POLICY policy_testdata_select ON testdata
        FOR SELECT TO PUBLIC
        USING ((bitstring & (select user_bitstring from account where username = current_user)) <> B'0'::BIT(16));
Jetzt habe ich zwei Fragen:
1. Intuitiv würde ich behaupten, dass die zweite Möglichkeit die performantere ist, da ein Bitstring nicht viel Speicher verbraucht und Binäroperationen nicht viel kosten, wenn man die Performance vergleicht, so ist die Array-Version aber sogar etwas schneller. Wie kommt das?
Hier die beiden Auswertungspläne mit den selben Testdaten (2 Mio. Zeilen und User hat Zugriff auf die Hälfte):

Code: Alles auswählen

Array:
                                                                 QUERY PLAN                                                                  
---------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=10000000008.16..10000526114.16 rows=666667 width=1160) (actual time=0.025..2733.524 rows=1000000 loops=1)
   InitPlan 1 (returns $0)
     ->  Index Scan using username2_index on account2  (cost=0.14..8.16 rows=1 width=4) (actual time=0.014..0.014 rows=1 loops=1)
           Index Cond: (username = CURRENT_USER)
   ->  Seq Scan on testdata  (cost=10000000000.00..10000526106.00 rows=666667 width=1160) (actual time=0.025..2660.927 rows=1000000 loops=1)
         Filter: (rights[$0] > 0)
         Rows Removed by Filter: 1000000
 Planning Time: 0.181 ms
 Execution Time: 2768.561 ms
(9 rows)

Bitstring:
                                                                  QUERY PLAN                                                                  
----------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=10000000008.16..10000266895.60 rows=1000000 width=1160) (actual time=0.026..2759.098 rows=1000000 loops=1)
   InitPlan 1 (returns $0)
     ->  Index Scan using username2_index on account2  (cost=0.14..8.16 rows=1 width=7) (actual time=0.013..0.014 rows=1 loops=1)
           Index Cond: (username = CURRENT_USER)
   ->  Seq Scan on testdata  (cost=10000000000.00..10000531106.00 rows=1990000 width=1160) (actual time=0.025..2685.145 rows=1000000 loops=1)
         Filter: ((bitstring & $0) <> '0000000000000000'::bit(16))
         Rows Removed by Filter: 1000000
 Planning Time: 0.167 ms
 Execution Time: 2794.719 ms
(9 rows)
2. Gibt es eine bessere Möglichkeit, den Zugriff zu filtern unter der Anforderung, dass die Rechte auf eine Zeile änderbar sein sollen.
Wäre es beispielsweise möglich einen Index zu bauen, der die Filterung beschleunigt?

Besten Dank vorab!

katenum
Neuer Benutzer
Beiträge: 2
Registriert: Do 5. Sep 2019, 12:19

Re: Performance von Bitstrings schlechter als Arrays

Beitrag von katenum » Fr 6. Sep 2019, 13:12

TLDR: Warum ist eine Array-Operation auf Integern schneller als eine einfache Bit-Operation?

Hat jemand eine Idee warum das sein kann?

akretschmer
Erfahrener Benutzer
Beiträge: 7640
Registriert: So 29. Okt 2006, 13:35
Wohnort: Kaufbach, Sachsen, Germany, Germany
Kontaktdaten:

Re: Performance von Bitstrings schlechter als Arrays

Beitrag von akretschmer » Sa 7. Sep 2019, 18:14

ich versuch mal zu antworten:

Du wirst da keinen Index erstellen können, auch keinen funktionalen, da die Funktion, mit der Du das berechnest, selbst wieder ein SELECT auf eine Tabelle macht. Damit kannst einen Index daraf vergessen. Ob die Array-Operation oder die Bit-Operation nun schneller ist, geht nicht wirklich aus den Explains hervor. Nachezu 100% der Zeit ist der Seq-Scan, den Rest kannst Du in den Skat drücken.
Dein Problem wäre lösbar, wenn Du die Nutzer in Rollen stecken würdest und den Namen der Rolle speichern würdest und in der Policy auf die Rolle bezug nimmst.
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Antworten