Example: String De-Duplication

Question: How do I save space by eliminating duplicate values from a string column while still being able to SELECT those values whenever necessary?

Answer: One method is to store a single copy of each different string value in a separate table, and replace the string column in the original table with a pointer to the new table.

Sounds simple, right?

Well, it's not too bad, given some of the language features built in to SQL Anywhere. Here's an example of the original table before any changes are made, plus a simple query:

CREATE TABLE t ( 
   pkey                BIGINT NOT NULL DEFAULT AUTOINCREMENT PRIMARY KEY,
   blob                LONG VARCHAR NULL );

SELECT pkey, blob
  FROM t;

The blob column can vary wildly in length, from NULL, to the empty string '', to a few characters, to megabytes in size.

Here's the new table, designed to hold t.blob values that are moved into tblob.blob:

CREATE TABLE tblob ( 
   blob_key            INTEGER NOT NULL DEFAULT AUTOINCREMENT PRIMARY KEY,
   hash_value          VARCHAR ( 64 ) NOT NULL,
   collision_counter   INTEGER NOT NULL,
   reference_count     BIGINT NOT NULL,
   blob                LONG VARCHAR NOT NULL,
   CONSTRAINT ukey UNIQUE ( hash_value, collision_counter ) );

• The blob_key column is an artificial primary key 1, 2, 3, ... for the new table; this is where the "pointer to the new table" comes from.
  

• The hash_value column is filled by applying SQL Anywhere's HASH() function to the long string in t.blob to create a much shorter but (almost?) perfect alternate version of t.blob. In other words, if two HASH() values are the same, then the two original strings are (probably) the same, and vice versa: if two HASH() values are different then the original strings are (probably) different.
  

• The collision_counter column counts the number of times 0, 1, 2, ... that the same HASH() value was returned for different t.blob values. This value has remained zero during all the testing done for this article, but... who knows?
  

• The reference_count column counts the number of times that separate copies of the same t.blob value were replaced by one row in tblob. This column is nice to have for testing, and it may even be needed in your application, but it does increase the overhead.
  

• The blob column is where the single copy goes, and it's NOT NULL because by the time anything is stored in tblob it's known to be longer than the threshold (e.g., 100 bytes).
  

• The UNIQUE constraint is a performance optimization to help with the process that inserts new rows in tblob.
  

Here's what the original table and query look like now, with the t.blob value moved to tblob.blob for some rows and not others:

CREATE TABLE t ( 
   pkey                BIGINT NOT NULL DEFAULT AUTOINCREMENT PRIMARY KEY,
   blob_key            INTEGER NULL REFERENCES tblob ( blob_key ), 
   blob                LONG VARCHAR NULL );

SELECT t.pkey, COALESCE ( t.blob, tblob.blob ) AS blob
  FROM t LEFT OUTER JOIN tblob 
          ON t.blob_key = tblob.blob_key;

• The LEFT OUTER JOIN matches each row in t with the corresponding row in tblob, if one exists. If no such row in tblob exists, that means the original blob value was too short to be moved, or it was NULL in the first place.
  

• The COALESCE function call returns t.blob if it isn't NULL,
  

• otherwise it returns tblob.blob if there was a matching row in tblob, or
  

• if neither is true, it returns NULL.
  

In other words, only one of t.blob_key and t.blob can be non-NULL. Both columns can be NULL, however, which is what happens when the original blob value was NULL.

Here's a sample of code that shows how to INSERT rows into t and tblob, using as test data the blob column from another table called x:

BEGIN

DECLARE @match_found                       VARCHAR ( 1 );
DECLARE @hash_value                        VARCHAR ( 64 );
DECLARE @max_existing_collision_counter    INTEGER;
DECLARE @blob_key                          INTEGER;

outer_fetch_loop: FOR f_outer AS c_outer NO SCROLL CURSOR FOR
SELECT x.blob AS @blob
  FROM x
FOR READ ONLY
DO

   IF LENGTH ( COALESCE ( @blob, '' ) ) > 100 THEN

      SET @match_found = 'N';

      SET @hash_value = HASH ( @blob, 'SHA256' );
      SET @max_existing_collision_counter = -1; 

      inner_fetch_loop: FOR f_inner AS c_inner NO SCROLL CURSOR FOR
      SELECT tblob.blob_key          AS @existing_blob_key,
             tblob.collision_counter AS @existing_collision_counter,
             tblob.blob              AS @existing_blob
        FROM tblob
       WHERE tblob.hash_value = @hash_value
       ORDER BY tblob.collision_counter
      FOR READ ONLY
      DO

         IF @blob = @existing_blob THEN
            SET @match_found = 'Y';
            SET @blob_key = @existing_blob_key;
            UPDATE tblob
               SET tblob.reference_count = tblob.reference_count + 1 
             WHERE tblob.blob_key = @existing_blob_key;
            LEAVE inner_fetch_loop;
         ELSE 
            SET @max_existing_collision_counter = @existing_collision_counter;
         END IF;
      END FOR inner_fetch_loop;

      IF @match_found = 'N' THEN
         INSERT tblob (
            hash_value,
            collision_counter,
            reference_count,
            blob )
         VALUES ( 
            @hash_value, 
            @max_existing_collision_counter + 1, 
            1, 
            @blob );
         SET @blob_key = @@IDENTITY;
      END IF;

      INSERT t ( blob_key, blob ) VALUES ( @blob_key, NULL );

   ELSE

      INSERT t ( blob_key, blob ) VALUES ( NULL, @blob );

   END IF;

   COMMIT;

END FOR outer_fetch_loop;

COMMIT;

END;

• The IF LENGTH > 100 on line 14 checks to see if the benefits of moving t.blob into tblob is worth the overhead. If not, the INSERT down on line 61 leaves the blob in t and sets the pointer to NULL.
  

• The HASH() function call on line 18 uses the SHA256 algorithm, the best that SQL Anywhere has to offer. HASH() returns VARCHAR ( 64 ) values like b9afc180bd8fa250a006229ba9c8b8eddba0b96dfcb8320740af84a4c485f5ea... in other words "trust me, it's unique".
  

• The FOR statement starting on line 21 looks through all the rows in tblob with matching HASH() values. In the real world, there will (probably) be zero or one rows processed by this FOR loop, and if one row is returned the IF @blob = @existing_blob on line 31 will be TRUE.
  

• The IF THEN on lines 31 through 37 handles the case where not only does the HASH() value match but so does the blob value, and it saves the tblob.blob_key value in @blob_key for later use, before using the LEAVE statement on line 37 to skip out of the inner FOR loop and resume processing at line 43.
  

• The ELSE starting on line 38 handles a collision, where the HASH() value matches but not the blob value, by bumping up the value of @max_existing_collision_counter (which was initialized to -1 back on line 19).
  

• The IF THEN on lines 43 through 55 handles the case where the HASH() value didn't match, so a new row in tblob must be inserted.
  

• The INSERT statement on line 57 fills in the pointer (t.blob_key) while setting t.blob to NULL. This is different from the INSERT on line 61 which sets the pointer to NULL and puts the original blob value into t.blob.
  

Here are some numbers...

SELECT tblob.reference_count,
       LENGTH ( tblob.blob ) AS length_blob,
       length_blob * ( reference_count - 1 ) AS bytes_saved
  FROM tblob
 ORDER BY bytes_saved DESC,
       length_blob DESC;

reference_count  length_blob  bytes_saved
            101       16,080    1,608,000
          5,801          135      783,000
             87        7,447      640,442
          1,036          575      595,125
            478          962      458,874
          2,270          135      306,315
             53        4,440      230,880
            166          654      107,910
            136          591       79,785
            415          135       55,890
             78          654       50,358
            362          136       49,096
             75          608       44,992
            313          135       42,120
             71          366       25,620
             37          571       20,556
            100          162       16,038
             29          437       12,236
             23          535       11,770
             68          135        9,045
              3        4,343        8,686
             13          644        7,728
             17          366        5,856
              9          577        4,616
             15          314        4,396
              6          805        4,025
              9          474        3,792
              6          566        2,830
              5          605        2,420
              7          357        2,142
              7          355        2,130
              4          581        1,743
             10          174        1,566
              4          451        1,353
              3          584        1,168
              9          119          952
              6          183          915
              3          345          690
              3          328          656
              3          323          646
              2          639          639
              3          317          634
              4          125          375
              2          358          358
              2          303          303
              2          188          188
              2          187          187
              2          136          136
              2          107          107
              1          798            0
              1          340            0
              1          179            0
              1          141            0
              1          110            0

Some parting thoughts...

• 100 bytes might not be a good threshold. There's a lot of overhead here, and it might not be worth it for strings that short.
  

• The whole idea might not be worth it... it depends on your data, and you'll never know until you try it, but if you do go to the trouble of implementing it, don't fall in love with it until you've done some objective performance tests.
  

• Unless you really need tblob.reference_count, the UPDATE on line 34 is pure waste.
  

• The tblob.collision_counter column might also be a waste since it is (almost) always zero. An alternative approach might be to just skip moving the blob into tblob if a collision occurs; i.e., just leave it in t.blob, and don't bother implementing tblob.collision_counter at all.
  

---