1

I have a database of text tuples. Imagine e.g. full file paths + standard comments. Then you dump large file tree and generate comments for files. A file can have lots of comments, but their text repeats exactly. The DB gets into several GBs size, so I think it's quite big for sqlite standard, I'm a noob here though.

Anyways, since strings in individual columns do repeat quite a lot, but combinations are original, I thought I can have tables for distinct original strings, and combinations just as tuples of foreign keys (I believe that's called normalization), then a VIEW, preserving all API, for reading.

The question is, can I implement deduplication mechanism on the DB side for insert?

I thought of something like INSERT on (text_column1, text_column2, text_column3) and then write some kind of INSTEAD OF INSERT trigger, that would split it into 3 INSERT IF NOT EXISTS commands + 1 insert into relation table. But I don't think it is even possible to have different "interface" and "storage" schema. I certainly failed to write it.

I have supplementary questions which tightly related (thus not worthy of separate entries, I believe):

  1. Maybe sqlite3 already does string deduplication behind the scenes? (I doubt it, since mutable strings would complicate things a bit. Nothing undoable though.)
  2. If it's hard then maybe it's a bad idea for some reason?

If it helps my data is read-only once inserted.

I've read:

  1. Does PostgreSQL have a variable character storage layer that optimizes storage space by automatic dedupe?

  2. Implement a deduplication trigger in Oracle

  3. Automatic deduplication (normalization) of strings in MySQL

But they regard different SQL systems, and don't really answer general question. I gather that this is not a popular problem and solution.

2

Here is a rough sketch. I could only test with SQLite 3.8 and it appears as if UPSERT is introduced in 2018-06-04 - Release 3.24.0. I.e. the following is untested, but hopefully you can make something out of it anyhow

create table Texts
( tid integer not null primary key AUTOINCREMENT
, textval varchar(20) not null unique);

create index x1 on texts (textval);

create table T
( x int not null 
, tid int not null references texts (tid)
, primary key (x, tid) );

create view v as 
   select t.x, texts.textval
   from t
   join texts
       on t.tid = texts.tid
;

CREATE TRIGGER trig1 
INSTEAD OF INSERT ON V 
BEGIN
        -- insert unless textval is already in place
        INSERT INTO texts (textval)
        VALUES (NEW.textval) ON CONFLICT (textval) DO NOTHING;

        -- lookup tid for textval
        insert into t (x, tid)
        select NEW.x, texts.tid
        from texts where texts.textval = NEW.textval;

END;

rowid appears to be recommended over autoincrement, but that is sort of beside the point so I used it anyhow.

For 3.8 I used this ugly workaround:

CREATE TRIGGER trig1 
INSTEAD OF INSERT ON V 
BEGIN
        -- insert unless textval is already in place
        INSERT INTO texts (textval)
        SELECT NEW.textval FROM (VALUES(1))
        WHERE NOT EXISTS (
            SELECT 1 FROM texts WHERE textval = NEW.textval 
        );

        --lookup tid for textval
        insert into t (x, tid)
        select NEW.x, texts.tid
        from texts where texts.textval = NEW.textval;
END;

You can try it at DB<>Fiddle. Test:

insert into V (x,textval) values (1,'a'); 
insert into V (x,textval) values (5,'bb');  
insert into V (x,textval) values (15,'a');

select * from v;
x   textval
1   a
5   bb
15  a

select * from texts;
tid textval
1   a
2   bb

select * from t;
x   tid
1   1
5   2
15  1
  • Your example gave ma a nice kickstart. My toy is more complicated, as it has two string repositories and a N-M relation between strings in them. So the insert trigger is a bit more complicated, as it needs to pull two ids - one for each repo, for final insert. But it was close enough, I am not sure if I should post my example as well. IMHO it's a bit richer. Regarding the workaround, I've also tripped on this, however we don't need UPSERT here, fortunately ON CONFLICT DO NOTHING idiom was already present as INSERT OR IGNORE. UPSERT does supersede it, but there's no need to update. – luk32 Jun 19 at 11:51
  • You did the right thing postning your own solution, since mine was just a sketch to get you going. For future questions, post ddl and some sample data as in your answer (or a fiddle or similar). You will get much more respons and help if people dont have to guess and create the ddl by them self. – Lennart Jun 19 at 18:08
  • Yea, but I came up it with after your help. I didn't have any toy DDL before, I just mingled with my "production". I was honestly thinking it's not a popular/good idea, since I couldn't find any similar answer. BTW in my case it worked pretty well, DB size dropped from 2.2.GB to 0.6 and with correct indexes and joins basically maintained speed (5-10% drop for creating DB). Great help. Thanks. – luk32 Jun 20 at 17:39
1

For the sake of the completeness, it works pretty fine. After kickstarted by Lennart's answer. Here is my final solution.

I have separate unique text repositories and an N-M relation between them:

CREATE TABLE "text_group1" (
    "id"    INTEGER NOT NULL DEFAULT null PRIMARY KEY AUTOINCREMENT UNIQUE,
    "text"  TEXT NOT NULL UNIQUE
)

CREATE TABLE "text_group2" (
    "id"    INTEGER NOT NULL DEFAULT null PRIMARY KEY AUTOINCREMENT UNIQUE,
    "text"  TEXT NOT NULL UNIQUE
)

CREATE TABLE text1_text2 (
    text1_id integer NOT NULL,
    text2_id integer NOT NULL,
    foreign key (text1_id) references text_group1 (id),
    foreign key (text2_id) references text_group2 (id)
)

A view to see original format:

CREATE VIEW text1_text2_view AS   
   select text_group1.text AS text1, text_group2.text AS text2
   from text1_text2
   join text_group1
       on text_group1.id = text1_id
   join text_group2
       on text_group2.id = text2_id

The cool part, which is what I call deduplication trigger. I wasn't aware that it's possible to add a trigger on a view:

CREATE TRIGGER trig1 
INSTEAD OF INSERT ON text1_text2_view
BEGIN
        -- insert new texts into unique text groups
        INSERT INTO text_group1 (text)
        VALUES (NEW.text1) ON CONFLICT DO NOTHING;

        INSERT INTO text_group2 (text)
        VALUES (NEW.text2) ON CONFLICT DO NOTHING;

        -- pickup ids from unique string repos and insert into normalized relation table
        insert into text1_text2 (text1_id, text2_id)
           select text_group1.id, (SELECT text_group2.id FROM text_group2 WHERE text_group2.text = NEW.text2) id2
             from text_group1
             where text_group1.text = NEW.text1;
END

The ugly part is selection statement, because in case of more text repositories the 1st id and it's FROM WHERE are separated by sub selections.

We can insert data as into original 2 text-column table via the view:

INSERT INTO text1_text2_view (text1, text2) VALUES ("g1_text1", "g2_text1")
INSERT INTO text1_text2_view (text1, text2) VALUES ("g1_text2", "g2_text2")
INSERT INTO text1_text2_view (text1, text2) VALUES ("g1_text1", "g2_text2")

The result is two strings in each repository, and a view with 3 tuples.

  • Some feedback on your ddl. UNIQUE is not necessary for primary Keys. Default null is the default, you can leave that out. Text1_text2 should probably have a composite primary key – Lennart Jun 19 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.