jaimeiniesta
Hello!
I have a large postgres table that has a text column called help. Typically this is under 200 chars but there is no length limit on that column.
I need to group by this column, but this is super slow - like 8 seconds or so when there are many rows in the query. Obviously grouping by a text column is not a good choice (unless there’s some performance tip that you can share!), so my approach to optimize this has been adding a new help_key integer column, that contains an integer generated as a hash from that text. Grouping by this column has proved to be much faster (now it’s under 1 second).
Now, what I need is a good way to generate a (reasonably) unique integer from a text so I can ensure that given 2 different texts, the generated integers are different. I don’t need to decode the hash back to the original text, I need is a one-way conversion from text to integer.
I know that theoretically this is not possible but, is there a good way to guarantee a reasonable small chance of collision?
My first attempt for the proof of concept is this function:
@maxint 2_147_483_647
def string_to_integer(str) do
:crypto.hash(:sha, str)
|> :binary.bin_to_list()
|> Enum.with_index()
|> Enum.map(fn {x, i} -> x + i end)
|> Enum.sum()
|> rem(@maxint)
end
Another idea would be having a separate table with an autoincrement id to store the unique texts, but I’m afraid this would take a lot of DB space.
What would you be your approach for this problem?
Where Next?
Trending in Questions
Other Trending Topics
Latest on Elixir Forum
Sponsor Spotlight
Deploy Phoenix to your own VPS with PaaS ease: push-to-deploy, zero downtime, auto SSL, managed Postgres. 14-day free trial at potions.io
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #deployment
- #library
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #elixirconf
- #channels
- #exunit
- #discussion
- #code-sync
- #javascript
- #podcasts
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #elixir-ls
- #blog-post
- #ai
- #elixirconf-us
- #phoenix_html
- #iex
- #graphql
- #genstage
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #api
- #forms
- #hex
- #security
- #metaprogramming
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Error tracking, logs, uptime, and Just Enough APM. Built for developers.
Practical resources that improve the lives of professional developers.
Master modern tools, write cleaner code, and tackle real-world challenges.
Producing high quality Elixir screencasts since 2017.
The team behind Membrane, Popcorn, LiveDebugger. Available for hire.
Courses that'll move you from confusion to "Aha, now I get it!"
Showing Posts 1 to 10- Show Best Posts
- Show All (oldest first)
- Show All (newest first)
tangui
Take a look at
:erlang.phash2/1NobbZ
Have you tried if solving this at the database by adding an index on that column is quick enough?
By relying on the suggested
phash2/1,2, it will be hard to re-apply the technique from another language if necessary later on.jaimeiniesta
Thanks, this looks great. I have to see how I can specify a range larger than integer to minimize change of collisions, though.
jaimeiniesta
I already have this index, that improves searching, but it doesn’t help in grouping:
malaire
Wikipedia has nice table of collision probability given hash size and number of items.
For example with 32 bits hash and 9300 strings there is 1% chance of collision and with 77000 strings 50% chance of collision.
jaimeiniesta
Thanks, I’ll run some checks using the current content we have and see how many collisions there are.
al2o3cr
Nitpick: if
GROUP BYis doing anything useful with these rows, that means you’ve got multiple copies of identical text in the table currently; extracting them to a separate table and referencing them by ID will save space unless your texts are usually shorter than a bigint.NobbZ
Then you loose the ability to edit those texts individually. This might be a requirement, or it might not be…
jaimeiniesta
You’re right, probably the best solution is improving the relational design on those tables.
jaimeiniesta
True. Not in my case, these texts don’t need to be edited. I would need to do some cleanup and remove orphan texts though.