· Nov 6, 2017

How to find duplicates for a large text field in Caché Objects?

Hi, folks!

Suppose you have a Caché class with %String property which contains relatively large text (from 10 to 2000 symbols).

The class:

Class Test.Duplicates Extends %Persistent 


Property Text As %String (MAXLEN = 2000);


And you have thousands of entries.

What are the best options to find entries which are duplicates on this property?

Discussion (26)1
Log in or sign up to continue

Yep, right, looks like Index can't help here and problem not only 511(and this length could be different on different strings).
But, you still can use Index but you should set length which should be stored. But find duplicates you can do without SQL, just by reading this index, it should be much faster, to find, all duplicates by indexed value, and then you can compare real values.

So, the final recipe looks like following:

For Insert and Update calculate the hash e.g. with MD5 and put it in Hash property. Index it with not unique index.

Find duplicates with SQL query on Hash where group by for hash shows more than one occurrence.

Loop through all the values with same hash just and check Text property values to be sure that they are duplicates but not hash collisions.

Thanks, Alex, Dmitry, Robert!

It depends.

If you don't care about uniqueness of this hash, you can use any algorithm (the quicker the better, MD5Hash or even CRC32) and store your index like normal non-unique one. On calculated hash match to already stored (indexed) hash value you just compare the correspondent strings to separate real matches from the collisions. Maybe it's worth to use whole string as an index for reasonably short strings.

having this done ~ 9 yrs back I can't resist to share my old solution (at that time for a UNIQUE on 2000  char)

- split Text into 4 sections in calculated properties e.g.
tx1 = $e(Text,1,500)
tx2 = $e(Text,501,1000) 
tx3 = $e(Text,1001,1500)
tx4 = $e(Text,1501,2000)

- index them
- then you can build an SQL  statement to have all 4 pieces identic.
you end up with a cascade of embedded SELECTS

It's not to fast but very precise.

Class Test.Duplicates Extends %Persistent

Index iText On (Text(KEYS), Text(ELEMENTS)) [ Type = bitmap ];

Property Text As %String(MAXLEN 2000);

ClassMethod TextBuildValueArray(
  ByRef arrAs %Status
  #define sizeOfChunk 400

  i v="" {
    f i=1:1:$l(v)\$$$sizeOfChunk+($l(v)#$$$sizeOfChunk>0) {
      s:hasDupl&&'$d(^Test.DuplicatesI("iText"," "_i,##class(%Collation).SqlUpper(arr(i)))) hasDupl=$$$NO
    s:hasDupl arr("hasDupl")=""
  q $$$OK

ClassMethod Test()
  ;d ##class(Test.Duplicates).Test()

  &sql(insert into Test.Duplicates(Text)
  select 'ab'
  union all select 'abc' union all select 'abc'
  union all select 'abe' union all select 'abe' union all select 'abe'
  union all select null  union all select null
  union all select :text union all select :text)
  d $SYSTEM.SQL.PurgeForTable($classname()),
  sql(1)="select %ID,$extract(Text,1,10) Text10 from Test.Duplicates",
    sql(2)="select * from Test.Duplicates where FOR SOME %ELEMENT(Text) (%KEY='null')",
    sql(3)="select %ID,$extract(Text,1,10) HasDupl_Text10_All from Test.Duplicates where FOR SOME %ELEMENT(Text) (%KEY='hasdupl')",
    sql(4)="select distinct $extract(%exact(Text),1,10) HasDupl_Text10 from Test.Duplicates where FOR SOME %ELEMENT(Text) (%KEY='hasdupl')"
  i=1:1:$o(sql(""),-1) !,sql(i),!! ##class(%SQL.Statement).%ExecDirect(,sql(i)).%Display() !,"---------",!



select %ID,$extract(Text,1,10) Text10 from Test.Duplicates
ID      Text10
1       ab
2       abc
3       abc
4       abe
5       abe
6       abe
9       QfgrABXjbT
10      QfgrABXjbT
10 Rows(s) Affected
select * from Test.Duplicates where FOR SOME %ELEMENT(Text) (%KEY='null')
ID      Text
2 Rows(s) Affected
select %ID,$extract(Text,1,10) HasDupl_Text10_All from Test.Duplicates where FOR SOME %ELEMENT(Text) (%KEY='hasdupl')
ID      HasDupl_Text10_All
3       abc
5       abe
6       abe
10      QfgrABXjbT
4 Rows(s) Affected
select distinct $extract(%exact(Text),1,10) HasDupl_Text10 from Test.Duplicates where FOR SOME %ELEMENT(Text) (%KEY='hasdupl')
3 Rows(s) Affected


  • not used hashing, so there's no risk of collisions
  • support for strings of unlimited length up to 3641144 ($zu(96,39))
  • customizable chunk size
  • minimum code
  • should work for older versions of Caché
  • high performance
  • possible else more optimize code ;)

See Indexing of non-atomic attributes

I would probably go for some extra hashing safety and add a CRC or something similar to the hash. There may be more subtle hashing methods or combinations thereof that will make duplicates "almost impossible" ;)

Class Test.Duplicates Extends %Persistent

Property myText As %String (MAXLEN = 32000);

Property myHash as %String (MAXLEN=50)
 SqlComputeCode={ set {myHash} = $SYSTEM.Encryption.MD5Hash({myText})_"|"_$ZCRC({myText},7)},
 SqlComputeOnChange = (%%INSERT,%%UPDATE,myText)

/// a bitmap would not be worth the effort
Index ixMyHash on myHash;

ClassMethod RunTest(pMax as %Integer = 1000, pDelete as %Boolean = 0)
    write !,"begin "_..%ClassName(1)
        do:pDelete ..%KillExtent()
        for tIdx = 1 : 1 : pMax
            set tRandomStr = ##class(%PopulateUtils).StringMin(100,32000)
            &sql(INSERT INTO Duplicates(myText) VALUES(:tRandomStr))
            write:(tIdx#100=0) !,tIdx_" records inserted"
        write !,"Oops..."
        write !,tEx.DisplayString()

    write !,"end "_..%ClassName(1)


I don't think that checking for duplicates can be solved other than have a reliable index per hash.

Note you can have more subtle hashing (hash sub-pieces, etc.) but you cannot have a reliable hasDuplicate property at runtime that goes beyond the current snapshot of data during INSERT.  IOW, it does not mean much in a system with lots of concurrent access.

In the end if will be 

SELECT COUNT(*) AS CountDuplicates
  FROM Test.Duplicates
 GROUP BY myHash

If you want to avoid duplicates you can make the index unique.