Use of cryolite and fluorspar in electrolytic reduction of pure alumina by Hall-Héroult process
According to the CRC Handbook of Chemistry and Physics, melting point of $\ce{CaF2}$ is $\pu{1418 ^\circ C}$, of $\ce{Al2O3}$ (in its corundum form) is $\pu{2053 ^\circ C}$, and of $\ce{Na3AlF6}$ is $\pu{1009 ^\circ C}$ (lowest of the all three). Thus the cryolite should melt first.
I have read mentions of the problem you asked in the book Nonaqueous Electrochemistry (you can find information about it here. For the best of my summarising ability, I can conclude that the role of the cryolite and other salts added to the reaction mixture is that they decrease the melting point of alumina. As cryolite's melting point is much lower than that of alumina as cited above, when the cryolite melts it acts as a solvent to &quot;dissolve&quot; the $\ce{Al2O3}$, by the process of complexation. Recall how silver chloride dissolves in aqueous ammonia or lead iodide dissolves in excess iodide. The book states that:

Cryolite is used as solvent for alumina because it has high chemical stability and a high solubility for alumina.

In detail:
When pure cryolite ($\ce{Na3AlF6}$) melts, it dissociates into fluoride ions and various lower fluoroaluminates:
$$\ce{[AlF6]^3- -&gt; [AlF4]- + 2 F-}$$
$$\ce{[AlF6]^3- -&gt; [AlF5]^2- + F-}$$
(etc.)
However, in the presence of alumina, the dissociation process is complicated by the fact that the products arise from $\ce{Na3AlF6}$ dissociation can react with $\ce{Al2O3}$ creating oxofluoroaluminates, and it is those complexes that directly get electrolysed (cathodically reduced) rather than the $\ce{Al2O3}$ itself. By various means of calculation and experiments (Raman spectroscopy etc.) they proposed some following reactions (or equilibria):
$$\ce{Al2O3 + 4 [AlF5]^2- -&gt; 3 [Al2OF6]^2- +  2 F-}$$
$$\ce{Al2O3 + [AlF5]^2- + F- -&gt; 3/2 [Al2O2F4]^2-}$$
$$\ce{2 Al2O3 + [Al2O2F4]^2- + 4 F- -&gt; 2 [Al3O4F4]^3-}$$
...
When you add calcium fluoride (or magnesium fluoride) into the mixture, the following reactions also occur:
$$\ce{MgF2 + n F- + (2-n) [AlF5]^2- -&gt; [MgF_{(2+n)}(AlF5)_{(2-n)}]^{(4-n)-} }$$
$$\ce{CaF2 + (3-n) [AlF5]^2- -&gt; [CaF_{n}(AlF5)_{(3-n)}]^{(4-n)-} + (2-n)F-}$$
The electrolytes in the electrolysis process is obviously &quot;$\ce{Na3AlF6}$&quot;, but in fact they always add an excess of $\ce{AlF3}$ alongside other salts such as $\ce{CaF2}$ ($\pu{3-5 \%}$), $\ce{LiF}$ ($\pu{0-4 \%}$) and $\ce{MgF2}$ (also $\pu{0-4 \%}$). In fact, those salts decrease the solubility of $\ce{Al2O3}$ rather than increase it; that's why they only add a little of those salts.
Then why adding those salts?
There are a couple of reasons for this. Firstly, addition of those salts increase the density of the electrolyte. Because aluminium is already produced in the liquid state (melting point $\pu{660 ^\circ C}$), if the density of the two components are too similar, it is impossible to achieve a good separation-by-weight. Kvande and Rorvik had derived an equation of the melt density as a function of temperature and salt composition:
$\pu{d = 2.64 - 0.0008T + 0.18(wt. ratio NaF/AlF_{3}) - 0.008(wt. \% Al_{2}O_{3}) + 0.005(wt. \% CaF_{2}) + 0.008(wt. \% MgF_{2}) - 0.004(wt. \% LiF)}$
As you can see from the above equation density of the mixture increases with CaF2 content.
The other reason is that those salts increase the interfacial tension at the liquid Al-electrolyte boundary. The higher interfacial tension is, the less does aluminium re-dissolve in the electrolyte (yes it can!), thus better current efficiency. For example: at the boundary this reaction occurs: $\ce{Al + 3 NaF -&gt; AlF3 + 3 Na}$. Adding more $\ce{AlF3}$ (or other fluorides) helps surpressing this reaction, and also may increase the $\ce{Na+}$ concentration in the electrolyte - the researchers found that $\ce{Na+}$ ions are the primary charge carriers.